tsearch(3)


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, void *const *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 argument is a  pointer  to  the
   node  being  visited.  The structure of the node is unspecified, but it
   is possible to cast the pointer to a  pointer-to-pointer-to-element  in
   order  to  access  the element stored within the node.  The application
   must not modify the structure pointed to by this argument.  The  second
   argument  is  an  integer  which  takes  one  of  the  values preorder,
   postorder, or endorder depending on whether this is the first,  second,
   or  third  visit to the internal node, or the value leaf if this is the
   single  visit  to  a  leaf  node.   (These  symbols  are   defined   in
   <search.h>.)   The  third  argument  is the depth of the node; the root
   node has depth zero.

   (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.

ATTRIBUTES

   For   an   explanation   of   the  terms  used  in  this  section,  see
   attributes(7).

   ┌────────────────────┬───────────────┬────────────────────┐
   │InterfaceAttributeValue              │
   ├────────────────────┼───────────────┼────────────────────┤
   │tsearch(), tfind(), │ Thread safety │ MT-Safe race:rootp │
   │tdelete()           │               │                    │
   ├────────────────────┼───────────────┼────────────────────┤
   │twalk()             │ Thread safety │ MT-Safe race:root  │
   ├────────────────────┼───────────────┼────────────────────┤
   │tdestroy()          │ Thread safety │ MT-Safe            │
   └────────────────────┴───────────────┴────────────────────┘

CONFORMING TO

   POSIX.1-2001, POSIX.1-2008, SVr4.  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.

   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>

   static void *root = NULL;

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

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

   static 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 = 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 4.09 of the Linux  man-pages  project.   A
   description  of  the project, information about reporting bugs, and the
   latest    version    of    this    page,    can     be     found     at
   https://www.kernel.org/doc/man-pages/.





Opportunity


Personal Opportunity - Free software gives you access to billions of dollars of software at no cost. Use this software for your business, personal use or to develop a profitable skill. Access to source code provides access to a level of capabilities/information that companies protect though copyrights. Open source is a core component of the Internet and it is available to you. Leverage the billions of dollars in resources and capabilities to build a career, establish a business or change the world. The potential is endless for those who understand the opportunity.

Business Opportunity - Goldman Sachs, IBM and countless large corporations are leveraging open source to reduce costs, develop products and increase their bottom lines. Learn what these companies know about open source and how open source can give you the advantage.





Free Software


Free Software provides computer programs and capabilities at no cost but more importantly, it provides the freedom to run, edit, contribute to, and share the software. The importance of free software is a matter of access, not price. Software at no cost is a benefit but ownership rights to the software and source code is far more significant.


Free Office Software - The Libre Office suite provides top desktop productivity tools for free. This includes, a word processor, spreadsheet, presentation engine, drawing and flowcharting, database and math applications. Libre Office is available for Linux or Windows.





Free Books


The Free Books Library is a collection of thousands of the most popular public domain books in an online readable format. The collection includes great classical literature and more recent works where the U.S. copyright has expired. These books are yours to read and use without restrictions.


Source Code - Want to change a program or know how it works? Open Source provides the source code for its programs so that anyone can use, modify or learn how to write those programs themselves. Visit the GNU source code repositories to download the source.





Education


Study at Harvard, Stanford or MIT - Open edX provides free online courses from Harvard, MIT, Columbia, UC Berkeley and other top Universities. Hundreds of courses for almost all major subjects and course levels. Open edx also offers some paid courses and selected certifications.


Linux Manual Pages - A man or manual page is a form of software documentation found on Linux/Unix operating systems. Topics covered include computer programs (including library and system calls), formal standards and conventions, and even abstract concepts.