Add hash(9) and hashinit(9).

1 files changed, 161 insertions, 0 deletions

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 .