diff options
author | Szabolcs Nagy <nsz@port70.net> | 2016-08-21 20:06:56 +0000 |
---|---|---|
committer | Rich Felker <dalias@aerifal.cx> | 2018-09-20 17:57:47 -0400 |
commit | c50985d5c8e316c5c464f352e79eeebfed1121a9 (patch) | |
tree | 46f4250072be1d98f3f98ccd3ae244b4eec5f3f1 /src/search/tsearch_avl.c | |
parent | 5ef60206ff9e697d3011bcf48afca50c9fe85e1b (diff) | |
download | musl-c50985d5c8e316c5c464f352e79eeebfed1121a9.tar.gz musl-c50985d5c8e316c5c464f352e79eeebfed1121a9.tar.bz2 musl-c50985d5c8e316c5c464f352e79eeebfed1121a9.tar.xz musl-c50985d5c8e316c5c464f352e79eeebfed1121a9.zip |
new tsearch implementation
Rewrote the AVL tree implementation:
- It is now non-recursive with fixed stack usage (large enough for
worst case tree height). twalk and tdestroy are still recursive as
that's smaller/simpler.
- Moved unrelated interfaces into separate translation units.
- The node structure is changed to use indexed children instead of
left/right pointers, this simplifies the balancing logic.
- Using void * pointers instead of struct node * in various places,
because this better fits the api (node address is passed in a void**
argument, so it is tempting to incorrectly cast it to struct node **).
- As a further performance improvement the rebalancing now stops
when it is not needed (subtree height is unchanged). Otherwise
the behaviour should be the same as before (checked over generated
random inputs that the resulting tree shape is equivalent).
- Removed the old copyright notice (including prng related one: it
should be licensed under the same terms as the rest of the project).
.text size of pic tsearch + tfind + tdelete + twalk:
x86_64 i386 aarch64 arm mips powerpc ppc64le sh4 m68k s390x
old 941 899 1220 1068 1852 1400 1600 1008 1008 1488
new 857 881 1040 976 1564 1192 1360 736 820 1408
Diffstat (limited to 'src/search/tsearch_avl.c')
-rw-r--r-- | src/search/tsearch_avl.c | 204 |
1 files changed, 0 insertions, 204 deletions
diff --git a/src/search/tsearch_avl.c b/src/search/tsearch_avl.c deleted file mode 100644 index 57194c84..00000000 --- a/src/search/tsearch_avl.c +++ /dev/null @@ -1,204 +0,0 @@ -#include <stdlib.h> -#include <search.h> - -/* -avl tree implementation using recursive functions -the height of an n node tree is less than 1.44*log2(n+2)-1 -(so the max recursion depth in case of a tree with 2^32 nodes is 45) -*/ - -struct node { - const void *key; - struct node *left; - struct node *right; - int height; -}; - -static int delta(struct node *n) { - return (n->left ? n->left->height:0) - (n->right ? n->right->height:0); -} - -static void updateheight(struct node *n) { - n->height = 0; - if (n->left && n->left->height > n->height) - n->height = n->left->height; - if (n->right && n->right->height > n->height) - n->height = n->right->height; - n->height++; -} - -static struct node *rotl(struct node *n) { - struct node *r = n->right; - n->right = r->left; - r->left = n; - updateheight(n); - updateheight(r); - return r; -} - -static struct node *rotr(struct node *n) { - struct node *l = n->left; - n->left = l->right; - l->right = n; - updateheight(n); - updateheight(l); - return l; -} - -static struct node *balance(struct node *n) { - int d = delta(n); - - if (d < -1) { - if (delta(n->right) > 0) - n->right = rotr(n->right); - return rotl(n); - } else if (d > 1) { - if (delta(n->left) < 0) - n->left = rotl(n->left); - return rotr(n); - } - updateheight(n); - return n; -} - -static struct node *find(struct node *n, const void *k, - int (*cmp)(const void *, const void *)) -{ - int c; - - if (!n) - return 0; - c = cmp(k, n->key); - if (c == 0) - return n; - if (c < 0) - return find(n->left, k, cmp); - else - return find(n->right, k, cmp); -} - -static struct node *insert(struct node *n, const void *k, - int (*cmp)(const void *, const void *), struct node **found) -{ - struct node *r; - int c; - - if (!n) { - n = malloc(sizeof *n); - if (n) { - n->key = k; - n->left = n->right = 0; - n->height = 1; - } - *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); - } - return 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); -} - -static struct node *remove(struct node **n, const void *k, - int (*cmp)(const void *, const void *), struct node *parent) -{ - int c; - - if (!*n) - return 0; - c = cmp(k, (*n)->key); - if (c == 0) { - struct node *r = *n; - 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; - } - if (c < 0) - parent = remove(&(*n)->left, k, cmp, *n); - else - parent = remove(&(*n)->right, k, cmp, *n); - if (parent) - *n = balance(*n); - return parent; -} - -void *tdelete(const void *restrict key, void **restrict rootp, - int(*compar)(const void *, const void *)) -{ - if (!rootp) - return 0; - struct node *n = *rootp; - struct node *ret; - /* last argument is arbitrary non-null pointer - which is returned when the root node is deleted */ - ret = remove(&n, key, compar, n); - *rootp = n; - return ret; -} - -void *tfind(const void *key, void *const *rootp, - int(*compar)(const void *, const void *)) -{ - if (!rootp) - return 0; - return find(*rootp, key, compar); -} - -void *tsearch(const void *key, void **rootp, - int (*compar)(const void *, const void *)) -{ - struct node *update; - struct node *ret; - if (!rootp) - return 0; - update = insert(*rootp, key, compar, &ret); - if (update) - *rootp = update; - return ret; -} - -static void walk(const struct node *r, void (*action)(const void *, VISIT, int), int d) -{ - if (r == 0) - return; - if (r->left == 0 && r->right == 0) - action(r, leaf, d); - else { - action(r, preorder, d); - walk(r->left, action, d+1); - action(r, postorder, d); - walk(r->right, action, d+1); - action(r, endorder, d); - } -} - -void twalk(const void *root, void (*action)(const void *, VISIT, int)) -{ - walk(root, action, 0); -} |