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. 67If anything is added or removed from the tree, then the value of 68.Fa where 69is no longer valid. 70This is commonly used as part of a pattern to see if something that should be 71added to the tree already exists, and if not, insert it. 72For more information, see the examples in 73.Xr libavl 3LIB . 74.Pp 75If the lookup is successful, then the contents of 76.Fa where 77are undefined. 78.Sh RETURN VALUES 79If 80.Fa node 81matches an entry in the tree, the matching entry is returned. 82Otherwise, 83.Sy NULL 84is returned and if 85.Fa where 86is 87.Pf non- Sy NULL , 88it is updated to point to a location in the tree. 89.Sh EXAMPLES 90See the 91.Sy EXAMPLES 92section in 93.Xr libavl 3LIB . 94.Sh INTERFACE STABILITY 95.Sy Committed 96.Sh MT-Level 97See 98.Sx Locking 99in 100.Xr libavl 3LIB . 101.Sh SEE ALSO 102.Xr avl_create 3AVL , 103.Xr avl_insert 3AVL , 104.Xr avl_nearest 3AVL , 105.Xr libavl 3LIB 106