Content-type: text/html Man page of tsearch

tsearch

Section: C Library Functions (3)
Index Return to Main Contents
 

NAME

tsearch, tfind, tdelete, twalk - Manage binary search trees  

LIBRARY

Standard C Library (libc.so, libc.a)  

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 *, VISIT, int));  

STANDARDS

Interfaces documented on this reference page conform to industry standards as follows:

tsearch(), tfind(), tdelete(), twalk():  XPG4, XPG4-UNIX

Refer to the standards(5) reference page for more information about industry standards and associated tags.  

PARAMETERS

Points to a key that specifies the entry to be searched in the binary tree. Points to a variable that points to the root of the binary tree. Specifies the name of a user-supplied comparison function (strcmp(), for example). This function is called with two parameters that point to the data undergoing comparison in the binary tree. Points to the root of the binary tree to be walked. The name of a routine to be invoked at each node during a walk through the binary tree.  

DESCRIPTION

The tsearch(), tfind(), tdelete() and twalk() functions are used to operate on binary search trees. Comparisons are done with a user-supplied function whose address is passed as the compar parameter in the tsearch(), tfind(), and tdelete() functions. The compare function is called with two parameters that point to objects that are compared during the tree search. This function returns an integer less than, equal to, or greater than 0 (zero), depending on whether the object pointed to by the first parameter is less than, equal to, or greater than the object pointed to by the second parameter.

The tsearch() function is used to build and search a binary tree. The key parameter is a pointer to an entry that is to be found in the tree or stored in the tree. When an entry in the tree is found that matches key, a pointer to the entry is returned. If a matching entry is not found, the value pointed to by key is inserted into the tree in its proper place, and a pointer to the inserted key is returned. Only pointers are copied, so the calling routine must store the data. The rootp parameter points to a variable that points to the root of a binary tree. A null pointer value for the variable pointed to by rootp denotes an empty tree; in this case, the variable is set to point to the node which will be at the root of the new tree.

As with tsearch(), tfind() searches for an entry in the binary tree, returning a pointer to that entry when a match is found. However, when key is not matched, tfind() returns a null pointer.

The tdelete() function deletes a node from a binary search tree. Parameters for this function are used in the same way as for the tsearch() function. The variable pointed to by the rootp parameter is changed when the deleted node was the root of the binary tree. The tdelete() function returns a pointer to the parent of the deleted node, or a null pointer if the node is not found.

The twalk() function traverses a binary search tree. The root parameter specifies the root of the binary tree to be traversed. Any node in a binary tree can be used as the root node for a walk below that node. The action parameter is the name of a routine to be invoked at each node. This action routine is called with three parameters. The first parameter specifies the address of the visited node. The second parameter specifies a value from an enum data type, which is defined in the search.h header file as follows:


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

The value of the second parameter in the action routine depends on whether this is the first (preorder), second (postorder), or third (endorder) time that the node has been visited during a depth-first, left-to-right traversal of the tree, or whether the node is a leaf. (A leaf is a node that is not the parent of another node). The third parameter in the action routine is the level of the node in the binary tree with the root being level 0 (zero).  

NOTES

Note that the functions tsearch(), tfind(), tdelete(), and twalk() are reentrant, but care should be taken to ensure that the functions supplied as the arguments to compar or action are also reentrant.

The comparison function need not compare every byte; consequently, arbitrary data can be contained in the searched keys in addition to the values undergoing comparison.  

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);
       } }  

RETURN VALUES

If a node is found, both the tsearch() and tfind() functions return a pointer to it. If not, the tfind() function returns a null pointer. The tsearch() function inserts the entry and returns a pointer to the newly inserted entry.

The tsearch() function returns a null pointer when there is not enough space available to create a new node.

The tsearch(), tfind(), and tdelete() functions return a null pointer if rootp is a null pointer on entry.

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

No value is returned by the twalk() function.  

ERRORS

If any of the following conditions occurs, the tsearch(), tfind(), twalk(), or tdelete() function sets errno to the corresponding value: [Digital] Insufficient storage space is available to add an entry to the binary tree.  

RELATED INFORMATION

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

Standards: standards(5) delim off


 

Index

NAME
LIBRARY
SYNOPSIS
STANDARDS
PARAMETERS
DESCRIPTION
NOTES
EXAMPLES
RETURN VALUES
ERRORS
RELATED INFORMATION

This document was created by man2html, using the manual pages.
Time: 02:41:28 GMT, October 02, 2010