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