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