1TSEARCH(3)                 Linux Programmer's Manual                TSEARCH(3)
2
3
4

NAME

6       tsearch, tfind, tdelete, twalk, tdestroy - manage a binary tree
7

SYNOPSIS

9       #include <search.h>
10
11       void *tsearch(const void *key, void **rootp,
12                       int (*compar)(const void *, const void *));
13
14       void *tfind(const void *key, const void **rootp,
15                       int (*compar)(const void *, const void *));
16
17       void *tdelete(const void *key, void **rootp,
18                       int (*compar)(const void *, const void *));
19
20       void twalk(const void *root, void (*action)(const void *nodep,
21                                          const VISIT which,
22                                          const int depth));
23
24       #define _GNU_SOURCE
25       #include <search.h>
26
27       void tdestroy(void *root, void (*free_node)(void *nodep));
28

DESCRIPTION

30       tsearch(),  tfind(), twalk(), and tdelete() manage a binary tree.  They
31       are generalized from Knuth (6.2.2) Algorithm T.   The  first  field  in
32       each  node  of  the  tree  is a pointer to the corresponding data item.
33       (The calling program must store the actual data.)  compar points  to  a
34       comparison  routine,  which  takes  pointers  to  two items.  It should
35       return an integer which is negative, zero, or  positive,  depending  on
36       whether the first item is less than, equal to, or greater than the sec‐
37       ond.
38
39       tsearch() searches the tree for an item.  key points to the item to  be
40       searched  for.   rootp points to a variable which points to the root of
41       the tree.  If the tree is empty, then the variable that rootp points to
42       should  be  set  to  NULL.   If  the  item  is  found in the tree, then
43       tsearch() returns a pointer to it.  If it is not found, then  tsearch()
44       adds it, and returns a pointer to the newly added item.
45
46       tfind()  is  like tsearch(), except that if the item is not found, then
47       tfind() returns NULL.
48
49       tdelete() deletes an item from the tree.  Its arguments are the same as
50       for tsearch().
51
52       twalk() performs depth-first, left-to-right traversal of a binary tree.
53       root points to the starting node for the traversal.  If  that  node  is
54       not  the  root,  then  only  part of the tree will be visited.  twalk()
55       calls the user function action each time a node is  visited  (that  is,
56       three  times  for  an  internal node, and once for a leaf).  action, in
57       turn, takes three arguments.  The first is a pointer to the node  being
58       visited.   The second is an integer which takes on the values preorder,
59       postorder, and endorder depending on whether this is the first, second,
60       or  third visit to the internal node, or leaf if it is the single visit
61       to a leaf node.  (These symbols are defined in <search.h>.)  The  third
62       argument is the depth of the node, with zero being the root.
63
64       (More  commonly,  preorder,  postorder,  and endorder are known as pre‐
65       order, inorder, and postorder: before visiting the children, after  the
66       first  and  before  the second, and after visiting the children.  Thus,
67       the choice of name postorder is rather confusing.)
68
69       tdestroy() removes the whole tree  pointed  to  by  root,  freeing  all
70       resources  allocated  by  the tsearch() function.  For the data in each
71       tree node the function free_node is called.  The pointer to the data is
72       passed  as  the argument to the function.  If no such work is necessary
73       free_node must point to a function doing nothing.
74

RETURN VALUE

76       tsearch() returns a pointer to a matching item in the tree, or  to  the
77       newly  added  item, or NULL if there was insufficient memory to add the
78       item.  tfind() returns a pointer to the item, or NULL if  no  match  is
79       found.   If there are multiple elements that match the key, the element
80       returned is unspecified.
81
82       tdelete() returns a pointer to the parent of the item deleted, or  NULL
83       if the item was not found.
84
85       tsearch(), tfind(), and tdelete() also return NULL if rootp was NULL on
86       entry.
87

CONFORMING TO

89       SVr4, POSIX.1-2001.  The function tdestroy() is a GNU extension.
90

NOTES

92       twalk() takes a pointer to the root, while the other functions  take  a
93       pointer to a variable which points to the root.
94
95       twalk()  uses postorder to mean "after the left subtree, but before the
96       right subtree".   Some  authorities  would  call  this  "inorder",  and
97       reserve "postorder" to mean "after both subtrees".
98
99       tdelete() frees the memory required for the node in the tree.  The user
100       is responsible for freeing the memory for the corresponding data.
101
102       The example program depends on the fact that twalk() makes  no  further
103       reference  to  a  node  after  calling  the user function with argument
104       "endorder" or "leaf".  This works with the GNU library  implementation,
105       but is not in the System V documentation.
106

EXAMPLE

108       The following program inserts twelve random numbers into a binary tree,
109       where duplicate numbers are  collapsed,  then  prints  the  numbers  in
110       order.
111
112       #define _GNU_SOURCE     /* Expose declaration of tdestroy() */
113       #include <search.h>
114       #include <stdlib.h>
115       #include <stdio.h>
116       #include <time.h>
117
118       void *root = NULL;
119
120       void *
121       xmalloc(unsigned n)
122       {
123           void *p;
124           p = malloc(n);
125           if (p)
126               return p;
127           fprintf(stderr, "insufficient memory\n");
128           exit(EXIT_FAILURE);
129       }
130
131       int
132       compare(const void *pa, const void *pb)
133       {
134           if (*(int *) pa < *(int *) pb)
135               return -1;
136           if (*(int *) pa > *(int *) pb)
137               return 1;
138           return 0;
139       }
140
141       void
142       action(const void *nodep, const VISIT which, const int depth)
143       {
144           int *datap;
145
146           switch (which) {
147           case preorder:
148               break;
149           case postorder:
150               datap = *(int **) nodep;
151               printf("%6d\n", *datap);
152               break;
153           case endorder:
154               break;
155           case leaf:
156               datap = *(int **) nodep;
157               printf("%6d\n", *datap);
158               break;
159           }
160       }
161
162       int
163       main(void)
164       {
165           int i, *ptr;
166           void *val;
167
168           srand(time(NULL));
169           for (i = 0; i < 12; i++) {
170               ptr = (int *) xmalloc(sizeof(int));
171               *ptr = rand() & 0xff;
172               val = tsearch((void *) ptr, &root, compare);
173               if (val == NULL)
174                   exit(EXIT_FAILURE);
175               else if ((*(int **) val) != ptr)
176                   free(ptr);
177           }
178           twalk(root, action);
179           tdestroy(root, free);
180           exit(EXIT_SUCCESS);
181       }
182

SEE ALSO

184       bsearch(3), hsearch(3), lsearch(3), qsort(3), feature_test_macros(7)
185

COLOPHON

187       This  page  is  part of release 3.22 of the Linux man-pages project.  A
188       description of the project, and information about reporting  bugs,  can
189       be found at http://www.kernel.org/doc/man-pages/.
190
191
192
193GNU                               2008-09-23                        TSEARCH(3)
Impressum