#include <stdio.h>
#include <stdlib.h>

#include <sys/tree.h>
#include <kern/subr_tree.c>

struct node {
	AVL_ENTRY()	entry;
	unsigned int	key;
};

AVL_HEAD(nodes, node);

static inline int
node_cmp(const struct node *a, const struct node *b)
{
	if (a->key > b->key)
		return (1);
	if (a->key < b->key)
		return (-1);

	return (0);
}

AVL_PROTOTYPE(nodes, node, entry, node_cmp);

#ifndef nitems
#define nitems(_a) (sizeof((_a)) / sizeof((_a)[0]))
#endif

static int
avl_height(struct node *n)
{
	int l = 1, r = 1;
	struct node *child;

	child = AVL_LEFT(nodes, n);
	if (child != NULL)
		l += avl_height(child);
	child = AVL_RIGHT(nodes, n);
	if (child != NULL)
		r += avl_height(child);

	if (l > r) {
		int swap = l;
		l = r;
		r = swap;
	}
	if (r - l > 1)
		printf("%p %d %d\n", n, l, r);

	return (r);
}

static int
avl_verify(struct nodes *tree)
{
	printf("%p %d\n", AVL_ROOT(nodes, tree),
	    avl_height(AVL_ROOT(nodes, tree)));
	return (0);
}

int
main(int argc, char *argv[])
{
	struct nodes nodes = AVL_INITIALIZER();
	struct node nlist[48];
	unsigned int i;
	struct node *n;

	for (i = 0; i < nitems(nlist); i++) {
		n = &nlist[i];
		do {
			n->key = arc4random();
		} while (AVL_INSERT(nodes, &nodes, n) != NULL);
		if (AVL_PARENT(nodes, n) == n)
			exit(1);
		avl_verify(&nodes);
	}
	for (i = 0; i < nitems(nlist); i++) {
		n = AVL_FIND(nodes, &nodes, &nlist[i]);
		if (n == NULL) {
			n = &nlist[i];
			printf("%s: %p (%p %p %d)\n", __func__, n,
			    n->entry.bst_children[0],
			    n->entry.bst_children[1],
			    n->entry.bst_data);
		}
	}

	printf("digraph G {\n");
	printf("root -> k%u;\n", AVL_ROOT(nodes, &nodes)->key);
	AVL_FOREACH(n, nodes, &nodes) {
		if (AVL_LEFT(nodes, n))
			printf("k%u -> k%u;\n",
			    n->key, AVL_LEFT(nodes, n)->key);
		if (AVL_RIGHT(nodes, n))
			printf("k%u -> k%u;\n",
			    n->key, AVL_RIGHT(nodes, n)->key);
	}
	printf("}\n");
	exit(0);

	AVL_FOREACH(n, nodes, &nodes) {
		printf("0x%08x %u %p\n", n->key, n->key, n);
	}

	for (i = 0; i < nitems(nlist); i++) {
		n = &nlist[i];
		AVL_REMOVE(nodes, &nodes, n);
	}

	printf("empty %d\n", AVL_EMPTY(nodes, &nodes));

	return (0);
}

AVL_GENERATE(nodes, node, entry, node_cmp);