Make libohash a proper internallib instead of hidding it in m4

mandoc development seems to be also using ohash so prepare to share the code when
needed

5 files changed, 3 insertions, 779 deletions

diff --git a/usr.bin/m4/Makefile b/usr.bin/m4/Makefile
index 4f71244da9ce..47cbe3ed18c0 100644
--- a/usr.bin/m4/Makefile
+++ b/usr.bin/m4/Makefile
@@ -7,16 +7,13 @@
 .include <src.opts.mk>
 
 PROG=	m4
-CFLAGS+=-DEXTENDED -I${.CURDIR} -I${.CURDIR}/lib
-DPADD=	${LIBY} ${LIBL} ${LIBM}
-LDADD=	-ly -ll -lm
+CFLAGS+=-DEXTENDED -I${.CURDIR} -I${.CURDIR}/../../lib/libohash
+DPADD=	${LIBY} ${LIBL} ${LIBM} ${LIBOHASH}
+LDADD=	-ly -ll -lm ${LDOHASH}
 
 NO_WMISSING_VARIABLE_DECLARATIONS=
 
 SRCS=	eval.c expr.c look.c main.c misc.c gnum4.c trace.c parser.y tokenizer.l
-.PATH: ${.CURDIR}/lib
-SRCS+=	ohash.c
-WARNS=	3
 
 tokenizer.o: parser.h
 
