HASH(3)

NAME
hash: hashcreate, hashdestroy, hashstore, hashentry, hashfetch, hashdelete, hashwalk - string interface to general-purpose in-memory hashed lookup
hash: hdbmcreate, hdbmdestroy, hdbmstore, hdbmentry, hdbmfetch, hdbmdelete, hdbmwalk - dbm interface to general-purpose in-memory hashed lookup

SYNOPSIS
#include <hdbm.h>
#include <hash.h>

HASHTABLE *hashcreate(size, hashfunc)
unsigned size;
unsigned (*hashfunc)();

hashdestroy(tbl)
HASHTABLE *tbl;

int hashstore(tbl, key, data)
HASHTABLE *tbl;
HASHDATUM key, data;

HASHDATUM hashentry(tbl, key, allocator)
HASHTABLE *tbl;
HASHDATUM key;
HASHDATUM (*allocator)();

HASHDATUM hashfetch(tbl, key)
HASHTABLE *tbl;
HASHDATUM key;

int hashdelete(tbl, key)
HASHTABLE *tbl;
HASHDATUM key;

hashwalk(tbl, nodefunc, hook)
HASHTABLE *tbl;
int (*nodefunc)();
char *hook;

DESCRIPTION
This package maintains, searches, and enumerates multiple hash tables in memory simultaneously. (Hashing is a technique to map a `key' to the data corresponding to that key very quickly by use of a hash function.) This package implements hashing with chaining.

Hash.h defines some data types: HASHDATUM is the type of keys and data objects manipulated by these routines; (HASHTABLE *) is a magic cookie returned by hashcreate and used by the other routines:

typedef char *HASHDATUM;

Hashcreate allocates a fresh hash table of size entries and set up to use the hashing function hashfunc. It returns a magic cookie which refers to the new hash table, for use with the other routines. The precise value of size doesn't matter; it only affects efficiency: larger values consume more memory but generally result in faster lookups. Some theoreticians believe that prime numbers make better sizes, but it's not clear that it really matters in practice. If hashfunc is a null pointer, a default hash function will be used. Otherwise, hashfunc(key) will be called for each HASHDATUM key that must be hashed; the result will be taken modulus the hash table size to determine the hash chain to search for the corresponding data. Hashdestroy destroys utterly the hash table corresponding to tbl.

Hashstore associates the data pointer with key in the table corresponding to tbl. Any prior association with key in this table is lost. Hashstore assumes that data pointed to by a key HASHDATUM remains constant, and that data pointed to by a data HASHDATUM does not move in memory and is not freed, during the life of the table. Hashentry returns the data associated with key in the table corresponding to tbl, if any, else invokes allocator(key) and associates the result with key, and returns the result. Hashentry is primarily an optimisation for symbol table maintenance. Hashfetch returns the data associated with key in the table corresponding to tbl, if any, else 0. Hashdelete removes any entry for key.

Hashwalk visits each entry in the table corresponding to tbl in no particularly useful order and executes nodefunc(key, data, hook); for each, where key and data are the values of the mapping for that entry. Hook is a crude attempt to allow side effects in nodefunc with reentrancy.

There exists a parallel set of routines with whose names are the same except that the prefix hash is replaced with hdbm. These routines operate on the data type HDBMDATUM rather than HASHDATUM; HDBMDATUM is a (pointer, size) pair defined by hdbm.h and contains these members:

	char	*dat_ptr;
	unsigned dat_len;

An implementation of hsearch(3) is also provided; see hsearch(3) for details.

DIAGNOSTICS
Functions which return a value return 0 on failure, except for hdbmfetch and hdbmentry, which return an HDBMDATUM whose dat_ptr is set to 0.

EXAMPLE
static char Unix[] = "UNIX", plan9[] = "Plan 9";
HASHTABLE *tbl = hashcreate(100, (unsigned (*)())NULL);
if (tbl == 0)
	error("can't hash", "");
if (!hashstore(tbl, Unix, "is a registered trademark of AT&T, etc."))
	error("can't install %s", Unix);
if (!hashstore(tbl, plan9, "is probably a trademark of MCA"))
	error("can't install %s", plan9);
printf("%s %s\n", Unix, hashfetch(tbl, Unix));
printf("%s %s\n", plan9, hashfetch(tbl, plan9));
hashdestroy(tbl);

SEE ALSO
hsearch(3), tsearch(3)
The Art of Computer Programming, Donald E. Knuth

HISTORY
Written by Geoff Collyer of Software Tool & Die because hsearch(3) is inadequate for serious hashing.