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