2 .\" Copyright 1995 by Jim Van Zandt <jrv@vanzandt.mv.com>
4 .\" SPDX-License-Identifier: Linux-man-pages-copyleft
6 .TH tsearch 3 (date) "Linux man-pages (unreleased)"
8 tsearch, tfind, tdelete, twalk, twalk_r, tdestroy \- manage a binary search tree
11 .RI ( libc ", " \-lc )
14 .B #include <search.h>
16 .B typedef enum { preorder, postorder, endorder, leaf } VISIT;
18 .BI "void *tsearch(const void *" key ", void **" rootp ,
19 .BI " int (*" compar ")(const void *, const void *));"
20 .BI "void *tfind(const void *" key ", void *const *" rootp ,
21 .BI " int (*" compar ")(const void *, const void *));"
22 .BI "void *tdelete(const void *restrict " key ", void **restrict " rootp ,
23 .BI " int (*" compar ")(const void *, const void *));"
24 .BI "void twalk(const void *" root ,
25 .BI " void (*" action ")(const void *" nodep ", VISIT " which ,
28 .BR "#define _GNU_SOURCE" " /* See feature_test_macros(7) */"
29 .B #include <search.h>
31 .BI "void twalk_r(const void *" root ,
32 .BI " void (*" action ")(const void *" nodep ", VISIT " which ,
33 .BI " void *" closure ),
34 .BI " void *" closure );
35 .BI "void tdestroy(void *" root ", void (*" free_node ")(void *" nodep ));
45 They are generalized from Knuth (6.2.2) Algorithm T.
46 The first field in each node of the tree is a pointer to the
47 corresponding data item.
48 (The calling program must store the actual data.)
50 points to a comparison routine, which takes
51 pointers to two items.
52 It should return an integer which is negative,
53 zero, or positive, depending on whether the first item is less than,
54 equal to, or greater than the second.
57 searches the tree for an item.
59 points to the item to be searched for.
61 points to a variable which points to the root of the tree.
63 then the variable that
65 points to should be set to NULL.
66 If the item is found in the tree, then
69 to the corresponding tree node.
72 returns a pointer to a pointer to the data item.)
73 If the item is not found, then
75 adds it, and returns a
76 pointer to the corresponding tree node.
81 except that if the item is not
87 deletes an item from the tree.
88 Its arguments are the same as for
92 performs depth-first, left-to-right traversal of a binary
95 points to the starting node for the traversal.
96 If that node is not the root, then only part of the tree will be visited.
98 calls the user function
101 visited (that is, three times for an internal node, and once for a
104 in turn, takes three arguments.
105 The first argument is a pointer to the node being visited.
106 The structure of the node is unspecified,
107 but it is possible to cast the pointer to a pointer-to-pointer-to-element
108 in order to access the element stored within the node.
109 The application must not modify the structure pointed to by this argument.
110 The second argument is an integer which
111 takes one of the values
116 depending on whether this is the first, second, or
117 third visit to the internal node,
120 if this is the single visit to a leaf node.
121 (These symbols are defined in
123 The third argument is the depth of the node;
124 the root node has depth zero.
136 before visiting the children, after the first and before the second,
137 and after visiting the children.
138 Thus, the choice of name
140 is rather confusing.)
149 argument pointer is passed to each invocation of the action callback,
151 This pointer can be used to pass information to and from
152 the callback function in a thread-safe fashion, without resorting
156 removes the whole tree pointed to by
158 freeing all resources allocated by the
161 For the data in each tree node the function
164 The pointer to the data is passed as the argument to the function.
165 If no such work is necessary,
167 must point to a function
171 returns a pointer to a matching node in the tree, or to
172 the newly added node, or NULL if there was insufficient memory
175 returns a pointer to the node, or
176 NULL if no match is found.
177 If there are multiple items that match the key,
178 the item whose node is returned is unspecified.
181 returns a pointer to the parent of the node deleted, or
182 NULL if the item was not found.
183 If the deleted node was the root node,
185 returns a dangling pointer that must not be accessed.
196 For an explanation of the terms used in this section, see
202 Interface Attribute Value
209 T} Thread safety MT-Safe race:rootp
214 T} Thread safety MT-Safe race:root
219 T} Thread safety MT-Safe race:root
224 T} Thread safety MT-Safe
251 POSIX.1-2001, POSIX.1-2008, SVr4.
257 takes a pointer to the root, while the other functions
258 take a pointer to a variable which points to the root.
261 frees the memory required for the node in the tree.
262 The user is responsible for freeing the memory for the corresponding
265 The example program depends on the fact that
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.
273 The following program inserts twelve random numbers into a binary
274 tree, where duplicate numbers are collapsed, then prints the numbers
277 .\" SRC BEGIN (tsearch.c)
279 #define _GNU_SOURCE /* Expose declaration of tdestroy() */
286 static void *root = NULL;
296 fprintf(stderr, "insufficient memory\en");
301 compare(const void *pa, const void *pb)
303 if (*(int *) pa < *(int *) pb)
305 if (*(int *) pa > *(int *) pb)
311 action(const void *nodep, VISIT which, int depth)
319 datap = *(int **) nodep;
320 printf("%6d\en", *datap);
325 datap = *(int **) nodep;
326 printf("%6d\en", *datap);
338 for (unsigned int i = 0; i < 12; i++) {
339 ptr = xmalloc(sizeof(*ptr));
340 *ptr = rand() & 0xff;
341 val = tsearch(ptr, &root, compare);
348 tdestroy(root, free);