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.
14 Copyright (c) 2014, Intel Corporation. All rights reserved.<BR>
16 SPDX-License-Identifier: BSD-2-Clause-Patent
19 #include <Library/OrderedCollectionLib.h>
20 #include <Library/DebugLib.h>
21 #include <Library/MemoryAllocationLib.h>
26 } RED_BLACK_TREE_COLOR
;
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.
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
;
38 struct ORDERED_COLLECTION
{
39 RED_BLACK_TREE_NODE
*Root
;
40 RED_BLACK_TREE_USER_COMPARE UserStructCompare
;
41 RED_BLACK_TREE_KEY_COMPARE KeyCompare
;
44 struct ORDERED_COLLECTION_ENTRY
{
46 RED_BLACK_TREE_NODE
*Parent
;
47 RED_BLACK_TREE_NODE
*Left
;
48 RED_BLACK_TREE_NODE
*Right
;
49 RED_BLACK_TREE_COLOR Color
;
54 Retrieve the user structure linked by the specified tree node.
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
62 @return Pointer to user structure linked by Node.
66 OrderedCollectionUserStruct (
67 IN CONST RED_BLACK_TREE_NODE
*Node
70 return Node
->UserStruct
;
74 A slow function that asserts that the tree is a valid red-black tree, and
75 that it orders user structures correctly.
79 This function uses the stack for recursion and is not recommended for
82 @param[in] Tree The tree to validate.
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 (BOOLEAN
)(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.
421 RedBlackTreeRotateRight (
422 IN OUT RED_BLACK_TREE_NODE
*Pivot
,
423 OUT RED_BLACK_TREE_NODE
**NewRoot
426 RED_BLACK_TREE_NODE
*Parent
;
427 RED_BLACK_TREE_NODE
*LeftChild
;
428 RED_BLACK_TREE_NODE
*LeftRightChild
;
430 Parent
= Pivot
->Parent
;
431 LeftChild
= Pivot
->Left
;
432 LeftRightChild
= LeftChild
->Right
;
434 Pivot
->Left
= LeftRightChild
;
435 if (LeftRightChild
!= NULL
) {
436 LeftRightChild
->Parent
= Pivot
;
438 LeftChild
->Parent
= Parent
;
439 if (Parent
== NULL
) {
440 *NewRoot
= LeftChild
;
442 if (Pivot
== Parent
->Left
) {
443 Parent
->Left
= LeftChild
;
445 Parent
->Right
= LeftChild
;
448 LeftChild
->Right
= Pivot
;
449 Pivot
->Parent
= LeftChild
;
454 Rotate tree nodes around Pivot to the left.
460 Node1 RightChild ---> Pivot Node2
462 RightLeftChild Node2 Node1 RightLeftChild
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.
468 Edges marked with a dot (".") don't change during rotation.
470 Internal read-write operation.
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.
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
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.
486 RedBlackTreeRotateLeft (
487 IN OUT RED_BLACK_TREE_NODE
*Pivot
,
488 OUT RED_BLACK_TREE_NODE
**NewRoot
491 RED_BLACK_TREE_NODE
*Parent
;
492 RED_BLACK_TREE_NODE
*RightChild
;
493 RED_BLACK_TREE_NODE
*RightLeftChild
;
495 Parent
= Pivot
->Parent
;
496 RightChild
= Pivot
->Right
;
497 RightLeftChild
= RightChild
->Left
;
499 Pivot
->Right
= RightLeftChild
;
500 if (RightLeftChild
!= NULL
) {
501 RightLeftChild
->Parent
= Pivot
;
503 RightChild
->Parent
= Parent
;
504 if (Parent
== NULL
) {
505 *NewRoot
= RightChild
;
507 if (Pivot
== Parent
->Left
) {
508 Parent
->Left
= RightChild
;
510 Parent
->Right
= RightChild
;
513 RightChild
->Left
= Pivot
;
514 Pivot
->Parent
= RightChild
;
519 Insert (link) a user structure into the tree.
521 Read-write operation.
523 This function allocates the new tree node with MemoryAllocationLib's
524 AllocatePool() function.
526 @param[in,out] Tree The tree to insert UserStruct into.
528 @param[out] Node The meaning of this optional, output-only
529 parameter depends on the return value of the
532 When insertion is successful (RETURN_SUCCESS),
533 Node is set on output to the new tree node that
534 now links UserStruct.
536 When insertion fails due to lack of memory
537 (RETURN_OUT_OF_RESOURCES), Node is not changed.
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
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()
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).
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.
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.
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.
581 OrderedCollectionInsert (
582 IN OUT RED_BLACK_TREE
*Tree
,
583 OUT RED_BLACK_TREE_NODE
**Node OPTIONAL
,
587 RED_BLACK_TREE_NODE
*Tmp
;
588 RED_BLACK_TREE_NODE
*Parent
;
590 RETURN_STATUS Status
;
591 RED_BLACK_TREE_NODE
*NewRoot
;
598 // First look for a collision, saving the last examined node for the case
599 // when there's no collision.
601 while (Tmp
!= NULL
) {
602 Result
= Tree
->UserStructCompare (UserStruct
, Tmp
->UserStruct
);
607 Tmp
= (Result
< 0) ? Tmp
->Left
: Tmp
->Right
;
614 Status
= RETURN_ALREADY_STARTED
;
619 // no collision, allocate a new node
621 Tmp
= AllocatePool (sizeof *Tmp
);
623 Status
= RETURN_OUT_OF_RESOURCES
;
631 // reference the user structure from the node
633 Tmp
->UserStruct
= UserStruct
;
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.
639 Tmp
->Parent
= Parent
;
642 if (Parent
== NULL
) {
644 Tmp
->Color
= RedBlackTreeBlack
;
645 Status
= RETURN_SUCCESS
;
653 Tmp
->Color
= RedBlackTreeRed
;
656 // Red-black tree properties:
658 // #1 Each node is either red or black (RED_BLACK_TREE_NODE.Color).
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.
663 // #3 Each red node has two black children.
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.
668 // #5 The root node is black.
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.
675 NewRoot
= Tree
->Root
;
676 while (Tmp
!= NewRoot
&& Parent
->Color
== RedBlackTreeRed
) {
677 RED_BLACK_TREE_NODE
*GrandParent
;
678 RED_BLACK_TREE_NODE
*Uncle
;
681 // Tmp is not the root node. Tmp is red. Tmp's parent is red. (Breaking
684 // Due to property #5, Tmp's parent cannot be the root node, hence Tmp's
685 // grandparent exists.
687 // Tmp's grandparent is black, because property #3 is only broken between
688 // Tmp and Tmp's parent.
690 GrandParent
= Parent
->Parent
;
692 if (Parent
== GrandParent
->Left
) {
693 Uncle
= GrandParent
->Right
;
694 if (Uncle
!= NULL
&& Uncle
->Color
== RedBlackTreeRed
) {
696 // GrandParent (black)
698 // Parent (red) Uncle (red)
703 Parent
->Color
= RedBlackTreeBlack
;
704 Uncle
->Color
= RedBlackTreeBlack
;
705 GrandParent
->Color
= RedBlackTreeRed
;
710 // Parent (black) Uncle (black)
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.
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.
724 Parent
= Tmp
->Parent
;
727 // Tmp's uncle is black (satisfied by the case too when Tmp's uncle is
728 // NULL, see property #2).
731 if (Tmp
== Parent
->Right
) {
733 // GrandParent (black): D
735 // Parent (red): A Uncle (black): E
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).
746 RedBlackTreeRotateLeft (Tmp
, &NewRoot
);
747 Parent
= Tmp
->Parent
;
750 // With the rotation we reached the same configuration as if Tmp had
751 // been a left child to begin with.
753 // GrandParent (black): D
755 // Parent (red): B Uncle (black): E
757 // Tmp (red): A black: C
759 ASSERT (GrandParent
== Parent
->Parent
);
762 Parent
->Color
= RedBlackTreeBlack
;
763 GrandParent
->Color
= RedBlackTreeRed
;
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.
770 // GrandParent (red): D
772 // Parent (black): B Uncle (black): E
774 // Tmp (red): A black: C
777 RedBlackTreeRotateRight (GrandParent
, &NewRoot
);
780 // Property #4 has been restored for node E, and preserved for others.
784 // Tmp (red): A [GrandParent] (red): D
786 // black: C [Uncle] (black): E
788 // This configuration terminates the loop because Tmp's parent is now
794 // Symmetrical to the other branch.
796 Uncle
= GrandParent
->Left
;
797 if (Uncle
!= NULL
&& Uncle
->Color
== RedBlackTreeRed
) {
798 Parent
->Color
= RedBlackTreeBlack
;
799 Uncle
->Color
= RedBlackTreeBlack
;
800 GrandParent
->Color
= RedBlackTreeRed
;
802 Parent
= Tmp
->Parent
;
804 if (Tmp
== Parent
->Left
) {
806 RedBlackTreeRotateRight (Tmp
, &NewRoot
);
807 Parent
= Tmp
->Parent
;
808 ASSERT (GrandParent
== Parent
->Parent
);
810 Parent
->Color
= RedBlackTreeBlack
;
811 GrandParent
->Color
= RedBlackTreeRed
;
812 RedBlackTreeRotateLeft (GrandParent
, &NewRoot
);
817 NewRoot
->Color
= RedBlackTreeBlack
;
818 Tree
->Root
= NewRoot
;
819 Status
= RETURN_SUCCESS
;
822 if (FeaturePcdGet (PcdValidateOrderedCollection
)) {
823 RedBlackTreeValidate (Tree
);
830 Check if a node is black, allowing for leaf nodes (see property #2).
832 This is a convenience shorthand.
834 param[in] Node The node to check. Node may be NULL, corresponding to a leaf.
836 @return If Node is NULL or colored black.
840 IN CONST RED_BLACK_TREE_NODE
*Node
843 return (BOOLEAN
)(Node
== NULL
|| Node
->Color
== RedBlackTreeBlack
);
848 Delete a node from the tree, unlinking the associated user structure.
850 Read-write operation.
852 @param[in,out] Tree The tree to delete Node from.
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
860 - OrderedCollectionFind(), for deleting a node by
863 - OrderedCollectionMin() / OrderedCollectionMax(),
864 for deleting the minimum / maximum node,
866 - OrderedCollectionNext() /
867 OrderedCollectionPrev(), for deleting a node
868 found during an iteration,
870 - OrderedCollectionInsert() with return value
871 RETURN_ALREADY_STARTED, for deleting a node
872 whose linked user structure caused collision
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).
879 Node is released with MemoryAllocationLib's
882 Existing RED_BLACK_TREE_NODE pointers (ie.
883 iterators) *different* from Node remain valid. For
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,
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
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
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.
914 OrderedCollectionDelete (
915 IN OUT RED_BLACK_TREE
*Tree
,
916 IN RED_BLACK_TREE_NODE
*Node
,
917 OUT VOID
**UserStruct OPTIONAL
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
;
928 NewRoot
= Tree
->Root
;
929 OrigLeftChild
= Node
->Left
,
930 OrigRightChild
= Node
->Right
,
931 OrigParent
= Node
->Parent
;
933 if (UserStruct
!= NULL
) {
934 *UserStruct
= Node
->UserStruct
;
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.
944 if (OrigLeftChild
== NULL
|| OrigRightChild
== NULL
) {
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.
952 Child
= (OrigLeftChild
!= NULL
) ? OrigLeftChild
: OrigRightChild
;
953 ColorOfUnlinked
= Node
->Color
;
956 Child
->Parent
= Parent
;
958 if (OrigParent
== NULL
) {
961 if (Node
== OrigParent
->Left
) {
962 OrigParent
->Left
= Child
;
964 OrigParent
->Right
= Child
;
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
972 // - Node's left subtree is less than Node, hence less than Node's
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
981 RED_BLACK_TREE_NODE
*ToRelink
;
983 ToRelink
= OrigRightChild
;
984 if (ToRelink
->Left
== NULL
) {
986 // OrigRightChild itself is Node's successor, it has no left child:
992 // OrigLeftChild: A OrigRightChild: E <--- Parent, ToRelink
996 Parent
= OrigRightChild
;
997 Child
= OrigRightChild
->Right
;
1000 ToRelink
= ToRelink
->Left
;
1001 } while (ToRelink
->Left
!= NULL
);
1004 // Node's successor is the minimum of OrigRightChild's proper subtree:
1010 // OrigLeftChild: A OrigRightChild: E <--- Parent
1015 Parent
= ToRelink
->Parent
;
1016 Child
= ToRelink
->Right
;
1019 // Unlink Node's successor (ie. ToRelink):
1025 // OrigLeftChild: A OrigRightChild: E <--- Parent
1031 Parent
->Left
= Child
;
1032 if (Child
!= NULL
) {
1033 Child
->Parent
= Parent
;
1037 // We start to link Node's unlinked successor into Node's place:
1041 // Node: B C <--- ToRelink
1043 // OrigLeftChild: A OrigRightChild: E <--- Parent
1049 ToRelink
->Right
= OrigRightChild
;
1050 OrigRightChild
->Parent
= ToRelink
;
1054 // The rest handles both cases, attaching ToRelink (Node's original
1055 // successor) to OrigLeftChild and OrigParent.
1058 // OrigParent ToRelink OrigParent
1060 // Node: B | Node: B Parent
1062 // OrigRightChild: E C <--- ToRelink |
1064 // OrigLeftChild: A F OrigLeftChild: A OrigRightChild: E
1069 ToRelink
->Left
= OrigLeftChild
;
1070 OrigLeftChild
->Parent
= ToRelink
;
1073 // Node's color must be preserved in Node's original place.
1075 ColorOfUnlinked
= ToRelink
->Color
;
1076 ToRelink
->Color
= Node
->Color
;
1079 // Finish linking Node's unlinked successor into Node's place.
1082 // Node: B ToRelink Node: B
1084 // OrigParent | OrigParent Parent
1086 // OrigRightChild: E C <--- ToRelink |
1088 // OrigLeftChild: A F OrigLeftChild: A OrigRightChild: E
1093 ToRelink
->Parent
= OrigParent
;
1094 if (OrigParent
== NULL
) {
1097 if (Node
== OrigParent
->Left
) {
1098 OrigParent
->Left
= ToRelink
;
1100 OrigParent
->Right
= ToRelink
;
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.
1113 if (ColorOfUnlinked
== RedBlackTreeBlack
) {
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.
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
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
1129 // Rotations in the loop preserve property #4.
1131 while (Child
!= NewRoot
&& NodeIsNullOrBlack (Child
)) {
1132 RED_BLACK_TREE_NODE
*Sibling
;
1133 RED_BLACK_TREE_NODE
*LeftNephew
;
1134 RED_BLACK_TREE_NODE
*RightNephew
;
1136 if (Child
== Parent
->Left
) {
1137 Sibling
= Parent
->Right
;
1139 // Sibling can never be NULL (ie. a leaf).
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.
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.)
1151 ASSERT (Sibling
!= NULL
);
1152 if (Sibling
->Color
== RedBlackTreeRed
) {
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.
1157 // grandparent grandparent
1161 // Child,2b:A Sibling,r:D ---> Parent,r:B b:E
1163 // b:C b:E Child,2b:A Sibling,b:C
1165 Sibling
->Color
= RedBlackTreeBlack
;
1166 Parent
->Color
= RedBlackTreeRed
;
1167 RedBlackTreeRotateLeft (Parent
, &NewRoot
);
1168 Sibling
= Parent
->Right
;
1170 // Same reasoning as above.
1172 ASSERT (Sibling
!= NULL
);
1176 // Sibling is black, and not NULL. (Ie. Sibling is a black internal
1179 ASSERT (Sibling
->Color
== RedBlackTreeBlack
);
1180 LeftNephew
= Sibling
->Left
;
1181 RightNephew
= Sibling
->Right
;
1182 if (NodeIsNullOrBlack (LeftNephew
) &&
1183 NodeIsNullOrBlack (RightNephew
)) {
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
1191 // Sibling is allowed to become red because both of its children are
1192 // black (property #3).
1194 // grandparent Parent
1196 // Parent,x:B Child,x:B
1198 // Child,2b:A Sibling,b:D ---> b:A r:D
1200 // LeftNephew,b:C RightNephew,b:E b:C b:E
1202 Sibling
->Color
= RedBlackTreeRed
;
1204 Parent
= Parent
->Parent
;
1206 // Continue ascending.
1210 // At least one nephew is red.
1212 if (NodeIsNullOrBlack (RightNephew
)) {
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
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.
1222 // grandparent grandparent
1224 // Parent,x:B Parent,x:B
1226 // Child,2b:A Sibling,b:F ---> Child,2b:A Sibling,b:D
1228 // LeftNephew,r:D RightNephew,b:G b:C RightNephew,r:F
1232 LeftNephew
->Color
= RedBlackTreeBlack
;
1233 Sibling
->Color
= RedBlackTreeRed
;
1234 RedBlackTreeRotateRight (Sibling
, &NewRoot
);
1235 Sibling
= Parent
->Right
;
1236 RightNephew
= Sibling
->Right
;
1238 // These operations ensure that...
1242 // ... RightNephew is definitely red here, plus Sibling is (still)
1243 // black and non-NULL.
1245 ASSERT (RightNephew
!= NULL
);
1246 ASSERT (RightNephew
->Color
== RedBlackTreeRed
);
1247 ASSERT (Sibling
!= NULL
);
1248 ASSERT (Sibling
->Color
== RedBlackTreeBlack
);
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.
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
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).
1266 // grandparent grandparent
1270 // Child,2b:A Sibling,b:D ---> b:B b:E
1272 // y:C RightNephew,r:E b:A y:C
1275 Sibling
->Color
= Parent
->Color
;
1276 Parent
->Color
= RedBlackTreeBlack
;
1277 RightNephew
->Color
= RedBlackTreeBlack
;
1278 RedBlackTreeRotateLeft (Parent
, &NewRoot
);
1281 // This terminates the loop.
1286 // Mirrors the other branch.
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
);
1298 ASSERT (Sibling
->Color
== RedBlackTreeBlack
);
1299 RightNephew
= Sibling
->Right
;
1300 LeftNephew
= Sibling
->Left
;
1301 if (NodeIsNullOrBlack (RightNephew
) &&
1302 NodeIsNullOrBlack (LeftNephew
)) {
1303 Sibling
->Color
= RedBlackTreeRed
;
1305 Parent
= Parent
->Parent
;
1307 if (NodeIsNullOrBlack (LeftNephew
)) {
1308 RightNephew
->Color
= RedBlackTreeBlack
;
1309 Sibling
->Color
= RedBlackTreeRed
;
1310 RedBlackTreeRotateLeft (Sibling
, &NewRoot
);
1311 Sibling
= Parent
->Left
;
1312 LeftNephew
= Sibling
->Left
;
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
);
1327 if (Child
!= NULL
) {
1328 Child
->Color
= RedBlackTreeBlack
;
1332 Tree
->Root
= NewRoot
;
1334 if (FeaturePcdGet (PcdValidateOrderedCollection
)) {
1335 RedBlackTreeValidate (Tree
);
1341 Recursively check the red-black tree properties #1 to #4 on a node.
1343 @param[in] Node The root of the subtree to validate.
1345 @retval The black-height of Node's parent.
1348 RedBlackTreeRecursiveCheck (
1349 IN CONST RED_BLACK_TREE_NODE
*Node
1365 ASSERT (Node
->Color
== RedBlackTreeRed
|| Node
->Color
== RedBlackTreeBlack
);
1370 if (Node
->Color
== RedBlackTreeRed
) {
1371 ASSERT (NodeIsNullOrBlack (Node
->Left
));
1372 ASSERT (NodeIsNullOrBlack (Node
->Right
));
1378 LeftHeight
= RedBlackTreeRecursiveCheck (Node
->Left
);
1379 RightHeight
= RedBlackTreeRecursiveCheck (Node
->Right
);
1380 ASSERT (LeftHeight
== RightHeight
);
1382 return (Node
->Color
== RedBlackTreeBlack
) + LeftHeight
;
1387 A slow function that asserts that the tree is a valid red-black tree, and
1388 that it orders user structures correctly.
1390 Read-only operation.
1392 This function uses the stack for recursion and is not recommended for
1395 @param[in] Tree The tree to validate.
1398 RedBlackTreeValidate (
1399 IN CONST RED_BLACK_TREE
*Tree
1403 UINT32 ForwardCount
;
1404 UINT32 BackwardCount
;
1405 CONST RED_BLACK_TREE_NODE
*Last
;
1406 CONST RED_BLACK_TREE_NODE
*Node
;
1408 DEBUG ((DEBUG_VERBOSE
, "%a: Tree=%p\n", __FUNCTION__
, Tree
));
1413 ASSERT (NodeIsNullOrBlack (Tree
->Root
));
1416 // check the other properties
1418 BlackHeight
= RedBlackTreeRecursiveCheck (Tree
->Root
) - 1;
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);
1433 // backward ordering
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);
1444 ASSERT (ForwardCount
== BackwardCount
);
1446 DEBUG ((DEBUG_VERBOSE
, "%a: Tree=%p BlackHeight=%Ld Count=%Ld\n",
1447 __FUNCTION__
, Tree
, (INT64
)BlackHeight
, (INT64
)ForwardCount
));