Debian Codegraph @

upstream/debian-unstable/man3/tsearch.3

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