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: src/share/man/man9/hash.9,v 1.4 2007/04/09 22:55:14 thompsa Exp $
  28 .\"
  29 .Dd June 6, 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 .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
  54 The
  55 .Fn hash32
  56 functions are used to give a consistent and general interface to
  57 a decent hashing algorithm within the kernel.
  58 These functions can be used to hash
  59 .Tn ASCII
  60 .Dv NUL
  61 terminated strings, as well as blocks of memory.
  62 .Pp
  63 The
  64 .Fn hash32_buf
  65 function is used as a general buffer hashing function.
  66 The argument
  67 .Fa buf
  68 is used to pass in the location, and
  69 .Fa len
  70 is the length of the buffer.
  71 The argument
  72 .Fa hash
  73 is used to extend an existing hash, or is passed the initial value
  74 .Dv HASHINIT
  75 to start a new hash.
  76 .Pp
  77 The
  78 .Fn hash32_str
  79 function is used to hash a
  80 .Dv NUL
  81 terminated string passed in
  82 .Fa buf
  83 with initial hash value given in
  84 .Fa hash .
  85 .Pp
  86 The
  87 .Fn hash32_strn
  88 function is like the
  89 .Fn hash32_str
  90 function, except it also takes a
  91 .Fa len
  92 argument, which is the maximal length of the expected string.
  93 .Pp
  94 The
  95 .Fn hash32_stre
  96 and
  97 .Fn hash32_strne
  98 functions are helper functions used by the kernel to hash pathname
  99 components.
 100 These functions have the additional termination condition
 101 of terminating when they find a character given by
 102 .Fa end
 103 in the string to be hashed.
 104 If the argument
 105 .Fa ep
 106 is not
 107 .Dv NULL ,
 108 it is set to the point in the buffer at which the hash function
 109 terminated hashing.
 110 .Sh RETURN VALUES
 111 The
 112 .Fn hash32
 113 functions return a 32 bit hash value of the buffer or string.
 114 .Sh EXAMPLES
 115 .Bd -literal -offset indent
 116 LIST_HEAD(head, cache) *hashtbl = NULL;
 117 u_long mask = 0;
 118
 119 void
 120 sample_init(void)
 121 {
 122
 123         hashtbl = hashinit(numwanted, type, flags, &mask);
 124 }
 125
 126 void
 127 sample_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 hashinit 9 ,
 138 .Xr kfree 9 ,
 139 .Xr kmalloc 9
 140 .Sh LIMITATIONS
 141 The
 142 .Fn hash32
 143 functions are only 32 bit functions.
 144 They will prove to give poor 64 bit performance, especially for the
 145 top 32 bits.
 146 At the current time, this is not seen as a great limitation, as these
 147 hash values are usually used to index into an array.
 148 Should these hash values be used for other means, this limitation should
 149 be revisited.
 150 .Sh HISTORY
 151 The
 152 .Nm
 153 functions were first committed to
 154 .Nx 1.6 .
 155 The
 156 .Ox
 157 versions were written and massaged for
 158 .Ox 2.3
 159 by Tobias Weingartner,
 160 and finally committed for
 161 .Ox 3.2 .