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 May 07, 2015 15*d9fc8ba6SRobert Mustacchi.Dt AVL_INSERT 3AVL 16*d9fc8ba6SRobert Mustacchi.Os 17*d9fc8ba6SRobert Mustacchi.Sh NAME 18*d9fc8ba6SRobert Mustacchi.Nm avl_insert , 19*d9fc8ba6SRobert Mustacchi.Nm avl_insert_here 20*d9fc8ba6SRobert Mustacchi.Nd insert items into 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_insert 26*d9fc8ba6SRobert Mustacchi.Fa "avl_tree_t *tree" 27*d9fc8ba6SRobert Mustacchi.Fa "void *new" 28*d9fc8ba6SRobert Mustacchi.Fa "avl_index_t where" 29*d9fc8ba6SRobert Mustacchi.Fc 30*d9fc8ba6SRobert Mustacchi.Ft void 31*d9fc8ba6SRobert Mustacchi.Fo avl_insert_here 32*d9fc8ba6SRobert Mustacchi.Fa "avl_tree_t *tree" 33*d9fc8ba6SRobert Mustacchi.Fa "void *new" 34*d9fc8ba6SRobert Mustacchi.Fa "void *here" 35*d9fc8ba6SRobert Mustacchi.Fa "int direction" 36*d9fc8ba6SRobert Mustacchi.Fc 37*d9fc8ba6SRobert Mustacchi.Sh DESCRIPTION 38*d9fc8ba6SRobert MustacchiThe 39*d9fc8ba6SRobert Mustacchi.Fn avl_insert 40*d9fc8ba6SRobert Mustacchiand 41*d9fc8ba6SRobert Mustacchi.Fn avl_insert_here 42*d9fc8ba6SRobert Mustacchifunctions are used to add the entry 43*d9fc8ba6SRobert Mustacchi.Fa new 44*d9fc8ba6SRobert Mustacchito the tree rooted at 45*d9fc8ba6SRobert Mustacchi.Fa tree . 46*d9fc8ba6SRobert Mustacchi.Pp 47*d9fc8ba6SRobert MustacchiThe 48*d9fc8ba6SRobert Mustacchi.Fn avl_insert 49*d9fc8ba6SRobert Mustacchifunction uses the 50*d9fc8ba6SRobert Mustacchi.Fa where 51*d9fc8ba6SRobert Mustacchivalue, obtained from a call to 52*d9fc8ba6SRobert Mustacchi.Xr avl_find 3AVL , 53*d9fc8ba6SRobert Mustacchito determine where to insert the new entry into the tree. The tree must 54*d9fc8ba6SRobert Mustacchinot have been modified inbetween the call to 55*d9fc8ba6SRobert Mustacchi.Xr avl_find 3AVL 56*d9fc8ba6SRobert Mustacchiand the call to 57*d9fc8ba6SRobert Mustacchi.Fn avl_insert . 58*d9fc8ba6SRobert MustacchiIf callers are not using 59*d9fc8ba6SRobert Mustacchi.Xr avl_find 3AVL 60*d9fc8ba6SRobert Mustacchito validate the presence of 61*d9fc8ba6SRobert Mustacchi.Fa new 62*d9fc8ba6SRobert Mustacchiin the tree and only immediately insert it, then 63*d9fc8ba6SRobert Mustacchi.Xr avl_add 3AVL 64*d9fc8ba6SRobert Mustacchimay be used instead. 65*d9fc8ba6SRobert Mustacchi.Pp 66*d9fc8ba6SRobert MustacchiThe 67*d9fc8ba6SRobert Mustacchi.Fn avl_insert_here 68*d9fc8ba6SRobert Mustacchifunction is for consumers who are keeping track of recently accessed 69*d9fc8ba6SRobert Mustacchidata and wish to avoid an additional call to 70*d9fc8ba6SRobert Mustacchi.Xr avl_find 3AVL . 71*d9fc8ba6SRobert MustacchiThe new entry, 72*d9fc8ba6SRobert Mustacchi.Fa new , 73*d9fc8ba6SRobert Mustacchiwill be inserted starting at the node 74*d9fc8ba6SRobert Mustacchi.Fa here , 75*d9fc8ba6SRobert Mustacchiwhich must already exist in the tree. To insert the node in the tree 76*d9fc8ba6SRobert Mustacchibefore 77*d9fc8ba6SRobert Mustacchi.Fa here , 78*d9fc8ba6SRobert Mustacchithen the argument 79*d9fc8ba6SRobert Mustacchi.Fa direction 80*d9fc8ba6SRobert Mustacchishould have the value 81*d9fc8ba6SRobert Mustacchi.Dv AVL_BEFORE . 82*d9fc8ba6SRobert MustacchiOtherwise, to indicate that the new entry should be inserted after 83*d9fc8ba6SRobert Mustacchi.Fa here, 84*d9fc8ba6SRobert Mustacchithen 85*d9fc8ba6SRobert Mustacchi.Fa direction 86*d9fc8ba6SRobert Mustacchishould be set to 87*d9fc8ba6SRobert Mustacchi.Dv AVL_AFTER . 88*d9fc8ba6SRobert MustacchiIt is illegal to set 89*d9fc8ba6SRobert Mustacchi.Fa direction 90*d9fc8ba6SRobert Mustacchito anything other than 91*d9fc8ba6SRobert Mustacchi.Dv AVL_BEFORE 92*d9fc8ba6SRobert Mustacchior 93*d9fc8ba6SRobert Mustacchi.Dv AVL_AFTER . 94*d9fc8ba6SRobert MustacchiIf this is done, the behavior is not defined. 95*d9fc8ba6SRobert Mustacchi.Sh EXAMPLES 96*d9fc8ba6SRobert MustacchiSee the 97*d9fc8ba6SRobert Mustacchi.Sy EXAMPLES 98*d9fc8ba6SRobert Mustacchisection in 99*d9fc8ba6SRobert Mustacchi.Xr libavl 3LIB . 100*d9fc8ba6SRobert Mustacchi.Sh INTERFACE STABILITY 101*d9fc8ba6SRobert Mustacchi.Sy Committed 102*d9fc8ba6SRobert Mustacchi.Sh MT-Level 103*d9fc8ba6SRobert MustacchiSee 104*d9fc8ba6SRobert Mustacchi.Sx Locking 105*d9fc8ba6SRobert Mustacchiin 106*d9fc8ba6SRobert Mustacchi.Xr libavl 3LIB . 107*d9fc8ba6SRobert Mustacchi.Sh SEE ALSO 108*d9fc8ba6SRobert Mustacchi.Xr libavl 3LIB , 109*d9fc8ba6SRobert Mustacchi.Xr avl_add 3AVL , 110*d9fc8ba6SRobert Mustacchi.Xr avl_find 3AVL 111