GSP
Quick Navigator

Search Site

Unix VPS
A - Starter
B - Basic
C - Preferred
D - Commercial
MPS - Dedicated
Previous VPSs
* Sign Up! *

Support
Contact Us
Online Help
Handbooks
Domain Status
Man Pages

FAQ
Virtual Servers
Pricing
Billing
Technical

Network
Facilities
Connectivity
Topology Map

Miscellaneous
Server Agreement
Year 2038
Credits
 

USA Flag

 

 

Man Pages


Manual Reference Pages  -  GHASH (3)

NAME

ghash - generic hash table library

CONTENTS

Library
Synopsis
Description
Return Values
Implementation Notes
See Also
History
Authors

LIBRARY

PDEL Library (libpdel, -lpdel)

SYNOPSIS


.In sys/types.h
.In 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.

SEE ALSO

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

HISTORY

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

AUTHORS


.An Archie Cobbs Aq archie@freebsd.org
Search for    or go to Top of page |  Section 3 |  Main Index


Powered by GSP Visit the GSP FreeBSD Man Page Interface.
Output converted with manServer 1.07.