hsearch()

Search the hash search table

Synopsis:

#include <search.h>

ENTRY* hsearch ( ENTRY item, 
                 ACTION action );

Arguments:

item

A structure of type ENTRY, defined in <search.h>, that contains:

• char *key — a pointer to the comparison key.
• void *data — a pointer to any other data to be associated with the key.

action

A member of an enumeration type ACTION, also defined in <search.h>, indicating what to do with the entry if it isn't in the table:

• ENTER — insert the entry in the table at the appropriate point. If the item is a duplicate of an existing item, the new item isn't added, and hsearch() returns a pointer to the existing one.
• FIND — don't add the entry. If the item can't be found, hsearch() returns NULL.

Library:

libc

Use the -l c option to qcc to link against this library. This library is usually included automatically.

Description:

The hsearch() function is a hash-table search routine generalized from Knuth (6.4) Algorithm D. Before using this function, you must call hcreate() to create the hash table.

The hsearch() function returns a pointer into a hash table indicating the location at which an entry can be found. This function uses strcmp() as the comparison function.

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

Only one hash search table may be active at any given time. You can destroy the table 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);
         }
     }
     hdestroy();
     return 0;
}

Classification:

POSIX 1003.1 XSI

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.