From 4abab5ad6c8465a7528ccdd5f49367da05f78bbd Mon Sep 17 00:00:00 2001 From: Vladimir Azarov Date: Tue, 1 Oct 2024 15:47:05 +0200 Subject: Initial version --- src/search/tdelete.c | 49 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 49 insertions(+) create mode 100644 src/search/tdelete.c (limited to 'src/search/tdelete.c') diff --git a/src/search/tdelete.c b/src/search/tdelete.c new file mode 100644 index 0000000..b8bb924 --- /dev/null +++ b/src/search/tdelete.c @@ -0,0 +1,49 @@ +#include +#include +#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; +} -- cgit v1.2.3