xref: /illumos-gate/usr/src/man/man3avl/avl_find.3avl (revision 15a0c3a7ba78a992f7bad7c25b74c4a6b91b7ff4)
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