diff --git a/usr.bin/m4/lib/ohash.c b/usr.bin/m4/lib/ohash.c
deleted file mode 100644
index 3a0f5dde449c..000000000000
--- a/usr.bin/m4/lib/ohash.c
+++ /dev/null
@@ -1,330 +0,0 @@
-/* $OpenBSD: src/lib/libutil/ohash.c,v 1.1 2014/06/02 18:52:03 deraadt Exp $ */
-
-/* Copyright (c) 1999, 2004 Marc Espie <espie@openbsd.org>
- *
- * Permission to use, copy, modify, and distribute this software for any
- * purpose with or without fee is hereby granted, provided that the above
- * copyright notice and this permission notice appear in all copies.
- *
- * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
- * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
- * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
- * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
- * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
- * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
- * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
- */
-
-#include <sys/cdefs.h>
-__FBSDID("$FreeBSD$");
-
-#include <stddef.h>
-#include <stdint.h>
-#include <stdlib.h>
-#include <string.h>
-#include <limits.h>
-#include "ohash.h"
-
-struct _ohash_record {
-	uint32_t	hv;
-	const char	*p;
-};
-
-#define DELETED		((const char *)h)
-#define NONE		(h->size)
-
-/* Don't bother changing the hash table if the change is small enough.  */
-#define MINSIZE		(1UL << 4)
-#define MINDELETED	4
-
-static void ohash_resize(struct ohash *);
-
-
-/* This handles the common case of variable length keys, where the
- * key is stored at the end of the record.
- */
-void *
-ohash_create_entry(struct ohash_info *i, const char *start, const char **end)
-{
-	char *p;
-
-	if (!*end)
-		*end = start + strlen(start);
-	p = (i->alloc)(i->key_offset + (*end - start) + 1, i->data);
-	if (p) {
-		memcpy(p+i->key_offset, start, *end-start);
-		p[i->key_offset + (*end - start)] = '\0';
-	}
-	return (void *)p;
-}
-
-/* hash_delete only frees the hash structure. Use hash_first/hash_next
- * to free entries as well.  */
-void
-ohash_delete(struct ohash *h)
-{
-	(h->info.free)(h->t, h->info.data);
-#ifndef NDEBUG
-	h->t = NULL;
-#endif
-}
-
-static void
-ohash_resize(struct ohash *h)
-{
-	struct _ohash_record *n;
-	size_t ns;
-	unsigned int	j;
-	unsigned int	i, incr;
-
-	if (4 * h->deleted < h->total) {
-		if (h->size >= (UINT_MAX >> 1U))
-			ns = UINT_MAX;
-		else
-			ns = h->size << 1U;
-	} else if (3 * h->deleted > 2 * h->total)
-		ns = h->size >> 1U;
-	else
-		ns = h->size;
-	if (ns < MINSIZE)
-		ns = MINSIZE;
-#ifdef STATS_HASH
-	STAT_HASH_EXPAND++;
-	STAT_HASH_SIZE += ns - h->size;
-#endif
-
-	n = (h->info.calloc)(ns, sizeof(struct _ohash_record), h->info.data);
-	if (!n)
-		return;
-
-	for (j = 0; j < h->size; j++) {
-		if (h->t[j].p != NULL && h->t[j].p != DELETED) {
-			i = h->t[j].hv % ns;
-			incr = ((h->t[j].hv % (ns - 2)) & ~1) + 1;
-			while (n[i].p != NULL) {
-				i += incr;
-				if (i >= ns)
-					i -= ns;
-			}
-			n[i].hv = h->t[j].hv;
-			n[i].p = h->t[j].p;
-		}
-	}
-	(h->info.free)(h->t, h->info.data);
-	h->t = n;
-	h->size = ns;
-	h->total -= h->deleted;
-	h->deleted = 0;
-}
-
-void *
-ohash_remove(struct ohash *h, unsigned int i)
-{
-	void		*result = (void *)h->t[i].p;
-
-	if (result == NULL || result == DELETED)
-		return NULL;
-
-#ifdef STATS_HASH
-	STAT_HASH_ENTRIES--;
-#endif
-	h->t[i].p = DELETED;
-	h->deleted++;
-	if (h->deleted >= MINDELETED && 4 * h->deleted > h->total)
-		ohash_resize(h);
-	return result;
-}
-
-void *
-ohash_find(struct ohash *h, unsigned int i)
-{
-	if (h->t[i].p == DELETED)
-		return NULL;
-	else
-		return (void *)h->t[i].p;
-}
-
-void *
-ohash_insert(struct ohash *h, unsigned int i, void *p)
-{
-#ifdef STATS_HASH
-	STAT_HASH_ENTRIES++;
-#endif
-	if (h->t[i].p == DELETED) {
-		h->deleted--;
-		h->t[i].p = p;
-	} else {
-		h->t[i].p = p;
-		/* Arbitrary resize boundary.  Tweak if not efficient enough.  */
-		if (++h->total * 4 > h->size * 3)
-			ohash_resize(h);
-	}
-	return p;
-}
-
-unsigned int
-ohash_entries(struct ohash *h)
-{
-	return h->total - h->deleted;
-}
-
-void *
-ohash_first(struct ohash *h, unsigned int *pos)
-{
-	*pos = 0;
-	return ohash_next(h, pos);
-}
-
-void *
-ohash_next(struct ohash *h, unsigned int *pos)
-{
-	for (; *pos < h->size; (*pos)++)
-		if (h->t[*pos].p != DELETED && h->t[*pos].p != NULL)
-			return (void *)h->t[(*pos)++].p;
-	return NULL;
-}
-
-void
-ohash_init(struct ohash *h, unsigned int size, struct ohash_info *info)
-{
-	h->size = 1UL << size;
-	if (h->size < MINSIZE)
-		h->size = MINSIZE;
-#ifdef STATS_HASH
-	STAT_HASH_CREATION++;
-	STAT_HASH_SIZE += h->size;
-#endif
-	/* Copy info so that caller may free it.  */
-	h->info.key_offset = info->key_offset;
-	h->info.calloc = info->calloc;
-	h->info.free = info->free;
-	h->info.alloc = info->alloc;
-	h->info.data = info->data;
-	h->t = (h->info.calloc)(h->size, sizeof(struct _ohash_record),
-		    h->info.data);
-	h->total = h->deleted = 0;
-}
-
-uint32_t
-ohash_interval(const char *s, const char **e)
-{
-	uint32_t k;
-
-	if (!*e)
-		*e = s + strlen(s);
-	if (s == *e)
-		k = 0;
-	else
-		k = *s++;
-	while (s != *e)
-		k =  ((k << 2) | (k >> 30)) ^ *s++;
-	return k;
-}
-
-unsigned int
-ohash_lookup_interval(struct ohash *h, const char *start, const char *end,
-    uint32_t hv)
-{
-	unsigned int	i, incr;
-	unsigned int	empty;
-
-#ifdef STATS_HASH
-	STAT_HASH_LOOKUP++;
-#endif
-	empty = NONE;
-	i = hv % h->size;
-	incr = ((hv % (h->size-2)) & ~1) + 1;
-	while (h->t[i].p != NULL) {
-#ifdef STATS_HASH
-		STAT_HASH_LENGTH++;
-#endif
-		if (h->t[i].p == DELETED) {
-			if (empty == NONE)
-				empty = i;
-		} else if (h->t[i].hv == hv &&
-		    strncmp(h->t[i].p+h->info.key_offset, start,
-			end - start) == 0 &&
-		    (h->t[i].p+h->info.key_offset)[end-start] == '\0') {
-			if (empty != NONE) {
-				h->t[empty].hv = hv;
-				h->t[empty].p = h->t[i].p;
-				h->t[i].p = DELETED;
-				return empty;
-			} else {
-#ifdef STATS_HASH
-				STAT_HASH_POSITIVE++;
-#endif
-				return i;
-			}
-		}
-		i += incr;
-		if (i >= h->size)
-			i -= h->size;
-	}
-
-	/* Found an empty position.  */
-	if (empty != NONE)
-		i = empty;
-	h->t[i].hv = hv;
-	return i;
-}
-
-unsigned int
-ohash_lookup_memory(struct ohash *h, const char *k, size_t size, uint32_t hv)
-{
-	unsigned int	i, incr;
-	unsigned int	empty;
-
-#ifdef STATS_HASH
-	STAT_HASH_LOOKUP++;
-#endif
-	empty = NONE;
-	i = hv % h->size;
-	incr = ((hv % (h->size-2)) & ~1) + 1;
-	while (h->t[i].p != NULL) {
-#ifdef STATS_HASH
-		STAT_HASH_LENGTH++;
-#endif
-		if (h->t[i].p == DELETED) {
-			if (empty == NONE)
-				empty = i;
-		} else if (h->t[i].hv == hv &&
-		    memcmp(h->t[i].p+h->info.key_offset, k, size) == 0) {
-			if (empty != NONE) {
-				h->t[empty].hv = hv;
-				h->t[empty].p = h->t[i].p;
-				h->t[i].p = DELETED;
-				return empty;
-			} else {
-#ifdef STATS_HASH
-				STAT_HASH_POSITIVE++;
-#endif
-			}	return i;
-		}
-		i += incr;
-		if (i >= h->size)
-			i -= h->size;
-	}
-
-	/* Found an empty position.  */
-	if (empty != NONE)
-		i = empty;
-	h->t[i].hv = hv;
-	return i;
-}
-
-unsigned int
-ohash_qlookup(struct ohash *h, const char *s)
-{
-	const char *e = NULL;
-	return ohash_qlookupi(h, s, &e);
-}
-
-unsigned int
-ohash_qlookupi(struct ohash *h, const char *s, const char **e)
-{
-	uint32_t hv;
-
-	hv = ohash_interval(s, e);
-	return ohash_lookup_interval(h, s, *e, hv);
-}
diff --git a/usr.bin/m4/lib/ohash.h b/usr.bin/m4/lib/ohash.h
deleted file mode 100644
index 03de431d726b..000000000000
--- a/usr.bin/m4/lib/ohash.h
+++ /dev/null
@@ -1,75 +0,0 @@
-/* $OpenBSD: src/lib/libutil/ohash.h,v 1.2 2014/06/02 18:52:03 deraadt Exp $ */
-
-/* Copyright (c) 1999, 2004 Marc Espie <espie@openbsd.org>
- *
- * Permission to use, copy, modify, and distribute this software for any
- * purpose with or without fee is hereby granted, provided that the above
- * copyright notice and this permission notice appear in all copies.
- *
- * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
- * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
- * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
- * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
- * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
- * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
- * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
- *
- * $FreeBSD$
- */
-
-#ifndef OHASH_H
-#define OHASH_H
-
-/* Open hashing support. 
- * Open hashing was chosen because it is much lighter than other hash
- * techniques, and more efficient in most cases.
- */
-
-/* user-visible data structure */
-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 *);
-};
-
-struct _ohash_record;
-
-/* private structure. It's there just so you can do a sizeof */
-struct ohash {
-	struct _ohash_record 	*t;
-	struct ohash_info 	info;
-	unsigned int 		size;
-	unsigned int 		total;
-	unsigned int 		deleted;
-};
-
-/* For this to be tweakable, we use small primitives, and leave part of the
- * logic to the client application.  e.g., hashing is left to the client
- * application.  We also provide a simple table entry lookup that yields
- * a hashing table index (opaque) to be used in find/insert/remove.
- * The keys are stored at a known position in the client data.
- */
-__BEGIN_DECLS
-void ohash_init(struct ohash *, unsigned, struct ohash_info *);
-void ohash_delete(struct ohash *);
-
-unsigned int ohash_lookup_interval(struct ohash *, const char *,
-	    const char *, uint32_t);
-unsigned int ohash_lookup_memory(struct ohash *, const char *,
-	    size_t, uint32_t);
-void *ohash_find(struct ohash *, unsigned int);
-void *ohash_remove(struct ohash *, unsigned int);
-void *ohash_insert(struct ohash *, unsigned int, void *);
-void *ohash_first(struct ohash *, unsigned int *);
-void *ohash_next(struct ohash *, unsigned int *);
-unsigned int ohash_entries(struct ohash *);
-
-void *ohash_create_entry(struct ohash_info *, const char *, const char **);
-uint32_t ohash_interval(const char *, const char **);
-
-unsigned int ohash_qlookupi(struct ohash *, const char *, const char **);
-unsigned int ohash_qlookup(struct ohash *, const char *);
-__END_DECLS
-#endif
diff --git a/usr.bin/m4/lib/ohash_init.3 b/usr.bin/m4/lib/ohash_init.3
deleted file mode 100644
index 184c4e389b24..000000000000
--- a/usr.bin/m4/lib/ohash_init.3
+++ /dev/null
@@ -1,273 +0,0 @@
-.\"	$OpenBSD: ohash_init.3,v 1.2 2014/05/13 14:01:41 jmc Exp $
-.\" Copyright (c) 1999 Marc Espie <espie@openbsd.org>
-.\"
-.\" Permission to use, copy, modify, and distribute this software for any
-.\" purpose with or without fee is hereby granted, provided that the above
-.\" copyright notice and this permission notice appear in all copies.
-.\"
-.\" THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
-.\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
-.\" MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
-.\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
-.\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
-.\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
-.\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
-.\"
-.\" $FreeBSD$
-.\"
-.Dd May 12, 2014
-.Dt OHASH_INIT 3
-.Os
-.Sh NAME
-.Nm ohash_init ,
-.Nm ohash_delete ,
-.Nm ohash_lookup_interval ,
-.Nm ohash_lookup_memory ,
-.Nm ohash_find ,
-.Nm ohash_remove ,
-.Nm ohash_insert ,
-.Nm ohash_first ,
-.Nm ohash_next ,
-.Nm ohash_entries
-.Nd light-weight open hashing
-.Sh SYNOPSIS
-.In stdint.h
-.In stddef.h
-.In ohash.h
-.Ft void
-.Fn ohash_init "struct ohash *h" "unsigned int size" "struct ohash_info *info"
-.Ft void
-.Fn ohash_delete "struct ohash *h"
-.Ft "unsigned int"
-.Fn ohash_lookup_interval "struct ohash *h" "const char *start" "const char *end" "uint32_t hv"
-.Ft "unsigned int"
-.Fn ohash_lookup_memory "struct ohash *h" "const char *k" "size_t s" "uint32_t hv"
-.Ft void *
-.Fn ohash_find "struct ohash *h" "unsigned int i"
-.Ft void *
-.Fn ohash_remove "struct ohash *h" "unsigned int i"
-.Ft void *
-.Fn ohash_insert "struct ohash *h" "unsigned int i" "void *p"
-.Ft void *
-.Fn ohash_first "struct ohash *h" "unsigned int *i"
-.Ft void *
-.Fn ohash_next "struct ohash *h" "unsigned int *i"
-.Ft "unsigned int"
-.Fn ohash_entries "struct ohash *h"
-.Sh 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
-.Fa h
-function argument.
-Storage for this structure should be provided by user code.
-.Pp
-.Fn ohash_init
-initializes the table to store roughly 2 to the power
-.Fa size
-elements.
-.Fa info
-is a pointer to a
-.Fa struct ohash_info .
-.Bd -literal -offset indent
-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 *);
-};
-.Ed
-.Pp
-The
-.Va offset
-field holds the position of the key in each record;
-the
-.Va calloc
-and
-.Va free
-fields are pointers to
-.Xr calloc 3
-and
-.Xr free 3 Ns -like
-functions, used for managing the table internal storage;
-the
-.Va alloc
-field is only used by the utility function
-.Xr ohash_create_entry 3 .
-.Pp
-Each of these functions are called similarly to their standard counterpart,
-but with an extra
-.Ft void *
-parameter corresponding to the content of the field
-.Fa data ,
-which can be used to communicate specific information to the functions.
-.Pp
-.Fn ohash_init
-stores a copy of those fields internally, so
-.Fa info
-can be reclaimed after initialization.
-.Pp
-.Fn ohash_delete
-frees storage internal to
-.Fa h .
-Elements themselves should be freed by the user first, using for instance
-.Fn ohash_first
-and
-.Fn ohash_next .
-.Pp
-.Fn ohash_lookup_interval
-and
-.Fn ohash_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 ohash table
-.Fa h ,
-to be used with
-.Fn ohash_find ,
-.Fn ohash_insert ,
-or
-.Fn ohash_remove .
-This slot is only valid up to the next call to
-.Fn ohash_insert
-or
-.Fn ohash_remove .
-.Pp
-.Fn ohash_lookup_interval
-handles string-like keys.
-.Fn ohash_lookup_interval
-assumes the key is the interval between
-.Fa start
-and
-.Fa end ,
-exclusive,
-though the actual elements stored in the table should only contain
-NUL-terminated keys.
-.Pp
-.Fn ohash_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 ohash_find
-retrieves an element from a slot
-.Fa i
-returned by the
-.Fn ohash_lookup*
-functions.
-It returns
-.Dv NULL
-if the slot is empty.
-.Pp
-.Fn ohash_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 ohash_lookup*
-call.
-.Pp
-.Fn ohash_remove
-removes the element at slot
-.Fa i .
-It returns the removed element, for user code to dispose of, or
-.Dv NULL
-if the slot was empty.
-.Pp
-.Fn ohash_first
-and
-.Fn ohash_next
-can be used to access all elements in an ohash table, like this:
-.Bd -literal -offset indent
-for (n = ohash_first(h, &i); n != NULL; n = ohash_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 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.
-.Pp
-.Fn ohash_entries
-returns the number of elements in the hash table.
-.Sh STORAGE HANDLING
-Only
-.Fn ohash_init ,
-.Fn ohash_insert ,
-.Fn ohash_remove
-and
-.Fn ohash_delete
-may call the user-supplied memory functions:
-.Bd -literal -offset indent
-p = (*info->calloc)(n, sizeof_record, info->data);
-/* copy data from old to p */
-(*info->free)(old, info->data);
-.Ed
-.Pp
-It is the responsibility of the user memory allocation code to verify
-that those calls did not fail.
-.Pp
-If memory allocation fails,
-.Fn ohash_init
-returns a useless hash table.
-.Fn ohash_insert
-and
-.Fn ohash_remove
-still perform the requested operation, but the returned table should be
-considered read-only.
-It can still be accessed by
-.Fn ohash_lookup* ,
-.Fn ohash_find ,
-.Fn ohash_first
-and
-.Fn ohash_next
-to dump relevant information to disk before aborting.
-.Sh THREAD SAFETY
-The open hashing functions are not thread-safe by design.
-In particular, in a threaded environment, there is no guarantee that a
-.Qq slot
-will not move between a
-.Fn ohash_lookup*
-and a
-.Fn ohash_find ,
-.Fn ohash_insert
-or
-.Fn ohash_remove
-call.
-.Pp
-Multi-threaded applications should explicitly protect ohash table access.
-.Sh SEE ALSO
-.Xr hcreate 3 ,
-.Xr ohash_interval 3
-.Rs
-.%A Donald E. Knuth
-.%B The Art of Computer Programming
-.%V Vol. 3
-.%P pp 506-550
-.%D 1973
-.Re
-.Sh STANDARDS
-Those functions are completely non-standard and should be avoided in
-portable programs.
-.Sh HISTORY
-Those functions were designed and written for
-.Ox
-.Xr make 1
-by Marc Espie in 1999.
diff --git a/usr.bin/m4/lib/ohash_interval.3 b/usr.bin/m4/lib/ohash_interval.3
deleted file mode 100644
index 3809c34e3c0f..000000000000
--- a/usr.bin/m4/lib/ohash_interval.3
+++ /dev/null
@@ -1,95 +0,0 @@
-.\"	$OpenBSD: ohash_interval.3,v 1.1 2014/05/12 19:09:00 espie Exp $
-.\" Copyright (c) 2001 Marc Espie <espie@openbsd.org>
-.\"
-.\" Permission to use, copy, modify, and distribute this software for any
-.\" purpose with or without fee is hereby granted, provided that the above
-.\" copyright notice and this permission notice appear in all copies.
-.\"
-.\" THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
-.\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
-.\" MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
-.\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
-.\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
-.\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
-.\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
-.\"
-.\" $FreeBSD$
-.\"
-.Dd June 5, 2013
-.Dt OHASH_INTERVAL 3
-.Os
-.Sh NAME
-.Nm ohash_interval ,
-.Nm ohash_create_entry ,
-.Nm ohash_qlookup ,
-.Nm ohash_qlookupi
-.Nd helper functions for open hashing
-.Sh SYNOPSIS
-.In stdint.h
-.In stddef.h
-.In ohash.h
-.Ft uint32_t
-.Fn ohash_interval "const char *start" "const char **pend"
-.Ft "void *"
-.Fn ohash_create_entry "struct ohash_info *info" "const char *start" "const char **pend"
-.Ft "unsigned int"
-.Fn ohash_qlookupi "struct ohash *h" "const char *start" "const char **pend"
-.Ft "unsigned int"
-.Fn ohash_qlookup "struct ohash *h" "const char *start"
-.Sh DESCRIPTION
-These functions are commonly used to simplify open hashing usage, and use
-similar conventions.
-They operate indifferently on NUL-terminated strings
-.Po
-by setting
-.Fa *pend
-=
-.Dv NULL
-.Pc
-or memory ranges
-.Po
-delimited by
-.Fa start
-and
-.Fa *pend
-.Pc .
-For NUL-terminated strings, as a side effect, those functions
-set
-.Fa *pend
-to the terminating NUL byte.
-.Pp
-.Fn ohash_interval
-is a simple hashing function that yields good results on common data sets.
-.Pp
-.Fn ohash_create_entry
-can be used to create a new record with a given key.
-In that case,
-the alloc field of
-.Fa info
-should point to a
-.Xr malloc 3 Ns -like
-function to allocate the storage:
-.Bd -literal -offset indent
-p = (*info->alloc)(sz, info->data);
-.Ed
-.Pp
-.Fn ohash_qlookupi
-is a wrapper function that simply calls
-.Fn ohash_interval
-and
-.Fn ohash_lookup_interval .
-.Pp
-.Fn ohash_qlookup
-is a variation on
-.Fn ohash_qlookupi
-designed for NUL-terminated strings.
-.Sh SEE ALSO
-.Xr ohash_init 3
-.Sh STANDARDS
-Those functions are completely non-standard and should be avoided in
-portable programs.
-.Sh HISTORY
-Those functions were designed and written for
-.Ox
-.Xr make 1
-by Marc Espie in 1999.