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, void *const *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         /* See feature_test_macros(7) */
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 argument is a  pointer  to  the
58       node  being  visited.  The structure of the node is unspecified, but it
59       is possible to cast the pointer to a  pointer-to-pointer-to-element  in
60       order  to  access  the element stored within the node.  The application
61       must not modify the structure pointed to by this argument.  The  second
62       argument  is  an  integer  which takes one of the values preorder, pos‐
63       torder, or endorder depending on whether this is the first, second,  or
64       third visit to the internal node, or the value leaf if this is the sin‐
65       gle visit to a leaf node.  (These symbols are defined  in  <search.h>.)
66       The  third  argument  is the depth of the node; the root node has depth
67       zero.
68
69       (More commonly, preorder, postorder, and endorder  are  known  as  pre‐
70       order,  inorder, and postorder: before visiting the children, after the
71       first and before the second, and after visiting  the  children.   Thus,
72       the choice of name postorder is rather confusing.)
73
74       tdestroy()  removes  the  whole  tree  pointed  to by root, freeing all
75       resources allocated by the tsearch() function.  For the  data  in  each
76       tree node the function free_node is called.  The pointer to the data is
77       passed as the argument to the function.  If no such work is  necessary,
78       free_node must point to a function doing nothing.
79

RETURN VALUE

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

ATTRIBUTES

94       For   an   explanation   of   the  terms  used  in  this  section,  see
95       attributes(7).
96
97       ┌────────────────────┬───────────────┬────────────────────┐
98Interface           Attribute     Value              
99       ├────────────────────┼───────────────┼────────────────────┤
100tsearch(), tfind(), │ Thread safety │ MT-Safe race:rootp │
101tdelete()           │               │                    │
102       ├────────────────────┼───────────────┼────────────────────┤
103twalk()             │ Thread safety │ MT-Safe race:root  │
104       ├────────────────────┼───────────────┼────────────────────┤
105tdestroy()          │ Thread safety │ MT-Safe            │
106       └────────────────────┴───────────────┴────────────────────┘

CONFORMING TO

108       POSIX.1-2001, POSIX.1-2008, SVr4.  The function  tdestroy()  is  a  GNU
109       extension.
110

NOTES

112       twalk()  takes  a pointer to the root, while the other functions take a
113       pointer to a variable which points to the root.
114
115       tdelete() frees the memory required for the node in the tree.  The user
116       is responsible for freeing the memory for the corresponding data.
117
118       The  example  program depends on the fact that twalk() makes no further
119       reference to a node after  calling  the  user  function  with  argument
120       "endorder"  or "leaf".  This works with the GNU library implementation,
121       but is not in the System V documentation.
122

EXAMPLE

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

SEE ALSO

200       bsearch(3), hsearch(3), lsearch(3), qsort(3)
201

COLOPHON

203       This page is part of release 4.15 of the Linux  man-pages  project.   A
204       description  of  the project, information about reporting bugs, and the
205       latest    version    of    this    page,    can     be     found     at
206       https://www.kernel.org/doc/man-pages/.
207
208
209
210GNU                               2015-08-08                        TSEARCH(3)
Impressum