summaryrefslogtreecommitdiffstats
path: root/MdePkg/Library/BaseOrderedCollectionRedBlackTreeLib
diff options
context:
space:
mode:
authorEric Dong <eric.dong@intel.com>2014-08-20 02:06:12 +0000
committerydong10 <ydong10@6f19259b-4bc3-4df7-8a09-765794883524>2014-08-20 02:06:12 +0000
commit64fabae54bf39a3b164e911b9d3ff6985dc66036 (patch)
treea5b4a3907e7879b1c33123a7c99fd31f43e419dc /MdePkg/Library/BaseOrderedCollectionRedBlackTreeLib
parent30cad98e5fc4dfff73486b5b9e420a0a0b7a1bed (diff)
downloadedk2-64fabae54bf39a3b164e911b9d3ff6985dc66036.tar.gz
edk2-64fabae54bf39a3b164e911b9d3ff6985dc66036.tar.bz2
edk2-64fabae54bf39a3b164e911b9d3ff6985dc66036.zip
MdePkg: BaseOrderedCollectionRedBlackTreeLib: improve coding style
- The edk2 coding style prefers each variable declaration to stand on its own line. - Internal linkage (ie. STATIC) functions have caused problems with source level debugging before, so we generally avoid STATIC in MdePkg. - Even forward declarations of functions should carry full comment blocks. - Nullity checks in controlling expressions should be spelled out explicitly, as (Ptr != NULL). Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Eric Dong <eric.dong@intel.com> Reviewed-by: Laszlo Ersek <lersek@redhat.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15843 6f19259b-4bc3-4df7-8a09-765794883524
Diffstat (limited to 'MdePkg/Library/BaseOrderedCollectionRedBlackTreeLib')
-rw-r--r--MdePkg/Library/BaseOrderedCollectionRedBlackTreeLib/BaseOrderedCollectionRedBlackTreeLib.c58
1 files changed, 36 insertions, 22 deletions
diff --git a/MdePkg/Library/BaseOrderedCollectionRedBlackTreeLib/BaseOrderedCollectionRedBlackTreeLib.c b/MdePkg/Library/BaseOrderedCollectionRedBlackTreeLib/BaseOrderedCollectionRedBlackTreeLib.c
index b37caf239a..8d18a4b2bf 100644
--- a/MdePkg/Library/BaseOrderedCollectionRedBlackTreeLib/BaseOrderedCollectionRedBlackTreeLib.c
+++ b/MdePkg/Library/BaseOrderedCollectionRedBlackTreeLib/BaseOrderedCollectionRedBlackTreeLib.c
@@ -11,6 +11,7 @@
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
@@ -75,12 +76,17 @@ OrderedCollectionUserStruct (
return Node->UserStruct;
}
+/**
+ A slow function that asserts that the tree is a valid red-black tree, and
+ that it orders user structures correctly.
-//
-// Forward declaration of internal, unit test helper function. See
-// specification and function definition later.
-//
-STATIC
+ 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
@@ -417,14 +423,15 @@ OrderedCollectionPrev (
the root of the tree), then the function stores the
new root node of the tree in NewRoot.
**/
-STATIC
VOID
RedBlackTreeRotateRight (
IN OUT RED_BLACK_TREE_NODE *Pivot,
OUT RED_BLACK_TREE_NODE **NewRoot
)
{
- RED_BLACK_TREE_NODE *Parent, *LeftChild, *LeftRightChild;
+ RED_BLACK_TREE_NODE *Parent;
+ RED_BLACK_TREE_NODE *LeftChild;
+ RED_BLACK_TREE_NODE *LeftRightChild;
Parent = Pivot->Parent;
LeftChild = Pivot->Left;
@@ -481,14 +488,15 @@ RedBlackTreeRotateRight (
the root of the tree), then the function stores the
new root node of the tree in NewRoot.
**/
-STATIC
VOID
RedBlackTreeRotateLeft (
IN OUT RED_BLACK_TREE_NODE *Pivot,
OUT RED_BLACK_TREE_NODE **NewRoot
)
{
- RED_BLACK_TREE_NODE *Parent, *RightChild, *RightLeftChild;
+ RED_BLACK_TREE_NODE *Parent;
+ RED_BLACK_TREE_NODE *RightChild;
+ RED_BLACK_TREE_NODE *RightLeftChild;
Parent = Pivot->Parent;
RightChild = Pivot->Right;
@@ -582,7 +590,8 @@ OrderedCollectionInsert (
IN VOID *UserStruct
)
{
- RED_BLACK_TREE_NODE *Tmp, *Parent;
+ RED_BLACK_TREE_NODE *Tmp;
+ RED_BLACK_TREE_NODE *Parent;
INTN Result;
RETURN_STATUS Status;
RED_BLACK_TREE_NODE *NewRoot;
@@ -671,7 +680,8 @@ OrderedCollectionInsert (
NewRoot = Tree->Root;
while (Tmp != NewRoot && Parent->Color == RedBlackTreeRed) {
- RED_BLACK_TREE_NODE *GrandParent, *Uncle;
+ 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
@@ -831,8 +841,6 @@ Done:
@return If Node is NULL or colored black.
**/
-
-STATIC
BOOLEAN
NodeIsNullOrBlack (
IN CONST RED_BLACK_TREE_NODE *Node
@@ -916,8 +924,11 @@ OrderedCollectionDelete (
)
{
RED_BLACK_TREE_NODE *NewRoot;
- RED_BLACK_TREE_NODE *OrigLeftChild, *OrigRightChild, *OrigParent;
- RED_BLACK_TREE_NODE *Child, *Parent;
+ 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;
@@ -1024,7 +1035,7 @@ OrderedCollectionDelete (
// C <--- ToRelink
//
Parent->Left = Child;
- if (Child) {
+ if (Child != NULL) {
Child->Parent = Parent;
}
@@ -1124,7 +1135,9 @@ OrderedCollectionDelete (
// Rotations in the loop preserve property #4.
//
while (Child != NewRoot && NodeIsNullOrBlack (Child)) {
- RED_BLACK_TREE_NODE *Sibling, *LeftNephew, *RightNephew;
+ RED_BLACK_TREE_NODE *Sibling;
+ RED_BLACK_TREE_NODE *LeftNephew;
+ RED_BLACK_TREE_NODE *RightNephew;
if (Child == Parent->Left) {
Sibling = Parent->Right;
@@ -1337,13 +1350,13 @@ OrderedCollectionDelete (
@retval The black-height of Node's parent.
**/
-STATIC
UINT32
RedBlackTreeRecursiveCheck (
IN CONST RED_BLACK_TREE_NODE *Node
)
{
- UINT32 LeftHeight, RightHeight;
+ UINT32 LeftHeight;
+ UINT32 RightHeight;
//
// property #2
@@ -1387,15 +1400,16 @@ RedBlackTreeRecursiveCheck (
@param[in] Tree The tree to validate.
**/
-STATIC
VOID
RedBlackTreeValidate (
IN CONST RED_BLACK_TREE *Tree
)
{
UINT32 BlackHeight;
- UINT32 ForwardCount, BackwardCount;
- CONST RED_BLACK_TREE_NODE *Last, *Node;
+ 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));