man3/tsearch.3

   1 '\" t
   2 .\" Copyright 1995 by Jim Van Zandt <jrv@vanzandt.mv.com>
   3 .\"
   4 .\" SPDX-License-Identifier: Linux-man-pages-copyleft
   5 .\"
   6 .TH tsearch 3 (date) "Linux man-pages (unreleased)"
   7 .SH NAME
   8 tsearch, tfind, tdelete, twalk, twalk_r, tdestroy \- manage a binary search tree
   9 .SH LIBRARY
  10 Standard C library
  11 .RI ( libc ", " \-lc )
  12 .SH SYNOPSIS
  13 .nf
  14 .B #include <search.h>
  15 .PP
  16 .B typedef enum { preorder, postorder, endorder, leaf } VISIT;
  17 .PP
  18 .BI "void *tsearch(const void *" key ", void **" rootp ,
  19 .BI "                int (*" compar ")(const void *, const void *));"
  20 .BI "void *tfind(const void *" key ", void *const *" rootp ,
  21 .BI "                int (*" compar ")(const void *, const void *));"
  22 .BI "void *tdelete(const void *restrict " key ", void **restrict " rootp ,
  23 .BI "                int (*" compar ")(const void *, const void *));"
  24 .BI "void twalk(const void *" root ,
  25 .BI "                void (*" action ")(const void *" nodep ", VISIT " which ,
  26 .BI "                               int " depth ));
  27 .PP
  28 .BR "#define _GNU_SOURCE" "         /* See feature_test_macros(7) */"
  29 .B #include <search.h>
  30 .PP
  31 .BI "void twalk_r(const void *" root ,
  32 .BI "                void (*" action ")(const void *" nodep ", VISIT " which ,
  33 .BI "                               void *" closure ),
  34 .BI "                void *" closure );
  35 .BI "void tdestroy(void *" root ", void (*" free_node ")(void *" nodep ));
  36 .fi
  37 .SH DESCRIPTION
  38 .BR tsearch (),
  39 .BR tfind (),
  40 .BR twalk (),
  41 and
  42 .BR tdelete ()
  43 manage a
  44 binary search tree.
  45 They are generalized from Knuth (6.2.2) Algorithm T.
  46 The first field in each node of the tree is a pointer to the
  47 corresponding data item.
  48 (The calling program must store the actual data.)
  49 .I compar
  50 points to a comparison routine, which takes
  51 pointers to two items.
  52 It should return an integer which is negative,
  53 zero, or positive, depending on whether the first item is less than,
  54 equal to, or greater than the second.
  55 .PP
  56 .BR tsearch ()
  57 searches the tree for an item.
  58 .I key
  59 points to the item to be searched for.
  60 .I rootp
  61 points to a variable which points to the root of the tree.
  62 If the tree is empty,
  63 then the variable that
  64 .I rootp
  65 points to should be set to NULL.
  66 If the item is found in the tree, then
  67 .BR tsearch ()
  68 returns a pointer
  69 to the corresponding tree node.
  70 (In other words,
  71 .BR tsearch ()
  72 returns a pointer to a pointer to the data item.)
  73 If the item is not found, then
  74 .BR tsearch ()
  75 adds it, and returns a
  76 pointer to the corresponding tree node.
  77 .PP
  78 .BR tfind ()
  79 is like
  80 .BR tsearch (),
  81 except that if the item is not
  82 found, then
  83 .BR tfind ()
  84 returns NULL.
  85 .PP
  86 .BR tdelete ()
  87 deletes an item from the tree.
  88 Its arguments are the same as for
  89 .BR tsearch ().
  90 .PP
  91 .BR twalk ()
  92 performs depth-first, left-to-right traversal of a binary
  93 tree.
  94 .I root
  95 points to the starting node for the traversal.
  96 If that node is not the root, then only part of the tree will be visited.
  97 .BR twalk ()
  98 calls the user function
  99 .I action
 100 each time a node is
 101 visited (that is, three times for an internal node, and once for a
 102 leaf).
 103 .IR action ,
 104 in turn, takes three arguments.
 105 The first argument is a pointer to the node being visited.
 106 The structure of the node is unspecified,
 107 but it is possible to cast the pointer to a pointer-to-pointer-to-element
 108 in order to access the element stored within the node.
 109 The application must not modify the structure pointed to by this argument.
 110 The second argument is an integer which
 111 takes one of the values
 112 .BR preorder ,
 113 .BR postorder ,
 114 or
 115 .B endorder
 116 depending on whether this is the first, second, or
 117 third visit to the internal node,
 118 or the value
 119 .B leaf
 120 if this is the single visit to a leaf node.
 121 (These symbols are defined in
 122 .IR <search.h> .)
 123 The third argument is the depth of the node;
 124 the root node has depth zero.
 125 .PP
 126 (More commonly,
 127 .BR preorder ,
 128 .BR postorder ,
 129 and
 130 .B endorder
 131 are known as
 132 .BR preorder ,
 133 .BR inorder ,
 134 and
 135 .BR postorder :
 136 before visiting the children, after the first and before the second,
 137 and after visiting the children.
 138 Thus, the choice of name
 139 .B post\%order
 140 is rather confusing.)
 141 .PP
 142 .BR twalk_r ()
 143 is similar to
 144 .BR twalk (),
 145 but instead of the
 146 .I depth
 147 argument, the
 148 .I closure
 149 argument pointer is passed to each invocation of the action callback,
 150 unchanged.
 151 This pointer can be used to pass information to and from
 152 the callback function in a thread-safe fashion, without resorting
 153 to global variables.
 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 .I 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 .I 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 .I 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 .ad l
 199 .nh
 200 .TS
 201 allbox;
 202 lbx lb lb
 203 l l l.
 204 Interface       Attribute       Value
 205 T{
 206 .BR tsearch (),
 207 .BR tfind (),
 208 .BR tdelete ()
 209 T}      Thread safety   MT-Safe race:rootp
 210 T{
 211 .BR twalk ()
 212 T}      Thread safety   MT-Safe race:root
 213 T{
 214 .BR twalk_r ()
 215 T}      Thread safety   MT-Safe race:root
 216 T{
 217 .BR tdestroy ()
 218 T}      Thread safety   MT-Safe
 219 .TE
 220 .hy
 221 .ad
 222 .sp 1
 223 .SH STANDARDS
 224 .TP
 225 .BR tsearch ()
 226 .TQ
 227 .BR tfind ()
 228 .TQ
 229 .BR tdelete ()
 230 .TQ
 231 .BR twalk ()
 232 POSIX.1-2008.
 233 .TP
 234 .BR tdestroy ()
 235 .TQ
 236 .BR twalk_r ()
 237 GNU.
 238 .SH HISTORY
 239 .TP
 240 .BR tsearch ()
 241 .TQ
 242 .BR tfind ()
 243 .TQ
 244 .BR tdelete ()
 245 .TQ
 246 .BR twalk ()
 247 POSIX.1-2001, POSIX.1-2008, SVr4.
 248 .TP
 249 .BR twalk_r ()
 250 glibc 2.30.
 251 .SH NOTES
 252 .BR twalk ()
 253 takes a pointer to the root, while the other functions
 254 take a pointer to a variable which points to the root.
 255 .PP
 256 .BR tdelete ()
 257 frees the memory required for the node in the tree.
 258 The user is responsible for freeing the memory for the corresponding
 259 data.
 260 .PP
 261 The example program depends on the fact that
 262 .BR twalk ()
 263 makes no
 264 further reference to a node after calling the user function with
 265 argument "endorder" or "leaf".
 266 This works with the GNU library
 267 implementation, but is not in the System V documentation.
 268 .SH EXAMPLES
 269 The following program inserts twelve random numbers into a binary
 270 tree, where duplicate numbers are collapsed, then prints the numbers
 271 in order.
 272 .PP
 273 .\" SRC BEGIN (tsearch.c)
 274 .EX
 275 #define _GNU_SOURCE     /* Expose declaration of tdestroy() */
 276 #include <search.h>
 277 #include <stddef.h>
 278 #include <stdio.h>
 279 #include <stdlib.h>
 280 #include <time.h>
 281 \&
 282 static void *root = NULL;
 283 \&
 284 static void *
 285 xmalloc(size_t n)
 286 {
 287     void *p;
 288 \&
 289     p = malloc(n);
 290     if (p)
 291         return p;
 292     fprintf(stderr, "insufficient memory\en");
 293     exit(EXIT_FAILURE);
 294 }
 295 \&
 296 static int
 297 compare(const void *pa, const void *pb)
 298 {
 299     if (*(int *) pa < *(int *) pb)
 300         return \-1;
 301     if (*(int *) pa > *(int *) pb)
 302         return 1;
 303     return 0;
 304 }
 305 \&
 306 static void
 307 action(const void *nodep, VISIT which, int depth)
 308 {
 309     int *datap;
 310 \&
 311     switch (which) {
 312     case preorder:
 313         break;
 314     case postorder:
 315         datap = *(int **) nodep;
 316         printf("%6d\en", *datap);
 317         break;
 318     case endorder:
 319         break;
 320     case leaf:
 321         datap = *(int **) nodep;
 322         printf("%6d\en", *datap);
 323         break;
 324     }
 325 }
 326 \&
 327 int
 328 main(void)
 329 {
 330     int  *ptr;
 331     int  **val;
 332 \&
 333     srand(time(NULL));
 334     for (unsigned int i = 0; i < 12; i++) {
 335         ptr = xmalloc(sizeof(*ptr));
 336         *ptr = rand() & 0xff;
 337         val = tsearch(ptr, &root, compare);
 338         if (val == NULL)
 339             exit(EXIT_FAILURE);
 340         if (*val != ptr)
 341             free(ptr);
 342     }
 343     twalk(root, action);
 344     tdestroy(root, free);
 345     exit(EXIT_SUCCESS);
 346 }
 347 .EE
 348 .\" SRC END
 349 .SH SEE ALSO
 350 .BR bsearch (3),
 351 .BR hsearch (3),
 352 .BR lsearch (3),
 353 .BR qsort (3)