summaryrefslogtreecommitdiff
path: root/src/search/tsearch_avl.c
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/search/tsearch_avl.c
parentbc9744763afe72d626e7b9f461001d425582fe9c (diff)
downloadmusl-8994908b199a57097f420707b1fca75fc30236fa.tar.gz
tsearch code cleanup
changed the insertion method to simplify the recursion logic and reduce code size a bit.
Diffstat (limited to 'src/search/tsearch_avl.c')
-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;
}