[<prev] [next>] [day] [month] [year] [list]
Message-ID: <20151205200234.GU23362@port70.net>
Date: Sat, 5 Dec 2015 21:02:34 +0100
From: Szabolcs Nagy <nsz@...t70.net>
To: musl@...ts.openwall.com
Cc: Ed Schouten <ed@...i.nl>
Subject: [PATCH 1/3] fix tdelete to properly balance the tree
the tsearch data structure is an avl tree, but it did not implement
the deletion operation correctly so the tree could become unbalanced.
reported by Ed Schouten.
---
src/search/tsearch_avl.c | 19 ++++++++++++++-----
1 file changed, 14 insertions(+), 5 deletions(-)
diff --git a/src/search/tsearch_avl.c b/src/search/tsearch_avl.c
index 8620092..0864460 100644
--- a/src/search/tsearch_avl.c
+++ b/src/search/tsearch_avl.c
@@ -105,10 +105,13 @@ static struct node *insert(struct node **n, const void *k,
return r;
}
-static struct node *movr(struct node *n, struct node *r) {
- if (!n)
- return r;
- n->right = movr(n->right, r);
+static struct node *remove_rightmost(struct node *n, struct node **rightmost)
+{
+ if (!n->right) {
+ *rightmost = n;
+ return n->left;
+ }
+ n->right = remove_rightmost(n->right, rightmost);
return balance(n);
}
@@ -122,7 +125,13 @@ static struct node *remove(struct node **n, const void *k,
c = cmp(k, (*n)->key);
if (c == 0) {
struct node *r = *n;
- *n = movr(r->left, r->right);
+ if (r->left) {
+ r->left = remove_rightmost(r->left, n);
+ (*n)->left = r->left;
+ (*n)->right = r->right;
+ *n = balance(*n);
+ } else
+ *n = r->right;
free(r);
return parent;
}
--
2.4.1
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
