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_FIND 3AVL 16.Os 17.Sh NAME 18.Nm avl_find 19.Nd find a node in an AVL tree 20.Sh SYNOPSIS 21.Lb libavl 22.In sys/avl.h 23.Ft void * 24.Fo avl_find 25.Fa "avl_tree_t *tree" 26.Fa "const void *node" 27.Fa "avl_index_t *where" 28.Fc 29.Sh DESCRIPTION 30The 31.Fn avl_find 32function is used to look up a node in the tree rooted at 33.Fa tree . 34.Pp 35To perform a lookup, a caller should construct an instance of the data 36structure, the argument 37.Fa node . 38.Fn avl_find 39searches through the tree for a node which compares equal to the passed 40in 41.Fa node 42using the comparison function specified when the tree was created with 43.Xr avl_create 3AVL . 44The only fields of 45.Fa node 46that need to be initialized are those that the comparison function will 47use, the others may remain uninitialized. 48.Pp 49If a match exists in the tree, then that entry will be returned. 50Otherwise, 51.Sy NULL 52is returned. 53.Pp 54If 55.Fa node 56does not match anything in the tree and the value of 57.Fa where 58is a 59.Pf non- Sy NULL 60pointer, then 61.Fa where 62will be updated to a value that can be used with both 63.Xr avl_insert 3AVL 64and 65.Xr avl_nearest 3AVL . 66This value is only valid as long as the tree is not modified. If 67anything is added or removed from the tree, then the value of 68.Fa where 69is no longer valid. This is commonly used as part of a pattern to see if 70something that should be added to the tree already exists, and if not, 71insert it. For more information, see the examples in 72.Xr libavl 3LIB . 73.Pp 74If the lookup is successful, then the contents of 75.Fa where 76are undefined. 77.Sh RETURN VALUES 78If 79.Fa node 80matches an entry in the tree, the matching entry is returned. Otherwise, 81.Sy NULL 82is returned and if 83.Fa where 84is 85.Pf non- Sy NULL , 86it is updated to point to a location in the tree. 87.Sh EXAMPLES 88See the 89.Sy EXAMPLES 90section in 91.Xr libavl 3LIB . 92.Sh INTERFACE STABILITY 93.Sy Committed 94.Sh MT-Level 95See 96.Sx Locking 97in 98.Xr libavl 3LIB . 99.Sh SEE ALSO 100.Xr libavl 3LIB , 101.Xr avl_create 3AVL , 102.Xr avl_insert 3AVL , 103.Xr avl_nearest 3AVL 104