ALL_HASH(3) LAM INTERNALS ALL_HASH(3)NAME
all_hash, all_shash - general purpose hash table management (LAM)
SYNOPSIS
#include <all_hash.h>
HASH *ah_init (int size, int elemsize, int nullkey, int mode);
int ah_delete (HASH *ahd, int key);
int ah_delete_elm (HASH *ahd, void *cmpelm);
int ah_expand (HASH *ahd, int newsize);
int ah_insert (HASH *ahd, void *elem);
int ah_kick (HASH *ahd, void *elem);
int ah_count (HASH *ahd);
int ah_size (HASH *ahd);
void *ah_find (HASH *ahd, int key);
void *ah_find_elm (HASH *ahd, void *cmpelm);
void *ah_top (HASH *ahd);
void *ah_next (HASH *ahd, void *elem);
void ah_free (HASH *ahd);
void ah_setcmp (HASH *ahd, int (*cmp)(void *e1, void *e2));
SHASH *ahs_init (int size, int elemsize, int nullkey, int mode,
void *htable, int *lru, SHASH *ahsd);
int ahs_delete (SHASH *ahsd, int key);
int ahs_delete_elm (SHASH *ahsd, void *cmpelm);
int ahs_insert (SHASH *ahsd, void *elem);
int ahs_kick (SHASH *ahsd, void *elem);
int ahs_count (SHASH *ahsd);
int ahs_size (SHASH *ahsd);
void *ahs_find (SHASH *ahsd, int key);
void *ahs_find_elm (SHASH *ahsd, void *cmpelm);
void *ahs_top (SHASH *ahsd);
void *ahs_next (SHASH *ahsd, void *elem);
void ahs_setcmp (HASH *ahsd, int (*cmp)(void *e1, void *e2));
DESCRIPTION
The all_hash and all_shash packages provide general purpose hash table
management. They differ only in the way memory is allocated for a hash
table. The dynamic package, all_hash, obtains memory from malloc(3)
whenever a new hash table is created or its size expanded, and returns
memory with free(3) whenever a hash table is destroyed. The static
package, all_shash, requires that the caller provide memory for the
maximum number of hash table entries when the table is first created.
Functions that operate on a dynamic hash table are named ah_* and func‐
tions that operate on a static hash table are named ahs_*.
A hash table is created and initialized with the ah_init() or
ahs_init() functions. These functions return a pointer to a hash table
descriptor, typedef HASH or SHASH respectively. The hash table
descriptor pointer is used in all subsequent hash table operation. In
the static function, ahs_init(), the caller supplies space not only for
the maximum number of hash table entries, but for the hash table
descriptor and the LRU counters when this mode of operation is used.
The LRU (Least Recently Used) counters keep track of the number of
accesses made to each hash table entry and are used when the AHLRU mode
is chosen. This enables ah_kick() to choose, when the hash table is
full, the least recently used entry as a good candidate to be replaced
by the new entry to be stored in the table. If the AHLRU mode is not
chosen, the LRU counters are not required. In this case, if the hash
table is full, a new entry replaces the old entry at the optimal hash
location. The mode argument is a bit-mapped flag, each flag control‐
ling some characteristic of the hash table. Mode values are con‐
structed by ORing flags from the following list:
AHLRU The least recently used entry is overwritten if the hash
table is full when ah_kick() is called, otherwise the first
(optimal) hashed location is overwritten.
AHNOINIT The hash table is not initialized. Usually, if the data
structures are properly designed (data hiding), this mode
of operation would not be required. If used, the burden of
properly initializing the hash table entries rests on the
user.
A dynamic hash table is freed with the ah_free() function. A static
hash table is simply forgotten, since the caller is responsible for all
the memory involved. Allocating the space for a static hash table is
straight forward. The user needs to allocate two separate arrays of
equal number of entries. One, htable, is the actual hash table and
each of its entries is a user-defined structure. The second, lru, is
only used if the AHLRU mode is chosen and consists of an array of inte‐
gers (32-bit integers) each being used as a counter for an entry in the
hash table. If the AHLRU mode is not chosen, there is no need to allo‐
cate the lru array. An example of how to allocate space for a static
hash table for the AHLRU mode of operation is given below:
struct myelement htable[31];
int lru[31];
SHASH ahsd;
#define ELEMSIZE sizeof(struct myelement)
ahs_init(31, ELEMSIZE, -1, AHLRU, htable, lru, &ahsd);
Thirty one elements of type myelement are allocated and named htable,
and thirty one 32-bit counters are allocated and named lru.
Hash Key and Comparison Function
A hash table entry can be any user-defined structure as long as its
first structure member is a 32-bit integer, known as the key. The user
has to choose one key value, nullkey, to represent an invalid key and
specify it during initialization. This special key value is used to
distinguish between empty and full hash table entries. The key values
are used to insert, delete, and locate entries in the hash table. This
is sufficient in the case where each table entry has a unique key
value.
In some cases, different entries may have equal key values (e.g. hash‐
ing strings). Such a case requires a more general mechanism to distin‐
guish between the different same-key entries. A user-defined compari‐
son function, cmp(), has to be provided to enable searching and delet‐
ing the proper entry among several having the same key value. The user
still has to provide the key value to insert elements, but searching
and deleting are done by using both the hashed key for speed, and the
comparison function to make sure only the right entry is affected. The
comparison function takes two pointers to hash table entries and
returns 0 only if the entries are equal.
Dynamic Hash Table Operators
The following functions operate on dynamic hash tables:
ah_init() Allocate and initialize a dynamic hash table. A hash
table descriptor pointer is returned, or NULL if alloca‐
tion fails. The caller supplies the total number of
entries in the hash table, the size of each element, the
value in the key of an empty element, and the mode of
operation. The size of the element must be at least the
size of an integer (32 bits) in order to be able to con‐
tain the hashing key, which must be the first 32 bits of
the element.
ah_setcmp() Set the comparison function. This function is called
right after ah_init() and is needed when key values are
not unique to each element.
ah_delete() Delete an existing element from a hash table. The ele‐
ment is specified by its key. The function returns -1
and sets errno to EDELETE if the element could not be
found in the given hash table. Otherwise it returns 0.
ah_delete_elm()
Delete an existing element from a hash table. The ele‐
ment is specified by providing a pointer to an equal
element, as determined by the comparison function. The
key of the comparison element must be filled, in addi‐
tion to other user-defined comparison parameters.
Return values are similar to those of ah_delete().
ah_insert() Insert a new element into a hash table. The caller pre‐
pares and supplies a pointer to the new element. The
function copies the contents of the caller supplied ele‐
ment into the appropriate space in the hash table. The
caller can reuse the element. ah_insert() returns -1
and sets errno to EFULL if the hash table has no empty
slots to store the element. Otherwise it returns 0.
ah_kick() Like ah_insert() if the hash table is not full. If the
hash table is full, a slot is chosen and overwritten
with the new information. If the AHLRU mode is used,
the least recently used slot is chosen, otherwise the
first hashed location is overwritten.
ah_free() Free all allocated memory in a dynamic hash table
including the hash table descriptor. The hash table is
effectively blown away. The hash table descriptor
pointer is no longer valid.
ah_find() Find an existing element in the hash table. The caller
provides the search key for the element. A pointer to
the found element is returned, or NULL if the element is
not found.
ah_find_elm() Find an existing element in the hash table. As done in
the case of ah_delete_elm(), the element is specified by
providing a pointer to an equal element. Return values
are similar to those of ah_find().
ah_top() Find the first element in the hash table. A pointer to
the element is returned, or NULL if the hash table is
empty.
ah_next() Find the next element in the hash table. A pointer to
the element is returned, or NULL if the hash table is
empty or the end of the table has been reached. This
function is typically used in conjunction with ah_top()
in order to access all the elements in the hash table
with no prior knowledge of their contents (keys or com‐
parison parameters).
ah_count() A count of all elements in a given hash table is
returned.
ah_size() The size of the given hash table is returned.
ah_expand() Expand the size of a dynamic hash table in order to
accommodate more elements. The caller provides the
desired new hash table size. The new size has to be
larger than the current size. The new hash table inher‐
its the operation mode of the previous hash table except
for the AHNOINIT status which is always turned off, and
the new hash table is initialized. If the AHLRU mode
was set, the LRU counters are reset to zero. This gives
all entries equal chance to be kicked out once the
expanded hash table fills up again. The function
returns -1 if a new hash table could not be allocated.
Otherwise it returns 0.
Static Hash Table Operators
The static hash table functions are very similar. The differences are
listed below.
ahs_init() As explained above, this function requires the caller to
allocate all the memory used by the hash table, includ‐
ing the descriptor.
ahs_free() This function does not exist.
ahs_expand() This function does not exist.
SEE ALSOall_list(3), all_queue(3)LAM 7.1.2 March, 2006 ALL_HASH(3)
