1fa9922c2SRobert Mustacchi.\" 2fa9922c2SRobert Mustacchi.\" This file and its contents are supplied under the terms of the 3fa9922c2SRobert Mustacchi.\" Common Development and Distribution License ("CDDL"), version 1.0. 4fa9922c2SRobert Mustacchi.\" You may only use this file in accordance with the terms of version 5fa9922c2SRobert Mustacchi.\" 1.0 of the CDDL. 6fa9922c2SRobert Mustacchi.\" 7fa9922c2SRobert Mustacchi.\" A full copy of the text of the CDDL should have accompanied this 8fa9922c2SRobert Mustacchi.\" source. A copy of the CDDL is also available via the Internet at 9fa9922c2SRobert Mustacchi.\" http://www.illumos.org/license/CDDL. 10fa9922c2SRobert Mustacchi.\" 11fa9922c2SRobert Mustacchi.\" 12a6ae0091SRobert Mustacchi.\" Copyright 2016 Joyent, Inc. 13*7a87437fSAndy Fiddaman.\" Copyright 2024 Oxide Computer Company 14fa9922c2SRobert Mustacchi.\" 15*7a87437fSAndy Fiddaman.Dd Feb 27, 2024 16fa9922c2SRobert Mustacchi.Dt AVL 9F 17fa9922c2SRobert Mustacchi.Os 18fa9922c2SRobert Mustacchi.Sh NAME 19fa9922c2SRobert Mustacchi.Nm avl , 20fa9922c2SRobert Mustacchi.Nm avl_add , 21fa9922c2SRobert Mustacchi.Nm avl_create , 22fa9922c2SRobert Mustacchi.Nm avl_destroy , 23fa9922c2SRobert Mustacchi.Nm avl_destroy_nodes , 24fa9922c2SRobert Mustacchi.Nm avl_find , 25fa9922c2SRobert Mustacchi.Nm avl_first , 26fa9922c2SRobert Mustacchi.Nm avl_insert , 27fa9922c2SRobert Mustacchi.Nm avl_insert_here , 28fa9922c2SRobert Mustacchi.Nm avl_is_empty , 29fa9922c2SRobert Mustacchi.Nm avl_last , 30fa9922c2SRobert Mustacchi.Nm avl_nearest , 31fa9922c2SRobert Mustacchi.Nm avl_numnodes , 32a6ae0091SRobert Mustacchi.Nm avl_remove , 33fa9922c2SRobert Mustacchi.Nm avl_swap , 34*7a87437fSAndy Fiddaman.Nm avl_update , 35*7a87437fSAndy Fiddaman.Nm avl_update_gt , 36*7a87437fSAndy Fiddaman.Nm avl_update_lt , 37fa9922c2SRobert Mustacchi.Nm AVL_NEXT , 3872d3dbb9SYuri Pankov.Nm AVL_PREV 39fa9922c2SRobert Mustacchi.Nd AVL tree routines 40fa9922c2SRobert Mustacchi.Sh DESCRIPTION 41fa9922c2SRobert MustacchiAVL trees are a general purpose, self-balancing binary tree that can be 42*7a87437fSAndy Fiddamanused instead of the standard linked list interfaces \(em 43fa9922c2SRobert Mustacchi.Xr list_create 9F . 44fa9922c2SRobert MustacchiAVL trees are particularly useful either when order is important or 45fa9922c2SRobert Mustacchibetter lookup performance is required. 46fa9922c2SRobert Mustacchi.Pp 47fa9922c2SRobert MustacchiThe AVL tree interfaces are identical in both userland and the kernel. 48fa9922c2SRobert MustacchiFor more general information on AVL trees, see 49fa9922c2SRobert Mustacchi.Xr libavl 3LIB . 50*7a87437fSAndy FiddamanFor more information on any of the functions defined here, please see the 5172d3dbb9SYuri Pankovcorresponding manual page in section 3AVL. 5272d3dbb9SYuri PankovPlease note, that while the descriptions in those manual pages are accurate for 5372d3dbb9SYuri Pankovwriters of Device Drivers, the examples provided use scaffolding not available 5472d3dbb9SYuri Pankovin the kernel, such as the use of 55fa9922c2SRobert Mustacchi.Fn malloc , 56*7a87437fSAndy Fiddamanand need to be adapted. 57fa9922c2SRobert Mustacchi.Sh CONTEXT 58fa9922c2SRobert MustacchiAll of the AVL routines may be used in user, kernel, and interrupt 59fa9922c2SRobert Mustacchicontext. 60fa9922c2SRobert Mustacchi.Sh EXAMPLES 61fa9922c2SRobert MustacchiSee 62fa9922c2SRobert Mustacchi.Sy EXAMPLES 63fa9922c2SRobert Mustacchiin 64fa9922c2SRobert Mustacchi.Xr libavl 3LIB . 65fa9922c2SRobert Mustacchi.Sh INTERFACE STABILITY 66fa9922c2SRobert Mustacchi.Sy Committed 67fa9922c2SRobert Mustacchi.Sh MT-Safety 68fa9922c2SRobert MustacchiAVL trees do not inherently have any internal locking, it is up to the 6972d3dbb9SYuri Pankovconsumer to use locks as appropriate. 7072d3dbb9SYuri PankovSee 71fa9922c2SRobert Mustacchi.Xr mutex 9F 72fa9922c2SRobert Mustacchiand 73fa9922c2SRobert Mustacchi.Xr rwlock 9F 74fa9922c2SRobert Mustacchifor more information on synchronization primitives. 75fa9922c2SRobert Mustacchi.Sh SEE ALSO 76fa9922c2SRobert Mustacchi.Xr avl_add 3AVL , 77fa9922c2SRobert Mustacchi.Xr avl_create 3AVL , 78fa9922c2SRobert Mustacchi.Xr avl_destroy 3AVL , 79fa9922c2SRobert Mustacchi.Xr avl_destroy_nodes 3AVL , 80fa9922c2SRobert Mustacchi.Xr avl_find 3AVL , 81fa9922c2SRobert Mustacchi.Xr avl_first 3AVL , 82fa9922c2SRobert Mustacchi.Xr avl_insert 3AVL , 83fa9922c2SRobert Mustacchi.Xr avl_insert_here 3AVL , 84fa9922c2SRobert Mustacchi.Xr avl_is_empty 3AVL , 85fa9922c2SRobert Mustacchi.Xr avl_last 3AVL , 86fa9922c2SRobert Mustacchi.Xr avl_nearest 3AVL , 87fa9922c2SRobert Mustacchi.Xr AVL_NEXT 3AVL , 883a005aadSYuri Pankov.Xr avl_numnodes 3AVL , 89fa9922c2SRobert Mustacchi.Xr AVL_PREV 3AVL , 90a6ae0091SRobert Mustacchi.Xr avl_remove 3AVL , 913a005aadSYuri Pankov.Xr avl_swap 3AVL , 92*7a87437fSAndy Fiddaman.Xr avl_update 3AVL , 93*7a87437fSAndy Fiddaman.Xr avl_update_gt 3AVL , 94*7a87437fSAndy Fiddaman.Xr avl_update_lt 3AVL , 953a005aadSYuri Pankov.Xr libavl 3LIB 96fa9922c2SRobert Mustacchi.Rs 97fa9922c2SRobert Mustacchi.%T Writing Device Drivers 98fa9922c2SRobert Mustacchi.Re 99