Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages


home | help
OHASH_INIT(3)		 BSD Library Functions Manual		 OHASH_INIT(3)

     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

     OpenBSD Utilities Library (libopenbsd, -lopenbsd)

     #include <stdint.h>
     #include <stddef.h>
     #include <ohash.h>

     ohash_init(struct ohash *h, unsigned int size, struct ohash_info *info);

     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);

     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 counter-
     part, 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 re-
     claimed 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_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 el-
     ement, 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))

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

     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.

     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.

     hcreate(3), ohash_interval(3)

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

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

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

BSD				 May 12, 2014				   BSD


Want to link to this manual page? Use this URL:

home | help