 |
Index for
Section 3 |
|
 |
Alphabetical
listing for T |
|
 |
Bottom of
page |
|
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 standards
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
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 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.
root
Points to the root of the binary tree to be walked.
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 user-supplied 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 during 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. 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 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 parameter
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 parameter 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 supplied
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:
[ENOMEM]
[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_compare(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)
|
Index for
Section 3 |
|
|
Alphabetical
listing for T |
|
 |
Top of
page |
|