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