1 .\" Copyright 1995 by Jim Van Zandt <jrv@vanzandt.mv.com>
3 .\" %%%LICENSE_START(VERBATIM)
4 .\" Permission is granted to make and distribute verbatim copies of this
5 .\" manual provided the copyright notice and this permission notice are
6 .\" preserved on all copies.
8 .\" Permission is granted to copy and distribute modified versions of this
9 .\" manual under the conditions for verbatim copying, provided that the
10 .\" entire resulting derived work is distributed under the terms of a
11 .\" permission notice identical to this one.
13 .\" Since the Linux kernel and libraries are constantly changing, this
14 .\" manual page may be incorrect or out-of-date. The author(s) assume no
15 .\" responsibility for errors or omissions, or for damages resulting from
16 .\" the use of the information contained herein. The author(s) may not
17 .\" have taken the same level of care in the production of this manual,
18 .\" which is licensed free of charge, as they might when working
21 .\" Formatted or processed versions of this manual, if unaccompanied by
22 .\" the source, must acknowledge the copyright and authors of this work.
25 .TH TSEARCH 3 2018-04-30 "GNU" "Linux Programmer's Manual"
27 tsearch, tfind, tdelete, twalk, tdestroy \- manage a binary search tree
30 .B #include <search.h>
32 .BI "void *tsearch(const void *" key ", void **" rootp ,
33 .BI " int (*" compar ")(const void *, const void *));"
35 .BI "void *tfind(const void *" key ", void *const *" rootp ,
36 .BI " int (*" compar ")(const void *, const void *));"
38 .BI "void *tdelete(const void *" key ", void **" rootp ,
39 .BI " int (*" compar ")(const void *, const void *));"
41 .BI "void twalk(const void *" root ", void (*" action ")(const void *" nodep ,
42 .BI " const VISIT " which ,
43 .BI " const int " depth "));"
45 .BR "#define _GNU_SOURCE" " /* See feature_test_macros(7) */"
46 .B #include <search.h>
48 .BI "void tdestroy(void *" root ", void (*" free_node ")(void *" nodep ));
58 They are generalized from Knuth (6.2.2) Algorithm T.
59 The first field in each node of the tree is a pointer to the
60 corresponding data item.
61 (The calling program must store the actual data.)
63 points to a comparison routine, which takes
64 pointers to two items.
65 It should return an integer which is negative,
66 zero, or positive, depending on whether the first item is less than,
67 equal to, or greater than the second.
70 searches the tree for an item.
72 points to the item to be searched for.
74 points to a variable which points to the root of the tree.
76 then the variable that
78 points to should be set to NULL.
79 If the item is found in the tree, then
82 to the corresponding tree node.
85 returns a pointer to a pointer to the data item.)
86 If the item is not found, then
88 adds it, and returns a
89 pointer to the corresponding tree node.
94 except that if the item is not
100 deletes an item from the tree.
101 Its arguments are the same as for
105 performs depth-first, left-to-right traversal of a binary
108 points to the starting node for the traversal.
109 If that node is not the root, then only part of the tree will be visited.
111 calls the user function
114 visited (that is, three times for an internal node, and once for a
117 in turn, takes three arguments.
118 The first argument is a pointer to the node being visited.
119 The structure of the node is unspecified,
120 but it is possible to cast the pointer to a pointer-to-pointer-to-element
121 in order to access the element stored within the node.
122 The application must not modify the structure pointed to by this argument.
123 The second argument is an integer which
124 takes one of the values
129 depending on whether this is the first, second, or
130 third visit to the internal node,
133 if this is the single visit to a leaf node.
134 (These symbols are defined in
136 The third argument is the depth of the node;
137 the root node has depth zero.
149 before visiting the children, after the first and before the second,
150 and after visiting the children.
151 Thus, the choice of name
153 is rather confusing.)
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
208 T} Thread safety MT-Safe race:rootp
211 T} Thread safety MT-Safe race:root
214 T} Thread safety MT-Safe
217 POSIX.1-2001, POSIX.1-2008, SVr4.
223 takes a pointer to the root, while the other functions
224 take a pointer to a variable which points to the root.
227 frees the memory required for the node in the tree.
228 The user is responsible for freeing the memory for the corresponding
231 The example program depends on the fact that
234 further reference to a node after calling the user function with
235 argument "endorder" or "leaf".
236 This works with the GNU library
237 implementation, but is not in the System V documentation.
239 The following program inserts twelve random numbers into a binary
240 tree, where duplicate numbers are collapsed, then prints the numbers
244 #define _GNU_SOURCE /* Expose declaration of tdestroy() */
250 static void *root = NULL;
259 fprintf(stderr, "insufficient memory\en");
264 compare(const void *pa, const void *pb)
266 if (*(int *) pa < *(int *) pb)
268 if (*(int *) pa > *(int *) pb)
274 action(const void *nodep, const VISIT which, const int depth)
282 datap = *(int **) nodep;
283 printf("%6d\en", *datap);
288 datap = *(int **) nodep;
289 printf("%6d\en", *datap);
301 for (i = 0; i < 12; i++) {
302 ptr = xmalloc(sizeof(int));
303 *ptr = rand() & 0xff;
304 val = tsearch((void *) ptr, &root, compare);
307 else if ((*(int **) val) != ptr)
311 tdestroy(root, free);