share/man/man9/hash.9

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