MirOS Manual: ohash_delete(3), ohash_entries(3), ohash_find(3), ohash_first(3), ohash_init(3), ohash_insert(3), ohash_lookup_interval(3), ohash_lookup_memory(3), ohash_next(3), ohash_remove(3)

OPEN_HASH(3)               BSD Programmer's Manual                OPEN_HASH(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 <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);

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

STORAGE HANDLING

     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.

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

     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.

MirOS BSD #10-current          November 3, 1999                              1

Generated on 2017-04-03 16:26:17 by $MirOS: src/scripts/roff2htm,v 1.88 2017/01/29 00:51:06 tg Exp $

These manual pages and other documentation are copyrighted by their respective writers; their source is available at our CVSweb, AnonCVS, and other mirrors. The rest is Copyright © 2002–2017 The MirOS Project, Germany.
This product includes material provided by mirabilos.

This manual page’s HTML representation is supposed to be valid XHTML/1.1; if not, please send a bug report — diffs preferred.