HSEARCH
NAME
hcreate, hdestroy, hsearch - hash table management
SYNOPSIS
#include <search.h>
I int hcreate(size_t nel );
I ENTRY *hsearch(ENTRY item , ACTION action );
void hdestroy(void);
#define _GNU_SOURCE
#include <search.h>
I int hcreate_r(size_t nel , struct hsearch_data * tab );
I int hsearch_r(ENTRY item , ACTION action , ENTRY ** ret ,
I struct hsearch_data * tab );
I void hdestroy_r(struct hsearch_data * tab );
DESCRIPTION
The three functions
R hcreate (),
R hsearch (),
and
R hdestroy ()
allow the user to create a hash table (only one at a time)
which associates a key with any data.
First the table must be created with the function
R hcreate ().
The argument nel is an estimate of the maximum number of entries
in the table.
The function
R hcreate ()
may adjust this value upward to improve the
performance of the resulting hash table.
The corresponding function
R hdestroy ()
frees the memory occupied by
the hash table so that a new table can be constructed.
The argument
item is of type
ENTRY, which is a typedef defined in
<search.h> and includes these elements:
typedef struct entry {
char *key;
void *data;
} ENTRY;
The field
key points to the null-terminated string which is the
search key.
The field
data points to the data associated with that key.
The function
R hsearch ()
searches the hash table for an
item with the same key as
item (where "the same" is determined using
strcmp(3)),
and if successful returns a pointer to it.
The argument
action determines what
R hsearch ()
does
after an unsuccessful search.
A value of
ENTER instructs it to
insert a copy of
item, while a value of
FIND means to return
NULL.
The three functions
R hcreate_r (),
R hsearch_r (),
R hdestroy_r ()
are reentrant versions that allow the use of more than one table.
The last argument used identifies the table.
The struct it points to
must be zeroed before the first call to
R hcreate_r ().
RETURN VALUE
R hcreate ()
and
R hcreate_r ()
return 0 when allocation of the memory
for the hash table fails, non-zero otherwise.
R hsearch ()
returns NULL if action is ENTER and
the hash table is full, or action is FIND and item
cannot be found in the hash table.
R hsearch_r ()
returns 0 if action is ENTER and
the hash table is full, and non-zero otherwise.
ERRORS
POSIX documents
The glibc implementation will return the following two errors.
ENOMEM
Table full with action set to ENTER.
ESRCH
The action parameter is FIND and no corresponding element
is found in the table.
CONFORMING TO
The functions
R hcreate (),
R hsearch (),
and
R hdestroy ()
are from SVr4, and are described in POSIX.1-2001.
The functions
R hcreate_r (),
R hsearch_r (),
R hdestroy_r ()
are GNU extensions.
BUGS
SVr4 and POSIX.1-2001 specify that action
is significant only for unsuccessful searches, so that an ENTER
should not do anything for a successful search.
The libc and glibc
implementations update the data for the given key
in this case.
Individual hash table entries can be added, but not deleted.
EXAMPLE
The following program inserts 24 items in to a hash table, then prints
some of them.
#include <stdio.h>
#include <stdlib.h>
#include <search.h>
char *data[] = { "alpha", "bravo", "charlie", "delta",
"echo", "foxtrot", "golf", "hotel", "india", "juliet",
"kilo", "lima", "mike", "november", "oscar", "papa",
"quebec", "romeo", "sierra", "tango", "uniform",
"victor", "whisky", "x-ray", "yankee", "zulu"
};
int
main(void)
{
ENTRY e, *ep;
int i;
/* starting with small table, and letting it grow does not work */
hcreate(30);
for (i = 0; i < 24; i++) {
e.key = data[i];
/* data is just an integer, instead of a
pointer to something */
e.data = (void *) i;
ep = hsearch(e, ENTER);
/* there should be no failures */
if (ep == NULL) {
fprintf(stderr, "entry failed\n");
exit(EXIT_FAILURE);
}
}
for (i = 22; i < 26; i++) {
/* print two entries from the table, and
show that two are not in the table */
e.key = data[i];
ep = hsearch(e, FIND);
printf("%9.9s -> %9.9s:%d\n", e.key,
ep ? ep->key : "NULL", ep ? (int)(ep->data) : 0);
}
exit(EXIT_SUCCESS);
}
SEE ALSO
ČLÁNKY DO MAILU