Unix/Linux Go Back    


Linux 2.6 - man page for tsearch (linux section 3)

Linux & Unix Commands - Search Man Pages
Man Page or Keyword Search:   man
Select Man Page Set:       apropos Keyword Search (sections above)


TSEARCH(3)			    Linux Programmer's Manual			       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, 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 argument is a pointer to the node being visited.  The struc-
       ture 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 pos-
       torder:	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 vari-
       able 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>

       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 = 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.55 of the Linux man-pages project.  A  description  of  the
       project,     and    information	  about    reporting	bugs,	 can	be    found    at
       http://www.kernel.org/doc/man-pages/.

GNU					    2012-08-03				       TSEARCH(3)
Unix & Linux Commands & Man Pages : ©2000 - 2018 Unix and Linux Forums


All times are GMT -4. The time now is 01:52 AM.