LIBAVL(3LIB) Interface Libraries LIBAVL(3LIB)
NNAAMMEE
lliibbaavvll - generic self-balancing binary search tree library
SSYYNNOOPPSSIISS
AVL Tree Library (libavl, -lavl)
##iinncclluuddee <~~>
DDEESSCCRRIIPPTTIIOONN
The lliibbaavvll library provides a generic implementation of AVL trees, a form
of self-balancing binary tree. The interfaces provided allow for an
efficient way of implementing an ordered set of data structures and, due
to its embeddable nature, allow for a single instance of a data structure
to belong to multiple AVL trees.
Each AVL tree contains entries of a single type of data structure.
Rather than allocating memory for pointers for those data structures, the
storage for the tree is embedded into the data structures by declaring a
member of type _a_v_l___n_o_d_e___t. When an AVL tree is created, through the use
of aavvll__ccrreeaattee(), it encodes the size of the data structure, the offset of
the data structure, and a comparator function which is used to compare
two instances of a data structure. A data structure may be a member of
multiple AVL trees by creating AVL trees which use different offsets
(different members) into the data structure.
AVL trees support both look up of an arbitrary item and ordered iteration
over the contents of the entire tree. In addition, from any node, you can
find the previous and next entries in the tree, if they exist. In
addition, AVL trees support arbitrary insertion and deletion.
PPeerrffoorrmmaannccee
AVL trees are often used in place of linked lists. Compared to the
standard, intrusive, doubly linked list, it has the following performance
characteristics:
LLooookkuupp OOnnee NNooddee
Lookup of a single node in a linked list is OO((nn)), whereas lookup
of a single node in an AVL tree is OO((lloogg((nn)))).
IInnsseerrtt OOnnee NNooddee
Inserting a single node into a linked list is OO((11)). Inserting a
single node into an AVL tree is OO((lloogg((nn)))).
Note, insertions into an AVL tree always result in an ordered
tree. Insertions into a linked list do not guarantee order. If
order is required, then the time to do the insertion into a
linked list will depend on the time of the search algorithm being
employed to find the place to insert at.
DDeelleettee OOnnee NNooddee
Deleting a single node from a linked list is OO((11)),, whereas
deleting a single node from an AVL tree takes OO((lloogg((nn)))) time.
DDeelleettee AAllll NNooddeess
Deleting all nodes from a linked list is OO((nn)). With an AVL tree,
if using the avl_destroy_nodes(3AVL) function then deleting all
nodes is OO((nn)). However, if iterating over each entry in the tree
and then removing it using a while loop, avl_first(3AVL) and
avl_remove(3AVL) then the time to remove all nodes is
OO((nn ** lloogg((nn))))..
VViissiitt tthhee NNeexxtt oorr PPrreevviioouuss NNooddee
Visiting the next or previous node in a linked list is OO((11)),
whereas going from the next to the previous node in an AVL tree
will take between OO((11)) and OO((lloogg((nn)))).
In general, AVL trees are a good alternative for linked lists when order
or lookup speed is important and a reasonable number of items will be
present.
IINNTTEERRFFAACCEESS
The shared object lliibbaavvll..ssoo..11 provides the public interfaces defined
below. See Intro(3) for additional information on shared object
interfaces. Individual functions are documented in their own manual
pages.
aavvll__aadddd aavvll__ccrreeaattee
aavvll__ddeessttrrooyy aavvll__ddeessttrrooyy__nnooddeess
aavvll__ffiinndd aavvll__ffiirrsstt
aavvll__iinnsseerrtt aavvll__iinnsseerrtt__hheerree
aavvll__iiss__eemmppttyy aavvll__llaasstt
aavvll__nneeaarreesstt aavvll__nnuummnnooddeess
aavvll__rreemmoovvee aavvll__sswwaapp
In addition, the library defines C pre-processor macros which are defined
below and documented in their own manual pages.
AAVVLL__NNEEXXTT AAVVLL__PPRREEVV
TTYYPPEESS
The lliibbaavvll library defines the following types:
aavvll__ttrreeee__tt
Type used for the root of the AVL tree. Consumers define one of these for
each of the different trees that they want to have.
aavvll__nnooddee__tt
Type used as the data node for an AVL tree. One of these is embedded in
each data structure that is the member of an AVL tree.
aavvll__iinnddeexx__tt
Type used to locate a position in a tree. This is used with
avl_find(3AVL) and avl_insert(3AVL).
LLOOCCKKIINNGG
The lliibbaavvll library provides no locking. Callers that are using the same
AVL tree from multiple threads need to provide their own synchronization.
If only one thread is ever accessing or modifying the AVL tree, then
there are no synchronization concerns. If multiple AVL trees exist, then
they may all be used simultaneously; however, they are subject to the
same rules around simultaneous access from a single thread.
All routines are both FFoorrkk--ssaaffee and AAssyynncc--SSiiggnnaall--SSaaffee. Callers may call
functions in lliibbaavvll from a signal handler and lliibbaavvll calls are all safe
in face of fork(2); however, if callers have their own locks, then they
must make sure that they are accounted for by the use of routines such as
pthread_atfork(3C).
EEXXAAMMPPLLEESS
The following code shows examples of exercising all of the functionality
that is present in lliibbaavvll. It can be compiled by using a C compiler and
linking against lliibbaavvll. For example, given a file named avl.c, with gcc,
one would run:
$ gcc -Wall -o avl avl.c -lavl
/*
* Example of using AVL Trees
*/
#include
#include
#include
#include
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();
}
/*
* 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();
cleanup();
return (0);
}
IINNTTEERRFFAACCEE SSTTAABBIILLIITTYY
CCoommmmiitttteedd
MMTT--LLeevveell
See _L_o_c_k_i_n_g_.
SSEEEE AALLSSOO
Intro(3), pthread_atfork(3C)
avl_add(3AVL), avl_create(3AVL), avl_destroy(3AVL),
avl_destroy_nodes(3AVL), avl_find(3AVL), avl_first(3AVL),
avl_insert(3AVL), avl_insert_here(3AVL), avl_is_empty(3AVL),
avl_last(3AVL), avl_nearest(3AVL), avl_numnodes(3AVL), avl_remove(3AVL),
avl_swap(3AVL),
Adel'son-Vel'skiy, G. M. and Landis, Ye. M., _A_n _A_l_g_o_r_i_t_h_m _f_o_r _t_h_e
_O_r_g_a_n_i_z_a_t_i_o_n _o_f _I_n_f_o_r_m_a_t_i_o_n, No. 2, Vol. 16, 263-266, Deklady Akademii
Nauk, USSR, Moscow, 1962.
illumos December 4, 2015 illumos
~~