functions implement a generic hash table data structure.
The hash table stores
The user code supplies callback routines for:
- Computing the hash value of an item
- Comparing two items for equality
- Housekeeping associated with adding and removing an item
creates a new hash table.
parameter can be retrieved at any time via
and is otherwise ignored.
The initial size of the hash table (in buckets) is determined by
or defaults to 31 if
is a typed memory type string (see
used when allocating memory for the hash table.
is a maximum load value, measured in percent.
If the ratio of the number of items in the hash table to the number
of buckets grows larger than this value, the number of buckets is
For example, if
is 200, then on average there will never be more than 2 items per bucket.
is given as zero, the default value of 75% is used.
parameters are pointers to user-supplied callback functions having
the following types:
typedef int ghash_equal_t(struct ghash *g,
const void *item1, const void *item2);
typedef u_int32_t ghash_hash_t(struct ghash *g, const void *item);
typedef void ghash_add_t(struct ghash *g, void *item);
typedef void ghash_del_t(struct ghash *g, void *item);
function should return 1 if the items are equal, otherwise 0.
function should return the items 32-bit hash value.
must be consistent, i.e., two items that are equal must
have the same hash value.
the item pointers themselves are compared and hashed;
in effect, the hash table behaves like a set of pointers.
routines, if not
will be called whenever an item is added to, or removed from, the hash table.
For example, if
causes a new item to replace an old item, there will be a call to the
function for the old item, followed by a call to the
function for the new item.
These callbacks are typically used to increase and decrease reference counts.
destroys a hash table and frees all associated memory.
If any items remain in the hash table, the
callback will be invoked once for each item.
Note that this function takes a pointer to a pointer to a hash table.
Upon return, the pointer to the hash table will be set to
If it is already equal to
retrieves an item previously stored in the hash table, or else returns
if the item is not found.
adds an item to the hash table, replacing any item that is equal to it
(as determined by the
is an invalid item and may not be stored in a hash table.
removes an item from the hash table.
If the item does not exist, nothing happens.
returns the number of items in the hash table.
generates an array of all the items in the hash table.
A pointer to the array is stored in
The array is allocated with memory type
The caller must eventually free the array, also using
are used to traverse all items in the hash table consecutively.
is called with a pointer to the caller-supplied
Then, each invocation of
returns the next item in the hash table, or
if no more items remain.
Another way to traverse all hash table elements is using a
which acts as an iterator object.
returns such a structure.
returns non-zero if there are items remaining.
Each invocation of
returns the next item.
removes item the most recently returned by
destroys the iterator.
Note: all associated iterators must be destroyed before calling