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   Copyright (c) 2014, Intel Corporation. All rights reserved.<BR>
  15
  16   SPDX-License-Identifier: BSD-2-Clause-Patent
  17 **/
  18
  19 #include <Library/OrderedCollectionLib.h>
  20 #include <Library/DebugLib.h>
  21 #include <Library/MemoryAllocationLib.h>
  22
  23 typedef enum {
  24   RedBlackTreeRed,
  25   RedBlackTreeBlack
  26 } RED_BLACK_TREE_COLOR;
  27
  28 //
  29 // Incomplete types and convenience typedefs are present in the library class
  30 // header. Beside completing the types, we introduce typedefs here that reflect
  31 // the implementation closely.
  32 //
  33 typedef ORDERED_COLLECTION              RED_BLACK_TREE;
  34 typedef ORDERED_COLLECTION_ENTRY        RED_BLACK_TREE_NODE;
  35 typedef ORDERED_COLLECTION_USER_COMPARE RED_BLACK_TREE_USER_COMPARE;
  36 typedef ORDERED_COLLECTION_KEY_COMPARE  RED_BLACK_TREE_KEY_COMPARE;
  37
  38 struct ORDERED_COLLECTION {
  39   RED_BLACK_TREE_NODE         *Root;
  40   RED_BLACK_TREE_USER_COMPARE UserStructCompare;
  41   RED_BLACK_TREE_KEY_COMPARE  KeyCompare;
  42 };
  43
  44 struct ORDERED_COLLECTION_ENTRY {
  45   VOID                 *UserStruct;
  46   RED_BLACK_TREE_NODE  *Parent;
  47   RED_BLACK_TREE_NODE  *Left;
  48   RED_BLACK_TREE_NODE  *Right;
  49   RED_BLACK_TREE_COLOR Color;
  50 };
  51
  52
  53 /**
  54   Retrieve the user structure linked by the specified tree node.
  55
  56   Read-only operation.
  57
  58   @param[in] Node  Pointer to the tree node whose associated user structure we
  59                    want to retrieve. The caller is responsible for passing a
  60                    non-NULL argument.
  61
  62   @return  Pointer to user structure linked by Node.
  63 **/
  64 VOID *
  65 EFIAPI
  66 OrderedCollectionUserStruct (
  67   IN CONST RED_BLACK_TREE_NODE *Node
  68   )
  69 {
  70   return Node->UserStruct;
  71 }
  72
  73 /**
  74   A slow function that asserts that the tree is a valid red-black tree, and
  75   that it orders user structures correctly.
  76
  77   Read-only operation.
  78
  79   This function uses the stack for recursion and is not recommended for
  80   "production use".
  81
  82   @param[in] Tree  The tree to validate.
  83 **/
  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 (BOOLEAN)(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 VOID
 421 RedBlackTreeRotateRight (
 422   IN OUT RED_BLACK_TREE_NODE *Pivot,
 423   OUT    RED_BLACK_TREE_NODE **NewRoot
 424   )
 425 {
 426   RED_BLACK_TREE_NODE *Parent;
 427   RED_BLACK_TREE_NODE *LeftChild;
 428   RED_BLACK_TREE_NODE *LeftRightChild;
 429
 430   Parent         = Pivot->Parent;
 431   LeftChild      = Pivot->Left;
 432   LeftRightChild = LeftChild->Right;
 433
 434   Pivot->Left = LeftRightChild;
 435   if (LeftRightChild != NULL) {
 436     LeftRightChild->Parent = Pivot;
 437   }
 438   LeftChild->Parent = Parent;
 439   if (Parent == NULL) {
 440     *NewRoot = LeftChild;
 441   } else {
 442     if (Pivot == Parent->Left) {
 443       Parent->Left = LeftChild;
 444     } else {
 445       Parent->Right = LeftChild;
 446     }
 447   }
 448   LeftChild->Right = Pivot;
 449   Pivot->Parent = LeftChild;
 450 }
 451
 452
 453 /**
 454   Rotate tree nodes around Pivot to the left.
 455
 456           Parent                                 Parent
 457             |                                      |
 458           Pivot                                RightChild
 459          .     \                              /          .
 460     Node1       RightChild    --->       Pivot            Node2
 461                     /.                    . \_
 462       RightLeftChild  Node2          Node1   RightLeftChild
 463
 464   The ordering Node1 < Pivot < RightLeftChild < RightChild < Node2 is kept
 465   intact. Parent (if any) is either at the left extreme or the right extreme of
 466   this ordering, and that relation is also kept intact.
 467
 468   Edges marked with a dot (".") don't change during rotation.
 469
 470   Internal read-write operation.
 471
 472   @param[in,out] Pivot    The tree node to rotate other nodes left around. It
 473                           is the caller's responsibility to ensure that
 474                           Pivot->Right is not NULL.
 475
 476   @param[out]    NewRoot  If Pivot has a parent node on input, then the
 477                           function updates Pivot's original parent on output
 478                           according to the rotation, and NewRoot is not
 479                           accessed.
 480
 481                           If Pivot has no parent node on input (ie. Pivot is
 482                           the root of the tree), then the function stores the
 483                           new root node of the tree in NewRoot.
 484 **/
 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;
 492   RED_BLACK_TREE_NODE *RightChild;
 493   RED_BLACK_TREE_NODE *RightLeftChild;
 494
 495   Parent         = Pivot->Parent;
 496   RightChild     = Pivot->Right;
 497   RightLeftChild = RightChild->Left;
 498
 499   Pivot->Right = RightLeftChild;
 500   if (RightLeftChild != NULL) {
 501     RightLeftChild->Parent = Pivot;
 502   }
 503   RightChild->Parent = Parent;
 504   if (Parent == NULL) {
 505     *NewRoot = RightChild;
 506   } else {
 507     if (Pivot == Parent->Left) {
 508       Parent->Left = RightChild;
 509     } else {
 510       Parent->Right = RightChild;
 511     }
 512   }
 513   RightChild->Left = Pivot;
 514   Pivot->Parent = RightChild;
 515 }
 516
 517
 518 /**
 519   Insert (link) a user structure into the tree.
 520
 521   Read-write operation.
 522
 523   This function allocates the new tree node with MemoryAllocationLib's
 524   AllocatePool() function.
 525
 526   @param[in,out] Tree        The tree to insert UserStruct into.
 527
 528   @param[out]    Node        The meaning of this optional, output-only
 529                              parameter depends on the return value of the
 530                              function.
 531
 532                              When insertion is successful (RETURN_SUCCESS),
 533                              Node is set on output to the new tree node that
 534                              now links UserStruct.
 535
 536                              When insertion fails due to lack of memory
 537                              (RETURN_OUT_OF_RESOURCES), Node is not changed.
 538
 539                              When insertion fails due to key collision (ie.
 540                              another user structure is already in the tree that
 541                              compares equal to UserStruct), with return value
 542                              RETURN_ALREADY_STARTED, then Node is set on output
 543                              to the node that links the colliding user
 544                              structure. This enables "find-or-insert" in one
 545                              function call, or helps with later removal of the
 546                              colliding element.
 547
 548   @param[in]     UserStruct  The user structure to link into the tree.
 549                              UserStruct is ordered against in-tree user
 550                              structures with the Tree->UserStructCompare()
 551                              function.
 552
 553   @retval RETURN_SUCCESS           Insertion successful. A new tree node has
 554                                    been allocated, linking UserStruct. The new
 555                                    tree node is reported back in Node (if the
 556                                    caller requested it).
 557
 558                                    Existing RED_BLACK_TREE_NODE pointers into
 559                                    Tree remain valid. For example, on-going
 560                                    iterations in the caller can continue with
 561                                    OrderedCollectionNext() /
 562                                    OrderedCollectionPrev(), and they will
 563                                    return the new node at some point if user
 564                                    structure order dictates it.
 565
 566   @retval RETURN_OUT_OF_RESOURCES  AllocatePool() failed to allocate memory for
 567                                    the new tree node. The tree has not been
 568                                    changed. Existing RED_BLACK_TREE_NODE
 569                                    pointers into Tree remain valid.
 570
 571   @retval RETURN_ALREADY_STARTED   A user structure has been found in the tree
 572                                    that compares equal to UserStruct. The node
 573                                    linking the colliding user structure is
 574                                    reported back in Node (if the caller
 575                                    requested it). The tree has not been
 576                                    changed. Existing RED_BLACK_TREE_NODE
 577                                    pointers into Tree remain valid.
 578 **/
 579 RETURN_STATUS
 580 EFIAPI
 581 OrderedCollectionInsert (
 582   IN OUT RED_BLACK_TREE      *Tree,
 583   OUT    RED_BLACK_TREE_NODE **Node      OPTIONAL,
 584   IN     VOID                *UserStruct
 585   )
 586 {
 587   RED_BLACK_TREE_NODE *Tmp;
 588   RED_BLACK_TREE_NODE *Parent;
 589   INTN                Result;
 590   RETURN_STATUS       Status;
 591   RED_BLACK_TREE_NODE *NewRoot;
 592
 593   Tmp = Tree->Root;
 594   Parent = NULL;
 595   Result = 0;
 596
 597   //
 598   // First look for a collision, saving the last examined node for the case
 599   // when there's no collision.
 600   //
 601   while (Tmp != NULL) {
 602     Result = Tree->UserStructCompare (UserStruct, Tmp->UserStruct);
 603     if (Result == 0) {
 604       break;
 605     }
 606     Parent = Tmp;
 607     Tmp = (Result < 0) ? Tmp->Left : Tmp->Right;
 608   }
 609
 610   if (Tmp != NULL) {
 611     if (Node != NULL) {
 612       *Node = Tmp;
 613     }
 614     Status = RETURN_ALREADY_STARTED;
 615     goto Done;
 616   }
 617
 618   //
 619   // no collision, allocate a new node
 620   //
 621   Tmp = AllocatePool (sizeof *Tmp);
 622   if (Tmp == NULL) {
 623     Status = RETURN_OUT_OF_RESOURCES;
 624     goto Done;
 625   }
 626   if (Node != NULL) {
 627     *Node = Tmp;
 628   }
 629
 630   //
 631   // reference the user structure from the node
 632   //
 633   Tmp->UserStruct = UserStruct;
 634
 635   //
 636   // Link the node as a child to the correct side of the parent.
 637   // If there's no parent, the new node is the root node in the tree.
 638   //
 639   Tmp->Parent = Parent;
 640   Tmp->Left = NULL;
 641   Tmp->Right = NULL;
 642   if (Parent == NULL) {
 643     Tree->Root = Tmp;
 644     Tmp->Color = RedBlackTreeBlack;
 645     Status = RETURN_SUCCESS;
 646     goto Done;
 647   }
 648   if (Result < 0) {
 649     Parent->Left = Tmp;
 650   } else {
 651     Parent->Right = Tmp;
 652   }
 653   Tmp->Color = RedBlackTreeRed;
 654
 655   //
 656   // Red-black tree properties:
 657   //
 658   // #1 Each node is either red or black (RED_BLACK_TREE_NODE.Color).
 659   //
 660   // #2 Each leaf (ie. a pseudo-node pointed-to by a NULL valued
 661   //    RED_BLACK_TREE_NODE.Left or RED_BLACK_TREE_NODE.Right field) is black.
 662   //
 663   // #3 Each red node has two black children.
 664   //
 665   // #4 For any node N, and for any leaves L1 and L2 reachable from N, the
 666   //    paths N..L1 and N..L2 contain the same number of black nodes.
 667   //
 668   // #5 The root node is black.
 669   //
 670   // By replacing a leaf with a red node above, only property #3 may have been
 671   // broken. (Note that this is the only edge across which property #3 might
 672   // not hold in the entire tree.) Restore property #3.
 673   //
 674
 675   NewRoot = Tree->Root;
 676   while (Tmp != NewRoot && Parent->Color == RedBlackTreeRed) {
 677     RED_BLACK_TREE_NODE *GrandParent;
 678     RED_BLACK_TREE_NODE *Uncle;
 679
 680     //
 681     // Tmp is not the root node. Tmp is red. Tmp's parent is red. (Breaking
 682     // property #3.)
 683     //
 684     // Due to property #5, Tmp's parent cannot be the root node, hence Tmp's
 685     // grandparent exists.
 686     //
 687     // Tmp's grandparent is black, because property #3 is only broken between
 688     // Tmp and Tmp's parent.
 689     //
 690     GrandParent = Parent->Parent;
 691
 692     if (Parent == GrandParent->Left) {
 693       Uncle = GrandParent->Right;
 694       if (Uncle != NULL && Uncle->Color == RedBlackTreeRed) {
 695         //
 696         //             GrandParent (black)
 697         //            /                   \_
 698         // Parent (red)                    Uncle (red)
 699         //      |
 700         //  Tmp (red)
 701         //
 702
 703         Parent->Color = RedBlackTreeBlack;
 704         Uncle->Color = RedBlackTreeBlack;
 705         GrandParent->Color = RedBlackTreeRed;
 706
 707         //
 708         //                GrandParent (red)
 709         //               /                 \_
 710         // Parent (black)                   Uncle (black)
 711         //       |
 712         //   Tmp (red)
 713         //
 714         // We restored property #3 between Tmp and Tmp's parent, without
 715         // breaking property #4. However, we may have broken property #3
 716         // between Tmp's grandparent and Tmp's great-grandparent (if any), so
 717         // repeat the loop for Tmp's grandparent.
 718         //
 719         // If Tmp's grandparent has no parent, then the loop will terminate,
 720         // and we will have broken property #5, by coloring the root red. We'll
 721         // restore property #5 after the loop, without breaking any others.
 722         //
 723         Tmp = GrandParent;
 724         Parent = Tmp->Parent;
 725       } else {
 726         //
 727         // Tmp's uncle is black (satisfied by the case too when Tmp's uncle is
 728         // NULL, see property #2).
 729         //
 730
 731         if (Tmp == Parent->Right) {
 732           //
 733           //                 GrandParent (black): D
 734           //                /                      \_
 735           // Parent (red): A                        Uncle (black): E
 736           //      \_
 737           //       Tmp (red): B
 738           //            \_
 739           //             black: C
 740           //
 741           // Rotate left, pivoting on node A. This keeps the breakage of
 742           // property #3 in the same spot, and keeps other properties intact
 743           // (because both Tmp and its parent are red).
 744           //
 745           Tmp = Parent;
 746           RedBlackTreeRotateLeft (Tmp, &NewRoot);
 747           Parent = Tmp->Parent;
 748
 749           //
 750           // With the rotation we reached the same configuration as if Tmp had
 751           // been a left child to begin with.
 752           //
 753           //                       GrandParent (black): D
 754           //                      /                      \_
 755           //       Parent (red): B                        Uncle (black): E
 756           //             / \_
 757           // Tmp (red): A   black: C
 758           //
 759           ASSERT (GrandParent == Parent->Parent);
 760         }
 761
 762         Parent->Color = RedBlackTreeBlack;
 763         GrandParent->Color = RedBlackTreeRed;
 764
 765         //
 766         // Property #3 is now restored, but we've broken property #4. Namely,
 767         // paths going through node E now see a decrease in black count, while
 768         // paths going through node B don't.
 769         //
 770         //                        GrandParent (red): D
 771         //                       /                    \_
 772         //      Parent (black): B                      Uncle (black): E
 773         //             / \_
 774         // Tmp (red): A   black: C
 775         //
 776
 777         RedBlackTreeRotateRight (GrandParent, &NewRoot);
 778
 779         //
 780         // Property #4 has been restored for node E, and preserved for others.
 781         //
 782         //              Parent (black): B
 783         //             /                 \_
 784         // Tmp (red): A                   [GrandParent] (red): D
 785         //                                         / \_
 786         //                                 black: C   [Uncle] (black): E
 787         //
 788         // This configuration terminates the loop because Tmp's parent is now
 789         // black.
 790         //
 791       }
 792     } else {
 793       //
 794       // Symmetrical to the other branch.
 795       //
 796       Uncle = GrandParent->Left;
 797       if (Uncle != NULL && Uncle->Color == RedBlackTreeRed) {
 798         Parent->Color = RedBlackTreeBlack;
 799         Uncle->Color = RedBlackTreeBlack;
 800         GrandParent->Color = RedBlackTreeRed;
 801         Tmp = GrandParent;
 802         Parent = Tmp->Parent;
 803       } else {
 804         if (Tmp == Parent->Left) {
 805           Tmp = Parent;
 806           RedBlackTreeRotateRight (Tmp, &NewRoot);
 807           Parent = Tmp->Parent;
 808           ASSERT (GrandParent == Parent->Parent);
 809         }
 810         Parent->Color = RedBlackTreeBlack;
 811         GrandParent->Color = RedBlackTreeRed;
 812         RedBlackTreeRotateLeft (GrandParent, &NewRoot);
 813       }
 814     }
 815   }
 816
 817   NewRoot->Color = RedBlackTreeBlack;
 818   Tree->Root = NewRoot;
 819   Status = RETURN_SUCCESS;
 820
 821 Done:
 822   if (FeaturePcdGet (PcdValidateOrderedCollection)) {
 823     RedBlackTreeValidate (Tree);
 824   }
 825   return Status;
 826 }
 827
 828
 829 /**
 830   Check if a node is black, allowing for leaf nodes (see property #2).
 831
 832   This is a convenience shorthand.
 833
 834   param[in] Node  The node to check. Node may be NULL, corresponding to a leaf.
 835
 836   @return  If Node is NULL or colored black.
 837 **/
 838 BOOLEAN
 839 NodeIsNullOrBlack (
 840   IN CONST RED_BLACK_TREE_NODE *Node
 841   )
 842 {
 843   return (BOOLEAN)(Node == NULL || Node->Color == RedBlackTreeBlack);
 844 }
 845
 846
 847 /**
 848   Delete a node from the tree, unlinking the associated user structure.
 849
 850   Read-write operation.
 851
 852   @param[in,out] Tree        The tree to delete Node from.
 853
 854   @param[in]     Node        The tree node to delete from Tree. The caller is
 855                              responsible for ensuring that Node belongs to
 856                              Tree, and that Node is non-NULL and valid. Node is
 857                              typically an earlier return value, or output
 858                              parameter, of:
 859
 860                              - OrderedCollectionFind(), for deleting a node by
 861                                user structure key,
 862
 863                              - OrderedCollectionMin() / OrderedCollectionMax(),
 864                                for deleting the minimum / maximum node,
 865
 866                              - OrderedCollectionNext() /
 867                                OrderedCollectionPrev(), for deleting a node
 868                                found during an iteration,
 869
 870                              - OrderedCollectionInsert() with return value
 871                                RETURN_ALREADY_STARTED, for deleting a node
 872                                whose linked user structure caused collision
 873                                during insertion.
 874
 875                              Given a non-empty Tree, Tree->Root is also a valid
 876                              Node argument (typically used for simplicity in
 877                              loops that empty the tree completely).
 878
 879                              Node is released with MemoryAllocationLib's
 880                              FreePool() function.
 881
 882                              Existing RED_BLACK_TREE_NODE pointers (ie.
 883                              iterators) *different* from Node remain valid. For
 884                              example:
 885
 886                              - OrderedCollectionNext() /
 887                                OrderedCollectionPrev() iterations in the caller
 888                                can be continued from Node, if
 889                                OrderedCollectionNext() or
 890                                OrderedCollectionPrev() is called on Node
 891                                *before* OrderedCollectionDelete() is. That is,
 892                                fetch the successor / predecessor node first,
 893                                then delete Node.
 894
 895                              - On-going iterations in the caller that would
 896                                have otherwise returned Node at some point, as
 897                                dictated by user structure order, will correctly
 898                                reflect the absence of Node after
 899                                OrderedCollectionDelete() is called
 900                                mid-iteration.
 901
 902   @param[out]    UserStruct  If the caller provides this optional output-only
 903                              parameter, then on output it is set to the user
 904                              structure originally linked by Node (which is now
 905                              freed).
 906
 907                              This is a convenience that may save the caller a
 908                              OrderedCollectionUserStruct() invocation before
 909                              calling OrderedCollectionDelete(), in order to
 910                              retrieve the user structure being unlinked.
 911 **/
 912 VOID
 913 EFIAPI
 914 OrderedCollectionDelete (
 915   IN OUT RED_BLACK_TREE      *Tree,
 916   IN     RED_BLACK_TREE_NODE *Node,
 917   OUT    VOID                **UserStruct OPTIONAL
 918   )
 919 {
 920   RED_BLACK_TREE_NODE  *NewRoot;
 921   RED_BLACK_TREE_NODE  *OrigLeftChild;
 922   RED_BLACK_TREE_NODE  *OrigRightChild;
 923   RED_BLACK_TREE_NODE  *OrigParent;
 924   RED_BLACK_TREE_NODE  *Child;
 925   RED_BLACK_TREE_NODE  *Parent;
 926   RED_BLACK_TREE_COLOR ColorOfUnlinked;
 927
 928   NewRoot        = Tree->Root;
 929   OrigLeftChild  = Node->Left,
 930   OrigRightChild = Node->Right,
 931   OrigParent     = Node->Parent;
 932
 933   if (UserStruct != NULL) {
 934     *UserStruct = Node->UserStruct;
 935   }
 936
 937   //
 938   // After this block, no matter which branch we take:
 939   // - Child will point to the unique (or NULL) original child of the node that
 940   //   we will have unlinked,
 941   // - Parent will point to the *position* of the original parent of the node
 942   //   that we will have unlinked.
 943   //
 944   if (OrigLeftChild == NULL || OrigRightChild == NULL) {
 945     //
 946     // Node has at most one child. We can connect that child (if any) with
 947     // Node's parent (if any), unlinking Node. This will preserve ordering
 948     // because the subtree rooted in Node's child (if any) remains on the same
 949     // side of Node's parent (if any) that Node was before.
 950     //
 951     Parent = OrigParent;
 952     Child = (OrigLeftChild != NULL) ? OrigLeftChild : OrigRightChild;
 953     ColorOfUnlinked = Node->Color;
 954
 955     if (Child != NULL) {
 956       Child->Parent = Parent;
 957     }
 958     if (OrigParent == NULL) {
 959       NewRoot = Child;
 960     } else {
 961       if (Node == OrigParent->Left) {
 962         OrigParent->Left = Child;
 963       } else {
 964         OrigParent->Right = Child;
 965       }
 966     }
 967   } else {
 968     //
 969     // Node has two children. We unlink Node's successor, and then link it into
 970     // Node's place, keeping Node's original color. This preserves ordering
 971     // because:
 972     // - Node's left subtree is less than Node, hence less than Node's
 973     //   successor.
 974     // - Node's right subtree is greater than Node. Node's successor is the
 975     //   minimum of that subtree, hence Node's successor is less than Node's
 976     //   right subtree with its minimum removed.
 977     // - Node's successor is in Node's subtree, hence it falls on the same side
 978     //   of Node's parent as Node itself. The relinking doesn't change this
 979     //   relation.
 980     //
 981     RED_BLACK_TREE_NODE *ToRelink;
 982
 983     ToRelink = OrigRightChild;
 984     if (ToRelink->Left == NULL) {
 985       //
 986       // OrigRightChild itself is Node's successor, it has no left child:
 987       //
 988       //                OrigParent
 989       //                    |
 990       //                  Node: B
 991       //                 /       \_
 992       // OrigLeftChild: A         OrigRightChild: E <--- Parent, ToRelink
 993       //                                           \_
 994       //                                            F <--- Child
 995       //
 996       Parent = OrigRightChild;
 997       Child = OrigRightChild->Right;
 998     } else {
 999       do {
1000         ToRelink = ToRelink->Left;
1001       } while (ToRelink->Left != NULL);
1002
1003       //
1004       // Node's successor is the minimum of OrigRightChild's proper subtree:
1005       //
1006       //                OrigParent
1007       //                    |
1008       //                  Node: B
1009       //                 /       \_
1010       // OrigLeftChild: A         OrigRightChild: E <--- Parent
1011       //                                  /
1012       //                                 C <--- ToRelink
1013       //                                  \_
1014       //                                   D <--- Child
1015       Parent = ToRelink->Parent;
1016       Child = ToRelink->Right;
1017
1018       //
1019       // Unlink Node's successor (ie. ToRelink):
1020       //
1021       //                OrigParent
1022       //                    |
1023       //                  Node: B
1024       //                 /       \_
1025       // OrigLeftChild: A         OrigRightChild: E <--- Parent
1026       //                                  /
1027       //                                 D <--- Child
1028       //
1029       //                                 C <--- ToRelink
1030       //
1031       Parent->Left = Child;
1032       if (Child != NULL) {
1033         Child->Parent = Parent;
1034       }
1035
1036       //
1037       // We start to link Node's unlinked successor into Node's place:
1038       //
1039       //                OrigParent
1040       //                    |
1041       //                  Node: B     C <--- ToRelink
1042       //                 /             \_
1043       // OrigLeftChild: A               OrigRightChild: E <--- Parent
1044       //                                        /
1045       //                                       D <--- Child
1046       //
1047       //
1048       //
1049       ToRelink->Right = OrigRightChild;
1050       OrigRightChild->Parent = ToRelink;
1051     }
1052
1053     //
1054     // The rest handles both cases, attaching ToRelink (Node's original
1055     // successor) to OrigLeftChild and OrigParent.
1056     //
1057     //                           Parent,
1058     //              OrigParent   ToRelink             OrigParent
1059     //                  |        |                        |
1060     //                Node: B    |                      Node: B          Parent
1061     //                           v                                          |
1062     //           OrigRightChild: E                        C <--- ToRelink   |
1063     //                 / \                               / \                v
1064     // OrigLeftChild: A   F              OrigLeftChild: A   OrigRightChild: E
1065     //                    ^                                         /
1066     //                    |                                        D <--- Child
1067     //                  Child
1068     //
1069     ToRelink->Left = OrigLeftChild;
1070     OrigLeftChild->Parent = ToRelink;
1071
1072     //
1073     // Node's color must be preserved in Node's original place.
1074     //
1075     ColorOfUnlinked = ToRelink->Color;
1076     ToRelink->Color = Node->Color;
1077
1078     //
1079     // Finish linking Node's unlinked successor into Node's place.
1080     //
1081     //                           Parent,
1082     //                Node: B    ToRelink               Node: B
1083     //                           |
1084     //              OrigParent   |                    OrigParent         Parent
1085     //                  |        v                        |                 |
1086     //           OrigRightChild: E                        C <--- ToRelink   |
1087     //                 / \                               / \                v
1088     // OrigLeftChild: A   F              OrigLeftChild: A   OrigRightChild: E
1089     //                    ^                                         /
1090     //                    |                                        D <--- Child
1091     //                  Child
1092     //
1093     ToRelink->Parent = OrigParent;
1094     if (OrigParent == NULL) {
1095       NewRoot = ToRelink;
1096     } else {
1097       if (Node == OrigParent->Left) {
1098         OrigParent->Left = ToRelink;
1099       } else {
1100         OrigParent->Right = ToRelink;
1101       }
1102     }
1103   }
1104
1105   FreePool (Node);
1106
1107   //
1108   // If the node that we unlinked from its original spot (ie. Node itself, or
1109   // Node's successor), was red, then we broke neither property #3 nor property
1110   // #4: we didn't create any red-red edge between Child and Parent, and we
1111   // didn't change the black count on any path.
1112   //
1113   if (ColorOfUnlinked == RedBlackTreeBlack) {
1114     //
1115     // However, if the unlinked node was black, then we have to transfer its
1116     // "black-increment" to its unique child (pointed-to by Child), lest we
1117     // break property #4 for its ancestors.
1118     //
1119     // If Child is red, we can simply color it black. If Child is black
1120     // already, we can't technically transfer a black-increment to it, due to
1121     // property #1.
1122     //
1123     // In the following loop we ascend searching for a red node to color black,
1124     // or until we reach the root (in which case we can drop the
1125     // black-increment). Inside the loop body, Child has a black value of 2,
1126     // transitorily breaking property #1 locally, but maintaining property #4
1127     // globally.
1128     //
1129     // Rotations in the loop preserve property #4.
1130     //
1131     while (Child != NewRoot && NodeIsNullOrBlack (Child)) {
1132       RED_BLACK_TREE_NODE *Sibling;
1133       RED_BLACK_TREE_NODE *LeftNephew;
1134       RED_BLACK_TREE_NODE *RightNephew;
1135
1136       if (Child == Parent->Left) {
1137         Sibling = Parent->Right;
1138         //
1139         // Sibling can never be NULL (ie. a leaf).
1140         //
1141         // If Sibling was NULL, then the black count on the path from Parent to
1142         // Sibling would equal Parent's black value, plus 1 (due to property
1143         // #2). Whereas the black count on the path from Parent to any leaf via
1144         // Child would be at least Parent's black value, plus 2 (due to Child's
1145         // black value of 2). This would clash with property #4.
1146         //
1147         // (Sibling can be black of course, but it has to be an internal node.
1148         // Internality allows Sibling to have children, bumping the black
1149         // counts of paths that go through it.)
1150         //
1151         ASSERT (Sibling != NULL);
1152         if (Sibling->Color == RedBlackTreeRed) {
1153           //
1154           // Sibling's red color implies its children (if any), node C and node
1155           // E, are black (property #3). It also implies that Parent is black.
1156           //
1157           //           grandparent                                 grandparent
1158           //                |                                           |
1159           //            Parent,b:B                                     b:D
1160           //           /          \                                   /   \_
1161           // Child,2b:A            Sibling,r:D  --->        Parent,r:B     b:E
1162           //                           /\                       /\_
1163           //                        b:C  b:E          Child,2b:A  Sibling,b:C
1164           //
1165           Sibling->Color = RedBlackTreeBlack;
1166           Parent->Color = RedBlackTreeRed;
1167           RedBlackTreeRotateLeft (Parent, &NewRoot);
1168           Sibling = Parent->Right;
1169           //
1170           // Same reasoning as above.
1171           //
1172           ASSERT (Sibling != NULL);
1173         }
1174
1175         //
1176         // Sibling is black, and not NULL. (Ie. Sibling is a black internal
1177         // node.)
1178         //
1179         ASSERT (Sibling->Color == RedBlackTreeBlack);
1180         LeftNephew = Sibling->Left;
1181         RightNephew = Sibling->Right;
1182         if (NodeIsNullOrBlack (LeftNephew) &&
1183             NodeIsNullOrBlack (RightNephew)) {
1184           //
1185           // In this case we can "steal" one black value from Child and Sibling
1186           // each, and pass it to Parent. "Stealing" means that Sibling (black
1187           // value 1) becomes red, Child (black value 2) becomes singly-black,
1188           // and Parent will have to be examined if it can eat the
1189           // black-increment.
1190           //
1191           // Sibling is allowed to become red because both of its children are
1192           // black (property #3).
1193           //
1194           //           grandparent                             Parent
1195           //                |                                     |
1196           //            Parent,x:B                            Child,x:B
1197           //           /          \                          /         \_
1198           // Child,2b:A            Sibling,b:D    --->    b:A           r:D
1199           //                           /\                                /\_
1200           //             LeftNephew,b:C  RightNephew,b:E              b:C  b:E
1201           //
1202           Sibling->Color = RedBlackTreeRed;
1203           Child = Parent;
1204           Parent = Parent->Parent;
1205           //
1206           // Continue ascending.
1207           //
1208         } else {
1209           //
1210           // At least one nephew is red.
1211           //
1212           if (NodeIsNullOrBlack (RightNephew)) {
1213             //
1214             // Since the right nephew is black, the left nephew is red. Due to
1215             // property #3, LeftNephew has two black children, hence node E is
1216             // black.
1217             //
1218             // Together with the rotation, this enables us to color node F red
1219             // (because property #3 will be satisfied). We flip node D to black
1220             // to maintain property #4.
1221             //
1222             //      grandparent                         grandparent
1223             //           |                                   |
1224             //       Parent,x:B                          Parent,x:B
1225             //           /\                                  /\_
1226             // Child,2b:A  Sibling,b:F     --->    Child,2b:A  Sibling,b:D
1227             //                  /\                            /   \_
1228             //    LeftNephew,r:D  RightNephew,b:G          b:C  RightNephew,r:F
1229             //               /\                                       /\_
1230             //            b:C  b:E                                 b:E  b:G
1231             //
1232             LeftNephew->Color = RedBlackTreeBlack;
1233             Sibling->Color = RedBlackTreeRed;
1234             RedBlackTreeRotateRight (Sibling, &NewRoot);
1235             Sibling = Parent->Right;
1236             RightNephew = Sibling->Right;
1237             //
1238             // These operations ensure that...
1239             //
1240           }
1241           //
1242           // ... RightNephew is definitely red here, plus Sibling is (still)
1243           // black and non-NULL.
1244           //
1245           ASSERT (RightNephew != NULL);
1246           ASSERT (RightNephew->Color == RedBlackTreeRed);
1247           ASSERT (Sibling != NULL);
1248           ASSERT (Sibling->Color == RedBlackTreeBlack);
1249           //
1250           // In this case we can flush the extra black-increment immediately,
1251           // restoring property #1 for Child (node A): we color RightNephew
1252           // (node E) from red to black.
1253           //
1254           // In order to maintain property #4, we exchange colors between
1255           // Parent and Sibling (nodes B and D), and rotate left around Parent
1256           // (node B). The transformation doesn't change the black count
1257           // increase incurred by each partial path, eg.
1258           // - ascending from node A: 2 + x     == 1 + 1 + x
1259           // - ascending from node C: y + 1 + x == y + 1 + x
1260           // - ascending from node E: 0 + 1 + x == 1 + x
1261           //
1262           // The color exchange is valid, because even if x stands for red,
1263           // both children of node D are black after the transformation
1264           // (preserving property #3).
1265           //
1266           //           grandparent                                  grandparent
1267           //                |                                            |
1268           //            Parent,x:B                                      x:D
1269           //           /          \                                    /   \_
1270           // Child,2b:A            Sibling,b:D              --->    b:B     b:E
1271           //                         /     \                       /   \_
1272           //                      y:C       RightNephew,r:E     b:A     y:C
1273           //
1274           //
1275           Sibling->Color = Parent->Color;
1276           Parent->Color = RedBlackTreeBlack;
1277           RightNephew->Color = RedBlackTreeBlack;
1278           RedBlackTreeRotateLeft (Parent, &NewRoot);
1279           Child = NewRoot;
1280           //
1281           // This terminates the loop.
1282           //
1283         }
1284       } else {
1285         //
1286         // Mirrors the other branch.
1287         //
1288         Sibling = Parent->Left;
1289         ASSERT (Sibling != NULL);
1290         if (Sibling->Color == RedBlackTreeRed) {
1291           Sibling->Color = RedBlackTreeBlack;
1292           Parent->Color = RedBlackTreeRed;
1293           RedBlackTreeRotateRight (Parent, &NewRoot);
1294           Sibling = Parent->Left;
1295           ASSERT (Sibling != NULL);
1296         }
1297
1298         ASSERT (Sibling->Color == RedBlackTreeBlack);
1299         RightNephew = Sibling->Right;
1300         LeftNephew = Sibling->Left;
1301         if (NodeIsNullOrBlack (RightNephew) &&
1302             NodeIsNullOrBlack (LeftNephew)) {
1303           Sibling->Color = RedBlackTreeRed;
1304           Child = Parent;
1305           Parent = Parent->Parent;
1306         } else {
1307           if (NodeIsNullOrBlack (LeftNephew)) {
1308             RightNephew->Color = RedBlackTreeBlack;
1309             Sibling->Color = RedBlackTreeRed;
1310             RedBlackTreeRotateLeft (Sibling, &NewRoot);
1311             Sibling = Parent->Left;
1312             LeftNephew = Sibling->Left;
1313           }
1314           ASSERT (LeftNephew != NULL);
1315           ASSERT (LeftNephew->Color == RedBlackTreeRed);
1316           ASSERT (Sibling != NULL);
1317           ASSERT (Sibling->Color == RedBlackTreeBlack);
1318           Sibling->Color = Parent->Color;
1319           Parent->Color = RedBlackTreeBlack;
1320           LeftNephew->Color = RedBlackTreeBlack;
1321           RedBlackTreeRotateRight (Parent, &NewRoot);
1322           Child = NewRoot;
1323         }
1324       }
1325     }
1326
1327     if (Child != NULL) {
1328       Child->Color = RedBlackTreeBlack;
1329     }
1330   }
1331
1332   Tree->Root = NewRoot;
1333
1334   if (FeaturePcdGet (PcdValidateOrderedCollection)) {
1335     RedBlackTreeValidate (Tree);
1336   }
1337 }
1338
1339
1340 /**
1341   Recursively check the red-black tree properties #1 to #4 on a node.
1342
1343   @param[in] Node  The root of the subtree to validate.
1344
1345   @retval  The black-height of Node's parent.
1346 **/
1347 UINT32
1348 RedBlackTreeRecursiveCheck (
1349   IN CONST RED_BLACK_TREE_NODE *Node
1350   )
1351 {
1352   UINT32 LeftHeight;
1353   UINT32 RightHeight;
1354
1355   //
1356   // property #2
1357   //
1358   if (Node == NULL) {
1359     return 1;
1360   }
1361
1362   //
1363   // property #1
1364   //
1365   ASSERT (Node->Color == RedBlackTreeRed || Node->Color == RedBlackTreeBlack);
1366
1367   //
1368   // property #3
1369   //
1370   if (Node->Color == RedBlackTreeRed) {
1371     ASSERT (NodeIsNullOrBlack (Node->Left));
1372     ASSERT (NodeIsNullOrBlack (Node->Right));
1373   }
1374
1375   //
1376   // property #4
1377   //
1378   LeftHeight = RedBlackTreeRecursiveCheck (Node->Left);
1379   RightHeight = RedBlackTreeRecursiveCheck (Node->Right);
1380   ASSERT (LeftHeight == RightHeight);
1381
1382   return (Node->Color == RedBlackTreeBlack) + LeftHeight;
1383 }
1384
1385
1386 /**
1387   A slow function that asserts that the tree is a valid red-black tree, and
1388   that it orders user structures correctly.
1389
1390   Read-only operation.
1391
1392   This function uses the stack for recursion and is not recommended for
1393   "production use".
1394
1395   @param[in] Tree  The tree to validate.
1396 **/
1397 VOID
1398 RedBlackTreeValidate (
1399   IN CONST RED_BLACK_TREE *Tree
1400   )
1401 {
1402   UINT32                    BlackHeight;
1403   UINT32                    ForwardCount;
1404   UINT32                    BackwardCount;
1405   CONST RED_BLACK_TREE_NODE *Last;
1406   CONST RED_BLACK_TREE_NODE *Node;
1407
1408   DEBUG ((DEBUG_VERBOSE, "%a: Tree=%p\n", __FUNCTION__, Tree));
1409
1410   //
1411   // property #5
1412   //
1413   ASSERT (NodeIsNullOrBlack (Tree->Root));
1414
1415   //
1416   // check the other properties
1417   //
1418   BlackHeight = RedBlackTreeRecursiveCheck (Tree->Root) - 1;
1419
1420   //
1421   // forward ordering
1422   //
1423   Last = OrderedCollectionMin (Tree);
1424   ForwardCount = (Last != NULL);
1425   for (Node = OrderedCollectionNext (Last); Node != NULL;
1426        Node = OrderedCollectionNext (Last)) {
1427     ASSERT (Tree->UserStructCompare (Last->UserStruct, Node->UserStruct) < 0);
1428     Last = Node;
1429     ++ForwardCount;
1430   }
1431
1432   //
1433   // backward ordering
1434   //
1435   Last = OrderedCollectionMax (Tree);
1436   BackwardCount = (Last != NULL);
1437   for (Node = OrderedCollectionPrev (Last); Node != NULL;
1438        Node = OrderedCollectionPrev (Last)) {
1439     ASSERT (Tree->UserStructCompare (Last->UserStruct, Node->UserStruct) > 0);
1440     Last = Node;
1441     ++BackwardCount;
1442   }
1443
1444   ASSERT (ForwardCount == BackwardCount);
1445
1446   DEBUG ((DEBUG_VERBOSE, "%a: Tree=%p BlackHeight=%Ld Count=%Ld\n",
1447     __FUNCTION__, Tree, (INT64)BlackHeight, (INT64)ForwardCount));
1448 }