1 /*-
2 * See the file LICENSE for redistribution information.
3 *
4 * Copyright (c) 1996, 1997
5 * Sleepycat Software. All rights reserved.
6 */
7 /*
8 * Copyright (c) 1990, 1993
9 * Margo Seltzer. All rights reserved.
10 */
11 /*
12 * Copyright (c) 1990, 1993
13 * The Regents of the University of California. All rights reserved.
14 *
15 * This code is derived from software contributed to Berkeley by
16 * Margo Seltzer.
17 *
18 * Redistribution and use in source and binary forms, with or without
19 * modification, are permitted provided that the following conditions
20 * are met:
21 * 1. Redistributions of source code must retain the above copyright
22 * notice, this list of conditions and the following disclaimer.
23 * 2. Redistributions in binary form must reproduce the above copyright
24 * notice, this list of conditions and the following disclaimer in the
25 * documentation and/or other materials provided with the distribution.
26 * 3. All advertising materials mentioning features or use of this software
27 * must display the following acknowledgement:
28 * This product includes software developed by the University of
29 * California, Berkeley and its contributors.
30 * 4. Neither the name of the University nor the names of its contributors
31 * may be used to endorse or promote products derived from this software
32 * without specific prior written permission.
33 *
34 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
35 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
36 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
37 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
38 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
39 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
40 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
41 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
42 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
43 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
44 * SUCH DAMAGE.
45 */
46 /*
47 * Copyright (c) 1998 by Sun Microsystems, Inc.
48 * All rights reserved.
49 */
50
51 #include "config.h"
52
53 #pragma ident "%Z%%M% %I% %E% SMI"
54
55 #ifndef lint
56 static const char sccsid[] = "@(#)hash_func.c 10.7 (Sleepycat) 9/16/97";
57 static const char sccsi2[] = "%W% (Sun) %G%";
58 #endif /* not lint */
59
60 #ifndef NO_SYSTEM_INCLUDES
61 #include <sys/types.h>
62 #endif
63
64 #include "db_int.h"
65 #include "db_page.h"
66 #include "hash.h"
67
68 /*
69 * __ham_func2 --
70 * Phong Vo's linear congruential hash.
71 *
72 * PUBLIC: u_int32_t __ham_func2 __P((const void *, u_int32_t));
73 */
74 #define DCHARHASH(h, c) ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c))
75
76 u_int32_t
__ham_func2(key,len)77 __ham_func2(key, len)
78 const void *key;
79 u_int32_t len;
80 {
81 const u_int8_t *e, *k;
82 u_int32_t h;
83 u_int8_t c;
84
85 k = key;
86 e = k + len;
87 for (h = 0; k != e;) {
88 c = *k++;
89 if (!c && k > e)
90 break;
91 DCHARHASH(h, c);
92 }
93 return (h);
94 }
95
96 /*
97 * __ham_func3 --
98 * Ozan Yigit's original sdbm hash.
99 *
100 * Ugly, but fast. Break the string up into 8 byte units. On the first time
101 * through the loop get the "leftover bytes" (strlen % 8). On every other
102 * iteration, perform 8 HASHC's so we handle all 8 bytes. Essentially, this
103 * saves us 7 cmp & branch instructions.
104 *
105 * PUBLIC: u_int32_t __ham_func3 __P((const void *, u_int32_t));
106 */
107 u_int32_t
__ham_func3(key,len)108 __ham_func3(key, len)
109 const void *key;
110 u_int32_t len;
111 {
112 const u_int8_t *k;
113 u_int32_t n, loop;
114
115 if (len == 0)
116 return (0);
117
118 #define HASHC n = *k++ + 65599 * n
119 n = 0;
120 k = key;
121
122 loop = (len + 8 - 1) >> 3;
123 switch (len & (8 - 1)) {
124 case 0:
125 do {
126 HASHC;
127 case 7:
128 HASHC;
129 case 6:
130 HASHC;
131 case 5:
132 HASHC;
133 case 4:
134 HASHC;
135 case 3:
136 HASHC;
137 case 2:
138 HASHC;
139 case 1:
140 HASHC;
141 } while (--loop);
142 }
143 return (n);
144 }
145
146 /*
147 * __ham_func4 --
148 * Chris Torek's hash function. Although this function performs only
149 * slightly worse than __ham_func5 on strings, it performs horribly on
150 * numbers.
151 *
152 * PUBLIC: u_int32_t __ham_func4 __P((const void *, u_int32_t));
153 */
154 u_int32_t
__ham_func4(key,len)155 __ham_func4(key, len)
156 const void *key;
157 u_int32_t len;
158 {
159 const u_int8_t *k;
160 u_int32_t h, loop;
161
162 if (len == 0)
163 return (0);
164
165 #define HASH4a h = (h << 5) - h + *k++;
166 #define HASH4b h = (h << 5) + h + *k++;
167 #define HASH4 HASH4b
168 h = 0;
169 k = key;
170
171 loop = (len + 8 - 1) >> 3;
172 switch (len & (8 - 1)) {
173 case 0:
174 do {
175 HASH4;
176 case 7:
177 HASH4;
178 case 6:
179 HASH4;
180 case 5:
181 HASH4;
182 case 4:
183 HASH4;
184 case 3:
185 HASH4;
186 case 2:
187 HASH4;
188 case 1:
189 HASH4;
190 } while (--loop);
191 }
192 return (h);
193 }
194
195 /*
196 * Fowler/Noll/Vo hash
197 *
198 * The basis of the hash algorithm was taken from an idea sent by email to the
199 * IEEE Posix P1003.2 mailing list from Phong Vo (kpv@research.att.com) and
200 * Glenn Fowler (gsf@research.att.com). Landon Curt Noll (chongo@toad.com)
201 * later improved on their algorithm.
202 *
203 * The magic is in the interesting relationship between the special prime
204 * 16777619 (2^24 + 403) and 2^32 and 2^8.
205 *
206 * This hash produces the fewest collisions of any function that we've seen so
207 * far, and works well on both numbers and strings.
208 *
209 * PUBLIC: u_int32_t __ham_func5 __P((const void *, u_int32_t));
210 */
211 u_int32_t
__ham_func5(key,len)212 __ham_func5(key, len)
213 const void *key;
214 u_int32_t len;
215 {
216 const u_int8_t *k, *e;
217 u_int32_t h;
218
219 k = key;
220 e = k + len;
221 for (h = 0; k < e; ++k) {
222 h *= 16777619;
223 h ^= *k;
224 }
225 return (h);
226 }
227