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 September 4, 2012 30.Dt HASH 9 31.Os 32.Sh NAME 33.Nm hash , 34.Nm hash32 , 35.Nm hash32_buf , 36.Nm hash32_str , 37.Nm hash32_strn , 38.Nm hash32_stre , 39.Nm hash32_strne , 40.Nm jenkins_hash32 , 41.Nm jenkins_hash 42.Nd general kernel hashing functions 43.Sh SYNOPSIS 44.In sys/hash.h 45.Ft uint32_t 46.Fn hash32_buf "const void *buf" "size_t len" "uint32_t hash" 47.Ft uint32_t 48.Fn hash32_str "const void *buf" "uint32_t hash" 49.Ft uint32_t 50.Fn hash32_strn "const void *buf" "size_t len" "uint32_t hash" 51.Ft uint32_t 52.Fn hash32_stre "const void *buf" "int end" "const char **ep" "uint32_t hash" 53.Ft uint32_t 54.Fn hash32_strne "const void *buf" "size_t len" "int end" "const char **ep" "uint32_t hash" 55.Ft uint32_t 56.Fn jenkins_hash "const void *buf" "size_t len" "uint32_t hash" 57.Ft uint32_t 58.Fn jenkins_hash32 "const uint32_t *buf" "size_t count" "uint32_t hash" 59.Sh DESCRIPTION 60The 61.Fn hash32 62functions are used to give a consistent and general interface to 63a decent hashing algorithm within the kernel. 64These functions can be used to hash 65.Tn ASCII 66.Dv NUL 67terminated strings, as well as blocks of memory. 68.Pp 69The 70.Fn hash32_buf 71function is used as a general buffer hashing function. 72The argument 73.Fa buf 74is used to pass in the location, and 75.Fa len 76is the length of the buffer. 77The argument 78.Fa hash 79is used to extend an existing hash, or is passed the initial value 80.Dv HASHINIT 81to start a new hash. 82.Pp 83The 84.Fn hash32_str 85function is used to hash a 86.Dv NUL 87terminated string passed in 88.Fa buf 89with initial hash value given in 90.Fa hash . 91.Pp 92The 93.Fn hash32_strn 94function is like the 95.Fn hash32_str 96function, except it also takes a 97.Fa len 98argument, which is the maximal length of the expected string. 99.Pp 100The 101.Fn hash32_stre 102and 103.Fn hash32_strne 104functions are helper functions used by the kernel to hash pathname 105components. 106These functions have the additional termination condition 107of terminating when they find a character given by 108.Fa end 109in the string to be hashed. 110If the argument 111.Fa ep 112is not 113.Dv NULL , 114it is set to the point in the buffer at which the hash function 115terminated hashing. 116.Pp 117The 118.Fn jenkins_hash 119function has same semantics as the 120.Fn hash32_buf , 121but provides more advanced hashing algorithm with better distribution. 122.Pp 123The 124.Fn jenkins_hash32 125uses same hashing algorithm as the 126.Fn jenkins_hash 127function, but works only on 128.Ft uint32_t 129sized arrays, thus is simplier and faster. 130It accepts an array of 131.Ft uint32_t 132values in its first argument and size of this array in the second argument. 133.Sh RETURN VALUES 134The 135.Fn hash32 136functions return a 32 bit hash value of the buffer or string. 137.Sh EXAMPLES 138.Bd -literal -offset indent 139LIST_HEAD(head, cache) *hashtbl = NULL; 140u_long mask = 0; 141 142void 143sample_init(void) 144{ 145 146 hashtbl = hashinit(numwanted, type, flags, &mask); 147} 148 149void 150sample_use(char *str, int len) 151{ 152 uint32_t hash; 153 154 hash = hash32_str(str, HASHINIT); 155 hash = hash32_buf(&len, sizeof(len), hash); 156 hashtbl[hash & mask] = len; 157} 158.Ed 159.Sh SEE ALSO 160.Xr free 9 , 161.Xr hashinit 9 , 162.Xr malloc 9 163.Sh LIMITATIONS 164The 165.Fn hash32 166functions are only 32 bit functions. 167They will prove to give poor 64 bit performance, especially for the 168top 32 bits. 169At the current time, this is not seen as a great limitation, as these 170hash values are usually used to index into an array. 171Should these hash values be used for other means, this limitation should 172be revisited. 173.Sh HISTORY 174The 175.Nm 176functions first appeared in 177.Nx 1.6 . 178The current implementation of 179.Nm hash32 180functions was first committed to 181.Ox 3.2 , 182and later imported to 183.Fx 6.1 . 184The 185.Nm jenkins_hash 186functions were added in 187.Fx 10.0 . 188.Sh AUTHORS 189The 190.Nm hash32 191functions were written by 192.An Tobias Weingartner . 193The 194.Nm jenkins_hash 195functions was written by 196Bob Jenkins . 197