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