Add ohash_* functions to libc.

Ok'd deraadt@, millert@

17 files changed, 1069 insertions, 2 deletions

diff --git a/lib/libc/Makefile.inc b/lib/libc/Makefile.inc
index 72ecb7fa6d1..c9f6ddef254 100644
--- a/lib/libc/Makefile.inc
+++ b/lib/libc/Makefile.inc
@@ -1,4 +1,4 @@
-#	$OpenBSD: Makefile.inc,v 1.3 2000/09/03 18:41:13 espie Exp $
+#	$OpenBSD: Makefile.inc,v 1.4 2001/03/02 13:27:05 espie Exp $
 #
 # This file contains make rules that are shared by libc and libc_r.
 #
@@ -35,6 +35,7 @@ AINC+=  -nostdinc -idirafter ${DESTDIR}/usr/include
 .include "${LIBCSRCDIR}/md/Makefile.inc"
 .include "${LIBCSRCDIR}/net/Makefile.inc"
 .include "${LIBCSRCDIR}/nls/Makefile.inc"
+.include "${LIBCSRCDIR}/ohash/Makefile.inc"
 .if (${MACHINE_ARCH} != "alpha")
 .include "${LIBCSRCDIR}/quad/Makefile.inc"
 .endif
diff --git a/lib/libc/ohash/Makefile.inc b/lib/libc/ohash/Makefile.inc
new file mode 100644
index 00000000000..91babfa3671
--- /dev/null
+++ b/lib/libc/ohash/Makefile.inc
@@ -0,0 +1,25 @@
+# $OpenBSD: Makefile.inc,v 1.1 2001/03/02 13:27:06 espie Exp $
+
+
+# open hashing functions
+.PATH: ${LIBCSRCDIR}/ohash
+
+SRCS+=	ohash_create_entry.c ohash_delete.c ohash_do.c ohash_entries.c \
+	ohash_enum.c ohash_init.c ohash_interval.c \
+	ohash_lookup_interval.c ohash_lookup_memory.c \
+	ohash_qlookup.c ohash_qlookupi.c
+
+MAN+=	ohash_init.3 ohash_interval.3
+MLINKS+=ohash_init.3 ohash_delete.3 \
+	ohash_init.3 ohash_lookup_string.3 \
+	ohash_init.3 ohash_lookup_interval.3 \
+	ohash_init.3 ohash_lookup_memory.3 \
+	ohash_init.3 ohash_find.3 \
+	ohash_init.3 ohash_remove.3 \
+	ohash_init.3 ohash_insert.3 \
+	ohash_init.3 ohash_first.3 \
+	ohash_init.3 ohash_next.3 \
+	ohash_init.3 ohash_entries.3 \
+	ohash_interval.3 ohash_create_entry.3 \
+	ohash_interval.3 ohash_qlookupi.3 \
+	ohash_interval.3 ohash_qlookup.3
diff --git a/lib/libc/ohash/ohash_create_entry.c b/lib/libc/ohash/ohash_create_entry.c
new file mode 100644
index 00000000000..6f8d1a01077
--- /dev/null
+++ b/lib/libc/ohash/ohash_create_entry.c
@@ -0,0 +1,53 @@
+/* $OpenBSD: ohash_create_entry.c,v 1.1 2001/03/02 13:27:07 espie Exp $ */
+/* ex:ts=8 sw=4: 
+ */
+
+/*
+ * Copyright (c) 1999 Marc Espie.
+ *
+ * Code written for the OpenBSD project.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OPENBSD
+ * PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "ohash_int.h"
+
+/* This handles the common case of variable length keys, where the 
+ * key is stored at the end of the record.
+ */
+void *
+ohash_create_entry(i, start, end)
+	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;
+}
diff --git a/lib/libc/ohash/ohash_delete.c b/lib/libc/ohash/ohash_delete.c
new file mode 100644
index 00000000000..55067558861
--- /dev/null
+++ b/lib/libc/ohash/ohash_delete.c
@@ -0,0 +1,45 @@
+/* $OpenBSD: ohash_delete.c,v 1.1 2001/03/02 13:27:07 espie Exp $ */
+/* ex:ts=8 sw=4: 
+ */
+
+/*
+ * Copyright (c) 1999 Marc Espie.
+ *
+ * Code written for the OpenBSD project.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OPENBSD
+ * PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "ohash_int.h"
+/* hash_delete only frees the hash structure. Use hash_first/hash_next
+ * to free entries as well.  */
+void 
+ohash_delete(h)
+	struct ohash 	*h;
+{
+	(h->info.hfree)(h->t, sizeof(struct _ohash_record) * h->size,
+		h->info.data);
+#ifndef NDEBUG
+	h->t = NULL;
+#endif
+}
+	
diff --git a/lib/libc/ohash/ohash_do.c b/lib/libc/ohash/ohash_do.c
new file mode 100644
index 00000000000..c5fc551d763
--- /dev/null
+++ b/lib/libc/ohash/ohash_do.c
@@ -0,0 +1,132 @@
+/* $OpenBSD: ohash_do.c,v 1.1 2001/03/02 13:27:07 espie Exp $ */
+/* ex:ts=8 sw=4: 
+ */
+
+/*
+ * Copyright (c) 1999 Marc Espie.
+ *
+ * Code written for the OpenBSD project.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OPENBSD
+ * PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "ohash_int.h"
+
+static void ohash_resize __P((struct ohash *));
+
+static void 
+ohash_resize(h)
+	struct ohash 	*h;
+{
+	struct _ohash_record *n;
+	unsigned int 	ns, j;
+	unsigned int	i, incr;
+
+	if (4 * h->deleted < h->total)
+		ns = h->size << 1;
+	else if (3 * h->deleted > 2 * h->total)
+		ns = h->size >> 1;
+	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.halloc)(sizeof(struct _ohash_record) * ns, 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.hfree)(h->t, sizeof(struct _ohash_record) * h->size, 
+		h->info.data);
+	h->t = n;
+	h->size = ns;
+	h->total -= h->deleted;
+	h->deleted = 0;
+}
+
+void *
+ohash_remove(h, i)
+	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)
+		hash_resize(h);
+	return result;
+}
+
+void *
+ohash_find(h, i)
+	struct ohash 	*h;
+	unsigned int 	i;
+{
+	if (h->t[i].p == DELETED)
+		return NULL;
+	else
+		return (void *)h->t[i].p;
+}
+
+void *
+ohash_insert(h, i, p)
+	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)
+			hash_resize(h);
+	}
+    	return p;
+}
+
diff --git a/lib/libc/ohash/ohash_entries.c b/lib/libc/ohash/ohash_entries.c
new file mode 100644
index 00000000000..9668eb4282d
--- /dev/null
+++ b/lib/libc/ohash/ohash_entries.c
@@ -0,0 +1,40 @@
+/* $OpenBSD: ohash_entries.c,v 1.1 2001/03/02 13:27:07 espie Exp $ */
+/* ex:ts=8 sw=4: 
+ */
+
+/*
+ * Copyright (c) 1999 Marc Espie.
+ *
+ * Code written for the OpenBSD project.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OPENBSD
+ * PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "ohash_int.h"
+
+unsigned int
+ohash_entries(h)
+	struct ohash	*h;
+{
+	return h->total - h->deleted;
+}
+
diff --git a/lib/libc/ohash/ohash_enum.c b/lib/libc/ohash/ohash_enum.c
new file mode 100644
index 00000000000..6c43e5e0263
--- /dev/null
+++ b/lib/libc/ohash/ohash_enum.c
@@ -0,0 +1,52 @@
+/* $OpenBSD: ohash_enum.c,v 1.1 2001/03/02 13:27:07 espie Exp $ */
+/* ex:ts=8 sw=4: 
+ */
+
+/*
+ * Copyright (c) 1999 Marc Espie.
+ *
+ * Code written for the OpenBSD project.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OPENBSD
+ * PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "ohash_int.h"
+
+void *
+ohash_first(h, pos)
+	struct ohash 	*h;
+	unsigned int 	*pos;
+{
+	*pos = 0;
+	return ohash_next(h, pos);
+}
+	
+void *
+hash_next(h, pos)
+	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;
+}
diff --git a/lib/libc/ohash/ohash_init.3 b/lib/libc/ohash/ohash_init.3
new file mode 100644
index 00000000000..204d4519004
--- /dev/null
+++ b/lib/libc/ohash/ohash_init.3
@@ -0,0 +1,242 @@
+.\"	$OpenBSD: ohash_init.3,v 1.1 2001/03/02 13:27:07 espie Exp $
+.\"
+.\" Copyright (c) 1999 Marc Espie.
+.\"
+.\" Code written for the OpenBSD project.
+.\"
+.\" Redistribution and use in source and binary forms, with or without
+.\" modification, are permitted provided that the following conditions
+.\" are met:
+.\" 1. Redistributions of source code must retain the above copyright
+.\"    notice, this list of conditions and the following disclaimer.
+.\" 2. Redistributions in binary form must reproduce the above copyright
+.\"    notice, this list of conditions and the following disclaimer in the
+.\"    documentation and/or other materials provided with the distribution.
+.\"
+.\" THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS
+.\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+.\" LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+.\" A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OPENBSD
+.\" PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+.\" SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+.\" LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+.\" DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+.\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+.\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+.\" OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+.\"
+.Dd November 3, 1999
+.Dt OPEN_HASH 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
+.Fd #include <sys/types.h>
+.Fd #include <stddef.h>
+.Fd #include <ohash.h>
+.Ft void
+.Fn ohash_init "struct ohash *h" "unsigned int size" "struct ohash_info *info"
+.Ft void
+.Fn ohash_delete "struct oohash *h"
+.Ft "unsigned int"
+.Fn ohash_lookup_interval "struct ohash *h" "const char *start" "const char *end" "u_int32_t hv"
+.Ft "unsigned int"
+.Fn ohash_lookup_memory "struct ohash *h" "const char *k" "size_t s" "u_int32_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
+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 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
+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 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 ohash should contain
+null-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
+.Va 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 element of ohash 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 ohash_first
+and
+.Fn ohash_next
+can be used to access all elements in a ohash table, like this:
+.Pp
+.Bd -literal
+	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 ohash 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.
+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 ohash_init
+returns a useless ohash 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 ohashing 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 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
+.Rs
+.%A Donald E. Knuth
+.%B The Art of Computer Programming
+.%V Vol. 3
+.%P pp 506-550
+.%D 1973
+.Re
+.Xr ohash_interval 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
+make
+by Marc Espie in 1999.
diff --git a/lib/libc/ohash/ohash_init.c b/lib/libc/ohash/ohash_init.c
new file mode 100644
index 00000000000..b563525e97f
--- /dev/null
+++ b/lib/libc/ohash/ohash_init.c
@@ -0,0 +1,58 @@
+/* $OpenBSD: ohash_init.c,v 1.1 2001/03/02 13:27:07 espie Exp $ */
+/* ex:ts=8 sw=4: 
+ */
+
+/*
+ * Copyright (c) 1999 Marc Espie.
+ *
+ * Code written for the OpenBSD project.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OPENBSD
+ * PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+
+#include "ohash_int.h"
+
+void 
+ohash_init(h, size, info)
+	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.halloc = info->halloc;
+	h->info.hfree = info->hfree;
+	h->info.alloc = info->alloc;
+	h->info.data = info->data;
+	h->t = (h->info.halloc)(sizeof(struct _ohash_record) * h->size,
+	    h->info.data);
+	h->total = h->deleted = 0;
+}
+
diff --git a/lib/libc/ohash/ohash_int.h b/lib/libc/ohash/ohash_int.h
new file mode 100644
index 00000000000..5984e024bb6
--- /dev/null
+++ b/lib/libc/ohash/ohash_int.h
@@ -0,0 +1,20 @@
+/*	$OpenBSD: ohash_int.h,v 1.1 2001/03/02 13:27:07 espie Exp $	*/
+
+#include <sys/types.h>
+#include <stddef.h>
+#include <stdlib.h>
+#include <string.h>
+#include "ohash.h"
+
+struct _ohash_record {
+	u_int32_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
+
diff --git a/lib/libc/ohash/ohash_interval.3 b/lib/libc/ohash/ohash_interval.3
new file mode 100644
index 00000000000..97de05de98b
--- /dev/null
+++ b/lib/libc/ohash/ohash_interval.3
@@ -0,0 +1,98 @@
+.\"	$OpenBSD: ohash_interval.3,v 1.1 2001/03/02 13:27:07 espie Exp $
+.\"
+.\" Copyright (c) 2001 Marc Espie.
+.\"
+.\" Code written for the OpenBSD project.
+.\"
+.\" Redistribution and use in source and binary forms, with or without
+.\" modification, are permitted provided that the following conditions
+.\" are met:
+.\" 1. Redistributions of source code must retain the above copyright
+.\"    notice, this list of conditions and the following disclaimer.
+.\" 2. Redistributions in binary form must reproduce the above copyright
+.\"    notice, this list of conditions and the following disclaimer in the
+.\"    documentation and/or other materials provided with the distribution.
+.\"
+.\" THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS
+.\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+.\" LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+.\" A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OPENBSD
+.\" PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+.\" SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+.\" LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+.\" DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+.\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+.\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+.\" OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+.\"
+.Dd February 23, 2001
+.Dt OPEN_HASH_HELPER 3
+.Nm ohash_interval ,
+.Nm ohash_create_entry ,
+.Nm ohash_qlookup ,
+.Nm ohash_qlookupi
+.Nm helper functions for open hashing
+.Sh SYNOPSIS
+.Fd #include <sys/types.h>
+.Fd #include <stddef.h>
+.Fd #include <ohash.h>
+.Ft u_int32_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 null-terminated strings
+.Po
+by setting
+.Fa *pend
+=
+.Dv NULL
+.Pc
+or memory ranges
+.Po
+deliminated by
+.Fa start
+and
+.Fa *pend
+.Pc .
+For null-terminated strings, as a side effect, those functions
+set
+.Fa *pend
+to the terminating null byte.
+.Pp
+.Fn ohash_interval
+is a simple hashing function that yields good results on many 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
+-like function to allocate the storage.
+.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 null-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
+make
+by Marc Espie in 1999.
diff --git a/lib/libc/ohash/ohash_interval.c b/lib/libc/ohash/ohash_interval.c
new file mode 100644
index 00000000000..1c907f576a6
--- /dev/null
+++ b/lib/libc/ohash/ohash_interval.c
@@ -0,0 +1,50 @@
+/* $OpenBSD: ohash_interval.c,v 1.1 2001/03/02 13:27:07 espie Exp $ */
+/* ex:ts=8 sw=4: 
+ */
+
+/*
+ * Copyright (c) 1999 Marc Espie.
+ *
+ * Code written for the OpenBSD project.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OPENBSD
+ * PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "ohash_int.h"
+
+u_int32_t
+ohash_interval(s, e)
+	const char *s;
+	const char **e;
+{
+	u_int32_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;
+}
diff --git a/lib/libc/ohash/ohash_lookup_interval.c b/lib/libc/ohash/ohash_lookup_interval.c
new file mode 100644
index 00000000000..0eaf9643005
--- /dev/null
+++ b/lib/libc/ohash/ohash_lookup_interval.c
@@ -0,0 +1,84 @@
+/* $OpenBSD: ohash_lookup_interval.c,v 1.1 2001/03/02 13:27:07 espie Exp $ */
+/* ex:ts=8 sw=4: 
+ */
+
+/*
+ * Copyright (c) 1999 Marc Espie.
+ *
+ * Code written for the OpenBSD project.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OPENBSD
+ * PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "ohash_int.h"
+	
+unsigned int
+ohash_lookup_interval(h, start, end, hv)
+	struct ohash 	*h;
+	const char 	*start;
+	const char 	*end;
+	u_int32_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;
+}
+	
diff --git a/lib/libc/ohash/ohash_lookup_memory.c b/lib/libc/ohash/ohash_lookup_memory.c
new file mode 100644
index 00000000000..eb4ab16eed1
--- /dev/null
+++ b/lib/libc/ohash/ohash_lookup_memory.c
@@ -0,0 +1,81 @@
+/* $OpenBSD: ohash_lookup_memory.c,v 1.1 2001/03/02 13:27:08 espie Exp $ */
+/* ex:ts=8 sw=4: 
+ */
+
+/*
+ * Copyright (c) 1999 Marc Espie.
+ *
+ * Code written for the OpenBSD project.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OPENBSD
+ * PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "ohash_int.h"
+
+unsigned int
+ohash_lookup_memory(h, k, size, hv)
+	struct ohash 	*h;
+	const char 	*k;
+	size_t		size;
+	u_int32_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;
+}
+
diff --git a/lib/libc/ohash/ohash_qlookup.c b/lib/libc/ohash/ohash_qlookup.c
new file mode 100644
index 00000000000..89f0318221a
--- /dev/null
+++ b/lib/libc/ohash/ohash_qlookup.c
@@ -0,0 +1,42 @@
+/* $OpenBSD: ohash_qlookup.c,v 1.1 2001/03/02 13:27:08 espie Exp $ */
+/* ex:ts=8 sw=4: 
+ */
+
+/*
+ * Copyright (c) 1999 Marc Espie.
+ *
+ * Code written for the OpenBSD project.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OPENBSD
+ * PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "ohash_int.h"
+
+unsigned int
+ohash_qlookup(h, s)
+	struct ohash *h;
+	const char *s;
+{
+	const char *e = NULL;
+	return ohash_qlookupi(h, s, &e);
+}
+
diff --git a/lib/libc/ohash/ohash_qlookupi.c b/lib/libc/ohash/ohash_qlookupi.c
new file mode 100644
index 00000000000..1b1e6383257
--- /dev/null
+++ b/lib/libc/ohash/ohash_qlookupi.c
@@ -0,0 +1,44 @@
+/* $OpenBSD: ohash_qlookupi.c,v 1.1 2001/03/02 13:27:08 espie Exp $ */
+/* ex:ts=8 sw=4: 
+ */
+
+/*
+ * Copyright (c) 1999 Marc Espie.
+ *
+ * Code written for the OpenBSD project.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OPENBSD
+ * PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "ohash_int.h"
+
+unsigned int
+ohash_qlookupi(h, s, e)
+	struct ohash *h;
+	const char *s;
+	const char **e;
+{
+	u_int32_t hv;
+
+	hv = ohash_interval(s, e);
+	return ohash_lookup_interval(h, s, *e, hv);
+}
diff --git a/lib/libc/shlib_version b/lib/libc/shlib_version
index c622cb8cdf3..72168dfd16a 100644
--- a/lib/libc/shlib_version
+++ b/lib/libc/shlib_version
@@ -1,2 +1,2 @@
 major=26
-minor=0
+minor=1