tsearch(3)
_________________________________________________________________
tsearch, tfind, tdelete, twalk Subroutine
manage binary search trees
_________________________________________________________________
SYNTAX
#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)
DG/UX 4.00 Page 1
Licensed material--property of copyright holder(s)
tsearch(3)
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.
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)
DG/UX 4.00 Page 2
Licensed material--property of copyright holder(s)
tsearch(3)
char *node;
VISIT order;
The user-supplied action routine above is called each time a 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);
DG/UX 4.00 Page 3
Licensed material--property of copyright holder(s)
tsearch(3)
}
/*
This routine compares two data, based on an alphabetical
ordering of the string field.
*/
int
compare_data(datum1, datum2)
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
DG/UX 4.00 Page 4
Licensed material--property of copyright holder(s)
tsearch(3)
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
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.
DG/UX 4.00 Page 5
Licensed material--property of copyright holder(s)