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 April 3, 2007 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.Nd general kernel hashing functions 41.Sh SYNOPSIS 42.In sys/hash.h 43.Ft uint32_t 44.Fn hash32_buf "const void *buf" "size_t len" "uint32_t hash" 45.Ft uint32_t 46.Fn hash32_str "const void *buf" "uint32_t hash" 47.Ft uint32_t 48.Fn hash32_strn "const void *buf" "size_t len" "uint32_t hash" 49.Ft uint32_t 50.Fn hash32_stre "const void *buf" "int end" "const char **ep" "uint32_t hash" 51.Ft uint32_t 52.Fn hash32_strne "const void *buf" "size_t len" "int end" "const char **ep" "uint32_t hash" 53.Sh DESCRIPTION 54The 55.Fn hash32 56functions are used to give a consistent and general interface to 57a decent hashing algorithm within the kernel. 58These functions can be used to hash 59.Tn 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 123 hashtbl = hashinit(numwanted, type, flags, &mask); 124} 125 126void 127sample_use(char *str, int len) 128{ 129 uint32_t hash; 130 131 hash = hash32_str(str, HASHINIT); 132 hash = hash32_buf(&len, sizeof(len), hash); 133 hashtbl[hash & mask] = len; 134} 135.Ed 136.Sh SEE ALSO 137.Xr free 9 , 138.Xr hashinit 9 , 139.Xr malloc 9 140.Sh LIMITATIONS 141The 142.Fn hash32 143functions are only 32 bit functions. 144They will prove to give poor 64 bit performance, especially for the 145top 32 bits. 146At the current time, this is not seen as a great limitation, as these 147hash values are usually used to index into an array. 148Should these hash values be used for other means, this limitation should 149be revisited. 150.Sh HISTORY 151The 152.Nm 153functions were first committed to 154.Nx 1.6 . 155The 156.Ox 157versions were written and massaged for 158.Ox 2.3 159by Tobias Weingartner, 160and finally committed for 161.Ox 3.2 . 162