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 2015 Joyent, Inc. 13.\" 14.Dd May 08, 2015 15.Dt AVL 9F 16.Os 17.Sh NAME 18.Nm avl , 19.Nm avl_add , 20.Nm avl_create , 21.Nm avl_destroy , 22.Nm avl_destroy_nodes , 23.Nm avl_find , 24.Nm avl_first , 25.Nm avl_insert , 26.Nm avl_insert_here , 27.Nm avl_is_empty , 28.Nm avl_last , 29.Nm avl_nearest , 30.Nm avl_numnodes , 31.Nm avl_swap , 32.Nm AVL_NEXT , 33.Nm AVL_PREV , 34.Nd AVL tree routines 35.Sh DESCRIPTION 36AVL trees are a general purpose, self-balancing binary tree that can be 37used instead of the standard linked list interfaces -- 38.Xr list_create 9F . 39AVL trees are particularly useful either when order is important or 40better lookup performance is required. 41.Pp 42The AVL tree interfaces are identical in both userland and the kernel. 43For more general information on AVL trees, see 44.Xr libavl 3LIB . 45For more information on any of the funtions defined here, please see the 46corresponding manual page in section 3AVL. Please note, that while 47the descriptions in those manual pages are accurate for writers of 48Device Drivers, the examples provided use scaffolding not available in 49the kernel, such as the use of 50.Fn malloc , 51and need to be adapated. 52.Sh CONTEXT 53All of the AVL routines may be used in user, kernel, and interrupt 54context. 55.Sh EXAMPLES 56See 57.Sy EXAMPLES 58in 59.Xr libavl 3LIB . 60.Sh INTERFACE STABILITY 61.Sy Committed 62.Sh MT-Safety 63AVL trees do not inherently have any internal locking, it is up to the 64consumer to use locks as appropriate. See 65.Xr mutex 9F 66and 67.Xr rwlock 9F 68for more information on synchronization primitives. 69.Sh SEE ALSO 70.Xr avl_add 3AVL , 71.Xr avl_create 3AVL , 72.Xr avl_destroy 3AVL , 73.Xr avl_destroy_nodes 3AVL , 74.Xr avl_find 3AVL , 75.Xr avl_first 3AVL , 76.Xr avl_insert 3AVL , 77.Xr avl_insert_here 3AVL , 78.Xr avl_is_empty 3AVL , 79.Xr avl_last 3AVL , 80.Xr avl_nearest 3AVL , 81.Xr AVL_NEXT 3AVL , 82.Xr avl_numnodes 3AVL , 83.Xr AVL_PREV 3AVL , 84.Xr avl_swap 3AVL , 85.Xr libavl 3LIB 86.Rs 87.%T Writing Device Drivers 88.Re 89