[<prev] [next>] [day] [month] [year] [list]
Date: Sat, 5 Dec 2015 21:06:02 +0100
From: Szabolcs Nagy <nsz@...t70.net>
To: musl@...ts.openwall.com
Cc: Ed Schouten <ed@...i.nl>
Subject: [PATCH 3/3] tsearch code cleanup
changed the insertion method to simplify the recursion logic and
reduce code size a bit.
---
src/search/tsearch_avl.c | 52 ++++++++++++++++++++++++++----------------------
1 file changed, 28 insertions(+), 24 deletions(-)
diff --git a/src/search/tsearch_avl.c b/src/search/tsearch_avl.c
index 8c2f347..e4fb131 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;
}
--
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.
