HP C/iX Library Reference Manual (30026-90004)

372 Chapter5
HP C/iX Library Function Descriptions
tsearch
tsearch
Builds and provides access to a binary search tree.
Syntax
#include <search.h>
void *tsearch (void * key , void ** rootp ,
int (* compar )());
Parameters
key A pointer to an item to be accessed or stored.
rootp A pointer to a variable that points to the root of the tree.
compar A pointer to a comparison function supplied by the programmer.
Return Values
x A pointer to the value pointed to by key .
NULL There is not enough space available to create a new node or
rootp is NULL.
Description
The tsearch function builds and accesses a binary search tree. The tsearch, tfind,
tdelete, and twalk functions manage binary search trees generalized from Knuth
Algorithms T and D (6.2.2) described in The Art of Computer Programming, Vol3 (Sorting
and Searching) by Donald Ervin Knuth (Reading, Mass.:Addison-Wesley, 1973).
The pointers to the key and the root of the tree should be of type pointer-to-element, and
cast to type pointer-to-character. Similarly, although declared as type pointer-to-character,
the value returned should be cast into type pointer-to-element.
If the calling function alters the pointer to the root, results are unpredictable.
If there is an item in the tree equal to *
key (the value pointed to by key ), a pointer to the
item found is returned. Otherwise, *
key is inserted, and a pointer to it is returned. Only
pointers are copied, so the calling function must store the data.
A null value for the variable pointed to by
rootp indicates an empty tree; in this case, the
variable is set to point to the item that is at the root of the new tree.
All comparisons are done with the function
compar , which must be supplied by you. The
function is called with two arguments, the pointers to the elements being compared.
It returns an integer less than, equal to, or greater than zero, according to whether the
first argument is to be considered less than, equal to, or greater than the second argument.
The comparison function does not need to compare every byte, so arbitrary data can be
contained in the elements in addition to the values being compared.