Sync with trunk (48237)
[reactos.git] / 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 VOID
32 FORCEINLINE
33 RtlpCopyAvlNodeData(IN PRTL_BALANCED_LINKS Node1,
34 IN PRTL_BALANCED_LINKS Node2)
35 {
36 Node1->u1.Parent = Node2->u1.Parent;
37 Node1->LeftChild = Node2->LeftChild;
38 Node1->RightChild = Node2->RightChild;
39 }
40
41 RTL_GENERIC_COMPARE_RESULTS
42 FORCEINLINE
43 RtlpAvlCompareRoutine(IN PRTL_AVL_TABLE Table,
44 IN PVOID Buffer,
45 IN PVOID UserData)
46 {
47 PRTL_BALANCED_LINKS CurrentNode = (PVOID)((ULONG_PTR)UserData - sizeof(LIST_ENTRY) - sizeof(RTL_BALANCED_LINKS));
48 ULONG_PTR StartingVpn = (ULONG_PTR)Buffer;
49 if (StartingVpn < CurrentNode->StartingVpn)
50 {
51 return GenericLessThan;
52 }
53 else if (StartingVpn <= CurrentNode->EndingVpn)
54 {
55 return GenericEqual;
56 }
57 else
58 {
59 return GenericGreaterThan;
60 }
61 }
62
63 VOID
64 FORCEINLINE
65 RtlSetParent(IN PRTL_BALANCED_LINKS Node,
66 IN PRTL_BALANCED_LINKS Parent)
67 {
68 Node->u1.Parent = (PRTL_BALANCED_LINKS)((ULONG_PTR)Parent | (Node->u1.Balance & 0x3));
69 }
70
71 VOID
72 FORCEINLINE
73 RtlSetBalance(IN PRTL_BALANCED_LINKS Node,
74 IN SCHAR Balance)
75 {
76 Node->u1.Balance = Balance;
77 }
78
79 SCHAR
80 FORCEINLINE
81 RtlBalance(IN PRTL_BALANCED_LINKS Node)
82 {
83 return Node->u1.Balance;
84 }
85
86 PRTL_BALANCED_LINKS
87 FORCEINLINE
88 RtlParentAvl(IN PRTL_BALANCED_LINKS Node)
89 {
90 return (PRTL_BALANCED_LINKS)((ULONG_PTR)Node->u1.Parent & ~3);
91 }
92
93 BOOLEAN
94 FORCEINLINE
95 RtlIsRootAvl(IN PRTL_BALANCED_LINKS Node)
96 {
97 return (RtlParentAvl(Node) == Node);
98 }
99
100 PRTL_BALANCED_LINKS
101 FORCEINLINE
102 RtlRightChildAvl(IN PRTL_BALANCED_LINKS Node)
103 {
104 return Node->RightChild;
105 }
106
107 PRTL_BALANCED_LINKS
108 FORCEINLINE
109 RtlLeftChildAvl(IN PRTL_BALANCED_LINKS Node)
110 {
111 return Node->LeftChild;
112 }
113
114 BOOLEAN
115 FORCEINLINE
116 RtlIsLeftChildAvl(IN PRTL_BALANCED_LINKS Node)
117 {
118 return (RtlLeftChildAvl(RtlParentAvl(Node)) == Node);
119 }
120
121 BOOLEAN
122 FORCEINLINE
123 RtlIsRightChildAvl(IN PRTL_BALANCED_LINKS Node)
124 {
125 return (RtlRightChildAvl(RtlParentAvl(Node)) == Node);
126 }
127
128 VOID
129 FORCEINLINE
130 RtlInsertAsLeftChildAvl(IN PRTL_BALANCED_LINKS Parent,
131 IN PRTL_BALANCED_LINKS Node)
132 {
133 Parent->LeftChild = Node;
134 RtlSetParent(Node, Parent);
135 }
136
137 VOID
138 FORCEINLINE
139 RtlInsertAsRightChildAvl(IN PRTL_BALANCED_LINKS Parent,
140 IN PRTL_BALANCED_LINKS Node)
141 {
142 Parent->RightChild = Node;
143 RtlSetParent(Node, Parent);
144 }
145
146 /* EOF */