about summary refs log tree commit diff
path: root/src
diff options
context:
space:
mode:
authorSzabolcs Nagy <nsz@port70.net>2015-12-05 21:06:02 +0100
committerRich Felker <dalias@aerifal.cx>2015-12-08 18:53:02 -0500
commit8994908b199a57097f420707b1fca75fc30236fa (patch)
tree688bb6348ae9835c2433f696dedbce89c635a096 /src
parentbc9744763afe72d626e7b9f461001d425582fe9c (diff)
downloadmusl-8994908b199a57097f420707b1fca75fc30236fa.tar.gz
musl-8994908b199a57097f420707b1fca75fc30236fa.tar.xz
musl-8994908b199a57097f420707b1fca75fc30236fa.zip
tsearch code cleanup
changed the insertion method to simplify the recursion logic and
reduce code size a bit.
Diffstat (limited to 'src')
-rw-r--r--src/search/tsearch_avl.c52
1 files changed, 28 insertions, 24 deletions
diff --git a/src/search/tsearch_avl.c b/src/search/tsearch_avl.c
index 8c2f3470..e4fb1316 100644
--- a/src/search/tsearch_avl.c
+++ b/src/search/tsearch_avl.c
@@ -77,31 +77,35 @@ static struct node *find(struct node *n, const void *k,
 		return find(n->right, k, cmp);
 }
 
-static struct node *insert(struct node **n, const void *k,
-	int (*cmp)(const void *, const void *), int *new)
+static struct node *insert(struct node *n, const void *k,
+	int (*cmp)(const void *, const void *), struct node **found)
 {
-	struct node *r = *n;
+	struct node *r;
 	int c;
 
-	if (!r) {
-		*n = r = malloc(sizeof **n);
-		if (r) {
-			r->key = k;
-			r->left = r->right = 0;
-			r->height = 1;
-			*new = 1;
+	if (!n) {
+		n = malloc(sizeof *n);
+		if (n) {
+			n->key = k;
+			n->left = n->right = 0;
+			n->height = 1;
 		}
-		return r;
+		*found = n;
+		return n;
+	}
+	c = cmp(k, n->key);
+	if (c == 0) {
+		*found = n;
+		return 0;
+	}
+	r = insert(c < 0 ? n->left : n->right, k, cmp, found);
+	if (r) {
+		if (c < 0)
+			n->left = r;
+		else
+			n->right = r;
+		r = balance(n);
 	}
-	c = cmp(k, r->key);
-	if (c == 0)
-		return r;
-	if (c < 0)
-		r = insert(&r->left, k, cmp, new);
-	else
-		r = insert(&r->right, k, cmp, new);
-	if (*new)
-		*n = balance(*n);
 	return r;
 }
 
@@ -165,11 +169,11 @@ void *tfind(const void *key, void *const *rootp,
 void *tsearch(const void *key, void **rootp,
 	int (*compar)(const void *, const void *))
 {
-	int new = 0;
-	struct node *n = *rootp;
+	struct node *update;
 	struct node *ret;
-	ret = insert(&n, key, compar, &new);
-	*rootp = n;
+	update = insert(*rootp, key, compar, &ret);
+	if (update)
+		*rootp = update;
 	return ret;
 }