Unix/Linux Go Back    


Linux 2.6 - man page for twalk (linux section 3posix)

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


TDELETE(P)			    POSIX Programmer's Manual			       TDELETE(P)

NAME
       tdelete, tfind, tsearch, twalk - manage a binary search tree

SYNOPSIS
       #include <search.h>

       void *tdelete(const void *restrict key, void **restrict rootp,
	      int(*compar)(const void *, const void *));
       void *tfind(const void *key, void *const *rootp,
	      int(*compar)(const void *, const void *));
       void *tsearch(const void *key, void **rootp,
	      int (*compar)(const void *, const void *));
       void twalk(const void *root,
	      void (*action)(const void *, VISIT, int));

DESCRIPTION
       The  tdelete(),	tfind(), tsearch(), and twalk() functions manipulate binary search trees.
       Comparisons are made with a user-supplied routine, the address of which is passed  as  the
       compar  argument. This routine is called with two arguments, which are the pointers to the
       elements being compared.  The application shall	ensure	that  the  user-supplied  routine
       returns	an integer less than, equal to, or greater than 0, according to whether the first
       argument is to be considered less than, equal to, or greater than the second argument. The
       comparison function need not compare every byte, so arbitrary data may be contained in the
       elements in addition to the values being compared.

       The tsearch() function shall build and access the tree. The key argument is a  pointer  to
       an element to be accessed or stored. If there is a node in the tree whose element is equal
       to the value pointed to by key, a pointer to this found node shall be returned. Otherwise,
       the  value  pointed  to	by  key shall be inserted (that is, a new node is created and the
       value of key is copied to this node), and a pointer to this node returned.  Only  pointers
       are  copied, so the application shall ensure that the calling routine stores the data. The
       rootp argument points to a variable that points to the root  node  of  the  tree.  A  null
       pointer	value  for  the variable pointed to by rootp denotes an empty tree; in this case,
       the variable shall be set to point to the node which shall be at the root of the new tree.

       Like tsearch(), tfind() shall search for a node in the tree, returning a pointer to it  if
       found. However, if it is not found, tfind() shall return a null pointer. The arguments for
       tfind() are the same as for tsearch().

       The tdelete() function shall delete a node from a binary search tree.  The  arguments  are
       the  same  as  for  tsearch().	The  variable pointed to by rootp shall be changed if the
       deleted node was the root of the tree. The tdelete() function shall return  a  pointer  to
       the parent of the deleted node, or a null pointer if the node is not found.

       The  twalk()  function shall traverse a binary search tree. The root argument is a pointer
       to the root node of the tree to be traversed. (Any node in a tree may be used as the  root
       for a walk below that node.) The argument action is the name of a routine to be invoked at
       each node. This routine is, in turn, called with three arguments. The first argument shall
       be  the	address  of  the node being visited. The structure pointed to by this argument is
       unspecified and shall not be modified by the application, but it shall be possible to cast
       a pointer-to-node into a pointer-to-pointer-to-element to access the element stored in the
       node. The second argument shall be a value from an enumeration data type:

	      typedef enum { preorder, postorder, endorder, leaf } VISIT;

       (defined in <search.h>), depending on whether this is the first,  second,  or  third  time
       that  the  node is visited (during a depth-first, left-to-right traversal of the tree), or
       whether the node is a leaf. The third argument shall be the level of the node in the tree,
       with the root being level 0.

       If the calling function alters the pointer to the root, the result is undefined.

RETURN VALUE
       If  the	node  is  found, both tsearch() and tfind() shall return a pointer to it. If not,
       tfind() shall return a null pointer, and tsearch() shall return a pointer to the  inserted
       item.

       A  null	pointer  shall be returned by tsearch() if there is not enough space available to
       create a new node.

       A null pointer shall be returned by tdelete(), tfind(), and tsearch() if rootp is  a  null
       pointer on entry.

       The tdelete() function shall return a pointer to the parent of the deleted node, or a null
       pointer if the node is not found.

       The twalk() function shall not return a value.

