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 Apr 13, 2015 15*fa9922c2SRobert Mustacchi.Dt AVL_ADD 3AVL 16*fa9922c2SRobert Mustacchi.Os 17*fa9922c2SRobert Mustacchi.Sh NAME 18*fa9922c2SRobert Mustacchi.Nm avl_add , 19*fa9922c2SRobert Mustacchi.Nm avl_remove 20*fa9922c2SRobert Mustacchi.Nd add and remove nodes from an AVL tree 21*fa9922c2SRobert Mustacchi.Sh SYNOPSIS 22*fa9922c2SRobert Mustacchi.Lb libavl 23*fa9922c2SRobert Mustacchi.In sys/avl.h 24*fa9922c2SRobert Mustacchi.Ft void 25*fa9922c2SRobert Mustacchi.Fo avl_add 26*fa9922c2SRobert Mustacchi.Fa "avl_tree_t *tree" 27*fa9922c2SRobert Mustacchi.Fa "void *node" 28*fa9922c2SRobert Mustacchi.Fc 29*fa9922c2SRobert Mustacchi.Ft void 30*fa9922c2SRobert Mustacchi.Fo avl_remove 31*fa9922c2SRobert Mustacchi.Fa "avl_tree_t *tree" 32*fa9922c2SRobert Mustacchi.Fa "void *node" 33*fa9922c2SRobert Mustacchi.Fc 34*fa9922c2SRobert Mustacchi.Sh DESCRIPTION 35*fa9922c2SRobert MustacchiThe 36*fa9922c2SRobert Mustacchi.Fn avl_add 37*fa9922c2SRobert Mustacchiand 38*fa9922c2SRobert Mustacchi.Fn avl_remove 39*fa9922c2SRobert Mustacchifunctions add and remove objects from the AVL tree rooted at 40*fa9922c2SRobert Mustacchi.Fa tree . 41*fa9922c2SRobert Mustacchi.Pp 42*fa9922c2SRobert MustacchiThe 43*fa9922c2SRobert Mustacchi.Fn avl_add 44*fa9922c2SRobert Mustacchifunction inserts 45*fa9922c2SRobert Mustacchi.Fa node 46*fa9922c2SRobert Mustacchiinto the tree. 47*fa9922c2SRobert Mustacchi.Fa node 48*fa9922c2SRobert Mustacchimust not already be in the tree, thus implying it must not compare equal 49*fa9922c2SRobert Mustacchito any other node in the tree. Adding 50*fa9922c2SRobert Mustacchi.Fa node 51*fa9922c2SRobert Mustacchito 52*fa9922c2SRobert Mustacchi.Fa tree 53*fa9922c2SRobert Mustacchiwill take 54*fa9922c2SRobert Mustacchi.Sy O(log(n)) 55*fa9922c2SRobert Mustacchitime, as it implicitly determines where to place it in the tree. 56*fa9922c2SRobert MustacchiIf 57*fa9922c2SRobert Mustacchi.Fa node Ns 's 58*fa9922c2SRobert Mustacchilocation has already been determined by 59*fa9922c2SRobert Mustacchi.Xr avl_find 3AVL , 60*fa9922c2SRobert Mustacchithen instead use 61*fa9922c2SRobert Mustacchi.Xr avl_insert 3AVL . 62*fa9922c2SRobert Mustacchi.Pp 63*fa9922c2SRobert MustacchiThe 64*fa9922c2SRobert Mustacchi.Fn avl_remove 65*fa9922c2SRobert Mustacchifunction removes 66*fa9922c2SRobert Mustacchi.Fa node 67*fa9922c2SRobert Mustacchifrom the tree rooted at 68*fa9922c2SRobert Mustacchi.Fa tree . 69*fa9922c2SRobert Mustacchi.Fa node 70*fa9922c2SRobert Mustacchimust be present in the tree, otherwise, the behavior is undefined. 71*fa9922c2SRobert MustacchiDeleting 72*fa9922c2SRobert Mustacchi.Fa node 73*fa9922c2SRobert Mustacchifrom 74*fa9922c2SRobert Mustacchi.Fa tree 75*fa9922c2SRobert Mustacchioccurs in 76*fa9922c2SRobert Mustacchi.Sy O(log(n)) 77*fa9922c2SRobert Mustacchitime. 78*fa9922c2SRobert Mustacchi.Sh EXAMPLES 79*fa9922c2SRobert MustacchiSee the 80*fa9922c2SRobert Mustacchi.Sy EXAMPLES 81*fa9922c2SRobert Mustacchisection in 82*fa9922c2SRobert Mustacchi.Xr libavl 3LIB . 83*fa9922c2SRobert Mustacchi.Sh INTERFACE STABILITY 84*fa9922c2SRobert Mustacchi.Sy Committed 85*fa9922c2SRobert Mustacchi.Sh MT-Level 86*fa9922c2SRobert MustacchiSee 87*fa9922c2SRobert Mustacchi.Sx Locking 88*fa9922c2SRobert Mustacchiin 89*fa9922c2SRobert Mustacchi.Xr libavl 3LIB . 90*fa9922c2SRobert Mustacchi.Sh SEE ALSO 91*fa9922c2SRobert Mustacchi.Xr libavl 3LIB , 92*fa9922c2SRobert Mustacchi.Xr avl_create 3AVL , 93*fa9922c2SRobert Mustacchi.Xr avl_insert 3AVL , 94*fa9922c2SRobert Mustacchi.Xr avl_insert_here 3AVL , 95*fa9922c2SRobert Mustacchi.Xr avl_destroy 3AVL 96