1tsearch(3C) Standard C Library Functions tsearch(3C)
2
6 tsearch, tfind, tdelete, twalk - manage binary search trees
7
9 #include <search.h>
10 void *tsearch(const void *key, void **rootp,
12 int (*compar)(const void *, const void *));
13 void *tfind(const void *key, void * const *rootp,
16 int (*compar)(const void *, const void *));
17 void *tdelete(const void *restrict key, void **restrict rootp,
20 int (*compar)(const void *, const void *));
21 void twalk(const void *root, void(*action) (void *, VISIT, int));
24
27 The tsearch(), tfind(), tdelete(), and twalk() functions are routines
28 for manipulating binary search trees. They are generalized from Knuth
29 (6.2.2) Algorithms T and D. All comparisons are done with a user-sup‐
30 plied routine. This routine is called with two arguments, the pointers
31 to the elements being compared. It returns an integer less than, equal
32 to, or greater than 0, according to whether the first argument is to be
33 considered less than, equal to or greater than the second argument. The
34 comparison function need not compare every byte, so arbitrary data may
35 be contained in the elements in addition to the values being compared.
36 The tsearch() function is used to build and access the tree. The key
39 argument is a pointer to a datum to be accessed or stored. If there is
40 a datum in the tree equal to *key (the value pointed to by key), a
41 pointer to this found datum is returned. Otherwise, *key is inserted,
42 and a pointer to it returned. Only pointers are copied, so the calling
43 routine must store the data. The rootp argument points to a variable
44 that points to the root of the tree. A null value for the variable
45 pointed to by rootp denotes an empty tree; in this case, the variable
46 will be set to point to the datum which will be at the root of the new
47 tree.
48 Like tsearch(), tfind() will search for a datum in the tree, returning
51 a pointer to it if found. However, if it is not found, tfind() will
52 return a null pointer. The arguments for tfind() are the same as for
53 tsearch().
54 The tdelete() function deletes a node from a binary search tree. The
57 arguments are the same as for tsearch(). The variable pointed to by
58 rootp will be changed if the deleted node was the root of the tree.
59 tdelete() returns a pointer to the parent of the deleted node, or a
60 null pointer if the node is not found.
61 The twalk() function traverses a binary search tree. The root argument
64 is the root of the tree to be traversed. (Any node in a tree may be
65 used as the root for a walk below that node.) action is the name of a
66 routine to be invoked at each node. This routine is, in turn, called
67 with three arguments. The first argument is the address of the node
68 being visited. The second argument is a value from an enumeration data
69 type
70 typedef enum { preorder, postorder, endorder, leaf } VISIT;
72 (defined in <search.h>), depending on whether this is the first, second
76 or third time that the node has been visited (during a depth-first,
77 left-to-right traversal of the tree), or whether the node is a leaf.
78 The third argument is the level of the node in the tree, with the root
79 being level zero.
80 The pointers to the key and the root of the tree should be of type
83 pointer-to-element, and cast to type pointer-to-character. Similarly,
84 although declared as type pointer-to-character, the value returned
85 should be cast into type pointer-to-element.
86
88 If the node is found, both tsearch() and tfind() return a pointer to
89 it. If not, tfind() returns a null pointer, and tsearch() returns a
90 pointer to the inserted item.
91 A null pointer is returned by tsearch() if there is not enough space
94 available to create a new node.
95 A null pointer is returned by tsearch(), tfind() and tdelete() if rootp
98 is a null pointer on entry.
99 The tdelete() function returns a pointer to the parent of the deleted
102 node, or a null pointer if the node is not found.
103 The twalk() function returns no value.
106
108 No errors are defined.
109
111 The root argument to twalk() is one level of indirection less than the
112 rootp arguments to tsearch() and tdelete().
113 There are two nomenclatures used to refer to the order in which tree
116 nodes are visited. tsearch() uses preorder, postorder and endorder to
117 refer respectively to visiting a node before any of its children, after
118 its left child and before its right, and after both its children. The
119 alternate nomenclature uses preorder, inorder and postorder to refer to
120 the same visits, which could result in some confusion over the meaning
121 of postorder.
122 If the calling function alters the pointer to the root, the results are
125 unpredictable.
126 These functions safely allows concurrent access by multiple threads to
129 disjoint data, such as overlapping subtrees or tables.
130
132 Example 1 A sample program of using tsearch() function.
133 The following code reads in strings and stores structures containing a
136 pointer to each string and a count of its length. It then walks the
137 tree, printing out the stored strings and their lengths in alphabetical
138 order.
139 #include <string.h>
142 #include <stdio.h>
143 #include <search.h>
144 struct node {
145 char *string;
146 int length;
147 };
148 char string_space[10000];
149 struct node nodes[500];
150 void *root = NULL;
151 int node_compare(const void *node1, const void *node2) {
153 return strcmp(((const struct node *) node1)->string,
154 ((const struct node *) node2)->string);
155 }
156 void print_node(const void *node, VISIT order, int level) {
158 if (order == preorder || order == leaf) {
159 printf("length=%d, string=%20s\n",
160 (*(struct node **)node)->length,
161 (*(struct node **)node)->string);
162 }
163 }
164 main()
166 {
167 char *strptr = string_space;
168 struct node *nodeptr = nodes;
169 int i = 0;
170 while (gets(strptr) != NULL && i++ < 500) {
172 nodeptr->string = strptr;
173 nodeptr->length = strlen(strptr);
174 (void) tsearch((void *)nodeptr,
175 &root, node_compare);
176 strptr += nodeptr->length + 1;
177 nodeptr++;
178 }
179 twalk(root, print_node);
180 }
181
184 See attributes(5) for descriptions of the following attributes:
185 ┌─────────────────────────────┬─────────────────────────────┐
190 │ ATTRIBUTE TYPE │ ATTRIBUTE VALUE │
191 ├─────────────────────────────┼─────────────────────────────┤
192 │Interface Stability │Standard │
193 ├─────────────────────────────┼─────────────────────────────┤
194 │MT-Level │MT-Safe │
195 └─────────────────────────────┴─────────────────────────────┘
196
198 bsearch(3C), hsearch(3C), lsearch(3C), attributes(5), standards(5)
199SunOS 5.11 6 Dec 2004 tsearch(3C)