MdePkg/Library/BaseOrderedCollectionRedBlackTreeLib/BaseOrderedCollectionRedBlackTreeLib.c

   1 /** @file
   2   An OrderedCollectionLib instance that provides a red-black tree
   3   implementation, and allocates and releases tree nodes with
   4   MemoryAllocationLib.
   5
   6   This library instance is useful when a fast associative container is needed.
   7   Worst case time complexity is O(log n) for Find(), Next(), Prev(), Min(),
   8   Max(), Insert(), and Delete(), where "n" is the number of elements in the
   9   tree. Complete ordered traversal takes O(n) time.
  10
  11   The implementation is also useful as a fast priority queue.
  12
  13   Copyright (C) 2014, Red Hat, Inc.
  14
  15   This program and the accompanying materials are licensed and made available
  16   under the terms and conditions of the BSD License that accompanies this
  17   distribution. The full text of the license may be found at
  18   http://opensource.org/licenses/bsd-license.php.
  19
  20   THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, WITHOUT
  21   WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
  22 **/
  23
  24 #include <Library/OrderedCollectionLib.h>
  25 #include <Library/DebugLib.h>
  26 #include <Library/MemoryAllocationLib.h>
  27
  28 typedef enum {
  29   RedBlackTreeRed,
  30   RedBlackTreeBlack
  31 } RED_BLACK_TREE_COLOR;
  32
  33 //
  34 // Incomplete types and convenience typedefs are present in the library class
  35 // header. Beside completing the types, we introduce typedefs here that reflect
  36 // the implementation closely.
  37 //
  38 typedef ORDERED_COLLECTION              RED_BLACK_TREE;
  39 typedef ORDERED_COLLECTION_ENTRY        RED_BLACK_TREE_NODE;
  40 typedef ORDERED_COLLECTION_USER_COMPARE RED_BLACK_TREE_USER_COMPARE;
  41 typedef ORDERED_COLLECTION_KEY_COMPARE  RED_BLACK_TREE_KEY_COMPARE;
  42
  43 struct ORDERED_COLLECTION {
  44   RED_BLACK_TREE_NODE         *Root;
  45   RED_BLACK_TREE_USER_COMPARE UserStructCompare;
  46   RED_BLACK_TREE_KEY_COMPARE  KeyCompare;
  47 };
  48
  49 struct ORDERED_COLLECTION_ENTRY {
  50   VOID                 *UserStruct;
  51   RED_BLACK_TREE_NODE  *Parent;
  52   RED_BLACK_TREE_NODE  *Left;
  53   RED_BLACK_TREE_NODE  *Right;
  54   RED_BLACK_TREE_COLOR Color;
  55 };
  56
  57
  58 /**
  59   Retrieve the user structure linked by the specified tree node.
  60
  61   Read-only operation.
  62
  63   @param[in] Node  Pointer to the tree node whose associated user structure we
  64                    want to retrieve. The caller is responsible for passing a
  65                    non-NULL argument.
  66
  67   @return  Pointer to user structure linked by Node.
  68 **/
  69 VOID *
  70 EFIAPI
  71 OrderedCollectionUserStruct (
  72   IN CONST RED_BLACK_TREE_NODE *Node
  73   )
  74 {
  75   return Node->UserStruct;
  76 }
  77
  78
  79 //
  80 // Forward declaration of internal, unit test helper function. See
  81 // specification and function definition later.
  82 //
  83 STATIC
  84 VOID
  85 RedBlackTreeValidate (
  86   IN CONST RED_BLACK_TREE *Tree
  87   );
  88
  89
  90 /**
  91   Allocate and initialize the RED_BLACK_TREE structure.
  92
  93   Allocation occurs via MemoryAllocationLib's AllocatePool() function.
  94
  95   @param[in]  UserStructCompare  This caller-provided function will be used to
  96                                  order two user structures linked into the
  97                                  tree, during the insertion procedure.
  98
  99   @param[in]  KeyCompare         This caller-provided function will be used to
 100                                  order the standalone search key against user
 101                                  structures linked into the tree, during the
 102                                  lookup procedure.
 103
 104   @retval NULL  If allocation failed.
 105
 106   @return       Pointer to the allocated, initialized RED_BLACK_TREE structure,
 107                 otherwise.
 108 **/
 109 RED_BLACK_TREE *
 110 EFIAPI
 111 OrderedCollectionInit (
 112   IN RED_BLACK_TREE_USER_COMPARE UserStructCompare,
 113   IN RED_BLACK_TREE_KEY_COMPARE  KeyCompare
 114   )
 115 {
 116   RED_BLACK_TREE *Tree;
 117
 118   Tree = AllocatePool (sizeof *Tree);
 119   if (Tree == NULL) {
 120     return NULL;
 121   }
 122
 123   Tree->Root              = NULL;
 124   Tree->UserStructCompare = UserStructCompare;
 125   Tree->KeyCompare        = KeyCompare;
 126
 127   if (FeaturePcdGet (PcdValidateOrderedCollection)) {
 128     RedBlackTreeValidate (Tree);
 129   }
 130   return Tree;
 131 }
 132
 133
 134 /**
 135   Check whether the tree is empty (has no nodes).
 136
 137   Read-only operation.
 138
 139   @param[in] Tree  The tree to check for emptiness.
 140
 141   @retval TRUE   The tree is empty.
 142
 143   @retval FALSE  The tree is not empty.
 144 **/
 145 BOOLEAN
 146 EFIAPI
 147 OrderedCollectionIsEmpty (
 148   IN CONST RED_BLACK_TREE *Tree
 149   )
 150 {
 151   return Tree->Root == NULL;
 152 }
 153
 154
 155 /**
 156   Uninitialize and release an empty RED_BLACK_TREE structure.
 157
 158   Read-write operation.
 159
 160   Release occurs via MemoryAllocationLib's FreePool() function.
 161
 162   It is the caller's responsibility to delete all nodes from the tree before
 163   calling this function.
 164
 165   @param[in] Tree  The empty tree to uninitialize and release.
 166 **/
 167 VOID
 168 EFIAPI
 169 OrderedCollectionUninit (
 170   IN RED_BLACK_TREE *Tree
 171   )
 172 {
 173   ASSERT (OrderedCollectionIsEmpty (Tree));
 174   FreePool (Tree);
 175 }
 176
 177
 178 /**
 179   Look up the tree node that links the user structure that matches the
 180   specified standalone key.
 181
 182   Read-only operation.
 183
 184   @param[in] Tree           The tree to search for StandaloneKey.
 185
 186   @param[in] StandaloneKey  The key to locate among the user structures linked
 187                             into Tree. StandaloneKey will be passed to
 188                             Tree->KeyCompare().
 189
 190   @retval NULL  StandaloneKey could not be found.
 191
 192   @return       The tree node that links to the user structure matching
 193                 StandaloneKey, otherwise.
 194 **/
 195 RED_BLACK_TREE_NODE *
 196 EFIAPI
 197 OrderedCollectionFind (
 198   IN CONST RED_BLACK_TREE *Tree,
 199   IN CONST VOID           *StandaloneKey
 200   )
 201 {
 202   RED_BLACK_TREE_NODE *Node;
 203
 204   Node = Tree->Root;
 205   while (Node != NULL) {
 206     INTN Result;
 207
 208     Result = Tree->KeyCompare (StandaloneKey, Node->UserStruct);
 209     if (Result == 0) {
 210       break;
 211     }
 212     Node = (Result < 0) ? Node->Left : Node->Right;
 213   }
 214   return Node;
 215 }
 216
 217
 218 /**
 219   Find the tree node of the minimum user structure stored in the tree.
 220
 221   Read-only operation.
 222
 223   @param[in] Tree  The tree to return the minimum node of. The user structure
 224                    linked by the minimum node compares less than all other user
 225                    structures in the tree.
 226
 227   @retval NULL  If Tree is empty.
 228
 229   @return       The tree node that links the minimum user structure, otherwise.
 230 **/
 231 RED_BLACK_TREE_NODE *
 232 EFIAPI
 233 OrderedCollectionMin (
 234   IN CONST RED_BLACK_TREE *Tree
 235   )
 236 {
 237   RED_BLACK_TREE_NODE *Node;
 238
 239   Node = Tree->Root;
 240   if (Node == NULL) {
 241     return NULL;
 242   }
 243   while (Node->Left != NULL) {
 244     Node = Node->Left;
 245   }
 246   return Node;
 247 }
 248
 249
 250 /**
 251   Find the tree node of the maximum user structure stored in the tree.
 252
 253   Read-only operation.
 254
 255   @param[in] Tree  The tree to return the maximum node of. The user structure
 256                    linked by the maximum node compares greater than all other
 257                    user structures in the tree.
 258
 259   @retval NULL  If Tree is empty.
 260
 261   @return       The tree node that links the maximum user structure, otherwise.
 262 **/
 263 RED_BLACK_TREE_NODE *
 264 EFIAPI
 265 OrderedCollectionMax (
 266   IN CONST RED_BLACK_TREE *Tree
 267   )
 268 {
 269   RED_BLACK_TREE_NODE *Node;
 270
 271   Node = Tree->Root;
 272   if (Node == NULL) {
 273     return NULL;
 274   }
 275   while (Node->Right != NULL) {
 276     Node = Node->Right;
 277   }
 278   return Node;
 279 }
 280
 281
 282 /**
 283   Get the tree node of the least user structure that is greater than the one
 284   linked by Node.
 285
 286   Read-only operation.
 287
 288   @param[in] Node  The node to get the successor node of.
 289
 290   @retval NULL  If Node is NULL, or Node is the maximum node of its containing
 291                 tree (ie. Node has no successor node).
 292
 293   @return       The tree node linking the least user structure that is greater
 294                 than the one linked by Node, otherwise.
 295 **/
 296 RED_BLACK_TREE_NODE *
 297 EFIAPI
 298 OrderedCollectionNext (
 299   IN CONST RED_BLACK_TREE_NODE *Node
 300   )
 301 {
 302   RED_BLACK_TREE_NODE       *Walk;
 303   CONST RED_BLACK_TREE_NODE *Child;
 304
 305   if (Node == NULL) {
 306     return NULL;
 307   }
 308
 309   //
 310   // If Node has a right subtree, then the successor is the minimum node of
 311   // that subtree.
 312   //
 313   Walk = Node->Right;
 314   if (Walk != NULL) {
 315     while (Walk->Left != NULL) {
 316       Walk = Walk->Left;
 317     }
 318     return Walk;
 319   }
 320
 321   //
 322   // Otherwise we have to ascend as long as we're our parent's right child (ie.
 323   // ascending to the left).
 324   //
 325   Child = Node;
 326   Walk = Child->Parent;
 327   while (Walk != NULL && Child == Walk->Right) {
 328     Child = Walk;
 329     Walk = Child->Parent;
 330   }
 331   return Walk;
 332 }
 333
 334
 335 /**
 336   Get the tree node of the greatest user structure that is less than the one
 337   linked by Node.
 338
 339   Read-only operation.
 340
 341   @param[in] Node  The node to get the predecessor node of.
 342
 343   @retval NULL  If Node is NULL, or Node is the minimum node of its containing
 344                 tree (ie. Node has no predecessor node).
 345
 346   @return       The tree node linking the greatest user structure that is less
 347                 than the one linked by Node, otherwise.
 348 **/
 349 RED_BLACK_TREE_NODE *
 350 EFIAPI
 351 OrderedCollectionPrev (
 352   IN CONST RED_BLACK_TREE_NODE *Node
 353   )
 354 {
 355   RED_BLACK_TREE_NODE       *Walk;
 356   CONST RED_BLACK_TREE_NODE *Child;
 357
 358   if (Node == NULL) {
 359     return NULL;
 360   }
 361
 362   //
 363   // If Node has a left subtree, then the predecessor is the maximum node of
 364   // that subtree.
 365   //
 366   Walk = Node->Left;
 367   if (Walk != NULL) {
 368     while (Walk->Right != NULL) {
 369       Walk = Walk->Right;
 370     }
 371     return Walk;
 372   }
 373
 374   //
 375   // Otherwise we have to ascend as long as we're our parent's left child (ie.
 376   // ascending to the right).
 377   //
 378   Child = Node;
 379   Walk = Child->Parent;
 380   while (Walk != NULL && Child == Walk->Left) {
 381     Child = Walk;
 382     Walk = Child->Parent;
 383   }
 384   return Walk;
 385 }
 386
 387
 388 /**
 389   Rotate tree nodes around Pivot to the right.
 390
 391                 Parent                       Parent
 392                   |                            |
 393                 Pivot                      LeftChild
 394                /     .                    .         \_
 395       LeftChild       Node1   --->   Node2           Pivot
 396          . \                                          / .
 397     Node2   LeftRightChild              LeftRightChild   Node1
 398
 399   The ordering Node2 < LeftChild < LeftRightChild < Pivot < Node1 is kept
 400   intact. Parent (if any) is either at the left extreme or the right extreme of
 401   this ordering, and that relation is also kept intact.
 402
 403   Edges marked with a dot (".") don't change during rotation.
 404
 405   Internal read-write operation.
 406
 407   @param[in,out] Pivot    The tree node to rotate other nodes right around. It
 408                           is the caller's responsibility to ensure that
 409                           Pivot->Left is not NULL.
 410
 411   @param[out]    NewRoot  If Pivot has a parent node on input, then the
 412                           function updates Pivot's original parent on output
 413                           according to the rotation, and NewRoot is not
 414                           accessed.
 415
 416                           If Pivot has no parent node on input (ie. Pivot is
 417                           the root of the tree), then the function stores the
 418                           new root node of the tree in NewRoot.
 419 **/
 420 STATIC
 421 VOID
 422 RedBlackTreeRotateRight (
 423   IN OUT RED_BLACK_TREE_NODE *Pivot,
 424   OUT    RED_BLACK_TREE_NODE **NewRoot
 425   )
 426 {
 427   RED_BLACK_TREE_NODE *Parent, *LeftChild, *LeftRightChild;
 428
 429   Parent         = Pivot->Parent;
 430   LeftChild      = Pivot->Left;
 431   LeftRightChild = LeftChild->Right;
 432
 433   Pivot->Left = LeftRightChild;
 434   if (LeftRightChild != NULL) {
 435     LeftRightChild->Parent = Pivot;
 436   }
 437   LeftChild->Parent = Parent;
 438   if (Parent == NULL) {
 439     *NewRoot = LeftChild;
 440   } else {
 441     if (Pivot == Parent->Left) {
 442       Parent->Left = LeftChild;
 443     } else {
 444       Parent->Right = LeftChild;
 445     }
 446   }
 447   LeftChild->Right = Pivot;
 448   Pivot->Parent = LeftChild;
 449 }
 450
 451
 452 /**
 453   Rotate tree nodes around Pivot to the left.
 454
 455           Parent                                 Parent
 456             |                                      |
 457           Pivot                                RightChild
 458          .     \                              /          .
 459     Node1       RightChild    --->       Pivot            Node2
 460                     /.                    . \_
 461       RightLeftChild  Node2          Node1   RightLeftChild
 462
 463   The ordering Node1 < Pivot < RightLeftChild < RightChild < Node2 is kept
 464   intact. Parent (if any) is either at the left extreme or the right extreme of
 465   this ordering, and that relation is also kept intact.
 466
 467   Edges marked with a dot (".") don't change during rotation.
 468
 469   Internal read-write operation.
 470
 471   @param[in,out] Pivot    The tree node to rotate other nodes left around. It
 472                           is the caller's responsibility to ensure that
 473                           Pivot->Right is not NULL.
 474
 475   @param[out]    NewRoot  If Pivot has a parent node on input, then the
 476                           function updates Pivot's original parent on output
 477                           according to the rotation, and NewRoot is not
 478                           accessed.
 479
 480                           If Pivot has no parent node on input (ie. Pivot is
 481                           the root of the tree), then the function stores the
 482                           new root node of the tree in NewRoot.
 483 **/
 484 STATIC
 485 VOID
 486 RedBlackTreeRotateLeft (
 487   IN OUT RED_BLACK_TREE_NODE *Pivot,
 488   OUT    RED_BLACK_TREE_NODE **NewRoot
 489   )
 490 {
 491   RED_BLACK_TREE_NODE *Parent, *RightChild, *RightLeftChild;
 492
 493   Parent         = Pivot->Parent;
 494   RightChild     = Pivot->Right;
 495   RightLeftChild = RightChild->Left;
 496
 497   Pivot->Right = RightLeftChild;
 498   if (RightLeftChild != NULL) {
 499     RightLeftChild->Parent = Pivot;
 500   }
 501   RightChild->Parent = Parent;
 502   if (Parent == NULL) {
 503     *NewRoot = RightChild;
 504   } else {
 505     if (Pivot == Parent->Left) {
 506       Parent->Left = RightChild;
 507     } else {
 508       Parent->Right = RightChild;
 509     }
 510   }
 511   RightChild->Left = Pivot;
 512   Pivot->Parent = RightChild;
 513 }
 514
 515
 516 /**
 517   Insert (link) a user structure into the tree.
 518
 519   Read-write operation.
 520
 521   This function allocates the new tree node with MemoryAllocationLib's
 522   AllocatePool() function.
 523
 524   @param[in,out] Tree        The tree to insert UserStruct into.
 525
 526   @param[out]    Node        The meaning of this optional, output-only
 527                              parameter depends on the return value of the
 528                              function.
 529
 530                              When insertion is successful (RETURN_SUCCESS),
 531                              Node is set on output to the new tree node that
 532                              now links UserStruct.
 533
 534                              When insertion fails due to lack of memory
 535                              (RETURN_OUT_OF_RESOURCES), Node is not changed.
 536
 537                              When insertion fails due to key collision (ie.
 538                              another user structure is already in the tree that
 539                              compares equal to UserStruct), with return value
 540                              RETURN_ALREADY_STARTED, then Node is set on output
 541                              to the node that links the colliding user
 542                              structure. This enables "find-or-insert" in one
 543                              function call, or helps with later removal of the
 544                              colliding element.
 545
 546   @param[in]     UserStruct  The user structure to link into the tree.
 547                              UserStruct is ordered against in-tree user
 548                              structures with the Tree->UserStructCompare()
 549                              function.
 550
 551   @retval RETURN_SUCCESS           Insertion successful. A new tree node has
 552                                    been allocated, linking UserStruct. The new
 553                                    tree node is reported back in Node (if the
 554                                    caller requested it).
 555
 556                                    Existing RED_BLACK_TREE_NODE pointers into
 557                                    Tree remain valid. For example, on-going
 558                                    iterations in the caller can continue with
 559                                    OrderedCollectionNext() /
 560                                    OrderedCollectionPrev(), and they will
 561                                    return the new node at some point if user
 562                                    structure order dictates it.
 563
 564   @retval RETURN_OUT_OF_RESOURCES  AllocatePool() failed to allocate memory for
 565                                    the new tree node. The tree has not been
 566                                    changed. Existing RED_BLACK_TREE_NODE
 567                                    pointers into Tree remain valid.
 568
 569   @retval RETURN_ALREADY_STARTED   A user structure has been found in the tree
 570                                    that compares equal to UserStruct. The node
 571                                    linking the colliding user structure is
 572                                    reported back in Node (if the caller
 573                                    requested it). The tree has not been
 574                                    changed. Existing RED_BLACK_TREE_NODE
 575                                    pointers into Tree remain valid.
 576 **/
 577 RETURN_STATUS
 578 EFIAPI
 579 OrderedCollectionInsert (
 580   IN OUT RED_BLACK_TREE      *Tree,
 581   OUT    RED_BLACK_TREE_NODE **Node      OPTIONAL,
 582   IN     VOID                *UserStruct
 583   )
 584 {
 585   RED_BLACK_TREE_NODE *Tmp, *Parent;
 586   INTN                Result;
 587   RETURN_STATUS       Status;
 588   RED_BLACK_TREE_NODE *NewRoot;
 589
 590   Tmp = Tree->Root;
 591   Parent = NULL;
 592   Result = 0;
 593
 594   //
 595   // First look for a collision, saving the last examined node for the case
 596   // when there's no collision.
 597   //
 598   while (Tmp != NULL) {
 599     Result = Tree->UserStructCompare (UserStruct, Tmp->UserStruct);
 600     if (Result == 0) {
 601       break;
 602     }
 603     Parent = Tmp;
 604     Tmp = (Result < 0) ? Tmp->Left : Tmp->Right;
 605   }
 606
 607   if (Tmp != NULL) {
 608     if (Node != NULL) {
 609       *Node = Tmp;
 610     }
 611     Status = RETURN_ALREADY_STARTED;
 612     goto Done;
 613   }
 614
 615   //
 616   // no collision, allocate a new node
 617   //
 618   Tmp = AllocatePool (sizeof *Tmp);
 619   if (Tmp == NULL) {
 620     Status = RETURN_OUT_OF_RESOURCES;
 621     goto Done;
 622   }
 623   if (Node != NULL) {
 624     *Node = Tmp;
 625   }
 626
 627   //
 628   // reference the user structure from the node
 629   //
 630   Tmp->UserStruct = UserStruct;
 631
 632   //
 633   // Link the node as a child to the correct side of the parent.
 634   // If there's no parent, the new node is the root node in the tree.
 635   //
 636   Tmp->Parent = Parent;
 637   Tmp->Left = NULL;
 638   Tmp->Right = NULL;
 639   if (Parent == NULL) {
 640     Tree->Root = Tmp;
 641     Tmp->Color = RedBlackTreeBlack;
 642     Status = RETURN_SUCCESS;
 643     goto Done;
 644   }
 645   if (Result < 0) {
 646     Parent->Left = Tmp;
 647   } else {
 648     Parent->Right = Tmp;
 649   }
 650   Tmp->Color = RedBlackTreeRed;
 651
 652   //
 653   // Red-black tree properties:
 654   //
 655   // #1 Each node is either red or black (RED_BLACK_TREE_NODE.Color).
 656   //
 657   // #2 Each leaf (ie. a pseudo-node pointed-to by a NULL valued
 658   //    RED_BLACK_TREE_NODE.Left or RED_BLACK_TREE_NODE.Right field) is black.
 659   //
 660   // #3 Each red node has two black children.
 661   //
 662   // #4 For any node N, and for any leaves L1 and L2 reachable from N, the
 663   //    paths N..L1 and N..L2 contain the same number of black nodes.
 664   //
 665   // #5 The root node is black.
 666   //
 667   // By replacing a leaf with a red node above, only property #3 may have been
 668   // broken. (Note that this is the only edge across which property #3 might
 669   // not hold in the entire tree.) Restore property #3.
 670   //
 671
 672   NewRoot = Tree->Root;
 673   while (Tmp != NewRoot && Parent->Color == RedBlackTreeRed) {
 674     RED_BLACK_TREE_NODE *GrandParent, *Uncle;
 675
 676     //
 677     // Tmp is not the root node. Tmp is red. Tmp's parent is red. (Breaking
 678     // property #3.)
 679     //
 680     // Due to property #5, Tmp's parent cannot be the root node, hence Tmp's
 681     // grandparent exists.
 682     //
 683     // Tmp's grandparent is black, because property #3 is only broken between
 684     // Tmp and Tmp's parent.
 685     //
 686     GrandParent = Parent->Parent;
 687
 688     if (Parent == GrandParent->Left) {
 689       Uncle = GrandParent->Right;
 690       if (Uncle != NULL && Uncle->Color == RedBlackTreeRed) {
 691         //
 692         //             GrandParent (black)
 693         //            /                   \_
 694         // Parent (red)                    Uncle (red)
 695         //      |
 696         //  Tmp (red)
 697         //
 698
 699         Parent->Color = RedBlackTreeBlack;
 700         Uncle->Color = RedBlackTreeBlack;
 701         GrandParent->Color = RedBlackTreeRed;
 702
 703         //
 704         //                GrandParent (red)
 705         //               /                 \_
 706         // Parent (black)                   Uncle (black)
 707         //       |
 708         //   Tmp (red)
 709         //
 710         // We restored property #3 between Tmp and Tmp's parent, without
 711         // breaking property #4. However, we may have broken property #3
 712         // between Tmp's grandparent and Tmp's great-grandparent (if any), so
 713         // repeat the loop for Tmp's grandparent.
 714         //
 715         // If Tmp's grandparent has no parent, then the loop will terminate,
 716         // and we will have broken property #5, by coloring the root red. We'll
 717         // restore property #5 after the loop, without breaking any others.
 718         //
 719         Tmp = GrandParent;
 720         Parent = Tmp->Parent;
 721       } else {
 722         //
 723         // Tmp's uncle is black (satisfied by the case too when Tmp's uncle is
 724         // NULL, see property #2).
 725         //
 726
 727         if (Tmp == Parent->Right) {
 728           //
 729           //                 GrandParent (black): D
 730           //                /                      \_
 731           // Parent (red): A                        Uncle (black): E
 732           //      \_
 733           //       Tmp (red): B
 734           //            \_
 735           //             black: C
 736           //
 737           // Rotate left, pivoting on node A. This keeps the breakage of
 738           // property #3 in the same spot, and keeps other properties intact
 739           // (because both Tmp and its parent are red).
 740           //
 741           Tmp = Parent;
 742           RedBlackTreeRotateLeft (Tmp, &NewRoot);
 743           Parent = Tmp->Parent;
 744
 745           //
 746           // With the rotation we reached the same configuration as if Tmp had
 747           // been a left child to begin with.
 748           //
 749           //                       GrandParent (black): D
 750           //                      /                      \_
 751           //       Parent (red): B                        Uncle (black): E
 752           //             / \_
 753           // Tmp (red): A   black: C
 754           //
 755           ASSERT (GrandParent == Parent->Parent);
 756         }
 757
 758         Parent->Color = RedBlackTreeBlack;
 759         GrandParent->Color = RedBlackTreeRed;
 760
 761         //
 762         // Property #3 is now restored, but we've broken property #4. Namely,
 763         // paths going through node E now see a decrease in black count, while
 764         // paths going through node B don't.
 765         //
 766         //                        GrandParent (red): D
 767         //                       /                    \_
 768         //      Parent (black): B                      Uncle (black): E
 769         //             / \_
 770         // Tmp (red): A   black: C
 771         //
 772
 773         RedBlackTreeRotateRight (GrandParent, &NewRoot);
 774
 775         //
 776         // Property #4 has been restored for node E, and preserved for others.
 777         //
 778         //              Parent (black): B
 779         //             /                 \_
 780         // Tmp (red): A                   [GrandParent] (red): D
 781         //                                         / \_
 782         //                                 black: C   [Uncle] (black): E
 783         //
 784         // This configuration terminates the loop because Tmp's parent is now
 785         // black.
 786         //
 787       }
 788     } else {
 789       //
 790       // Symmetrical to the other branch.
 791       //
 792       Uncle = GrandParent->Left;
 793       if (Uncle != NULL && Uncle->Color == RedBlackTreeRed) {
 794         Parent->Color = RedBlackTreeBlack;
 795         Uncle->Color = RedBlackTreeBlack;
 796         GrandParent->Color = RedBlackTreeRed;
 797         Tmp = GrandParent;
 798         Parent = Tmp->Parent;
 799       } else {
 800         if (Tmp == Parent->Left) {
 801           Tmp = Parent;
 802           RedBlackTreeRotateRight (Tmp, &NewRoot);
 803           Parent = Tmp->Parent;
 804           ASSERT (GrandParent == Parent->Parent);
 805         }
 806         Parent->Color = RedBlackTreeBlack;
 807         GrandParent->Color = RedBlackTreeRed;
 808         RedBlackTreeRotateLeft (GrandParent, &NewRoot);
 809       }
 810     }
 811   }
 812
 813   NewRoot->Color = RedBlackTreeBlack;
 814   Tree->Root = NewRoot;
 815   Status = RETURN_SUCCESS;
 816
 817 Done:
 818   if (FeaturePcdGet (PcdValidateOrderedCollection)) {
 819     RedBlackTreeValidate (Tree);
 820   }
 821   return Status;
 822 }
 823
 824
 825 /**
 826   Check if a node is black, allowing for leaf nodes (see property #2).
 827
 828   This is a convenience shorthand.
 829
 830   param[in] Node  The node to check. Node may be NULL, corresponding to a leaf.
 831
 832   @return  If Node is NULL or colored black.
 833 **/
 834
 835 STATIC
 836 BOOLEAN
 837 NodeIsNullOrBlack (
 838   IN CONST RED_BLACK_TREE_NODE *Node
 839   )
 840 {
 841   return Node == NULL || Node->Color == RedBlackTreeBlack;
 842 }
 843
 844
 845 /**
 846   Delete a node from the tree, unlinking the associated user structure.
 847
 848   Read-write operation.
 849
 850   @param[in,out] Tree        The tree to delete Node from.
 851
 852   @param[in]     Node        The tree node to delete from Tree. The caller is
 853                              responsible for ensuring that Node belongs to
 854                              Tree, and that Node is non-NULL and valid. Node is
 855                              typically an earlier return value, or output
 856                              parameter, of:
 857
 858                              - OrderedCollectionFind(), for deleting a node by
 859                                user structure key,
 860
 861                              - OrderedCollectionMin() / OrderedCollectionMax(),
 862                                for deleting the minimum / maximum node,
 863
 864                              - OrderedCollectionNext() /
 865                                OrderedCollectionPrev(), for deleting a node
 866                                found during an iteration,
 867
 868                              - OrderedCollectionInsert() with return value
 869                                RETURN_ALREADY_STARTED, for deleting a node
 870                                whose linked user structure caused collision
 871                                during insertion.
 872
 873                              Given a non-empty Tree, Tree->Root is also a valid
 874                              Node argument (typically used for simplicity in
 875                              loops that empty the tree completely).
 876
 877                              Node is released with MemoryAllocationLib's
 878                              FreePool() function.
 879
 880                              Existing RED_BLACK_TREE_NODE pointers (ie.
 881                              iterators) *different* from Node remain valid. For
 882                              example:
 883
 884                              - OrderedCollectionNext() /
 885                                OrderedCollectionPrev() iterations in the caller
 886                                can be continued from Node, if
 887                                OrderedCollectionNext() or
 888                                OrderedCollectionPrev() is called on Node
 889                                *before* OrderedCollectionDelete() is. That is,
 890                                fetch the successor / predecessor node first,
 891                                then delete Node.
 892
 893                              - On-going iterations in the caller that would
 894                                have otherwise returned Node at some point, as
 895                                dictated by user structure order, will correctly
 896                                reflect the absence of Node after
 897                                OrderedCollectionDelete() is called
 898                                mid-iteration.
 899
 900   @param[out]    UserStruct  If the caller provides this optional output-only
 901                              parameter, then on output it is set to the user
 902                              structure originally linked by Node (which is now
 903                              freed).
 904
 905                              This is a convenience that may save the caller a
 906                              OrderedCollectionUserStruct() invocation before
 907                              calling OrderedCollectionDelete(), in order to
 908                              retrieve the user structure being unlinked.
 909 **/
 910 VOID
 911 EFIAPI
 912 OrderedCollectionDelete (
 913   IN OUT RED_BLACK_TREE      *Tree,
 914   IN     RED_BLACK_TREE_NODE *Node,
 915   OUT    VOID                **UserStruct OPTIONAL
 916   )
 917 {
 918   RED_BLACK_TREE_NODE  *NewRoot;
 919   RED_BLACK_TREE_NODE  *OrigLeftChild, *OrigRightChild, *OrigParent;
 920   RED_BLACK_TREE_NODE  *Child, *Parent;
 921   RED_BLACK_TREE_COLOR ColorOfUnlinked;
 922
 923   NewRoot        = Tree->Root;
 924   OrigLeftChild  = Node->Left,
 925   OrigRightChild = Node->Right,
 926   OrigParent     = Node->Parent;
 927
 928   if (UserStruct != NULL) {
 929     *UserStruct = Node->UserStruct;
 930   }
 931
 932   //
 933   // After this block, no matter which branch we take:
 934   // - Child will point to the unique (or NULL) original child of the node that
 935   //   we will have unlinked,
 936   // - Parent will point to the *position* of the original parent of the node
 937   //   that we will have unlinked.
 938   //
 939   if (OrigLeftChild == NULL || OrigRightChild == NULL) {
 940     //
 941     // Node has at most one child. We can connect that child (if any) with
 942     // Node's parent (if any), unlinking Node. This will preserve ordering
 943     // because the subtree rooted in Node's child (if any) remains on the same
 944     // side of Node's parent (if any) that Node was before.
 945     //
 946     Parent = OrigParent;
 947     Child = (OrigLeftChild != NULL) ? OrigLeftChild : OrigRightChild;
 948     ColorOfUnlinked = Node->Color;
 949
 950     if (Child != NULL) {
 951       Child->Parent = Parent;
 952     }
 953     if (OrigParent == NULL) {
 954       NewRoot = Child;
 955     } else {
 956       if (Node == OrigParent->Left) {
 957         OrigParent->Left = Child;
 958       } else {
 959         OrigParent->Right = Child;
 960       }
 961     }
 962   } else {
 963     //
 964     // Node has two children. We unlink Node's successor, and then link it into
 965     // Node's place, keeping Node's original color. This preserves ordering
 966     // because:
 967     // - Node's left subtree is less than Node, hence less than Node's
 968     //   successor.
 969     // - Node's right subtree is greater than Node. Node's successor is the
 970     //   minimum of that subtree, hence Node's successor is less than Node's
 971     //   right subtree with its minimum removed.
 972     // - Node's successor is in Node's subtree, hence it falls on the same side
 973     //   of Node's parent as Node itself. The relinking doesn't change this
 974     //   relation.
 975     //
 976     RED_BLACK_TREE_NODE *ToRelink;
 977
 978     ToRelink = OrigRightChild;
 979     if (ToRelink->Left == NULL) {
 980       //
 981       // OrigRightChild itself is Node's successor, it has no left child:
 982       //
 983       //                OrigParent
 984       //                    |
 985       //                  Node: B
 986       //                 /       \_
 987       // OrigLeftChild: A         OrigRightChild: E <--- Parent, ToRelink
 988       //                                           \_
 989       //                                            F <--- Child
 990       //
 991       Parent = OrigRightChild;
 992       Child = OrigRightChild->Right;
 993     } else {
 994       do {
 995         ToRelink = ToRelink->Left;
 996       } while (ToRelink->Left != NULL);
 997
 998       //
 999       // Node's successor is the minimum of OrigRightChild's proper subtree:
1000       //
1001       //                OrigParent
1002       //                    |
1003       //                  Node: B
1004       //                 /       \_
1005       // OrigLeftChild: A         OrigRightChild: E <--- Parent
1006       //                                  /
1007       //                                 C <--- ToRelink
1008       //                                  \_
1009       //                                   D <--- Child
1010       Parent = ToRelink->Parent;
1011       Child = ToRelink->Right;
1012
1013       //
1014       // Unlink Node's successor (ie. ToRelink):
1015       //
1016       //                OrigParent
1017       //                    |
1018       //                  Node: B
1019       //                 /       \_
1020       // OrigLeftChild: A         OrigRightChild: E <--- Parent
1021       //                                  /
1022       //                                 D <--- Child
1023       //
1024       //                                 C <--- ToRelink
1025       //
1026       Parent->Left = Child;
1027       if (Child) {
1028         Child->Parent = Parent;
1029       }
1030
1031       //
1032       // We start to link Node's unlinked successor into Node's place:
1033       //
1034       //                OrigParent
1035       //                    |
1036       //                  Node: B     C <--- ToRelink
1037       //                 /             \_
1038       // OrigLeftChild: A               OrigRightChild: E <--- Parent
1039       //                                        /
1040       //                                       D <--- Child
1041       //
1042       //
1043       //
1044       ToRelink->Right = OrigRightChild;
1045       OrigRightChild->Parent = ToRelink;
1046     }
1047
1048     //
1049     // The rest handles both cases, attaching ToRelink (Node's original
1050     // successor) to OrigLeftChild and OrigParent.
1051     //
1052     //                           Parent,
1053     //              OrigParent   ToRelink             OrigParent
1054     //                  |        |                        |
1055     //                Node: B    |                      Node: B          Parent
1056     //                           v                                          |
1057     //           OrigRightChild: E                        C <--- ToRelink   |
1058     //                 / \                               / \                v
1059     // OrigLeftChild: A   F              OrigLeftChild: A   OrigRightChild: E
1060     //                    ^                                         /
1061     //                    |                                        D <--- Child
1062     //                  Child
1063     //
1064     ToRelink->Left = OrigLeftChild;
1065     OrigLeftChild->Parent = ToRelink;
1066
1067     //
1068     // Node's color must be preserved in Node's original place.
1069     //
1070     ColorOfUnlinked = ToRelink->Color;
1071     ToRelink->Color = Node->Color;
1072
1073     //
1074     // Finish linking Node's unlinked successor into Node's place.
1075     //
1076     //                           Parent,
1077     //                Node: B    ToRelink               Node: B
1078     //                           |
1079     //              OrigParent   |                    OrigParent         Parent
1080     //                  |        v                        |                 |
1081     //           OrigRightChild: E                        C <--- ToRelink   |
1082     //                 / \                               / \                v
1083     // OrigLeftChild: A   F              OrigLeftChild: A   OrigRightChild: E
1084     //                    ^                                         /
1085     //                    |                                        D <--- Child
1086     //                  Child
1087     //
1088     ToRelink->Parent = OrigParent;
1089     if (OrigParent == NULL) {
1090       NewRoot = ToRelink;
1091     } else {
1092       if (Node == OrigParent->Left) {
1093         OrigParent->Left = ToRelink;
1094       } else {
1095         OrigParent->Right = ToRelink;
1096       }
1097     }
1098   }
1099
1100   FreePool (Node);
1101
1102   //
1103   // If the node that we unlinked from its original spot (ie. Node itself, or
1104   // Node's successor), was red, then we broke neither property #3 nor property
1105   // #4: we didn't create any red-red edge between Child and Parent, and we
1106   // didn't change the black count on any path.
1107   //
1108   if (ColorOfUnlinked == RedBlackTreeBlack) {
1109     //
1110     // However, if the unlinked node was black, then we have to transfer its
1111     // "black-increment" to its unique child (pointed-to by Child), lest we
1112     // break property #4 for its ancestors.
1113     //
1114     // If Child is red, we can simply color it black. If Child is black
1115     // already, we can't technically transfer a black-increment to it, due to
1116     // property #1.
1117     //
1118     // In the following loop we ascend searching for a red node to color black,
1119     // or until we reach the root (in which case we can drop the
1120     // black-increment). Inside the loop body, Child has a black value of 2,
1121     // transitorily breaking property #1 locally, but maintaining property #4
1122     // globally.
1123     //
1124     // Rotations in the loop preserve property #4.
1125     //
1126     while (Child != NewRoot && NodeIsNullOrBlack (Child)) {
1127       RED_BLACK_TREE_NODE *Sibling, *LeftNephew, *RightNephew;
1128
1129       if (Child == Parent->Left) {
1130         Sibling = Parent->Right;
1131         //
1132         // Sibling can never be NULL (ie. a leaf).
1133         //
1134         // If Sibling was NULL, then the black count on the path from Parent to
1135         // Sibling would equal Parent's black value, plus 1 (due to property
1136         // #2). Whereas the black count on the path from Parent to any leaf via
1137         // Child would be at least Parent's black value, plus 2 (due to Child's
1138         // black value of 2). This would clash with property #4.
1139         //
1140         // (Sibling can be black of course, but it has to be an internal node.
1141         // Internality allows Sibling to have children, bumping the black
1142         // counts of paths that go through it.)
1143         //
1144         ASSERT (Sibling != NULL);
1145         if (Sibling->Color == RedBlackTreeRed) {
1146           //
1147           // Sibling's red color implies its children (if any), node C and node
1148           // E, are black (property #3). It also implies that Parent is black.
1149           //
1150           //           grandparent                                 grandparent
1151           //                |                                           |
1152           //            Parent,b:B                                     b:D
1153           //           /          \                                   /   \_
1154           // Child,2b:A            Sibling,r:D  --->        Parent,r:B     b:E
1155           //                           /\                       /\_
1156           //                        b:C  b:E          Child,2b:A  Sibling,b:C
1157           //
1158           Sibling->Color = RedBlackTreeBlack;
1159           Parent->Color = RedBlackTreeRed;
1160           RedBlackTreeRotateLeft (Parent, &NewRoot);
1161           Sibling = Parent->Right;
1162           //
1163           // Same reasoning as above.
1164           //
1165           ASSERT (Sibling != NULL);
1166         }
1167
1168         //
1169         // Sibling is black, and not NULL. (Ie. Sibling is a black internal
1170         // node.)
1171         //
1172         ASSERT (Sibling->Color == RedBlackTreeBlack);
1173         LeftNephew = Sibling->Left;
1174         RightNephew = Sibling->Right;
1175         if (NodeIsNullOrBlack (LeftNephew) &&
1176             NodeIsNullOrBlack (RightNephew)) {
1177           //
1178           // In this case we can "steal" one black value from Child and Sibling
1179           // each, and pass it to Parent. "Stealing" means that Sibling (black
1180           // value 1) becomes red, Child (black value 2) becomes singly-black,
1181           // and Parent will have to be examined if it can eat the
1182           // black-increment.
1183           //
1184           // Sibling is allowed to become red because both of its children are
1185           // black (property #3).
1186           //
1187           //           grandparent                             Parent
1188           //                |                                     |
1189           //            Parent,x:B                            Child,x:B
1190           //           /          \                          /         \_
1191           // Child,2b:A            Sibling,b:D    --->    b:A           r:D
1192           //                           /\                                /\_
1193           //             LeftNephew,b:C  RightNephew,b:E              b:C  b:E
1194           //
1195           Sibling->Color = RedBlackTreeRed;
1196           Child = Parent;
1197           Parent = Parent->Parent;
1198           //
1199           // Continue ascending.
1200           //
1201         } else {
1202           //
1203           // At least one nephew is red.
1204           //
1205           if (NodeIsNullOrBlack (RightNephew)) {
1206             //
1207             // Since the right nephew is black, the left nephew is red. Due to
1208             // property #3, LeftNephew has two black children, hence node E is
1209             // black.
1210             //
1211             // Together with the rotation, this enables us to color node F red
1212             // (because property #3 will be satisfied). We flip node D to black
1213             // to maintain property #4.
1214             //
1215             //      grandparent                         grandparent
1216             //           |                                   |
1217             //       Parent,x:B                          Parent,x:B
1218             //           /\                                  /\_
1219             // Child,2b:A  Sibling,b:F     --->    Child,2b:A  Sibling,b:D
1220             //                  /\                            /   \_
1221             //    LeftNephew,r:D  RightNephew,b:G          b:C  RightNephew,r:F
1222             //               /\                                       /\_
1223             //            b:C  b:E                                 b:E  b:G
1224             //
1225             LeftNephew->Color = RedBlackTreeBlack;
1226             Sibling->Color = RedBlackTreeRed;
1227             RedBlackTreeRotateRight (Sibling, &NewRoot);
1228             Sibling = Parent->Right;
1229             RightNephew = Sibling->Right;
1230             //
1231             // These operations ensure that...
1232             //
1233           }
1234           //
1235           // ... RightNephew is definitely red here, plus Sibling is (still)
1236           // black and non-NULL.
1237           //
1238           ASSERT (RightNephew != NULL);
1239           ASSERT (RightNephew->Color == RedBlackTreeRed);
1240           ASSERT (Sibling != NULL);
1241           ASSERT (Sibling->Color == RedBlackTreeBlack);
1242           //
1243           // In this case we can flush the extra black-increment immediately,
1244           // restoring property #1 for Child (node A): we color RightNephew
1245           // (node E) from red to black.
1246           //
1247           // In order to maintain property #4, we exchange colors between
1248           // Parent and Sibling (nodes B and D), and rotate left around Parent
1249           // (node B). The transformation doesn't change the black count
1250           // increase incurred by each partial path, eg.
1251           // - ascending from node A: 2 + x     == 1 + 1 + x
1252           // - ascending from node C: y + 1 + x == y + 1 + x
1253           // - ascending from node E: 0 + 1 + x == 1 + x
1254           //
1255           // The color exchange is valid, because even if x stands for red,
1256           // both children of node D are black after the transformation
1257           // (preserving property #3).
1258           //
1259           //           grandparent                                  grandparent
1260           //                |                                            |
1261           //            Parent,x:B                                      x:D
1262           //           /          \                                    /   \_
1263           // Child,2b:A            Sibling,b:D              --->    b:B     b:E
1264           //                         /     \                       /   \_
1265           //                      y:C       RightNephew,r:E     b:A     y:C
1266           //
1267           //
1268           Sibling->Color = Parent->Color;
1269           Parent->Color = RedBlackTreeBlack;
1270           RightNephew->Color = RedBlackTreeBlack;
1271           RedBlackTreeRotateLeft (Parent, &NewRoot);
1272           Child = NewRoot;
1273           //
1274           // This terminates the loop.
1275           //
1276         }
1277       } else {
1278         //
1279         // Mirrors the other branch.
1280         //
1281         Sibling = Parent->Left;
1282         ASSERT (Sibling != NULL);
1283         if (Sibling->Color == RedBlackTreeRed) {
1284           Sibling->Color = RedBlackTreeBlack;
1285           Parent->Color = RedBlackTreeRed;
1286           RedBlackTreeRotateRight (Parent, &NewRoot);
1287           Sibling = Parent->Left;
1288           ASSERT (Sibling != NULL);
1289         }
1290
1291         ASSERT (Sibling->Color == RedBlackTreeBlack);
1292         RightNephew = Sibling->Right;
1293         LeftNephew = Sibling->Left;
1294         if (NodeIsNullOrBlack (RightNephew) &&
1295             NodeIsNullOrBlack (LeftNephew)) {
1296           Sibling->Color = RedBlackTreeRed;
1297           Child = Parent;
1298           Parent = Parent->Parent;
1299         } else {
1300           if (NodeIsNullOrBlack (LeftNephew)) {
1301             RightNephew->Color = RedBlackTreeBlack;
1302             Sibling->Color = RedBlackTreeRed;
1303             RedBlackTreeRotateLeft (Sibling, &NewRoot);
1304             Sibling = Parent->Left;
1305             LeftNephew = Sibling->Left;
1306           }
1307           ASSERT (LeftNephew != NULL);
1308           ASSERT (LeftNephew->Color == RedBlackTreeRed);
1309           ASSERT (Sibling != NULL);
1310           ASSERT (Sibling->Color == RedBlackTreeBlack);
1311           Sibling->Color = Parent->Color;
1312           Parent->Color = RedBlackTreeBlack;
1313           LeftNephew->Color = RedBlackTreeBlack;
1314           RedBlackTreeRotateRight (Parent, &NewRoot);
1315           Child = NewRoot;
1316         }
1317       }
1318     }
1319
1320     if (Child != NULL) {
1321       Child->Color = RedBlackTreeBlack;
1322     }
1323   }
1324
1325   Tree->Root = NewRoot;
1326
1327   if (FeaturePcdGet (PcdValidateOrderedCollection)) {
1328     RedBlackTreeValidate (Tree);
1329   }
1330 }
1331
1332
1333 /**
1334   Recursively check the red-black tree properties #1 to #4 on a node.
1335
1336   @param[in] Node  The root of the subtree to validate.
1337
1338   @retval  The black-height of Node's parent.
1339 **/
1340 STATIC
1341 UINT32
1342 RedBlackTreeRecursiveCheck (
1343   IN CONST RED_BLACK_TREE_NODE *Node
1344   )
1345 {
1346   UINT32 LeftHeight, RightHeight;
1347
1348   //
1349   // property #2
1350   //
1351   if (Node == NULL) {
1352     return 1;
1353   }
1354
1355   //
1356   // property #1
1357   //
1358   ASSERT (Node->Color == RedBlackTreeRed || Node->Color == RedBlackTreeBlack);
1359
1360   //
1361   // property #3
1362   //
1363   if (Node->Color == RedBlackTreeRed) {
1364     ASSERT (NodeIsNullOrBlack (Node->Left));
1365     ASSERT (NodeIsNullOrBlack (Node->Right));
1366   }
1367
1368   //
1369   // property #4
1370   //
1371   LeftHeight = RedBlackTreeRecursiveCheck (Node->Left);
1372   RightHeight = RedBlackTreeRecursiveCheck (Node->Right);
1373   ASSERT (LeftHeight == RightHeight);
1374
1375   return (Node->Color == RedBlackTreeBlack) + LeftHeight;
1376 }
1377
1378
1379 /**
1380   A slow function that asserts that the tree is a valid red-black tree, and
1381   that it orders user structures correctly.
1382
1383   Read-only operation.
1384
1385   This function uses the stack for recursion and is not recommended for
1386   "production use".
1387
1388   @param[in] Tree  The tree to validate.
1389 **/
1390 STATIC
1391 VOID
1392 RedBlackTreeValidate (
1393   IN CONST RED_BLACK_TREE *Tree
1394   )
1395 {
1396   UINT32                    BlackHeight;
1397   UINT32                    ForwardCount, BackwardCount;
1398   CONST RED_BLACK_TREE_NODE *Last, *Node;
1399
1400   DEBUG ((DEBUG_VERBOSE, "%a: Tree=%p\n", __FUNCTION__, Tree));
1401
1402   //
1403   // property #5
1404   //
1405   ASSERT (NodeIsNullOrBlack (Tree->Root));
1406
1407   //
1408   // check the other properties
1409   //
1410   BlackHeight = RedBlackTreeRecursiveCheck (Tree->Root) - 1;
1411
1412   //
1413   // forward ordering
1414   //
1415   Last = OrderedCollectionMin (Tree);
1416   ForwardCount = (Last != NULL);
1417   for (Node = OrderedCollectionNext (Last); Node != NULL;
1418        Node = OrderedCollectionNext (Last)) {
1419     ASSERT (Tree->UserStructCompare (Last->UserStruct, Node->UserStruct) < 0);
1420     Last = Node;
1421     ++ForwardCount;
1422   }
1423
1424   //
1425   // backward ordering
1426   //
1427   Last = OrderedCollectionMax (Tree);
1428   BackwardCount = (Last != NULL);
1429   for (Node = OrderedCollectionPrev (Last); Node != NULL;
1430        Node = OrderedCollectionPrev (Last)) {
1431     ASSERT (Tree->UserStructCompare (Last->UserStruct, Node->UserStruct) > 0);
1432     Last = Node;
1433     ++BackwardCount;
1434   }
1435
1436   ASSERT (ForwardCount == BackwardCount);
1437
1438   DEBUG ((DEBUG_VERBOSE, "%a: Tree=%p BlackHeight=%Ld Count=%Ld\n",
1439     __FUNCTION__, Tree, (INT64)BlackHeight, (INT64)ForwardCount));
1440 }