.\"
.\" This file and its contents are supplied under the terms of the
.\" Common Development and Distribution License ("CDDL"), version 1.0.
.\" You may only use this file in accordance with the terms of version
.\" 1.0 of the CDDL.
.\"
.\" A full copy of the text of the CDDL should have accompanied this
.\" source.  A copy of the CDDL is also available via the Internet at
.\" http://www.illumos.org/license/CDDL.
.\"
.\"
.\" Copyright 2016 Joyent, Inc.
.\" Copyright 2024 Oxide Computer Company
.\"
.Dd Feb 27, 2024
.Dt AVL 9F
.Os
.Sh NAME
.Nm avl ,
.Nm avl_add ,
.Nm avl_create ,
.Nm avl_destroy ,
.Nm avl_destroy_nodes ,
.Nm avl_find  ,
.Nm avl_first ,
.Nm avl_insert ,
.Nm avl_insert_here ,
.Nm avl_is_empty ,
.Nm avl_last ,
.Nm avl_nearest ,
.Nm avl_numnodes ,
.Nm avl_remove ,
.Nm avl_swap ,
.Nm avl_update ,
.Nm avl_update_gt ,
.Nm avl_update_lt ,
.Nm AVL_NEXT ,
.Nm AVL_PREV
.Nd AVL tree routines
.Sh DESCRIPTION
AVL trees are a general purpose, self-balancing binary tree that can be
used instead of the standard linked list interfaces \(em
.Xr list_create 9F .
AVL trees are particularly useful either when order is important or
better lookup performance is required.
.Pp
The AVL tree interfaces are identical in both userland and the kernel.
For more general information on AVL trees, see
.Xr 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
.Fn malloc ,
and need to be adapted.
.Sh CONTEXT
All of the AVL routines may be used in user, kernel, and interrupt
context.
.Sh EXAMPLES
See
.Sy EXAMPLES
in
.Xr libavl 3LIB .
.Sh INTERFACE STABILITY
.Sy Committed
.Sh MT-Safety
AVL trees do not inherently have any internal locking, it is up to the
consumer to use locks as appropriate.
See
.Xr mutex 9F
and
.Xr rwlock 9F
for more information on synchronization primitives.
.Sh SEE ALSO
.Xr avl_add 3AVL ,
.Xr avl_create 3AVL ,
.Xr avl_destroy 3AVL ,
.Xr avl_destroy_nodes 3AVL ,
.Xr avl_find  3AVL ,
.Xr avl_first 3AVL ,
.Xr avl_insert 3AVL ,
.Xr avl_insert_here 3AVL ,
.Xr avl_is_empty 3AVL ,
.Xr avl_last 3AVL ,
.Xr avl_nearest 3AVL ,
.Xr AVL_NEXT 3AVL ,
.Xr avl_numnodes 3AVL ,
.Xr AVL_PREV 3AVL ,
.Xr avl_remove 3AVL ,
.Xr avl_swap 3AVL ,
.Xr avl_update 3AVL ,
.Xr avl_update_gt 3AVL ,
.Xr avl_update_lt 3AVL ,
.Xr libavl 3LIB
.Rs
.%T Writing Device Drivers
.Re