hsearch(3) CLIX hsearch(3)
NAME
hsearch, hcreate, hdestroy - Manages hash search tables
LIBRARY
The Standard C Library (libc.a)
SYNOPSIS
#include <stdio.h>
#include <search.h>
ENTRY *hsearch(
ENTRY item ,
ACTION action );
int hcreate(
unsigned nel );
void hdestroy(
void );
PARAMETERS
item Points to the comparison key and any other data to be associated
with that data
action Indicates what action to take if the entry is not found in the
hash table. A value of ENTER indicates that the entry should be
inserted. A value of FIND indicates that no entry should be
made.
nel Specifies an estimate of the maximum number of entries that the
table will have.
DESCRIPTION
The hsearch() function is a hash-table search function 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 item
parameter is a structure of type ENTRY (defined in the <search.h> header
file) containing two pointers: the item.key points to the comparison key;
the item.data points to data to be associated with that key. (Pointers to
types other than character should be cast to pointer-to-character.) The
action parameter is a member of an enumeration type indicating the
disposition of the entry if it cannot be found in the table. A value of
ENTRY indicates that the item should be inserted in the table at an
appropriate point. A value of FIND indicates that no entry should be
made. Unsuccessful resolution is indicated by the return of a NULL
2/94 - Intergraph Corporation 1
hsearch(3) CLIX hsearch(3)
pointer.
The hcreate() function allocates sufficient space for the table, and must
be called before hsearch() is used. The 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.
The hdestroy() function destroys the search table and may be followed by
another call to hcreate(). Only one hash search table may be active at
any given time.
EXAMPLES
To read in strings followed by two numbers and stores them in a hash
table, discarding duplicates, reading in strings and finding the matching
entry in the hash table and displaying it:
#include <stdio.h>
#include <search.h>
struct info { /* this is the info stored in the 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, *hsearch();
/* 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 = (char *)info_ptr;
str_ptr += strlen(str_ptr) + 1;
info_ptr++;
/* put item into table */
2 Intergraph Corporation - 2/94
hsearch(3) CLIX hsearch(3)
(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)
}
}
}
NOTES
The hsearch() function 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.
USCR Use a user-supplied comparison function for ascertaining table
membership. The function should be named hcompar and should
behave in a manner similar to strcmp() [see string()].
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.
Also, there are preprocessor flags for obtaining debugging printout -
DDEBUG and for including a test driver in the calling function -DDRIVER.
Consult the source code for further details.
CAUTIONS
2/94 - Intergraph Corporation 3
hsearch(3) CLIX hsearch(3)
The functions hsearch() and hcreate() use malloc() to allocate space.
RETURN VALUES
The hsearch() function 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, else a pointer to the entry is returned. The hcreate() function
returns zero if it cannot allocate sufficient space for the table, else it
returns a 1. hdestroy does not return a value.
ERRORS
Out of core
Failed to allocate necessary memory.
RELATED INFORMATION
Functions: bsearch(3), lsearch(3), malloc(3), tsearch(3)
4 Intergraph Corporation - 2/94