[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.
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=24... ============================================================================== --- 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=24... ============================================================================== --- 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=2... ============================================================================== --- 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=... ============================================================================== --- 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;
-
arty＠svn.reactos.org