*** UNIX MANUAL PAGE BROWSER ***

OHASH_INIT(3) FreeBSD Library Functions Manual OHASH_INIT(3) NAME ohash_init, ohash_delete, ohash_lookup_interval, ohash_lookup_memory, ohash_find, ohash_remove, ohash_insert, ohash_first, ohash_next, ohash_entries - light-weight open hashing SYNOPSIS #include <stdint.h> #include <stddef.h> #include <ohash.h> void ohash_init(struct ohash *h, unsigned int size, struct ohash_info *info); void ohash_delete(struct ohash *h); unsigned int ohash_lookup_interval(struct ohash *h, const char *start, const char *end, uint32_t hv); unsigned int ohash_lookup_memory(struct ohash *h, const char *k, size_t s, uint32_t hv); void * ohash_find(struct ohash *h, unsigned int i); void * ohash_remove(struct ohash *h, unsigned int i); void * ohash_insert(struct ohash *h, unsigned int i, void *p); void * ohash_first(struct ohash *h, unsigned int *i); void * ohash_next(struct ohash *h, unsigned int *i); unsigned int ohash_entries(struct ohash *h); DESCRIPTION These functions have been designed as a fast, extensible alternative to the usual hash table functions. They provide storage and retrieval of records indexed by keys, where a key is a contiguous sequence of bytes at a fixed position in each record. Keys can either be NUL-terminated strings or fixed-size memory areas. All functions take a pointer to an ohash structure as the h function argument. Storage for this structure should be provided by user code. ohash_init() initializes the table to store roughly 2 to the power size elements. info is a pointer to a struct ohash_info. struct ohash_info { ptrdiff_t key_offset; void *data; /* user data */ void *(*calloc)(size_t, size_t, void *); void (*free)(void *, void *); void *(*alloc)(size_t, void *); }; The offset field holds the position of the key in each record; the calloc and free fields are pointers to calloc(3) and free(3)-like functions, used for managing the table internal storage; the alloc field is only used by the utility function ohash_create_entry(3). Each of these functions are called similarly to their standard counterpart, but with an extra void * parameter corresponding to the content of the field data, which can be used to communicate specific information to the functions. ohash_init() stores a copy of those fields internally, so info can be reclaimed after initialization. ohash_delete() frees storage internal to h. Elements themselves should be freed by the user first, using for instance ohash_first() and ohash_next(). ohash_lookup_interval() and ohash_lookup_memory() are the basic look-up element functions. The hashing function result is provided by the user as hv. These return a "slot" in the ohash table h, to be used with ohash_find(), ohash_insert(), or ohash_remove(). This slot is only valid up to the next call to ohash_insert() or ohash_remove(). ohash_lookup_interval() handles string-like keys. ohash_lookup_interval() assumes the key is the interval between start and end, exclusive, though the actual elements stored in the table should only contain NUL-terminated keys. ohash_lookup_memory() assumes the key is the memory area starting at k of size s. All bytes are significant in key comparison. ohash_find() retrieves an element from a slot i returned by the ohash_lookup*() functions. It returns NULL if the slot is empty. ohash_insert() inserts a new element p at slot i. Slot i must be empty and element p must have a key corresponding to the ohash_lookup*() call. ohash_remove() removes the element at slot i. It returns the removed element, for user code to dispose of, or NULL if the slot was empty. ohash_first() and ohash_next() can be used to access all elements in an ohash table, like this: for (n = ohash_first(h, &i); n != NULL; n = ohash_next(h, &i)) do_something_with(n); i points to an auxiliary unsigned integer used to record the current position in the ohash table. Those functions are safe to use even while entries are added to/removed from the table, but in such a case they don't guarantee that new entries will be returned. As a special case, they can safely be used to free elements in the table. ohash_entries() returns the number of elements in the hash table. STORAGE HANDLING Only ohash_init(), ohash_insert(), ohash_remove() and ohash_delete() may call the user-supplied memory functions: p = (*info->calloc)(n, sizeof_record, info->data); /* copy data from old to p */ (*info->free)(old, info->data); It is the responsibility of the user memory allocation code to verify that those calls did not fail. If memory allocation fails, ohash_init() returns a useless hash table. ohash_insert() and ohash_remove() still perform the requested operation, but the returned table should be considered read-only. It can still be accessed by ohash_lookup*(), ohash_find(), ohash_first() and ohash_next() to dump relevant information to disk before aborting. THREAD SAFETY The open hashing functions are not thread-safe by design. In particular, in a threaded environment, there is no guarantee that a "slot" will not move between a ohash_lookup*() and a ohash_find(), ohash_insert() or ohash_remove() call. Multi-threaded applications should explicitly protect ohash table access. SEE ALSO hcreate(3), ohash_interval(3) Donald E. Knuth, The Art of Computer Programming, Vol. 3, pp. 506-550, 1973. STANDARDS Those functions are completely non-standard and should be avoided in portable programs. HISTORY Those functions were designed and written for OpenBSD make(1) by Marc Espie in 1999. FreeBSD 14.1-RELEASE-p8 April 23, 2019 FreeBSD 14.1-RELEASE-p8