]>
Commit | Line | Data |
---|---|---|
fea681da MK |
1 | .\" Hey Emacs! This file is -*- nroff -*- source. |
2 | .\" Copyright 1995 by Jim Van Zandt <jrv@vanzandt.mv.com> | |
3 | .\" | |
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. | |
12 | .\" | |
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. | |
20 | .\" | |
21 | .\" Formatted or processed versions of this manual, if unaccompanied by | |
22 | .\" the source, must acknowledge the copyright and authors of this work. | |
23 | .\" | |
24 | .TH TSEARCH 3 1995-09-24 "GNU" "Linux Programmer's Manual" | |
25 | .SH NAME | |
b559f818 | 26 | tsearch, tfind, tdelete, twalk, tdestroy \- manage a binary tree |
fea681da MK |
27 | .SH SYNOPSIS |
28 | .nf | |
29 | .B #include <search.h> | |
30 | .sp | |
31 | .BI "void *tsearch(const void *" key ", void **" rootp , | |
32 | .BI " int(*" compar ")(const void *, const void *));" | |
33 | .sp | |
34 | .BI "void *tfind(const void *" key ", const void **" rootp , | |
35 | .BI " int(*" compar ")(const void *, const void *));" | |
36 | .sp | |
37 | .BI "void *tdelete(const void *" key ", void **" rootp , | |
38 | .BI " int(*" compar ")(const void *, const void *));" | |
39 | .sp | |
40 | .BI "void twalk(const void *" root ", void(*" action ")(const void *" nodep , | |
41 | .BI " const VISIT " which , | |
42 | .BI " const int " depth "));" | |
43 | .sp | |
44 | .B #define _GNU_SOURCE | |
45 | .br | |
46 | .B #include <search.h> | |
47 | .sp | |
48 | .BI "void tdestroy (void *" root ", void (*" free_node ")(void *" nodep )); | |
49 | .RE | |
50 | .fi | |
51 | .SH DESCRIPTION | |
e511ffb6 | 52 | \fBtsearch\fP(), \fBtfind\fP(), \fBtwalk\fP(), and \fBtdelete\fP() manage a |
fea681da MK |
53 | binary tree. They are generalized from Knuth (6.2.2) Algorithm T. |
54 | The first field in each node of the tree is a pointer to the | |
55 | corresponding data item. (The calling program must store the actual | |
56 | data.) \fIcompar\fP points to a comparison routine, which takes | |
57 | pointers to two items. It should return an integer which is negative, | |
58 | zero, or positive, depending on whether the first item is less than, | |
59 | equal to, or greater than the second. | |
60 | .PP | |
e511ffb6 | 61 | \fBtsearch\fP() searches the tree for an item. \fIkey\fP |
fea681da MK |
62 | points to the item to be searched for. \fIrootp\fP points to a |
63 | variable which points to the root of the tree. If the tree is empty, | |
64 | then the variable that \fIrootp\fP points to should be set to \fBNULL\fP. | |
e511ffb6 MK |
65 | If the item is found in the tree, then \fBtsearch\fP() returns a pointer |
66 | to it. If it is not found, then \fBtsearch\fP() adds it, and returns a | |
fea681da MK |
67 | pointer to the newly added item. |
68 | .PP | |
e511ffb6 MK |
69 | \fBtfind\fP() is like \fBtsearch\fP(), except that if the item is not |
70 | found, then \fBtfind\fP() returns \fBNULL\fP. | |
fea681da | 71 | .PP |
e511ffb6 MK |
72 | \fBtdelete\fP() deletes an item from the tree. Its arguments are the |
73 | same as for \fBtsearch\fP(). | |
fea681da | 74 | .PP |
e511ffb6 | 75 | \fBtwalk\fP() performs depth-first, left-to-right traversal of a binary |
fea681da MK |
76 | tree. \fIroot\fP points to the starting node for the traversal. If |
77 | that node is not the root, then only part of the tree will be visited. | |
e511ffb6 | 78 | \fBtwalk\fP() calls the user function \fIaction\fP each time a node is |
fea681da MK |
79 | visited (that is, three times for an internal node, and once for a |
80 | leaf). \fIaction\fP, in turn, takes three arguments. The first is a | |
81 | pointer to the node being visited. The second is an integer which | |
82 | takes on the values \fBpreorder\fP, \fBpostorder\fP, and | |
83 | \fBendorder\fP depending on whether this is the first, second, or | |
84 | third visit to the internal node, or \fBleaf\fP if it is the single | |
85 | visit to a leaf node. (These symbols are defined in | |
86 | \fI<search.h>\fP.) The third argument is the depth of the node, with | |
87 | zero being the root. | |
88 | .PP | |
89 | (More commonly, \fBpreorder\fP, \fBpostorder\fP, and \fBendorder\fP | |
90 | are known as \fBpreorder\fP, \fBinorder\fP, and \fBpostorder\fP: | |
91 | before visiting the children, after the first and before the second, | |
92 | and after visiting the children. Thus, the choice of name \fBpost\%order\fP | |
93 | is rather confusing.) | |
94 | .PP | |
e511ffb6 MK |
95 | \fBtdestroy\fP() removes the whole tree pointed to by \fIrootp\fP, |
96 | freeing all resources allocated by the \fBtsearch\fP() function. For | |
fea681da MK |
97 | the data in each tree node the function \fIfree_node\fP is called. |
98 | The pointer to the data is passed as the argument to the function. If | |
99 | no such work is necessary \fIfree_node\fP must point to a function | |
100 | doing nothing. | |
101 | .SH "RETURN VALUE" | |
e511ffb6 | 102 | \fBtsearch\fP() returns a pointer to a matching item in the tree, or to |
fea681da | 103 | the newly added item, or \fBNULL\fP if there was insufficient memory |
e511ffb6 | 104 | to add the item. \fBtfind\fP() returns a pointer to the item, or |
fea681da MK |
105 | \fBNULL\fP if no match is found. If there |
106 | are multiple elements that match the key, the element returned is | |
107 | unspecified. | |
108 | .PP | |
e511ffb6 | 109 | \fBtdelete\fP() returns a pointer to the parent of the item deleted, or |
fea681da MK |
110 | \fBNULL\fP if the item was not found. |
111 | .PP | |
e511ffb6 | 112 | \fBtsearch\fP(), \fBtfind\fP(), and \fBtdelete\fP() also |
fea681da MK |
113 | return \fBNULL\fP if \fIrootp\fP was \fBNULL\fP on entry. |
114 | .SH WARNINGS | |
e511ffb6 | 115 | \fBtwalk\fP() takes a pointer to the root, while the other functions |
fea681da MK |
116 | take a pointer to a variable which points to the root. |
117 | .PP | |
e511ffb6 | 118 | \fBtwalk\fP() uses \fBpostorder\fP to mean "after the left subtree, but |
fea681da MK |
119 | before the right subtree". Some authorities would call this |
120 | "inorder", and reserve "postorder" to mean "after both subtrees". | |
121 | .PP | |
e511ffb6 | 122 | \fBtdelete\fP() frees the memory required for the node in the tree. |
fea681da MK |
123 | The user is responsible for freeing the memory for the corresponding |
124 | data. | |
125 | .PP | |
e511ffb6 | 126 | The example program depends on the fact that \fBtwalk\fP() makes no |
fea681da MK |
127 | further reference to a node after calling the user function with |
128 | argument "endorder" or "leaf". This works with the GNU library | |
129 | implementation, but is not in the SysV documentation. | |
130 | .SH EXAMPLE | |
131 | The following program inserts twelve random numbers into a binary | |
132 | tree, where duplicate numbers are collapsed, then prints the numbers | |
133 | in order. | |
134 | .sp | |
135 | .nf | |
136 | #include <search.h> | |
137 | #include <stdlib.h> | |
138 | #include <stdio.h> | |
139 | #include <time.h> | |
140 | ||
141 | void *root = NULL; | |
142 | ||
143 | void *xmalloc(unsigned n) { | |
144 | void *p; | |
145 | p = malloc(n); | |
146 | if (p) return p; | |
147 | fprintf(stderr, "insufficient memory\\n"); | |
148 | exit(1); | |
149 | } | |
150 | ||
151 | int compare(const void *pa, const void *pb) { | |
2bc2f479 | 152 | if (*(int *)pa < *(int *)pb) return \-1; |
fea681da MK |
153 | if (*(int *)pa > *(int *)pb) return 1; |
154 | return 0; | |
155 | } | |
156 | ||
157 | void action(const void *nodep, const VISIT which, const int depth) { | |
158 | int *datap; | |
159 | ||
160 | switch(which) { | |
161 | case preorder: | |
162 | break; | |
163 | case postorder: | |
164 | datap = *(int **)nodep; | |
165 | printf("%6d\\n", *datap); | |
166 | break; | |
167 | case endorder: | |
168 | break; | |
169 | case leaf: | |
170 | datap = *(int **)nodep; | |
171 | printf("%6d\\n", *datap); | |
172 | break; | |
173 | } | |
174 | } | |
175 | ||
176 | int main() { | |
177 | int i, *ptr; | |
178 | void *val; | |
179 | ||
180 | srand(time(NULL)); | |
181 | for (i = 0; i < 12; i++) { | |
182 | ptr = (int *)xmalloc(sizeof(int)); | |
183 | *ptr = rand()&0xff; | |
184 | val = tsearch((void *)ptr, &root, compare); | |
185 | if (val == NULL) exit(1); | |
186 | } | |
187 | twalk(root, action); | |
188 | return 0; | |
189 | } | |
190 | .fi | |
191 | .SH "CONFORMING TO" | |
192 | SVID. | |
193 | The function | |
63aa9df0 | 194 | .BR tdestroy () |
fea681da MK |
195 | is a GNU extension. |
196 | .SH "SEE ALSO" | |
197 | .BR bsearch (3), | |
198 | .BR hsearch (3), | |
199 | .BR lsearch (3), | |
200 | .BR qsort (3) |