HP 3000 Manuals HP 3000 Manuals
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.
NOTE The tsearch() function and the header file <search.h> are not part
of ANSI C. Using them makes your program less portable.
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 <stdio.h>
struct node { /* pointers to these are stored in the tree */
char *string;
int length;
};
char string_space[10000]; /* space to store strings */
struct node nodes[500]; /* nodes to store */
struct node *root = NULL; /* this points to the root */
main( )
{
char *strptr = string_space;
struct node *nodeptr = nodes;
void print_node( ), twalk( );
int i = 0, node_compare( );
while (gets(strptr) != NULL && i++ < 500) {
/* set node */
nodeptr->string = strptr;
nodeptr->length = strlen(strptr);
/* put node into the tree */
(void) tsearch((char *)nodeptr, &root,
node_compare);
/* adjust pointers, so we don't overwrite tree */
strptr += nodeptr->length + 1;
nodeptr++;
}
twalk(root, print_node);
}
/* This function compares two nodes, based on an
alphabetical ordering of the string field. */
int
node_compare(node1, node2)
struct node *node1, *node2;
{
return strcmp(node1->string, node2->string);
}
/* This function prints out a node, the first time
twalk encounters it. */
void
print_node(node, order, level)
struct node **node;
VISIT order;
int level;
{
if (order == preorder||order == leaf) {
(void)printf("string = %20s, length = %d\n",
(*node)->string, (*node)->length);
}
}
See Also
tfind(), tdelete(), twalk()