1.\" Copyright (c) 2001 Tobias Weingartner 2.\" All rights reserved. 3.\" 4.\" Redistribution and use in source and binary forms, with or without 5.\" modification, are permitted provided that the following conditions 6.\" are met: 7.\" 1. Redistributions of source code must retain the above copyright 8.\" notice, this list of conditions and the following disclaimer. 9.\" 2. Redistributions in binary form must reproduce the above copyright 10.\" notice, this list of conditions and the following disclaimer in the 11.\" documentation and/or other materials provided with the distribution. 12.\" 3. The name of the author may not be used to endorse or promote products 13.\" derived from this software without specific prior written permission. 14.\" 15.\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 16.\" IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 17.\" OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 18.\" IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 19.\" INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 20.\" NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 21.\" DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 22.\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 23.\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 24.\" THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 25.\" 26.\" $OpenBSD: hash.9,v 1.5 2003/04/17 05:08:39 jmc Exp $ 27.\" $FreeBSD$ 28.\" 29.Dd December 8, 2001 30.Dt HASH 9 31.Os 32.Sh NAME 33.Nm hash 34.\" XXX - Should all these be .Nm as well? 35.\" .Nm hash32 , 36.\" .Nm hash32_buf , 37.\" .Nm hash32_str , 38.\" .Nm hash32_strn , 39.\" .Nm hash32_stre , 40.\" .Nm hash32_strne 41.Nd general kernel hashing functions 42.Sh SYNOPSIS 43.Fd #include <sys/hash.h> 44.Ft uint32_t 45.Fn hash32_buf "void *buf" "size_t len" "uint32_t hash" 46.Ft uint32_t 47.Fn hash32_str "void *buf" "uint32_t hash" 48.Ft uint32_t 49.Fn hash32_strn "void *buf" "size_t len" "uint32_t hash" 50.Ft uint32_t 51.Fn hash32_stre "void *buf" "int end" "char **ep" "uint32_t hash" 52.Ft uint32_t 53.Fn hash32_strne "void *buf" "size_t len" "int end" "char **ep" "uint32_t hash" 54.Sh DESCRIPTION 55The 56.Fn hash32 57functions are used to give a consistent and general interface to 58a decent hashing algorithm within the kernel. 59These functions can be used to hash ASCII 60.Dv NUL 61terminated strings, as well as blocks of memory. 62.Pp 63The 64.Fn hash32_buf 65function is used as a general buffer hashing function. 66The argument 67.Fa buf 68is used to pass in the location, and 69.Fa len 70is the length of the buffer. 71The argument 72.Fa hash 73is used to extend an existing hash, or is passed the initial value 74.Dv HASHINIT 75to start a new hash. 76.Pp 77The 78.Fn hash32_str 79function is used to hash a 80.Dv NUL 81terminated string passed in 82.Fa buf 83with initial hash value given in 84.Fa hash . 85.Pp 86The 87.Fn hash32_strn 88function is like the 89.Fn hash32_str 90function, except it also takes a 91.Fa len 92argument, which is the maximal length of the expected string. 93.Pp 94The 95.Fn hash32_stre 96and 97.Fn hash32_strne 98functions are helper functions used by the kernel to hash pathname 99components. 100These functions have the additional termination condition 101of terminating when they find a character given by 102.Fa end 103in the string to be hashed. 104If the argument 105.Fa ep 106is not 107.Dv NULL , 108it is set to the point in the buffer at which the hash function 109terminated hashing. 110.Sh RETURN VALUES 111The 112.Fn hash32 113functions return a 32 bit hash value of the buffer or string. 114.Sh EXAMPLES 115.Bd -literal -offset indent 116LIST_HEAD(head, cache) *hashtbl = NULL; 117u_long mask = 0; 118 119void 120sample_init(void) 121{ 122 hashtbl = hashinit(numwanted, type, flags, &mask); 123} 124 125void 126sample_use(char *str, int len) 127{ 128 uint32_t hash; 129 130 hash = hash32_str(str, HASHINIT); 131 hash = hash32_buf(&len, sizeof(len), hash); 132 hashtbl[hash & mask] = len; 133} 134.Ed 135.Sh SEE ALSO 136.Xr free 9 , 137.Xr hashinit 9 , 138.Xr malloc 9 139.Sh LIMITATIONS 140The 141.Fn hash32 142functions are only 32 bit functions. 143They will prove to give poor 64 bit performance, especially for the 144top 32 bits. 145At the current time, this is not seen as a great limitation, as these 146hash values are usually used to index into an array. 147Should these hash values be used for other means, this limitation should 148be revisited. 149.Sh HISTORY 150The 151.Nm 152functions were first committed to 153.Nx 1.6 . 154The 155.Ox 156versions were written and massaged for 157.Ox 2.3 158by Tobias Weingartner, 159and finally committed for 160.Ox 3.2 . 161