[ros-diffs] [arty] 24510: Fixed avl tree completely. - We can't use the builtin node as a sentinel in exactly the same way as used in the austin lib, so we account for that by treating the builtin node like nil a few places.
arty at svn.reactos.org
arty at svn.reactos.org
Sat Oct 14 19:29:42 CEST 2006
Author: arty
Date: Sat Oct 14 21:29:41 2006
New Revision: 24510
URL: http://svn.reactos.org/svn/reactos?rev=24510&view=rev
Log:
Fixed avl tree completely.
- We can't use the builtin node as a sentinel in exactly the same way as used
in the austin lib, so we account for that by treating the builtin node like
nil a few places.
Modified:
trunk/reactos/lib/rtl/austin/avl.c
trunk/reactos/lib/rtl/austin/avl.h
trunk/reactos/lib/rtl/austin/tree.c
trunk/reactos/lib/rtl/generictable.c
Modified: trunk/reactos/lib/rtl/austin/avl.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/austin/avl.c?rev=24510&r1=24509&r2=24510&view=diff
==============================================================================
--- trunk/reactos/lib/rtl/austin/avl.c (original)
+++ trunk/reactos/lib/rtl/austin/avl.c Sat Oct 14 21:29:41 2006
@@ -34,6 +34,38 @@
#define LESS GenericLessThan
#define GREATER GenericGreaterThan
+void print_node(udict_t *ud, udict_node_t *node, int indent)
+{
+ int i;
+ char buf[100];
+ udict_node_t *nil = ud->BalancedRoot.Parent;
+
+ for( i = 0; i < indent; i++ ) buf[i] = ' ';
+ if( node == ud->BalancedRoot.Parent ) {
+ sprintf(buf+i, "Nil\n");
+ DbgPrint("%s", buf);
+ } else {
+ sprintf(buf+i, "Node %x (parent %x: balance %d)\n", (int)node, (int)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);
+ }
+ if( node->RightChild != nil ) {
+ sprintf(buf+i, "--> Right\n");
+ DbgPrint("%s", buf);
+ print_node(ud, node->RightChild, indent+1);
+ }
+ }
+}
+
+void print_tree(udict_t *ud)
+{
+ DbgPrint("TREE %x (Nil %x)\n", ud, ud->BalancedRoot.Parent);
+ print_node(ud, &ud->BalancedRoot, 0);
+}
+
void avl_init(udict_t *ud)
{
ud->BalancedRoot.left = ud->BalancedRoot.right =
@@ -43,7 +75,12 @@
ud->BalancedRoot.parent->parent = ud->BalancedRoot.parent;
}
-void RotateLeft(udict_node_t **top)
+void avl_deinit(udict_t *ud)
+{
+ ud->FreeRoutine(ud, ud->BalancedRoot.parent);
+}
+
+static void RotateLeft(udict_node_t **top)
{
udict_node_t *parent = *top;
udict_node_t *child = parent->right;
@@ -56,7 +93,7 @@
*top = child;
}/*RotateLeft*/
-void RotateRight(udict_node_t **top)
+static void RotateRight(udict_node_t **top)
{
udict_node_t *parent = *top;
udict_node_t *child = parent->left;
@@ -69,7 +106,7 @@
*top = child;
}/*RotateRight*/
-void FixBalance(udict_node_t **pnode, udict_avl_balance_t bal)
+static void FixBalance(udict_node_t **pnode, udict_avl_balance_t bal)
{
udict_node_t *node = *pnode;
udict_node_t *child;
@@ -157,7 +194,7 @@
}/*else*/
}/*FixBalance*/
-int Insert(udict_t *ud, udict_node_t *what, udict_node_t **where, udict_node_t *parent)
+static int Insert(udict_t *ud, udict_node_t *what, udict_node_t **where, udict_node_t *parent)
{
udict_node_t *here = *where;
int result;
@@ -169,6 +206,8 @@
}/*if*/
else {
result = ud->compare(ud, key(what), key(here));
+
+ assert (result != GenericEqual);
if (result == LESS) {
if (Insert(ud, what, &here->left, here)) {
@@ -204,6 +243,13 @@
nil->balance = LEFTHEAVY;
}/*if*/
+ if (ud->BalancedRoot.left == node) {
+ node->parent = &ud->BalancedRoot;
+ ud->BalancedRoot.balance = LEFTHEAVY;
+ }
+
+ print_tree(ud);
+
ud->nodecount++;
}
@@ -263,7 +309,6 @@
while (parent != nil) {
if ((parent->left == nil) && (parent->right == nil)) {
assert (child == nil);
- assert (parent->balance != BALANCED);
parent->balance = BALANCED;
/* propagate height reduction to upper level */
}/*if*/
@@ -299,7 +344,7 @@
else
break;
}/*while*/
-}/*avl_delete*/
+}/*avl_delete_node*/
void *avl_get_data(udict_node_t *here) {
return data(here);
@@ -337,7 +382,8 @@
int avl_is_nil(udict_t *ud, udict_node_t *node)
{
- return tree_null_priv(ud) == node;
+ return tree_null_priv(ud) == node ||
+ &ud->BalancedRoot == node;
}
udict_node_t *avl_first(udict_t *ud)
@@ -352,5 +398,9 @@
udict_node_t *avl_next(udict_t *ud, udict_node_t *prev)
{
- return udict_tree_next(ud, prev);
-}
+ udict_node_t *node = udict_tree_next(ud, prev);
+ if( node == tree_null_priv(ud) || node == &ud->BalancedRoot )
+ return NULL;
+ else
+ return node;
+}
Modified: trunk/reactos/lib/rtl/austin/avl.h
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/austin/avl.h?rev=24510&r1=24509&r2=24510&view=diff
==============================================================================
--- trunk/reactos/lib/rtl/austin/avl.h (original)
+++ trunk/reactos/lib/rtl/austin/avl.h Sat Oct 14 21:29:41 2006
@@ -12,6 +12,7 @@
#define avl_data(x) ((void*)(&(x)[1]))
void avl_init(PRTL_AVL_TABLE table);
+void avl_deinit(PRTL_AVL_TABLE table);
void avl_insert_node(PRTL_AVL_TABLE table, PRTL_BALANCED_LINKS node);
void avl_delete_node(PRTL_AVL_TABLE table, PRTL_BALANCED_LINKS node);
int avl_is_nil(PRTL_AVL_TABLE table, PRTL_BALANCED_LINKS node);
Modified: trunk/reactos/lib/rtl/austin/tree.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/austin/tree.c?rev=24510&r1=24509&r2=24510&view=diff
==============================================================================
--- trunk/reactos/lib/rtl/austin/tree.c (original)
+++ trunk/reactos/lib/rtl/austin/tree.c Sat Oct 14 21:29:41 2006
@@ -30,9 +30,15 @@
udict_node_t *nil = tree_null_priv(ud), *child, *delparent = node->parent;
udict_node_t *next = node, *nextparent;
+ if( tree_root_priv(ud) == node )
+ delparent = &ud->BalancedRoot;
+
if (node->left != nil && node->right != nil) {
next = udict_tree_next(ud, node);
nextparent = next->parent;
+
+ if( tree_root_priv(ud) == next )
+ nextparent = &ud->BalancedRoot;
assert (next != nil);
assert (next->parent != nil);
@@ -76,20 +82,19 @@
assert (node->left == nil || node->right == nil);
child = (node->left != nil) ? node->left : node->right;
-
child->parent = delparent = node->parent;
if (node == delparent->left) {
delparent->left = child;
} else {
- //assert (node == delparent->right);
+ assert (node == delparent->right);
delparent->right = child;
}
}
- node->parent = 0;
- node->right = 0;
- node->left = 0;
+ node->parent = nil;
+ node->right = nil;
+ node->left = nil;
ud->nodecount--;
Modified: trunk/reactos/lib/rtl/generictable.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/generictable.c?rev=24510&r1=24509&r2=24510&view=diff
==============================================================================
--- trunk/reactos/lib/rtl/generictable.c (original)
+++ trunk/reactos/lib/rtl/generictable.c Sat Oct 14 21:29:41 2006
@@ -132,6 +132,8 @@
{
avl_delete_node(Table, Node);
Table->FreeRoutine(Table, Node);
+ if( Table->NumberGenericTableElements == 0 )
+ avl_deinit(Table);
return TRUE;
}
else
@@ -303,7 +305,6 @@
Table->AllocateRoutine = AllocateRoutine;
Table->FreeRoutine = FreeRoutine;
Table->TableContext = TableContext;
- avl_init(Table);
}
@@ -358,6 +359,10 @@
PRTL_BALANCED_LINKS OurNodeOrParent;
TABLE_SEARCH_RESULT OurSearchResult;
+ if(Table->NumberGenericTableElements == 0) {
+ avl_init(Table);
+ }
+
if(NewElement)
*NewElement = FALSE;
More information about the Ros-diffs
mailing list