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

avl_create — create an AVL tree

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

The () 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 () using the 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 .
  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).

See Locking in libavl(3LIB).

libavl(3LIB)

May 7, 2015 OmniOS