Penguin
Recent Changes
Annotated edit history of twalk(3) version 1, including all changes. View license author blame.
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 ----
This page is a man page (or other imported legacy content). We are unable to automatically determine the license status of this page.