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

[arty at svn.reactos.org]

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=39899&r1=39898&r2=39899&view=diff
==============================================================================
--- 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;