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