2 An OrderedCollectionLib instance that provides a red-black tree
3 implementation, and allocates and releases tree nodes with
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.
11 The implementation is also useful as a fast priority queue.
13 Copyright (C) 2014, Red Hat, Inc.
15 This program and the accompanying materials are licensed and made available
16 under the terms and conditions of the BSD License that accompanies this
17 distribution. The full text of the license may be found at
18 http://opensource.org/licenses/bsd-license.php.
20 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, WITHOUT
21 WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
24 #include <Library/OrderedCollectionLib.h>
25 #include <Library/DebugLib.h>
26 #include <Library/MemoryAllocationLib.h>
31 } RED_BLACK_TREE_COLOR
;
34 // Incomplete types and convenience typedefs are present in the library class
35 // header. Beside completing the types, we introduce typedefs here that reflect
36 // the implementation closely.
38 typedef ORDERED_COLLECTION RED_BLACK_TREE
;
39 typedef ORDERED_COLLECTION_ENTRY RED_BLACK_TREE_NODE
;
40 typedef ORDERED_COLLECTION_USER_COMPARE RED_BLACK_TREE_USER_COMPARE
;
41 typedef ORDERED_COLLECTION_KEY_COMPARE RED_BLACK_TREE_KEY_COMPARE
;
43 struct ORDERED_COLLECTION
{
44 RED_BLACK_TREE_NODE
*Root
;
45 RED_BLACK_TREE_USER_COMPARE UserStructCompare
;
46 RED_BLACK_TREE_KEY_COMPARE KeyCompare
;
49 struct ORDERED_COLLECTION_ENTRY
{
51 RED_BLACK_TREE_NODE
*Parent
;
52 RED_BLACK_TREE_NODE
*Left
;
53 RED_BLACK_TREE_NODE
*Right
;
54 RED_BLACK_TREE_COLOR Color
;
59 Retrieve the user structure linked by the specified tree node.
63 @param[in] Node Pointer to the tree node whose associated user structure we
64 want to retrieve. The caller is responsible for passing a
67 @return Pointer to user structure linked by Node.
71 OrderedCollectionUserStruct (
72 IN CONST RED_BLACK_TREE_NODE
*Node
75 return Node
->UserStruct
;
80 // Forward declaration of internal, unit test helper function. See
81 // specification and function definition later.
85 RedBlackTreeValidate (
86 IN CONST RED_BLACK_TREE
*Tree
91 Allocate and initialize the RED_BLACK_TREE structure.
93 Allocation occurs via MemoryAllocationLib's AllocatePool() function.
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.
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
104 @retval NULL If allocation failed.
106 @return Pointer to the allocated, initialized RED_BLACK_TREE structure,
111 OrderedCollectionInit (
112 IN RED_BLACK_TREE_USER_COMPARE UserStructCompare
,
113 IN RED_BLACK_TREE_KEY_COMPARE KeyCompare
116 RED_BLACK_TREE
*Tree
;
118 Tree
= AllocatePool (sizeof *Tree
);
124 Tree
->UserStructCompare
= UserStructCompare
;
125 Tree
->KeyCompare
= KeyCompare
;
127 if (FeaturePcdGet (PcdValidateOrderedCollection
)) {
128 RedBlackTreeValidate (Tree
);
135 Check whether the tree is empty (has no nodes).
139 @param[in] Tree The tree to check for emptiness.
141 @retval TRUE The tree is empty.
143 @retval FALSE The tree is not empty.
147 OrderedCollectionIsEmpty (
148 IN CONST RED_BLACK_TREE
*Tree
151 return Tree
->Root
== NULL
;
156 Uninitialize and release an empty RED_BLACK_TREE structure.
158 Read-write operation.
160 Release occurs via MemoryAllocationLib's FreePool() function.
162 It is the caller's responsibility to delete all nodes from the tree before
163 calling this function.
165 @param[in] Tree The empty tree to uninitialize and release.
169 OrderedCollectionUninit (
170 IN RED_BLACK_TREE
*Tree
173 ASSERT (OrderedCollectionIsEmpty (Tree
));
179 Look up the tree node that links the user structure that matches the
180 specified standalone key.
184 @param[in] Tree The tree to search for StandaloneKey.
186 @param[in] StandaloneKey The key to locate among the user structures linked
187 into Tree. StandaloneKey will be passed to
190 @retval NULL StandaloneKey could not be found.
192 @return The tree node that links to the user structure matching
193 StandaloneKey, otherwise.
195 RED_BLACK_TREE_NODE
*
197 OrderedCollectionFind (
198 IN CONST RED_BLACK_TREE
*Tree
,
199 IN CONST VOID
*StandaloneKey
202 RED_BLACK_TREE_NODE
*Node
;
205 while (Node
!= NULL
) {
208 Result
= Tree
->KeyCompare (StandaloneKey
, Node
->UserStruct
);
212 Node
= (Result
< 0) ? Node
->Left
: Node
->Right
;
219 Find the tree node of the minimum user structure stored in the tree.
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.
227 @retval NULL If Tree is empty.
229 @return The tree node that links the minimum user structure, otherwise.
231 RED_BLACK_TREE_NODE
*
233 OrderedCollectionMin (
234 IN CONST RED_BLACK_TREE
*Tree
237 RED_BLACK_TREE_NODE
*Node
;
243 while (Node
->Left
!= NULL
) {
251 Find the tree node of the maximum user structure stored in the tree.
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.
259 @retval NULL If Tree is empty.
261 @return The tree node that links the maximum user structure, otherwise.
263 RED_BLACK_TREE_NODE
*
265 OrderedCollectionMax (
266 IN CONST RED_BLACK_TREE
*Tree
269 RED_BLACK_TREE_NODE
*Node
;
275 while (Node
->Right
!= NULL
) {
283 Get the tree node of the least user structure that is greater than the one
288 @param[in] Node The node to get the successor node of.
290 @retval NULL If Node is NULL, or Node is the maximum node of its containing
291 tree (ie. Node has no successor node).
293 @return The tree node linking the least user structure that is greater
294 than the one linked by Node, otherwise.
296 RED_BLACK_TREE_NODE
*
298 OrderedCollectionNext (
299 IN CONST RED_BLACK_TREE_NODE
*Node
302 RED_BLACK_TREE_NODE
*Walk
;
303 CONST RED_BLACK_TREE_NODE
*Child
;
310 // If Node has a right subtree, then the successor is the minimum node of
315 while (Walk
->Left
!= NULL
) {
322 // Otherwise we have to ascend as long as we're our parent's right child (ie.
323 // ascending to the left).
326 Walk
= Child
->Parent
;
327 while (Walk
!= NULL
&& Child
== Walk
->Right
) {
329 Walk
= Child
->Parent
;
336 Get the tree node of the greatest user structure that is less than the one
341 @param[in] Node The node to get the predecessor node of.
343 @retval NULL If Node is NULL, or Node is the minimum node of its containing
344 tree (ie. Node has no predecessor node).
346 @return The tree node linking the greatest user structure that is less
347 than the one linked by Node, otherwise.
349 RED_BLACK_TREE_NODE
*
351 OrderedCollectionPrev (
352 IN CONST RED_BLACK_TREE_NODE
*Node
355 RED_BLACK_TREE_NODE
*Walk
;
356 CONST RED_BLACK_TREE_NODE
*Child
;
363 // If Node has a left subtree, then the predecessor is the maximum node of
368 while (Walk
->Right
!= NULL
) {
375 // Otherwise we have to ascend as long as we're our parent's left child (ie.
376 // ascending to the right).
379 Walk
= Child
->Parent
;
380 while (Walk
!= NULL
&& Child
== Walk
->Left
) {
382 Walk
= Child
->Parent
;
389 Rotate tree nodes around Pivot to the right.
395 LeftChild Node1 ---> Node2 Pivot
397 Node2 LeftRightChild LeftRightChild Node1
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.
403 Edges marked with a dot (".") don't change during rotation.
405 Internal read-write operation.
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.
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
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.
422 RedBlackTreeRotateRight (
423 IN OUT RED_BLACK_TREE_NODE
*Pivot
,
424 OUT RED_BLACK_TREE_NODE
**NewRoot
427 RED_BLACK_TREE_NODE
*Parent
, *LeftChild
, *LeftRightChild
;
429 Parent
= Pivot
->Parent
;
430 LeftChild
= Pivot
->Left
;
431 LeftRightChild
= LeftChild
->Right
;
433 Pivot
->Left
= LeftRightChild
;
434 if (LeftRightChild
!= NULL
) {
435 LeftRightChild
->Parent
= Pivot
;
437 LeftChild
->Parent
= Parent
;
438 if (Parent
== NULL
) {
439 *NewRoot
= LeftChild
;
441 if (Pivot
== Parent
->Left
) {
442 Parent
->Left
= LeftChild
;
444 Parent
->Right
= LeftChild
;
447 LeftChild
->Right
= Pivot
;
448 Pivot
->Parent
= LeftChild
;
453 Rotate tree nodes around Pivot to the left.
459 Node1 RightChild ---> Pivot Node2
461 RightLeftChild Node2 Node1 RightLeftChild
463 The ordering Node1 < Pivot < RightLeftChild < RightChild < Node2 is kept
464 intact. Parent (if any) is either at the left extreme or the right extreme of
465 this ordering, and that relation is also kept intact.
467 Edges marked with a dot (".") don't change during rotation.
469 Internal read-write operation.
471 @param[in,out] Pivot The tree node to rotate other nodes left around. It
472 is the caller's responsibility to ensure that
473 Pivot->Right is not NULL.
475 @param[out] NewRoot If Pivot has a parent node on input, then the
476 function updates Pivot's original parent on output
477 according to the rotation, and NewRoot is not
480 If Pivot has no parent node on input (ie. Pivot is
481 the root of the tree), then the function stores the
482 new root node of the tree in NewRoot.
486 RedBlackTreeRotateLeft (
487 IN OUT RED_BLACK_TREE_NODE
*Pivot
,
488 OUT RED_BLACK_TREE_NODE
**NewRoot
491 RED_BLACK_TREE_NODE
*Parent
, *RightChild
, *RightLeftChild
;
493 Parent
= Pivot
->Parent
;
494 RightChild
= Pivot
->Right
;
495 RightLeftChild
= RightChild
->Left
;
497 Pivot
->Right
= RightLeftChild
;
498 if (RightLeftChild
!= NULL
) {
499 RightLeftChild
->Parent
= Pivot
;
501 RightChild
->Parent
= Parent
;
502 if (Parent
== NULL
) {
503 *NewRoot
= RightChild
;
505 if (Pivot
== Parent
->Left
) {
506 Parent
->Left
= RightChild
;
508 Parent
->Right
= RightChild
;
511 RightChild
->Left
= Pivot
;
512 Pivot
->Parent
= RightChild
;
517 Insert (link) a user structure into the tree.
519 Read-write operation.
521 This function allocates the new tree node with MemoryAllocationLib's
522 AllocatePool() function.
524 @param[in,out] Tree The tree to insert UserStruct into.
526 @param[out] Node The meaning of this optional, output-only
527 parameter depends on the return value of the
530 When insertion is successful (RETURN_SUCCESS),
531 Node is set on output to the new tree node that
532 now links UserStruct.
534 When insertion fails due to lack of memory
535 (RETURN_OUT_OF_RESOURCES), Node is not changed.
537 When insertion fails due to key collision (ie.
538 another user structure is already in the tree that
539 compares equal to UserStruct), with return value
540 RETURN_ALREADY_STARTED, then Node is set on output
541 to the node that links the colliding user
542 structure. This enables "find-or-insert" in one
543 function call, or helps with later removal of the
546 @param[in] UserStruct The user structure to link into the tree.
547 UserStruct is ordered against in-tree user
548 structures with the Tree->UserStructCompare()
551 @retval RETURN_SUCCESS Insertion successful. A new tree node has
552 been allocated, linking UserStruct. The new
553 tree node is reported back in Node (if the
554 caller requested it).
556 Existing RED_BLACK_TREE_NODE pointers into
557 Tree remain valid. For example, on-going
558 iterations in the caller can continue with
559 OrderedCollectionNext() /
560 OrderedCollectionPrev(), and they will
561 return the new node at some point if user
562 structure order dictates it.
564 @retval RETURN_OUT_OF_RESOURCES AllocatePool() failed to allocate memory for
565 the new tree node. The tree has not been
566 changed. Existing RED_BLACK_TREE_NODE
567 pointers into Tree remain valid.
569 @retval RETURN_ALREADY_STARTED A user structure has been found in the tree
570 that compares equal to UserStruct. The node
571 linking the colliding user structure is
572 reported back in Node (if the caller
573 requested it). The tree has not been
574 changed. Existing RED_BLACK_TREE_NODE
575 pointers into Tree remain valid.
579 OrderedCollectionInsert (
580 IN OUT RED_BLACK_TREE
*Tree
,
581 OUT RED_BLACK_TREE_NODE
**Node OPTIONAL
,
585 RED_BLACK_TREE_NODE
*Tmp
, *Parent
;
587 RETURN_STATUS Status
;
588 RED_BLACK_TREE_NODE
*NewRoot
;
595 // First look for a collision, saving the last examined node for the case
596 // when there's no collision.
598 while (Tmp
!= NULL
) {
599 Result
= Tree
->UserStructCompare (UserStruct
, Tmp
->UserStruct
);
604 Tmp
= (Result
< 0) ? Tmp
->Left
: Tmp
->Right
;
611 Status
= RETURN_ALREADY_STARTED
;
616 // no collision, allocate a new node
618 Tmp
= AllocatePool (sizeof *Tmp
);
620 Status
= RETURN_OUT_OF_RESOURCES
;
628 // reference the user structure from the node
630 Tmp
->UserStruct
= UserStruct
;
633 // Link the node as a child to the correct side of the parent.
634 // If there's no parent, the new node is the root node in the tree.
636 Tmp
->Parent
= Parent
;
639 if (Parent
== NULL
) {
641 Tmp
->Color
= RedBlackTreeBlack
;
642 Status
= RETURN_SUCCESS
;
650 Tmp
->Color
= RedBlackTreeRed
;
653 // Red-black tree properties:
655 // #1 Each node is either red or black (RED_BLACK_TREE_NODE.Color).
657 // #2 Each leaf (ie. a pseudo-node pointed-to by a NULL valued
658 // RED_BLACK_TREE_NODE.Left or RED_BLACK_TREE_NODE.Right field) is black.
660 // #3 Each red node has two black children.
662 // #4 For any node N, and for any leaves L1 and L2 reachable from N, the
663 // paths N..L1 and N..L2 contain the same number of black nodes.
665 // #5 The root node is black.
667 // By replacing a leaf with a red node above, only property #3 may have been
668 // broken. (Note that this is the only edge across which property #3 might
669 // not hold in the entire tree.) Restore property #3.
672 NewRoot
= Tree
->Root
;
673 while (Tmp
!= NewRoot
&& Parent
->Color
== RedBlackTreeRed
) {
674 RED_BLACK_TREE_NODE
*GrandParent
, *Uncle
;
677 // Tmp is not the root node. Tmp is red. Tmp's parent is red. (Breaking
680 // Due to property #5, Tmp's parent cannot be the root node, hence Tmp's
681 // grandparent exists.
683 // Tmp's grandparent is black, because property #3 is only broken between
684 // Tmp and Tmp's parent.
686 GrandParent
= Parent
->Parent
;
688 if (Parent
== GrandParent
->Left
) {
689 Uncle
= GrandParent
->Right
;
690 if (Uncle
!= NULL
&& Uncle
->Color
== RedBlackTreeRed
) {
692 // GrandParent (black)
694 // Parent (red) Uncle (red)
699 Parent
->Color
= RedBlackTreeBlack
;
700 Uncle
->Color
= RedBlackTreeBlack
;
701 GrandParent
->Color
= RedBlackTreeRed
;
706 // Parent (black) Uncle (black)
710 // We restored property #3 between Tmp and Tmp's parent, without
711 // breaking property #4. However, we may have broken property #3
712 // between Tmp's grandparent and Tmp's great-grandparent (if any), so
713 // repeat the loop for Tmp's grandparent.
715 // If Tmp's grandparent has no parent, then the loop will terminate,
716 // and we will have broken property #5, by coloring the root red. We'll
717 // restore property #5 after the loop, without breaking any others.
720 Parent
= Tmp
->Parent
;
723 // Tmp's uncle is black (satisfied by the case too when Tmp's uncle is
724 // NULL, see property #2).
727 if (Tmp
== Parent
->Right
) {
729 // GrandParent (black): D
731 // Parent (red): A Uncle (black): E
737 // Rotate left, pivoting on node A. This keeps the breakage of
738 // property #3 in the same spot, and keeps other properties intact
739 // (because both Tmp and its parent are red).
742 RedBlackTreeRotateLeft (Tmp
, &NewRoot
);
743 Parent
= Tmp
->Parent
;
746 // With the rotation we reached the same configuration as if Tmp had
747 // been a left child to begin with.
749 // GrandParent (black): D
751 // Parent (red): B Uncle (black): E
753 // Tmp (red): A black: C
755 ASSERT (GrandParent
== Parent
->Parent
);
758 Parent
->Color
= RedBlackTreeBlack
;
759 GrandParent
->Color
= RedBlackTreeRed
;
762 // Property #3 is now restored, but we've broken property #4. Namely,
763 // paths going through node E now see a decrease in black count, while
764 // paths going through node B don't.
766 // GrandParent (red): D
768 // Parent (black): B Uncle (black): E
770 // Tmp (red): A black: C
773 RedBlackTreeRotateRight (GrandParent
, &NewRoot
);
776 // Property #4 has been restored for node E, and preserved for others.
780 // Tmp (red): A [GrandParent] (red): D
782 // black: C [Uncle] (black): E
784 // This configuration terminates the loop because Tmp's parent is now
790 // Symmetrical to the other branch.
792 Uncle
= GrandParent
->Left
;
793 if (Uncle
!= NULL
&& Uncle
->Color
== RedBlackTreeRed
) {
794 Parent
->Color
= RedBlackTreeBlack
;
795 Uncle
->Color
= RedBlackTreeBlack
;
796 GrandParent
->Color
= RedBlackTreeRed
;
798 Parent
= Tmp
->Parent
;
800 if (Tmp
== Parent
->Left
) {
802 RedBlackTreeRotateRight (Tmp
, &NewRoot
);
803 Parent
= Tmp
->Parent
;
804 ASSERT (GrandParent
== Parent
->Parent
);
806 Parent
->Color
= RedBlackTreeBlack
;
807 GrandParent
->Color
= RedBlackTreeRed
;
808 RedBlackTreeRotateLeft (GrandParent
, &NewRoot
);
813 NewRoot
->Color
= RedBlackTreeBlack
;
814 Tree
->Root
= NewRoot
;
815 Status
= RETURN_SUCCESS
;
818 if (FeaturePcdGet (PcdValidateOrderedCollection
)) {
819 RedBlackTreeValidate (Tree
);
826 Check if a node is black, allowing for leaf nodes (see property #2).
828 This is a convenience shorthand.
830 param[in] Node The node to check. Node may be NULL, corresponding to a leaf.
832 @return If Node is NULL or colored black.
838 IN CONST RED_BLACK_TREE_NODE
*Node
841 return Node
== NULL
|| Node
->Color
== RedBlackTreeBlack
;
846 Delete a node from the tree, unlinking the associated user structure.
848 Read-write operation.
850 @param[in,out] Tree The tree to delete Node from.
852 @param[in] Node The tree node to delete from Tree. The caller is
853 responsible for ensuring that Node belongs to
854 Tree, and that Node is non-NULL and valid. Node is
855 typically an earlier return value, or output
858 - OrderedCollectionFind(), for deleting a node by
861 - OrderedCollectionMin() / OrderedCollectionMax(),
862 for deleting the minimum / maximum node,
864 - OrderedCollectionNext() /
865 OrderedCollectionPrev(), for deleting a node
866 found during an iteration,
868 - OrderedCollectionInsert() with return value
869 RETURN_ALREADY_STARTED, for deleting a node
870 whose linked user structure caused collision
873 Given a non-empty Tree, Tree->Root is also a valid
874 Node argument (typically used for simplicity in
875 loops that empty the tree completely).
877 Node is released with MemoryAllocationLib's
880 Existing RED_BLACK_TREE_NODE pointers (ie.
881 iterators) *different* from Node remain valid. For
884 - OrderedCollectionNext() /
885 OrderedCollectionPrev() iterations in the caller
886 can be continued from Node, if
887 OrderedCollectionNext() or
888 OrderedCollectionPrev() is called on Node
889 *before* OrderedCollectionDelete() is. That is,
890 fetch the successor / predecessor node first,
893 - On-going iterations in the caller that would
894 have otherwise returned Node at some point, as
895 dictated by user structure order, will correctly
896 reflect the absence of Node after
897 OrderedCollectionDelete() is called
900 @param[out] UserStruct If the caller provides this optional output-only
901 parameter, then on output it is set to the user
902 structure originally linked by Node (which is now
905 This is a convenience that may save the caller a
906 OrderedCollectionUserStruct() invocation before
907 calling OrderedCollectionDelete(), in order to
908 retrieve the user structure being unlinked.
912 OrderedCollectionDelete (
913 IN OUT RED_BLACK_TREE
*Tree
,
914 IN RED_BLACK_TREE_NODE
*Node
,
915 OUT VOID
**UserStruct OPTIONAL
918 RED_BLACK_TREE_NODE
*NewRoot
;
919 RED_BLACK_TREE_NODE
*OrigLeftChild
, *OrigRightChild
, *OrigParent
;
920 RED_BLACK_TREE_NODE
*Child
, *Parent
;
921 RED_BLACK_TREE_COLOR ColorOfUnlinked
;
923 NewRoot
= Tree
->Root
;
924 OrigLeftChild
= Node
->Left
,
925 OrigRightChild
= Node
->Right
,
926 OrigParent
= Node
->Parent
;
928 if (UserStruct
!= NULL
) {
929 *UserStruct
= Node
->UserStruct
;
933 // After this block, no matter which branch we take:
934 // - Child will point to the unique (or NULL) original child of the node that
935 // we will have unlinked,
936 // - Parent will point to the *position* of the original parent of the node
937 // that we will have unlinked.
939 if (OrigLeftChild
== NULL
|| OrigRightChild
== NULL
) {
941 // Node has at most one child. We can connect that child (if any) with
942 // Node's parent (if any), unlinking Node. This will preserve ordering
943 // because the subtree rooted in Node's child (if any) remains on the same
944 // side of Node's parent (if any) that Node was before.
947 Child
= (OrigLeftChild
!= NULL
) ? OrigLeftChild
: OrigRightChild
;
948 ColorOfUnlinked
= Node
->Color
;
951 Child
->Parent
= Parent
;
953 if (OrigParent
== NULL
) {
956 if (Node
== OrigParent
->Left
) {
957 OrigParent
->Left
= Child
;
959 OrigParent
->Right
= Child
;
964 // Node has two children. We unlink Node's successor, and then link it into
965 // Node's place, keeping Node's original color. This preserves ordering
967 // - Node's left subtree is less than Node, hence less than Node's
969 // - Node's right subtree is greater than Node. Node's successor is the
970 // minimum of that subtree, hence Node's successor is less than Node's
971 // right subtree with its minimum removed.
972 // - Node's successor is in Node's subtree, hence it falls on the same side
973 // of Node's parent as Node itself. The relinking doesn't change this
976 RED_BLACK_TREE_NODE
*ToRelink
;
978 ToRelink
= OrigRightChild
;
979 if (ToRelink
->Left
== NULL
) {
981 // OrigRightChild itself is Node's successor, it has no left child:
987 // OrigLeftChild: A OrigRightChild: E <--- Parent, ToRelink
991 Parent
= OrigRightChild
;
992 Child
= OrigRightChild
->Right
;
995 ToRelink
= ToRelink
->Left
;
996 } while (ToRelink
->Left
!= NULL
);
999 // Node's successor is the minimum of OrigRightChild's proper subtree:
1005 // OrigLeftChild: A OrigRightChild: E <--- Parent
1010 Parent
= ToRelink
->Parent
;
1011 Child
= ToRelink
->Right
;
1014 // Unlink Node's successor (ie. ToRelink):
1020 // OrigLeftChild: A OrigRightChild: E <--- Parent
1026 Parent
->Left
= Child
;
1028 Child
->Parent
= Parent
;
1032 // We start to link Node's unlinked successor into Node's place:
1036 // Node: B C <--- ToRelink
1038 // OrigLeftChild: A OrigRightChild: E <--- Parent
1044 ToRelink
->Right
= OrigRightChild
;
1045 OrigRightChild
->Parent
= ToRelink
;
1049 // The rest handles both cases, attaching ToRelink (Node's original
1050 // successor) to OrigLeftChild and OrigParent.
1053 // OrigParent ToRelink OrigParent
1055 // Node: B | Node: B Parent
1057 // OrigRightChild: E C <--- ToRelink |
1059 // OrigLeftChild: A F OrigLeftChild: A OrigRightChild: E
1064 ToRelink
->Left
= OrigLeftChild
;
1065 OrigLeftChild
->Parent
= ToRelink
;
1068 // Node's color must be preserved in Node's original place.
1070 ColorOfUnlinked
= ToRelink
->Color
;
1071 ToRelink
->Color
= Node
->Color
;
1074 // Finish linking Node's unlinked successor into Node's place.
1077 // Node: B ToRelink Node: B
1079 // OrigParent | OrigParent Parent
1081 // OrigRightChild: E C <--- ToRelink |
1083 // OrigLeftChild: A F OrigLeftChild: A OrigRightChild: E
1088 ToRelink
->Parent
= OrigParent
;
1089 if (OrigParent
== NULL
) {
1092 if (Node
== OrigParent
->Left
) {
1093 OrigParent
->Left
= ToRelink
;
1095 OrigParent
->Right
= ToRelink
;
1103 // If the node that we unlinked from its original spot (ie. Node itself, or
1104 // Node's successor), was red, then we broke neither property #3 nor property
1105 // #4: we didn't create any red-red edge between Child and Parent, and we
1106 // didn't change the black count on any path.
1108 if (ColorOfUnlinked
== RedBlackTreeBlack
) {
1110 // However, if the unlinked node was black, then we have to transfer its
1111 // "black-increment" to its unique child (pointed-to by Child), lest we
1112 // break property #4 for its ancestors.
1114 // If Child is red, we can simply color it black. If Child is black
1115 // already, we can't technically transfer a black-increment to it, due to
1118 // In the following loop we ascend searching for a red node to color black,
1119 // or until we reach the root (in which case we can drop the
1120 // black-increment). Inside the loop body, Child has a black value of 2,
1121 // transitorily breaking property #1 locally, but maintaining property #4
1124 // Rotations in the loop preserve property #4.
1126 while (Child
!= NewRoot
&& NodeIsNullOrBlack (Child
)) {
1127 RED_BLACK_TREE_NODE
*Sibling
, *LeftNephew
, *RightNephew
;
1129 if (Child
== Parent
->Left
) {
1130 Sibling
= Parent
->Right
;
1132 // Sibling can never be NULL (ie. a leaf).
1134 // If Sibling was NULL, then the black count on the path from Parent to
1135 // Sibling would equal Parent's black value, plus 1 (due to property
1136 // #2). Whereas the black count on the path from Parent to any leaf via
1137 // Child would be at least Parent's black value, plus 2 (due to Child's
1138 // black value of 2). This would clash with property #4.
1140 // (Sibling can be black of course, but it has to be an internal node.
1141 // Internality allows Sibling to have children, bumping the black
1142 // counts of paths that go through it.)
1144 ASSERT (Sibling
!= NULL
);
1145 if (Sibling
->Color
== RedBlackTreeRed
) {
1147 // Sibling's red color implies its children (if any), node C and node
1148 // E, are black (property #3). It also implies that Parent is black.
1150 // grandparent grandparent
1154 // Child,2b:A Sibling,r:D ---> Parent,r:B b:E
1156 // b:C b:E Child,2b:A Sibling,b:C
1158 Sibling
->Color
= RedBlackTreeBlack
;
1159 Parent
->Color
= RedBlackTreeRed
;
1160 RedBlackTreeRotateLeft (Parent
, &NewRoot
);
1161 Sibling
= Parent
->Right
;
1163 // Same reasoning as above.
1165 ASSERT (Sibling
!= NULL
);
1169 // Sibling is black, and not NULL. (Ie. Sibling is a black internal
1172 ASSERT (Sibling
->Color
== RedBlackTreeBlack
);
1173 LeftNephew
= Sibling
->Left
;
1174 RightNephew
= Sibling
->Right
;
1175 if (NodeIsNullOrBlack (LeftNephew
) &&
1176 NodeIsNullOrBlack (RightNephew
)) {
1178 // In this case we can "steal" one black value from Child and Sibling
1179 // each, and pass it to Parent. "Stealing" means that Sibling (black
1180 // value 1) becomes red, Child (black value 2) becomes singly-black,
1181 // and Parent will have to be examined if it can eat the
1184 // Sibling is allowed to become red because both of its children are
1185 // black (property #3).
1187 // grandparent Parent
1189 // Parent,x:B Child,x:B
1191 // Child,2b:A Sibling,b:D ---> b:A r:D
1193 // LeftNephew,b:C RightNephew,b:E b:C b:E
1195 Sibling
->Color
= RedBlackTreeRed
;
1197 Parent
= Parent
->Parent
;
1199 // Continue ascending.
1203 // At least one nephew is red.
1205 if (NodeIsNullOrBlack (RightNephew
)) {
1207 // Since the right nephew is black, the left nephew is red. Due to
1208 // property #3, LeftNephew has two black children, hence node E is
1211 // Together with the rotation, this enables us to color node F red
1212 // (because property #3 will be satisfied). We flip node D to black
1213 // to maintain property #4.
1215 // grandparent grandparent
1217 // Parent,x:B Parent,x:B
1219 // Child,2b:A Sibling,b:F ---> Child,2b:A Sibling,b:D
1221 // LeftNephew,r:D RightNephew,b:G b:C RightNephew,r:F
1225 LeftNephew
->Color
= RedBlackTreeBlack
;
1226 Sibling
->Color
= RedBlackTreeRed
;
1227 RedBlackTreeRotateRight (Sibling
, &NewRoot
);
1228 Sibling
= Parent
->Right
;
1229 RightNephew
= Sibling
->Right
;
1231 // These operations ensure that...
1235 // ... RightNephew is definitely red here, plus Sibling is (still)
1236 // black and non-NULL.
1238 ASSERT (RightNephew
!= NULL
);
1239 ASSERT (RightNephew
->Color
== RedBlackTreeRed
);
1240 ASSERT (Sibling
!= NULL
);
1241 ASSERT (Sibling
->Color
== RedBlackTreeBlack
);
1243 // In this case we can flush the extra black-increment immediately,
1244 // restoring property #1 for Child (node A): we color RightNephew
1245 // (node E) from red to black.
1247 // In order to maintain property #4, we exchange colors between
1248 // Parent and Sibling (nodes B and D), and rotate left around Parent
1249 // (node B). The transformation doesn't change the black count
1250 // increase incurred by each partial path, eg.
1251 // - ascending from node A: 2 + x == 1 + 1 + x
1252 // - ascending from node C: y + 1 + x == y + 1 + x
1253 // - ascending from node E: 0 + 1 + x == 1 + x
1255 // The color exchange is valid, because even if x stands for red,
1256 // both children of node D are black after the transformation
1257 // (preserving property #3).
1259 // grandparent grandparent
1263 // Child,2b:A Sibling,b:D ---> b:B b:E
1265 // y:C RightNephew,r:E b:A y:C
1268 Sibling
->Color
= Parent
->Color
;
1269 Parent
->Color
= RedBlackTreeBlack
;
1270 RightNephew
->Color
= RedBlackTreeBlack
;
1271 RedBlackTreeRotateLeft (Parent
, &NewRoot
);
1274 // This terminates the loop.
1279 // Mirrors the other branch.
1281 Sibling
= Parent
->Left
;
1282 ASSERT (Sibling
!= NULL
);
1283 if (Sibling
->Color
== RedBlackTreeRed
) {
1284 Sibling
->Color
= RedBlackTreeBlack
;
1285 Parent
->Color
= RedBlackTreeRed
;
1286 RedBlackTreeRotateRight (Parent
, &NewRoot
);
1287 Sibling
= Parent
->Left
;
1288 ASSERT (Sibling
!= NULL
);
1291 ASSERT (Sibling
->Color
== RedBlackTreeBlack
);
1292 RightNephew
= Sibling
->Right
;
1293 LeftNephew
= Sibling
->Left
;
1294 if (NodeIsNullOrBlack (RightNephew
) &&
1295 NodeIsNullOrBlack (LeftNephew
)) {
1296 Sibling
->Color
= RedBlackTreeRed
;
1298 Parent
= Parent
->Parent
;
1300 if (NodeIsNullOrBlack (LeftNephew
)) {
1301 RightNephew
->Color
= RedBlackTreeBlack
;
1302 Sibling
->Color
= RedBlackTreeRed
;
1303 RedBlackTreeRotateLeft (Sibling
, &NewRoot
);
1304 Sibling
= Parent
->Left
;
1305 LeftNephew
= Sibling
->Left
;
1307 ASSERT (LeftNephew
!= NULL
);
1308 ASSERT (LeftNephew
->Color
== RedBlackTreeRed
);
1309 ASSERT (Sibling
!= NULL
);
1310 ASSERT (Sibling
->Color
== RedBlackTreeBlack
);
1311 Sibling
->Color
= Parent
->Color
;
1312 Parent
->Color
= RedBlackTreeBlack
;
1313 LeftNephew
->Color
= RedBlackTreeBlack
;
1314 RedBlackTreeRotateRight (Parent
, &NewRoot
);
1320 if (Child
!= NULL
) {
1321 Child
->Color
= RedBlackTreeBlack
;
1325 Tree
->Root
= NewRoot
;
1327 if (FeaturePcdGet (PcdValidateOrderedCollection
)) {
1328 RedBlackTreeValidate (Tree
);
1334 Recursively check the red-black tree properties #1 to #4 on a node.
1336 @param[in] Node The root of the subtree to validate.
1338 @retval The black-height of Node's parent.
1342 RedBlackTreeRecursiveCheck (
1343 IN CONST RED_BLACK_TREE_NODE
*Node
1346 UINT32 LeftHeight
, RightHeight
;
1358 ASSERT (Node
->Color
== RedBlackTreeRed
|| Node
->Color
== RedBlackTreeBlack
);
1363 if (Node
->Color
== RedBlackTreeRed
) {
1364 ASSERT (NodeIsNullOrBlack (Node
->Left
));
1365 ASSERT (NodeIsNullOrBlack (Node
->Right
));
1371 LeftHeight
= RedBlackTreeRecursiveCheck (Node
->Left
);
1372 RightHeight
= RedBlackTreeRecursiveCheck (Node
->Right
);
1373 ASSERT (LeftHeight
== RightHeight
);
1375 return (Node
->Color
== RedBlackTreeBlack
) + LeftHeight
;
1380 A slow function that asserts that the tree is a valid red-black tree, and
1381 that it orders user structures correctly.
1383 Read-only operation.
1385 This function uses the stack for recursion and is not recommended for
1388 @param[in] Tree The tree to validate.
1392 RedBlackTreeValidate (
1393 IN CONST RED_BLACK_TREE
*Tree
1397 UINT32 ForwardCount
, BackwardCount
;
1398 CONST RED_BLACK_TREE_NODE
*Last
, *Node
;
1400 DEBUG ((DEBUG_VERBOSE
, "%a: Tree=%p\n", __FUNCTION__
, Tree
));
1405 ASSERT (NodeIsNullOrBlack (Tree
->Root
));
1408 // check the other properties
1410 BlackHeight
= RedBlackTreeRecursiveCheck (Tree
->Root
) - 1;
1415 Last
= OrderedCollectionMin (Tree
);
1416 ForwardCount
= (Last
!= NULL
);
1417 for (Node
= OrderedCollectionNext (Last
); Node
!= NULL
;
1418 Node
= OrderedCollectionNext (Last
)) {
1419 ASSERT (Tree
->UserStructCompare (Last
->UserStruct
, Node
->UserStruct
) < 0);
1425 // backward ordering
1427 Last
= OrderedCollectionMax (Tree
);
1428 BackwardCount
= (Last
!= NULL
);
1429 for (Node
= OrderedCollectionPrev (Last
); Node
!= NULL
;
1430 Node
= OrderedCollectionPrev (Last
)) {
1431 ASSERT (Tree
->UserStructCompare (Last
->UserStruct
, Node
->UserStruct
) > 0);
1436 ASSERT (ForwardCount
== BackwardCount
);
1438 DEBUG ((DEBUG_VERBOSE
, "%a: Tree=%p BlackHeight=%Ld Count=%Ld\n",
1439 __FUNCTION__
, Tree
, (INT64
)BlackHeight
, (INT64
)ForwardCount
));