[RTL/NTOSKRNL]

[reactos.git] / reactos / lib / rtl / avlsupp.c

diff --git a/reactos/lib/rtl/avlsupp.c b/reactos/lib/rtl/avlsupp.c
index 1db1da8..ff89bc1 100644 (file)
--- a/reactos/lib/rtl/avlsupp.c
+++ b/reactos/lib/rtl/avlsupp.c
@@ -27,8 +27,8 @@ C_ASSERT(RtlBalancedAvlTree == 0);
 
 /* FUNCTIONS ******************************************************************/
 
-TABLE_SEARCH_RESULT
 FORCEINLINE
+TABLE_SEARCH_RESULT
 RtlpFindAvlTableNodeOrParent(IN PRTL_AVL_TABLE Table,
                              IN PVOID Buffer,
                              OUT PRTL_BALANCED_LINKS *NodeOrParent)
@@ -94,9 +94,9 @@ RtlpFindAvlTableNodeOrParent(IN PRTL_AVL_TABLE Table,
     }
 }
 
-VOID
 FORCEINLINE
-RtlPromoteAvlTreeNode(IN PRTL_BALANCED_LINKS Node)
+VOID
+RtlpPromoteAvlTreeNode(IN PRTL_BALANCED_LINKS Node)
 {
     PRTL_BALANCED_LINKS ParentNode, SuperParentNode;
     PRTL_BALANCED_LINKS *SwapNode1, *SwapNode2;
@@ -122,8 +122,8 @@ RtlPromoteAvlTreeNode(IN PRTL_BALANCED_LINKS Node)
     RtlSetParent(Node, SuperParentNode);
 }
 
-BOOLEAN
 FORCEINLINE
