Provided by: manpages-dev_3.35-0.1ubuntu1_all bug

NAME

       tsearch, tfind, tdelete, twalk, tdestroy - manage a binary tree

SYNOPSIS

       #include <search.h>

       void *tsearch(const void *key, void **rootp,
                       int (*compar)(const void *, const void *));

       void *tfind(const void *key, const void **rootp,
                       int (*compar)(const void *, const void *));

       void *tdelete(const void *key, void **rootp,
                       int (*compar)(const void *, const void *));

       void twalk(const void *root, void (*action)(const void *nodep,
                                          const VISIT which,
                                          const int depth));

       #define _GNU_SOURCE         /* See feature_test_macros(7) */
       #include <search.h>

       void tdestroy(void *root, void (*free_node)(void *nodep));

DESCRIPTION

       tsearch(),  tfind(),  twalk(),  and  tdelete() manage a binary tree.  They are generalized
       from Knuth (6.2.2) Algorithm T.  The first field in each node of the tree is a pointer  to
       the  corresponding  data  item.  (The calling program must store the actual data.)  compar
       points to a comparison routine, which takes pointers to two items.  It  should  return  an
       integer  which is negative, zero, or positive, depending on whether the first item is less
       than, equal to, or greater than the second.

       tsearch() searches the tree for an item.  key points to  the  item  to  be  searched  for.
       rootp  points  to  a variable which points to the root of the tree.  If the tree is empty,
       then the variable that rootp points to should be set to NULL.  If the item is found in the
       tree, then tsearch() returns a pointer to it.  If it is not found, then tsearch() adds it,
       and returns a pointer to the newly added item.

       tfind() is like tsearch(), except that if the item is  not  found,  then  tfind()  returns
       NULL.

       tdelete() deletes an item from the tree.  Its arguments are the same as for tsearch().

       twalk()  performs  depth-first,  left-to-right traversal of a binary tree.  root points to
       the starting node for the traversal.  If that node is not the root, then only part of  the
       tree  will be visited.  twalk() calls the user function action each time a node is visited
       (that is, three times for an internal node, and once for a leaf).  action, in turn,  takes
       three  arguments.   The  first  is  a pointer to the node being visited.  The second is an
       integer which takes on the values preorder, postorder, and endorder depending  on  whether
       this  is  the  first,  second,  or  third visit to the internal node, or leaf if it is the
       single visit to a leaf node.  (These  symbols  are  defined  in  <search.h>.)   The  third
       argument  is  the  depth of the node, with zero being the root.  You should not modify the
       tree while traversing it as the the results would be undefined.

       (More commonly, preorder, postorder, and endorder are  known  as  preorder,  inorder,  and
       postorder:  before visiting the children, after the first and before the second, and after
       visiting the children.  Thus, the choice of name postorder is rather confusing.)

       tdestroy() removes the whole tree pointed to by root, freeing all resources  allocated  by
       the  tsearch() function.  For the data in each tree node the function free_node is called.
       The pointer to the data is passed as the argument to the function.  If  no  such  work  is
       necessary free_node must point to a function doing nothing.

RETURN VALUE

       tsearch() returns a pointer to a matching item in the tree, or to the newly added item, or
       NULL if there was insufficient memory to add the item.  tfind() returns a pointer  to  the
       item,  or  NULL  if no match is found.  If there are multiple elements that match the key,
       the element returned is unspecified.

       tdelete() returns a pointer to the parent of the item deleted, or NULL if the item was not
       found.

       tsearch(), tfind(), and tdelete() also return NULL if rootp was NULL on entry.

CONFORMING TO

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

NOTES

       twalk()  takes  a  pointer  to  the  root,  while  the other functions take a pointer to a
       variable which points to the root.

       twalk() uses postorder to mean "after the left subtree, but  before  the  right  subtree".
       Some  authorities  would  call this "inorder", and reserve "postorder" to mean "after both
       subtrees".

       tdelete() frees the memory required for the node in the tree.  The user is responsible for
       freeing the memory for the corresponding data.

       The  example program depends on the fact that twalk() makes no further reference to a node
       after calling the user function with argument "endorder" or "leaf".  This works  with  the
       GNU library implementation, but is not in the System V documentation.

EXAMPLE

       The  following  program  inserts twelve random numbers into a binary tree, where duplicate
       numbers are collapsed, then prints the numbers in order.

       #define _GNU_SOURCE     /* Expose declaration of tdestroy() */
       #include <search.h>
       #include <stdlib.h>
       #include <stdio.h>
       #include <time.h>

       void *root = NULL;

       void *
       xmalloc(unsigned n)
       {
           void *p;
           p = malloc(n);
           if (p)
               return p;
           fprintf(stderr, "insufficient memory\n");
           exit(EXIT_FAILURE);
       }

       int
       compare(const void *pa, const void *pb)
       {
           if (*(int *) pa < *(int *) pb)
               return -1;
           if (*(int *) pa > *(int *) pb)
               return 1;
           return 0;
       }

       void
       action(const void *nodep, const VISIT which, const int depth)
       {
           int *datap;

           switch (which) {
           case preorder:
               break;
           case postorder:
               datap = *(int **) nodep;
               printf("%6d\n", *datap);
               break;
           case endorder:
               break;
           case leaf:
               datap = *(int **) nodep;
               printf("%6d\n", *datap);
               break;
           }
       }

       int
       main(void)
       {
           int i, *ptr;
           void *val;

           srand(time(NULL));
           for (i = 0; i < 12; i++) {
               ptr = (int *) xmalloc(sizeof(int));
               *ptr = rand() & 0xff;
               val = tsearch((void *) ptr, &root, compare);
               if (val == NULL)
                   exit(EXIT_FAILURE);
               else if ((*(int **) val) != ptr)
                   free(ptr);
           }
           twalk(root, action);
           tdestroy(root, free);
           exit(EXIT_SUCCESS);
       }

SEE ALSO

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

COLOPHON

       This page is part of release 3.35 of the Linux man-pages project.  A  description  of  the
       project,  and information about reporting bugs, can be found at http://man7.org/linux/man-
       pages/.