$ gcc -Wall -o avl avl.c -lavl

/*
 * Example of using AVL Trees
 */

#include <sys/avl.h>
#include <assert.h>
#include <stddef.h>
#include <stdlib.h>
#include <stdio.h>

static avl_tree_t inttree;

/*
 * The structure that we're storing in an AVL tree.
 */
typedef struct intnode {
	int in_val;
	avl_node_t in_avl;
} intnode_t;

static int
intnode_comparator(const void *l, const void *r)
{
	const intnode_t *li = l;
	const intnode_t *ri = r;

	if (li->in_val > ri->in_val)
		return (1);
	if (li->in_val < ri->in_val)
		return (-1);
	return (0);
}

/*
 * Create an AVL Tree
 */
static void
create_avl(void)
{
	avl_create(&inttree, intnode_comparator, sizeof (intnode_t),
	    offsetof(intnode_t, in_avl));
}

/*
 * Add entries to the tree with the avl_add function.
 */
static void
fill_avl(void)
{
	int i;
	intnode_t *inp;

	for (i = 0; i < 20; i++) {
		inp = malloc(sizeof (intnode_t));
		assert(inp != NULL);
		inp->in_val = i;
		avl_add(&inttree, inp);
	}
}

/*
 * Find entries in the AVL tree. Note, we create an intnode_t on the
 * stack that we use to look this up.
 */
static void
find_avl(void)
{
	int i;
	intnode_t lookup, *inp;

	for (i = 10; i < 30; i++) {
		lookup.in_val = i;
		inp = avl_find(&inttree, &lookup, NULL);
		if (inp == NULL) {
			printf("Entry %d is not in the tree\n", i);
		} else {
			printf("Entry %d is in the tree\n",
			    inp->in_val);
		}
	}
}

/*
 * Walk the tree forwards
 */
static void
walk_forwards(void)
{
	intnode_t *inp;
	for (inp = avl_first(&inttree); inp != NULL;
	    inp = AVL_NEXT(&inttree, inp)) {
		printf("Found entry %d\n", inp->in_val);
	}
}

/*
 * Walk the tree backwards.
 */
static void
walk_backwards(void)
{
	intnode_t *inp;
	for (inp = avl_last(&inttree); inp != NULL;
	    inp = AVL_PREV(&inttree, inp)) {
		printf("Found entry %d\n", inp->in_val);
	}
}

/*
 * Determine the number of nodes in the tree and if it is empty or
 * not.
 */
static void
inttree_inspect(void)
{
	printf("The tree is %s, there are %ld nodes in it\n",
	    avl_is_empty(&inttree) == B_TRUE ? "empty" : "not empty",
	    avl_numnodes(&inttree));
}

/*
 * Use avl_remove to remove entries from the tree.
 */
static void
remove_nodes(void)
{
	int i;
	intnode_t lookup, *inp;

	for (i = 0; i < 20; i+= 4) {
		lookup.in_val = i;
		inp = avl_find(&inttree, &lookup, NULL);
		if (inp != NULL)
			avl_remove(&inttree, inp);
	}
}

/*
 * Find the nearest nodes in the tree.
 */
static void
nearest_nodes(void)
{
	intnode_t lookup, *inp;
	avl_index_t where;

	lookup.in_val = 12;
	if (avl_find(&inttree, &lookup, &where) != NULL)
		abort();
	inp = avl_nearest(&inttree, where, AVL_BEFORE);
	assert(inp != NULL);
	printf("closest node before 12 is: %d\n", inp->in_val);
	inp = avl_nearest(&inttree, where, AVL_AFTER);
	assert(inp != NULL);
	printf("closest node after 12 is: %d\n", inp->in_val);
}

static void
insert_avl(void)
{
	intnode_t lookup, *inp;
	avl_index_t where;

	lookup.in_val = 12;
	if (avl_find(&inttree, &lookup, &where) != NULL)
		abort();
	inp = malloc(sizeof (intnode_t));
	assert(inp != NULL);
	avl_insert(&inttree, inp, where);
}

static void
swap_avl(void)
{
	avl_tree_t swap;

	avl_create(&swap, intnode_comparator, sizeof (intnode_t),
	    offsetof(intnode_t, in_avl));
	avl_swap(&inttree, &swap);
	inttree_inspect();
	avl_swap(&inttree, &swap);
	inttree_inspect();
}

static void
update_avl(void)
{
	intnode_t lookup, *inp;
	avl_index_t where;

	lookup.in_val = 9;
	inp = avl_find(&inttree, &lookup, &where);
	assert(inp != NULL);
	inp->in_val = 25;
	avl_update(&inttree, inp);
}

/*
 * Remove all remaining nodes in the tree. We first use
 * avl_destroy_nodes to empty the tree, then avl_destroy to finish.
 */
static void
cleanup(void)
{
	intnode_t *inp;
	void *c = NULL;

	while ((inp = avl_destroy_nodes(&inttree, &c)) != NULL) {
		free(inp);
	}
	avl_destroy(&inttree);
}

int
main(void)
{
	create_avl();
	inttree_inspect();
	fill_avl();
	find_avl();
	walk_forwards();
	walk_backwards();
	inttree_inspect();
	remove_nodes();
	inttree_inspect();
	nearest_nodes();
	insert_avl();
	inttree_inspect();
	swap_avl();
	update_avl();
	cleanup();
	return (0);
}