[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.
13 Oct
2006
13 Oct
'06
7:02 a.m.
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=2…
==============================================================================
--- 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?re…
==============================================================================
--- 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=…
==============================================================================
--- 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=…
==============================================================================
--- 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;
6883
days inactive
6883
days old
0 comments
1 participants
participants (1)
-
arty＠svn.reactos.org