OSF

NAME

tsearch, tfind, tdelete, twalk − Manages binary search trees

LIBRARY

Standard  C  Library (libc.a)

SYNOPSIS

#include <search.h>

void ∗tsearch(

const void ∗key,

const 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,

const void ∗∗rootp,

int ((∗compar) (const void ∗, const void ∗)) ;

void twalk( const void ∗∗rootp,

void (∗action)(const void ∗, const enum VISIT, const int)) ;

PARAMETERS

key Points to a key that specifies the entry to be searched in the binary tree. 

rootp Points to a variable that points to the root of the binary tree. 

compar
Specifies the name (that you supply) of a comparison function (strcmp(), for example). This function is called with two parameters that point to the data undergoing comparison in the binary tree. 

action
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 function that you supply (strcmp(), for example). The address of the compare function is passed as the compar parameter in these functions.  The compare function must be called with two parameters that point to entries in the binary tree undergoing comparison. 

The tsearch() function is used to build and access a binary tree during a search. The key parameter is a pointer to an entry that is accessed or stored. When an entry in the binary tree compares with (is equal to) the value pointed to by the key parameter, a pointer to this entry in the binary tree is returned. Otherwise, the value pointed to by the key parameter is inserted into the binary 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.  When a null value is specified for the rootp parameter, an empty tree is specified; in this case, the variable pointed to by the rootp parameter is set to point to the entry, which is located at the root of a new tree. 

As with the tsearch() function, the tfind() function searches for an entry in the binary tree, returning a pointer to that entry in the binary tree when a match with the key parameter occurs. However, when key is not matched, this function 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 is the root of the binary tree.  The tdelete() function returns a pointer to the parent of the deleted node. 

The twalk() function traverses a binary search tree.  The rootp parameter specifies the root of the binary tree to be traversed. Any node in a binary tree may be used as the root node for a traverse at the level below the specified root 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 include 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; the root level of a binary tree is 0 (zero). 

NOTES

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

Pointers to keys and to roots of binary trees should be of type pointer-to-element.  Although declared as type pointer-to-void, the value returned must be cast to type pointer-to-element. 

AES Support Level: Trial use

RETURN VALUES

When the key parameter is matched with an entry in the binary tree, both the tsearch() and tfind() functions return a pointer to the matching entry in the binary tree. When key remains unmatched, the tfind() function returns a null pointer.  The tsearch() function returns a pointer to the inserted entry. 

A null pointer is returned by the tsearch() function when there is not enough space available in the binary tree to create a new node. 

A null pointer is returned by the tsearch(), tfind(), and tdelete() functions when the rootp parameter is set to the null pointer value. 

No value is returned by the twalk() function. 

ERRORS

If the tsearch(), tfind(), twalk(), or tdelete() function fails, errno may be set to the following value:

[ENOMEM] Insufficient storage space is available to add an entry to the binary tree. 

RELATED INFORMATION

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