tsearch(3C) DG/UX 5.4.2 tsearch(3C)
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 (void *root, void(*action) (void *, VISIT, int));
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.
tsearch is used to build and access the tree. key is a pointer to a
datum to be accessed or stored. If a datum already in the tree is
equal to *key (as determined by the user-supplied comparison
routine), a pointer to its node is returned. Otherwise a node
containing key is inserted into the tree, and a pointer to the new
node is returned; this returned pointer will point to key, so that
key == *((char **) returned)
Only the pointer key is copied, so the calling routine must store
what key points to. You must provide the root pointer, *rootp.
Licensed material--property of copyright holder(s) 1
tsearch(3C) DG/UX 5.4.2 tsearch(3C)
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 node is
encountered during a traversal of the tree. node is a pointer to the
datum for the node; thus, if the call tsearch(key, rootp, compar)
created the node, then key == *((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 <string.h>
#Include <search.h>
#Include <stdio.h>
struct datum { /*pointers to these are stored */
char *string; */in the tree*/
int length;
};
Licensed material--property of copyright holder(s) 2
tsearch(3C) DG/UX 5.4.2 tsearch(3C)
char stringspace [10000]; /* space to store stings */
struct datum data [500]; /* data to store */
char *root = NULL; /* this points to root */
main()
{
char *strptr = stringspace;
struct datum *datumptr = data;
void printdatum(), twalk();
int i = 0, comparedata();
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, comparedata);
/* adjust pointers so we don't overwrite tree*/
strptr =+ datumptr->length + 1;
datumptr++;
}
twalk(root, printdatum);
}
/*
This routine compares two data, based on an alphabetical
ordering of the string field.
*/
int
comparedata(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
printdatum(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;
}
}
Licensed material--property of copyright holder(s) 3
tsearch(3C) DG/UX 5.4.2 tsearch(3C)
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
key == *((char **) returned)
NOTES
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
refer respectively to visiting 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.
If the calling function alters the pointer to the root, results are
unpredictable.
Licensed material--property of copyright holder(s) 4