tsearch(3) DG/UX 4.30 tsearch(3)
NAME
tsearch, tfind, tdelete, twalk - manage binary search trees
SYNOPSIS
#include <search.h>
char *tsearch (datump, rootp, compar)
char *datump;
char **rootp;
int (*compar)();
char *tfind(datump, rootp, compar)
char *datump;
char **rootp;
int (*compar) ();
char *tdelete(datump, rootp, compar)
char *datump;
char **rootp;
int (*compar)();
void twalk (root, action)
char *root;
void (*action)( );
DESCRIPTION
Tsearch, tfind, tdelete, and twalk are routines for
manipulating binary search trees. They are generalized from
Knuth (6.2.2) Algorithms T and D.
Each node of these trees contains a pointer to a datum
supplied by the user. These routines manipulate trees
without any knowledge of the data these pointers point to.
You will need to supply two routines of your own (described
later in this section) that understand the data: one for
comparing two data, and another for acting on each datum
during a traversal of the tree. Pointers to these routines
are passed as parameters to tsearch, tfind, tdelete, and
twalk.
All but twalk return pointers to nodes; everthing about the
structure of a node is hidden except that its first element
is the pointer to the node's datum, so that
*((char **) node)
can be used as if it were a pointer to the node's datum.
You must provide storage for a pointer, root, that these
routines use to keep track of the root of the tree. It
should be initialized to NULL before any routines are
called.
Licensed material--property of copyright holder(s) Page 1
tsearch(3) DG/UX 4.30 tsearch(3)
Tsearch is used to build and access the tree. Datump is a
pointer to a datum to be accessed or stored. If a datum
already in the tree is equal to *datump (as determined by
the user-supplied comparison routine), a pointer to its node
is returned. Otherwise a node containing datump is inserted
into the tree, and a pointer to the new node is returned;
this returned pointer will point to datump, so that
datump == *((char **) returned)
Only the pointer datump is copied, so the calling routine
must store what datump points to. You must provide the root
pointer, *rootp.
Like tsearch, tfind will search for a datum in the tree,
returning a pointer to its node if found. However if it is
not found, tfind will return a NULL pointer. The arguments
for tfind are the same as for tsearch.
Tdelete searches for a datum in the tree and deletes its
node if found. If the datum was not found, NULL is
returned. If the datum not found, a pointer to the node's
parent is returned. The arguments for tdelete are the same
as for tsearch.
Twalk traverses the tree. Root points to the root of the
tree to be traversed. (Any node in the tree may be used as
the root for a walk beneath that node.) Action is a pointer
to the user-supplied action routine that will be invoked at
each node. This user-supplied comparison routine is as
follows:
compar(datum1p, datum2p)
char *datum1p;
char *datum2p;
The user-supplied comparison routine above returns an
integer that is less than, equal to, or greater than 0,
according to whether the datum pointed to by datum1p should
be considered less than, equal to, or greater than the datum
pointed to by datum2p. The comparison function need not
compare every byte, so arbitrary information may be
contained in each datum in addition to the values being
compared.
The user-supplied action routine is as follows:
void action(node, order, level)
char *node;
VISIT order;
The user-supplied action routine above is called each time a
Licensed material--property of copyright holder(s) Page 2
tsearch(3) DG/UX 4.30 tsearch(3)
node is encountered during a traversal of the tree. Node is
a pointer to the datum for the node; thus, if the call
tsearch(datump, rootp, compar) created the node, then datump
== *((char **) node ).
The enumeration VISIT is defined in <search.h>.
Order is leaf if the node is a leaf; if the node is not a
leaf, order is preorder the first time the node is
encountered, postorder the second, and endorder the third
time. Level is the level of the node in the tree, with the
root being level zero.
EXAMPLES
#Include <search.h>
#Include <stdio.h>
struct datum { /*pointers to these are stored */
char *string; */in the tree*/
int length;
};
char string_space [10000]; /* space to store stings */
struct datum data [500]; /* data to store */
char *root = NULL; /* this points to root */
main()
{
char *strptr = string_space;
struct datum *datumptr = data;
void print_datum(), twalk();
int i = 0, compare_data();
char *tsearch();
while (gets(strptr) != NULL && i++ < 500) {
/* set datum */
datumptr ->string = strptr;
datumptr ->length = strlen(strptr);
/* put datum into the tree */
tsearch((char *) datumptr, &root, compare_data);
/* adjust pointers so we don't overwrite tree*/
strptr =+ datumptr->length + 1;
datumptr++;
}
twalk(root, print_datum);
}
/*
This routine compares two data, based on an alphabetical
ordering of the string field.
*/
int
compare_data(datum1, datum2)
Licensed material--property of copyright holder(s) Page 3
tsearch(3) DG/UX 4.30 tsearch(3)
char *datum1, *datum2;
{
return(strcmp(((struct datum *) datum1)->string,
(((struct datum *) datum2)->string;
}
/*
This routine prints out a datum the first time
twalk encounters it.
*/
void
print_datum(datum, order, level)
char *datum;
VISIT order;
int level;
{
if (order == preorder || order == leaf) {
printf ("string = %20s, length = %d0
((struct datum *) *((char **) datum))->string,
((struct datum *) *((char **) datum))->length;
}
}
SEE ALSO
bsearch(3C), hsearch(3C), lsearch(3C).
DIAGNOSTICS
A NULL pointer is returned by tsearch if there is not enough
space available to create a new node.
A NULL pointer is returned by tsearch, tfind, and tdelete if
rootp (which should be &root) is NULL.
If the datum is found both tsearch and tfind return a
pointer to its node. If not, tfind returns NULL, and
tsearch returns a pointer to the inserted datum's node, such
that
datump == *((char **) returned)
WARNINGS
The root argument to twalk is one level of indirection less
than the rootp arguments to tsearch and tdelete.
There are two nomenclatures that refer to the order in which
tree nodes are visited. Tsearch uses preorder, postorder
and endorder to respectively refer to visting a node before
any of its children, after its left child and before its
right, and after both its children. The alternate
nomenclature uses preorder, inorder, and postorder to refer
to the same visits. This could result in some confusion over
the meaning of postorder.
There are two cases in which tsearch and tfind return a NULL
Licensed material--property of copyright holder(s) Page 4
tsearch(3) DG/UX 4.30 tsearch(3)
pointer. The first case is relatively normal: tsearch
cannot allocate more space, or tfind did not find the datum.
The second case, that rootp is NULL, is not normal and
should never occur unless tsearch and tfind have been called
incorrectly.
Tsearch, tfind, and tdelete return pointers to nodes, not
pointers to data; the caller must dereference and cast the
node pointer to get a datum pointer.
CAVEAT
If the calling function alters the pointer to the root,
results are unpredictable.
Licensed material--property of copyright holder(s) Page 5