1.\" 2.\" This file and its contents are supplied under the terms of the 3.\" Common Development and Distribution License ("CDDL"), version 1.0. 4.\" You may only use this file in accordance with the terms of version 5.\" 1.0 of the CDDL. 6.\" 7.\" A full copy of the text of the CDDL should have accompanied this 8.\" source. A copy of the CDDL is also available via the Internet at 9.\" http://www.illumos.org/license/CDDL. 10.\" 11.\" 12.\" Copyright 2015 Joyent, Inc. 13.\" 14.Dd May 07, 2015 15.Dt AVL_INSERT 3AVL 16.Os 17.Sh NAME 18.Nm avl_insert , 19.Nm avl_insert_here 20.Nd insert items into an AVL tree 21.Sh SYNOPSIS 22.Lb libavl 23.In sys/avl.h 24.Ft void 25.Fo avl_insert 26.Fa "avl_tree_t *tree" 27.Fa "void *new" 28.Fa "avl_index_t where" 29.Fc 30.Ft void 31.Fo avl_insert_here 32.Fa "avl_tree_t *tree" 33.Fa "void *new" 34.Fa "void *here" 35.Fa "int direction" 36.Fc 37.Sh DESCRIPTION 38The 39.Fn avl_insert 40and 41.Fn avl_insert_here 42functions are used to add the entry 43.Fa new 44to the tree rooted at 45.Fa tree . 46.Pp 47The 48.Fn avl_insert 49function uses the 50.Fa where 51value, obtained from a call to 52.Xr avl_find 3AVL , 53to determine where to insert the new entry into the tree. The tree must 54not have been modified in between the call to 55.Xr avl_find 3AVL 56and the call to 57.Fn avl_insert . 58If callers are not using 59.Xr avl_find 3AVL 60to validate the presence of 61.Fa new 62in the tree and only immediately insert it, then 63.Xr avl_add 3AVL 64may be used instead. 65.Pp 66The 67.Fn avl_insert_here 68function is for consumers who are keeping track of recently accessed 69data and wish to avoid an additional call to 70.Xr avl_find 3AVL . 71The new entry, 72.Fa new , 73will be inserted starting at the node 74.Fa here , 75which must already exist in the tree. To insert the node in the tree 76before 77.Fa here , 78then the argument 79.Fa direction 80should have the value 81.Dv AVL_BEFORE . 82Otherwise, to indicate that the new entry should be inserted after 83.Fa here , 84then 85.Fa direction 86should be set to 87.Dv AVL_AFTER . 88It is illegal to set 89.Fa direction 90to anything other than 91.Dv AVL_BEFORE 92or 93.Dv AVL_AFTER . 94If this is done, the behavior is not defined. 95.Sh EXAMPLES 96See the 97.Sy EXAMPLES 98section in 99.Xr libavl 3LIB . 100.Sh INTERFACE STABILITY 101.Sy Committed 102.Sh MT-Level 103See 104.Sx Locking 105in 106.Xr libavl 3LIB . 107.Sh SEE ALSO 108.Xr avl_add 3AVL , 109.Xr avl_find 3AVL , 110.Xr libavl 3LIB 111