| /** @file | |
| An OrderedCollectionLib instance that provides a red-black tree | |
| implementation, and allocates and releases tree nodes with | |
| MemoryAllocationLib. | |
| This library instance is useful when a fast associative container is needed. | |
| Worst case time complexity is O(log n) for Find(), Next(), Prev(), Min(), | |
| Max(), Insert(), and Delete(), where "n" is the number of elements in the | |
| tree. Complete ordered traversal takes O(n) time. | |
| The implementation is also useful as a fast priority queue. | |
| Copyright (C) 2014, Red Hat, Inc. | |
| Copyright (c) 2014, Intel Corporation. All rights reserved.<BR> | |
| This program and the accompanying materials are licensed and made available | |
| under the terms and conditions of the BSD License that accompanies this | |
| distribution. The full text of the license may be found at | |
| http://opensource.org/licenses/bsd-license.php. | |
| THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, WITHOUT | |
| WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED. | |
| **/ | |
| #include <Library/OrderedCollectionLib.h> | |
| #include <Library/DebugLib.h> | |
| #include <Library/MemoryAllocationLib.h> | |
| typedef enum { | |
| RedBlackTreeRed, | |
| RedBlackTreeBlack | |
| } RED_BLACK_TREE_COLOR; | |
| // | |
| // Incomplete types and convenience typedefs are present in the library class | |
| // header. Beside completing the types, we introduce typedefs here that reflect | |
| // the implementation closely. | |
| // | |
| typedef ORDERED_COLLECTION RED_BLACK_TREE; | |
| typedef ORDERED_COLLECTION_ENTRY RED_BLACK_TREE_NODE; | |
| typedef ORDERED_COLLECTION_USER_COMPARE RED_BLACK_TREE_USER_COMPARE; | |
| typedef ORDERED_COLLECTION_KEY_COMPARE RED_BLACK_TREE_KEY_COMPARE; | |
| struct ORDERED_COLLECTION { | |
| RED_BLACK_TREE_NODE *Root; | |
| RED_BLACK_TREE_USER_COMPARE UserStructCompare; | |
| RED_BLACK_TREE_KEY_COMPARE KeyCompare; | |
| }; | |
| struct ORDERED_COLLECTION_ENTRY { | |
| VOID *UserStruct; | |
| RED_BLACK_TREE_NODE *Parent; | |
| RED_BLACK_TREE_NODE *Left; | |
| RED_BLACK_TREE_NODE *Right; | |
| RED_BLACK_TREE_COLOR Color; | |
| }; | |
| /** | |
| Retrieve the user structure linked by the specified tree node. | |
| Read-only operation. | |
| @param[in] Node Pointer to the tree node whose associated user structure we | |
| want to retrieve. The caller is responsible for passing a | |
| non-NULL argument. | |
| @return Pointer to user structure linked by Node. | |
| **/ | |
| VOID * | |
| EFIAPI | |
| OrderedCollectionUserStruct ( | |
| IN CONST RED_BLACK_TREE_NODE *Node | |
| ) | |
| { | |
| return Node->UserStruct; | |
| } | |
| /** | |
| A slow function that asserts that the tree is a valid red-black tree, and | |
| that it orders user structures correctly. | |
| Read-only operation. | |
| This function uses the stack for recursion and is not recommended for | |
| "production use". | |
| @param[in] Tree The tree to validate. | |
| **/ | |
| VOID | |
| RedBlackTreeValidate ( | |
| IN CONST RED_BLACK_TREE *Tree | |
| ); | |
| /** | |
| Allocate and initialize the RED_BLACK_TREE structure. | |
| Allocation occurs via MemoryAllocationLib's AllocatePool() function. | |
| @param[in] UserStructCompare This caller-provided function will be used to | |
| order two user structures linked into the | |
| tree, during the insertion procedure. | |
| @param[in] KeyCompare This caller-provided function will be used to | |
| order the standalone search key against user | |
| structures linked into the tree, during the | |
| lookup procedure. | |
| @retval NULL If allocation failed. | |
| @return Pointer to the allocated, initialized RED_BLACK_TREE structure, | |
| otherwise. | |
| **/ | |
| RED_BLACK_TREE * | |
| EFIAPI | |
| OrderedCollectionInit ( | |
| IN RED_BLACK_TREE_USER_COMPARE UserStructCompare, | |
| IN RED_BLACK_TREE_KEY_COMPARE KeyCompare | |
| ) | |
| { | |
| RED_BLACK_TREE *Tree; | |
| Tree = AllocatePool (sizeof *Tree); | |
| if (Tree == NULL) { | |
| return NULL; | |
| } | |
| Tree->Root = NULL; | |
| Tree->UserStructCompare = UserStructCompare; | |
| Tree->KeyCompare = KeyCompare; | |
| if (FeaturePcdGet (PcdValidateOrderedCollection)) { | |
| RedBlackTreeValidate (Tree); | |
| } | |
| return Tree; | |
| } | |
| /** | |
| Check whether the tree is empty (has no nodes). | |
| Read-only operation. | |
| @param[in] Tree The tree to check for emptiness. | |
| @retval TRUE The tree is empty. | |
| @retval FALSE The tree is not empty. | |
| **/ | |
| BOOLEAN | |
| EFIAPI | |
| OrderedCollectionIsEmpty ( | |
| IN CONST RED_BLACK_TREE *Tree | |
| ) | |
| { | |
| return (BOOLEAN)(Tree->Root == NULL); | |
| } | |
| /** | |
| Uninitialize and release an empty RED_BLACK_TREE structure. | |
| Read-write operation. | |
| Release occurs via MemoryAllocationLib's FreePool() function. | |
| It is the caller's responsibility to delete all nodes from the tree before | |
| calling this function. | |
| @param[in] Tree The empty tree to uninitialize and release. | |
| **/ | |
| VOID | |
| EFIAPI | |
| OrderedCollectionUninit ( | |
| IN RED_BLACK_TREE *Tree | |
| ) | |
| { | |
| ASSERT (OrderedCollectionIsEmpty (Tree)); | |
| FreePool (Tree); | |
| } | |
| /** | |
| Look up the tree node that links the user structure that matches the | |
| specified standalone key. | |
| Read-only operation. | |
| @param[in] Tree The tree to search for StandaloneKey. | |
| @param[in] StandaloneKey The key to locate among the user structures linked | |
| into Tree. StandaloneKey will be passed to | |
| Tree->KeyCompare(). | |
| @retval NULL StandaloneKey could not be found. | |
| @return The tree node that links to the user structure matching | |
| StandaloneKey, otherwise. | |
| **/ | |
| RED_BLACK_TREE_NODE * | |
| EFIAPI | |
| OrderedCollectionFind ( | |
| IN CONST RED_BLACK_TREE *Tree, | |
| IN CONST VOID *StandaloneKey | |
| ) | |
| { | |
| RED_BLACK_TREE_NODE *Node; | |
| Node = Tree->Root; | |
| while (Node != NULL) { | |
| INTN Result; | |
| Result = Tree->KeyCompare (StandaloneKey, Node->UserStruct); | |
| if (Result == 0) { | |
| break; | |
| } | |
| Node = (Result < 0) ? Node->Left : Node->Right; | |
| } | |
| return Node; | |
| } | |
| /** | |
| Find the tree node of the minimum user structure stored in the tree. | |
| Read-only operation. | |
| @param[in] Tree The tree to return the minimum node of. The user structure | |
| linked by the minimum node compares less than all other user | |
| structures in the tree. | |
| @retval NULL If Tree is empty. | |
| @return The tree node that links the minimum user structure, otherwise. | |
| **/ | |
| RED_BLACK_TREE_NODE * | |
| EFIAPI | |
| OrderedCollectionMin ( | |
| IN CONST RED_BLACK_TREE *Tree | |
| ) | |
| { | |
| RED_BLACK_TREE_NODE *Node; | |
| Node = Tree->Root; | |
| if (Node == NULL) { | |
| return NULL; | |
| } | |
| while (Node->Left != NULL) { | |
| Node = Node->Left; | |
| } | |
| return Node; | |
| } | |
| /** | |
| Find the tree node of the maximum user structure stored in the tree. | |
| Read-only operation. | |
| @param[in] Tree The tree to return the maximum node of. The user structure | |
| linked by the maximum node compares greater than all other | |
| user structures in the tree. | |
| @retval NULL If Tree is empty. | |
| @return The tree node that links the maximum user structure, otherwise. | |
| **/ | |
| RED_BLACK_TREE_NODE * | |
| EFIAPI | |
| OrderedCollectionMax ( | |
| IN CONST RED_BLACK_TREE *Tree | |
| ) | |
| { | |
| RED_BLACK_TREE_NODE *Node; | |
| Node = Tree->Root; | |
| if (Node == NULL) { | |
| return NULL; | |
| } | |
| while (Node->Right != NULL) { | |
| Node = Node->Right; | |
| } | |
| return Node; | |
| } | |
| /** | |
| Get the tree node of the least user structure that is greater than the one | |
| linked by Node. | |
| Read-only operation. | |
| @param[in] Node The node to get the successor node of. | |
| @retval NULL If Node is NULL, or Node is the maximum node of its containing | |
| tree (ie. Node has no successor node). | |
| @return The tree node linking the least user structure that is greater | |
| than the one linked by Node, otherwise. | |
| **/ | |
| RED_BLACK_TREE_NODE * | |
| EFIAPI | |
| OrderedCollectionNext ( | |
| IN CONST RED_BLACK_TREE_NODE *Node | |
| ) | |
| { | |
| RED_BLACK_TREE_NODE *Walk; | |
| CONST RED_BLACK_TREE_NODE *Child; | |
| if (Node == NULL) { | |
| return NULL; | |
| } | |
| // | |
| // If Node has a right subtree, then the successor is the minimum node of | |
| // that subtree. | |
| // | |
| Walk = Node->Right; | |
| if (Walk != NULL) { | |
| while (Walk->Left != NULL) { | |
| Walk = Walk->Left; | |
| } | |
| return Walk; | |
| } | |
| // | |
| // Otherwise we have to ascend as long as we're our parent's right child (ie. | |
| // ascending to the left). | |
| // | |
| Child = Node; | |
| Walk = Child->Parent; | |
| while (Walk != NULL && Child == Walk->Right) { | |
| Child = Walk; | |
| Walk = Child->Parent; | |
| } | |
| return Walk; | |
| } | |
| /** | |
| Get the tree node of the greatest user structure that is less than the one | |
| linked by Node. | |
| Read-only operation. | |
| @param[in] Node The node to get the predecessor node of. | |
| @retval NULL If Node is NULL, or Node is the minimum node of its containing | |
| tree (ie. Node has no predecessor node). | |
| @return The tree node linking the greatest user structure that is less | |
| than the one linked by Node, otherwise. | |
| **/ | |
| RED_BLACK_TREE_NODE * | |
| EFIAPI | |
| OrderedCollectionPrev ( | |
| IN CONST RED_BLACK_TREE_NODE *Node | |
| ) | |
| { | |
| RED_BLACK_TREE_NODE *Walk; | |
| CONST RED_BLACK_TREE_NODE *Child; | |
| if (Node == NULL) { | |
| return NULL; | |
| } | |
| // | |
| // If Node has a left subtree, then the predecessor is the maximum node of | |
| // that subtree. | |
| // | |
| Walk = Node->Left; | |
| if (Walk != NULL) { | |
| while (Walk->Right != NULL) { | |
| Walk = Walk->Right; | |
| } | |
| return Walk; | |
| } | |
| // | |
| // Otherwise we have to ascend as long as we're our parent's left child (ie. | |
| // ascending to the right). | |
| // | |
| Child = Node; | |
| Walk = Child->Parent; | |
| while (Walk != NULL && Child == Walk->Left) { | |
| Child = Walk; | |
| Walk = Child->Parent; | |
| } | |
| return Walk; | |
| } | |
| /** | |
| Rotate tree nodes around Pivot to the right. | |
| Parent Parent | |
| | | | |
| Pivot LeftChild | |
| / . . \_ | |
| LeftChild Node1 ---> Node2 Pivot | |
| . \ / . | |
| Node2 LeftRightChild LeftRightChild Node1 | |
| The ordering Node2 < LeftChild < LeftRightChild < Pivot < Node1 is kept | |
| intact. Parent (if any) is either at the left extreme or the right extreme of | |
| this ordering, and that relation is also kept intact. | |
| Edges marked with a dot (".") don't change during rotation. | |
| Internal read-write operation. | |
| @param[in,out] Pivot The tree node to rotate other nodes right around. It | |
| is the caller's responsibility to ensure that | |
| Pivot->Left is not NULL. | |
| @param[out] NewRoot If Pivot has a parent node on input, then the | |
| function updates Pivot's original parent on output | |
| according to the rotation, and NewRoot is not | |
| accessed. | |
| If Pivot has no parent node on input (ie. Pivot is | |
| the root of the tree), then the function stores the | |
| new root node of the tree in NewRoot. | |
| **/ | |
| VOID | |
| RedBlackTreeRotateRight ( | |
| IN OUT RED_BLACK_TREE_NODE *Pivot, | |
| OUT RED_BLACK_TREE_NODE **NewRoot | |
| ) | |
| { | |
| RED_BLACK_TREE_NODE *Parent; | |
| RED_BLACK_TREE_NODE *LeftChild; | |
| RED_BLACK_TREE_NODE *LeftRightChild; | |
| Parent = Pivot->Parent; | |
| LeftChild = Pivot->Left; | |
| LeftRightChild = LeftChild->Right; | |
| Pivot->Left = LeftRightChild; | |
| if (LeftRightChild != NULL) { | |
| LeftRightChild->Parent = Pivot; | |
| } | |
| LeftChild->Parent = Parent; | |
| if (Parent == NULL) { | |
| *NewRoot = LeftChild; | |
| } else { | |
| if (Pivot == Parent->Left) { | |
| Parent->Left = LeftChild; | |
| } else { | |
| Parent->Right = LeftChild; | |
| } | |
| } | |
| LeftChild->Right = Pivot; | |
| Pivot->Parent = LeftChild; | |
| } | |
| /** | |
| Rotate tree nodes around Pivot to the left. | |
| Parent Parent | |
| | | | |
| Pivot RightChild | |
| . \ / . | |
| Node1 RightChild ---> Pivot Node2 | |
| /. . \_ | |
| RightLeftChild Node2 Node1 RightLeftChild | |
| The ordering Node1 < Pivot < RightLeftChild < RightChild < Node2 is kept | |
| intact. Parent (if any) is either at the left extreme or the right extreme of | |
| this ordering, and that relation is also kept intact. | |
| Edges marked with a dot (".") don't change during rotation. | |
| Internal read-write operation. | |
| @param[in,out] Pivot The tree node to rotate other nodes left around. It | |
| is the caller's responsibility to ensure that | |
| Pivot->Right is not NULL. | |
| @param[out] NewRoot If Pivot has a parent node on input, then the | |
| function updates Pivot's original parent on output | |
| according to the rotation, and NewRoot is not | |
| accessed. | |
| If Pivot has no parent node on input (ie. Pivot is | |
| the root of the tree), then the function stores the | |
| new root node of the tree in NewRoot. | |
| **/ | |
| VOID | |
| RedBlackTreeRotateLeft ( | |
| IN OUT RED_BLACK_TREE_NODE *Pivot, | |
| OUT RED_BLACK_TREE_NODE **NewRoot | |
| ) | |
| { | |
| RED_BLACK_TREE_NODE *Parent; | |
| RED_BLACK_TREE_NODE *RightChild; | |
| RED_BLACK_TREE_NODE *RightLeftChild; | |
| Parent = Pivot->Parent; | |
| RightChild = Pivot->Right; | |
| RightLeftChild = RightChild->Left; | |
| Pivot->Right = RightLeftChild; | |
| if (RightLeftChild != NULL) { | |
| RightLeftChild->Parent = Pivot; | |
| } | |
| RightChild->Parent = Parent; | |
| if (Parent == NULL) { | |
| *NewRoot = RightChild; | |
| } else { | |
| if (Pivot == Parent->Left) { | |
| Parent->Left = RightChild; | |
| } else { | |
| Parent->Right = RightChild; | |
| } | |
| } | |
| RightChild->Left = Pivot; | |
| Pivot->Parent = RightChild; | |
| } | |
| /** | |
| Insert (link) a user structure into the tree. | |
| Read-write operation. | |
| This function allocates the new tree node with MemoryAllocationLib's | |
| AllocatePool() function. | |
| @param[in,out] Tree The tree to insert UserStruct into. | |
| @param[out] Node The meaning of this optional, output-only | |
| parameter depends on the return value of the | |
| function. | |
| When insertion is successful (RETURN_SUCCESS), | |
| Node is set on output to the new tree node that | |
| now links UserStruct. | |
| When insertion fails due to lack of memory | |
| (RETURN_OUT_OF_RESOURCES), Node is not changed. | |
| When insertion fails due to key collision (ie. | |
| another user structure is already in the tree that | |
| compares equal to UserStruct), with return value | |
| RETURN_ALREADY_STARTED, then Node is set on output | |
| to the node that links the colliding user | |
| structure. This enables "find-or-insert" in one | |
| function call, or helps with later removal of the | |
| colliding element. | |
| @param[in] UserStruct The user structure to link into the tree. | |
| UserStruct is ordered against in-tree user | |
| structures with the Tree->UserStructCompare() | |
| function. | |
| @retval RETURN_SUCCESS Insertion successful. A new tree node has | |
| been allocated, linking UserStruct. The new | |
| tree node is reported back in Node (if the | |
| caller requested it). | |
| Existing RED_BLACK_TREE_NODE pointers into | |
| Tree remain valid. For example, on-going | |
| iterations in the caller can continue with | |
| OrderedCollectionNext() / | |
| OrderedCollectionPrev(), and they will | |
| return the new node at some point if user | |
| structure order dictates it. | |
| @retval RETURN_OUT_OF_RESOURCES AllocatePool() failed to allocate memory for | |
| the new tree node. The tree has not been | |
| changed. Existing RED_BLACK_TREE_NODE | |
| pointers into Tree remain valid. | |
| @retval RETURN_ALREADY_STARTED A user structure has been found in the tree | |
| that compares equal to UserStruct. The node | |
| linking the colliding user structure is | |
| reported back in Node (if the caller | |
| requested it). The tree has not been | |
| changed. Existing RED_BLACK_TREE_NODE | |
| pointers into Tree remain valid. | |
| **/ | |
| RETURN_STATUS | |
| EFIAPI | |
| OrderedCollectionInsert ( | |
| IN OUT RED_BLACK_TREE *Tree, | |
| OUT RED_BLACK_TREE_NODE **Node OPTIONAL, | |
| IN VOID *UserStruct | |
| ) | |
| { | |
| RED_BLACK_TREE_NODE *Tmp; | |
| RED_BLACK_TREE_NODE *Parent; | |
| INTN Result; | |
| RETURN_STATUS Status; | |
| RED_BLACK_TREE_NODE *NewRoot; | |
| Tmp = Tree->Root; | |
| Parent = NULL; | |
| Result = 0; | |
| // | |
| // First look for a collision, saving the last examined node for the case | |
| // when there's no collision. | |
| // | |
| while (Tmp != NULL) { | |
| Result = Tree->UserStructCompare (UserStruct, Tmp->UserStruct); | |
| if (Result == 0) { | |
| break; | |
| } | |
| Parent = Tmp; | |
| Tmp = (Result < 0) ? Tmp->Left : Tmp->Right; | |
| } | |
| if (Tmp != NULL) { | |
| if (Node != NULL) { | |
| *Node = Tmp; | |
| } | |
| Status = RETURN_ALREADY_STARTED; | |
| goto Done; | |
| } | |
| // | |
| // no collision, allocate a new node | |
| // | |
| Tmp = AllocatePool (sizeof *Tmp); | |
| if (Tmp == NULL) { | |
| Status = RETURN_OUT_OF_RESOURCES; | |
| goto Done; | |
| } | |
| if (Node != NULL) { | |
| *Node = Tmp; | |
| } | |
| // | |
| // reference the user structure from the node | |
| // | |
| Tmp->UserStruct = UserStruct; | |
| // | |
| // Link the node as a child to the correct side of the parent. | |
| // If there's no parent, the new node is the root node in the tree. | |
| // | |
| Tmp->Parent = Parent; | |
| Tmp->Left = NULL; | |
| Tmp->Right = NULL; | |
| if (Parent == NULL) { | |
| Tree->Root = Tmp; | |
| Tmp->Color = RedBlackTreeBlack; | |
| Status = RETURN_SUCCESS; | |
| goto Done; | |
| } | |
| if (Result < 0) { | |
| Parent->Left = Tmp; | |
| } else { | |
| Parent->Right = Tmp; | |
| } | |
| Tmp->Color = RedBlackTreeRed; | |
| // | |
| // Red-black tree properties: | |
| // | |
| // #1 Each node is either red or black (RED_BLACK_TREE_NODE.Color). | |
| // | |
| // #2 Each leaf (ie. a pseudo-node pointed-to by a NULL valued | |
| // RED_BLACK_TREE_NODE.Left or RED_BLACK_TREE_NODE.Right field) is black. | |
| // | |
| // #3 Each red node has two black children. | |
| // | |
| // #4 For any node N, and for any leaves L1 and L2 reachable from N, the | |
| // paths N..L1 and N..L2 contain the same number of black nodes. | |
| // | |
| // #5 The root node is black. | |
| // | |
| // By replacing a leaf with a red node above, only property #3 may have been | |
| // broken. (Note that this is the only edge across which property #3 might | |
| // not hold in the entire tree.) Restore property #3. | |
| // | |
| NewRoot = Tree->Root; | |
| while (Tmp != NewRoot && Parent->Color == RedBlackTreeRed) { | |
| RED_BLACK_TREE_NODE *GrandParent; | |
| RED_BLACK_TREE_NODE *Uncle; | |
| // | |
| // Tmp is not the root node. Tmp is red. Tmp's parent is red. (Breaking | |
| // property #3.) | |
| // | |
| // Due to property #5, Tmp's parent cannot be the root node, hence Tmp's | |
| // grandparent exists. | |
| // | |
| // Tmp's grandparent is black, because property #3 is only broken between | |
| // Tmp and Tmp's parent. | |
| // | |
| GrandParent = Parent->Parent; | |
| if (Parent == GrandParent->Left) { | |
| Uncle = GrandParent->Right; | |
| if (Uncle != NULL && Uncle->Color == RedBlackTreeRed) { | |
| // | |
| // GrandParent (black) | |
| // / \_ | |
| // Parent (red) Uncle (red) | |
| // | | |
| // Tmp (red) | |
| // | |
| Parent->Color = RedBlackTreeBlack; | |
| Uncle->Color = RedBlackTreeBlack; | |
| GrandParent->Color = RedBlackTreeRed; | |
| // | |
| // GrandParent (red) | |
| // / \_ | |
| // Parent (black) Uncle (black) | |
| // | | |
| // Tmp (red) | |
| // | |
| // We restored property #3 between Tmp and Tmp's parent, without | |
| // breaking property #4. However, we may have broken property #3 | |
| // between Tmp's grandparent and Tmp's great-grandparent (if any), so | |
| // repeat the loop for Tmp's grandparent. | |
| // | |
| // If Tmp's grandparent has no parent, then the loop will terminate, | |
| // and we will have broken property #5, by coloring the root red. We'll | |
| // restore property #5 after the loop, without breaking any others. | |
| // | |
| Tmp = GrandParent; | |
| Parent = Tmp->Parent; | |
| } else { | |
| // | |
| // Tmp's uncle is black (satisfied by the case too when Tmp's uncle is | |
| // NULL, see property #2). | |
| // | |
| if (Tmp == Parent->Right) { | |
| // | |
| // GrandParent (black): D | |
| // / \_ | |
| // Parent (red): A Uncle (black): E | |
| // \_ | |
| // Tmp (red): B | |
| // \_ | |
| // black: C | |
| // | |
| // Rotate left, pivoting on node A. This keeps the breakage of | |
| // property #3 in the same spot, and keeps other properties intact | |
| // (because both Tmp and its parent are red). | |
| // | |
| Tmp = Parent; | |
| RedBlackTreeRotateLeft (Tmp, &NewRoot); | |
| Parent = Tmp->Parent; | |
| // | |
| // With the rotation we reached the same configuration as if Tmp had | |
| // been a left child to begin with. | |
| // | |
| // GrandParent (black): D | |
| // / \_ | |
| // Parent (red): B Uncle (black): E | |
| // / \_ | |
| // Tmp (red): A black: C | |
| // | |
| ASSERT (GrandParent == Parent->Parent); | |
| } | |
| Parent->Color = RedBlackTreeBlack; | |
| GrandParent->Color = RedBlackTreeRed; | |
| // | |
| // Property #3 is now restored, but we've broken property #4. Namely, | |
| // paths going through node E now see a decrease in black count, while | |
| // paths going through node B don't. | |
| // | |
| // GrandParent (red): D | |
| // / \_ | |
| // Parent (black): B Uncle (black): E | |
| // / \_ | |
| // Tmp (red): A black: C | |
| // | |
| RedBlackTreeRotateRight (GrandParent, &NewRoot); | |
| // | |
| // Property #4 has been restored for node E, and preserved for others. | |
| // | |
| // Parent (black): B | |
| // / \_ | |
| // Tmp (red): A [GrandParent] (red): D | |
| // / \_ | |
| // black: C [Uncle] (black): E | |
| // | |
| // This configuration terminates the loop because Tmp's parent is now | |
| // black. | |
| // | |
| } | |
| } else { | |
| // | |
| // Symmetrical to the other branch. | |
| // | |
| Uncle = GrandParent->Left; | |
| if (Uncle != NULL && Uncle->Color == RedBlackTreeRed) { | |
| Parent->Color = RedBlackTreeBlack; | |
| Uncle->Color = RedBlackTreeBlack; | |
| GrandParent->Color = RedBlackTreeRed; | |
| Tmp = GrandParent; | |
| Parent = Tmp->Parent; | |
| } else { | |
| if (Tmp == Parent->Left) { | |
| Tmp = Parent; | |
| RedBlackTreeRotateRight (Tmp, &NewRoot); | |
| Parent = Tmp->Parent; | |
| ASSERT (GrandParent == Parent->Parent); | |
| } | |
| Parent->Color = RedBlackTreeBlack; | |
| GrandParent->Color = RedBlackTreeRed; | |
| RedBlackTreeRotateLeft (GrandParent, &NewRoot); | |
| } | |
| } | |
| } | |
| NewRoot->Color = RedBlackTreeBlack; | |
| Tree->Root = NewRoot; | |
| Status = RETURN_SUCCESS; | |
| Done: | |
| if (FeaturePcdGet (PcdValidateOrderedCollection)) { | |
| RedBlackTreeValidate (Tree); | |
| } | |
| return Status; | |
| } | |
| /** | |
| Check if a node is black, allowing for leaf nodes (see property #2). | |
| This is a convenience shorthand. | |
| param[in] Node The node to check. Node may be NULL, corresponding to a leaf. | |
| @return If Node is NULL or colored black. | |
| **/ | |
| BOOLEAN | |
| NodeIsNullOrBlack ( | |
| IN CONST RED_BLACK_TREE_NODE *Node | |
| ) | |
| { | |
| return (BOOLEAN)(Node == NULL || Node->Color == RedBlackTreeBlack); | |
| } | |
| /** | |
| Delete a node from the tree, unlinking the associated user structure. | |
| Read-write operation. | |
| @param[in,out] Tree The tree to delete Node from. | |
| @param[in] Node The tree node to delete from Tree. The caller is | |
| responsible for ensuring that Node belongs to | |
| Tree, and that Node is non-NULL and valid. Node is | |
| typically an earlier return value, or output | |
| parameter, of: | |
| - OrderedCollectionFind(), for deleting a node by | |
| user structure key, | |
| - OrderedCollectionMin() / OrderedCollectionMax(), | |
| for deleting the minimum / maximum node, | |
| - OrderedCollectionNext() / | |
| OrderedCollectionPrev(), for deleting a node | |
| found during an iteration, | |
| - OrderedCollectionInsert() with return value | |
| RETURN_ALREADY_STARTED, for deleting a node | |
| whose linked user structure caused collision | |
| during insertion. | |
| Given a non-empty Tree, Tree->Root is also a valid | |
| Node argument (typically used for simplicity in | |
| loops that empty the tree completely). | |
| Node is released with MemoryAllocationLib's | |
| FreePool() function. | |
| Existing RED_BLACK_TREE_NODE pointers (ie. | |
| iterators) *different* from Node remain valid. For | |
| example: | |
| - OrderedCollectionNext() / | |
| OrderedCollectionPrev() iterations in the caller | |
| can be continued from Node, if | |
| OrderedCollectionNext() or | |
| OrderedCollectionPrev() is called on Node | |
| *before* OrderedCollectionDelete() is. That is, | |
| fetch the successor / predecessor node first, | |
| then delete Node. | |
| - On-going iterations in the caller that would | |
| have otherwise returned Node at some point, as | |
| dictated by user structure order, will correctly | |
| reflect the absence of Node after | |
| OrderedCollectionDelete() is called | |
| mid-iteration. | |
| @param[out] UserStruct If the caller provides this optional output-only | |
| parameter, then on output it is set to the user | |
| structure originally linked by Node (which is now | |
| freed). | |
| This is a convenience that may save the caller a | |
| OrderedCollectionUserStruct() invocation before | |
| calling OrderedCollectionDelete(), in order to | |
| retrieve the user structure being unlinked. | |
| **/ | |
| VOID | |
| EFIAPI | |
| OrderedCollectionDelete ( | |
| IN OUT RED_BLACK_TREE *Tree, | |
| IN RED_BLACK_TREE_NODE *Node, | |
| OUT VOID **UserStruct OPTIONAL | |
| ) | |
| { | |
| RED_BLACK_TREE_NODE *NewRoot; | |
| RED_BLACK_TREE_NODE *OrigLeftChild; | |
| RED_BLACK_TREE_NODE *OrigRightChild; | |
| RED_BLACK_TREE_NODE *OrigParent; | |
| RED_BLACK_TREE_NODE *Child; | |
| RED_BLACK_TREE_NODE *Parent; | |
| RED_BLACK_TREE_COLOR ColorOfUnlinked; | |
| NewRoot = Tree->Root; | |
| OrigLeftChild = Node->Left, | |
| OrigRightChild = Node->Right, | |
| OrigParent = Node->Parent; | |
| if (UserStruct != NULL) { | |
| *UserStruct = Node->UserStruct; | |
| } | |
| // | |
| // After this block, no matter which branch we take: | |
| // - Child will point to the unique (or NULL) original child of the node that | |
| // we will have unlinked, | |
| // - Parent will point to the *position* of the original parent of the node | |
| // that we will have unlinked. | |
| // | |
| if (OrigLeftChild == NULL || OrigRightChild == NULL) { | |
| // | |
| // Node has at most one child. We can connect that child (if any) with | |
| // Node's parent (if any), unlinking Node. This will preserve ordering | |
| // because the subtree rooted in Node's child (if any) remains on the same | |
| // side of Node's parent (if any) that Node was before. | |
| // | |
| Parent = OrigParent; | |
| Child = (OrigLeftChild != NULL) ? OrigLeftChild : OrigRightChild; | |
| ColorOfUnlinked = Node->Color; | |
| if (Child != NULL) { | |
| Child->Parent = Parent; | |
| } | |
| if (OrigParent == NULL) { | |
| NewRoot = Child; | |
| } else { | |
| if (Node == OrigParent->Left) { | |
| OrigParent->Left = Child; | |
| } else { | |
| OrigParent->Right = Child; | |
| } | |
| } | |
| } else { | |
| // | |
| // Node has two children. We unlink Node's successor, and then link it into | |
| // Node's place, keeping Node's original color. This preserves ordering | |
| // because: | |
| // - Node's left subtree is less than Node, hence less than Node's | |
| // successor. | |
| // - Node's right subtree is greater than Node. Node's successor is the | |
| // minimum of that subtree, hence Node's successor is less than Node's | |
| // right subtree with its minimum removed. | |
| // - Node's successor is in Node's subtree, hence it falls on the same side | |
| // of Node's parent as Node itself. The relinking doesn't change this | |
| // relation. | |
| // | |
| RED_BLACK_TREE_NODE *ToRelink; | |
| ToRelink = OrigRightChild; | |
| if (ToRelink->Left == NULL) { | |
| // | |
| // OrigRightChild itself is Node's successor, it has no left child: | |
| // | |
| // OrigParent | |
| // | | |
| // Node: B | |
| // / \_ | |
| // OrigLeftChild: A OrigRightChild: E <--- Parent, ToRelink | |
| // \_ | |
| // F <--- Child | |
| // | |
| Parent = OrigRightChild; | |
| Child = OrigRightChild->Right; | |
| } else { | |
| do { | |
| ToRelink = ToRelink->Left; | |
| } while (ToRelink->Left != NULL); | |
| // | |
| // Node's successor is the minimum of OrigRightChild's proper subtree: | |
| // | |
| // OrigParent | |
| // | | |
| // Node: B | |
| // / \_ | |
| // OrigLeftChild: A OrigRightChild: E <--- Parent | |
| // / | |
| // C <--- ToRelink | |
| // \_ | |
| // D <--- Child | |
| Parent = ToRelink->Parent; | |
| Child = ToRelink->Right; | |
| // | |
| // Unlink Node's successor (ie. ToRelink): | |
| // | |
| // OrigParent | |
| // | | |
| // Node: B | |
| // / \_ | |
| // OrigLeftChild: A OrigRightChild: E <--- Parent | |
| // / | |
| // D <--- Child | |
| // | |
| // C <--- ToRelink | |
| // | |
| Parent->Left = Child; | |
| if (Child != NULL) { | |
| Child->Parent = Parent; | |
| } | |
| // | |
| // We start to link Node's unlinked successor into Node's place: | |
| // | |
| // OrigParent | |
| // | | |
| // Node: B C <--- ToRelink | |
| // / \_ | |
| // OrigLeftChild: A OrigRightChild: E <--- Parent | |
| // / | |
| // D <--- Child | |
| // | |
| // | |
| // | |
| ToRelink->Right = OrigRightChild; | |
| OrigRightChild->Parent = ToRelink; | |
| } | |
| // | |
| // The rest handles both cases, attaching ToRelink (Node's original | |
| // successor) to OrigLeftChild and OrigParent. | |
| // | |
| // Parent, | |
| // OrigParent ToRelink OrigParent | |
| // | | | | |
| // Node: B | Node: B Parent | |
| // v | | |
| // OrigRightChild: E C <--- ToRelink | | |
| // / \ / \ v | |
| // OrigLeftChild: A F OrigLeftChild: A OrigRightChild: E | |
| // ^ / | |
| // | D <--- Child | |
| // Child | |
| // | |
| ToRelink->Left = OrigLeftChild; | |
| OrigLeftChild->Parent = ToRelink; | |
| // | |
| // Node's color must be preserved in Node's original place. | |
| // | |
| ColorOfUnlinked = ToRelink->Color; | |
| ToRelink->Color = Node->Color; | |
| // | |
| // Finish linking Node's unlinked successor into Node's place. | |
| // | |
| // Parent, | |
| // Node: B ToRelink Node: B | |
| // | | |
| // OrigParent | OrigParent Parent | |
| // | v | | | |
| // OrigRightChild: E C <--- ToRelink | | |
| // / \ / \ v | |
| // OrigLeftChild: A F OrigLeftChild: A OrigRightChild: E | |
| // ^ / | |
| // | D <--- Child | |
| // Child | |
| // | |
| ToRelink->Parent = OrigParent; | |
| if (OrigParent == NULL) { | |
| NewRoot = ToRelink; | |
| } else { | |
| if (Node == OrigParent->Left) { | |
| OrigParent->Left = ToRelink; | |
| } else { | |
| OrigParent->Right = ToRelink; | |
| } | |
| } | |
| } | |
| FreePool (Node); | |
| // | |
| // If the node that we unlinked from its original spot (ie. Node itself, or | |
| // Node's successor), was red, then we broke neither property #3 nor property | |
| // #4: we didn't create any red-red edge between Child and Parent, and we | |
| // didn't change the black count on any path. | |
| // | |
| if (ColorOfUnlinked == RedBlackTreeBlack) { | |
| // | |
| // However, if the unlinked node was black, then we have to transfer its | |
| // "black-increment" to its unique child (pointed-to by Child), lest we | |
| // break property #4 for its ancestors. | |
| // | |
| // If Child is red, we can simply color it black. If Child is black | |
| // already, we can't technically transfer a black-increment to it, due to | |
| // property #1. | |
| // | |
| // In the following loop we ascend searching for a red node to color black, | |
| // or until we reach the root (in which case we can drop the | |
| // black-increment). Inside the loop body, Child has a black value of 2, | |
| // transitorily breaking property #1 locally, but maintaining property #4 | |
| // globally. | |
| // | |
| // Rotations in the loop preserve property #4. | |
| // | |
| while (Child != NewRoot && NodeIsNullOrBlack (Child)) { | |
| RED_BLACK_TREE_NODE *Sibling; | |
| RED_BLACK_TREE_NODE *LeftNephew; | |
| RED_BLACK_TREE_NODE *RightNephew; | |
| if (Child == Parent->Left) { | |
| Sibling = Parent->Right; | |
| // | |
| // Sibling can never be NULL (ie. a leaf). | |
| // | |
| // If Sibling was NULL, then the black count on the path from Parent to | |
| // Sibling would equal Parent's black value, plus 1 (due to property | |
| // #2). Whereas the black count on the path from Parent to any leaf via | |
| // Child would be at least Parent's black value, plus 2 (due to Child's | |
| // black value of 2). This would clash with property #4. | |
| // | |
| // (Sibling can be black of course, but it has to be an internal node. | |
| // Internality allows Sibling to have children, bumping the black | |
| // counts of paths that go through it.) | |
| // | |
| ASSERT (Sibling != NULL); | |
| if (Sibling->Color == RedBlackTreeRed) { | |
| // | |
| // Sibling's red color implies its children (if any), node C and node | |
| // E, are black (property #3). It also implies that Parent is black. | |
| // | |
| // grandparent grandparent | |
| // | | | |
| // Parent,b:B b:D | |
| // / \ / \_ | |
| // Child,2b:A Sibling,r:D ---> Parent,r:B b:E | |
| // /\ /\_ | |
| // b:C b:E Child,2b:A Sibling,b:C | |
| // | |
| Sibling->Color = RedBlackTreeBlack; | |
| Parent->Color = RedBlackTreeRed; | |
| RedBlackTreeRotateLeft (Parent, &NewRoot); | |
| Sibling = Parent->Right; | |
| // | |
| // Same reasoning as above. | |
| // | |
| ASSERT (Sibling != NULL); | |
| } | |
| // | |
| // Sibling is black, and not NULL. (Ie. Sibling is a black internal | |
| // node.) | |
| // | |
| ASSERT (Sibling->Color == RedBlackTreeBlack); | |
| LeftNephew = Sibling->Left; | |
| RightNephew = Sibling->Right; | |
| if (NodeIsNullOrBlack (LeftNephew) && | |
| NodeIsNullOrBlack (RightNephew)) { | |
| // | |
| // In this case we can "steal" one black value from Child and Sibling | |
| // each, and pass it to Parent. "Stealing" means that Sibling (black | |
| // value 1) becomes red, Child (black value 2) becomes singly-black, | |
| // and Parent will have to be examined if it can eat the | |
| // black-increment. | |
| // | |
| // Sibling is allowed to become red because both of its children are | |
| // black (property #3). | |
| // | |
| // grandparent Parent | |
| // | | | |
| // Parent,x:B Child,x:B | |
| // / \ / \_ | |
| // Child,2b:A Sibling,b:D ---> b:A r:D | |
| // /\ /\_ | |
| // LeftNephew,b:C RightNephew,b:E b:C b:E | |
| // | |
| Sibling->Color = RedBlackTreeRed; | |
| Child = Parent; | |
| Parent = Parent->Parent; | |
| // | |
| // Continue ascending. | |
| // | |
| } else { | |
| // | |
| // At least one nephew is red. | |
| // | |
| if (NodeIsNullOrBlack (RightNephew)) { | |
| // | |
| // Since the right nephew is black, the left nephew is red. Due to | |
| // property #3, LeftNephew has two black children, hence node E is | |
| // black. | |
| // | |
| // Together with the rotation, this enables us to color node F red | |
| // (because property #3 will be satisfied). We flip node D to black | |
| // to maintain property #4. | |
| // | |
| // grandparent grandparent | |
| // | | | |
| // Parent,x:B Parent,x:B | |
| // /\ /\_ | |
| // Child,2b:A Sibling,b:F ---> Child,2b:A Sibling,b:D | |
| // /\ / \_ | |
| // LeftNephew,r:D RightNephew,b:G b:C RightNephew,r:F | |
| // /\ /\_ | |
| // b:C b:E b:E b:G | |
| // | |
| LeftNephew->Color = RedBlackTreeBlack; | |
| Sibling->Color = RedBlackTreeRed; | |
| RedBlackTreeRotateRight (Sibling, &NewRoot); | |
| Sibling = Parent->Right; | |
| RightNephew = Sibling->Right; | |
| // | |
| // These operations ensure that... | |
| // | |
| } | |
| // | |
| // ... RightNephew is definitely red here, plus Sibling is (still) | |
| // black and non-NULL. | |
| // | |
| ASSERT (RightNephew != NULL); | |
| ASSERT (RightNephew->Color == RedBlackTreeRed); | |
| ASSERT (Sibling != NULL); | |
| ASSERT (Sibling->Color == RedBlackTreeBlack); | |
| // | |
| // In this case we can flush the extra black-increment immediately, | |
| // restoring property #1 for Child (node A): we color RightNephew | |
| // (node E) from red to black. | |
| // | |
| // In order to maintain property #4, we exchange colors between | |
| // Parent and Sibling (nodes B and D), and rotate left around Parent | |
| // (node B). The transformation doesn't change the black count | |
| // increase incurred by each partial path, eg. | |
| // - ascending from node A: 2 + x == 1 + 1 + x | |
| // - ascending from node C: y + 1 + x == y + 1 + x | |
| // - ascending from node E: 0 + 1 + x == 1 + x | |
| // | |
| // The color exchange is valid, because even if x stands for red, | |
| // both children of node D are black after the transformation | |
| // (preserving property #3). | |
| // | |
| // grandparent grandparent | |
| // | | | |
| // Parent,x:B x:D | |
| // / \ / \_ | |
| // Child,2b:A Sibling,b:D ---> b:B b:E | |
| // / \ / \_ | |
| // y:C RightNephew,r:E b:A y:C | |
| // | |
| // | |
| Sibling->Color = Parent->Color; | |
| Parent->Color = RedBlackTreeBlack; | |
| RightNephew->Color = RedBlackTreeBlack; | |
| RedBlackTreeRotateLeft (Parent, &NewRoot); | |
| Child = NewRoot; | |
| // | |
| // This terminates the loop. | |
| // | |
| } | |
| } else { | |
| // | |
| // Mirrors the other branch. | |
| // | |
| Sibling = Parent->Left; | |
| ASSERT (Sibling != NULL); | |
| if (Sibling->Color == RedBlackTreeRed) { | |
| Sibling->Color = RedBlackTreeBlack; | |
| Parent->Color = RedBlackTreeRed; | |
| RedBlackTreeRotateRight (Parent, &NewRoot); | |
| Sibling = Parent->Left; | |
| ASSERT (Sibling != NULL); | |
| } | |
| ASSERT (Sibling->Color == RedBlackTreeBlack); | |
| RightNephew = Sibling->Right; | |
| LeftNephew = Sibling->Left; | |
| if (NodeIsNullOrBlack (RightNephew) && | |
| NodeIsNullOrBlack (LeftNephew)) { | |
| Sibling->Color = RedBlackTreeRed; | |
| Child = Parent; | |
| Parent = Parent->Parent; | |
| } else { | |
| if (NodeIsNullOrBlack (LeftNephew)) { | |
| RightNephew->Color = RedBlackTreeBlack; | |
| Sibling->Color = RedBlackTreeRed; | |
| RedBlackTreeRotateLeft (Sibling, &NewRoot); | |
| Sibling = Parent->Left; | |
| LeftNephew = Sibling->Left; | |
| } | |
| ASSERT (LeftNephew != NULL); | |
| ASSERT (LeftNephew->Color == RedBlackTreeRed); | |
| ASSERT (Sibling != NULL); | |
| ASSERT (Sibling->Color == RedBlackTreeBlack); | |
| Sibling->Color = Parent->Color; | |
| Parent->Color = RedBlackTreeBlack; | |
| LeftNephew->Color = RedBlackTreeBlack; | |
| RedBlackTreeRotateRight (Parent, &NewRoot); | |
| Child = NewRoot; | |
| } | |
| } | |
| } | |
| if (Child != NULL) { | |
| Child->Color = RedBlackTreeBlack; | |
| } | |
| } | |
| Tree->Root = NewRoot; | |
| if (FeaturePcdGet (PcdValidateOrderedCollection)) { | |
| RedBlackTreeValidate (Tree); | |
| } | |
| } | |
| /** | |
| Recursively check the red-black tree properties #1 to #4 on a node. | |
| @param[in] Node The root of the subtree to validate. | |
| @retval The black-height of Node's parent. | |
| **/ | |
| UINT32 | |
| RedBlackTreeRecursiveCheck ( | |
| IN CONST RED_BLACK_TREE_NODE *Node | |
| ) | |
| { | |
| UINT32 LeftHeight; | |
| UINT32 RightHeight; | |
| // | |
| // property #2 | |
| // | |
| if (Node == NULL) { | |
| return 1; | |
| } | |
| // | |
| // property #1 | |
| // | |
| ASSERT (Node->Color == RedBlackTreeRed || Node->Color == RedBlackTreeBlack); | |
| // | |
| // property #3 | |
| // | |
| if (Node->Color == RedBlackTreeRed) { | |
| ASSERT (NodeIsNullOrBlack (Node->Left)); | |
| ASSERT (NodeIsNullOrBlack (Node->Right)); | |
| } | |
| // | |
| // property #4 | |
| // | |
| LeftHeight = RedBlackTreeRecursiveCheck (Node->Left); | |
| RightHeight = RedBlackTreeRecursiveCheck (Node->Right); | |
| ASSERT (LeftHeight == RightHeight); | |
| return (Node->Color == RedBlackTreeBlack) + LeftHeight; | |
| } | |
| /** | |
| A slow function that asserts that the tree is a valid red-black tree, and | |
| that it orders user structures correctly. | |
| Read-only operation. | |
| This function uses the stack for recursion and is not recommended for | |
| "production use". | |
| @param[in] Tree The tree to validate. | |
| **/ | |
| VOID | |
| RedBlackTreeValidate ( | |
| IN CONST RED_BLACK_TREE *Tree | |
| ) | |
| { | |
| UINT32 BlackHeight; | |
| UINT32 ForwardCount; | |
| UINT32 BackwardCount; | |
| CONST RED_BLACK_TREE_NODE *Last; | |
| CONST RED_BLACK_TREE_NODE *Node; | |
| DEBUG ((DEBUG_VERBOSE, "%a: Tree=%p\n", __FUNCTION__, Tree)); | |
| // | |
| // property #5 | |
| // | |
| ASSERT (NodeIsNullOrBlack (Tree->Root)); | |
| // | |
| // check the other properties | |
| // | |
| BlackHeight = RedBlackTreeRecursiveCheck (Tree->Root) - 1; | |
| // | |
| // forward ordering | |
| // | |
| Last = OrderedCollectionMin (Tree); | |
| ForwardCount = (Last != NULL); | |
| for (Node = OrderedCollectionNext (Last); Node != NULL; | |
| Node = OrderedCollectionNext (Last)) { | |
| ASSERT (Tree->UserStructCompare (Last->UserStruct, Node->UserStruct) < 0); | |
| Last = Node; | |
| ++ForwardCount; | |
| } | |
| // | |
| // backward ordering | |
| // | |
| Last = OrderedCollectionMax (Tree); | |
| BackwardCount = (Last != NULL); | |
| for (Node = OrderedCollectionPrev (Last); Node != NULL; | |
| Node = OrderedCollectionPrev (Last)) { | |
| ASSERT (Tree->UserStructCompare (Last->UserStruct, Node->UserStruct) > 0); | |
| Last = Node; | |
| ++BackwardCount; | |
| } | |
| ASSERT (ForwardCount == BackwardCount); | |
| DEBUG ((DEBUG_VERBOSE, "%a: Tree=%p BlackHeight=%Ld Count=%Ld\n", | |
| __FUNCTION__, Tree, (INT64)BlackHeight, (INT64)ForwardCount)); | |
| } |