From a26da875753cb3febc7b98bd2f634e0adb3f048d Mon Sep 17 00:00:00 2001 From: Tobias Weingartner Date: Fri, 21 Jun 2002 07:40:15 +0000 Subject: Add hash(9) and hashinit(9). --- share/man/man9/hash.9 | 161 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 161 insertions(+) create mode 100644 share/man/man9/hash.9 (limited to 'share/man/man9/hash.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 +.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 . -- cgit v1.2.3