From 495f7e56299ee7682a164afe1f84c1f638b27542 Mon Sep 17 00:00:00 2001 From: Howard Chu Date: Wed, 21 Sep 2005 19:18:40 +0000 Subject: [PATCH] tavl_delete - swap whole structures, not the data pointers. --- libraries/liblutil/tavl.c | 42 ++++++++++++++++++++++++++++++++++----- 1 file changed, 37 insertions(+), 5 deletions(-) diff --git a/libraries/liblutil/tavl.c b/libraries/liblutil/tavl.c index 923356c2ea..988b7b750b 100644 --- a/libraries/liblutil/tavl.c +++ b/libraries/liblutil/tavl.c @@ -220,16 +220,48 @@ tavl_delete( Avlnode **root, void* data, AVL_CMP fcmp ) /* find the immediate predecessor */ q = p->avl_link[0]; - pdir[depth] = 0; - pptr[depth++] = p; + side = depth; + pdir[depth++] = 0; while (q->avl_bits[1] == AVL_CHILD && q->avl_link[1]) { pdir[depth] = 1; pptr[depth++] = q; q = q->avl_link[1]; } - /* swap */ - p->avl_data = q->avl_data; - p = q; + /* swap links */ + r = p->avl_link[0]; + p->avl_link[0] = q->avl_link[0]; + q->avl_link[0] = r; + + q->avl_link[1] = p->avl_link[1]; + p->avl_link[1] = q; + + p->avl_bits[0] = q->avl_bits[0]; + p->avl_bits[1] = q->avl_bits[1]; + q->avl_bits[0] = q->avl_bits[1] = AVL_CHILD; + + /* fix stack positions: old parent of p points to q */ + pptr[side] = q; + if ( side ) { + --side; + r = pptr[side]; + r->avl_link[pdir[side]] = q; + } else { + *root = q; + } + /* new parent of p points to p */ + if ( depth > 2 ) { + r = pptr[depth-2]; + r->avl_link[1] = p; + pptr[depth-1] = p; + } else { + q->avl_link[0] = p; + } + + /* fix right subtree: successor of p points to q */ + r = q->avl_link[1]; + while ( r->avl_bits[0] == AVL_CHILD && r->avl_link[0] ) + r = r->avl_link[0]; + r->avl_link[0] = q; } /* now

has at most one child, get it */ -- 2.39.5