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