MdePkg/UefiDebugLibDebugPortProtocol: Make it runtime safe

[mirror_edk2.git] / MdePkg / Library / BaseOrderedCollectionRedBlackTreeLib / BaseOrderedCollectionRedBlackTreeLib.c

diff --git a/MdePkg/Library/BaseOrderedCollectionRedBlackTreeLib/BaseOrderedCollectionRedBlackTreeLib.c b/MdePkg/Library/BaseOrderedCollectionRedBlackTreeLib/BaseOrderedCollectionRedBlackTreeLib.c
index 9f40b70ff5516674d8df82d92598dc6e9f0b11d4..650a761480287d30edddcb50a5c399da892568de 100644 (file)
--- a/MdePkg/Library/BaseOrderedCollectionRedBlackTreeLib/BaseOrderedCollectionRedBlackTreeLib.c
+++ b/MdePkg/Library/BaseOrderedCollectionRedBlackTreeLib/BaseOrderedCollectionRedBlackTreeLib.c
@@ -11,14 +11,9 @@
   The implementation is also useful as a fast priority queue.\r
 \r
   Copyright (C) 2014, Red Hat, Inc.\r
+  Copyright (c) 2014, Intel Corporation. All rights reserved.<BR>\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
+  SPDX-License-Identifier: BSD-2-Clause-Patent\r
 **/\r
 \r
 #include <Library/OrderedCollectionLib.h>\r
@@ -75,12 +70,17 @@ OrderedCollectionUserStruct (
   return Node->UserStruct;\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
-//\r
-// Forward declaration of internal, unit test helper function. See\r
-// specification and function definition later.\r
-//\r
-STATIC\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
 VOID\r
 RedBlackTreeValidate (\r
   IN CONST RED_BLACK_TREE *Tree\r
@@ -148,7 +148,7 @@ OrderedCollectionIsEmpty (
   IN CONST RED_BLACK_TREE *Tree\r
   )\r
 {\r
-  return Tree->Root == NULL;\r
+  return (BOOLEAN)(Tree->Root == NULL);\r
 }\r
 \r
 \r
@@ -417,14 +417,15 @@ OrderedCollectionPrev (
                           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
+  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
@@ -481,14 +482,15 @@ RedBlackTreeRotateRight (
                           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
+  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
@@ -582,7 +584,8 @@ OrderedCollectionInsert (
   IN     VOID                *UserStruct\r
   )\r
 {\r
-  RED_BLACK_TREE_NODE *Tmp, *Parent;\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
@@ -671,7 +674,8 @@ OrderedCollectionInsert (
 \r
   NewRoot = Tree->Root;\r
   while (Tmp != NewRoot && Parent->Color == RedBlackTreeRed) {\r
-    RED_BLACK_TREE_NODE *GrandParent, *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
@@ -831,14 +835,12 @@ Done:
 \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
+  return (BOOLEAN)(Node == NULL || Node->Color == RedBlackTreeBlack);\r
 }\r
 \r
 \r
@@ -916,8 +918,11 @@ OrderedCollectionDelete (
   )\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_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
@@ -1024,7 +1029,7 @@ OrderedCollectionDelete (
       //                                 C <--- ToRelink\r
       //\r
       Parent->Left = Child;\r
-      if (Child) {\r
+      if (Child != NULL) {\r
         Child->Parent = Parent;\r
       }\r
 \r
@@ -1124,7 +1129,9 @@ OrderedCollectionDelete (
     // Rotations in the loop preserve property #4.\r
     //\r
     while (Child != NewRoot && NodeIsNullOrBlack (Child)) {\r
-      RED_BLACK_TREE_NODE *Sibling, *LeftNephew, *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
@@ -1337,13 +1344,13 @@ OrderedCollectionDelete (
 \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
+  UINT32 LeftHeight;\r
+  UINT32 RightHeight;\r
 \r
   //\r
   // property #2\r
@@ -1387,15 +1394,16 @@ RedBlackTreeRecursiveCheck (
 \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
+  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