[arty] 24495: Fixen. Delete is still broken. We now use BalancedRoot->Parent as the nil element and distinguish it from the embedded element. Fix null and root macros, assert macro and some other stuff.
Author: arty Date: Fri Oct 13 11:02:04 2006 New Revision: 24495
URL: http://svn.reactos.org/svn/reactos?rev=24495&view=rev Log: Fixen. Delete is still broken. We now use BalancedRoot->Parent as the nil element and distinguish it from the embedded element. Fix null and root macros, assert macro and some other stuff.
Modified: trunk/reactos/lib/rtl/austin/avl.c trunk/reactos/lib/rtl/austin/macros.h trunk/reactos/lib/rtl/austin/tree.c trunk/reactos/lib/rtl/austin/tree.h trunk/reactos/lib/rtl/austin/udict.h 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 Fri Oct 13 11:02:04 2006 @@ -36,8 +36,11 @@
void avl_init(udict_t *ud) { - ud->sentinel.left = ud->sentinel.right = ud->sentinel.parent = - &ud->sentinel; + ud->BalancedRoot.left = ud->BalancedRoot.right = + ud->BalancedRoot.parent = (udict_node_t*) + ud->AllocateRoutine(ud, sizeof(udict_node_t)); + ud->BalancedRoot.parent->left = ud->BalancedRoot.parent->right = + ud->BalancedRoot.parent->parent = ud->BalancedRoot.parent; }
void RotateLeft(udict_node_t **top) @@ -197,7 +200,7 @@ node->right = nil; node->balance = BALANCED;
- if (Insert(ud, node, &nil->left, nil)) { + if (Insert(ud, node, &ud->BalancedRoot.left, nil)) { nil->balance = LEFTHEAVY; }/*if*/
@@ -253,6 +256,7 @@ /* root has been deleted */ if (child == nil) { parent->balance = BALANCED; + ud->BalancedRoot.left = nil; }/*if*/ }/*if*/
@@ -297,9 +301,16 @@ }/*while*/ }/*avl_delete*/
+void *avl_get_data(udict_node_t *here) { + return data(here); +} + int avl_search(udict_t *ud, void *_key, udict_node_t *here, udict_node_t **where) { int result; + + if (avl_is_nil(ud, here)) + return TableInsertAsLeft;
result = ud->compare(ud, _key, key(here));
@@ -309,14 +320,14 @@ }
if (result == LESS) { - if( here->left == &ud->sentinel ) { + if( here->left == tree_null_priv(ud) ) { *where = here; return TableInsertAsLeft; } return avl_search(ud, _key, here->left, where); }/*if*/ else { - if( here->right == &ud->sentinel ) { + if( here->right == tree_null_priv(ud) ) { *where = here; return TableInsertAsRight; } @@ -326,7 +337,7 @@
int avl_is_nil(udict_t *ud, udict_node_t *node) { - return &ud->sentinel == node; + return tree_null_priv(ud) == node; }
udict_node_t *avl_first(udict_t *ud)
Modified: trunk/reactos/lib/rtl/austin/macros.h URL: http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/austin/macros.h?rev... ============================================================================== --- trunk/reactos/lib/rtl/austin/macros.h (original) +++ trunk/reactos/lib/rtl/austin/macros.h Fri Oct 13 11:02:04 2006 @@ -47,5 +47,5 @@ #define nodefree FreeRoutine #define context TableContext
-#define assert(x) { if(x) { RtlAssert(#x, __FILE__, __LINE__, NULL); } } +#define assert(x) { if(!(x)) { RtlAssert(#x, __FILE__, __LINE__, NULL); } }
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 Fri Oct 13 11:02:04 2006 @@ -82,7 +82,7 @@ if (node == delparent->left) { delparent->left = child; } else { - assert (node == delparent->right); + //assert (node == delparent->right); delparent->right = child; } }
Modified: trunk/reactos/lib/rtl/austin/tree.h URL: http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/austin/tree.h?rev=2... ============================================================================== --- trunk/reactos/lib/rtl/austin/tree.h (original) +++ trunk/reactos/lib/rtl/austin/tree.h Fri Oct 13 11:02:04 2006 @@ -36,6 +36,6 @@ void udict_tree_rotate_left(udict_node_t *, udict_node_t *); void udict_tree_rotate_right(udict_node_t *, udict_node_t *);
-#define tree_root_priv(T) ((T)->sentinel.left) -#define tree_null_priv(L) (&(L)->sentinel) +#define tree_root_priv(T) ((T)->BalancedRoot.left) +#define tree_null_priv(L) ((L)->BalancedRoot.parent) #define TREE_DEPTH_MAX 64
Modified: trunk/reactos/lib/rtl/austin/udict.h URL: http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/austin/udict.h?rev=... ============================================================================== --- trunk/reactos/lib/rtl/austin/udict.h (original) +++ trunk/reactos/lib/rtl/austin/udict.h Fri Oct 13 11:02:04 2006 @@ -56,9 +56,9 @@ } udict_rb_color_t;
typedef enum { - udict_balanced, - udict_leftheavy, - udict_rightheavy + udict_balanced = 0, + udict_leftheavy = -1, + udict_rightheavy = 1 } udict_avl_balance_t;
typedef union {
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 Fri Oct 13 11:02:04 2006 @@ -60,7 +60,7 @@ PRTL_BALANCED_LINKS OurNodeOrParent; TABLE_SEARCH_RESULT OurSearchResult;
- if( Table->NumberGenericTableElements ) + if( !Table->NumberGenericTableElements ) { *SearchResult = TableEmptyTree; *NodeOrParent = NULL; @@ -68,7 +68,8 @@ }
OurSearchResult = avl_search - (Table, Buffer, &Table->BalancedRoot, &OurNodeOrParent); + (Table, Buffer, + Table->BalancedRoot.LeftChild, &OurNodeOrParent);
if(SearchResult) *SearchResult = OurSearchResult; if(NodeOrParent) *NodeOrParent = OurNodeOrParent; @@ -129,7 +130,7 @@
if( Result == TableFoundNode ) { - avl_delete_node(Table, Buffer); + avl_delete_node(Table, Node); Table->FreeRoutine(Table, Node); return TRUE; } @@ -169,18 +170,15 @@ if( Restart ) { Table->RestartKey = avl_first(Table); + } + else + { + Table->RestartKey = avl_next(Table, Table->RestartKey); + } + if( !Table->RestartKey ) + return NULL; + else return avl_data(Table->RestartKey); - } - else - { - Table->RestartKey = avl_next(Table, Table->RestartKey); - if( avl_is_nil(Table, Table->RestartKey) ) - return NULL; - else - return avl_data(Table->RestartKey); - } - - return 0; }
/* @@ -363,25 +361,19 @@ if(NewElement) *NewElement = FALSE;
- if( Table->NumberGenericTableElements ) - { - OurSearchResult = TableEmptyTree; - OurNodeOrParent = NULL; - return NULL; - } - OurSearchResult = avl_search - (Table, Buffer, &Table->BalancedRoot, &OurNodeOrParent); + (Table, Buffer, + Table->BalancedRoot.LeftChild, &OurNodeOrParent);
if(NodeOrParent) *NodeOrParent = OurNodeOrParent; if(SearchResult) *SearchResult = OurSearchResult;
if(OurSearchResult == TableFoundNode) { - if(NewElement) - *NewElement = TRUE; - RtlCopyMemory(avl_data(OurNodeOrParent), Buffer, BufferSize); - return avl_data(OurNodeOrParent); + RtlDeleteElementGenericTableAvl(Table, Buffer); + return RtlInsertElementGenericTableFullAvl + (Table, Buffer, BufferSize, + NewElement, NodeOrParent, SearchResult); } else { @@ -392,6 +384,7 @@
if( !NewNode ) return NULL;
+ NewNode->Balance = 0; RtlCopyMemory(avl_data(NewNode), Buffer, BufferSize);
OurNodeOrParent = NewNode;
-
arty＠svn.reactos.org