man3/tsearch.3

   1 .\" Copyright 1995 by Jim Van Zandt <jrv@vanzandt.mv.com>
   2 .\"
   3 .\" %%%LICENSE_START(VERBATIM)
   4 .\" Permission is granted to make and distribute verbatim copies of this
   5 .\" manual provided the copyright notice and this permission notice are
   6 .\" preserved on all copies.
   7 .\"
   8 .\" Permission is granted to copy and distribute modified versions of this
   9 .\" manual under the conditions for verbatim copying, provided that the
  10 .\" entire resulting derived work is distributed under the terms of a
  11 .\" permission notice identical to this one.
  12 .\"
  13 .\" Since the Linux kernel and libraries are constantly changing, this
  14 .\" manual page may be incorrect or out-of-date.  The author(s) assume no
  15 .\" responsibility for errors or omissions, or for damages resulting from
  16 .\" the use of the information contained herein.  The author(s) may not
  17 .\" have taken the same level of care in the production of this manual,
  18 .\" which is licensed free of charge, as they might when working
  19 .\" professionally.
  20 .\"
  21 .\" Formatted or processed versions of this manual, if unaccompanied by
  22 .\" the source, must acknowledge the copyright and authors of this work.
  23 .\" %%%LICENSE_END
  24 .\"
  25 .TH TSEARCH 3  2018-04-30 "GNU" "Linux Programmer's Manual"
  26 .SH NAME
  27 tsearch, tfind, tdelete, twalk, tdestroy \- manage a binary search tree
  28 .SH SYNOPSIS
  29 .nf
  30 .B #include <search.h>
  31 .PP
  32 .BI "void *tsearch(const void *" key ", void **" rootp ,
  33 .BI "                int (*" compar ")(const void *, const void *));"
  34 .PP
  35 .BI "void *tfind(const void *" key ", void *const *" rootp ,
  36 .BI "                int (*" compar ")(const void *, const void *));"
  37 .PP
  38 .BI "void *tdelete(const void *" key ", void **" rootp ,
  39 .BI "                int (*" compar ")(const void *, const void *));"
  40 .PP
  41 .BI "void twalk(const void *" root ", void (*" action ")(const void *" nodep ,
  42 .BI "                                   const VISIT " which ,
  43 .BI "                                   const int " depth "));"
  44
  45 .BR "#define _GNU_SOURCE" "         /* See feature_test_macros(7) */"
  46 .B #include <search.h>
  47 .PP
  48 .BI "void tdestroy(void *" root ", void (*" free_node ")(void *" nodep ));
  49 .fi
  50 .SH DESCRIPTION
  51 .BR tsearch (),
  52 .BR tfind (),
  53 .BR twalk (),
  54 and
  55 .BR tdelete ()
  56 manage a
  57 binary search tree.
  58 They are generalized from Knuth (6.2.2) Algorithm T.
  59 The first field in each node of the tree is a pointer to the
  60 corresponding data item.
  61 (The calling program must store the actual data.)
  62 .IR compar
  63 points to a comparison routine, which takes
  64 pointers to two items.
  65 It should return an integer which is negative,
  66 zero, or positive, depending on whether the first item is less than,
  67 equal to, or greater than the second.
  68 .PP
  69 .BR tsearch ()
  70 searches the tree for an item.
  71 .IR key
  72 points to the item to be searched for.
  73 .IR rootp
  74 points to a variable which points to the root of the tree.
  75 If the tree is empty,
  76 then the variable that
  77 .IR rootp
  78 points to should be set to NULL.
  79 If the item is found in the tree, then
  80 .BR tsearch ()
  81 returns a pointer
  82 to the corresponding tree node.
  83 (In other words,
  84 .BR tsearch ()
  85 returns a pointer to a pointer to the data item.)
  86 If the item is not found, then
  87 .BR tsearch ()
  88 adds it, and returns a
  89 pointer to the corresponding tree node.
  90 .PP
  91 .BR tfind ()
  92 is like
  93 .BR tsearch (),
  94 except that if the item is not
  95 found, then
  96 .BR tfind ()
  97 returns NULL.
  98 .PP
  99 .BR tdelete ()
 100 deletes an item from the tree.
 101 Its arguments are the same as for
 102 .BR tsearch ().
 103 .PP
 104 .BR twalk ()
 105 performs depth-first, left-to-right traversal of a binary
 106 tree.
 107 .IR root
 108 points to the starting node for the traversal.
 109 If that node is not the root, then only part of the tree will be visited.
 110 .BR twalk ()
 111 calls the user function
 112 .IR action
 113 each time a node is
 114 visited (that is, three times for an internal node, and once for a
 115 leaf).
 116 .IR action ,
 117 in turn, takes three arguments.
 118 The first argument is a pointer to the node being visited.
 119 The structure of the node is unspecified,
 120 but it is possible to cast the pointer to a pointer-to-pointer-to-element
 121 in order to access the element stored within the node.
 122 The application must not modify the structure pointed to by this argument.
 123 The second argument is an integer which
 124 takes one of the values
 125 .BR preorder ,
 126 .BR postorder ,
 127 or
 128 .BR endorder
 129 depending on whether this is the first, second, or
 130 third visit to the internal node,
 131 or the value
 132 .BR leaf
 133 if this is the single visit to a leaf node.
 134 (These symbols are defined in
 135 .IR <search.h> .)
 136 The third argument is the depth of the node;
 137 the root node has depth zero.
 138 .PP
 139 (More commonly,
 140 .BR preorder ,
 141 .BR postorder ,
 142 and
 143 .BR endorder
 144 are known as
 145 .BR preorder ,
 146 .BR inorder ,
 147 and
 148 .BR postorder :
 149 before visiting the children, after the first and before the second,
 150 and after visiting the children.
 151 Thus, the choice of name
 152 .BR post\%order
 153 is rather confusing.)
 154 .PP
 155 .BR tdestroy ()
 156 removes the whole tree pointed to by
 157 .IR root ,
 158 freeing all resources allocated by the
 159 .BR tsearch ()
 160 function.
 161 For the data in each tree node the function
 162 .IR free_node
 163 is called.
 164 The pointer to the data is passed as the argument to the function.
 165 If no such work is necessary,
 166 .IR free_node
 167 must point to a function
 168 doing nothing.
 169 .SH RETURN VALUE
 170 .BR tsearch ()
 171 returns a pointer to a matching node in the tree, or to
 172 the newly added node, or NULL if there was insufficient memory
 173 to add the item.
 174 .BR tfind ()
 175 returns a pointer to the node, or
 176 NULL if no match is found.
 177 If there are multiple items that match the key,
 178 the item whose node is returned is unspecified.
 179 .PP
 180 .BR tdelete ()
 181 returns a pointer to the parent of the node deleted, or
 182 NULL if the item was not found.
 183 If the deleted node was the root node,
 184 .BR tdelete ()
 185 returns a dangling pointer that must not be accessed.
 186 .PP
 187 .BR tsearch (),
 188 .BR tfind (),
 189 and
 190 .BR tdelete ()
 191 also
 192 return NULL if
 193 .IR rootp
 194 was NULL on entry.
 195 .SH ATTRIBUTES
 196 For an explanation of the terms used in this section, see
 197 .BR attributes (7).
 198 .TS
 199 allbox;
 200 lb lb lb
 201 l l l.
 202 Interface       Attribute       Value
 203 T{
 204 .BR tsearch (),
 205 .BR tfind (),
 206 .br
 207 .BR tdelete ()
 208 T}      Thread safety   MT-Safe race:rootp
 209 T{
 210 .BR twalk ()
 211 T}      Thread safety   MT-Safe race:root
 212 T{
 213 .BR tdestroy ()
 214 T}      Thread safety   MT-Safe
 215 .TE
 216 .SH CONFORMING TO
 217 POSIX.1-2001, POSIX.1-2008, SVr4.
 218 The function
 219 .BR tdestroy ()
 220 is a GNU extension.
 221 .SH NOTES
 222 .BR twalk ()
 223 takes a pointer to the root, while the other functions
 224 take a pointer to a variable which points to the root.
 225 .PP
 226 .BR tdelete ()
 227 frees the memory required for the node in the tree.
 228 The user is responsible for freeing the memory for the corresponding
 229 data.
 230 .PP
 231 The example program depends on the fact that
 232 .BR twalk ()
 233 makes no
 234 further reference to a node after calling the user function with
 235 argument "endorder" or "leaf".
 236 This works with the GNU library
 237 implementation, but is not in the System V documentation.
 238 .SH EXAMPLE
 239 The following program inserts twelve random numbers into a binary
 240 tree, where duplicate numbers are collapsed, then prints the numbers
 241 in order.
 242 .PP
 243 .EX
 244 #define _GNU_SOURCE     /* Expose declaration of tdestroy() */
 245 #include <search.h>
 246 #include <stdlib.h>
 247 #include <stdio.h>
 248 #include <time.h>
 249
 250 static void *root = NULL;
 251
 252 static void *
 253 xmalloc(unsigned n)
 254 {
 255     void *p;
 256     p = malloc(n);
 257     if (p)
 258         return p;
 259     fprintf(stderr, "insufficient memory\\n");
 260     exit(EXIT_FAILURE);
 261 }
 262
 263 static int
 264 compare(const void *pa, const void *pb)
 265 {
 266     if (*(int *) pa < *(int *) pb)
 267         return \-1;
 268     if (*(int *) pa > *(int *) pb)
 269         return 1;
 270     return 0;
 271 }
 272
 273 static void
 274 action(const void *nodep, const VISIT which, const int depth)
 275 {
 276     int *datap;
 277
 278     switch (which) {
 279     case preorder:
 280         break;
 281     case postorder:
 282         datap = *(int **) nodep;
 283         printf("%6d\\n", *datap);
 284         break;
 285     case endorder:
 286         break;
 287     case leaf:
 288         datap = *(int **) nodep;
 289         printf("%6d\\n", *datap);
 290         break;
 291     }
 292 }
 293
 294 int
 295 main(void)
 296 {
 297     int i, *ptr;
 298     void *val;
 299
 300     srand(time(NULL));
 301     for (i = 0; i < 12; i++) {
 302         ptr = xmalloc(sizeof(int));
 303         *ptr = rand() & 0xff;
 304         val = tsearch((void *) ptr, &root, compare);
 305         if (val == NULL)
 306             exit(EXIT_FAILURE);
 307         else if ((*(int **) val) != ptr)
 308             free(ptr);
 309     }
 310     twalk(root, action);
 311     tdestroy(root, free);
 312     exit(EXIT_SUCCESS);
 313 }
 314 .EE
 315 .SH SEE ALSO
 316 .BR bsearch (3),
 317 .BR hsearch (3),
 318 .BR lsearch (3),
 319 .BR qsort (3)