1tsearch(3C)              Standard C Library Functions              tsearch(3C)
2
3
4

NAME

6       tsearch, tfind, tdelete, twalk - manage binary search trees
7

SYNOPSIS

9       #include <search.h>
10
11       void *tsearch(const void *key, void **rootp,
12            int (*compar)(const void *, const void *));
13
14
15       void *tfind(const void *key, void * const *rootp,
16            int (*compar)(const void *, const void *));
17
18
19       void *tdelete(const void *restrict key, void **restrict rootp,
20            int (*compar)(const void *, const void *));
21
22
23       void twalk(const void *root, void(*action) (void *, VISIT, int));
24
25

DESCRIPTION

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
37
38       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
49
50       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
55
56       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
62
63       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
71         typedef enum { preorder, postorder, endorder, leaf } VISIT;
72
73
74
75       (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
81
82       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

RETURN VALUES

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
92
93       A null pointer is returned by tsearch() if there is  not  enough  space
94       available to create a new node.
95
96
97       A null pointer is returned by tsearch(), tfind() and tdelete() if rootp
98       is a null pointer on entry.
99
100
101       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
104
105       The twalk() function returns no value.
106

ERRORS

108       No errors are defined.
109

USAGE

111       The root argument to  twalk() is one level of indirection less than the
112       rootp arguments to tsearch() and tdelete().
113
114
115       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
123
124       If the calling function alters the pointer to the root, the results are
125       unpredictable.
126
127
128       These  functions safely allows concurrent access by multiple threads to
129       disjoint data, such as overlapping subtrees or tables.
130

EXAMPLES

132       Example 1 A sample program of using tsearch() function.
133
134
135       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
140
141         #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
152         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
157         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
165         main()
166         {
167                 char *strptr = string_space;
168                 struct node *nodeptr = nodes;
169                 int i = 0;
170
171                 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
182

ATTRIBUTES

184       See attributes(5) for descriptions of the following attributes:
185
186
187
188
189       ┌─────────────────────────────┬─────────────────────────────┐
190       │      ATTRIBUTE TYPE         │      ATTRIBUTE VALUE        │
191       ├─────────────────────────────┼─────────────────────────────┤
192       │Interface Stability          │Standard                     │
193       ├─────────────────────────────┼─────────────────────────────┤
194       │MT-Level                     │MT-Safe                      │
195       └─────────────────────────────┴─────────────────────────────┘
196

SEE ALSO

198       bsearch(3C), hsearch(3C), lsearch(3C), attributes(5), standards(5)
199
200
201
202SunOS 5.11                        6 Dec 2004                       tsearch(3C)
Impressum