.Dd November 3, 1999
.Dt OPEN_HASH 3
.Os
.Sh NAME
.Nm hash_init ,
.Nm hash_delete ,
.Nm hash_lookup_string ,
.Nm hash_lookup_interval ,
.Nm hash_lookup_memory ,
.Nm hash_find ,
.Nm hash_remove ,
.Nm hash_insert ,
.Nm hash_first ,
.Nm hash_next ,
.Nm hash_entries
.Nd light-weight open hashing 
.Sh SYNOPSIS
.Fd #include <sys/types.h>
.Fd #include <stddef.h>
.Fd #include <ohash.h>
.Ft void 
.Fn hash_init "struct hash *h" "unsigned int size" "struct hash_info *info"
.Ft void
.Fn hash_delete "struct hash *h"
.Ft "unsigned int"
.Fn hash_lookup_string "struct hash *h" "const char *k" "u_int32_t v"
.Ft "unsigned int"
.Fn hash_lookup_interval "struct hash *h" "const char *start" "const char *end" "u_int32_t hv"
.Ft "unsigned int"
.Fn hash_lookup_memory "struct hash *h" "const char *k" "size_t s" "u_int32_t hv"
.Ft void *
.Fn hash_find "struct hash *h" "unsigned int i"
.Ft void *
.Fn hash_remove "struct hash *h" "unsigned int i"
.Ft void *
.Fn hash_insert "struct hash *h" "unsigned int i" "void *p"
.Ft void *
.Fn hash_first "struct hash *h" "unsigned int *i"
.Ft void *
.Fn hash_next "struct hash *h" "unsigned int *i"
.Ft "unsigned int"
.Fn hash_entries "struct hash *h"
.Sh DESCRIPTION
Those functions have been designed as a fast, extensible alternative to
the usual hash table functions.  
These provide storing 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  null-terminated strings, or fixed-size memory areas.
All functions take a pointer to a hash structure as the
.Fa h
function argument.  
Storage for this structure should be provided by user code.
.Pp
.Fn hash_init
initializes the table to store roughly 2 to the power
.Fa size
elements.  
.Fa info
holds the position of the key in each record, and two pointers to 
.Xr calloc 3
and
.Xr free 3
-like functions, to use for managing the table internal storage.
.Pp
.Fn hash_delete
frees storage internal to 
.Fa h .
Elements themselves should be freed by the user first, using  for instance
.Fn hash_first 
and
.Fn hash_next .
.Pp
.Fn hash_lookup_string ,
.Fn hash_lookup_interval 
and
.Fn hash_lookup_memory
are the basic look-up element functions.  
The hashing function result is provided by the user as 
.Fa hv .
These return a 
.Qq slot
in the hash table
.Fa h ,
to be used with
.Fn hash_find ,
.Fn hash_insert ,
or
.Fn hash_remove .
This slot is only valid up to the next call to
.Fn hash_insert 
or
.Fn hash_remove .
.Pp
.Fn hash_lookup_string
and
.Fn hash_lookup_interval
handle string-like keys. 
.Fn hash_lookup_string
assumes a null-terminated 
.Ft char *
.Fa k ,
whereas 
.Fn hash_lookup_interval
assumes the key is the interval between 
.Fa start
and
.Fa end ,
exclusive.  
In both cases, the actual elements stored in the hash should contain 
null-terminated keys.
.Pp
.Fn hash_lookup_memory
assumes the key is the memory area starting at
.Fa k
of size
.Fa s .
All bytes are significant in key comparison.
.Pp
.Fn hash_find 
retrieves an element from a slot 
.Fa i 
returned by the 
.Fn hash_lookup*
functions.  
It returns 
.Va NULL 
if the slot is empty.
.Pp
.Fn hash_insert
inserts a new element 
.Fa p
at slot 
.Fa i .
Slot 
.Fa i
must be empty and element
.Fa p
must have a key corresponding to the 
.Fn hash_lookup*
call.
.Pp
.Fn hash_remove
removes element of hash table at slot
.Fa i .
It returns the removed element, for user code to dispose of, or 
.Va NULL
if the slot was empty.
.Pp
.Fn hash_first 
and
.Fn hash_next
can be used to access all elements in a hash table, like this:
.Pp
.Bd -literal
	for (n = hash_first(h, &i); n != NULL; n = hash_next(h, &i))
		do_something_with(n);
.Ed
.Pp
.Fa i
points to an auxiliary unsigned integer used to record the current position
in the hash 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. 
.Pp
.Fn hash_entries
returns the number of elements in the hash table.
.Sh STORAGE HANDLING
Only
.Fn hash_init ,
.Fn hash_insert ,
.Fn hash_remove 
and
.Fn hash_delete
may call the user-supplied memory functions.  
It is the responsability of the user memory allocation code to verify 
that those calls did not fail. 
.Pp
In case memory allocation fails, 
.Fn hash_init
returns a useless hash table.
.Fn hash_insert
and
.Fn hash_remove
still perform the requested operation, but the returned table should be
considered read-only.  
It can still be accessed by
.Fn hash_lookup* ,
.Fn hash_find ,
.Fn hash_first 
and
.Fn hash_next
to dump relevant information to disk before aborting.
.Sh THREAD SAFETY
The open hashing functions are not thread-safe by design.  
In particular, it cannot be guaranteed that a
.Qq slot
will not move in a threaded environment between a 
.Fn hash_lookup*
and a
.Fn hash_find ,
.Fn hash_insert
or
.Fn hash_remove
call.
.Pp
Multi-threaded applications should explicitly protect hash table access.
.Sh SEE ALSO
.Rs
.%A Donald E. Knuth
.%B The Art of Computer Programming
.%V Vol. 3
.%P pp 506-550
.%D 1973
.Re
.Sh HISTORY
Those functions were designed and written for
.Ox
make
by Marc Espie in 1999.