Sync with trunk (48237)
[reactos.git] / lib / rtl / avlsupp.c
1 /*
2 * PROJECT: ReactOS Runtime Library
3 * LICENSE: BSD - See COPYING.ARM in the top level directory
4 * FILE: lib/rtl/avlsupp.c
5 * PURPOSE: AVL Tree Internal Support Routines/Main Algorithms
6 * PROGRAMMERS: ReactOS Portable Systems Group
7 */
8
9 /* INCLUDES ******************************************************************/
10
11 /* Internal header for table entries */
12 typedef struct _TABLE_ENTRY_HEADER
13 {
14 RTL_BALANCED_LINKS BalancedLinks;
15 LIST_ENTRY ListEntry;
16 LONGLONG UserData;
17 } TABLE_ENTRY_HEADER, *PTABLE_ENTRY_HEADER;
18
19 typedef enum _RTL_AVL_BALANCE_FACTOR
20 {
21 RtlUnbalancedAvlTree = -2,
22 RtlLeftHeavyAvlTree,
23 RtlBalancedAvlTree,
24 RtlRightHeavyAvlTree,
25 } RTL_AVL_BALANCE_FACTOR;
26
27 C_ASSERT(RtlBalancedAvlTree == 0);
28
29 /* FUNCTIONS ******************************************************************/
30
31 TABLE_SEARCH_RESULT
32 FORCEINLINE
33 RtlpFindAvlTableNodeOrParent(IN PRTL_AVL_TABLE Table,
34 IN PVOID Buffer,
35 OUT PRTL_BALANCED_LINKS *NodeOrParent)
36 {
37 PRTL_BALANCED_LINKS CurrentNode, ChildNode;
38 RTL_GENERIC_COMPARE_RESULTS Result;
39
40 /* Quick check to see if the table is empty */
41 if (!Table->NumberGenericTableElements) return TableEmptyTree;
42
43 /* Set the current node */
44 CurrentNode = RtlRightChildAvl(&Table->BalancedRoot);
45
46 /* Start compare loop */
47 while (TRUE)
48 {
49 /* Compare which side is greater */
50 Result = RtlpAvlCompareRoutine(Table,
51 Buffer,
52 &((PTABLE_ENTRY_HEADER)CurrentNode)->
53 UserData);
54 if (Result == GenericLessThan)
55 {
56 /* We're less, check if this is the left child */
57 ChildNode = RtlLeftChildAvl(CurrentNode);
58 if (ChildNode)
59 {
60 /* Continue searching from this node */
61 CurrentNode = ChildNode;
62 }
63 else
64 {
65 /* Otherwise, the element isn't in this tree */
66 *NodeOrParent = CurrentNode;
67 return TableInsertAsLeft;
68 }
69 }
70 else if (Result == GenericGreaterThan)
71 {
72 /* We're more, check if this is the right child */
73 ChildNode = RtlRightChildAvl(CurrentNode);
74 if (ChildNode)
75 {
76 /* Continue searching from this node */
77 CurrentNode = ChildNode;
78 }
79 else
80 {
81 /* Otherwise, the element isn't in this tree */
82 *NodeOrParent = CurrentNode;
83 return TableInsertAsRight;
84 }
85 }
86 else
87 {
88 /* We should've found the node */
89 ASSERT(Result == GenericEqual);
90
91 /* Return node found */
92 *NodeOrParent = CurrentNode;
93 return TableFoundNode;
94 }
95 }
96 }
97
98 VOID
99 FORCEINLINE
100 RtlPromoteAvlTreeNode(IN PRTL_BALANCED_LINKS Node)
101 {
102 PRTL_BALANCED_LINKS ParentNode, SuperParentNode;
103 PRTL_BALANCED_LINKS *SwapNode1, *SwapNode2;
104
105 /* Grab parents up to 2 levels high */
106 ParentNode = RtlParentAvl(Node);
107 SuperParentNode = RtlParentAvl(ParentNode);
108
109 /* Pick which nodes will be rotated */
110 SwapNode1 = RtlIsLeftChildAvl(Node) ? &ParentNode->LeftChild : &ParentNode->RightChild;
111 SwapNode2 = RtlIsLeftChildAvl(Node) ? &Node->RightChild : &Node->LeftChild;
112
113 /* Do the rotate, and update the parent and super-parent as needed */
114 *SwapNode1 = *SwapNode2;
115 if (*SwapNode1) RtlSetParent(*SwapNode1, ParentNode);
116 *SwapNode2 = ParentNode;
117 RtlSetParent(ParentNode, Node);
118
119 /* Now update the super-parent child link, and make it parent of the node*/
120 SwapNode1 = (RtlLeftChildAvl(SuperParentNode) == ParentNode) ?
121 &SuperParentNode->LeftChild: &SuperParentNode->RightChild;
122 *SwapNode1 = Node;
123 RtlSetParent(Node, SuperParentNode);
124 }
125
126 BOOLEAN
127 FORCEINLINE
128 RtlpRebalanceAvlTreeNode(IN PRTL_BALANCED_LINKS Node)
129 {
130 PRTL_BALANCED_LINKS ChildNode, SubChildNode;
131 CHAR Balance;
132 ASSERT(RtlParentAvl(Node) != Node);
133
134 /* Get the balance, and figure out which child node to go down on */
135 Balance = RtlBalance(Node);
136 ChildNode = (Balance == RtlRightHeavyAvlTree) ?
137 RtlRightChildAvl(Node) : RtlLeftChildAvl(Node);
138
139 /* The child and node have the same balance, promote the child upwards */
140 if (RtlBalance(ChildNode) == Balance)
141 {
142 /* This performs the rotation described in Knuth A8-A10 for Case 1 */
143 RtlPromoteAvlTreeNode(ChildNode);
144
145 /* The nodes are now balanced */
146 RtlSetBalance(ChildNode, RtlBalancedAvlTree);
147 RtlSetBalance(Node, RtlBalancedAvlTree);
148 return FALSE;
149 }
150
151 /* The child has the opposite balance, a double promotion of the child's child must happen */
152 if (RtlBalance(ChildNode) == -Balance)
153 {
154 /* Pick which sub-child to use based on the balance */
155 SubChildNode = (Balance == RtlRightHeavyAvlTree) ?
156 RtlLeftChildAvl(ChildNode) : RtlRightChildAvl(ChildNode);
157
158 /* Do the double-rotation described in Knuth A8-A10 for Case 2 */
159 RtlPromoteAvlTreeNode(SubChildNode);
160 RtlPromoteAvlTreeNode(SubChildNode);
161
162 /* Was the sub-child sharing the same balance as the node? */
163 if (RtlBalance(SubChildNode) == Balance)
164 {
165 /* Then the subchild is now balanced, and the node's weight is inversed */
166 RtlSetBalance(ChildNode, RtlBalancedAvlTree);
167 RtlSetBalance(Node, -Balance);
168 }
169 else if (RtlBalance(SubChildNode) == -Balance)
170 {
171 /*
172 * In this case, the sub-child weight was the inverse of the node, so
173 * the child now shares the node's balance original weight, while the
174 * node becomes balanced.
175 */
176 RtlSetBalance(ChildNode, Balance);
177 RtlSetBalance(Node, RtlBalancedAvlTree);
178 }
179 else
180 {
181 /*
182 * Otherwise, the sub-child was unbalanced, so both the child and node
183 * now become balanced.
184 */
185 RtlSetBalance(ChildNode, RtlBalancedAvlTree);
186 RtlSetBalance(Node, RtlBalancedAvlTree);
187 }
188
189 /* In all cases, the sub-child is now balanced */
190 RtlSetBalance(SubChildNode, RtlBalancedAvlTree);
191 return FALSE;
192 }
193
194 /*
195 * The case that remains is that the child was already balanced, so this is
196 * This is the rotation required for Case 3 in Knuth A8-A10
197 */
198 RtlPromoteAvlTreeNode(ChildNode);
199
200 /* Now the child has the opposite weight of the node */
201 RtlSetBalance(ChildNode, -Balance);
202
203 /* This only happens on deletion, so we return TRUE to terminate the delete */
204 return TRUE;
205 }
206
207 VOID
208 FORCEINLINE
209 RtlpInsertAvlTreeNode(IN PRTL_AVL_TABLE Table,
210 IN PRTL_BALANCED_LINKS NewNode,
211 IN OUT PVOID NodeOrParent,
212 IN OUT TABLE_SEARCH_RESULT SearchResult)
213 {
214 CHAR Balance;
215
216 /* Initialize the new inserted element */
217 MI_ASSERT(SearchResult != TableFoundNode);
218 NewNode->LeftChild = NewNode->RightChild = NULL;
219
220 /* Increase element count */
221 Table->NumberGenericTableElements++;
222
223 /* Check where we should insert the entry */
224 if (SearchResult == TableEmptyTree)
225 {
226 /* This is the new root node */
227 RtlInsertAsRightChildAvl(&Table->BalancedRoot, NewNode);
228 MI_ASSERT(RtlBalance(NewNode) == RtlBalancedAvlTree);
229
230 /* On AVL trees, we also update the depth */
231 ASSERT(Table->DepthOfTree == 0);
232 Table->DepthOfTree = 1;
233 return;
234 }
235 else if (SearchResult == TableInsertAsLeft)
236 {
237 /* Insert it left */
238 RtlInsertAsLeftChildAvl(NodeOrParent, NewNode);
239 }
240 else
241 {
242 /* Right node */
243 RtlInsertAsRightChildAvl(NodeOrParent, NewNode);
244 }
245
246 /* Little cheat to save on loop processing, taken from Timo */
247 MI_ASSERT(RtlBalance(NewNode) == RtlBalancedAvlTree);
248 RtlSetBalance(&Table->BalancedRoot, RtlLeftHeavyAvlTree);
249
250 /*
251 * This implements A6-A7 from Knuth based on http://coding.derkeiler.com
252 * /pdf/Archive/C_CPP/comp.lang.c/2004-01/1812.pdf, however the algorithm
253 * is slightly modified to follow the tree based on the Parent Node such
254 * as the Windows algorithm does it, instead of following the nodes down.
255 */
256 while (TRUE)
257 {
258 /* Calculate which side to balance on */
259 Balance = RtlIsLeftChildAvl(NewNode) ? RtlLeftHeavyAvlTree : RtlRightHeavyAvlTree;
260
261 /* Check if the parent node was balanced */
262 if (RtlBalance(NodeOrParent) == RtlBalancedAvlTree)
263 {
264 /* It's not balanced anymore (heavy on one side) */
265 RtlSetBalance(NodeOrParent, Balance);
266
267 /* Move up */
268 NewNode = NodeOrParent;
269 NodeOrParent = RtlParentAvl(NodeOrParent);
270 }
271 else if (RtlBalance(NodeOrParent) != Balance)
272 {
273 /* The parent's balance is opposite, so the tree is balanced now */
274 RtlSetBalance(NodeOrParent, RtlBalancedAvlTree);
275
276 /* Check if this is the root (the cheat applied earlier gets us here) */
277 if (RtlBalance(&Table->BalancedRoot) == RtlBalancedAvlTree)
278 {
279 /* The depth has thus increased */
280 Table->DepthOfTree++;
281 }
282
283 /* We reached the root or a balanced node, so we're done */
284 break;
285 }
286 else
287 {
288 /* The tree is now unbalanced, so AVL rebalancing must happen */
289 RtlpRebalanceAvlTreeNode(NodeOrParent);
290 break;
291 }
292 }
293 }
294
295 VOID
296 FORCEINLINE
297 RtlpDeleteAvlTreeNode(IN PRTL_AVL_TABLE Table,
298 IN PRTL_BALANCED_LINKS Node)
299 {
300 PRTL_BALANCED_LINKS DeleteNode = NULL, ParentNode;
301 PRTL_BALANCED_LINKS *Node1, *Node2;
302 CHAR Balance;
303
304 /* Take one of the children if possible */
305 if (!(RtlLeftChildAvl(Node)) || !(RtlRightChildAvl(Node))) DeleteNode = Node;
306
307 /* Otherwise, check if one side is longer */
308 if (!(DeleteNode) && (RtlBalance(Node) >= RtlBalancedAvlTree))
309 {
310 /* Pick the successor which will be the longest side in this case */
311 DeleteNode = RtlRightChildAvl(Node);
312 while (RtlLeftChildAvl(DeleteNode)) DeleteNode = RtlLeftChildAvl(DeleteNode);
313 }
314 else if (!DeleteNode)
315 {
316 /* Pick the predecessor which will be the longest side in this case */
317 DeleteNode = RtlLeftChildAvl(Node);
318 while (RtlRightChildAvl(DeleteNode)) DeleteNode = RtlRightChildAvl(DeleteNode);
319 }
320
321 /* Get the parent node */
322 ParentNode = RtlParentAvl(DeleteNode);
323 DPRINT("Parent: %p\n", ParentNode);
324
325 /* Pick which now to use based on whether or not we have a left child */
326 Node1 = RtlLeftChildAvl(DeleteNode) ? &DeleteNode->LeftChild : &DeleteNode->RightChild;
327 DPRINT("Node 1: %p %p\n", Node1, *Node1);
328
329 /* Pick which node to swap based on if we're already a left child or not */
330 Node2 = RtlIsLeftChildAvl(DeleteNode) ? &ParentNode->LeftChild : &ParentNode->RightChild;
331 DPRINT("Node 2: %p %p\n", Node2, *Node2);
332
333 /* Pick the correct balance depending on which side will get heavier */
334 Balance = RtlIsLeftChildAvl(DeleteNode) ? RtlLeftHeavyAvlTree : RtlRightHeavyAvlTree;
335 DPRINT("Balance: %lx\n", Balance);
336
337 /* Swap the children nodes, making one side heavier */
338 *Node2 = *Node1;
339
340 /* If the node has a child now, update its parent */
341 if (*Node1) RtlSetParent(*Node1, ParentNode);
342
343 /* Assume balanced root for loop optimization */
344 RtlSetBalance(&Table->BalancedRoot, RtlBalancedAvlTree);
345
346 /* Loop up the tree by parents */
347 while (TRUE)
348 {
349 /* Check if the tree's balance increased */
350 if (RtlBalance(ParentNode) == Balance)
351 {
352 /* Now the tree is balanced */
353 RtlSetBalance(ParentNode, RtlBalancedAvlTree);
354 }
355 else if (RtlBalance(ParentNode) == RtlBalancedAvlTree)
356 {
357 /* The tree has now become less balanced, since it was balanced */
358 RtlSetBalance(ParentNode, -Balance);
359
360 /* Deal with the loop optimization to detect loss of a tree level */
361 if (RtlBalance(&Table->BalancedRoot) != RtlBalancedAvlTree) Table->DepthOfTree--;
362 break;
363 }
364 else
365 {
366 /* The tree has become unbalanced, so a rebalance is needed */
367 if (RtlpRebalanceAvlTreeNode(ParentNode)) break;
368
369 /* Get the new parent after the balance */
370 ParentNode = RtlParentAvl(ParentNode);
371 }
372
373 /* Choose which balance factor to use based on which side we're on */
374 Balance = RtlIsRightChild(ParentNode) ?
375 RtlRightHeavyAvlTree : RtlLeftHeavyAvlTree;
376
377 /* Iterate up the tree */
378 ParentNode = RtlParentAvl(ParentNode);
379 }
380
381 /* Check if this isn't the node we ended up deleting directly */
382 if (Node == DeleteNode) return;
383
384 /* Copy the deleted node itself */
385 RtlpCopyAvlNodeData(DeleteNode, Node);
386
387 /* Pick the right node to unlink */
388 Node1 = RtlIsLeftChildAvl(Node) ?
389 &(RtlParentAvl(DeleteNode))->LeftChild : &(RtlParentAvl(DeleteNode))->RightChild;
390 *Node1 = DeleteNode;
391
392 /* Reparent as appropriate */
393 if (RtlLeftChildAvl(DeleteNode)) RtlSetParent(RtlLeftChildAvl(DeleteNode), DeleteNode);
394 if (RtlRightChildAvl(DeleteNode)) RtlSetParent(RtlRightChildAvl(DeleteNode), DeleteNode);
395 }
396
397 /* EOF */