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