1 /* 2 * PROJECT: ReactOS Kernel 3 * LICENSE: BSD - See COPYING.ARM in the top level directory 4 * FILE: ntoskrnl/mm/ARM3/miavl.h 5 * PURPOSE: ARM Memory Manager VAD Node Algorithms 6 * PROGRAMMERS: ReactOS Portable Systems Group 7 */ 8 9 /* INCLUDES ******************************************************************/ 10 11 /* 12 * This is the glue code for the Memory Manager version of AVL Trees that is used 13 * to store the MM_AVL_TABLE for Virtual Address Descriptors (VAD) in the VadRoot 14 * field in EPROCESS. 15 * 16 * In this version of the package, the balance and parent pointers are stored in 17 * the same field as a union (since we know the parent will be at least 8-byte 18 * aligned), saving some space, but requiring special logic to handle setting and 19 * querying the parent and balance. 20 * 21 * The other difference is that the AVL package for Rtl has custom callbacks for 22 * comparison purposes (which would access some internal, opaque, user data) while 23 * the Mm package stores the user-data inline as StartingVpn and EndingVpn. So 24 * when a compare is being made, RtlpAvlCompareRoutine is called, which will either 25 * perform the Mm work, or call the user-specified callback in the Rtl case. 26 */ 27 #define PRTL_AVL_TABLE PMM_AVL_TABLE 28 #define PRTL_BALANCED_LINKS PMMADDRESS_NODE 29 #define MI_ASSERT(x) ASSERT(x) 30 31 /* We need to rename the functions to prevent conflicts when not inlined! */ 32 #define RtlpFindAvlTableNodeOrParent MiFindAvlTableNodeOrParent 33 #define RtlpPromoteAvlTreeNode MiPromoteAvlTreeNode 34 #define RtlpRebalanceAvlTreeNode MiRebalanceAvlTreeNode 35 #define RtlpInsertAvlTreeNode MiInsertAvlTreeNode 36 #define RtlpDeleteAvlTreeNode MiDeleteAvlTreeNode 37 38 /* These are implementation specific */ 39 #define RtlpCopyAvlNodeData MiCopyAvlNodeData 40 #define RtlpAvlCompareRoutine MiAvlCompareRoutine 41 #define RtlSetParent MiSetParent 42 #define RtlSetBalance MiSetBalance 43 #define RtlBalance MiBalance 44 #define RtlParentAvl MiParentAvl 45 #define RtlRightChildAvl MiRightChildAvl 46 #define RtlLeftChildAvl MiLeftChildAvl 47 #define RtlIsLeftChildAvl MiIsLeftChildAvl 48 #define RtlIsRightChildAvl MiIsRightChildAvl 49 #define RtlInsertAsLeftChildAvl MiInsertAsLeftChildAvl 50 #define RtlInsertAsRightChildAvl MiInsertAsRightChildAvl 51 52 FORCEINLINE 53 VOID 54 MiCopyAvlNodeData(IN PRTL_BALANCED_LINKS Node1, 55 IN PRTL_BALANCED_LINKS Node2) 56 { 57 Node1->u1.Parent = Node2->u1.Parent; 58 Node1->LeftChild = Node2->LeftChild; 59 Node1->RightChild = Node2->RightChild; 60 } 61 62 FORCEINLINE 63 RTL_GENERIC_COMPARE_RESULTS 64 MiAvlCompareRoutine(IN PRTL_AVL_TABLE Table, 65 IN PVOID Buffer, 66 IN PVOID UserData) 67 { 68 PRTL_BALANCED_LINKS CurrentNode = (PVOID)((ULONG_PTR)UserData - sizeof(RTL_BALANCED_LINKS)); 69 ULONG_PTR StartingVpn = (ULONG_PTR)Buffer; 70 if (StartingVpn < CurrentNode->StartingVpn) 71 { 72 return GenericLessThan; 73 } 74 else if (StartingVpn <= CurrentNode->EndingVpn) 75 { 76 return GenericEqual; 77 } 78 else 79 { 80 return GenericGreaterThan; 81 } 82 } 83 84 FORCEINLINE 85 VOID 86 MiSetParent(IN PRTL_BALANCED_LINKS Node, 87 IN PRTL_BALANCED_LINKS Parent) 88 { 89 Node->u1.Parent = (PRTL_BALANCED_LINKS)((ULONG_PTR)Parent | (Node->u1.Balance & 0x3)); 90 } 91 92 FORCEINLINE 93 VOID 94 MiSetBalance(IN PRTL_BALANCED_LINKS Node, 95 IN SCHAR Balance) 96 { 97 Node->u1.Balance = Balance; 98 } 99 100 FORCEINLINE 101 SCHAR 102 MiBalance(IN PRTL_BALANCED_LINKS Node) 103 { 104 return (SCHAR)Node->u1.Balance; 105 } 106 107 FORCEINLINE 108 PRTL_BALANCED_LINKS 109 MiParentAvl(IN PRTL_BALANCED_LINKS Node) 110 { 111 return (PRTL_BALANCED_LINKS)((ULONG_PTR)Node->u1.Parent & ~3); 112 } 113 114 FORCEINLINE 115 PRTL_BALANCED_LINKS 116 MiRightChildAvl(IN PRTL_BALANCED_LINKS Node) 117 { 118 return Node->RightChild; 119 } 120 121 FORCEINLINE 122 PRTL_BALANCED_LINKS 123 MiLeftChildAvl(IN PRTL_BALANCED_LINKS Node) 124 { 125 return Node->LeftChild; 126 } 127 128 FORCEINLINE 129 BOOLEAN 130 MiIsLeftChildAvl(IN PRTL_BALANCED_LINKS Node) 131 { 132 return (RtlLeftChildAvl(RtlParentAvl(Node)) == Node); 133 } 134 135 FORCEINLINE 136 BOOLEAN 137 MiIsRightChildAvl(IN PRTL_BALANCED_LINKS Node) 138 { 139 return (RtlRightChildAvl(RtlParentAvl(Node)) == Node); 140 } 141 142 FORCEINLINE 143 VOID 144 MiInsertAsLeftChildAvl(IN PRTL_BALANCED_LINKS Parent, 145 IN PRTL_BALANCED_LINKS Node) 146 { 147 Parent->LeftChild = Node; 148 RtlSetParent(Node, Parent); 149 } 150 151 FORCEINLINE 152 VOID 153 MiInsertAsRightChildAvl(IN PRTL_BALANCED_LINKS Parent, 154 IN PRTL_BALANCED_LINKS Node) 155 { 156 Parent->RightChild = Node; 157 RtlSetParent(Node, Parent); 158 } 159 160 /* EOF */ 161