tsearch(3)tsearch(3)NAME
tsearch, tfind, tdelete, twalk - Manage binary search trees
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) );
LIBRARY
Standard C Library (libc)
STANDARDS
Interfaces documented on this reference page conform to industry stan‐
dards as follows:
tsearch(), tfind(), tdelete(), twalk(): XSH4.2
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-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
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. Param‐
eters 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 parame‐
ter 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 sup‐
plied 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.
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:
[Tru64 UNIX] Insufficient storage space is available to add an entry
to the binary tree.
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_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);
} }
SEE ALSO
Functions: bsearch(3), hsearch(3), lsearch(3), qsort(3)
Standards: standards(5)tsearch(3)
