// 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
+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
+ 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
+ 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
VOID *\r
EFIAPI\r
OrderedCollectionUserStruct (\r
- IN CONST RED_BLACK_TREE_NODE *Node\r
+ IN CONST RED_BLACK_TREE_NODE *Node\r
)\r
{\r
return Node->UserStruct;\r
**/\r
VOID\r
RedBlackTreeValidate (\r
- IN CONST RED_BLACK_TREE *Tree\r
+ IN CONST RED_BLACK_TREE *Tree\r
);\r
\r
-\r
/**\r
Allocate and initialize the RED_BLACK_TREE structure.\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
+ IN RED_BLACK_TREE_USER_COMPARE UserStructCompare,\r
+ IN RED_BLACK_TREE_KEY_COMPARE KeyCompare\r
)\r
{\r
- RED_BLACK_TREE *Tree;\r
+ RED_BLACK_TREE *Tree;\r
\r
Tree = AllocatePool (sizeof *Tree);\r
if (Tree == NULL) {\r
if (FeaturePcdGet (PcdValidateOrderedCollection)) {\r
RedBlackTreeValidate (Tree);\r
}\r
+\r
return Tree;\r
}\r
\r
-\r
/**\r
Check whether the tree is empty (has no nodes).\r
\r
BOOLEAN\r
EFIAPI\r
OrderedCollectionIsEmpty (\r
- IN CONST RED_BLACK_TREE *Tree\r
+ IN CONST RED_BLACK_TREE *Tree\r
)\r
{\r
return (BOOLEAN)(Tree->Root == NULL);\r
}\r
\r
-\r
/**\r
Uninitialize and release an empty RED_BLACK_TREE structure.\r
\r
VOID\r
EFIAPI\r
OrderedCollectionUninit (\r
- IN RED_BLACK_TREE *Tree\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
RED_BLACK_TREE_NODE *\r
EFIAPI\r
OrderedCollectionFind (\r
- IN CONST RED_BLACK_TREE *Tree,\r
- IN CONST VOID *StandaloneKey\r
+ IN CONST RED_BLACK_TREE *Tree,\r
+ IN CONST VOID *StandaloneKey\r
)\r
{\r
- RED_BLACK_TREE_NODE *Node;\r
+ RED_BLACK_TREE_NODE *Node;\r
\r
Node = Tree->Root;\r
while (Node != NULL) {\r
- INTN Result;\r
+ INTN Result;\r
\r
Result = Tree->KeyCompare (StandaloneKey, Node->UserStruct);\r
if (Result == 0) {\r
break;\r
}\r
+\r
Node = (Result < 0) ? Node->Left : Node->Right;\r
}\r
+\r
return Node;\r
}\r
\r
-\r
/**\r
Find the tree node of the minimum user structure stored in the tree.\r
\r
RED_BLACK_TREE_NODE *\r
EFIAPI\r
OrderedCollectionMin (\r
- IN CONST RED_BLACK_TREE *Tree\r
+ IN CONST RED_BLACK_TREE *Tree\r
)\r
{\r
- RED_BLACK_TREE_NODE *Node;\r
+ RED_BLACK_TREE_NODE *Node;\r
\r
Node = Tree->Root;\r
if (Node == NULL) {\r
return NULL;\r
}\r
+\r
while (Node->Left != NULL) {\r
Node = Node->Left;\r
}\r
+\r
return Node;\r
}\r
\r
-\r
/**\r
Find the tree node of the maximum user structure stored in the tree.\r
\r
RED_BLACK_TREE_NODE *\r
EFIAPI\r
OrderedCollectionMax (\r
- IN CONST RED_BLACK_TREE *Tree\r
+ IN CONST RED_BLACK_TREE *Tree\r
)\r
{\r
- RED_BLACK_TREE_NODE *Node;\r
+ RED_BLACK_TREE_NODE *Node;\r
\r
Node = Tree->Root;\r
if (Node == NULL) {\r
return NULL;\r
}\r
+\r
while (Node->Right != NULL) {\r
Node = Node->Right;\r
}\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
RED_BLACK_TREE_NODE *\r
EFIAPI\r
OrderedCollectionNext (\r
- IN CONST RED_BLACK_TREE_NODE *Node\r
+ IN CONST RED_BLACK_TREE_NODE *Node\r
)\r
{\r
- RED_BLACK_TREE_NODE *Walk;\r
- CONST RED_BLACK_TREE_NODE *Child;\r
+ RED_BLACK_TREE_NODE *Walk;\r
+ CONST RED_BLACK_TREE_NODE *Child;\r
\r
if (Node == NULL) {\r
return NULL;\r
while (Walk->Left != NULL) {\r
Walk = Walk->Left;\r
}\r
+\r
return Walk;\r
}\r
\r
// ascending to the left).\r
//\r
Child = Node;\r
- Walk = Child->Parent;\r
+ Walk = Child->Parent;\r
while (Walk != NULL && Child == Walk->Right) {\r
Child = Walk;\r
- Walk = Child->Parent;\r
+ Walk = Child->Parent;\r
}\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
RED_BLACK_TREE_NODE *\r
EFIAPI\r
OrderedCollectionPrev (\r
- IN CONST RED_BLACK_TREE_NODE *Node\r
+ IN CONST RED_BLACK_TREE_NODE *Node\r
)\r
{\r
- RED_BLACK_TREE_NODE *Walk;\r
- CONST RED_BLACK_TREE_NODE *Child;\r
+ RED_BLACK_TREE_NODE *Walk;\r
+ CONST RED_BLACK_TREE_NODE *Child;\r
\r
if (Node == NULL) {\r
return NULL;\r
while (Walk->Right != NULL) {\r
Walk = Walk->Right;\r
}\r
+\r
return Walk;\r
}\r
\r
// ascending to the right).\r
//\r
Child = Node;\r
- Walk = Child->Parent;\r
+ Walk = Child->Parent;\r
while (Walk != NULL && Child == Walk->Left) {\r
Child = Walk;\r
- Walk = Child->Parent;\r
+ Walk = Child->Parent;\r
}\r
+\r
return Walk;\r
}\r
\r
-\r
/**\r
Rotate tree nodes around Pivot to the right.\r
\r
**/\r
VOID\r
RedBlackTreeRotateRight (\r
- IN OUT RED_BLACK_TREE_NODE *Pivot,\r
- OUT RED_BLACK_TREE_NODE **NewRoot\r
+ IN OUT RED_BLACK_TREE_NODE *Pivot,\r
+ OUT RED_BLACK_TREE_NODE **NewRoot\r
)\r
{\r
- RED_BLACK_TREE_NODE *Parent;\r
- RED_BLACK_TREE_NODE *LeftChild;\r
- RED_BLACK_TREE_NODE *LeftRightChild;\r
+ RED_BLACK_TREE_NODE *Parent;\r
+ RED_BLACK_TREE_NODE *LeftChild;\r
+ RED_BLACK_TREE_NODE *LeftRightChild;\r
\r
Parent = Pivot->Parent;\r
LeftChild = Pivot->Left;\r
if (LeftRightChild != NULL) {\r
LeftRightChild->Parent = Pivot;\r
}\r
+\r
LeftChild->Parent = Parent;\r
if (Parent == NULL) {\r
*NewRoot = LeftChild;\r
Parent->Right = LeftChild;\r
}\r
}\r
+\r
LeftChild->Right = Pivot;\r
- Pivot->Parent = LeftChild;\r
+ Pivot->Parent = LeftChild;\r
}\r
\r
-\r
/**\r
Rotate tree nodes around Pivot to the left.\r
\r
**/\r
VOID\r
RedBlackTreeRotateLeft (\r
- IN OUT RED_BLACK_TREE_NODE *Pivot,\r
- OUT RED_BLACK_TREE_NODE **NewRoot\r
+ IN OUT RED_BLACK_TREE_NODE *Pivot,\r
+ OUT RED_BLACK_TREE_NODE **NewRoot\r
)\r
{\r
- RED_BLACK_TREE_NODE *Parent;\r
- RED_BLACK_TREE_NODE *RightChild;\r
- RED_BLACK_TREE_NODE *RightLeftChild;\r
+ RED_BLACK_TREE_NODE *Parent;\r
+ RED_BLACK_TREE_NODE *RightChild;\r
+ RED_BLACK_TREE_NODE *RightLeftChild;\r
\r
Parent = Pivot->Parent;\r
RightChild = Pivot->Right;\r
if (RightLeftChild != NULL) {\r
RightLeftChild->Parent = Pivot;\r
}\r
+\r
RightChild->Parent = Parent;\r
if (Parent == NULL) {\r
*NewRoot = RightChild;\r
Parent->Right = RightChild;\r
}\r
}\r
+\r
RightChild->Left = Pivot;\r
- Pivot->Parent = RightChild;\r
+ Pivot->Parent = RightChild;\r
}\r
\r
-\r
/**\r
Insert (link) a user structure into the tree.\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
+ 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;\r
- RED_BLACK_TREE_NODE *Parent;\r
- INTN Result;\r
- RETURN_STATUS Status;\r
- RED_BLACK_TREE_NODE *NewRoot;\r
+ RED_BLACK_TREE_NODE *Tmp;\r
+ RED_BLACK_TREE_NODE *Parent;\r
+ INTN Result;\r
+ RETURN_STATUS Status;\r
+ RED_BLACK_TREE_NODE *NewRoot;\r
\r
- Tmp = Tree->Root;\r
+ Tmp = Tree->Root;\r
Parent = NULL;\r
Result = 0;\r
\r
if (Result == 0) {\r
break;\r
}\r
+\r
Parent = Tmp;\r
- Tmp = (Result < 0) ? Tmp->Left : Tmp->Right;\r
+ Tmp = (Result < 0) ? Tmp->Left : Tmp->Right;\r
}\r
\r
if (Tmp != NULL) {\r
if (Node != NULL) {\r
*Node = Tmp;\r
}\r
+\r
Status = RETURN_ALREADY_STARTED;\r
goto Done;\r
}\r
Status = RETURN_OUT_OF_RESOURCES;\r
goto Done;\r
}\r
+\r
if (Node != NULL) {\r
*Node = Tmp;\r
}\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
+ Tmp->Left = NULL;\r
+ Tmp->Right = NULL;\r
if (Parent == NULL) {\r
Tree->Root = Tmp;\r
Tmp->Color = RedBlackTreeBlack;\r
- Status = RETURN_SUCCESS;\r
+ Status = RETURN_SUCCESS;\r
goto Done;\r
}\r
+\r
if (Result < 0) {\r
Parent->Left = Tmp;\r
} else {\r
Parent->Right = Tmp;\r
}\r
+\r
Tmp->Color = RedBlackTreeRed;\r
\r
//\r
\r
NewRoot = Tree->Root;\r
while (Tmp != NewRoot && Parent->Color == RedBlackTreeRed) {\r
- RED_BLACK_TREE_NODE *GrandParent;\r
- RED_BLACK_TREE_NODE *Uncle;\r
+ RED_BLACK_TREE_NODE *GrandParent;\r
+ RED_BLACK_TREE_NODE *Uncle;\r
\r
//\r
// Tmp is not the root node. Tmp is red. Tmp's parent is red. (Breaking\r
\r
if (Parent == GrandParent->Left) {\r
Uncle = GrandParent->Right;\r
- if (Uncle != NULL && Uncle->Color == RedBlackTreeRed) {\r
+ if ((Uncle != NULL) && (Uncle->Color == RedBlackTreeRed)) {\r
//\r
// GrandParent (black)\r
// / \_\r
// Tmp (red)\r
//\r
\r
- Parent->Color = RedBlackTreeBlack;\r
- Uncle->Color = RedBlackTreeBlack;\r
+ Parent->Color = RedBlackTreeBlack;\r
+ Uncle->Color = RedBlackTreeBlack;\r
GrandParent->Color = RedBlackTreeRed;\r
\r
//\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
+ Tmp = GrandParent;\r
Parent = Tmp->Parent;\r
} else {\r
//\r
ASSERT (GrandParent == Parent->Parent);\r
}\r
\r
- Parent->Color = RedBlackTreeBlack;\r
+ Parent->Color = RedBlackTreeBlack;\r
GrandParent->Color = RedBlackTreeRed;\r
\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
+ 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
+ Tmp = GrandParent;\r
+ Parent = Tmp->Parent;\r
} else {\r
if (Tmp == Parent->Left) {\r
Tmp = Parent;\r
Parent = Tmp->Parent;\r
ASSERT (GrandParent == Parent->Parent);\r
}\r
- Parent->Color = RedBlackTreeBlack;\r
+\r
+ Parent->Color = RedBlackTreeBlack;\r
GrandParent->Color = RedBlackTreeRed;\r
RedBlackTreeRotateLeft (GrandParent, &NewRoot);\r
}\r
}\r
\r
NewRoot->Color = RedBlackTreeBlack;\r
- Tree->Root = NewRoot;\r
- Status = RETURN_SUCCESS;\r
+ Tree->Root = NewRoot;\r
+ Status = RETURN_SUCCESS;\r
\r
Done:\r
if (FeaturePcdGet (PcdValidateOrderedCollection)) {\r
RedBlackTreeValidate (Tree);\r
}\r
+\r
return Status;\r
}\r
\r
-\r
/**\r
Check if a node is black, allowing for leaf nodes (see property #2).\r
\r
**/\r
BOOLEAN\r
NodeIsNullOrBlack (\r
- IN CONST RED_BLACK_TREE_NODE *Node\r
+ IN CONST RED_BLACK_TREE_NODE *Node\r
)\r
{\r
return (BOOLEAN)(Node == NULL || Node->Color == RedBlackTreeBlack);\r
}\r
\r
-\r
/**\r
Delete a node from the tree, unlinking the associated user structure.\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
+ 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;\r
- RED_BLACK_TREE_NODE *OrigRightChild;\r
- RED_BLACK_TREE_NODE *OrigParent;\r
- RED_BLACK_TREE_NODE *Child;\r
- RED_BLACK_TREE_NODE *Parent;\r
- RED_BLACK_TREE_COLOR ColorOfUnlinked;\r
+ RED_BLACK_TREE_NODE *NewRoot;\r
+ RED_BLACK_TREE_NODE *OrigLeftChild;\r
+ RED_BLACK_TREE_NODE *OrigRightChild;\r
+ RED_BLACK_TREE_NODE *OrigParent;\r
+ RED_BLACK_TREE_NODE *Child;\r
+ RED_BLACK_TREE_NODE *Parent;\r
+ RED_BLACK_TREE_COLOR ColorOfUnlinked;\r
\r
NewRoot = Tree->Root;\r
OrigLeftChild = Node->Left,\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
+ 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
+ Parent = OrigParent;\r
+ Child = (OrigLeftChild != NULL) ? OrigLeftChild : OrigRightChild;\r
ColorOfUnlinked = Node->Color;\r
\r
if (Child != NULL) {\r
Child->Parent = Parent;\r
}\r
+\r
if (OrigParent == NULL) {\r
NewRoot = Child;\r
} else {\r
// of Node's parent as Node itself. The relinking doesn't change this\r
// relation.\r
//\r
- RED_BLACK_TREE_NODE *ToRelink;\r
+ RED_BLACK_TREE_NODE *ToRelink;\r
\r
ToRelink = OrigRightChild;\r
if (ToRelink->Left == NULL) {\r
// F <--- Child\r
//\r
Parent = OrigRightChild;\r
- Child = OrigRightChild->Right;\r
+ Child = OrigRightChild->Right;\r
} else {\r
do {\r
ToRelink = ToRelink->Left;\r
// \_\r
// D <--- Child\r
Parent = ToRelink->Parent;\r
- Child = ToRelink->Right;\r
+ Child = ToRelink->Right;\r
\r
//\r
// Unlink Node's successor (ie. ToRelink):\r
//\r
//\r
//\r
- ToRelink->Right = OrigRightChild;\r
+ ToRelink->Right = OrigRightChild;\r
OrigRightChild->Parent = ToRelink;\r
}\r
\r
// | D <--- Child\r
// Child\r
//\r
- ToRelink->Left = OrigLeftChild;\r
+ ToRelink->Left = OrigLeftChild;\r
OrigLeftChild->Parent = ToRelink;\r
\r
//\r
// Rotations in the loop preserve property #4.\r
//\r
while (Child != NewRoot && NodeIsNullOrBlack (Child)) {\r
- RED_BLACK_TREE_NODE *Sibling;\r
- RED_BLACK_TREE_NODE *LeftNephew;\r
- RED_BLACK_TREE_NODE *RightNephew;\r
+ RED_BLACK_TREE_NODE *Sibling;\r
+ RED_BLACK_TREE_NODE *LeftNephew;\r
+ RED_BLACK_TREE_NODE *RightNephew;\r
\r
if (Child == Parent->Left) {\r
Sibling = Parent->Right;\r
// b:C b:E Child,2b:A Sibling,b:C\r
//\r
Sibling->Color = RedBlackTreeBlack;\r
- Parent->Color = RedBlackTreeRed;\r
+ Parent->Color = RedBlackTreeRed;\r
RedBlackTreeRotateLeft (Parent, &NewRoot);\r
Sibling = Parent->Right;\r
//\r
// node.)\r
//\r
ASSERT (Sibling->Color == RedBlackTreeBlack);\r
- LeftNephew = Sibling->Left;\r
+ LeftNephew = Sibling->Left;\r
RightNephew = Sibling->Right;\r
if (NodeIsNullOrBlack (LeftNephew) &&\r
- NodeIsNullOrBlack (RightNephew)) {\r
+ NodeIsNullOrBlack (RightNephew))\r
+ {\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
// LeftNephew,b:C RightNephew,b:E b:C b:E\r
//\r
Sibling->Color = RedBlackTreeRed;\r
- Child = Parent;\r
- Parent = Parent->Parent;\r
+ Child = Parent;\r
+ Parent = Parent->Parent;\r
//\r
// Continue ascending.\r
//\r
// b:C b:E b:E b:G\r
//\r
LeftNephew->Color = RedBlackTreeBlack;\r
- Sibling->Color = RedBlackTreeRed;\r
+ Sibling->Color = RedBlackTreeRed;\r
RedBlackTreeRotateRight (Sibling, &NewRoot);\r
- Sibling = Parent->Right;\r
+ Sibling = Parent->Right;\r
RightNephew = Sibling->Right;\r
//\r
// These operations ensure that...\r
//\r
}\r
+\r
//\r
// ... RightNephew is definitely red here, plus Sibling is (still)\r
// black and non-NULL.\r
// y:C RightNephew,r:E b:A y:C\r
//\r
//\r
- Sibling->Color = Parent->Color;\r
- Parent->Color = RedBlackTreeBlack;\r
+ Sibling->Color = Parent->Color;\r
+ Parent->Color = RedBlackTreeBlack;\r
RightNephew->Color = RedBlackTreeBlack;\r
RedBlackTreeRotateLeft (Parent, &NewRoot);\r
Child = NewRoot;\r
ASSERT (Sibling != NULL);\r
if (Sibling->Color == RedBlackTreeRed) {\r
Sibling->Color = RedBlackTreeBlack;\r
- Parent->Color = RedBlackTreeRed;\r
+ Parent->Color = RedBlackTreeRed;\r
RedBlackTreeRotateRight (Parent, &NewRoot);\r
Sibling = Parent->Left;\r
ASSERT (Sibling != NULL);\r
\r
ASSERT (Sibling->Color == RedBlackTreeBlack);\r
RightNephew = Sibling->Right;\r
- LeftNephew = Sibling->Left;\r
+ LeftNephew = Sibling->Left;\r
if (NodeIsNullOrBlack (RightNephew) &&\r
- NodeIsNullOrBlack (LeftNephew)) {\r
+ NodeIsNullOrBlack (LeftNephew))\r
+ {\r
Sibling->Color = RedBlackTreeRed;\r
- Child = Parent;\r
- Parent = Parent->Parent;\r
+ Child = Parent;\r
+ Parent = Parent->Parent;\r
} else {\r
if (NodeIsNullOrBlack (LeftNephew)) {\r
RightNephew->Color = RedBlackTreeBlack;\r
- Sibling->Color = RedBlackTreeRed;\r
+ Sibling->Color = RedBlackTreeRed;\r
RedBlackTreeRotateLeft (Sibling, &NewRoot);\r
- Sibling = Parent->Left;\r
+ Sibling = Parent->Left;\r
LeftNephew = Sibling->Left;\r
}\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
+ Sibling->Color = Parent->Color;\r
+ Parent->Color = RedBlackTreeBlack;\r
LeftNephew->Color = RedBlackTreeBlack;\r
RedBlackTreeRotateRight (Parent, &NewRoot);\r
Child = NewRoot;\r
}\r
}\r
\r
-\r
/**\r
Recursively check the red-black tree properties #1 to #4 on a node.\r
\r
**/\r
UINT32\r
RedBlackTreeRecursiveCheck (\r
- IN CONST RED_BLACK_TREE_NODE *Node\r
+ IN CONST RED_BLACK_TREE_NODE *Node\r
)\r
{\r
- UINT32 LeftHeight;\r
- UINT32 RightHeight;\r
+ UINT32 LeftHeight;\r
+ UINT32 RightHeight;\r
\r
//\r
// property #2\r
//\r
// property #4\r
//\r
- LeftHeight = RedBlackTreeRecursiveCheck (Node->Left);\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
VOID\r
RedBlackTreeValidate (\r
- IN CONST RED_BLACK_TREE *Tree\r
+ IN CONST RED_BLACK_TREE *Tree\r
)\r
{\r
- UINT32 BlackHeight;\r
- UINT32 ForwardCount;\r
- UINT32 BackwardCount;\r
- CONST RED_BLACK_TREE_NODE *Last;\r
- CONST RED_BLACK_TREE_NODE *Node;\r
+ UINT32 BlackHeight;\r
+ UINT32 ForwardCount;\r
+ UINT32 BackwardCount;\r
+ CONST RED_BLACK_TREE_NODE *Last;\r
+ CONST RED_BLACK_TREE_NODE *Node;\r
\r
DEBUG ((DEBUG_VERBOSE, "%a: Tree=%p\n", __FUNCTION__, Tree));\r
\r
//\r
// forward ordering\r
//\r
- Last = OrderedCollectionMin (Tree);\r
+ Last = OrderedCollectionMin (Tree);\r
ForwardCount = (Last != NULL);\r
for (Node = OrderedCollectionNext (Last); Node != NULL;\r
- Node = OrderedCollectionNext (Last)) {\r
+ Node = OrderedCollectionNext (Last))\r
+ {\r
ASSERT (Tree->UserStructCompare (Last->UserStruct, Node->UserStruct) < 0);\r
Last = Node;\r
++ForwardCount;\r
//\r
// backward ordering\r
//\r
- Last = OrderedCollectionMax (Tree);\r
+ Last = OrderedCollectionMax (Tree);\r
BackwardCount = (Last != NULL);\r
for (Node = OrderedCollectionPrev (Last); Node != NULL;\r
- Node = OrderedCollectionPrev (Last)) {\r
+ Node = OrderedCollectionPrev (Last))\r
+ {\r
ASSERT (Tree->UserStructCompare (Last->UserStruct, Node->UserStruct) > 0);\r
Last = Node;\r
++BackwardCount;\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
+ DEBUG ((\r
+ DEBUG_VERBOSE,\r
+ "%a: Tree=%p BlackHeight=%Ld Count=%Ld\n",\r
+ __FUNCTION__,\r
+ Tree,\r
+ (INT64)BlackHeight,\r
+ (INT64)ForwardCount\r
+ ));\r
}\r
projects / mirror_edk2.git / blobdiff