+BOOLEAN
 RtlpRebalanceAvlTreeNode(IN PRTL_BALANCED_LINKS Node)
 {
     PRTL_BALANCED_LINKS ChildNode, SubChildNode;
@@ -139,7 +139,7 @@ RtlpRebalanceAvlTreeNode(IN PRTL_BALANCED_LINKS Node)
     if (RtlBalance(ChildNode) == Balance)
     {
         /* This performs the rotation described in Knuth A8-A10 for Case 1 */
-        RtlPromoteAvlTreeNode(ChildNode);
+        RtlpPromoteAvlTreeNode(ChildNode);
 
         /* The nodes are now balanced */
         RtlSetBalance(ChildNode, RtlBalancedAvlTree);
@@ -155,8 +155,8 @@ RtlpRebalanceAvlTreeNode(IN PRTL_BALANCED_LINKS Node)
                         RtlLeftChildAvl(ChildNode) : RtlRightChildAvl(ChildNode);
 
         /* Do the double-rotation described in Knuth A8-A10 for Case 2 */
-        RtlPromoteAvlTreeNode(SubChildNode);
-        RtlPromoteAvlTreeNode(SubChildNode);
+        RtlpPromoteAvlTreeNode(SubChildNode);
+        RtlpPromoteAvlTreeNode(SubChildNode);
 
         /* Was the sub-child sharing the same balance as the node? */
         if (RtlBalance(SubChildNode) == Balance)
@@ -194,7 +194,7 @@ RtlpRebalanceAvlTreeNode(IN PRTL_BALANCED_LINKS Node)
      * The case that remains is that the child was already balanced, so this is
      * This is the rotation required for Case 3 in Knuth A8-A10
      */
-    RtlPromoteAvlTreeNode(ChildNode);
+    RtlpPromoteAvlTreeNode(ChildNode);
 
     /* Now the child has the opposite weight of the node */
     RtlSetBalance(ChildNode, -Balance);
@@ -203,48 +203,8 @@ RtlpRebalanceAvlTreeNode(IN PRTL_BALANCED_LINKS Node)
     return TRUE;
 }
 
-void
 FORCEINLINE
-Indent(ULONG Level)
-{
-    while (Level--)
-    {
-        DbgPrint("  ");
-    }
-}
-
 VOID
-FORCEINLINE
-DbgDumpAvlNodes(
-    PRTL_BALANCED_LINKS Node,
-    ULONG Level)
-{
-#ifdef PRTL_BALANCED_LINKS
-    if (Level == 0)
-    {
-        DbgPrint("++++++++++++++++++++++++++++++++++++++++++++++++++++++\n");
-        DbgPrint("Root = %p\n", Node);
-    }
-
-    Indent(Level+1); DbgPrint("LetChid = %p", Node->LeftChild);
-    if (Node->LeftChild)
-    {
-        DbgPrint("(%lx, %lx)\n", Node->LeftChild->StartingVpn,Node->LeftChild->EndingVpn);
-        DbgDumpAvlNodes(Node->LeftChild, Level+1);
-    }
-    else DbgPrint("\n");
-    Indent(Level+1); DbgPrint("RightChild = %p\n", Node->RightChild);
-    if (Node->RightChild)
-    {
-        DbgPrint("(%lx, %lx)\n", Node->RightChild->StartingVpn,Node->RightChild->EndingVpn);
-        DbgDumpAvlNodes(Node->RightChild, Level+1);
-    }
-#endif
-}
-
-
-VOID
-FORCEINLINE
 RtlpInsertAvlTreeNode(IN PRTL_AVL_TABLE Table,
                       IN PRTL_BALANCED_LINKS NewNode,
                       IN OUT PVOID NodeOrParent,
@@ -255,6 +215,7 @@ RtlpInsertAvlTreeNode(IN PRTL_AVL_TABLE Table,
     /* Initialize the new inserted element */
     MI_ASSERT(SearchResult != TableFoundNode);
     NewNode->LeftChild = NewNode->RightChild = NULL;
+    RtlSetBalance(NewNode, RtlBalancedAvlTree);
 
     /* Increase element count */
     Table->NumberGenericTableElements++;
@@ -264,15 +225,6 @@ RtlpInsertAvlTreeNode(IN PRTL_AVL_TABLE Table,
     {
         /* This is the new root node */
         RtlInsertAsRightChildAvl(&Table->BalancedRoot, NewNode);
-        //MI_ASSERT(RtlBalance(NewNode) == RtlBalancedAvlTree);
-        if (RtlBalance(NewNode) != RtlBalancedAvlTree)
-        {
-            DPRINT1("Warning: Root node unbalanced?\n");
-            DbgDumpAvlNodes(&Table->BalancedRoot, 0);
-#ifdef PRTL_BALANCED_LINKS
-            KeRosDumpStackFrames(NULL, 0);
-#endif
-        }
 
         /* On AVL trees, we also update the depth */
         ASSERT(Table->DepthOfTree == 0);
@@ -291,15 +243,6 @@ RtlpInsertAvlTreeNode(IN PRTL_AVL_TABLE Table,
     }
 
     /* Little cheat to save on loop processing, taken from Timo */
-    //MI_ASSERT(RtlBalance(NewNode) == RtlBalancedAvlTree);
-    if (RtlBalance(NewNode) != RtlBalancedAvlTree)
-    {
-        DPRINT1("Warning: Root node unbalanced?\n");
-        DbgDumpAvlNodes(&Table->BalancedRoot, 0);
-#ifdef PRTL_BALANCED_LINKS
-        KeRosDumpStackFrames(NULL, 0);
-#endif
-    }
     RtlSetBalance(&Table->BalancedRoot, RtlLeftHeavyAvlTree);
 
     /*
@@ -347,8 +290,8 @@ RtlpInsertAvlTreeNode(IN PRTL_AVL_TABLE Table,
     }
 }
 
-VOID
 FORCEINLINE
+VOID
 RtlpDeleteAvlTreeNode(IN PRTL_AVL_TABLE Table,
                       IN PRTL_BALANCED_LINKS Node)
 {