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