Add hash(9) and hashinit(9).

3 files changed, 245 insertions, 2 deletions

diff --git a/share/man/man9/Makefile b/share/man/man9/Makefile
index 0f45024006d..0f2fed8fb96 100644
--- a/share/man/man9/Makefile
+++ b/share/man/man9/Makefile
@@ -1,4 +1,4 @@
-#	$OpenBSD: Makefile,v 1.51 2002/06/12 02:39:28 provos Exp $
+#	$OpenBSD: Makefile,v 1.52 2002/06/21 07:40:14 weingart Exp $
 #	$NetBSD: Makefile,v 1.4 1996/01/09 03:23:01 thorpej Exp $
 
 #	Makefile for section 9 (kernel function and variable) manual pages.
@@ -7,7 +7,7 @@ MAN=	altq.9 audio.9 boot.9 bus_dma.9 bus_space.9 copy.9 crypto.9 ctxsw.9 \
 	disk.9 disklabel.9 \
 	dohooks.9 dopowerhooks.9 doshutdownhooks.9 dostartuphooks.9 \
 	extattr.9 \
-	fetch.9 fork1.9 extent.9 getdevvp.9 getnewvnode.9 \
+	fetch.9 fork1.9 extent.9 getdevvp.9 getnewvnode.9 hash.9 hashinit.9 \
 	hardclock.9 hook_establish.9 hz.9 hzto.9 intro.9 inittodr.9 log.9 \
 	kthread.9 lock.9 malloc.9 mbuf.9 mbuf_tags.9 md5.9 microtime.9 \
 	panic.9 pfind.9 physio.9 \
