HASH(3)

NAME
hash - procedures for managing hash tables in libmagicutils.a

SYNOPSIS
#include hash.h

HashInit(table, initsize, keysize)
HashTable *table;
int initsize, keysize;

HashInitClient(table, initsize, keysize, compareFn, copyFn, hashFn, killFn)
HashTable *table;
int initsize, keysize;
int (*compareFn)(key1, key2);
char *(*copyFn)(key);
int (*hashFn)(key);
Void (*killFn)(key);

int HashSize(keybytes)
int keybytes;

HashKill(table)
HashTable *table;

HashEntry *HashLookOnly(table, key)
HashTable *table;
ClientData key;

HashEntry *HashFind(table, key)
HashTable *table;
ClientData key;

ClientData HashGetValue(he)
HashEntry *he;

HashSetValue(he, value)
HashEntry *he;
ClientData value;

HashStartSearch(hs)
HashSearch *hs;

HashEntry *HashNext(table, hs)
HashTable *table;
HashSearch *hs;

DESCRIPTION
This module provides procedures for creating, accessing, and destroying hash tables. These tables grow automatically as more elements are added to them to avoid overloading. They may be indexed by strings, single words, or multi-word structures. Single-word can be interpreted (e.g., compared or hashed) by user-supplied procedures. Each entry stores a single word value, which may be set or read by the macros HashSetValue or HashGetValue but should not be manipulated directly.

HashInit is used to allocate space for the initially empty hash table table. Enough space is allocated for initsize buckets (which should be a power of two), although subsequent additions to the hash table can cause the number of buckets to increase. Tables can be organized in one of three different ways, depending on the value of keysize.

If keysize is HT_STRINGKEYS, then keys passed to HashFind (or HashLookOnly) are treated as the addresses of NULL-terminated strings. The HashEntry structures for this type of key are variable-sized; sufficient space is allocated at the end of each structure to hold the key string and its trailing NULL byte. If keysize is HT_WORDKEYS, then keys are single words of data passed directly to HashFind, and are compared using strcmp(1). If keysize is HT_STRUCTKEYS or greater, keys are multiple words of data, but their address is passed to HashFind (instead of the actual value as when keysize was HT_WORDKEYS). The value of keysize in this case should be the number of words in a key. The macro HashSize should be used to produce this number; HashSize(sizeof (struct foo)) gives the number of words needed if keys are to be of type (struct foo). In general, single-word keys (keysize equal to HT_WORDKEYS) are the fastest, but the most restrictive.

A second procedure, HashInitClient, may be used to initialize a hash table instead of HashInit. This second procedure is a more general one, in that it allows a fourth value of keysize to be provided, HT_CLIENTKEYS, along with four client procedures. The keys in such a case are single-word values, passed to HashFind just like keys when keysize is HT_WORDKEYS. However, they are interpreted using the client procedures passed in the call to HashInitClient. These procedures perform four functions; if any are NULL, then those functions are performed exactly as in the case of HT_WORDKEYS. The first, (*compareFn)(key1, key2), takes two single-word key values and returns either 0 if they are equal, or 1 if they are not. The next procedure, (*copyFn)(key), is called when a new entry is being created for a key; it performs whatever processing is needed to ensure that the key can be kept around permanently (e.g., making a copy of it), and returns the value that will actually be stored as the key in the hash table (e.g., the copy). The third procedure, (*hashFn)(key), is used to produce a single 32-bit value from key. It is primarily useful when key is in fact a pointer to a structure, and the contents of the structure, rather than its address, determine the hash value. Finally, (*killFn)(key) is called when the hash table is being freed by HashKill to perform any final cleanup of a key, such as freeing a key that had been copied by (*copyFn)() when it was installed in the hash table.

HashKill can be used to free all the storage associated with table.

Both HashLookOnly and HashFind are used for retrieving the entry from table that matchs key. They differ in their behavior when key is not in the table. HashLookOnly will return NULL if the key is not found, while HashFind will create a new HashEntry whose value (as returned by HashGetValue) is zero.

It is possible to scan sequentially through a hash table to visit all its entries. HashStartSearch initializes the HashSearch structure hs, which is then passed to HashNext, which keeps returning subsequent entries in the table until all have been returned, when it returns NULL.

BUGS
If it is possible for initialized entries in the hash table to have NULL values, then HashLookOnly must be called before HashFind if you are to be certain that an entry was not already in the table, since there is no distinction between a NULL value that was already in the table and a NULL value that signifies that the entry was newly created by HashFind.

SEE ALSO
magicutils(3)