1*d9fc8ba6SRobert Mustacchi.\" 2*d9fc8ba6SRobert Mustacchi.\" This file and its contents are supplied under the terms of the 3*d9fc8ba6SRobert Mustacchi.\" Common Development and Distribution License ("CDDL"), version 1.0. 4*d9fc8ba6SRobert Mustacchi.\" You may only use this file in accordance with the terms of version 5*d9fc8ba6SRobert Mustacchi.\" 1.0 of the CDDL. 6*d9fc8ba6SRobert Mustacchi.\" 7*d9fc8ba6SRobert Mustacchi.\" A full copy of the text of the CDDL should have accompanied this 8*d9fc8ba6SRobert Mustacchi.\" source. A copy of the CDDL is also available via the Internet at 9*d9fc8ba6SRobert Mustacchi.\" http://www.illumos.org/license/CDDL. 10*d9fc8ba6SRobert Mustacchi.\" 11*d9fc8ba6SRobert Mustacchi.\" 12*d9fc8ba6SRobert Mustacchi.\" Copyright 2015 Joyent, Inc. 13*d9fc8ba6SRobert Mustacchi.\" 14*d9fc8ba6SRobert Mustacchi.Dd Apr 13, 2015 15*d9fc8ba6SRobert Mustacchi.Dt AVL_ADD 3AVL 16*d9fc8ba6SRobert Mustacchi.Os 17*d9fc8ba6SRobert Mustacchi.Sh NAME 18*d9fc8ba6SRobert Mustacchi.Nm avl_add , 19*d9fc8ba6SRobert Mustacchi.Nm avl_remove 20*d9fc8ba6SRobert Mustacchi.Nd add and remove nodes from an AVL tree 21*d9fc8ba6SRobert Mustacchi.Sh SYNOPSIS 22*d9fc8ba6SRobert Mustacchi.Lb libavl 23*d9fc8ba6SRobert Mustacchi.In sys/avl.h 24*d9fc8ba6SRobert Mustacchi.Ft void 25*d9fc8ba6SRobert Mustacchi.Fo avl_add 26*d9fc8ba6SRobert Mustacchi.Fa "avl_tree_t *tree" 27*d9fc8ba6SRobert Mustacchi.Fa "void *node" 28*d9fc8ba6SRobert Mustacchi.Fc 29*d9fc8ba6SRobert Mustacchi.Ft void 30*d9fc8ba6SRobert Mustacchi.Fo avl_remove 31*d9fc8ba6SRobert Mustacchi.Fa "avl_tree_t *tree" 32*d9fc8ba6SRobert Mustacchi.Fa "void *node" 33*d9fc8ba6SRobert Mustacchi.Fc 34*d9fc8ba6SRobert Mustacchi.Sh DESCRIPTION 35*d9fc8ba6SRobert MustacchiThe 36*d9fc8ba6SRobert Mustacchi.Fn avl_add 37*d9fc8ba6SRobert Mustacchiand 38*d9fc8ba6SRobert Mustacchi.Fn avl_remove 39*d9fc8ba6SRobert Mustacchifunctions add and remove objects from the AVL tree rooted at 40*d9fc8ba6SRobert Mustacchi.Fa tree . 41*d9fc8ba6SRobert Mustacchi.Pp 42*d9fc8ba6SRobert MustacchiThe 43*d9fc8ba6SRobert Mustacchi.Fn avl_add 44*d9fc8ba6SRobert Mustacchifunction inserts 45*d9fc8ba6SRobert Mustacchi.Fa node 46*d9fc8ba6SRobert Mustacchiinto the tree. 47*d9fc8ba6SRobert Mustacchi.Fa node 48*d9fc8ba6SRobert Mustacchimust not already be in the tree, thus implying it must not compare equal 49*d9fc8ba6SRobert Mustacchito any other node in the tree. Adding 50*d9fc8ba6SRobert Mustacchi.Fa node 51*d9fc8ba6SRobert Mustacchito 52*d9fc8ba6SRobert Mustacchi.Fa tree 53*d9fc8ba6SRobert Mustacchiwill take 54*d9fc8ba6SRobert Mustacchi.Sy O(log(n)) 55*d9fc8ba6SRobert Mustacchitime, as it implicitly determines where to place it in the tree. 56*d9fc8ba6SRobert MustacchiIf 57*d9fc8ba6SRobert Mustacchi.Fa node Ns 's 58*d9fc8ba6SRobert Mustacchilocation has already been determined by 59*d9fc8ba6SRobert Mustacchi.Xr avl_find 3AVL , 60*d9fc8ba6SRobert Mustacchithen instead use 61*d9fc8ba6SRobert Mustacchi.Xr avl_insert 3AVL . 62*d9fc8ba6SRobert Mustacchi.Pp 63*d9fc8ba6SRobert MustacchiThe 64*d9fc8ba6SRobert Mustacchi.Fn avl_remove 65*d9fc8ba6SRobert Mustacchifunction removes 66*d9fc8ba6SRobert Mustacchi.Fa node 67*d9fc8ba6SRobert Mustacchifrom the tree rooted at 68*d9fc8ba6SRobert Mustacchi.Fa tree . 69*d9fc8ba6SRobert Mustacchi.Fa node 70*d9fc8ba6SRobert Mustacchimust be present in the tree, otherwise, the behavior is undefined. 71*d9fc8ba6SRobert MustacchiDeleting 72*d9fc8ba6SRobert Mustacchi.Fa node 73*d9fc8ba6SRobert Mustacchifrom 74*d9fc8ba6SRobert Mustacchi.Fa tree 75*d9fc8ba6SRobert Mustacchioccurs in 76*d9fc8ba6SRobert Mustacchi.Sy O(log(n)) 77*d9fc8ba6SRobert Mustacchitime. 78*d9fc8ba6SRobert Mustacchi.Sh EXAMPLES 79*d9fc8ba6SRobert MustacchiSee the 80*d9fc8ba6SRobert Mustacchi.Sy EXAMPLES 81*d9fc8ba6SRobert Mustacchisection in 82*d9fc8ba6SRobert Mustacchi.Xr libavl 3LIB . 83*d9fc8ba6SRobert Mustacchi.Sh INTERFACE STABILITY 84*d9fc8ba6SRobert Mustacchi.Sy Committed 85*d9fc8ba6SRobert Mustacchi.Sh MT-Level 86*d9fc8ba6SRobert MustacchiSee 87*d9fc8ba6SRobert Mustacchi.Sx Locking 88*d9fc8ba6SRobert Mustacchiin 89*d9fc8ba6SRobert Mustacchi.Xr libavl 3LIB . 90*d9fc8ba6SRobert Mustacchi.Sh SEE ALSO 91*d9fc8ba6SRobert Mustacchi.Xr libavl 3LIB , 92*d9fc8ba6SRobert Mustacchi.Xr avl_create 3AVL , 93*d9fc8ba6SRobert Mustacchi.Xr avl_insert 3AVL , 94*d9fc8ba6SRobert Mustacchi.Xr avl_insert_here 3AVL , 95*d9fc8ba6SRobert Mustacchi.Xr avl_destroy 3AVL 96