AVL_CREATE(3AVL) AVL Tree Library Functions AVL_CREATE(3AVL)

NAME

avl_create - create an AVL tree

SYNOPSIS

AVL Tree Library (libavl, -lavl)
#include <sys/avl.h>

void
avl_create(avl_tree_t *tree,
int (*compare)(const void *first, const void *second), size_t size,
size_t offset);

DESCRIPTION

The avl_create() function initializes an AVL tree rooted at tree.

An AVL tree needs to encode information about the type of data structures
being stored inside of it and needs to be told how to compare two different
entries in the same tree. The size argument represents the total size of
the data structure being used in the tree. This is a constant that is
generally expressed to avl_create() using the sizeof operator.

The data structure that is being stored in the AVL tree must include an
avl_node_t as a member of the structure. The structure may have multiple
avl_node_t's, one for each AVL tree that it may concurrently be a member
of. The offset argument indicates what the offset of the avl_node_t is for
the data structure that this AVL tree contains.

The compare function pointer is used to compare two nodes in the tree.
This is used as part of all operations on the tree that cause traversal.
The function is given, as arguments, two pointers to the actual data nodes,
which should be cast to the corresponding type of actual data. The return
value must adhere to the following rules:

1. If the first argument, first, is less than the second argument,
second, then the compare function must return -1.

2. If the first argument is greater than the second argument, then the
compare function must return 1.

3. Otherwise, if they compare to the same value, then it should return 0.

4. Only the return values, -1, 0, and 1, are valid. Returning values
other than those will result in undefined behavior.

When two nodes in the tree compare equal, then that means that they should
represent the same data, though they may not always be equivalent pointers,
due to lookups.

The life time and storage of the AVL tree is maintained by the caller. The
library does not perform any allocations as part of creating an AVL tree.

EXAMPLES

See the EXAMPLES section in libavl(3LIB).

INTERFACE STABILITY

Committed

MT-Level
See Locking in libavl(3LIB).

SEE ALSO

libavl(3LIB)

illumos May 7, 2015 illumos