version 1, including all changes.
.
Rev |
Author |
# |
Line |
1 |
perry |
1 |
TSEARCH |
|
|
2 |
!!!TSEARCH |
|
|
3 |
NAME |
|
|
4 |
SYNOPSIS |
|
|
5 |
DESCRIPTION |
|
|
6 |
RETURN VALUE |
|
|
7 |
WARNINGS |
|
|
8 |
EXAMPLE |
|
|
9 |
CONFORMING TO |
|
|
10 |
SEE ALSO |
|
|
11 |
---- |
|
|
12 |
!!NAME |
|
|
13 |
|
|
|
14 |
|
|
|
15 |
tsearch, tfind, tdelete, twalk - manage a binary tree |
|
|
16 |
!!SYNOPSIS |
|
|
17 |
|
|
|
18 |
|
|
|
19 |
__#include |
|
|
20 |
__''key''__, void **__''rootp''__, |
|
|
21 |
int (*__''compar''__)(const void *, const void *)); |
|
|
22 |
void *tfind (const void *__''key''__, const void **__''rootp''__, |
|
|
23 |
int (*__''compar''__)(const void *, const void *)); |
|
|
24 |
void *tdelete (const void *__''key''__, void **__''rootp''__, |
|
|
25 |
int (*__''compar''__)(const void *, const void *)); |
|
|
26 |
void twalk (const void *__''root''__, void (*__''action''__) (const void *__''nodep''__, |
|
|
27 |
const VISIT__ ''which''__, |
|
|
28 |
const int__ ''depth''__)); |
|
|
29 |
#ifdef _GNU_SOURCE |
|
|
30 |
typedef void (*__''__free_fn_t''__) (void *__''__nodep''__); |
|
|
31 |
void tdestroy (void *__''root''__, __free_fn_t__ ''free_content''__); |
|
|
32 |
#endif |
|
|
33 |
__ |
|
|
34 |
!!DESCRIPTION |
|
|
35 |
|
|
|
36 |
|
|
|
37 |
__tsearch__, __tfind__, __twalk__, and |
|
|
38 |
__tdelete__ manage a binary tree. They are generalized |
|
|
39 |
from Knuth (6.2.2) Algorithm T. The first field in each node |
|
|
40 |
of the tree is a pointer to the corresponding data item. |
|
|
41 |
(The calling program must store the actual data.) |
|
|
42 |
''compar'' points to a comparison routine, which takes |
|
|
43 |
pointers to two items. It should return an integer which is |
|
|
44 |
negative, zero, or positive, depending on whether the first |
|
|
45 |
item is less than, equal to, or greater than the |
|
|
46 |
second. |
|
|
47 |
|
|
|
48 |
|
|
|
49 |
__tsearch__ searches the tree for an item. ''key'' |
|
|
50 |
points to the item to be searched for. ''rootp'' points |
|
|
51 |
to a variable which points to the root of the tree. If the |
|
|
52 |
tree is empty, then the variable that ''rootp'' points to |
|
|
53 |
should be set to __NULL__. If the item is found in the |
|
|
54 |
tree, then __tsearch__ returns a pointer to it. If it is |
|
|
55 |
not found, then __tsearch__ adds it, and returns a |
|
|
56 |
pointer to the newly added item. |
|
|
57 |
|
|
|
58 |
|
|
|
59 |
__tfind__ is like __tsearch__, except that if the item |
|
|
60 |
is not found, then __tfind__ returns |
|
|
61 |
__NULL__. |
|
|
62 |
|
|
|
63 |
|
|
|
64 |
__tdelete__ deletes an item from the tree. Its arguments |
|
|
65 |
are the same as for __tsearch__. |
|
|
66 |
|
|
|
67 |
|
|
|
68 |
__twalk__ performs depth-first, left-to-right traversal |
|
|
69 |
of a binary tree. ''root'' points to the starting node |
|
|
70 |
for the traversal. If that node is not the root, then only |
|
|
71 |
part of the tree will be visited. __twalk__ calls the |
|
|
72 |
user function ''action'' each time a node is visited |
|
|
73 |
(that is, three times for an internal node, and once for a |
|
|
74 |
leaf). ''action'', in turn, takes three arguments. The |
|
|
75 |
first is a pointer to the node being visited. The second is |
|
|
76 |
an integer which takes on the values __preorder__, |
|
|
77 |
__postorder__, and __endorder__ depending on whether |
|
|
78 |
this is the first, second, or third visit to the internal |
|
|
79 |
node, or __leaf__ if it is the single visit to a leaf |
|
|
80 |
node. (These symbols are defined in |
|
|
81 |
''''.) The third argument is the depth of |
|
|
82 |
the node, with zero being the root. You should not modify |
|
|
83 |
the tree while traversing it as the the results would be |
|
|
84 |
undefined. |
|
|
85 |
|
|
|
86 |
|
|
|
87 |
__tdestroy__() removes the whole tree pointed to by |
|
|
88 |
''rootp'', freeing all resources allocated by the |
|
|
89 |
__tsearch__() function. For the data in each tree node |
|
|
90 |
the function ''free_content'' is called. The pointer to |
|
|
91 |
the data is passed as the argument to the function. If no |
|
|
92 |
such work is necessary ''free_content'' must point to a |
|
|
93 |
function doing nothing. It is called in any |
|
|
94 |
case. |
|
|
95 |
!!RETURN VALUE |
|
|
96 |
|
|
|
97 |
|
|
|
98 |
__tsearch__ returns a pointer to a matching item in the |
|
|
99 |
tree, or to the newly added item, or __NULL__ if there |
|
|
100 |
was insufficient memory to add the item. __tfind__ |
|
|
101 |
returns a pointer to the item, or __NULL__ if no match is |
|
|
102 |
found. If there are multiple elements that match the key, |
|
|
103 |
the element returned is unspecified. |
|
|
104 |
|
|
|
105 |
|
|
|
106 |
__tdelete__ returns a pointer to the parent of the item |
|
|
107 |
deleted, or __NULL__ if the item was not |
|
|
108 |
found. |
|
|
109 |
|
|
|
110 |
|
|
|
111 |
__tsearch__, __tfind__, and __tdelete__ also return |
|
|
112 |
__NULL__ if ''rootp'' was __NULL__ on |
|
|
113 |
entry. |
|
|
114 |
!!WARNINGS |
|
|
115 |
|
|
|
116 |
|
|
|
117 |
__twalk__ takes a pointer to the root, while the other |
|
|
118 |
functions take a pointer to a variable which points to the |
|
|
119 |
root. |
|
|
120 |
|
|
|
121 |
|
|
|
122 |
__twalk__ uses __postorder__ to mean |
|
|
123 |
__ |
|
|
124 |
|
|
|
125 |
|
|
|
126 |
__tdelete__ frees the memory required for the node in the |
|
|
127 |
tree. The user is responsible for freeing the memory for the |
|
|
128 |
corresponding data. |
|
|
129 |
|
|
|
130 |
|
|
|
131 |
The example program depends on the fact that __twalk__ |
|
|
132 |
makes no further reference to a node after calling the user |
|
|
133 |
function with argument |
|
|
134 |
__ |
|
|
135 |
!!EXAMPLE |
|
|
136 |
|
|
|
137 |
|
|
|
138 |
The following program inserts twelve random numbers into a |
|
|
139 |
binary tree, then prints the numbers in order. Note that |
|
|
140 |
this example will collapse duplicate numbers. |
|
|
141 |
|
|
|
142 |
|
|
|
143 |
#include |
|
|
144 |
!!CONFORMING TO |
|
|
145 |
|
|
|
146 |
|
|
|
147 |
SVID, SUSv2 |
|
|
148 |
|
|
|
149 |
|
|
|
150 |
The __tdestroy__() function is a GNU extension, and it's |
|
|
151 |
only defined when the symbol ___GNU_SOURCE__ is defined |
|
|
152 |
before including ''''. |
|
|
153 |
!!SEE ALSO |
|
|
154 |
|
|
|
155 |
|
|
|
156 |
qsort(3), bsearch(3), hsearch(3), |
|
|
157 |
lsearch(3) |
|
|
158 |
---- |