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

Data Structures
struct	avl_node

struct	avl_tree

struct	avl_allocator

Macros
#define	AVL_TREE_COMMENT_UNUSED 1

#define	AVL_DEPTH

#define	AVL_COUNT

#define	AVL_CMP(a, b) ((a) < (b) ? -1 : (a) != (b))

#define	AVL_NODE_INITIALIZER(item) { 0, 0, 0, 0, 0, (item), 0, 0 }

#define	AVL_TREE_INITIALIZER(cmp, free) { 0, 0, 0, (cmp), (free), {0}, 0, 0 }

#define	AVL_ALLOCATOR_INITIALIZER(alloc, dealloc) { (alloc), (dealloc) }

#define	AVL_NODE_COUNT(n) ((n) ? (n)->count : 0)

#define	AVL_L_COUNT(n) (AVL_NODE_COUNT((n)->left))

#define	AVL_R_COUNT(n) (AVL_NODE_COUNT((n)->right))

#define	AVL_CALC_COUNT(n) (AVL_L_COUNT(n) + AVL_R_COUNT(n) + 1)

#define	AVL_NODE_DEPTH(n) ((n) ? (n)->depth : 0)

#define	AVL_L_DEPTH(n) (AVL_NODE_DEPTH((n)->left))

#define	AVL_R_DEPTH(n) (AVL_NODE_DEPTH((n)->right))

#define	AVL_CALC_DEPTH(n) ((unsigned char)((AVL_L_DEPTH(n) > AVL_R_DEPTH(n) ? AVL_L_DEPTH(n) : AVL_R_DEPTH(n)) + 1))

#define	AVL_CONST_NODE(x) ((avl_node_t *)(x))

#define	AVL_CONST_ITEM(x) ((void *)(x))

Typedefs
typedef int(*	avl_compare_t) (const void a, const void b, void *userdata)

typedef void(*	avl_free_t) (void item, void userdata)

typedef struct avl_node	avl_node_t

typedef struct avl_tree	avl_tree_t

typedef avl_node_t (	avl_allocate_t) (struct avl_allocator *)

typedef void(*	avl_deallocate_t) (struct avl_allocator , avl_node_t )

typedef struct avl_allocator	avl_allocator_t

Functions
static void	avl_rebalance (avl_tree_t , avl_node_t )

static avl_node_t *	avl_node_insert_after (avl_tree_t avltree, avl_node_t node, avl_node_t *newnode)

static int	avl_check_balance (avl_node_t *avlnode)

static unsigned long	avl_count (const avl_tree_t *avltree)

static const avl_node_t *	avl_search_rightmost_equal (const avl_tree_t tree, const avl_node_t node, const void *item)

static avl_node_t *	avl_search_rightish (const avl_tree_t tree, const void item, int *exact)

static avl_node_t *	avl_item_search_right (const avl_tree_t tree, const void item, int *exact)

static avl_node_t *	avl_item_search (const avl_tree_t avltree, const void item)

static avl_tree_t *	avl_tree_init (avl_tree_t *avltree, avl_compare_t cmp, avl_free_t free_item)

static avl_tree_t *	avl_tree_construct (avl_compare_t cmp, avl_free_t free_item)

static avl_tree_t *	avl_tree_clear (avl_tree_t *avltree)

static void	avl_node_free (avl_tree_t avltree, avl_node_t node)

static avl_tree_t *	avl_tree_purge (avl_tree_t *avltree)

static void	avl_tree_destruct (avl_tree_t *avltree)

static void	avl_node_clear (avl_node_t *newnode)

static avl_node_t *	avl_node_init (avl_node_t newnode, const void item)

static avl_node_t *	avl_alloc (avl_tree_t avltree, const void item)

static avl_node_t *	avl_insert_top (avl_tree_t avltree, avl_node_t newnode)

static avl_node_t *	avl_node_insert_before (avl_tree_t avltree, avl_node_t node, avl_node_t *newnode)

static avl_node_t *	avl_node_insert (avl_tree_t avltree, avl_node_t newnode)

static avl_node_t *	avl_item_insert (avl_tree_t avltree, const void item)

static avl_node_t *	avl_node_unlink (avl_tree_t avltree, avl_node_t avlnode)

static void *	avl_node_delete (avl_tree_t avltree, avl_node_t avlnode)

static void *	avl_item_delete (avl_tree_t avltree, const void item)

Variables
const avl_node_t	avl_node_0 = { 0, 0, 0, 0, 0, 0, 0, 0 }

const avl_tree_t	avl_tree_0 = { 0, 0, 0, 0, 0, 0, 0 }

const avl_allocator_t	avl_allocator_0 = { 0, 0 }

Macro Definition Documentation

#define AVL_ALLOCATOR_INITIALIZER	(	alloc,
		dealloc
	)	{ (alloc), (dealloc) }

#define AVL_CALC_COUNT ( n ) (AVL_L_COUNT(n) + AVL_R_COUNT(n) + 1)

#define AVL_CALC_DEPTH ( n ) ((unsigned char)((AVL_L_DEPTH(n) > AVL_R_DEPTH(n) ? AVL_L_DEPTH(n) : AVL_R_DEPTH(n)) + 1))

