OPEN_HASH(3) BSD Programmer's Manual OPEN_HASH(3)
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
#include <sys/types.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, u_int32_t hv);
unsigned int
ohash_lookup_memory(struct ohash *h, const char *k, size_t s,
u_int32_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);
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 holds the position of the key in each record, and two
pointers to calloc(3) and free(3)-like functions, to use for managing the
table internal storage.
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 ele-
ment, 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 po-
sition in the ohash table. Those functions are safe to use even while en-
tries 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.
Only ohash_init(), ohash_insert(), ohash_remove() and ohash_delete() may
call the user-supplied memory functions. 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.
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.
ohash_interval(3)
Donald E. Knuth, The Art of Computer Programming, Vol. 3, pp 506-550,
1973.
Those functions are completely non-standard and should be avoided in
portable programs.
Those functions were designed and written for OpenBSD make(1) by Marc
Espie in 1999.
MirBSD #10-current November 3, 1999 1