[tkreuzer] 56249: [RTL] Add some temp AVL debugging code: In case an AVL table gets unbalanced, dump the table and a backtrace.

Author: tkreuzer
Date: Tue Mar 27 17:19:53 2012
New Revision: 56249

URL: http://svn.reactos.org/svn/reactos?rev=56249&view=rev
Log:
[RTL]
Add some temp AVL debugging code: In case an AVL table gets unbalanced, dump the table and a backtrace.

Modified:
    trunk/reactos/lib/rtl/avlsupp.c

Modified: trunk/reactos/lib/rtl/avlsupp.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/avlsupp.c?rev=56249...
==============================================================================
--- trunk/reactos/lib/rtl/avlsupp.c [iso-8859-1] (original)
+++ trunk/reactos/lib/rtl/avlsupp.c [iso-8859-1] Tue Mar 27 17:19:53 2012
@@ -140,7 +140,7 @@
     {
         /* This performs the rotation described in Knuth A8-A10 for Case 1 */
         RtlPromoteAvlTreeNode(ChildNode);
-        
+
         /* The nodes are now balanced */
         RtlSetBalance(ChildNode, RtlBalancedAvlTree);
         RtlSetBalance(Node, RtlBalancedAvlTree);
@@ -189,19 +189,59 @@
         RtlSetBalance(SubChildNode, RtlBalancedAvlTree);
         return FALSE;
     }
-    
+
     /*
      * 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);
-    
+
     /* Now the child has the opposite weight of the node */
     RtlSetBalance(ChildNode, -Balance);
-    
+
     /* This only happens on deletion, so we return TRUE to terminate the delete */
     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
@@ -211,7 +251,7 @@
                       IN OUT TABLE_SEARCH_RESULT SearchResult)
 {
     CHAR Balance;
-    
+
     /* Initialize the new inserted element */
     MI_ASSERT(SearchResult != TableFoundNode);
     NewNode->LeftChild = NewNode->RightChild = NULL;
@@ -225,8 +265,15 @@
         /* 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");
-        
+        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);
         Table->DepthOfTree = 1;
@@ -245,7 +292,14 @@

/* 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");
+    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);

/*
@@ -258,13 +312,13 @@
     {
         /* Calculate which side to balance on */
         Balance = RtlIsLeftChildAvl(NewNode) ? RtlLeftHeavyAvlTree : RtlRightHeavyAvlTree;
-        
+
         /* Check if the parent node was balanced */
         if (RtlBalance(NodeOrParent) == RtlBalancedAvlTree)
         {
             /* It's not balanced anymore (heavy on one side) */
             RtlSetBalance(NodeOrParent, Balance);
-            
+
             /* Move up */
             NewNode = NodeOrParent;
             NodeOrParent = RtlParentAvl(NodeOrParent);
@@ -273,14 +327,14 @@
         {
             /* The parent's balance is opposite, so the tree is balanced now */
             RtlSetBalance(NodeOrParent, RtlBalancedAvlTree);
-            
+
             /* Check if this is the root (the cheat applied earlier gets us here) */
             if (RtlBalance(&Table->BalancedRoot) == RtlBalancedAvlTree)
             {
                 /* The depth has thus increased */
                 Table->DepthOfTree++;
             }
-            
+
             /* We reached the root or a balanced node, so we're done */
             break;
         }
@@ -301,10 +355,10 @@
     PRTL_BALANCED_LINKS DeleteNode = NULL, ParentNode;
     PRTL_BALANCED_LINKS *Node1, *Node2;
     CHAR Balance;
-    
+
     /* Take one of the children if possible */
     if (!(RtlLeftChildAvl(Node)) || !(RtlRightChildAvl(Node))) DeleteNode = Node;
-    
+
     /* Otherwise, check if one side is longer */
     if (!(DeleteNode) && (RtlBalance(Node) >= RtlBalancedAvlTree))
     {
@@ -316,34 +370,34 @@
     {
         /* Pick the predecessor which will be the longest side in this case */
         DeleteNode = RtlLeftChildAvl(Node);
-        while (RtlRightChildAvl(DeleteNode)) DeleteNode = RtlRightChildAvl(DeleteNode);        
-    }
-    
+        while (RtlRightChildAvl(DeleteNode)) DeleteNode = RtlRightChildAvl(DeleteNode);
+    }
+
     /* Get the parent node */
     ParentNode = RtlParentAvl(DeleteNode);
     DPRINT("Parent: %p\n", ParentNode);
-    
+
     /* Pick which now to use based on whether or not we have a left child */
     Node1 = RtlLeftChildAvl(DeleteNode) ? &DeleteNode->LeftChild : &DeleteNode->RightChild;
     DPRINT("Node 1: %p %p\n", Node1, *Node1);
-            
+
     /* Pick which node to swap based on if we're already a left child or not */
     Node2 = RtlIsLeftChildAvl(DeleteNode) ? &ParentNode->LeftChild : &ParentNode->RightChild;
     DPRINT("Node 2: %p %p\n", Node2, *Node2);
-            
+
     /* Pick the correct balance depending on which side will get heavier */
     Balance = RtlIsLeftChildAvl(DeleteNode) ? RtlLeftHeavyAvlTree : RtlRightHeavyAvlTree;
     DPRINT("Balance: %lx\n", Balance);
-    
+
     /* Swap the children nodes, making one side heavier */
     *Node2 = *Node1;
-    
+
     /* If the node has a child now, update its parent */
     if (*Node1) RtlSetParent(*Node1, ParentNode);

/* Assume balanced root for loop optimization */
     RtlSetBalance(&Table->BalancedRoot, RtlBalancedAvlTree);
-    
+
     /* Loop up the tree by parents */
     while (TRUE)
     {
@@ -374,7 +428,7 @@
         /* Choose which balance factor to use based on which side we're on */
         Balance = RtlIsRightChild(ParentNode) ?
                   RtlRightHeavyAvlTree : RtlLeftHeavyAvlTree;
-        
+
         /* Iterate up the tree */
         ParentNode = RtlParentAvl(ParentNode);
     }
@@ -384,7 +438,7 @@

/* Copy the deleted node itself */
     RtlpCopyAvlNodeData(DeleteNode, Node);
-    
+
     /* Pick the right node to unlink */
     Node1 = RtlIsLeftChildAvl(Node) ?
             &(RtlParentAvl(DeleteNode))->LeftChild : &(RtlParentAvl(DeleteNode))->RightChild;