OHASH_INIT(3) | 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

System Utilities Library (libutil, -lutil)
`#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.

June 13, 2025 | Debian