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