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