ABCDEFGHIJKLMNOPQRSTUVWXYZ

tsearch

TSEARCH(3)                 Linux Programmer's Manual                TSEARCH(3)



NAME
       tsearch, tfind, tdelete, twalk - 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
       #include <search.h>

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

DESCRIPTION
       tsearch, tfind, twalk, and tdelete manage a binary tree.  They are gen-
       eralized 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 inte-
       ger 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 vis-
       ited.  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.

       (More commonly, preorder, postorder, and endorder  are  known  as  pre-
       order,  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 rootp, 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.

WARNINGS
       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 SysV documentation.

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

           #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(1);
           }

           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() {
             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(1);
             }
             twalk(root, action);
             return 0;
           }

CONFORMING TO
       SVID.  The function tdestroy() is a GNU extension.

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




GNU                               1995-09-24                        TSEARCH(3)