[RTL/NTOSKRNL]
[reactos.git] / reactos / ntoskrnl / mm / ARM3 / miavl.h
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 */