LIBAVL(3LIB) Interface Libraries LIBAVL(3LIB)

## NAME

**libavl **- generic self-balancing binary search tree library

## SYNOPSIS

AVL Tree Library (libavl, -lavl)

**#include <sys/avl.h>**

## DESCRIPTION

The**libavl **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__avl_node_t__. When an AVL tree is created, through the use of

**avl_create**(), 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.

### Performance

AVL trees are often used in place of linked lists. Compared to the

standard, intrusive, doubly linked list, it has the following performance

characteristics:

**Lookup One Node**

Lookup of a single node in a linked list is**O(n)**, whereas lookup of

a single node in an AVL tree is**O(log(n))**.

**Insert One Node**

Inserting a single node into a linked list is**O(1)**. Inserting a

single node into an AVL tree is**O(log(n))**.

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.

**Delete One Node**

Deleting a single node from a linked list is**O(1), **whereas deleting

a single node from an AVL tree takes**O(log(n)) **time.

**Delete All Nodes**

Deleting all nodes from a linked list is**O(n)**. With an AVL tree,

if using the avl_destroy_nodes(3AVL) function then deleting all

nodes is**O(n)**. 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

**O(n * log(n)).**

**Visit the Next or Previous Node**

Visiting the next or previous node in a linked list is**O(1)**,

whereas going from the next to the previous node in an AVL tree

will take between**O(1) **and **O(log(n))**.

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.

## INTERFACES

The shared object**libavl.so.1 **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.

**avl_add avl_create**

**avl_destroy avl_destroy_nodes**

**avl_find avl_first**

**avl_insert avl_insert_here**

**avl_is_empty avl_last**

**avl_nearest avl_numnodes**

**avl_remove avl_swap**

In addition, the library defines C pre-processor macros which are defined

below and documented in their own manual pages.

**AVL_NEXT AVL_PREV**

## TYPES

The**libavl **library defines the following types:

**avl_tree_t**

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.

**avl_node_t**

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.

**avl_index_t**

Type used to locate a position in a tree. This is used with avl_find(3AVL)

and avl_insert(3AVL).

## LOCKING

The**libavl **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**Fork-safe **and **Async-Signal-Safe**. Callers may call

functions in**libavl **from a signal handler and **libavl **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).

## EXAMPLES

The following code shows examples of exercising all of the functionality

that is present in**libavl**. It can be compiled by using a C compiler and

linking against**libavl**. 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 <sys/avl.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();

}

/*

* 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);

}

## INTERFACE STABILITY

**Committed**

**MT-Level**

See__Locking.__

## SEE ALSO

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.,__An__ __Algorithm__ __for__ __the__

__Organization__ __of__ __Information__, No. 2, Vol. 16, 263-266, Deklady Akademii

Nauk, USSR, Moscow, 1962.

illumos December 4, 2015 illumos

AVL Tree Library (libavl, -lavl)

The

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

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.

AVL trees are often used in place of linked lists. Compared to the

standard, intrusive, doubly linked list, it has the following performance

characteristics:

Lookup of a single node in a linked list is

a single node in an AVL tree is

Inserting a single node into a linked list is

single node into an AVL tree is

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.

Deleting a single node from a linked list is

a single node from an AVL tree takes

Deleting all nodes from a linked list is

if using the avl_destroy_nodes(3AVL) function then deleting all

nodes is

and then removing it using a while loop, avl_first(3AVL) and

avl_remove(3AVL) then the time to remove all nodes is

Visiting the next or previous node in a linked list is

whereas going from the next to the previous node in an AVL tree

will take between

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.

The shared object

See Intro(3) for additional information on shared object interfaces.

Individual functions are documented in their own manual pages.

In addition, the library defines C pre-processor macros which are defined

below and documented in their own manual pages.

The

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.

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.

Type used to locate a position in a tree. This is used with avl_find(3AVL)

and avl_insert(3AVL).

The

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

functions 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).

The following code shows examples of exercising all of the functionality

that is present in

linking against

one would run:

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

/*

* Example of using AVL Trees

*/

#include <sys/avl.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();

}

/*

* 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);

}

See

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.,

Nauk, USSR, Moscow, 1962.

illumos December 4, 2015 illumos