diff --git a/share/man/man9/hash.9 b/share/man/man9/hash.9
new file mode 100644
index 00000000000..35ee946990c
--- /dev/null
+++ b/share/man/man9/hash.9
@@ -0,0 +1,161 @@
+.\"	$OpenBSD: hash.9,v 1.1 2002/06/21 07:40:14 weingart Exp $
+.\"
+.\" Copyright (c) 2001 Tobias Weingartner
+.\" All rights reserved.
+.\"
+.\" 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.
+.\" 3. The name of the author may not be used to endorse or promote products
+.\"    derived from this software without specific prior written permission.
+.\"
+.\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 AUTHOR 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 December 8, 2001
+.Dt HASH 9
+.Os
+.Sh NAME
+.Nm hash
+.\" XXX - Should all these be .Nm as well?
+.\" .Nm hash32 ,
+.\" .Nm hash32_buf ,
+.\" .Nm hash32_str ,
+.\" .Nm hash32_strn ,
+.\" .Nm hash32_stre ,
+.\" .Nm hash32_strne
+.Nd general kernel hashing functions
+.Sh SYNOPSIS
+.Fd #include <sys/hash.h>
+.Ft uint32_t
+.Fn hash32_buf "void *buf" "size_t len" "uint32_t hash"
+.Ft uint32_t
+.Fn hash32_str "void *buf" "uint32_t hash"
+.Ft uint32_t
+.Fn hash32_strn "void *buf" "size_t len" "uint32_t hash"
+.Ft uint32_t
+.Fn hash32_stre "void *buf" "int end" "char **ep" "uint32_t hash"
+.Ft uint32_t
+.Fn hash32_strne "void *buf" "size_t len" "int end" "char **ep" "uint32_t hash"
+.Sh DESCRIPTION
+The
+.Fn hash32
+functions are used to give a consistent and general interface to
+a decent hashing algorithm within the kernel.
+These functions can be used to hash ASCII
+.Dv NUL
+terminated strings, as well as blocks of memory.
+.Pp
+The
+.Fn hash32_buf
+function is used as a general buffer hashing function.
+The argument
+.Fa buf
+is used to pass in the location, and
+.Fa len
+is the length of the buffer.
+The argument
+.Fa hash
+is used to extend an existing hash, or is passed the initial value
+.Dv HASHINIT
+to start a new hash.
+.Pp
+The
+.Fn hash32_str
+function is used to hash a
+.Dv NUL
+terminated string passed in
+.Fa buf
+with initial hash value given in
+.Fa hash .
+.Pp
+The
+.Fn hash32_strn
+function is like the
+.Fn hash32_str
+function, except it also takes a
+.Fa len
+argument, which is the maximal length of the expected string.
+.Pp
+The
+.Fn hash32_stre
+and
+.Fn hash32_strne
+functions are helper functions used by the kernel to hash pathname
+components.
+These functions have the additional termination condition
+of terminating when they find a character given by
+.Fa end
+in the string to be hashed.
+If the argument
+.Fa ep
+is not
+.Dv NULL ,
+it is set to the point in the buffer at which the hash function
+terminated hashing.
+.Sh RETURN VALUES
+The
+.Fn hash32
+functions return a 32 bit hash value of the buffer or string.
+.Sh EXAMPLES
+.Bd -literal -offset indent
+LIST_HEAD(head, cache) *hashtbl = NULL;
+u_long mask = 0;
+
+void
+sample_init(void)
+{
+	hashtbl = hashinit(numwanted, type, flags, &mask);
+}
+
+void
+sample_use(char *str, int len)
+{
+	uint32_t hash;
+
+	hash = hash32_str(str, HASHINIT);
+	hash = hash32_buf(&len, sizeof(len), hash);
+	hashtbl[hash & mask] = len;
+}
+.Ed
+.Pp
+.Sh SEE ALSO
+.\" Not written yet, comming I hope
+.Xr hashinit 9 ,
+.Xr malloc 9 ,
+.Xr free 9
+.Sh LIMITATIONS
+The
+.Fn hash32
+functions are only 32 bit functions.
+They will prove to give poor 64 bit performance, especially for the
+top 32 bits.
+At the current time, this is not seen as a great limitation, as these
+hash values are usually used to index into an array.
+Should these hash values be used for other means, this limitation should
+be revisited.
+.Sh HISTORY
+The
+.Nm
+functions were first commited to
+.Nx 1.6 .
+The
+.Ox
+versions were written and massaged for
+.Ox 2.3
+by Tobias Weingartner,
+and finally commited for
+.Ox 3.2 .
diff --git a/share/man/man9/hashinit.9 b/share/man/man9/hashinit.9
new file mode 100644
index 00000000000..e0987865197
--- /dev/null
+++ b/share/man/man9/hashinit.9
@@ -0,0 +1,82 @@
+.\"	$OpenBSD: hashinit.9,v 1.1 2002/06/21 07:40:14 weingart Exp $
+.\"
+.\" Copyright (c) 2001 Tobias Weingartner
+.\" All rights reserved.
+.\"
+.\" 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.
+.\" 3. The name of the author may not be used to endorse or promote products
+.\"    derived from this software without specific prior written permission.
+.\"
+.\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 AUTHOR 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 December 8, 2001
+.Dt HASHINIT 9
+.Os
+.Sh NAME
+.Nm hashinit
+.\" This should be ported from netbsd as well...
+.\" .Nm hashdone
+.Nd kernel hashtable functions
+.Sh SYNOPSIS
+.Fd #include <sys/systm.h>
+.Ft void *
+.Fn hashinit "int num" "int type" "int flags" "u_long *mask"
+.Sh DESCRIPTION
+The
+.Fn hashinit
+function is used to allocate a hashtable of a desired size given by the
+.Fa num
+argument.
+The
+.Fn hashinit
+function will round this number to the next power of two, and
+allocate and initialize the requested hashtable.
+The
+.Fa type
+and
+.Fa flags
+arguments are passed to the
+.Xr malloc 9
+function unchanged.
+The
+.Fa mask
+argument is used to pass back the mask for use with the allocated
+hashing table.
+For an example of its use, see
+.Xr hash 9 .
+.Sh RETURN VALUES
+The
+.Fn hashinit
+function returns a pointer to the allocated and initialized hash table.
+.Sh SEE ALSO
+.Xr hash 9 ,
+.Xr malloc 9 ,
+.Xr free 9
+.Sh LIMITATIONS
+The
+.Fn hashinit
+function currently only allocates hash tables with LIST bucket pointers
+at this time.
+Future enhancements to allocate QUEUE bucket pointers may be warranted.
+This may necessitate an API change to accommodate.
+.Sh HISTORY
+The
+.Nm
+function first appeared in
+.Bx 4.4 .