about summary refs log tree commit diff
diff options
context:
space:
mode:
authorSzabolcs Nagy <nsz@port70.net>2015-12-05 21:02:34 +0100
committerRich Felker <dalias@aerifal.cx>2015-12-08 18:52:25 -0500
commite4f9d811684011d8a67e363827de39d5f2d3ae5a (patch)
tree1ce17f8c89f1afd7d11ebedee5e9a5b03839cd39
parent7b712844e38bdfc1ef728e257fb8616c16ec4cc8 (diff)
downloadmusl-e4f9d811684011d8a67e363827de39d5f2d3ae5a.tar.gz
musl-e4f9d811684011d8a67e363827de39d5f2d3ae5a.tar.xz
musl-e4f9d811684011d8a67e363827de39d5f2d3ae5a.zip
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.
-rw-r--r--src/search/tsearch_avl.c19
1 files changed, 14 insertions, 5 deletions
diff --git a/src/search/tsearch_avl.c b/src/search/tsearch_avl.c
index 86200928..08644607 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;
 	}