xref: /dragonfly/share/man/man9/hash.9 (revision 67640b13) 
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
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 hashinit 9 ,
138.Xr kfree 9 ,
139.Xr kmalloc 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