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	{
12	void **a[MAXH+1];
13	struct node *n = *rootp;
14	struct node *parent;
15	struct node *child;
16	int i=0;
17	/* *a[0] is an arbitrary non-null pointer that is returned when
18	   the root node is deleted.  */
19	a[i++] = rootp;
20	a[i++] = rootp;
21	for (;;) {
22		if (!n)
23			return 0;
24		{
25		int c = cmp(key, n->key);
26		if (!c)
27			break;
28		a[i++] = &n->a[c>0];
29		n = n->a[c>0];
30		}
31	}
32	parent = *a[i-2];
33	if (n->a[0]) {
34		/* free the preceding node instead of the deleted one.  */
35		struct node *deleted = n;
36		a[i++] = &n->a[0];
37		n = n->a[0];
38		while (n->a[1]) {
39			a[i++] = &n->a[1];
40			n = n->a[1];
41		}
42		deleted->key = n->key;
43		child = n->a[0];
44	} else {
45		child = n->a[1];
46	}
47	/* freed node has at most one child, move it up and rebalance.  */
48	free(n);
49	*a[--i] = child;
50	while (--i && __tsearch_balance(a[i]));
51	return parent;
52	}
53}
54