ERRORS
       No errors are defined.

       The following sections are informative.

EXAMPLES
       The following code reads in strings and stores structures containing  a	pointer  to  each
       string  and a count of its length. It then walks the tree, printing out the stored strings
       and their lengths in alphabetical order.

	      #include <search.h>
	      #include <string.h>
	      #include <stdio.h>

	      #define STRSZ    10000
	      #define NODSZ    500

	      struct node {	 /* Pointers to these are stored in the tree. */
		  char	  *string;
		  int	  length;
	      };

	      char   string_space[STRSZ];  /* Space to store strings. */
	      struct node nodes[NODSZ];    /* Nodes to store. */
	      void  *root = NULL;	   /* This points to the root. */

	      int main(int argc, char *argv[])
	      {
		  char	 *strptr = string_space;
		  struct node	 *nodeptr = nodes;
		  void	 print_node(const void *, VISIT, int);
		  int	 i = 0, node_compare(const void *, const void *);

		  while (gets(strptr) != NULL && i++ < NODSZ)  {
		      /* Set node. */
		      nodeptr->string = strptr;
		      nodeptr->length = strlen(strptr);
		      /* Put node into the tree. */
		      (void) tsearch((void *)nodeptr, (void **)&root,
			  node_compare);
		      /* Adjust pointers, so we do not overwrite tree. */
		      strptr += nodeptr->length + 1;
		      nodeptr++;
		  }
		  twalk(root, print_node);
		  return 0;
	      }

	      /*
	       *  This routine compares two nodes, based on an
	       *  alphabetical ordering of the string field.
	       */
	      int
	      node_compare(const void *node1, const void *node2)
	      {
		  return strcmp(((const struct node *) node1)->string,
		      ((const struct node *) node2)->string);
	      }

	      /*
	       *  This routine prints out a node, the second time
	       *  twalk encounters it or if it is a leaf.
	       */
	      void
	      print_node(const void *ptr, VISIT order, int level)
	      {
		  const struct node *p = *(const struct node **) ptr;

		  if (order == postorder || order == leaf)  {
		      (void) printf("string = %s,  length = %d\n",
			  p->string, p->length);
		  }
	      }

APPLICATION USAGE
       The root argument to twalk() is one level of indirection less than the rootp arguments  to
       tdelete() and tsearch().

       There  are  two	nomenclatures used to refer to the order in which tree nodes are visited.
       The tsearch() function uses preorder, postorder, and endorder  to  refer  respectively  to
       visiting a node before any of its children, after its left child and before its right, and
       after both its children.  The alternative nomenclature uses preorder,  inorder,	and  pos-
       torder  to refer to the same visits, which could result in some confusion over the meaning
       of postorder.

RATIONALE
       None.

FUTURE DIRECTIONS
       None.

SEE ALSO
       hcreate() , lsearch() , the Base Definitions volume of IEEE Std 1003.1-2001, <search.h>

COPYRIGHT
       Portions of this text are reprinted and	reproduced  in	electronic  form  from	IEEE  Std
       1003.1,	2003  Edition,	Standard  for Information Technology -- Portable Operating System
       Interface (POSIX), The Open Group Base Specifications Issue 6, Copyright (C) 2001-2003  by
       the  Institute  of  Electrical  and  Electronics Engineers, Inc and The Open Group. In the
       event of any discrepancy between this version and the original IEEE  and  The  Open  Group
       Standard, the original IEEE and The Open Group Standard is the referee document. The orig-
       inal Standard can be obtained online at http://www.opengroup.org/unix/online.html .

IEEE/The Open Group			       2003				       TDELETE(P)
Unix & Linux Commands & Man Pages : 2000 - 2018 Unix and Linux Forums


All times are GMT -4. The time now is 09:33 AM.