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
9 /* INCLUDES ******************************************************************/
11 /* Internal header for table entries */
12 typedef struct _TABLE_ENTRY_HEADER
14 RTL_BALANCED_LINKS BalancedLinks
;
16 } TABLE_ENTRY_HEADER
, *PTABLE_ENTRY_HEADER
;
18 typedef enum _RTL_AVL_BALANCE_FACTOR
20 RtlUnbalancedAvlTree
= -2,
24 } RTL_AVL_BALANCE_FACTOR
;
26 C_ASSERT(RtlBalancedAvlTree
== 0);
28 /* FUNCTIONS ******************************************************************/
32 RtlpFindAvlTableNodeOrParent(IN PRTL_AVL_TABLE Table
,
34 OUT PRTL_BALANCED_LINKS
*NodeOrParent
)
36 PRTL_BALANCED_LINKS CurrentNode
, ChildNode
;
37 RTL_GENERIC_COMPARE_RESULTS Result
;
39 /* Quick check to see if the table is empty */
40 if (!Table
->NumberGenericTableElements
) return TableEmptyTree
;
42 /* Set the current node */
43 CurrentNode
= RtlRightChildAvl(&Table
->BalancedRoot
);
45 /* Start compare loop */
48 /* Compare which side is greater */
49 Result
= RtlpAvlCompareRoutine(Table
,
51 &((PTABLE_ENTRY_HEADER
)CurrentNode
)->
53 if (Result
== GenericLessThan
)
55 /* We're less, check if this is the left child */
56 ChildNode
= RtlLeftChildAvl(CurrentNode
);
59 /* Continue searching from this node */
60 CurrentNode
= ChildNode
;
64 /* Otherwise, the element isn't in this tree */
65 *NodeOrParent
= CurrentNode
;
66 return TableInsertAsLeft
;
69 else if (Result
== GenericGreaterThan
)
71 /* We're more, check if this is the right child */
72 ChildNode
= RtlRightChildAvl(CurrentNode
);
75 /* Continue searching from this node */
76 CurrentNode
= ChildNode
;
80 /* Otherwise, the element isn't in this tree */
81 *NodeOrParent
= CurrentNode
;
82 return TableInsertAsRight
;
87 /* We should've found the node */
88 ASSERT(Result
== GenericEqual
);
90 /* Return node found */
91 *NodeOrParent
= CurrentNode
;
92 return TableFoundNode
;
99 RtlpPromoteAvlTreeNode(IN PRTL_BALANCED_LINKS Node
)
101 PRTL_BALANCED_LINKS ParentNode
, SuperParentNode
;
102 PRTL_BALANCED_LINKS
*SwapNode1
, *SwapNode2
;
104 /* Grab parents up to 2 levels high */
105 ParentNode
= RtlParentAvl(Node
);
106 SuperParentNode
= RtlParentAvl(ParentNode
);
108 /* Pick which nodes will be rotated */
109 SwapNode1
= RtlIsLeftChildAvl(Node
) ? &ParentNode
->LeftChild
: &ParentNode
->RightChild
;
110 SwapNode2
= RtlIsLeftChildAvl(Node
) ? &Node
->RightChild
: &Node
->LeftChild
;
112 /* Do the rotate, and update the parent and super-parent as needed */
113 *SwapNode1
= *SwapNode2
;
114 if (*SwapNode1
) RtlSetParent(*SwapNode1
, ParentNode
);
115 *SwapNode2
= ParentNode
;
116 RtlSetParent(ParentNode
, Node
);
118 /* Now update the super-parent child link, and make it parent of the node*/
119 SwapNode1
= (RtlLeftChildAvl(SuperParentNode
) == ParentNode
) ?
120 &SuperParentNode
->LeftChild
: &SuperParentNode
->RightChild
;
122 RtlSetParent(Node
, SuperParentNode
);
127 RtlpRebalanceAvlTreeNode(IN PRTL_BALANCED_LINKS Node
)
129 PRTL_BALANCED_LINKS ChildNode
, SubChildNode
;
131 ASSERT(RtlParentAvl(Node
) != Node
);
133 /* Get the balance, and figure out which child node to go down on */
134 Balance
= RtlBalance(Node
);
135 ChildNode
= (Balance
== RtlRightHeavyAvlTree
) ?
136 RtlRightChildAvl(Node
) : RtlLeftChildAvl(Node
);
138 /* The child and node have the same balance, promote the child upwards */
139 if (RtlBalance(ChildNode
) == Balance
)
141 /* This performs the rotation described in Knuth A8-A10 for Case 1 */
142 RtlpPromoteAvlTreeNode(ChildNode
);
144 /* The nodes are now balanced */
145 RtlSetBalance(ChildNode
, RtlBalancedAvlTree
);
146 RtlSetBalance(Node
, RtlBalancedAvlTree
);
150 /* The child has the opposite balance, a double promotion of the child's child must happen */
151 if (RtlBalance(ChildNode
) == -Balance
)
153 /* Pick which sub-child to use based on the balance */
154 SubChildNode
= (Balance
== RtlRightHeavyAvlTree
) ?
155 RtlLeftChildAvl(ChildNode
) : RtlRightChildAvl(ChildNode
);
157 /* Do the double-rotation described in Knuth A8-A10 for Case 2 */
158 RtlpPromoteAvlTreeNode(SubChildNode
);
159 RtlpPromoteAvlTreeNode(SubChildNode
);
161 /* Was the sub-child sharing the same balance as the node? */
162 if (RtlBalance(SubChildNode
) == Balance
)
164 /* Then the subchild is now balanced, and the node's weight is inversed */
165 RtlSetBalance(ChildNode
, RtlBalancedAvlTree
);
166 RtlSetBalance(Node
, -Balance
);
168 else if (RtlBalance(SubChildNode
) == -Balance
)
171 * In this case, the sub-child weight was the inverse of the node, so
172 * the child now shares the node's balance original weight, while the
173 * node becomes balanced.
175 RtlSetBalance(ChildNode
, Balance
);
176 RtlSetBalance(Node
, RtlBalancedAvlTree
);
181 * Otherwise, the sub-child was unbalanced, so both the child and node
182 * now become balanced.
184 RtlSetBalance(ChildNode
, RtlBalancedAvlTree
);
185 RtlSetBalance(Node
, RtlBalancedAvlTree
);
188 /* In all cases, the sub-child is now balanced */
189 RtlSetBalance(SubChildNode
, RtlBalancedAvlTree
);
194 * The case that remains is that the child was already balanced, so this is
195 * This is the rotation required for Case 3 in Knuth A8-A10
197 RtlpPromoteAvlTreeNode(ChildNode
);
199 /* Now the child has the opposite weight of the node */
200 RtlSetBalance(ChildNode
, -Balance
);
202 /* This only happens on deletion, so we return TRUE to terminate the delete */
208 RtlpInsertAvlTreeNode(IN PRTL_AVL_TABLE Table
,
209 IN PRTL_BALANCED_LINKS NewNode
,
210 IN OUT PVOID NodeOrParent
,
211 IN OUT TABLE_SEARCH_RESULT SearchResult
)
215 /* Initialize the new inserted element */
216 MI_ASSERT(SearchResult
!= TableFoundNode
);
217 NewNode
->LeftChild
= NewNode
->RightChild
= NULL
;
218 RtlSetBalance(NewNode
, RtlBalancedAvlTree
);
220 /* Increase element count */
221 Table
->NumberGenericTableElements
++;
223 /* Check where we should insert the entry */
224 if (SearchResult
== TableEmptyTree
)
226 /* This is the new root node */
227 RtlInsertAsRightChildAvl(&Table
->BalancedRoot
, NewNode
);
229 /* On AVL trees, we also update the depth */
230 ASSERT(Table
->DepthOfTree
== 0);
231 Table
->DepthOfTree
= 1;
234 else if (SearchResult
== TableInsertAsLeft
)
237 RtlInsertAsLeftChildAvl(NodeOrParent
, NewNode
);
242 RtlInsertAsRightChildAvl(NodeOrParent
, NewNode
);
245 /* Little cheat to save on loop processing, taken from Timo */
246 RtlSetBalance(&Table
->BalancedRoot
, RtlLeftHeavyAvlTree
);
249 * This implements A6-A7 from Knuth based on http://coding.derkeiler.com
250 * /pdf/Archive/C_CPP/comp.lang.c/2004-01/1812.pdf, however the algorithm
251 * is slightly modified to follow the tree based on the Parent Node such
252 * as the Windows algorithm does it, instead of following the nodes down.
256 /* Calculate which side to balance on */
257 Balance
= RtlIsLeftChildAvl(NewNode
) ? RtlLeftHeavyAvlTree
: RtlRightHeavyAvlTree
;
259 /* Check if the parent node was balanced */
260 if (RtlBalance(NodeOrParent
) == RtlBalancedAvlTree
)
262 /* It's not balanced anymore (heavy on one side) */
263 RtlSetBalance(NodeOrParent
, Balance
);
266 NewNode
= NodeOrParent
;
267 NodeOrParent
= RtlParentAvl(NodeOrParent
);
269 else if (RtlBalance(NodeOrParent
) != Balance
)
271 /* The parent's balance is opposite, so the tree is balanced now */
272 RtlSetBalance(NodeOrParent
, RtlBalancedAvlTree
);
274 /* Check if this is the root (the cheat applied earlier gets us here) */
275 if (RtlBalance(&Table
->BalancedRoot
) == RtlBalancedAvlTree
)
277 /* The depth has thus increased */
278 Table
->DepthOfTree
++;
281 /* We reached the root or a balanced node, so we're done */
286 /* The tree is now unbalanced, so AVL rebalancing must happen */
287 RtlpRebalanceAvlTreeNode(NodeOrParent
);
295 RtlpDeleteAvlTreeNode(IN PRTL_AVL_TABLE Table
,
296 IN PRTL_BALANCED_LINKS Node
)
298 PRTL_BALANCED_LINKS DeleteNode
= NULL
, ParentNode
;
299 PRTL_BALANCED_LINKS
*Node1
, *Node2
;
302 /* Take one of the children if possible */
303 if (!(RtlLeftChildAvl(Node
)) || !(RtlRightChildAvl(Node
))) DeleteNode
= Node
;
305 /* Otherwise, check if one side is longer */
306 if (!(DeleteNode
) && (RtlBalance(Node
) >= RtlBalancedAvlTree
))
308 /* Pick the successor which will be the longest side in this case */
309 DeleteNode
= RtlRightChildAvl(Node
);
310 while (RtlLeftChildAvl(DeleteNode
)) DeleteNode
= RtlLeftChildAvl(DeleteNode
);
312 else if (!DeleteNode
)
314 /* Pick the predecessor which will be the longest side in this case */
315 DeleteNode
= RtlLeftChildAvl(Node
);
316 while (RtlRightChildAvl(DeleteNode
)) DeleteNode
= RtlRightChildAvl(DeleteNode
);
319 /* Get the parent node */
320 ParentNode
= RtlParentAvl(DeleteNode
);
321 DPRINT("Parent: %p\n", ParentNode
);
323 /* Pick which now to use based on whether or not we have a left child */
324 Node1
= RtlLeftChildAvl(DeleteNode
) ? &DeleteNode
->LeftChild
: &DeleteNode
->RightChild
;
325 DPRINT("Node 1: %p %p\n", Node1
, *Node1
);
327 /* Pick which node to swap based on if we're already a left child or not */
328 Node2
= RtlIsLeftChildAvl(DeleteNode
) ? &ParentNode
->LeftChild
: &ParentNode
->RightChild
;
329 DPRINT("Node 2: %p %p\n", Node2
, *Node2
);
331 /* Pick the correct balance depending on which side will get heavier */
332 Balance
= RtlIsLeftChildAvl(DeleteNode
) ? RtlLeftHeavyAvlTree
: RtlRightHeavyAvlTree
;
333 DPRINT("Balance: %lx\n", Balance
);
335 /* Swap the children nodes, making one side heavier */
338 /* If the node has a child now, update its parent */
339 if (*Node1
) RtlSetParent(*Node1
, ParentNode
);
341 /* Assume balanced root for loop optimization */
342 RtlSetBalance(&Table
->BalancedRoot
, RtlBalancedAvlTree
);
344 /* Loop up the tree by parents */
347 /* Check if the tree's balance increased */
348 if (RtlBalance(ParentNode
) == Balance
)
350 /* Now the tree is balanced */
351 RtlSetBalance(ParentNode
, RtlBalancedAvlTree
);
353 else if (RtlBalance(ParentNode
) == RtlBalancedAvlTree
)
355 /* The tree has now become less balanced, since it was balanced */
356 RtlSetBalance(ParentNode
, -Balance
);
358 /* Deal with the loop optimization to detect loss of a tree level */
359 if (RtlBalance(&Table
->BalancedRoot
) != RtlBalancedAvlTree
) Table
->DepthOfTree
--;
364 /* The tree has become unbalanced, so a rebalance is needed */
365 if (RtlpRebalanceAvlTreeNode(ParentNode
)) break;
367 /* Get the new parent after the balance */
368 ParentNode
= RtlParentAvl(ParentNode
);
371 /* Choose which balance factor to use based on which side we're on */
372 Balance
= RtlIsRightChild(ParentNode
) ?
373 RtlRightHeavyAvlTree
: RtlLeftHeavyAvlTree
;
375 /* Iterate up the tree */
376 ParentNode
= RtlParentAvl(ParentNode
);
379 /* Check if this isn't the node we ended up deleting directly */
380 if (Node
== DeleteNode
) return;
382 /* Copy the deleted node itself */
383 RtlpCopyAvlNodeData(DeleteNode
, Node
);
385 /* Pick the right node to unlink */
386 Node1
= RtlIsLeftChildAvl(Node
) ?
387 &(RtlParentAvl(DeleteNode
))->LeftChild
: &(RtlParentAvl(DeleteNode
))->RightChild
;
390 /* Reparent as appropriate */
391 if (RtlLeftChildAvl(DeleteNode
)) RtlSetParent(RtlLeftChildAvl(DeleteNode
), DeleteNode
);
392 if (RtlRightChildAvl(DeleteNode
)) RtlSetParent(RtlRightChildAvl(DeleteNode
), DeleteNode
);