NAME

ghash — generic hash table library

LIBRARY

PDEL Library (libpdel, -lpdel)

SYNOPSIS

#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);

DESCRIPTION

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

RETURN VALUES

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.

IMPLEMENTATION NOTES

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.

HISTORY

The PDEL library was developed at Packet Design, LLC. http://www.packetdesign.com/

AUTHORS

Archie Cobbs ⟨archie@freebsd.org⟩