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 This program and the accompanying materials are licensed and made available
17 under the terms and conditions of the BSD License that accompanies this
18 distribution. The full text of the license may be found at
19 http://opensource.org/licenses/bsd-license.php.
21 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, WITHOUT
22 WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
25 #include <Library/OrderedCollectionLib.h>
26 #include <Library/DebugLib.h>
27 #include <Library/MemoryAllocationLib.h>
32 } RED_BLACK_TREE_COLOR
;
35 // Incomplete types and convenience typedefs are present in the library class
36 // header. Beside completing the types, we introduce typedefs here that reflect
37 // the implementation closely.
39 typedef ORDERED_COLLECTION RED_BLACK_TREE
;
40 typedef ORDERED_COLLECTION_ENTRY RED_BLACK_TREE_NODE
;
41 typedef ORDERED_COLLECTION_USER_COMPARE RED_BLACK_TREE_USER_COMPARE
;
42 typedef ORDERED_COLLECTION_KEY_COMPARE RED_BLACK_TREE_KEY_COMPARE
;
44 struct ORDERED_COLLECTION
{
45 RED_BLACK_TREE_NODE
*Root
;
46 RED_BLACK_TREE_USER_COMPARE UserStructCompare
;
47 RED_BLACK_TREE_KEY_COMPARE KeyCompare
;
50 struct ORDERED_COLLECTION_ENTRY
{
52 RED_BLACK_TREE_NODE
*Parent
;
53 RED_BLACK_TREE_NODE
*Left
;
54 RED_BLACK_TREE_NODE
*Right
;
55 RED_BLACK_TREE_COLOR Color
;
60 Retrieve the user structure linked by the specified tree node.
64 @param[in] Node Pointer to the tree node whose associated user structure we
65 want to retrieve. The caller is responsible for passing a
68 @return Pointer to user structure linked by Node.
72 OrderedCollectionUserStruct (
73 IN CONST RED_BLACK_TREE_NODE
*Node
76 return Node
->UserStruct
;
80 A slow function that asserts that the tree is a valid red-black tree, and
81 that it orders user structures correctly.
85 This function uses the stack for recursion and is not recommended for
88 @param[in] Tree The tree to validate.
91 RedBlackTreeValidate (
92 IN CONST RED_BLACK_TREE
*Tree
97 Allocate and initialize the RED_BLACK_TREE structure.
99 Allocation occurs via MemoryAllocationLib's AllocatePool() function.
101 @param[in] UserStructCompare This caller-provided function will be used to
102 order two user structures linked into the
103 tree, during the insertion procedure.
105 @param[in] KeyCompare This caller-provided function will be used to
106 order the standalone search key against user
107 structures linked into the tree, during the
110 @retval NULL If allocation failed.
112 @return Pointer to the allocated, initialized RED_BLACK_TREE structure,
117 OrderedCollectionInit (
118 IN RED_BLACK_TREE_USER_COMPARE UserStructCompare
,
119 IN RED_BLACK_TREE_KEY_COMPARE KeyCompare
122 RED_BLACK_TREE
*Tree
;
124 Tree
= AllocatePool (sizeof *Tree
);
130 Tree
->UserStructCompare
= UserStructCompare
;
131 Tree
->KeyCompare
= KeyCompare
;
133 if (FeaturePcdGet (PcdValidateOrderedCollection
)) {
134 RedBlackTreeValidate (Tree
);
141 Check whether the tree is empty (has no nodes).
145 @param[in] Tree The tree to check for emptiness.
147 @retval TRUE The tree is empty.
149 @retval FALSE The tree is not empty.
153 OrderedCollectionIsEmpty (
154 IN CONST RED_BLACK_TREE
*Tree
157 return (BOOLEAN
)(Tree
->Root
== NULL
);
162 Uninitialize and release an empty RED_BLACK_TREE structure.
164 Read-write operation.
166 Release occurs via MemoryAllocationLib's FreePool() function.
168 It is the caller's responsibility to delete all nodes from the tree before
169 calling this function.
171 @param[in] Tree The empty tree to uninitialize and release.
175 OrderedCollectionUninit (
176 IN RED_BLACK_TREE
*Tree
179 ASSERT (OrderedCollectionIsEmpty (Tree
));
185 Look up the tree node that links the user structure that matches the
186 specified standalone key.
190 @param[in] Tree The tree to search for StandaloneKey.
192 @param[in] StandaloneKey The key to locate among the user structures linked
193 into Tree. StandaloneKey will be passed to
196 @retval NULL StandaloneKey could not be found.
198 @return The tree node that links to the user structure matching
199 StandaloneKey, otherwise.
201 RED_BLACK_TREE_NODE
*
203 OrderedCollectionFind (
204 IN CONST RED_BLACK_TREE
*Tree
,
205 IN CONST VOID
*StandaloneKey
208 RED_BLACK_TREE_NODE
*Node
;
211 while (Node
!= NULL
) {
214 Result
= Tree
->KeyCompare (StandaloneKey
, Node
->UserStruct
);
218 Node
= (Result
< 0) ? Node
->Left
: Node
->Right
;
225 Find the tree node of the minimum user structure stored in the tree.
229 @param[in] Tree The tree to return the minimum node of. The user structure
230 linked by the minimum node compares less than all other user
231 structures in the tree.
233 @retval NULL If Tree is empty.
235 @return The tree node that links the minimum user structure, otherwise.
237 RED_BLACK_TREE_NODE
*
239 OrderedCollectionMin (
240 IN CONST RED_BLACK_TREE
*Tree
243 RED_BLACK_TREE_NODE
*Node
;
249 while (Node
->Left
!= NULL
) {
257 Find the tree node of the maximum user structure stored in the tree.
261 @param[in] Tree The tree to return the maximum node of. The user structure
262 linked by the maximum node compares greater than all other
263 user structures in the tree.
265 @retval NULL If Tree is empty.
267 @return The tree node that links the maximum user structure, otherwise.
269 RED_BLACK_TREE_NODE
*
271 OrderedCollectionMax (
272 IN CONST RED_BLACK_TREE
*Tree
275 RED_BLACK_TREE_NODE
*Node
;
281 while (Node
->Right
!= NULL
) {
289 Get the tree node of the least user structure that is greater than the one
294 @param[in] Node The node to get the successor node of.
296 @retval NULL If Node is NULL, or Node is the maximum node of its containing
297 tree (ie. Node has no successor node).
299 @return The tree node linking the least user structure that is greater
300 than the one linked by Node, otherwise.
302 RED_BLACK_TREE_NODE
*
304 OrderedCollectionNext (
305 IN CONST RED_BLACK_TREE_NODE
*Node
308 RED_BLACK_TREE_NODE
*Walk
;
309 CONST RED_BLACK_TREE_NODE
*Child
;
316 // If Node has a right subtree, then the successor is the minimum node of
321 while (Walk
->Left
!= NULL
) {
328 // Otherwise we have to ascend as long as we're our parent's right child (ie.
329 // ascending to the left).
332 Walk
= Child
->Parent
;
333 while (Walk
!= NULL
&& Child
== Walk
->Right
) {
335 Walk
= Child
->Parent
;
342 Get the tree node of the greatest user structure that is less than the one
347 @param[in] Node The node to get the predecessor node of.
349 @retval NULL If Node is NULL, or Node is the minimum node of its containing
350 tree (ie. Node has no predecessor node).
352 @return The tree node linking the greatest user structure that is less
353 than the one linked by Node, otherwise.
355 RED_BLACK_TREE_NODE
*
357 OrderedCollectionPrev (
358 IN CONST RED_BLACK_TREE_NODE
*Node
361 RED_BLACK_TREE_NODE
*Walk
;
362 CONST RED_BLACK_TREE_NODE
*Child
;
369 // If Node has a left subtree, then the predecessor is the maximum node of
374 while (Walk
->Right
!= NULL
) {
381 // Otherwise we have to ascend as long as we're our parent's left child (ie.
382 // ascending to the right).
385 Walk
= Child
->Parent
;
386 while (Walk
!= NULL
&& Child
== Walk
->Left
) {
388 Walk
= Child
->Parent
;
395 Rotate tree nodes around Pivot to the right.
401 LeftChild Node1 ---> Node2 Pivot
403 Node2 LeftRightChild LeftRightChild Node1
405 The ordering Node2 < LeftChild < LeftRightChild < Pivot < Node1 is kept
406 intact. Parent (if any) is either at the left extreme or the right extreme of
407 this ordering, and that relation is also kept intact.
409 Edges marked with a dot (".") don't change during rotation.
411 Internal read-write operation.
413 @param[in,out] Pivot The tree node to rotate other nodes right around. It
414 is the caller's responsibility to ensure that
415 Pivot->Left is not NULL.
417 @param[out] NewRoot If Pivot has a parent node on input, then the
418 function updates Pivot's original parent on output
419 according to the rotation, and NewRoot is not
422 If Pivot has no parent node on input (ie. Pivot is
423 the root of the tree), then the function stores the
424 new root node of the tree in NewRoot.
427 RedBlackTreeRotateRight (
428 IN OUT RED_BLACK_TREE_NODE
*Pivot
,
429 OUT RED_BLACK_TREE_NODE
**NewRoot
432 RED_BLACK_TREE_NODE
*Parent
;
433 RED_BLACK_TREE_NODE
*LeftChild
;
434 RED_BLACK_TREE_NODE
*LeftRightChild
;
436 Parent
= Pivot
->Parent
;
437 LeftChild
= Pivot
->Left
;
438 LeftRightChild
= LeftChild
->Right
;
440 Pivot
->Left
= LeftRightChild
;
441 if (LeftRightChild
!= NULL
) {
442 LeftRightChild
->Parent
= Pivot
;
444 LeftChild
->Parent
= Parent
;
445 if (Parent
== NULL
) {
446 *NewRoot
= LeftChild
;
448 if (Pivot
== Parent
->Left
) {
449 Parent
->Left
= LeftChild
;
451 Parent
->Right
= LeftChild
;
454 LeftChild
->Right
= Pivot
;
455 Pivot
->Parent
= LeftChild
;
460 Rotate tree nodes around Pivot to the left.
466 Node1 RightChild ---> Pivot Node2
468 RightLeftChild Node2 Node1 RightLeftChild
470 The ordering Node1 < Pivot < RightLeftChild < RightChild < Node2 is kept
471 intact. Parent (if any) is either at the left extreme or the right extreme of
472 this ordering, and that relation is also kept intact.
474 Edges marked with a dot (".") don't change during rotation.
476 Internal read-write operation.
478 @param[in,out] Pivot The tree node to rotate other nodes left around. It
479 is the caller's responsibility to ensure that
480 Pivot->Right is not NULL.
482 @param[out] NewRoot If Pivot has a parent node on input, then the
483 function updates Pivot's original parent on output
484 according to the rotation, and NewRoot is not
487 If Pivot has no parent node on input (ie. Pivot is
488 the root of the tree), then the function stores the
489 new root node of the tree in NewRoot.
492 RedBlackTreeRotateLeft (
493 IN OUT RED_BLACK_TREE_NODE
*Pivot
,
494 OUT RED_BLACK_TREE_NODE
**NewRoot
497 RED_BLACK_TREE_NODE
*Parent
;
498 RED_BLACK_TREE_NODE
*RightChild
;
499 RED_BLACK_TREE_NODE
*RightLeftChild
;
501 Parent
= Pivot
->Parent
;
502 RightChild
= Pivot
->Right
;
503 RightLeftChild
= RightChild
->Left
;
505 Pivot
->Right
= RightLeftChild
;
506 if (RightLeftChild
!= NULL
) {
507 RightLeftChild
->Parent
= Pivot
;
509 RightChild
->Parent
= Parent
;
510 if (Parent
== NULL
) {
511 *NewRoot
= RightChild
;
513 if (Pivot
== Parent
->Left
) {
514 Parent
->Left
= RightChild
;
516 Parent
->Right
= RightChild
;
519 RightChild
->Left
= Pivot
;
520 Pivot
->Parent
= RightChild
;
525 Insert (link) a user structure into the tree.
527 Read-write operation.
529 This function allocates the new tree node with MemoryAllocationLib's
530 AllocatePool() function.
532 @param[in,out] Tree The tree to insert UserStruct into.
534 @param[out] Node The meaning of this optional, output-only
535 parameter depends on the return value of the
538 When insertion is successful (RETURN_SUCCESS),
539 Node is set on output to the new tree node that
540 now links UserStruct.
542 When insertion fails due to lack of memory
543 (RETURN_OUT_OF_RESOURCES), Node is not changed.
545 When insertion fails due to key collision (ie.
546 another user structure is already in the tree that
547 compares equal to UserStruct), with return value
548 RETURN_ALREADY_STARTED, then Node is set on output
549 to the node that links the colliding user
550 structure. This enables "find-or-insert" in one
551 function call, or helps with later removal of the
554 @param[in] UserStruct The user structure to link into the tree.
555 UserStruct is ordered against in-tree user
556 structures with the Tree->UserStructCompare()
559 @retval RETURN_SUCCESS Insertion successful. A new tree node has
560 been allocated, linking UserStruct. The new
561 tree node is reported back in Node (if the
562 caller requested it).
564 Existing RED_BLACK_TREE_NODE pointers into
565 Tree remain valid. For example, on-going
566 iterations in the caller can continue with
567 OrderedCollectionNext() /
568 OrderedCollectionPrev(), and they will
569 return the new node at some point if user
570 structure order dictates it.
572 @retval RETURN_OUT_OF_RESOURCES AllocatePool() failed to allocate memory for
573 the new tree node. The tree has not been
574 changed. Existing RED_BLACK_TREE_NODE
575 pointers into Tree remain valid.
577 @retval RETURN_ALREADY_STARTED A user structure has been found in the tree
578 that compares equal to UserStruct. The node
579 linking the colliding user structure is
580 reported back in Node (if the caller
581 requested it). The tree has not been
582 changed. Existing RED_BLACK_TREE_NODE
583 pointers into Tree remain valid.
587 OrderedCollectionInsert (
588 IN OUT RED_BLACK_TREE
*Tree
,
589 OUT RED_BLACK_TREE_NODE
**Node OPTIONAL
,
593 RED_BLACK_TREE_NODE
*Tmp
;
594 RED_BLACK_TREE_NODE
*Parent
;
596 RETURN_STATUS Status
;
597 RED_BLACK_TREE_NODE
*NewRoot
;
604 // First look for a collision, saving the last examined node for the case
605 // when there's no collision.
607 while (Tmp
!= NULL
) {
608 Result
= Tree
->UserStructCompare (UserStruct
, Tmp
->UserStruct
);
613 Tmp
= (Result
< 0) ? Tmp
->Left
: Tmp
->Right
;
620 Status
= RETURN_ALREADY_STARTED
;
625 // no collision, allocate a new node
627 Tmp
= AllocatePool (sizeof *Tmp
);
629 Status
= RETURN_OUT_OF_RESOURCES
;
637 // reference the user structure from the node
639 Tmp
->UserStruct
= UserStruct
;
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.
645 Tmp
->Parent
= Parent
;
648 if (Parent
== NULL
) {
650 Tmp
->Color
= RedBlackTreeBlack
;
651 Status
= RETURN_SUCCESS
;
659 Tmp
->Color
= RedBlackTreeRed
;
662 // Red-black tree properties:
664 // #1 Each node is either red or black (RED_BLACK_TREE_NODE.Color).
666 // #2 Each leaf (ie. a pseudo-node pointed-to by a NULL valued
667 // RED_BLACK_TREE_NODE.Left or RED_BLACK_TREE_NODE.Right field) is black.
669 // #3 Each red node has two black children.
671 // #4 For any node N, and for any leaves L1 and L2 reachable from N, the
672 // paths N..L1 and N..L2 contain the same number of black nodes.
674 // #5 The root node is black.
676 // By replacing a leaf with a red node above, only property #3 may have been
677 // broken. (Note that this is the only edge across which property #3 might
678 // not hold in the entire tree.) Restore property #3.
681 NewRoot
= Tree
->Root
;
682 while (Tmp
!= NewRoot
&& Parent
->Color
== RedBlackTreeRed
) {
683 RED_BLACK_TREE_NODE
*GrandParent
;
684 RED_BLACK_TREE_NODE
*Uncle
;
687 // Tmp is not the root node. Tmp is red. Tmp's parent is red. (Breaking
690 // Due to property #5, Tmp's parent cannot be the root node, hence Tmp's
691 // grandparent exists.
693 // Tmp's grandparent is black, because property #3 is only broken between
694 // Tmp and Tmp's parent.
696 GrandParent
= Parent
->Parent
;
698 if (Parent
== GrandParent
->Left
) {
699 Uncle
= GrandParent
->Right
;
700 if (Uncle
!= NULL
&& Uncle
->Color
== RedBlackTreeRed
) {
702 // GrandParent (black)
704 // Parent (red) Uncle (red)
709 Parent
->Color
= RedBlackTreeBlack
;
710 Uncle
->Color
= RedBlackTreeBlack
;
711 GrandParent
->Color
= RedBlackTreeRed
;
716 // Parent (black) Uncle (black)
720 // We restored property #3 between Tmp and Tmp's parent, without
721 // breaking property #4. However, we may have broken property #3
722 // between Tmp's grandparent and Tmp's great-grandparent (if any), so
723 // repeat the loop for Tmp's grandparent.
725 // If Tmp's grandparent has no parent, then the loop will terminate,
726 // and we will have broken property #5, by coloring the root red. We'll
727 // restore property #5 after the loop, without breaking any others.
730 Parent
= Tmp
->Parent
;
733 // Tmp's uncle is black (satisfied by the case too when Tmp's uncle is
734 // NULL, see property #2).
737 if (Tmp
== Parent
->Right
) {
739 // GrandParent (black): D
741 // Parent (red): A Uncle (black): E
747 // Rotate left, pivoting on node A. This keeps the breakage of
748 // property #3 in the same spot, and keeps other properties intact
749 // (because both Tmp and its parent are red).
752 RedBlackTreeRotateLeft (Tmp
, &NewRoot
);
753 Parent
= Tmp
->Parent
;
756 // With the rotation we reached the same configuration as if Tmp had
757 // been a left child to begin with.
759 // GrandParent (black): D
761 // Parent (red): B Uncle (black): E
763 // Tmp (red): A black: C
765 ASSERT (GrandParent
== Parent
->Parent
);
768 Parent
->Color
= RedBlackTreeBlack
;
769 GrandParent
->Color
= RedBlackTreeRed
;
772 // Property #3 is now restored, but we've broken property #4. Namely,
773 // paths going through node E now see a decrease in black count, while
774 // paths going through node B don't.
776 // GrandParent (red): D
778 // Parent (black): B Uncle (black): E
780 // Tmp (red): A black: C
783 RedBlackTreeRotateRight (GrandParent
, &NewRoot
);
786 // Property #4 has been restored for node E, and preserved for others.
790 // Tmp (red): A [GrandParent] (red): D
792 // black: C [Uncle] (black): E
794 // This configuration terminates the loop because Tmp's parent is now
800 // Symmetrical to the other branch.
802 Uncle
= GrandParent
->Left
;
803 if (Uncle
!= NULL
&& Uncle
->Color
== RedBlackTreeRed
) {
804 Parent
->Color
= RedBlackTreeBlack
;
805 Uncle
->Color
= RedBlackTreeBlack
;
806 GrandParent
->Color
= RedBlackTreeRed
;
808 Parent
= Tmp
->Parent
;
810 if (Tmp
== Parent
->Left
) {
812 RedBlackTreeRotateRight (Tmp
, &NewRoot
);
813 Parent
= Tmp
->Parent
;
814 ASSERT (GrandParent
== Parent
->Parent
);
816 Parent
->Color
= RedBlackTreeBlack
;
817 GrandParent
->Color
= RedBlackTreeRed
;
818 RedBlackTreeRotateLeft (GrandParent
, &NewRoot
);
823 NewRoot
->Color
= RedBlackTreeBlack
;
824 Tree
->Root
= NewRoot
;
825 Status
= RETURN_SUCCESS
;
828 if (FeaturePcdGet (PcdValidateOrderedCollection
)) {
829 RedBlackTreeValidate (Tree
);
836 Check if a node is black, allowing for leaf nodes (see property #2).
838 This is a convenience shorthand.
840 param[in] Node The node to check. Node may be NULL, corresponding to a leaf.
842 @return If Node is NULL or colored black.
846 IN CONST RED_BLACK_TREE_NODE
*Node
849 return (BOOLEAN
)(Node
== NULL
|| Node
->Color
== RedBlackTreeBlack
);
854 Delete a node from the tree, unlinking the associated user structure.
856 Read-write operation.
858 @param[in,out] Tree The tree to delete Node from.
860 @param[in] Node The tree node to delete from Tree. The caller is
861 responsible for ensuring that Node belongs to
862 Tree, and that Node is non-NULL and valid. Node is
863 typically an earlier return value, or output
866 - OrderedCollectionFind(), for deleting a node by
869 - OrderedCollectionMin() / OrderedCollectionMax(),
870 for deleting the minimum / maximum node,
872 - OrderedCollectionNext() /
873 OrderedCollectionPrev(), for deleting a node
874 found during an iteration,
876 - OrderedCollectionInsert() with return value
877 RETURN_ALREADY_STARTED, for deleting a node
878 whose linked user structure caused collision
881 Given a non-empty Tree, Tree->Root is also a valid
882 Node argument (typically used for simplicity in
883 loops that empty the tree completely).
885 Node is released with MemoryAllocationLib's
888 Existing RED_BLACK_TREE_NODE pointers (ie.
889 iterators) *different* from Node remain valid. For
892 - OrderedCollectionNext() /
893 OrderedCollectionPrev() iterations in the caller
894 can be continued from Node, if
895 OrderedCollectionNext() or
896 OrderedCollectionPrev() is called on Node
897 *before* OrderedCollectionDelete() is. That is,
898 fetch the successor / predecessor node first,
901 - On-going iterations in the caller that would
902 have otherwise returned Node at some point, as
903 dictated by user structure order, will correctly
904 reflect the absence of Node after
905 OrderedCollectionDelete() is called
908 @param[out] UserStruct If the caller provides this optional output-only
909 parameter, then on output it is set to the user
910 structure originally linked by Node (which is now
913 This is a convenience that may save the caller a
914 OrderedCollectionUserStruct() invocation before
915 calling OrderedCollectionDelete(), in order to
916 retrieve the user structure being unlinked.
920 OrderedCollectionDelete (
921 IN OUT RED_BLACK_TREE
*Tree
,
922 IN RED_BLACK_TREE_NODE
*Node
,
923 OUT VOID
**UserStruct OPTIONAL
926 RED_BLACK_TREE_NODE
*NewRoot
;
927 RED_BLACK_TREE_NODE
*OrigLeftChild
;
928 RED_BLACK_TREE_NODE
*OrigRightChild
;
929 RED_BLACK_TREE_NODE
*OrigParent
;
930 RED_BLACK_TREE_NODE
*Child
;
931 RED_BLACK_TREE_NODE
*Parent
;
932 RED_BLACK_TREE_COLOR ColorOfUnlinked
;
934 NewRoot
= Tree
->Root
;
935 OrigLeftChild
= Node
->Left
,
936 OrigRightChild
= Node
->Right
,
937 OrigParent
= Node
->Parent
;
939 if (UserStruct
!= NULL
) {
940 *UserStruct
= Node
->UserStruct
;
944 // After this block, no matter which branch we take:
945 // - Child will point to the unique (or NULL) original child of the node that
946 // we will have unlinked,
947 // - Parent will point to the *position* of the original parent of the node
948 // that we will have unlinked.
950 if (OrigLeftChild
== NULL
|| OrigRightChild
== NULL
) {
952 // Node has at most one child. We can connect that child (if any) with
953 // Node's parent (if any), unlinking Node. This will preserve ordering
954 // because the subtree rooted in Node's child (if any) remains on the same
955 // side of Node's parent (if any) that Node was before.
958 Child
= (OrigLeftChild
!= NULL
) ? OrigLeftChild
: OrigRightChild
;
959 ColorOfUnlinked
= Node
->Color
;
962 Child
->Parent
= Parent
;
964 if (OrigParent
== NULL
) {
967 if (Node
== OrigParent
->Left
) {
968 OrigParent
->Left
= Child
;
970 OrigParent
->Right
= Child
;
975 // Node has two children. We unlink Node's successor, and then link it into
976 // Node's place, keeping Node's original color. This preserves ordering
978 // - Node's left subtree is less than Node, hence less than Node's
980 // - Node's right subtree is greater than Node. Node's successor is the
981 // minimum of that subtree, hence Node's successor is less than Node's
982 // right subtree with its minimum removed.
983 // - Node's successor is in Node's subtree, hence it falls on the same side
984 // of Node's parent as Node itself. The relinking doesn't change this
987 RED_BLACK_TREE_NODE
*ToRelink
;
989 ToRelink
= OrigRightChild
;
990 if (ToRelink
->Left
== NULL
) {
992 // OrigRightChild itself is Node's successor, it has no left child:
998 // OrigLeftChild: A OrigRightChild: E <--- Parent, ToRelink
1002 Parent
= OrigRightChild
;
1003 Child
= OrigRightChild
->Right
;
1006 ToRelink
= ToRelink
->Left
;
1007 } while (ToRelink
->Left
!= NULL
);
1010 // Node's successor is the minimum of OrigRightChild's proper subtree:
1016 // OrigLeftChild: A OrigRightChild: E <--- Parent
1021 Parent
= ToRelink
->Parent
;
1022 Child
= ToRelink
->Right
;
1025 // Unlink Node's successor (ie. ToRelink):
1031 // OrigLeftChild: A OrigRightChild: E <--- Parent
1037 Parent
->Left
= Child
;
1038 if (Child
!= NULL
) {
1039 Child
->Parent
= Parent
;
1043 // We start to link Node's unlinked successor into Node's place:
1047 // Node: B C <--- ToRelink
1049 // OrigLeftChild: A OrigRightChild: E <--- Parent
1055 ToRelink
->Right
= OrigRightChild
;
1056 OrigRightChild
->Parent
= ToRelink
;
1060 // The rest handles both cases, attaching ToRelink (Node's original
1061 // successor) to OrigLeftChild and OrigParent.
1064 // OrigParent ToRelink OrigParent
1066 // Node: B | Node: B Parent
1068 // OrigRightChild: E C <--- ToRelink |
1070 // OrigLeftChild: A F OrigLeftChild: A OrigRightChild: E
1075 ToRelink
->Left
= OrigLeftChild
;
1076 OrigLeftChild
->Parent
= ToRelink
;
1079 // Node's color must be preserved in Node's original place.
1081 ColorOfUnlinked
= ToRelink
->Color
;
1082 ToRelink
->Color
= Node
->Color
;
1085 // Finish linking Node's unlinked successor into Node's place.
1088 // Node: B ToRelink Node: B
1090 // OrigParent | OrigParent Parent
1092 // OrigRightChild: E C <--- ToRelink |
1094 // OrigLeftChild: A F OrigLeftChild: A OrigRightChild: E
1099 ToRelink
->Parent
= OrigParent
;
1100 if (OrigParent
== NULL
) {
1103 if (Node
== OrigParent
->Left
) {
1104 OrigParent
->Left
= ToRelink
;
1106 OrigParent
->Right
= ToRelink
;
1114 // If the node that we unlinked from its original spot (ie. Node itself, or
1115 // Node's successor), was red, then we broke neither property #3 nor property
1116 // #4: we didn't create any red-red edge between Child and Parent, and we
1117 // didn't change the black count on any path.
1119 if (ColorOfUnlinked
== RedBlackTreeBlack
) {
1121 // However, if the unlinked node was black, then we have to transfer its
1122 // "black-increment" to its unique child (pointed-to by Child), lest we
1123 // break property #4 for its ancestors.
1125 // If Child is red, we can simply color it black. If Child is black
1126 // already, we can't technically transfer a black-increment to it, due to
1129 // In the following loop we ascend searching for a red node to color black,
1130 // or until we reach the root (in which case we can drop the
1131 // black-increment). Inside the loop body, Child has a black value of 2,
1132 // transitorily breaking property #1 locally, but maintaining property #4
1135 // Rotations in the loop preserve property #4.
1137 while (Child
!= NewRoot
&& NodeIsNullOrBlack (Child
)) {
1138 RED_BLACK_TREE_NODE
*Sibling
;
1139 RED_BLACK_TREE_NODE
*LeftNephew
;
1140 RED_BLACK_TREE_NODE
*RightNephew
;
1142 if (Child
== Parent
->Left
) {
1143 Sibling
= Parent
->Right
;
1145 // Sibling can never be NULL (ie. a leaf).
1147 // If Sibling was NULL, then the black count on the path from Parent to
1148 // Sibling would equal Parent's black value, plus 1 (due to property
1149 // #2). Whereas the black count on the path from Parent to any leaf via
1150 // Child would be at least Parent's black value, plus 2 (due to Child's
1151 // black value of 2). This would clash with property #4.
1153 // (Sibling can be black of course, but it has to be an internal node.
1154 // Internality allows Sibling to have children, bumping the black
1155 // counts of paths that go through it.)
1157 ASSERT (Sibling
!= NULL
);
1158 if (Sibling
->Color
== RedBlackTreeRed
) {
1160 // Sibling's red color implies its children (if any), node C and node
1161 // E, are black (property #3). It also implies that Parent is black.
1163 // grandparent grandparent
1167 // Child,2b:A Sibling,r:D ---> Parent,r:B b:E
1169 // b:C b:E Child,2b:A Sibling,b:C
1171 Sibling
->Color
= RedBlackTreeBlack
;
1172 Parent
->Color
= RedBlackTreeRed
;
1173 RedBlackTreeRotateLeft (Parent
, &NewRoot
);
1174 Sibling
= Parent
->Right
;
1176 // Same reasoning as above.
1178 ASSERT (Sibling
!= NULL
);
1182 // Sibling is black, and not NULL. (Ie. Sibling is a black internal
1185 ASSERT (Sibling
->Color
== RedBlackTreeBlack
);
1186 LeftNephew
= Sibling
->Left
;
1187 RightNephew
= Sibling
->Right
;
1188 if (NodeIsNullOrBlack (LeftNephew
) &&
1189 NodeIsNullOrBlack (RightNephew
)) {
1191 // In this case we can "steal" one black value from Child and Sibling
1192 // each, and pass it to Parent. "Stealing" means that Sibling (black
1193 // value 1) becomes red, Child (black value 2) becomes singly-black,
1194 // and Parent will have to be examined if it can eat the
1197 // Sibling is allowed to become red because both of its children are
1198 // black (property #3).
1200 // grandparent Parent
1202 // Parent,x:B Child,x:B
1204 // Child,2b:A Sibling,b:D ---> b:A r:D
1206 // LeftNephew,b:C RightNephew,b:E b:C b:E
1208 Sibling
->Color
= RedBlackTreeRed
;
1210 Parent
= Parent
->Parent
;
1212 // Continue ascending.
1216 // At least one nephew is red.
1218 if (NodeIsNullOrBlack (RightNephew
)) {
1220 // Since the right nephew is black, the left nephew is red. Due to
1221 // property #3, LeftNephew has two black children, hence node E is
1224 // Together with the rotation, this enables us to color node F red
1225 // (because property #3 will be satisfied). We flip node D to black
1226 // to maintain property #4.
1228 // grandparent grandparent
1230 // Parent,x:B Parent,x:B
1232 // Child,2b:A Sibling,b:F ---> Child,2b:A Sibling,b:D
1234 // LeftNephew,r:D RightNephew,b:G b:C RightNephew,r:F
1238 LeftNephew
->Color
= RedBlackTreeBlack
;
1239 Sibling
->Color
= RedBlackTreeRed
;
1240 RedBlackTreeRotateRight (Sibling
, &NewRoot
);
1241 Sibling
= Parent
->Right
;
1242 RightNephew
= Sibling
->Right
;
1244 // These operations ensure that...
1248 // ... RightNephew is definitely red here, plus Sibling is (still)
1249 // black and non-NULL.
1251 ASSERT (RightNephew
!= NULL
);
1252 ASSERT (RightNephew
->Color
== RedBlackTreeRed
);
1253 ASSERT (Sibling
!= NULL
);
1254 ASSERT (Sibling
->Color
== RedBlackTreeBlack
);
1256 // In this case we can flush the extra black-increment immediately,
1257 // restoring property #1 for Child (node A): we color RightNephew
1258 // (node E) from red to black.
1260 // In order to maintain property #4, we exchange colors between
1261 // Parent and Sibling (nodes B and D), and rotate left around Parent
1262 // (node B). The transformation doesn't change the black count
1263 // increase incurred by each partial path, eg.
1264 // - ascending from node A: 2 + x == 1 + 1 + x
1265 // - ascending from node C: y + 1 + x == y + 1 + x
1266 // - ascending from node E: 0 + 1 + x == 1 + x
1268 // The color exchange is valid, because even if x stands for red,
1269 // both children of node D are black after the transformation
1270 // (preserving property #3).
1272 // grandparent grandparent
1276 // Child,2b:A Sibling,b:D ---> b:B b:E
1278 // y:C RightNephew,r:E b:A y:C
1281 Sibling
->Color
= Parent
->Color
;
1282 Parent
->Color
= RedBlackTreeBlack
;
1283 RightNephew
->Color
= RedBlackTreeBlack
;
1284 RedBlackTreeRotateLeft (Parent
, &NewRoot
);
1287 // This terminates the loop.
1292 // Mirrors the other branch.
1294 Sibling
= Parent
->Left
;
1295 ASSERT (Sibling
!= NULL
);
1296 if (Sibling
->Color
== RedBlackTreeRed
) {
1297 Sibling
->Color
= RedBlackTreeBlack
;
1298 Parent
->Color
= RedBlackTreeRed
;
1299 RedBlackTreeRotateRight (Parent
, &NewRoot
);
1300 Sibling
= Parent
->Left
;
1301 ASSERT (Sibling
!= NULL
);
1304 ASSERT (Sibling
->Color
== RedBlackTreeBlack
);
1305 RightNephew
= Sibling
->Right
;
1306 LeftNephew
= Sibling
->Left
;
1307 if (NodeIsNullOrBlack (RightNephew
) &&
1308 NodeIsNullOrBlack (LeftNephew
)) {
1309 Sibling
->Color
= RedBlackTreeRed
;
1311 Parent
= Parent
->Parent
;
1313 if (NodeIsNullOrBlack (LeftNephew
)) {
1314 RightNephew
->Color
= RedBlackTreeBlack
;
1315 Sibling
->Color
= RedBlackTreeRed
;
1316 RedBlackTreeRotateLeft (Sibling
, &NewRoot
);
1317 Sibling
= Parent
->Left
;
1318 LeftNephew
= Sibling
->Left
;
1320 ASSERT (LeftNephew
!= NULL
);
1321 ASSERT (LeftNephew
->Color
== RedBlackTreeRed
);
1322 ASSERT (Sibling
!= NULL
);
1323 ASSERT (Sibling
->Color
== RedBlackTreeBlack
);
1324 Sibling
->Color
= Parent
->Color
;
1325 Parent
->Color
= RedBlackTreeBlack
;
1326 LeftNephew
->Color
= RedBlackTreeBlack
;
1327 RedBlackTreeRotateRight (Parent
, &NewRoot
);
1333 if (Child
!= NULL
) {
1334 Child
->Color
= RedBlackTreeBlack
;
1338 Tree
->Root
= NewRoot
;
1340 if (FeaturePcdGet (PcdValidateOrderedCollection
)) {
1341 RedBlackTreeValidate (Tree
);
1347 Recursively check the red-black tree properties #1 to #4 on a node.
1349 @param[in] Node The root of the subtree to validate.
1351 @retval The black-height of Node's parent.
1354 RedBlackTreeRecursiveCheck (
1355 IN CONST RED_BLACK_TREE_NODE
*Node
1371 ASSERT (Node
->Color
== RedBlackTreeRed
|| Node
->Color
== RedBlackTreeBlack
);
1376 if (Node
->Color
== RedBlackTreeRed
) {
1377 ASSERT (NodeIsNullOrBlack (Node
->Left
));
1378 ASSERT (NodeIsNullOrBlack (Node
->Right
));
1384 LeftHeight
= RedBlackTreeRecursiveCheck (Node
->Left
);
1385 RightHeight
= RedBlackTreeRecursiveCheck (Node
->Right
);
1386 ASSERT (LeftHeight
== RightHeight
);
1388 return (Node
->Color
== RedBlackTreeBlack
) + LeftHeight
;
1393 A slow function that asserts that the tree is a valid red-black tree, and
1394 that it orders user structures correctly.
1396 Read-only operation.
1398 This function uses the stack for recursion and is not recommended for
1401 @param[in] Tree The tree to validate.
1404 RedBlackTreeValidate (
1405 IN CONST RED_BLACK_TREE
*Tree
1409 UINT32 ForwardCount
;
1410 UINT32 BackwardCount
;
1411 CONST RED_BLACK_TREE_NODE
*Last
;
1412 CONST RED_BLACK_TREE_NODE
*Node
;
1414 DEBUG ((DEBUG_VERBOSE
, "%a: Tree=%p\n", __FUNCTION__
, Tree
));
1419 ASSERT (NodeIsNullOrBlack (Tree
->Root
));
1422 // check the other properties
1424 BlackHeight
= RedBlackTreeRecursiveCheck (Tree
->Root
) - 1;
1429 Last
= OrderedCollectionMin (Tree
);
1430 ForwardCount
= (Last
!= NULL
);
1431 for (Node
= OrderedCollectionNext (Last
); Node
!= NULL
;
1432 Node
= OrderedCollectionNext (Last
)) {
1433 ASSERT (Tree
->UserStructCompare (Last
->UserStruct
, Node
->UserStruct
) < 0);
1439 // backward ordering
1441 Last
= OrderedCollectionMax (Tree
);
1442 BackwardCount
= (Last
!= NULL
);
1443 for (Node
= OrderedCollectionPrev (Last
); Node
!= NULL
;
1444 Node
= OrderedCollectionPrev (Last
)) {
1445 ASSERT (Tree
->UserStructCompare (Last
->UserStruct
, Node
->UserStruct
) > 0);
1450 ASSERT (ForwardCount
== BackwardCount
);
1452 DEBUG ((DEBUG_VERBOSE
, "%a: Tree=%p BlackHeight=%Ld Count=%Ld\n",
1453 __FUNCTION__
, Tree
, (INT64
)BlackHeight
, (INT64
)ForwardCount
));