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