AVL_CREATE(3AVL) AVL Tree Library Functions AVL_CREATE(3AVL)
- create an AVL tree
AVL Tree Library (libavl, -lavl) #include <sys/avl.h> void avl_create
, int (*compare)(const void *first, const void *second)
, size_t size
, size_t offset
() 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
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
the data structure that this AVL tree contains.
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.
See the EXAMPLES
section in libavl(3LIB)
INTERFACE STABILITY CommittedMT-Level
SEE ALSO libavl(3LIB)
illumos May 7, 2015 illumos