* [PATCH 3/3] tsearch code cleanup
@ 2015-12-05 20:06 Szabolcs Nagy
0 siblings, 0 replies; only message in thread
From: Szabolcs Nagy @ 2015-12-05 20:06 UTC (permalink / raw)
To: musl; +Cc: Ed Schouten
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
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2015-12-05 20:06 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2015-12-05 20:06 [PATCH 3/3] tsearch code cleanup Szabolcs Nagy
Code repositories for project(s) associated with this public inbox
https://git.vuxu.org/mirror/musl/
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).