1TSEARCH(3) Linux Programmer's Manual TSEARCH(3)
2
6 tsearch, tfind, tdelete, twalk, tdestroy - manage a binary search tree
7
9 #include <search.h>
10 void *tsearch(const void *key, void **rootp,
12 int (*compar)(const void *, const void *));
13 void *tfind(const void *key, void *const *rootp,
15 int (*compar)(const void *, const void *));
16 void *tdelete(const void *key, void **rootp,
18 int (*compar)(const void *, const void *));
19 void twalk(const void *root, void (*action)(const void *nodep,
21 const VISIT which,
22 const int depth));
23 #define _GNU_SOURCE /* See feature_test_macros(7) */
25 #include <search.h>
26 void tdestroy(void *root, void (*free_node)(void *nodep));
28
30 tsearch(), tfind(), twalk(), and tdelete() manage a binary search tree.
31 They are generalized from Knuth (6.2.2) Algorithm T. The first field
32 in each node of the tree is a pointer to the corresponding data item.
33 (The calling program must store the actual data.) compar points to a
34 comparison routine, which takes pointers to two items. It should
35 return an integer which is negative, zero, or positive, depending on
36 whether the first item is less than, equal to, or greater than the sec‐
37 ond.
38 tsearch() searches the tree for an item. key points to the item to be
40 searched for. rootp points to a variable which points to the root of
41 the tree. If the tree is empty, then the variable that rootp points to
42 should be set to NULL. If the item is found in the tree, then
43 tsearch() returns a pointer to the corresponding tree node. (In other
44 words, tsearch() returns a pointer to a pointer to the data item.) If
45 the item is not found, then tsearch() adds it, and returns a pointer to
46 the corresponding tree node.
47 tfind() is like tsearch(), except that if the item is not found, then
49 tfind() returns NULL.
50 tdelete() deletes an item from the tree. Its arguments are the same as
52 for tsearch().
53 twalk() performs depth-first, left-to-right traversal of a binary tree.
55 root points to the starting node for the traversal. If that node is
56 not the root, then only part of the tree will be visited. twalk()
57 calls the user function action each time a node is visited (that is,
58 three times for an internal node, and once for a leaf). action, in
59 turn, takes three arguments. The first argument is a pointer to the
60 node being visited. The structure of the node is unspecified, but it
61 is possible to cast the pointer to a pointer-to-pointer-to-element in
62 order to access the element stored within the node. The application
63 must not modify the structure pointed to by this argument. The second
64 argument is an integer which takes one of the values preorder, pos‐
65 torder, or endorder depending on whether this is the first, second, or
66 third visit to the internal node, or the value leaf if this is the sin‐
67 gle visit to a leaf node. (These symbols are defined in <search.h>.)
68 The third argument is the depth of the node; the root node has depth
69 zero.
70 (More commonly, preorder, postorder, and endorder are known as pre‐
72 order, inorder, and postorder: before visiting the children, after the
73 first and before the second, and after visiting the children. Thus,
74 the choice of name postorder is rather confusing.)
75 tdestroy() removes the whole tree pointed to by root, freeing all
77 resources allocated by the tsearch() function. For the data in each
78 tree node the function free_node is called. The pointer to the data is
79 passed as the argument to the function. If no such work is necessary,
80 free_node must point to a function doing nothing.
81
83 tsearch() returns a pointer to a matching node in the tree, or to the
84 newly added node, or NULL if there was insufficient memory to add the
85 item. tfind() returns a pointer to the node, or NULL if no match is
86 found. If there are multiple items that match the key, the item whose
87 node is returned is unspecified.
88 tdelete() returns a pointer to the parent of the node deleted, or NULL
90 if the item was not found. If the deleted node was the root node,
91 tdelete() returns a dangling pointer that must not be accessed.
92 tsearch(), tfind(), and tdelete() also return NULL if rootp was NULL on
94 entry.
95
97 For an explanation of the terms used in this section, see
98 attributes(7).
99 ┌────────────────────┬───────────────┬────────────────────┐
101 │Interface │ Attribute │ Value │
102 ├────────────────────┼───────────────┼────────────────────┤
103 │tsearch(), tfind(), │ Thread safety │ MT-Safe race:rootp │
104 │tdelete() │ │ │
105 ├────────────────────┼───────────────┼────────────────────┤
106 │twalk() │ Thread safety │ MT-Safe race:root │
107 ├────────────────────┼───────────────┼────────────────────┤
108 │tdestroy() │ Thread safety │ MT-Safe │
109 └────────────────────┴───────────────┴────────────────────┘
111 POSIX.1-2001, POSIX.1-2008, SVr4. The function tdestroy() is a GNU
112 extension.
113
115 twalk() takes a pointer to the root, while the other functions take a
116 pointer to a variable which points to the root.
117 tdelete() frees the memory required for the node in the tree. The user
119 is responsible for freeing the memory for the corresponding data.
120 The example program depends on the fact that twalk() makes no further
122 reference to a node after calling the user function with argument
123 "endorder" or "leaf". This works with the GNU library implementation,
124 but is not in the System V documentation.
125
127 The following program inserts twelve random numbers into a binary tree,
128 where duplicate numbers are collapsed, then prints the numbers in
129 order.
130 #define _GNU_SOURCE /* Expose declaration of tdestroy() */
132 #include <search.h>
133 #include <stdlib.h>
134 #include <stdio.h>
135 #include <time.h>
136 static void *root = NULL;
138 static void *
140 xmalloc(unsigned n)
141 {
142 void *p;
143 p = malloc(n);
144 if (p)
145 return p;
146 fprintf(stderr, "insufficient memory\n");
147 exit(EXIT_FAILURE);
148 }
149 static int
151 compare(const void *pa, const void *pb)
152 {
153 if (*(int *) pa < *(int *) pb)
154 return -1;
155 if (*(int *) pa > *(int *) pb)
156 return 1;
157 return 0;
158 }
159 static void
161 action(const void *nodep, const VISIT which, const int depth)
162 {
163 int *datap;
164 switch (which) {
166 case preorder:
167 break;
168 case postorder:
169 datap = *(int **) nodep;
170 printf("%6d\n", *datap);
171 break;
172 case endorder:
173 break;
174 case leaf:
175 datap = *(int **) nodep;
176 printf("%6d\n", *datap);
177 break;
178 }
179 }
180 int
182 main(void)
183 {
184 int i, *ptr;
185 void *val;
186 srand(time(NULL));
188 for (i = 0; i < 12; i++) {
189 ptr = xmalloc(sizeof(int));
190 *ptr = rand() & 0xff;
191 val = tsearch((void *) ptr, &root, compare);
192 if (val == NULL)
193 exit(EXIT_FAILURE);
194 else if ((*(int **) val) != ptr)
195 free(ptr);
196 }
197 twalk(root, action);
198 tdestroy(root, free);
199 exit(EXIT_SUCCESS);
200 }
201
203 bsearch(3), hsearch(3), lsearch(3), qsort(3)
204
206 This page is part of release 4.16 of the Linux man-pages project. A
207 description of the project, information about reporting bugs, and the
208 latest version of this page, can be found at
209 https://www.kernel.org/doc/man-pages/.
210GNU 2018-04-30 TSEARCH(3)