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;
+}