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