[ros-diffs] [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.
arty at svn.reactos.org
arty at svn.reactos.org
Fri Oct 13 09:02:05 CEST 2006
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=24495&r1=24494&r2=24495&view=diff
==============================================================================
--- 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=24495&r1=24494&r2=24495&view=diff
==============================================================================
--- 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=24495&r1=24494&r2=24495&view=diff
==============================================================================
--- 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=24495&r1=24494&r2=24495&view=diff
==============================================================================
--- 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=24495&r1=24494&r2=24495&view=diff
==============================================================================
--- 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=24495&r1=24494&r2=24495&view=diff
==============================================================================
--- 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;
More information about the Ros-diffs
mailing list