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