1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
|
<table class="head">
<tr>
<td class="head-ltitle">HASH(9)</td>
<td class="head-vol">Kernel Developer's Manual</td>
<td class="head-rtitle">HASH(9)</td>
</tr>
</table>
<div class="manual-text">
<section class="Sh">
<h1 class="Sh" id="NAME"><a class="permalink" href="#NAME">NAME</a></h1>
<p class="Pp"><code class="Nm">hash</code>, <code class="Nm">hash32</code>,
<code class="Nm">hash32_buf</code>, <code class="Nm">hash32_str</code>,
<code class="Nm">hash32_strn</code>, <code class="Nm">hash32_stre</code>,
<code class="Nm">hash32_strne</code>, <code class="Nm">jenkins_hash</code>,
<code class="Nm">jenkins_hash32</code>,
<code class="Nm">murmur3_32_hash</code>,
<code class="Nm">murmur3_32_hash32</code> — <span class="Nd">general
kernel hashing functions</span></p>
</section>
<section class="Sh">
<h1 class="Sh" id="SYNOPSIS"><a class="permalink" href="#SYNOPSIS">SYNOPSIS</a></h1>
<p class="Pp"><code class="In">#include
<<a class="In">sys/hash.h</a>></code></p>
<p class="Pp"><var class="Ft">uint32_t</var>
<br/>
<code class="Fn">hash32_buf</code>(<var class="Fa" style="white-space: nowrap;">const
void *buf</var>, <var class="Fa" style="white-space: nowrap;">size_t
len</var>, <var class="Fa" style="white-space: nowrap;">uint32_t
hash</var>);</p>
<p class="Pp"><var class="Ft">uint32_t</var>
<br/>
<code class="Fn">hash32_str</code>(<var class="Fa" style="white-space: nowrap;">const
void *buf</var>, <var class="Fa" style="white-space: nowrap;">uint32_t
hash</var>);</p>
<p class="Pp"><var class="Ft">uint32_t</var>
<br/>
<code class="Fn">hash32_strn</code>(<var class="Fa" style="white-space: nowrap;">const
void *buf</var>, <var class="Fa" style="white-space: nowrap;">size_t
len</var>, <var class="Fa" style="white-space: nowrap;">uint32_t
hash</var>);</p>
<p class="Pp"><var class="Ft">uint32_t</var>
<br/>
<code class="Fn">hash32_stre</code>(<var class="Fa" style="white-space: nowrap;">const
void *buf</var>, <var class="Fa" style="white-space: nowrap;">int end</var>,
<var class="Fa" style="white-space: nowrap;">const char **ep</var>,
<var class="Fa" style="white-space: nowrap;">uint32_t hash</var>);</p>
<p class="Pp"><var class="Ft">uint32_t</var>
<br/>
<code class="Fn">hash32_strne</code>(<var class="Fa" style="white-space: nowrap;">const
void *buf</var>, <var class="Fa" style="white-space: nowrap;">size_t
len</var>, <var class="Fa" style="white-space: nowrap;">int end</var>,
<var class="Fa" style="white-space: nowrap;">const char **ep</var>,
<var class="Fa" style="white-space: nowrap;">uint32_t hash</var>);</p>
<p class="Pp"><var class="Ft">uint32_t</var>
<br/>
<code class="Fn">jenkins_hash</code>(<var class="Fa" style="white-space: nowrap;">const
void *buf</var>, <var class="Fa" style="white-space: nowrap;">size_t
len</var>, <var class="Fa" style="white-space: nowrap;">uint32_t
hash</var>);</p>
<p class="Pp"><var class="Ft">uint32_t</var>
<br/>
<code class="Fn">jenkins_hash32</code>(<var class="Fa" style="white-space: nowrap;">const
uint32_t *buf</var>, <var class="Fa" style="white-space: nowrap;">size_t
count</var>, <var class="Fa" style="white-space: nowrap;">uint32_t
hash</var>);</p>
<p class="Pp"><var class="Ft">uint32_t</var>
<br/>
<code class="Fn">murmur3_32_hash</code>(<var class="Fa" style="white-space: nowrap;">const
void *buf</var>, <var class="Fa" style="white-space: nowrap;">size_t
len</var>, <var class="Fa" style="white-space: nowrap;">uint32_t
hash</var>);</p>
<p class="Pp"><var class="Ft">uint32_t</var>
<br/>
<code class="Fn">murmur3_32_hash32</code>(<var class="Fa" style="white-space: nowrap;">const
uint32_t *buf</var>, <var class="Fa" style="white-space: nowrap;">size_t
count</var>, <var class="Fa" style="white-space: nowrap;">uint32_t
hash</var>);</p>
</section>
<section class="Sh">
<h1 class="Sh" id="DESCRIPTION"><a class="permalink" href="#DESCRIPTION">DESCRIPTION</a></h1>
<p class="Pp">The
<a class="permalink" href="#hash32"><code class="Fn" id="hash32">hash32</code></a>()
functions are used to give a consistent and general interface to a decent
hashing algorithm within the kernel. These functions can be used to hash
ASCII <code class="Dv">NUL</code> terminated strings, as well as blocks of
memory.</p>
<p class="Pp">A <var class="Fa">len</var> argument is the length of the buffer
in bytes. A <var class="Fa">count</var> argument is the length of the buffer
in 32-bit words.</p>
<p class="Pp" id="hash32_buf">The
<a class="permalink" href="#hash32_buf"><code class="Fn">hash32_buf</code></a>()
function is used as a general buffer hashing function. The argument
<var class="Fa">buf</var> is used to pass in the location, and
<var class="Fa">len</var> is the length of the buffer in bytes. The argument
<var class="Fa">hash</var> is used to extend an existing hash, or is passed
the initial value <code class="Dv">HASHINIT</code> to start a new hash.</p>
<p class="Pp" id="hash32_str">The
<a class="permalink" href="#hash32_str"><code class="Fn">hash32_str</code></a>()
function is used to hash a <code class="Dv">NUL</code> terminated string
passed in <var class="Fa">buf</var> with initial hash value given in
<var class="Fa">hash</var>.</p>
<p class="Pp" id="hash32_strn">The
<a class="permalink" href="#hash32_strn"><code class="Fn">hash32_strn</code></a>()
function is like the <code class="Fn">hash32_str</code>() function, except
it also takes a <var class="Fa">len</var> argument, which is the maximal
length of the expected string.</p>
<p class="Pp" id="hash32_stre">The
<a class="permalink" href="#hash32_stre"><code class="Fn">hash32_stre</code></a>()
and
<a class="permalink" href="#hash32_strne"><code class="Fn" id="hash32_strne">hash32_strne</code></a>()
functions are helper functions used by the kernel to hash pathname
components. These functions have the additional termination condition of
terminating when they find a character given by <var class="Fa">end</var> in
the string to be hashed. If the argument <var class="Fa">ep</var> is not
<code class="Dv">NULL</code>, it is set to the point in the buffer at which
the hash function terminated hashing.</p>
<p class="Pp" id="jenkins_hash">The
<a class="permalink" href="#jenkins_hash"><code class="Fn">jenkins_hash</code></a>()
function has same semantics as the <code class="Fn">hash32_buf</code>(), but
provides more advanced hashing algorithm with better distribution.</p>
<p class="Pp" id="jenkins_hash32">The
<a class="permalink" href="#jenkins_hash32"><code class="Fn">jenkins_hash32</code></a>()
uses same hashing algorithm as the <code class="Fn">jenkins_hash</code>()
function, but works only on <var class="Ft">uint32_t</var> sized arrays,
thus is simpler and faster. It accepts an array of
<var class="Ft">uint32_t</var> values in its first argument and size of this
array in the second argument.</p>
<p class="Pp" id="murmur3_32_hash">The
<a class="permalink" href="#murmur3_32_hash"><code class="Fn">murmur3_32_hash</code></a>()
and
<a class="permalink" href="#murmur3_32_hash32"><code class="Fn" id="murmur3_32_hash32">murmur3_32_hash32</code></a>()
functions are similar to <code class="Fn">jenkins_hash</code>() and
<code class="Fn">jenkins_hash32</code>(), but implement the 32-bit version
of MurmurHash3.</p>
</section>
<section class="Sh">
<h1 class="Sh" id="RETURN_VALUES"><a class="permalink" href="#RETURN_VALUES">RETURN
VALUES</a></h1>
<p class="Pp">The <code class="Fn">hash32</code>() functions return a 32 bit
hash value of the buffer or string.</p>
</section>
<section class="Sh">
<h1 class="Sh" id="EXAMPLES"><a class="permalink" href="#EXAMPLES">EXAMPLES</a></h1>
<div class="Bd Bd-indent Li">
<pre>LIST_HEAD(head, cache) *hashtbl = NULL;
u_long mask = 0;
void
sample_init(void)
{
hashtbl = hashinit(numwanted, type, flags, &mask);
}
void
sample_use(char *str, int len)
{
uint32_t hash;
hash = hash32_str(str, HASHINIT);
hash = hash32_buf(&len, sizeof(len), hash);
hashtbl[hash & mask] = len;
}</pre>
</div>
</section>
<section class="Sh">
<h1 class="Sh" id="SEE_ALSO"><a class="permalink" href="#SEE_ALSO">SEE
ALSO</a></h1>
<p class="Pp"><a class="Xr">free(9)</a>, <a class="Xr">hashinit(9)</a>,
<a class="Xr">malloc(9)</a></p>
</section>
<section class="Sh">
<h1 class="Sh" id="LIMITATIONS"><a class="permalink" href="#LIMITATIONS">LIMITATIONS</a></h1>
<p class="Pp">The <code class="Fn">hash32</code>() functions are only 32 bit
functions. They will prove to give poor 64 bit performance, especially for
the top 32 bits. At the current time, this is not seen as a great
limitation, as these hash values are usually used to index into an array.
Should these hash values be used for other means, this limitation should be
revisited.</p>
</section>
<section class="Sh">
<h1 class="Sh" id="HISTORY"><a class="permalink" href="#HISTORY">HISTORY</a></h1>
<p class="Pp">The <code class="Nm">hash</code> functions first appeared in
<span class="Ux">NetBSD 1.6</span>. The current implementation of
<code class="Nm">hash32</code> functions was first committed to
<span class="Ux">OpenBSD 3.2</span>, and later imported to
<span class="Ux">FreeBSD 6.1</span>. The
<code class="Nm">jenkins_hash</code> functions were added in
<span class="Ux">FreeBSD 10.0</span>. The
<code class="Nm">murmur3_32_hash</code> functions were added in
<span class="Ux">FreeBSD 10.1</span>.</p>
</section>
<section class="Sh">
<h1 class="Sh" id="AUTHORS"><a class="permalink" href="#AUTHORS">AUTHORS</a></h1>
<p class="Pp">The <code class="Nm">hash32</code> functions were written by
<span class="An">Tobias Weingartner</span>. The
<code class="Nm">jenkins_hash</code> functions were written by
<br/>
<span class="An">Bob Jenkins</span>. The
<code class="Nm">murmur3_32_hash</code> functions were written by
<br/>
<span class="An">Dag-Erling Smørgrav</span>
<<a class="Mt" href="mailto:des@FreeBSD.org">des@FreeBSD.org</a>>.</p>
</section>
</div>
<table class="foot">
<tr>
<td class="foot-date">June 30, 2015</td>
<td class="foot-os">FreeBSD 15.0</td>
</tr>
</table>
|
