#include <stdlib.h>
#include <search.h>

struct node {
	const void *key;
	struct node *left;
	struct node *right;
};

static struct node **lookup(const void *key, struct node **r,
	int (*compar)(const void *, const void *))
{
	while (*r) {
		int c = compar(key, (*r)->key);
		if (c < 0)
			r = &(*r)->left;
		else if (c > 0)
			r = &(*r)->right;
		else
			break;
	}
	return r;
}

void *tdelete(const void *restrict key, void **restrict rootp,
	int(*compar)(const void *, const void *))
{
	struct node **r = (void*)rootp;
	struct node *parent = *r; /* arbitrary non-null pointer */
	struct node *a;
	struct node *b;
	int c;

	for (;;) {
		if (!*r)
			return 0;
		c = compar(key, (*r)->key);
		if (c == 0)
			break;
		parent = *r;
		if (c < 0)
			r = &(*r)->left;
		else
			r = &(*r)->right;
	}
	a = (*r)->left;
	b = (*r)->right;
	free(*r);
	if (a) {
		*r = a;
		for (; a->right; a = a->right);
		a->right = b;
	} else
		*r = b;
	return parent;
}

void *tfind(const void *key, void *const *rootp,
	int(*compar)(const void *, const void *))
{
	return *lookup(key, (void*)rootp, compar);
}

void *tsearch(const void *key, void **rootp,
	int (*compar)(const void *, const void *))
{
	struct node **r = lookup(key, (void*)rootp, compar);
	if (*r)
		return *r;
	*r = malloc(sizeof **r);
	if (*r) {
		(*r)->left = (*r)->right = 0;
		(*r)->key = key;
	}
	return *r;
}

static void rec(const struct node *r, void (*action)(const void *, VISIT, int), int d) {
	if (r == 0)
		return;
	if (r->left == 0 && r->right == 0)
		action(r, leaf, d);
	else {
		action(r, preorder, d);
		rec(r->left, action, d+1);
		action(r, postorder, d);
		rec(r->right, action, d+1);
		action(r, endorder, d);
	}
}

void twalk(const void *root, void (*action)(const void *, VISIT, int))
{
	rec(root, action, 0);
}