Debian Codegraph @

upstream/fedora-44/man3/tsearch.3

raw
1 '\" t
2 .\" Copyright 1995 by Jim Van Zandt <[email protected]>
3 .\"
4 .\" SPDX-License-Identifier: Linux-man-pages-copyleft
5 .\"
6 .TH tsearch 3 2024-12-13 "Linux man-pages 6.13"
7 .SH NAME
8 tsearch, tfind, tdelete, twalk, twalk_r, tdestroy \- manage a binary search tree
9 .SH LIBRARY
10 Standard C library
11 .RI ( libc ,\~ \-lc )
12 .SH SYNOPSIS
13 .nf
14 .B #include <search.h>
15 .P
16 .B typedef enum { preorder, postorder, endorder, leaf } VISIT;
17 .P
18 .BI "void *tfind(const void *" key ", void *const *" rootp ,
19 .BI " typeof(int (const void *, const void *)) *" compar );
20 .BI "void *tsearch(const void *" key ", void **" rootp ,
21 .BI " typeof(int (const void *, const void *)) *" compar );
22 .BI "void *tdelete(const void *restrict " key ", void **restrict " rootp ,
23 .BI " typeof(int (const void *, const void *)) *" compar );
24 .BI "void twalk(const void *" root ,
25 .BI " typeof(void (const void *" nodep ", VISIT " which ", int " depth ))
26 .BI " *" action );
27 .P
28 .BR "#define _GNU_SOURCE" " /* See feature_test_macros(7) */"
29 .B #include <search.h>
30 .P
31 .BI "void twalk_r(const void *" root ,
32 .BI " typeof(void (const void *" nodep ", VISIT " which ", void *" closure ))
33 .BI " *" action ,
34 .BI " void *" closure );
35 .BI "void tdestroy(void *" root ,
36 .BI " typeof(void (void *" nodep ")) *" free_node );
37 .fi
38 .SH DESCRIPTION
39 .BR tsearch (),
40 .BR tfind (),
41 .BR twalk (),
42 and
43 .BR tdelete ()
44 manage a
45 binary search tree.
46 They are generalized from Knuth (6.2.2) Algorithm T.
47 The first field in each node of the tree is a pointer to the
48 corresponding data item.
49 (The calling program must store the actual data.)
50 .I compar
51 points to a comparison routine, which takes
52 pointers to two items.
53 It should return an integer which is negative,
54 zero, or positive, depending on whether the first item is less than,
55 equal to, or greater than the second.
56 .P
57 .BR tsearch ()
58 searches the tree for an item.
59 .I key
60 points to the item to be searched for.
61 .I rootp
62 points to a variable which points to the root of the tree.
63 If the tree is empty,
64 then the variable that
65 .I rootp
66 points to should be set to NULL.
67 If the item is found in the tree, then
68 .BR tsearch ()
69 returns a pointer
70 to the corresponding tree node.
71 (In other words,
72 .BR tsearch ()
73 returns a pointer to a pointer to the data item.)
74 If the item is not found, then
75 .BR tsearch ()
76 adds it, and returns a
77 pointer to the corresponding tree node.
78 .P
79 .BR tfind ()
80 is like
81 .BR tsearch (),
82 except that if the item is not
83 found, then
84 .BR tfind ()
85 returns NULL.
86 .P
87 .BR tdelete ()
88 deletes an item from the tree.
89 Its arguments are the same as for
90 .BR tsearch ().
91 .P
92 .BR twalk ()
93 performs depth-first, left-to-right traversal of a binary
94 tree.
95 .I root
96 points to the starting node for the traversal.
97 If that node is not the root, then only part of the tree will be visited.
98 .BR twalk ()
99 calls the user function
100 .I action
101 each time a node is
102 visited (that is, three times for an internal node, and once for a
103 leaf).
104 .IR action ,
105 in turn, takes three arguments.
106 The first argument is a pointer to the node being visited.
107 The structure of the node is unspecified,
108 but it is possible to cast the pointer to a pointer-to-pointer-to-element
109 in order to access the element stored within the node.
110 The application must not modify the structure pointed to by this argument.
111 The second argument is an integer which
112 takes one of the values
113 .BR preorder ,
114 .BR postorder ,
115 or
116 .B endorder
117 depending on whether this is the first, second, or
118 third visit to the internal node,
119 or the value
120 .B leaf
121 if this is the single visit to a leaf node.
122 (These symbols are defined in
123 .IR <search.h> .)
124 The third argument is the depth of the node;
125 the root node has depth zero.
126 .P
127 (More commonly,
128 .BR preorder ,
129 .BR postorder ,
130 and
131 .B endorder
132 are known as
133 .BR preorder ,
134 .BR inorder ,
135 and
136 .BR postorder :
137 before visiting the children, after the first and before the second,
138 and after visiting the children.
139 Thus, the choice of name
140 .B post\%order
141 is rather confusing.)
142 .P
143 .BR twalk_r ()
144 is similar to
145 .BR twalk (),
146 but instead of the
147 .I depth
148 argument, the
149 .I closure
150 argument pointer is passed to each invocation of the action callback,
151 unchanged.
152 This pointer can be used to pass information to and from
153 the callback function in a thread-safe fashion, without resorting
154 to global variables.
155 .P
156 .BR tdestroy ()
157 removes the whole tree pointed to by
158 .IR root ,
159 freeing all resources allocated by the
160 .BR tsearch ()
161 function.
162 For the data in each tree node the function
163 .I free_node
164 is called.
165 The pointer to the data is passed as the argument to the function.
166 If no such work is necessary,
167 .I free_node
168 must point to a function
169 doing nothing.
170 .SH RETURN VALUE
171 .BR tsearch ()
172 returns a pointer to a matching node in the tree, or to
173 the newly added node, or NULL if there was insufficient memory
174 to add the item.
175 .BR tfind ()
176 returns a pointer to the node, or
177 NULL if no match is found.
178 If there are multiple items that match the key,
179 the item whose node is returned is unspecified.
180 .P
181 .BR tdelete ()
182 returns a pointer to the parent of the node deleted, or
183 NULL if the item was not found.
184 If the deleted node was the root node,
185 .BR tdelete ()
186 returns a dangling pointer that must not be accessed.
187 .P
188 .BR tsearch (),
189 .BR tfind (),
190 and
191 .BR tdelete ()
192 also
193 return NULL if
194 .I rootp
195 was NULL on entry.
196 .SH ATTRIBUTES
197 For an explanation of the terms used in this section, see
198 .BR attributes (7).
199 .TS
200 allbox;
201 lbx lb lb
202 l l l.
203 Interface Attribute Value
204 T{
205 .na
206 .nh
207 .BR tsearch (),
208 .BR tfind (),
209 .BR tdelete ()
210 T} Thread safety MT-Safe race:rootp
211 T{
212 .na
213 .nh
214 .BR twalk ()
215 T} Thread safety MT-Safe race:root
216 T{
217 .na
218 .nh
219 .BR twalk_r ()
220 T} Thread safety MT-Safe race:root
221 T{
222 .na
223 .nh
224 .BR tdestroy ()
225 T} Thread safety MT-Safe
226 .TE
227 .SH STANDARDS
228 .TP
229 .BR tsearch ()
230 .TQ
231 .BR tfind ()
232 .TQ
233 .BR tdelete ()
234 .TQ
235 .BR twalk ()
236 POSIX.1-2008.
237 .TP
238 .BR tdestroy ()
239 .TQ
240 .BR twalk_r ()
241 GNU.
242 .SH HISTORY
243 .TP
244 .BR tsearch ()
245 .TQ
246 .BR tfind ()
247 .TQ
248 .BR tdelete ()
249 .TQ
250 .BR twalk ()
251 POSIX.1-2001, POSIX.1-2008, SVr4.
252 .TP
253 .BR twalk_r ()
254 glibc 2.30.
255 .SH NOTES
256 .BR twalk ()
257 takes a pointer to the root, while the other functions
258 take a pointer to a variable which points to the root.
259 .P
260 .BR tdelete ()
261 frees the memory required for the node in the tree.
262 The user is responsible for freeing the memory for the corresponding
263 data.
264 .P
265 The example program depends on the fact that
266 .BR twalk ()
267 makes no
268 further reference to a node after calling the user function with
269 argument "endorder" or "leaf".
270 This works with the GNU library
271 implementation, but is not in the System V documentation.
272 .SH EXAMPLES
273 The following program inserts twelve random numbers into a binary
274 tree, where duplicate numbers are collapsed, then prints the numbers
275 in order.
276 .P
277 .\" SRC BEGIN (tsearch.c)
278 .EX
279 #define _GNU_SOURCE /* Expose declaration of tdestroy() */
280 #include <search.h>
281 #include <stddef.h>
282 #include <stdio.h>
283 #include <stdlib.h>
284 #include <time.h>
285 \&
286 static void *root = NULL;
287 \&
288 static void *
289 xmalloc(size_t n)
290 {
291 void *p;
292 \&
293 p = malloc(n);
294 if (p)
295 return p;
296 fprintf(stderr, "insufficient memory\[rs]n");
297 exit(EXIT_FAILURE);
298 }
299 \&
300 static int
301 compare(const void *pa, const void *pb)
302 {
303 if (*(int *) pa < *(int *) pb)
304 return \-1;
305 if (*(int *) pa > *(int *) pb)
306 return 1;
307 return 0;
308 }
309 \&
310 static void
311 action(const void *nodep, VISIT which, int depth)
312 {
313 int *datap;
314 \&
315 switch (which) {
316 case preorder:
317 break;
318 case postorder:
319 datap = *(int **) nodep;
320 printf("%6d\[rs]n", *datap);
321 break;
322 case endorder:
323 break;
324 case leaf:
325 datap = *(int **) nodep;
326 printf("%6d\[rs]n", *datap);
327 break;
328 }
329 }
330 \&
331 int
332 main(void)
333 {
334 int *ptr;
335 int **val;
336 \&
337 srand(time(NULL));
338 for (unsigned int i = 0; i < 12; i++) {
339 ptr = xmalloc(sizeof(*ptr));
340 *ptr = rand() & 0xff;
341 val = tsearch(ptr, &root, compare);
342 if (val == NULL)
343 exit(EXIT_FAILURE);
344 if (*val != ptr)
345 free(ptr);
346 }
347 twalk(root, action);
348 tdestroy(root, free);
349 exit(EXIT_SUCCESS);
350 }
351 .EE
352 .\" SRC END
353 .SH SEE ALSO
354 .BR bsearch (3),
355 .BR hsearch (3),
356 .BR lsearch (3),
357 .BR qsort (3)