ALL_HASH (3)
general purpose hash table management (LAM)
SYNOPSIS
.75i 1.25i
#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 functions 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 controlling some characteristic
of the hash table.
Mode
values are constructed 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 integers
(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 allocate 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 .
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. hashing
strings).
Such a case requires a more general mechanism to distinguish between
the different same-key entries.
A user-defined comparison function,
cmp() ,
has to be provided to enable searching and deleting 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.
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 allocation 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 contain 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 element 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 element 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 addition 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 prepares and supplies a pointer to the new element.
The function copies the contents of the caller supplied element 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 comparison 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 inherits 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.
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, including the descriptor.
ahs_free()
This function does not exist.
ahs_expand()
This function does not exist.
SEE ALSO
|