1#include <stdlib.h>
 2#include <search.h>
 3#include "tsearch.h"
 4
 5void *tdelete(const void *restrict key, void **restrict rootp,
 6	int(*cmp)(const void *, const void *))
 7{
 8	if (!rootp)
 9		return 0;
10
11	void **a[MAXH+1];
12	struct node *n = *rootp;
13	struct node *parent;
14	struct node *child;
15	int i=0;
16	/* *a[0] is an arbitrary non-null pointer that is returned when
17	   the root node is deleted.  */
18	a[i++] = rootp;
19	a[i++] = rootp;
20	for (;;) {
21		if (!n)
22			return 0;
23		int c = cmp(key, n->key);
24		if (!c)
25			break;
26		a[i++] = &n->a[c>0];
27		n = n->a[c>0];
28	}
29	parent = *a[i-2];
30	if (n->a[0]) {
31		/* free the preceding node instead of the deleted one.  */
32		struct node *deleted = n;
33		a[i++] = &n->a[0];
34		n = n->a[0];
35		while (n->a[1]) {
36			a[i++] = &n->a[1];
37			n = n->a[1];
38		}
39		deleted->key = n->key;
40		child = n->a[0];
41	} else {
42		child = n->a[1];
43	}
44	/* freed node has at most one child, move it up and rebalance.  */
45	free(n);
46	*a[--i] = child;
47	while (--i && __tsearch_balance(a[i]));
48	return parent;
49}