[net.unix-wizards] Help with tsearch

hxd9622@ritcv.UUCP (07/18/86)

[]

   I need help with some subroutines in sysV ie tsearch(3C) and tdelete(3C).

   Does anyone know how to use these routines? 
   How do you pass the parameters?

   I have declared the following struct...

   struct rec 
	{
	char *string;
	struct rec *left, *right;
	}

   tsearch is declared as...

   char *tsearch ((char *) key, (char **)rootp, compar)
   int (*compar)();

   I'm in a loop that reads a line of text and calls tsearch to insert
   line in the tree...

   while (fgets(line, MAXLINE, file))
	
	ptr = (struct rec *)tsearch((char *)line, (char *)root, strcompar);

   Note:
	ptr should point to the node containing line in the binary tree.
	root will point to new node if NULL.
	strcompar SCfunction to compar 2 strings.
	(char *)root == (char **)&root (isn't it?)

   I don't understand the first argument to tsearch..

        (char *)key - what is key?
		      is it the field contents - a string?
		      or is it a ptr to new node with new string in it?

   I wrote my own routines for these but I need these routines for something
   bigger.  When I used my own routines, everything worked fine.
   Can anyone help?  Thanks a million!

   PS
	just in case Pnews doesn't ask for
	my .signature...

-+-+-+-

Herman Darmawan @ Rochester Institute of Technology
UUCP     {allegra,seismo}!rochester!ritcv!hxd9622
BITNET   HND9622@RITVAXC

... fight mail hunger ... mail me now!
#

moss@BRL.ARPA (Gary S. Moss (SLCBR-VLD-V)) (07/21/86)

Herman,
	I wrote my own tsearch(3C) before we got our system V sources, so I
have an opinion of how it is supposed to work, even though I never tried it.
You should not need to define a record type as this is supposed to be trans-
parent to the application.  That is why all pointers are cast to "char *" or
"char **" when passed in to the library.  Your use of key appears correct,
assuming that your strcompar function knows how to order strings and returns
the appropriate values.  Your use of rootp does not seem correct; its hard
to tell since you didn't declare it.  Rootp should be declared as a variable
(some kind of pointer), initialized to NULL, and its address should be passed
in.  Here is an example.

#include <stdio.h>
extern char	*malloc(), *tsearch();
char	*rootp = NULL;
char	line[MAXLINE];
char	*ptr, *datum;
int	strcompar();

	while( fgets( line, MAXLINE, file ) )
		{
		datum = malloc( strlen( line ) + 1 );
		if( datum == NULL )
			{
			(void) fprintf( stderr, "Malloc() no more core.\n" );
			return	1;
			}
		(void) strcpy( datum, line );
		ptr = tsearch( datum, &rootp, strcompar );
		}
The first time through the loop, rootp is NULL indicating to tsearch() that
the tree is empty, and a NULL pointer will be returned indicating the same,
while rootp's contents will be altered to contain the address of the datum
(line) at the new root of the tree.  On subsequent loops, the address of
the datum (line) will be returned by tsearch.  I assume that the datum is
not copied into the tree structure, so you must allocate space for it and
pass its address in, a simple test should confirm this.  If you wish, you
can store more complex data types:

struct rec
	{
	int	key;
	double	xyz[3];
	}
node, *datum, *rootp = NULL, *ptr;

int	compar( datum1, datum2 )
char	*datum1, *datum2;
	{
	return	(struct rec *) datum1->key - (struct rec *) datum2->key;
	}

...
	while( fread( (char *) node, sizeof(struct rec), 1, stdin ) == 1 )
		{
		datum = (struct rec *) malloc( sizeof(struct rec) );
		if( datum == NULL )
			{
			(void) fprintf( stderr, "Malloc() no more core.\n" );
			return	1;
			}
		*datum = node;
		ptr = (struct rec *)
			tsearch( (char *) datum, (char **)&rootp, compar );
		}
...

Be careful when using twalk(), that you pass rootp, NOT ITS ADDRESS.

Good luck,
-moss