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