tsearch, tfind, tdelete, twalk - Manage binary search
trees
#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) );
Standard C Library (libc)
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.
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 usersupplied
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.
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).
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.
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.
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.
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);
} }
Functions: bsearch(3), hsearch(3), lsearch(3), qsort(3)
Standards: standards(5)
tsearch(3)
[ Back ] |
