HASH

Section: C Library Functions (3)
Updated: 7 November 1991
Index Return to Main Contents
 

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.


 

Index

NAME
SYNOPSIS
DESCRIPTION
DIAGNOSTICS
EXAMPLE
SEE ALSO
HISTORY

This document was created by man2html, using the manual pages.
Time: 16:42:33 GMT, November 10, 2022