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