hsearch()

Search the hash search table

Synopsis:

#include <search.h>

ENTRY* hsearch ( ENTRY item, 
                 ACTION action );

Library:

libc

Description:

The hsearch() function is a hash-table search routine generalized from Knuth (6.4) Algorithm D. It uses the hash search table created by hcreate().

The hsearch() function 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().

The item argument is a structure of type ENTRY, defined in <search.h>, that contains:

key

A pointer to the comparison key.

data

A pointer to any other data to be associated with the key.

The action argument is a member of an enumeration type ACTION, also defined in <search.h>, indicating the disposition of the entry if it can't be found in the table:

ENTER

The item should be inserted in the table at an appropriate point. If the item is a duplicate of an existing item, the new item isn't entered and hsearch() returns a pointer to the existing one.

FIND

No entry should be made. If the item can't be found, hsearch() returns NULL.

The hsearch() and hcreate() functions use malloc() to allocate space.

Only one hash search table may be active at any given time. The table can be destroyed by calling hdestroy().

Returns:

A pointer to the item found, or NULL if either the action is FIND and the item wasn't found or the action is ENTER and the table is full.

Examples:

The following example reads in strings followed by two numbers and stores them in a hash table, discarding duplicates. It then reads in strings, finds the matching entry in the hash table and prints it.

#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 */
     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;
}

Classification:

Standard Unix

See also:

bsearch(), hcreate(), hdestroy(), malloc(), strcmp()

The Art of Computer Programming, Volume 3, Sorting and Searching by Donald E. Knuth, published by Addison-Wesley Publishing Company, 1973.