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