hsearch(3C)							   hsearch(3C)

NAME    [Toc]    [Back]

     hsearch, hcreate, hdestroy	- manage hash search tables

SYNOPSIS    [Toc]    [Back]

     #include <search.h>

     ENTRY *hsearch (ENTRY item, ACTION	action);

     int hcreate (size_t nel);

     void hdestroy (void);

DESCRIPTION    [Toc]    [Back]

     hsearch is	a hash-table search routine generalized	from Knuth (6.4)
     Algorithm D.  It returns a	pointer	into a hash table indicating the
     location at which an entry	can be found.  The comparison function used by
     hsearch is	strcmp [see string(3C)].  item is a structure of type ENTRY
     (defined in the search.h header file) containing two pointers:  item.key
     points to the comparison key, and item.data points	to any other data to
     be	associated with	that key.  (Pointers to	types other than void should
     be	cast to	pointer-to-void.)  action is a member of an enumeration	type
     ACTION (defined in	search.h) indicating the disposition of	the entry if
     it	cannot be found	in the table.  ENTER indicates that the	item should be
     inserted in the table at an appropriate point.  Given a duplicate of an
     existing item, the	new item is not	entered	and hsearch returns a pointer
     to	the existing item.  FIND indicates that	no entry should	be made.
     Unsuccessful resolution is	indicated by the return	of a null pointer.

     hcreate allocates sufficient space	for the	table, and must	be called
     before hsearch is used.  nel is an	estimate of the	maximum	number of
     entries that the table will contain.  This	number may be adjusted upward
     by	the algorithm in order to obtain certain mathematically	favorable
     circumstances.

     hdestroy destroys the search table, and may be followed by	another	call
     to	hcreate.

BUGS    [Toc]    [Back]

     Hsearch is	compiled by Silicon Graphics with none of the flags named in
     NOTES defined.

NOTES    [Toc]    [Back]

     hsearch uses open addressing with a multiplicative	hash function.
     However, its source code has many other options available which the user
     may select	by compiling the hsearch source	with the following symbols
     defined to	the preprocessor:

	  DIV	   Use the remainder modulo table size as the hash function
		   instead of the multiplicative algorithm.






									Page 1






hsearch(3C)							   hsearch(3C)



	  USCR	   Use a User Supplied Comparison Routine for ascertaining
		   table membership.  The routine should be named hcompar and
		   should behave in a manner similar to	strcmp [see
		   string(3C)].

	  CHAINED  Use a linked	list to	resolve	collisions.  If	this option is
		   selected, the following other options become	available.

		   START     Place new entries at the beginning	of the linked
			     list (default is at the end).

		   SORTUP    Keep the linked list sorted by key	in ascending
			     order.

		   SORTDOWN  Keep the linked list sorted by key	in descending
			     order.

     The source	code should be consulted for further details.

EXAMPLE    [Toc]    [Back]

     The following example will	read in	strings	followed by two	numbers	and
     store them	in a hash table, discarding duplicates.	 It will then read in
     strings and find the matching entry in the	hash table and print it	out.

	  #include <stdio.h>
	  #include <search.h>
	  #include <string.h>
	  #include <stdlib.h>

	  struct info {	      /* this is the info stored in table */
	       int age,	room; /* other than the	key */
	  };

	  #define NUM_EMPL    5000    /* # of elements in search table */

	  main(	)
	  {
	       /* space	to store strings */

















									Page 2






hsearch(3C)							   hsearch(3C)



	      char string_space[NUM_EMPL*20];
	       /* space	to store employee info */
	       struct info info_space[NUM_EMPL];
	       /* next avail space in string_space */
	       char *str_ptr = string_space;
	       /* next avail space in info_space */
	       struct info *info_ptr = info_space;
	       ENTRY item, *found_item;
	       /* name to look for in table */
	       char name_to_find[30];
	       int i = 0;

	       /* create table */
	       (void) hcreate(NUM_EMPL);
	       while (scanf("%s%d%d", str_ptr, &info_ptr->age,
		      &info_ptr->room) != EOF && i++ < NUM_EMPL) {
		    /* put info	in structure, and structure in item */
		    item.key = str_ptr;
		    item.data =	(void *)info_ptr;
		    str_ptr += strlen(str_ptr) + 1;
		    info_ptr++;
		    /* put item	into table */
		    (void) hsearch(item, ENTER);
	       }

	       /* access table */
	       item.key	= name_to_find;
	       while (scanf("%s", item.key) != EOF) {
		   if ((found_item = hsearch(item, FIND)) != NULL) {
		    /* if item is in the table */
		    (void)printf("found	%s, age	= %d, room = %d\n",
			 found_item->key,
			 ((struct info *)found_item->data)->age,
			 ((struct info *)found_item->data)->room);
		   } else {
		    (void)printf("no such employee %s\n",
			 name_to_find);
		   }
	       }
	       return 0;
	  }














									Page 3






hsearch(3C)							   hsearch(3C)

SEE ALSO    [Toc]    [Back]

     bsearch(3C), lsearch(3C), malloc(3C), malloc(3X), string(3C),
     tsearch(3C).

DIAGNOSTICS    [Toc]    [Back]

     hsearch returns a null pointer if either the action is FIND and the item
     could not be found	or the action is ENTER and the table is	full.

     hcreate returns zero if it	cannot allocate	sufficient space for the
     table.

NOTES    [Toc]    [Back]

     hsearch and hcreate use malloc(3C)	to allocate space.

     Only one hash search table	may be active at any given time.


									PPPPaaaaggggeeee 4444