all_hash

Langue: en

Version: 63240 (mandriva - 22/10/07)

Section: 3 (Bibliothèques de fonctions)

Sommaire

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 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.

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. 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.

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 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.

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, including the descriptor.
ahs_free()
This function does not exist.
ahs_expand()
This function does not exist.

SEE ALSO

all_list(3), all_queue(3)