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 .P
  16 .B typedef enum { preorder, postorder, endorder, leaf } VISIT;
  17 .P
  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 .P
  28 .BR "#define _GNU_SOURCE" "         /* See feature_test_macros(7) */"
  29 .B #include <search.h>
  30 .P
  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 .P
  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 .P
  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 .P
  86 .BR tdelete ()
  87 deletes an item from the tree.
  88 Its arguments are the same as for
  89 .BR tsearch ().
  90 .P
  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 .P
 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 .P
 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 .P
 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 .P
 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 .P
 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 .TS
 199 allbox;
 200 lbx lb lb
 201 l l l.
 202 Interface       Attribute       Value
 203 T{
 204 .na
 205 .nh
 206 .BR tsearch (),
 207 .BR tfind (),
 208 .BR tdelete ()
 209 T}      Thread safety   MT-Safe race:rootp
 210 T{
 211 .na
 212 .nh
 213 .BR twalk ()
 214 T}      Thread safety   MT-Safe race:root
 215 T{
 216 .na
 217 .nh
 218 .BR twalk_r ()
 219 T}      Thread safety   MT-Safe race:root
 220 T{
 221 .na
 222 .nh
 223 .BR tdestroy ()
 224 T}      Thread safety   MT-Safe
 225 .TE
 226 .SH STANDARDS
 227 .TP
 228 .BR tsearch ()
 229 .TQ
 230 .BR tfind ()
 231 .TQ
 232 .BR tdelete ()
 233 .TQ
 234 .BR twalk ()
 235 POSIX.1-2008.
 236 .TP
 237 .BR tdestroy ()
 238 .TQ
 239 .BR twalk_r ()
 240 GNU.
 241 .SH HISTORY
 242 .TP
 243 .BR tsearch ()
 244 .TQ
 245 .BR tfind ()
 246 .TQ
 247 .BR tdelete ()
 248 .TQ
 249 .BR twalk ()
 250 POSIX.1-2001, POSIX.1-2008, SVr4.
 251 .TP
 252 .BR twalk_r ()
 253 glibc 2.30.
 254 .SH NOTES
 255 .BR twalk ()
 256 takes a pointer to the root, while the other functions
 257 take a pointer to a variable which points to the root.
 258 .P
 259 .BR tdelete ()
 260 frees the memory required for the node in the tree.
 261 The user is responsible for freeing the memory for the corresponding
 262 data.
 263 .P
 264 The example program depends on the fact that
 265 .BR twalk ()
 266 makes no
 267 further reference to a node after calling the user function with
 268 argument "endorder" or "leaf".
 269 This works with the GNU library
 270 implementation, but is not in the System V documentation.
 271 .SH EXAMPLES
 272 The following program inserts twelve random numbers into a binary
 273 tree, where duplicate numbers are collapsed, then prints the numbers
 274 in order.
 275 .P
 276 .\" SRC BEGIN (tsearch.c)
 277 .EX
 278 #define _GNU_SOURCE     /* Expose declaration of tdestroy() */
 279 #include <search.h>
 280 #include <stddef.h>
 281 #include <stdio.h>
 282 #include <stdlib.h>
 283 #include <time.h>
 284 \&
 285 static void *root = NULL;
 286 \&
 287 static void *
 288 xmalloc(size_t n)
 289 {
 290     void *p;
 291 \&
 292     p = malloc(n);
 293     if (p)
 294         return p;
 295     fprintf(stderr, "insufficient memory\en");
 296     exit(EXIT_FAILURE);
 297 }
 298 \&
 299 static int
 300 compare(const void *pa, const void *pb)
 301 {
 302     if (*(int *) pa < *(int *) pb)
 303         return \-1;
 304     if (*(int *) pa > *(int *) pb)
 305         return 1;
 306     return 0;
 307 }
 308 \&
 309 static void
 310 action(const void *nodep, VISIT which, int depth)
 311 {
 312     int *datap;
 313 \&
 314     switch (which) {
 315     case preorder:
 316         break;
 317     case postorder:
 318         datap = *(int **) nodep;
 319         printf("%6d\en", *datap);
 320         break;
 321     case endorder:
 322         break;
 323     case leaf:
 324         datap = *(int **) nodep;
 325         printf("%6d\en", *datap);
 326         break;
 327     }
 328 }
 329 \&
 330 int
 331 main(void)
 332 {
 333     int  *ptr;
 334     int  **val;
 335 \&
 336     srand(time(NULL));
 337     for (unsigned int i = 0; i < 12; i++) {
 338         ptr = xmalloc(sizeof(*ptr));
 339         *ptr = rand() & 0xff;
 340         val = tsearch(ptr, &root, compare);
 341         if (val == NULL)
 342             exit(EXIT_FAILURE);
 343         if (*val != ptr)
 344             free(ptr);
 345     }
 346     twalk(root, action);
 347     tdestroy(root, free);
 348     exit(EXIT_SUCCESS);
 349 }
 350 .EE
 351 .\" SRC END
 352 .SH SEE ALSO
 353 .BR bsearch (3),
 354 .BR hsearch (3),
 355 .BR lsearch (3),
 356 .BR qsort (3)