diff options
Diffstat (limited to 'src/search/tdelete.c')
-rw-r--r-- | src/search/tdelete.c | 49 |
1 files changed, 49 insertions, 0 deletions
diff --git a/src/search/tdelete.c b/src/search/tdelete.c new file mode 100644 index 00000000..b8bb924b --- /dev/null +++ b/src/search/tdelete.c @@ -0,0 +1,49 @@ +#include <stdlib.h> +#include <search.h> +#include "tsearch.h" + +void *tdelete(const void *restrict key, void **restrict rootp, + int(*cmp)(const void *, const void *)) +{ + if (!rootp) + return 0; + + void **a[MAXH+1]; + struct node *n = *rootp; + struct node *parent; + struct node *child; + int i=0; + /* *a[0] is an arbitrary non-null pointer that is returned when + the root node is deleted. */ + a[i++] = rootp; + a[i++] = rootp; + for (;;) { + if (!n) + return 0; + int c = cmp(key, n->key); + if (!c) + break; + a[i++] = &n->a[c>0]; + n = n->a[c>0]; + } + parent = *a[i-2]; + if (n->a[0]) { + /* free the preceding node instead of the deleted one. */ + struct node *deleted = n; + a[i++] = &n->a[0]; + n = n->a[0]; + while (n->a[1]) { + a[i++] = &n->a[1]; + n = n->a[1]; + } + deleted->key = n->key; + child = n->a[0]; + } else { + child = n->a[1]; + } + /* freed node has at most one child, move it up and rebalance. */ + free(n); + *a[--i] = child; + while (--i && __tsearch_balance(a[i])); + return parent; +} |