[arty] 39899: Fix remaining issues in this neglected imported code. It's my fault it was in a poor state for so long.

Author: arty
Date: Sat Mar  7 03:18:06 2009
New Revision: 39899

URL: http://svn.reactos.org/svn/reactos?rev=39899&view=rev
Log:
Fix remaining issues in this neglected imported code.  It's my fault it was
in a poor state for so long.

Modified:
    trunk/reactos/lib/rtl/austin/avl.c

Modified: trunk/reactos/lib/rtl/austin/avl.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/austin/avl.c?rev=39...
==============================================================================
--- trunk/reactos/lib/rtl/austin/avl.c [iso-8859-1] (original)
+++ trunk/reactos/lib/rtl/austin/avl.c [iso-8859-1] Sat Mar  7 03:18:06 2009
@@ -34,9 +34,9 @@
 #define LESS GenericLessThan
 #define GREATER GenericGreaterThan

-void print_node(udict_t *ud, udict_node_t *node, int indent)
-{
-	int i;
+int print_node(udict_t *ud, udict_node_t *node, int indent)
+{
+	int i, rh = 0, lh = 0;
    char buf[100];
    udict_node_t *nil = ud->BalancedRoot.Parent;

@@ -44,19 +44,49 @@
    if( node == ud->BalancedRoot.Parent ) {
    	sprintf(buf+i, "Nil\n");
    	DbgPrint("%s", buf);
+		return 0;
    } else {
    	sprintf(buf+i, "Node %p (parent %p: balance %d)\n", node, node->parent, node->Balance);
    	DbgPrint("%s", buf);
    	if( node->LeftChild != nil ) {
    		sprintf(buf+i, "--> Left\n");
    		DbgPrint("%s", buf);
-			print_node(ud, node->LeftChild, indent+1);
+			lh = print_node(ud, node->LeftChild, indent+1);
    	}
    	if( node->RightChild != nil ) {
    		sprintf(buf+i, "--> Right\n");
    		DbgPrint("%s", buf);
-			print_node(ud, node->RightChild, indent+1);
+			rh = print_node(ud, node->RightChild, indent+1);
    	}
+		if (indent)
+		{
+			if (rh < lh - 1 || lh < rh - 1)
+			{
+				sprintf(buf+i, "warning: tree is too unbalanced %d vs %d\n",
+						lh, rh);
+				DbgPrint("%s", buf);
+			}
+			if (rh != lh && node->Balance == BALANCED)
+			{
+				sprintf(buf+i, "warning: tree says balanced, but %d vs %d\n", 
+						lh, rh);
+				DbgPrint("%s", buf);
+			}
+			else if (lh <= rh && node->Balance == LEFTHEAVY)
+			{
+				sprintf(buf+i, "warning: tree says leftheavy but %d vs %d\n",
+						lh, rh);
+				DbgPrint("%s", buf);
+			}
+			else if (lh >= rh && node->Balance == RIGHTHEAVY)
+			{
+				sprintf(buf+i, "warning: tree says rightheavy but %d vs %d\n",
+						lh, rh);
+				DbgPrint("%s", buf);
+			}
+		}
+		if (rh > lh) return 1+rh;
+		else return 1+lh;
    }
 }

@@ -248,8 +278,6 @@
    	ud->BalancedRoot.balance = LEFTHEAVY;
    }

-	print_tree(ud);
-
    ud->nodecount++;
 }

@@ -306,7 +334,7 @@
    	}/*if*/
    }/*if*/

-	while (parent != nil) {
+	while (parent != &ud->BalancedRoot) {
    	if ((parent->left == nil) && (parent->right == nil)) {
    		assert (child == nil);
    		parent->balance = BALANCED;