Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages


home | help
GHASH(3)	       FreeBSD Library Functions Manual		      GHASH(3)

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

     ghash_destroy(struct ghash	**gp);

     ghash_arg(struct ghash *g);

     void *
     ghash_get(struct ghash *g,	const void *item);

     ghash_put(struct ghash *g,	const void *item);

     ghash_remove(struct ghash *g, const void *item);

     ghash_size(struct ghash *g);

     ghash_dump(struct ghash *g, void ***listp,	const char *mtype);

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

     ghash_iter_destroy(struct ghash_iter **iterp);

     ghash_iter_has_next(struct	ghash_iter *iter);

     void *
     ghash_iter_next(struct ghash_iter *iter);

     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:

	+o   Computing the hash value of	an item

	+o   Comparing two items	for equality

	+o   Housekeeping associated with adding	and removing an	item

     ghash_create() creates a new hash table.  The arg parameter can be	re-
     trieved at	any time via ghash_arg() and is	otherwise ignored.  The	ini-
     tial size of the hash table (in buckets) is determined by isize, or de-
     faults 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

     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

     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()	re-
     turns 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_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 exam-
     ple, a reentrant call to ghash_put() from within the add callback func-
     tion 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.

     gtree(3), libpdel(3), typed_mem(3)

     The PDEL library was developed at Packet Design, LLC.

     Archie Cobbs <>

FreeBSD	13.0			April 22, 2002			  FreeBSD 13.0


Want to link to this manual page? Use this URL:

home | help