NAME    [Toc]    [Back]

     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    [Toc]    [Back]

     #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    [Toc]    [Back]

     Those 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 nullterminated
     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 null-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    [Toc]    [Back]

     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    [Toc]    [Back]

     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    [Toc]    [Back]

     Donald E. Knuth, The Art of Computer Programming, Vol. 3, pp
506-550,
     1973.  ohash_interval(3)

STANDARDS    [Toc]    [Back]

     Those  functions  are  completely non-standard and should be
avoided in
     portable programs.

HISTORY    [Toc]    [Back]

     Those  functions  were  designed  and  written  for  OpenBSD
make(1) by Marc Espie
 in 1999.

OpenBSD      3.6                         November     3,     1999