#define AVL_CMP	(	a,
		b
	)	((a) < (b) ? -1 : (a) != (b))

#define AVL_CONST_ITEM ( x ) ((void *)(x))

#define AVL_CONST_NODE ( x ) ((avl_node_t *)(x))

#define AVL_COUNT

#define AVL_DEPTH

#define AVL_L_COUNT ( n ) (AVL_NODE_COUNT((n)->left))

#define AVL_L_DEPTH ( n ) (AVL_NODE_DEPTH((n)->left))

#define AVL_NODE_COUNT ( n ) ((n) ? (n)->count : 0)

#define AVL_NODE_DEPTH ( n ) ((n) ? (n)->depth : 0)

#define AVL_NODE_INITIALIZER ( item ) { 0, 0, 0, 0, 0, (item), 0, 0 }

#define AVL_R_COUNT ( n ) (AVL_NODE_COUNT((n)->right))

#define AVL_R_DEPTH ( n ) (AVL_NODE_DEPTH((n)->right))

#define AVL_TREE_COMMENT_UNUSED 1

#define AVL_TREE_INITIALIZER	(	cmp,
		free
	)	{ 0, 0, 0, (cmp), (free), {0}, 0, 0 }

Typedef Documentation

typedef avl_node_t*(* avl_allocate_t) (struct avl_allocator *)

typedef struct avl_allocator avl_allocator_t

typedef int(* avl_compare_t) (const void *a, const void *b, void *userdata)

typedef void(* avl_deallocate_t) (struct avl_allocator *, avl_node_t *)

typedef void(* avl_free_t) (void *item, void *userdata)

typedef struct avl_node avl_node_t

typedef struct avl_tree avl_tree_t

Function Documentation

static avl_node_t* avl_alloc	(	avl_tree_t *	avltree,
		const void *	item
	)

static

static int avl_check_balance ( avl_node_t * avlnode )

static

static unsigned long avl_count ( const avl_tree_t * avltree )

static

static avl_node_t* avl_insert_top	(	avl_tree_t *	avltree,
		avl_node_t *	newnode
	)

static

static void* avl_item_delete	(	avl_tree_t *	avltree,
		const void *	item
	)

static

static avl_node_t* avl_item_insert	(	avl_tree_t *	avltree,
		const void *	item
	)

static

static avl_node_t* avl_item_search	(	const avl_tree_t *	avltree,
		const void *	item
	)

static

static avl_node_t* avl_item_search_right	(	const avl_tree_t *	tree,
		const void *	item,
		int *	exact
	)

static

static void avl_node_clear ( avl_node_t * newnode )

static

static void* avl_node_delete	(	avl_tree_t *	avltree,
		avl_node_t *	avlnode
	)

static

static void avl_node_free	(	avl_tree_t *	avltree,
		avl_node_t *	node
	)

static

static avl_node_t* avl_node_init	(	avl_node_t *	newnode,
		const void *	item
	)

static

static avl_node_t* avl_node_insert	(	avl_tree_t *	avltree,
		avl_node_t *	newnode
	)

static

static avl_node_t * avl_node_insert_after	(	avl_tree_t *	avltree,
		avl_node_t *	node,
		avl_node_t *	newnode
	)

static

static avl_node_t* avl_node_insert_before	(	avl_tree_t *	avltree,
		avl_node_t *	node,
		avl_node_t *	newnode
	)

static

static avl_node_t* avl_node_unlink	(	avl_tree_t *	avltree,
		avl_node_t *	avlnode
	)

static

static void avl_rebalance	(	avl_tree_t *	avltree,
		avl_node_t *	avlnode
	)

static

avl_rebalance: Rebalances the tree if one side becomes too heavy. This function assumes that both subtrees are AVL-trees with consistent data. The function has the additional side effect of recalculating the count of the tree at this node. It should be noted that at the return of this function, if a rebalance takes place, the top of this subtree is no longer going to be the same node.

static avl_node_t* avl_search_rightish	(	const avl_tree_t *	tree,
		const void *	item,
		int *	exact
	)

static

static const avl_node_t* avl_search_rightmost_equal	(	const avl_tree_t *	tree,
		const avl_node_t *	node,
		const void *	item
	)

static

static avl_tree_t* avl_tree_clear ( avl_tree_t * avltree )

static

static avl_tree_t* avl_tree_construct	(	avl_compare_t	cmp,
		avl_free_t	free_item
	)

static

static void avl_tree_destruct ( avl_tree_t * avltree )

static

static avl_tree_t* avl_tree_init	(	avl_tree_t *	avltree,
		avl_compare_t	cmp,
		avl_free_t	free_item
	)

static

static avl_tree_t* avl_tree_purge ( avl_tree_t * avltree )

static

Variable Documentation

const avl_allocator_t avl_allocator_0 = { 0, 0 }

const avl_node_t avl_node_0 = { 0, 0, 0, 0, 0, 0, 0, 0 }

const avl_tree_t avl_tree_0 = { 0, 0, 0, 0, 0, 0, 0 }

Data Structures

Macros

Typedefs

Functions

Variables

Macro Definition Documentation

Typedef Documentation

Function Documentation

Variable Documentation