reactos/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 */