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
 593   //
 594   // First look for a collision, saving the last examined node for the case
 595   // when there's no collision.
 596   //
 597   while (Tmp != NULL) {
 598     Result = Tree->UserStructCompare (UserStruct, Tmp->UserStruct);
 599     if (Result == 0) {
 600       break;
 601     }
 602     Parent = Tmp;
 603     Tmp = (Result < 0) ? Tmp->Left : Tmp->Right;
 604   }
 605
 606   if (Tmp != NULL) {
 607     if (Node != NULL) {
 608       *Node = Tmp;
 609     }
 610     Status = RETURN_ALREADY_STARTED;
 611     goto Done;
 612   }
 613
 614   //
 615   // no collision, allocate a new node
 616   //
 617   Tmp = AllocatePool (sizeof *Tmp);
 618   if (Tmp == NULL) {
 619     Status = RETURN_OUT_OF_RESOURCES;
 620     goto Done;
 621   }
 622   if (Node != NULL) {
 623     *Node = Tmp;
 624   }
 625
 626   //
 627   // reference the user structure from the node
 628   //
 629   Tmp->UserStruct = UserStruct;
 630
 631   //
 632   // Link the node as a child to the correct side of the parent.
 633   // If there's no parent, the new node is the root node in the tree.
 634   //
 635   Tmp->Parent = Parent;
 636   Tmp->Left = NULL;
 637   Tmp->Right = NULL;
 638   if (Parent == NULL) {
 639     Tree->Root = Tmp;
 640     Tmp->Color = RedBlackTreeBlack;
 641     Status = RETURN_SUCCESS;
 642     goto Done;
 643   }
 644   if (Result < 0) {
 645     Parent->Left = Tmp;
 646   } else {
 647     Parent->Right = Tmp;
 648   }
 649   Tmp->Color = RedBlackTreeRed;
 650
 651   //
 652   // Red-black tree properties:
 653   //
 654   // #1 Each node is either red or black (RED_BLACK_TREE_NODE.Color).
 655   //
 656   // #2 Each leaf (ie. a pseudo-node pointed-to by a NULL valued
 657   //    RED_BLACK_TREE_NODE.Left or RED_BLACK_TREE_NODE.Right field) is black.
 658   //
 659   // #3 Each red node has two black children.
 660   //
 661   // #4 For any node N, and for any leaves L1 and L2 reachable from N, the
 662   //    paths N..L1 and N..L2 contain the same number of black nodes.
 663   //
 664   // #5 The root node is black.
 665   //
 666   // By replacing a leaf with a red node above, only property #3 may have been
 667   // broken. (Note that this is the only edge across which property #3 might
 668   // not hold in the entire tree.) Restore property #3.
 669   //
 670
 671   NewRoot = Tree->Root;
 672   while (Tmp != NewRoot && Parent->Color == RedBlackTreeRed) {
 673     RED_BLACK_TREE_NODE *GrandParent, *Uncle;
 674
 675     //
 676     // Tmp is not the root node. Tmp is red. Tmp's parent is red. (Breaking
 677     // property #3.)
 678     //
 679     // Due to property #5, Tmp's parent cannot be the root node, hence Tmp's
 680     // grandparent exists.
 681     //
 682     // Tmp's grandparent is black, because property #3 is only broken between
 683     // Tmp and Tmp's parent.
 684     //
 685     GrandParent = Parent->Parent;
 686
 687     if (Parent == GrandParent->Left) {
 688       Uncle = GrandParent->Right;
 689       if (Uncle != NULL && Uncle->Color == RedBlackTreeRed) {
 690         //
 691         //             GrandParent (black)
 692         //            /                   \_
 693         // Parent (red)                    Uncle (red)
 694         //      |
 695         //  Tmp (red)
 696         //
 697
 698         Parent->Color = RedBlackTreeBlack;
 699         Uncle->Color = RedBlackTreeBlack;
 700         GrandParent->Color = RedBlackTreeRed;
 701
 702         //
 703         //                GrandParent (red)
 704         //               /                 \_
 705         // Parent (black)                   Uncle (black)
 706         //       |
 707         //   Tmp (red)
 708         //
 709         // We restored property #3 between Tmp and Tmp's parent, without
 710         // breaking property #4. However, we may have broken property #3
 711         // between Tmp's grandparent and Tmp's great-grandparent (if any), so
 712         // repeat the loop for Tmp's grandparent.
 713         //
 714         // If Tmp's grandparent has no parent, then the loop will terminate,
 715         // and we will have broken property #5, by coloring the root red. We'll
 716         // restore property #5 after the loop, without breaking any others.
 717         //
 718         Tmp = GrandParent;
 719         Parent = Tmp->Parent;
 720       } else {
 721         //
 722         // Tmp's uncle is black (satisfied by the case too when Tmp's uncle is
 723         // NULL, see property #2).
 724         //
 725
 726         if (Tmp == Parent->Right) {
 727           //
 728           //                 GrandParent (black): D
 729           //                /                      \_
 730           // Parent (red): A                        Uncle (black): E
 731           //      \_
 732           //       Tmp (red): B
 733           //            \_
 734           //             black: C
 735           //
 736           // Rotate left, pivoting on node A. This keeps the breakage of
 737           // property #3 in the same spot, and keeps other properties intact
 738           // (because both Tmp and its parent are red).
 739           //
 740           Tmp = Parent;
 741           RedBlackTreeRotateLeft (Tmp, &NewRoot);
 742           Parent = Tmp->Parent;
 743
 744           //
 745           // With the rotation we reached the same configuration as if Tmp had
 746           // been a left child to begin with.
 747           //
 748           //                       GrandParent (black): D
 749           //                      /                      \_
 750           //       Parent (red): B                        Uncle (black): E
 751           //             / \_
 752           // Tmp (red): A   black: C
 753           //
 754           ASSERT (GrandParent == Parent->Parent);
 755         }
 756
 757         Parent->Color = RedBlackTreeBlack;
 758         GrandParent->Color = RedBlackTreeRed;
 759
 760         //
 761         // Property #3 is now restored, but we've broken property #4. Namely,
 762         // paths going through node E now see a decrease in black count, while
 763         // paths going through node B don't.
 764         //
 765         //                        GrandParent (red): D
 766         //                       /                    \_
 767         //      Parent (black): B                      Uncle (black): E
 768         //             / \_
 769         // Tmp (red): A   black: C
 770         //
 771
 772         RedBlackTreeRotateRight (GrandParent, &NewRoot);
 773
 774         //
 775         // Property #4 has been restored for node E, and preserved for others.
 776         //
 777         //              Parent (black): B
 778         //             /                 \_
 779         // Tmp (red): A                   [GrandParent] (red): D
 780         //                                         / \_
 781         //                                 black: C   [Uncle] (black): E
 782         //
 783         // This configuration terminates the loop because Tmp's parent is now
 784         // black.
 785         //
 786       }
 787     } else {
 788       //
 789       // Symmetrical to the other branch.
 790       //
 791       Uncle = GrandParent->Left;
 792       if (Uncle != NULL && Uncle->Color == RedBlackTreeRed) {
 793         Parent->Color = RedBlackTreeBlack;
 794         Uncle->Color = RedBlackTreeBlack;
 795         GrandParent->Color = RedBlackTreeRed;
 796         Tmp = GrandParent;
 797         Parent = Tmp->Parent;
 798       } else {
 799         if (Tmp == Parent->Left) {
 800           Tmp = Parent;
 801           RedBlackTreeRotateRight (Tmp, &NewRoot);
 802           Parent = Tmp->Parent;
 803           ASSERT (GrandParent == Parent->Parent);
 804         }
 805         Parent->Color = RedBlackTreeBlack;
 806         GrandParent->Color = RedBlackTreeRed;
 807         RedBlackTreeRotateLeft (GrandParent, &NewRoot);
 808       }
 809     }
 810   }
 811
 812   NewRoot->Color = RedBlackTreeBlack;
 813   Tree->Root = NewRoot;
 814   Status = RETURN_SUCCESS;
 815
 816 Done:
 817   if (FeaturePcdGet (PcdValidateOrderedCollection)) {
 818     RedBlackTreeValidate (Tree);
 819   }
 820   return Status;
 821 }
 822
 823
 824 /**
 825   Check if a node is black, allowing for leaf nodes (see property #2).
 826
 827   This is a convenience shorthand.
 828
 829   param[in] Node  The node to check. Node may be NULL, corresponding to a leaf.
 830
 831   @return  If Node is NULL or colored black.
 832 **/
 833
 834 STATIC
 835 BOOLEAN
 836 NodeIsNullOrBlack (
 837   IN CONST RED_BLACK_TREE_NODE *Node
 838   )
 839 {
 840   return Node == NULL || Node->Color == RedBlackTreeBlack;
 841 }
 842
 843
 844 /**
 845   Delete a node from the tree, unlinking the associated user structure.
 846
 847   Read-write operation.
 848
 849   @param[in,out] Tree        The tree to delete Node from.
 850
 851   @param[in]     Node        The tree node to delete from Tree. The caller is
 852                              responsible for ensuring that Node belongs to
 853                              Tree, and that Node is non-NULL and valid. Node is
 854                              typically an earlier return value, or output
 855                              parameter, of:
 856
 857                              - OrderedCollectionFind(), for deleting a node by
 858                                user structure key,
 859
 860                              - OrderedCollectionMin() / OrderedCollectionMax(),
 861                                for deleting the minimum / maximum node,
 862
 863                              - OrderedCollectionNext() /
 864                                OrderedCollectionPrev(), for deleting a node
 865                                found during an iteration,
 866
 867                              - OrderedCollectionInsert() with return value
 868                                RETURN_ALREADY_STARTED, for deleting a node
 869                                whose linked user structure caused collision
 870                                during insertion.
 871
 872                              Given a non-empty Tree, Tree->Root is also a valid
 873                              Node argument (typically used for simplicity in
 874                              loops that empty the tree completely).
 875
 876                              Node is released with MemoryAllocationLib's
 877                              FreePool() function.
 878
 879                              Existing RED_BLACK_TREE_NODE pointers (ie.
 880                              iterators) *different* from Node remain valid. For
 881                              example:
 882
 883                              - OrderedCollectionNext() /
 884                                OrderedCollectionPrev() iterations in the caller
 885                                can be continued from Node, if
 886                                OrderedCollectionNext() or
 887                                OrderedCollectionPrev() is called on Node
 888                                *before* OrderedCollectionDelete() is. That is,
 889                                fetch the successor / predecessor node first,
 890                                then delete Node.
 891
 892                              - On-going iterations in the caller that would
 893                                have otherwise returned Node at some point, as
 894                                dictated by user structure order, will correctly
 895                                reflect the absence of Node after
 896                                OrderedCollectionDelete() is called
 897                                mid-iteration.
 898
 899   @param[out]    UserStruct  If the caller provides this optional output-only
 900                              parameter, then on output it is set to the user
 901                              structure originally linked by Node (which is now
 902                              freed).
 903
 904                              This is a convenience that may save the caller a
 905                              OrderedCollectionUserStruct() invocation before
 906                              calling OrderedCollectionDelete(), in order to
 907                              retrieve the user structure being unlinked.
 908 **/
 909 VOID
 910 EFIAPI
 911 OrderedCollectionDelete (
 912   IN OUT RED_BLACK_TREE      *Tree,
 913   IN     RED_BLACK_TREE_NODE *Node,
 914   OUT    VOID                **UserStruct OPTIONAL
 915   )
 916 {
 917   RED_BLACK_TREE_NODE  *NewRoot;
 918   RED_BLACK_TREE_NODE  *OrigLeftChild, *OrigRightChild, *OrigParent;
 919   RED_BLACK_TREE_NODE  *Child, *Parent;
 920   RED_BLACK_TREE_COLOR ColorOfUnlinked;
 921
 922   NewRoot        = Tree->Root;
 923   OrigLeftChild  = Node->Left,
 924   OrigRightChild = Node->Right,
 925   OrigParent     = Node->Parent;
 926
 927   if (UserStruct != NULL) {
 928     *UserStruct = Node->UserStruct;
 929   }
 930
 931   //
 932   // After this block, no matter which branch we take:
 933   // - Child will point to the unique (or NULL) original child of the node that
 934   //   we will have unlinked,
 935   // - Parent will point to the *position* of the original parent of the node
 936   //   that we will have unlinked.
 937   //
 938   if (OrigLeftChild == NULL || OrigRightChild == NULL) {
 939     //
 940     // Node has at most one child. We can connect that child (if any) with
 941     // Node's parent (if any), unlinking Node. This will preserve ordering
 942     // because the subtree rooted in Node's child (if any) remains on the same
 943     // side of Node's parent (if any) that Node was before.
 944     //
 945     Parent = OrigParent;
 946     Child = (OrigLeftChild != NULL) ? OrigLeftChild : OrigRightChild;
 947     ColorOfUnlinked = Node->Color;
 948
 949     if (Child != NULL) {
 950       Child->Parent = Parent;
 951     }
 952     if (OrigParent == NULL) {
 953       NewRoot = Child;
 954     } else {
 955       if (Node == OrigParent->Left) {
 956         OrigParent->Left = Child;
 957       } else {
 958         OrigParent->Right = Child;
 959       }
 960     }
 961   } else {
 962     //
 963     // Node has two children. We unlink Node's successor, and then link it into
 964     // Node's place, keeping Node's original color. This preserves ordering
 965     // because:
 966     // - Node's left subtree is less than Node, hence less than Node's
 967     //   successor.
 968     // - Node's right subtree is greater than Node. Node's successor is the
 969     //   minimum of that subtree, hence Node's successor is less than Node's
 970     //   right subtree with its minimum removed.
 971     // - Node's successor is in Node's subtree, hence it falls on the same side
 972     //   of Node's parent as Node itself. The relinking doesn't change this
 973     //   relation.
 974     //
 975     RED_BLACK_TREE_NODE *ToRelink;
 976
 977     ToRelink = OrigRightChild;
 978     if (ToRelink->Left == NULL) {
 979       //
 980       // OrigRightChild itself is Node's successor, it has no left child:
 981       //
 982       //                OrigParent
 983       //                    |
 984       //                  Node: B
 985       //                 /       \_
 986       // OrigLeftChild: A         OrigRightChild: E <--- Parent, ToRelink
 987       //                                           \_
 988       //                                            F <--- Child
 989       //
 990       Parent = OrigRightChild;
 991       Child = OrigRightChild->Right;
 992     } else {
 993       do {
 994         ToRelink = ToRelink->Left;
 995       } while (ToRelink->Left != NULL);
 996
 997       //
 998       // Node's successor is the minimum of OrigRightChild's proper subtree:
 999       //
1000       //                OrigParent
1001       //                    |
1002       //                  Node: B
1003       //                 /       \_
1004       // OrigLeftChild: A         OrigRightChild: E <--- Parent
1005       //                                  /
1006       //                                 C <--- ToRelink
1007       //                                  \_
1008       //                                   D <--- Child
1009       Parent = ToRelink->Parent;
1010       Child = ToRelink->Right;
1011
1012       //
1013       // Unlink Node's successor (ie. ToRelink):
1014       //
1015       //                OrigParent
1016       //                    |
1017       //                  Node: B
1018       //                 /       \_
1019       // OrigLeftChild: A         OrigRightChild: E <--- Parent
1020       //                                  /
1021       //                                 D <--- Child
1022       //
1023       //                                 C <--- ToRelink
1024       //
1025       Parent->Left = Child;
1026       if (Child) {
1027         Child->Parent = Parent;
1028       }
1029
1030       //
1031       // We start to link Node's unlinked successor into Node's place:
1032       //
1033       //                OrigParent
1034       //                    |
1035       //                  Node: B     C <--- ToRelink
1036       //                 /             \_
1037       // OrigLeftChild: A               OrigRightChild: E <--- Parent
1038       //                                        /
1039       //                                       D <--- Child
1040       //
1041       //
1042       //
1043       ToRelink->Right = OrigRightChild;
1044       OrigRightChild->Parent = ToRelink;
1045     }
1046
1047     //
1048     // The rest handles both cases, attaching ToRelink (Node's original
1049     // successor) to OrigLeftChild and OrigParent.
1050     //
1051     //                           Parent,
1052     //              OrigParent   ToRelink             OrigParent
1053     //                  |        |                        |
1054     //                Node: B    |                      Node: B          Parent
1055     //                           v                                          |
1056     //           OrigRightChild: E                        C <--- ToRelink   |
1057     //                 / \                               / \                v
1058     // OrigLeftChild: A   F              OrigLeftChild: A   OrigRightChild: E
1059     //                    ^                                         /
1060     //                    |                                        D <--- Child
1061     //                  Child
1062     //
1063     ToRelink->Left = OrigLeftChild;
1064     OrigLeftChild->Parent = ToRelink;
1065
1066     //
1067     // Node's color must be preserved in Node's original place.
1068     //
1069     ColorOfUnlinked = ToRelink->Color;
1070     ToRelink->Color = Node->Color;
1071
1072     //
1073     // Finish linking Node's unlinked successor into Node's place.
1074     //
1075     //                           Parent,
1076     //                Node: B    ToRelink               Node: B
1077     //                           |
1078     //              OrigParent   |                    OrigParent         Parent
1079     //                  |        v                        |                 |
1080     //           OrigRightChild: E                        C <--- ToRelink   |
1081     //                 / \                               / \                v
1082     // OrigLeftChild: A   F              OrigLeftChild: A   OrigRightChild: E
1083     //                    ^                                         /
1084     //                    |                                        D <--- Child
1085     //                  Child
1086     //
1087     ToRelink->Parent = OrigParent;
1088     if (OrigParent == NULL) {
1089       NewRoot = ToRelink;
1090     } else {
1091       if (Node == OrigParent->Left) {
1092         OrigParent->Left = ToRelink;
1093       } else {
1094         OrigParent->Right = ToRelink;
1095       }
1096     }
1097   }
1098
1099   FreePool (Node);
1100
1101   //
1102   // If the node that we unlinked from its original spot (ie. Node itself, or
1103   // Node's successor), was red, then we broke neither property #3 nor property
1104   // #4: we didn't create any red-red edge between Child and Parent, and we
1105   // didn't change the black count on any path.
1106   //
1107   if (ColorOfUnlinked == RedBlackTreeBlack) {
1108     //
1109     // However, if the unlinked node was black, then we have to transfer its
1110     // "black-increment" to its unique child (pointed-to by Child), lest we
1111     // break property #4 for its ancestors.
1112     //
1113     // If Child is red, we can simply color it black. If Child is black
1114     // already, we can't technically transfer a black-increment to it, due to
1115     // property #1.
1116     //
1117     // In the following loop we ascend searching for a red node to color black,
1118     // or until we reach the root (in which case we can drop the
1119     // black-increment). Inside the loop body, Child has a black value of 2,
1120     // transitorily breaking property #1 locally, but maintaining property #4
1121     // globally.
1122     //
1123     // Rotations in the loop preserve property #4.
1124     //
1125     while (Child != NewRoot && NodeIsNullOrBlack (Child)) {
1126       RED_BLACK_TREE_NODE *Sibling, *LeftNephew, *RightNephew;
1127
1128       if (Child == Parent->Left) {
1129         Sibling = Parent->Right;
1130         //
1131         // Sibling can never be NULL (ie. a leaf).
1132         //
1133         // If Sibling was NULL, then the black count on the path from Parent to
1134         // Sibling would equal Parent's black value, plus 1 (due to property
1135         // #2). Whereas the black count on the path from Parent to any leaf via
1136         // Child would be at least Parent's black value, plus 2 (due to Child's
1137         // black value of 2). This would clash with property #4.
1138         //
1139         // (Sibling can be black of course, but it has to be an internal node.
1140         // Internality allows Sibling to have children, bumping the black
1141         // counts of paths that go through it.)
1142         //
1143         ASSERT (Sibling != NULL);
1144         if (Sibling->Color == RedBlackTreeRed) {
1145           //
1146           // Sibling's red color implies its children (if any), node C and node
1147           // E, are black (property #3). It also implies that Parent is black.
1148           //
1149           //           grandparent                                 grandparent
1150           //                |                                           |
1151           //            Parent,b:B                                     b:D
1152           //           /          \                                   /   \_
1153           // Child,2b:A            Sibling,r:D  --->        Parent,r:B     b:E
1154           //                           /\                       /\_
1155           //                        b:C  b:E          Child,2b:A  Sibling,b:C
1156           //
1157           Sibling->Color = RedBlackTreeBlack;
1158           Parent->Color = RedBlackTreeRed;
1159           RedBlackTreeRotateLeft (Parent, &NewRoot);
1160           Sibling = Parent->Right;
1161           //
1162           // Same reasoning as above.
1163           //
1164           ASSERT (Sibling != NULL);
1165         }
1166
1167         //
1168         // Sibling is black, and not NULL. (Ie. Sibling is a black internal
1169         // node.)
1170         //
1171         ASSERT (Sibling->Color == RedBlackTreeBlack);
1172         LeftNephew = Sibling->Left;
1173         RightNephew = Sibling->Right;
1174         if (NodeIsNullOrBlack (LeftNephew) &&
1175             NodeIsNullOrBlack (RightNephew)) {
1176           //
1177           // In this case we can "steal" one black value from Child and Sibling
1178           // each, and pass it to Parent. "Stealing" means that Sibling (black
1179           // value 1) becomes red, Child (black value 2) becomes singly-black,
1180           // and Parent will have to be examined if it can eat the
1181           // black-increment.
1182           //
1183           // Sibling is allowed to become red because both of its children are
1184           // black (property #3).
1185           //
1186           //           grandparent                             Parent
1187           //                |                                     |
1188           //            Parent,x:B                            Child,x:B
1189           //           /          \                          /         \_
1190           // Child,2b:A            Sibling,b:D    --->    b:A           r:D
1191           //                           /\                                /\_
1192           //             LeftNephew,b:C  RightNephew,b:E              b:C  b:E
1193           //
1194           Sibling->Color = RedBlackTreeRed;
1195           Child = Parent;
1196           Parent = Parent->Parent;
1197           //
1198           // Continue ascending.
1199           //
1200         } else {
1201           //
1202           // At least one nephew is red.
1203           //
1204           if (NodeIsNullOrBlack (RightNephew)) {
1205             //
1206             // Since the right nephew is black, the left nephew is red. Due to
1207             // property #3, LeftNephew has two black children, hence node E is
1208             // black.
1209             //
1210             // Together with the rotation, this enables us to color node F red
1211             // (because property #3 will be satisfied). We flip node D to black
1212             // to maintain property #4.
1213             //
1214             //      grandparent                         grandparent
1215             //           |                                   |
1216             //       Parent,x:B                          Parent,x:B
1217             //           /\                                  /\_
1218             // Child,2b:A  Sibling,b:F     --->    Child,2b:A  Sibling,b:D
1219             //                  /\                            /   \_
1220             //    LeftNephew,r:D  RightNephew,b:G          b:C  RightNephew,r:F
1221             //               /\                                       /\_
1222             //            b:C  b:E                                 b:E  b:G
1223             //
1224             LeftNephew->Color = RedBlackTreeBlack;
1225             Sibling->Color = RedBlackTreeRed;
1226             RedBlackTreeRotateRight (Sibling, &NewRoot);
1227             Sibling = Parent->Right;
1228             RightNephew = Sibling->Right;
1229             //
1230             // These operations ensure that...
1231             //
1232           }
1233           //
1234           // ... RightNephew is definitely red here, plus Sibling is (still)
1235           // black and non-NULL.
1236           //
1237           ASSERT (RightNephew != NULL);
1238           ASSERT (RightNephew->Color == RedBlackTreeRed);
1239           ASSERT (Sibling != NULL);
1240           ASSERT (Sibling->Color == RedBlackTreeBlack);
1241           //
1242           // In this case we can flush the extra black-increment immediately,
1243           // restoring property #1 for Child (node A): we color RightNephew
1244           // (node E) from red to black.
1245           //
1246           // In order to maintain property #4, we exchange colors between
1247           // Parent and Sibling (nodes B and D), and rotate left around Parent
1248           // (node B). The transformation doesn't change the black count
1249           // increase incurred by each partial path, eg.
1250           // - ascending from node A: 2 + x     == 1 + 1 + x
1251           // - ascending from node C: y + 1 + x == y + 1 + x
1252           // - ascending from node E: 0 + 1 + x == 1 + x
1253           //
1254           // The color exchange is valid, because even if x stands for red,
1255           // both children of node D are black after the transformation
1256           // (preserving property #3).
1257           //
1258           //           grandparent                                  grandparent
1259           //                |                                            |
1260           //            Parent,x:B                                      x:D
1261           //           /          \                                    /   \_
1262           // Child,2b:A            Sibling,b:D              --->    b:B     b:E
1263           //                         /     \                       /   \_
1264           //                      y:C       RightNephew,r:E     b:A     y:C
1265           //
1266           //
1267           Sibling->Color = Parent->Color;
1268           Parent->Color = RedBlackTreeBlack;
1269           RightNephew->Color = RedBlackTreeBlack;
1270           RedBlackTreeRotateLeft (Parent, &NewRoot);
1271           Child = NewRoot;
1272           //
1273           // This terminates the loop.
1274           //
1275         }
1276       } else {
1277         //
1278         // Mirrors the other branch.
1279         //
1280         Sibling = Parent->Left;
1281         ASSERT (Sibling != NULL);
1282         if (Sibling->Color == RedBlackTreeRed) {
1283           Sibling->Color = RedBlackTreeBlack;
1284           Parent->Color = RedBlackTreeRed;
1285           RedBlackTreeRotateRight (Parent, &NewRoot);
1286           Sibling = Parent->Left;
1287           ASSERT (Sibling != NULL);
1288         }
1289
1290         ASSERT (Sibling->Color == RedBlackTreeBlack);
1291         RightNephew = Sibling->Right;
1292         LeftNephew = Sibling->Left;
1293         if (NodeIsNullOrBlack (RightNephew) &&
1294             NodeIsNullOrBlack (LeftNephew)) {
1295           Sibling->Color = RedBlackTreeRed;
1296           Child = Parent;
1297           Parent = Parent->Parent;
1298         } else {
1299           if (NodeIsNullOrBlack (LeftNephew)) {
1300             RightNephew->Color = RedBlackTreeBlack;
1301             Sibling->Color = RedBlackTreeRed;
1302             RedBlackTreeRotateLeft (Sibling, &NewRoot);
1303             Sibling = Parent->Left;
1304             LeftNephew = Sibling->Left;
1305           }
1306           ASSERT (LeftNephew != NULL);
1307           ASSERT (LeftNephew->Color == RedBlackTreeRed);
1308           ASSERT (Sibling != NULL);
1309           ASSERT (Sibling->Color == RedBlackTreeBlack);
1310           Sibling->Color = Parent->Color;
1311           Parent->Color = RedBlackTreeBlack;
1312           LeftNephew->Color = RedBlackTreeBlack;
1313           RedBlackTreeRotateRight (Parent, &NewRoot);
1314           Child = NewRoot;
1315         }
1316       }
1317     }
1318
1319     if (Child != NULL) {
1320       Child->Color = RedBlackTreeBlack;
1321     }
1322   }
1323
1324   Tree->Root = NewRoot;
1325
1326   if (FeaturePcdGet (PcdValidateOrderedCollection)) {
1327     RedBlackTreeValidate (Tree);
1328   }
1329 }
1330
1331
1332 /**
1333   Recursively check the red-black tree properties #1 to #4 on a node.
1334
1335   @param[in] Node  The root of the subtree to validate.
1336
1337   @retval  The black-height of Node's parent.
1338 **/
1339 STATIC
1340 UINT32
1341 RedBlackTreeRecursiveCheck (
1342   IN CONST RED_BLACK_TREE_NODE *Node
1343   )
1344 {
1345   UINT32 LeftHeight, RightHeight;
1346
1347   //
1348   // property #2
1349   //
1350   if (Node == NULL) {
1351     return 1;
1352   }
1353
1354   //
1355   // property #1
1356   //
1357   ASSERT (Node->Color == RedBlackTreeRed || Node->Color == RedBlackTreeBlack);
1358
1359   //
1360   // property #3
1361   //
1362   if (Node->Color == RedBlackTreeRed) {
1363     ASSERT (NodeIsNullOrBlack (Node->Left));
1364     ASSERT (NodeIsNullOrBlack (Node->Right));
1365   }
1366
1367   //
1368   // property #4
1369   //
1370   LeftHeight = RedBlackTreeRecursiveCheck (Node->Left);
1371   RightHeight = RedBlackTreeRecursiveCheck (Node->Right);
1372   ASSERT (LeftHeight == RightHeight);
1373
1374   return (Node->Color == RedBlackTreeBlack) + LeftHeight;
1375 }
1376
1377
1378 /**
1379   A slow function that asserts that the tree is a valid red-black tree, and
1380   that it orders user structures correctly.
1381
1382   Read-only operation.
1383
1384   This function uses the stack for recursion and is not recommended for
1385   "production use".
1386
1387   @param[in] Tree  The tree to validate.
1388 **/
1389 STATIC
1390 VOID
1391 RedBlackTreeValidate (
1392   IN CONST RED_BLACK_TREE *Tree
1393   )
1394 {
1395   UINT32                    BlackHeight;
1396   UINT32                    ForwardCount, BackwardCount;
1397   CONST RED_BLACK_TREE_NODE *Last, *Node;
1398
1399   DEBUG ((DEBUG_VERBOSE, "%a: Tree=%p\n", __FUNCTION__, Tree));
1400
1401   //
1402   // property #5
1403   //
1404   ASSERT (NodeIsNullOrBlack (Tree->Root));
1405
1406   //
1407   // check the other properties
1408   //
1409   BlackHeight = RedBlackTreeRecursiveCheck (Tree->Root) - 1;
1410
1411   //
1412   // forward ordering
1413   //
1414   Last = OrderedCollectionMin (Tree);
1415   ForwardCount = (Last != NULL);
1416   for (Node = OrderedCollectionNext (Last); Node != NULL;
1417        Node = OrderedCollectionNext (Last)) {
1418     ASSERT (Tree->UserStructCompare (Last->UserStruct, Node->UserStruct) < 0);
1419     Last = Node;
1420     ++ForwardCount;
1421   }
1422
1423   //
1424   // backward ordering
1425   //
1426   Last = OrderedCollectionMax (Tree);
1427   BackwardCount = (Last != NULL);
1428   for (Node = OrderedCollectionPrev (Last); Node != NULL;
1429        Node = OrderedCollectionPrev (Last)) {
1430     ASSERT (Tree->UserStructCompare (Last->UserStruct, Node->UserStruct) > 0);
1431     Last = Node;
1432     ++BackwardCount;
1433   }
1434
1435   ASSERT (ForwardCount == BackwardCount);
1436
1437   DEBUG ((DEBUG_VERBOSE, "%a: Tree=%p BlackHeight=%Ld Count=%Ld\n",
1438     __FUNCTION__, Tree, (INT64)BlackHeight, (INT64)ForwardCount));
1439 }