*** UNIX MANUAL PAGE BROWSER ***

tsearch(3) Library Functions Manual tsearch(3) 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 stan- dards as follows: tsearch(), tfind(), tdelete(), twalk(): XPG4, XPG4-UNIX Refer to the standards(5) reference page for more information about in- dustry 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 op- erate on binary search trees. Comparisons are done with a user-sup- plied 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 dur- ing 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 bi- nary 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. Para- meters 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 parame- ter 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 para- meter 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 (en- dorder) 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 sup- plied as the arguments to compar or action are also reentrant. The comparison function need not compare every byte; consequently, ar- bitrary 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 alphabeti- cal 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_com- pare(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 tsearch(3)