ghash
—
generic hash table library
PDEL Library (libpdel, -lpdel)
#include <sys/types.h>
#include <pdel/util/ghash.h>
struct ghash *
ghash_create
(void
*arg, u_int isize,
u_int maxload,
const char *mtype,
ghash_hash_t *hash,
ghash_equal_t *equal,
ghash_add_t *add,
ghash_del_t *del);
void
ghash_destroy
(struct
ghash **gp);
void
ghash_arg
(struct
ghash *g);
void *
ghash_get
(struct
ghash *g, const void
*item);
int
ghash_put
(struct
ghash *g, const void
*item);
int
ghash_remove
(struct
ghash *g, const void
*item);
u_int
ghash_size
(struct
ghash *g);
int
ghash_dump
(struct
ghash *g, void
***listp, const char
*mtype);
void
ghash_walk_init
(struct
ghash *g, struct
ghash_walk *walk);
void *
ghash_walk_next
(struct
ghash *g, struct
ghash_walk *walk);
struct ghash_iter *
ghash_iter_create
(struct
ghash *g);
void
ghash_iter_destroy
(struct
ghash_iter **iterp);
int
ghash_iter_has_next
(struct
ghash_iter *iter);
void *
ghash_iter_next
(struct
ghash_iter *iter);
int
ghash_iter_remove
(struct
ghash_iter *iter);
The ghash
functions implement a generic hash table data
structure. The hash table stores items of type
void *. 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
ghash_create
() creates a new hash table.
The arg parameter can be retrieved at any time via
ghash_arg
() and is otherwise ignored. The initial
size of the hash table (in buckets) is determined by
isize, or defaults to 31 if
isize is zero. mtype is a typed
memory type string (see
typed_mem(3))
used when allocating memory for the hash table.
maxload 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 increased.
For example, if maxload is 200, then on average there
will never be more than 2 items per bucket. If maxload
is given as zero, the default value of 75% is used.
The hash, equal,
add, and del 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);
The equal function should return 1 if the items are equal,
otherwise 0. The hash function should return the item's
32-bit hash value. Note that equal and
hash must be consistent, i.e., two items that are equal
must have the same hash value. If equal and
hash are NULL
, the item pointers
themselves are compared and hashed; in effect, the hash table behaves like a
set of pointers.
The add and del
routines, if not NULL
, will be called whenever an
item is added to, or removed from, the hash table. For example, if
ghash_put
() causes a new item to replace an old
item, there will be a call to the del function for the
old item, followed by a call to the add function for
the new item. These callbacks are typically used to increase and decrease
reference counts.
ghash_destroy
() destroys a hash table and
free's all associated memory. If any items remain in the hash table, the
del 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
NULL
. If it is already equal to
NULL
, ghash_destroy
() does
nothing.
ghash_get
() retrieves an item previously
stored in the hash table, or else returns NULL
if
the item is not found.
ghash_put
() adds an item to the hash
table, replacing any item that is equal to it (as determined by the
equal callback). NULL
is an
invalid item and may not be stored in a hash table.
ghash_remove
() removes an item from the
hash table. If the item does not exist, nothing happens.
ghash_size
() returns the number of items
in the hash table.
ghash_dump
() generates an array of all the
items in the hash table. A pointer to the array is stored in
*listp. The array is allocated with memory type
mtype. The caller must eventually free the array, also
using mtype.
ghash_walk_init
() and
ghash_walk_next
() are used to traverse all items in
the hash table consecutively. First,
ghash_walk_init
() is called with a pointer to the
caller-supplied struct ghash_walk
. Then, each
invocation of ghash_walk_next
() returns the next
item in the hash table, or NULL
if no more items
remain.
Another way to traverse all hash table elements is using a
struct ghash_iter
, which acts as an iterator object.
ghash_iter_create
() returns such a structure.
ghash_iter_has_next
() returns non-zero if there are
items remaining. Each invocation of
ghash_iter_next
() returns the next item.
ghash_iter_remove
() removes item the most recently
returned by ghash_iter_next
().
ghash_iter_destroy
() destroys the iterator. Note:
all associated iterators must be destroyed before calling
ghash_destroy
().
ghash_put
() returns 0 if the item is new, or 1 if the
item replaced an existing item. ghash_remove
() returns
0 if the item was not found, or 1 if the item was found and removed.
ghash_dump
() returns the number of items in the
generated array. ghash_create
(),
ghash_put
(), ghash_dump
(), and
ghash_iter_create
() return -1 or
NULL
to indicate an error; errno
will be set to the appropriate value.
The ghash
library is designed to gracefully handle buggy
code. For example, a reentrant call to ghash_put
()
from within the add callback function called as a result
of a previous call to ghash_put
() will return an error
with errno set to EBUSY
.
Similarly, if the hash table is modified in the middle of a traversal,
ghash_walk_next
() or
ghash_iter_next
() will return an error.
The PDEL library was developed at Packet Design, LLC.
http://www.packetdesign.com/
Archie Cobbs ⟨archie@freebsd.org⟩