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  2021-03-22 "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 "typedef enum { preorder, postorder, endorder, leaf } VISIT;"
  33 .PP
  34 .BI "void *tsearch(const void *" key ", void **" rootp ,
  35 .BI "                int (*" compar ")(const void *, const void *));"
  36 .BI "void *tfind(const void *" key ", void *const *" rootp ,
  37 .BI "                int (*" compar ")(const void *, const void *));"
  38 .BI "void *tdelete(const void *restrict " key ", void **restrict " rootp ,
  39 .BI "                int (*" compar ")(const void *, const void *));"
  40 .BI "void twalk(const void *" root ,
  41 .BI "                void (*" action ")(const void *" nodep ", VISIT " which ,
  42 .BI "                               int " depth ));
  43 .PP
  44 .BR "#define _GNU_SOURCE" "         /* See feature_test_macros(7) */"
  45 .B #include <search.h>
  46 .PP
  47 .BI "void twalk_r(const void *" root ,
  48 .BI "                void (*" action ")(const void *" nodep ", VISIT " which ,
  49 .BI "                               void *" closure ),
  50 .BI "                void *" closure );
  51 .BI "void tdestroy(void *" root ", void (*" free_node ")(void *" nodep ));
  52 .fi
  53 .SH DESCRIPTION
  54 .BR tsearch (),
  55 .BR tfind (),
  56 .BR twalk (),
  57 and
  58 .BR tdelete ()
  59 manage a
  60 binary search tree.
  61 They are generalized from Knuth (6.2.2) Algorithm T.
  62 The first field in each node of the tree is a pointer to the
  63 corresponding data item.
  64 (The calling program must store the actual data.)
  65 .I compar
  66 points to a comparison routine, which takes
  67 pointers to two items.
  68 It should return an integer which is negative,
  69 zero, or positive, depending on whether the first item is less than,
  70 equal to, or greater than the second.
  71 .PP
  72 .BR tsearch ()
  73 searches the tree for an item.
  74 .I key
  75 points to the item to be searched for.
  76 .I rootp
  77 points to a variable which points to the root of the tree.
  78 If the tree is empty,
  79 then the variable that
  80 .I rootp
  81 points to should be set to NULL.
  82 If the item is found in the tree, then
  83 .BR tsearch ()
  84 returns a pointer
  85 to the corresponding tree node.
  86 (In other words,
  87 .BR tsearch ()
  88 returns a pointer to a pointer to the data item.)
  89 If the item is not found, then
  90 .BR tsearch ()
  91 adds it, and returns a
  92 pointer to the corresponding tree node.
  93 .PP
  94 .BR tfind ()
  95 is like
  96 .BR tsearch (),
  97 except that if the item is not
  98 found, then
  99 .BR tfind ()
 100 returns NULL.
 101 .PP
 102 .BR tdelete ()
 103 deletes an item from the tree.
 104 Its arguments are the same as for
 105 .BR tsearch ().
 106 .PP
 107 .BR twalk ()
 108 performs depth-first, left-to-right traversal of a binary
 109 tree.
 110 .I root
 111 points to the starting node for the traversal.
 112 If that node is not the root, then only part of the tree will be visited.
 113 .BR twalk ()
 114 calls the user function
 115 .I action
 116 each time a node is
 117 visited (that is, three times for an internal node, and once for a
 118 leaf).
 119 .IR action ,
 120 in turn, takes three arguments.
 121 The first argument is a pointer to the node being visited.
 122 The structure of the node is unspecified,
 123 but it is possible to cast the pointer to a pointer-to-pointer-to-element
 124 in order to access the element stored within the node.
 125 The application must not modify the structure pointed to by this argument.
 126 The second argument is an integer which
 127 takes one of the values
 128 .BR preorder ,
 129 .BR postorder ,
 130 or
 131 .B endorder
 132 depending on whether this is the first, second, or
 133 third visit to the internal node,
 134 or the value
 135 .B leaf
 136 if this is the single visit to a leaf node.
 137 (These symbols are defined in
 138 .IR <search.h> .)
 139 The third argument is the depth of the node;
 140 the root node has depth zero.
 141 .PP
 142 (More commonly,
 143 .BR preorder ,
 144 .BR postorder ,
 145 and
 146 .B endorder
 147 are known as
 148 .BR preorder ,
 149 .BR inorder ,
 150 and
 151 .BR postorder :
 152 before visiting the children, after the first and before the second,
 153 and after visiting the children.
 154 Thus, the choice of name
 155 .B post\%order
 156 is rather confusing.)
 157 .PP
 158 .BR twalk_r ()
 159 is similar to
 160 .BR twalk (),
 161 but instead of the
 162 .I depth
 163 argument, the
 164 .I closure
 165 argument pointer is passed to each invocation of the action callback,
 166 unchanged.
 167 This pointer can be used to pass information to and from
 168 the callback function in a thread-safe fashion, without resorting
 169 to global variables.
 170 .PP
 171 .BR tdestroy ()
 172 removes the whole tree pointed to by
 173 .IR root ,
 174 freeing all resources allocated by the
 175 .BR tsearch ()
 176 function.
 177 For the data in each tree node the function
 178 .I free_node
 179 is called.
 180 The pointer to the data is passed as the argument to the function.
 181 If no such work is necessary,
 182 .I free_node
 183 must point to a function
 184 doing nothing.
 185 .SH RETURN VALUE
 186 .BR tsearch ()
 187 returns a pointer to a matching node in the tree, or to
 188 the newly added node, or NULL if there was insufficient memory
 189 to add the item.
 190 .BR tfind ()
 191 returns a pointer to the node, or
 192 NULL if no match is found.
 193 If there are multiple items that match the key,
 194 the item whose node is returned is unspecified.
 195 .PP
 196 .BR tdelete ()
 197 returns a pointer to the parent of the node deleted, or
 198 NULL if the item was not found.
 199 If the deleted node was the root node,
 200 .BR tdelete ()
 201 returns a dangling pointer that must not be accessed.
 202 .PP
 203 .BR tsearch (),
 204 .BR tfind (),
 205 and
 206 .BR tdelete ()
 207 also
 208 return NULL if
 209 .I rootp
 210 was NULL on entry.
 211 .SH VERSIONS
 212 .BR twalk_r ()
 213 is available in glibc since version 2.30.
 214 .SH ATTRIBUTES
 215 For an explanation of the terms used in this section, see
 216 .BR attributes (7).
 217 .ad l
 218 .nh
 219 .TS
 220 allbox;
 221 lbx lb lb
 222 l l l.
 223 Interface       Attribute       Value
 224 T{
 225 .BR tsearch (),
 226 .BR tfind (),
 227 .BR tdelete ()
 228 T}      Thread safety   MT-Safe race:rootp
 229 T{
 230 .BR twalk ()
 231 T}      Thread safety   MT-Safe race:root
 232 T{
 233 .BR twalk_r ()
 234 T}      Thread safety   MT-Safe race:root
 235 T{
 236 .BR tdestroy ()
 237 T}      Thread safety   MT-Safe
 238 .TE
 239 .hy
 240 .ad
 241 .sp 1
 242 .SH CONFORMING TO
 243 POSIX.1-2001, POSIX.1-2008, SVr4.
 244 The functions
 245 .BR tdestroy ()
 246 and
 247 .BR twalk_r ()
 248 are GNU extensions.
 249 .SH NOTES
 250 .BR twalk ()
 251 takes a pointer to the root, while the other functions
 252 take a pointer to a variable which points to the root.
 253 .PP
 254 .BR tdelete ()
 255 frees the memory required for the node in the tree.
 256 The user is responsible for freeing the memory for the corresponding
 257 data.
 258 .PP
 259 The example program depends on the fact that
 260 .BR twalk ()
 261 makes no
 262 further reference to a node after calling the user function with
 263 argument "endorder" or "leaf".
 264 This works with the GNU library
 265 implementation, but is not in the System V documentation.
 266 .SH EXAMPLES
 267 The following program inserts twelve random numbers into a binary
 268 tree, where duplicate numbers are collapsed, then prints the numbers
 269 in order.
 270 .PP
 271 .EX
 272 #define _GNU_SOURCE     /* Expose declaration of tdestroy() */
 273 #include <search.h>
 274 #include <stddef.h>
 275 #include <stdlib.h>
 276 #include <stdio.h>
 277 #include <time.h>
 278
 279 static void *root = NULL;
 280
 281 static void *
 282 xmalloc(size_t n)
 283 {
 284     void *p;
 285     p = malloc(n);
 286     if (p)
 287         return p;
 288     fprintf(stderr, "insufficient memory\en");
 289     exit(EXIT_FAILURE);
 290 }
 291
 292 static int
 293 compare(const void *pa, const void *pb)
 294 {
 295     if (*(int *) pa < *(int *) pb)
 296         return \-1;
 297     if (*(int *) pa > *(int *) pb)
 298         return 1;
 299     return 0;
 300 }
 301
 302 static void
 303 action(const void *nodep, VISIT which, int depth)
 304 {
 305     int *datap;
 306
 307     switch (which) {
 308     case preorder:
 309         break;
 310     case postorder:
 311         datap = *(int **) nodep;
 312         printf("%6d\en", *datap);
 313         break;
 314     case endorder:
 315         break;
 316     case leaf:
 317         datap = *(int **) nodep;
 318         printf("%6d\en", *datap);
 319         break;
 320     }
 321 }
 322
 323 int
 324 main(void)
 325 {
 326     int **val;
 327
 328     srand(time(NULL));
 329     for (int i = 0; i < 12; i++) {
 330         int *ptr = xmalloc(sizeof(*ptr));
 331         *ptr = rand() & 0xff;
 332         val = tsearch(ptr, &root, compare);
 333         if (val == NULL)
 334             exit(EXIT_FAILURE);
 335         else if (*val != ptr)
 336             free(ptr);
 337     }
 338     twalk(root, action);
 339     tdestroy(root, free);
 340     exit(EXIT_SUCCESS);
 341 }
 342 .EE
 343 .SH SEE ALSO
 344 .BR bsearch (3),
 345 .BR hsearch (3),
 346 .BR lsearch (3),
 347 .BR qsort (3)