NAME

avl, 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, avl_update, avl_update_gt, avl_update_lt, AVL_NEXT, AVL_PREV — AVL tree routines

DESCRIPTION

AVL trees are a general purpose, self-balancing binary tree that can be used instead of the standard linked list interfaces — list_create(9F). AVL trees are particularly useful either when order is important or better lookup performance is required.

The AVL tree interfaces are identical in both userland and the kernel. For more general information on AVL trees, see libavl(3LIB). For more information on any of the functions defined here, please see the corresponding manual page in section 3AVL. Please note, that while the descriptions in those manual pages are accurate for writers of Device Drivers, the examples provided use scaffolding not available in the kernel, such as the use of malloc(), and need to be adapted.

CONTEXT

All of the AVL routines may be used in user, kernel, and interrupt context.

EXAMPLES

See EXAMPLES in libavl(3LIB).

INTERFACE STABILITY

Committed

MT-Safety

AVL trees do not inherently have any internal locking, it is up to the consumer to use locks as appropriate. See mutex(9F) and rwlock(9F) for more information on synchronization primitives.