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 #ifndef NO_SYSTEM_INCLUDES
54 #include <sys/types.h>
55 #endif
56
57 #include "db_int.h"
58 #include "db_page.h"
59 #include "hash.h"
60
61 /*
62 * __ham_func2 --
63 * Phong Vo's linear congruential hash.
64 *
65 * PUBLIC: u_int32_t __ham_func2 __P((const void *, u_int32_t));
66 */
67 #define DCHARHASH(h, c) ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c))
68
69 u_int32_t
__ham_func2(key,len)70 __ham_func2(key, len)
71 const void *key;
72 u_int32_t len;
73 {
74 const u_int8_t *e, *k;
75 u_int32_t h;
76 u_int8_t c;
77
78 k = key;
79 e = k + len;
80 for (h = 0; k != e;) {
81 c = *k++;
82 if (!c && k > e)
83 break;
84 DCHARHASH(h, c);
85 }
86 return (h);
87 }
88
89 /*
90 * __ham_func3 --
91 * Ozan Yigit's original sdbm hash.
92 *
93 * Ugly, but fast. Break the string up into 8 byte units. On the first time
94 * through the loop get the "leftover bytes" (strlen % 8). On every other
95 * iteration, perform 8 HASHC's so we handle all 8 bytes. Essentially, this
96 * saves us 7 cmp & branch instructions.
97 *
98 * PUBLIC: u_int32_t __ham_func3 __P((const void *, u_int32_t));
99 */
100 u_int32_t
__ham_func3(key,len)101 __ham_func3(key, len)
102 const void *key;
103 u_int32_t len;
104 {
105 const u_int8_t *k;
106 u_int32_t n, loop;
107
108 if (len == 0)
109 return (0);
110
111 #define HASHC n = *k++ + 65599 * n
112 n = 0;
113 k = key;
114
115 loop = (len + 8 - 1) >> 3;
116 switch (len & (8 - 1)) {
117 case 0:
118 do {
119 HASHC;
120 /* FALLTHROUGH */
121 case 7:
122 HASHC;
123 /* FALLTHROUGH */
124 case 6:
125 HASHC;
126 /* FALLTHROUGH */
127 case 5:
128 HASHC;
129 /* FALLTHROUGH */
130 case 4:
131 HASHC;
132 /* FALLTHROUGH */
133 case 3:
134 HASHC;
135 /* FALLTHROUGH */
136 case 2:
137 HASHC;
138 /* FALLTHROUGH */
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 /* FALLTHROUGH */
177 case 7:
178 HASH4;
179 /* FALLTHROUGH */
180 case 6:
181 HASH4;
182 /* FALLTHROUGH */
183 case 5:
184 HASH4;
185 /* FALLTHROUGH */
186 case 4:
187 HASH4;
188 /* FALLTHROUGH */
189 case 3:
190 HASH4;
191 /* FALLTHROUGH */
192 case 2:
193 HASH4;
194 /* FALLTHROUGH */
195 case 1:
196 HASH4;
197 } while (--loop);
198 }
199 return (h);
200 }
201
202 /*
203 * Fowler/Noll/Vo hash
204 *
205 * The basis of the hash algorithm was taken from an idea sent by email to the
206 * IEEE Posix P1003.2 mailing list from Phong Vo (kpv@research.att.com) and
207 * Glenn Fowler (gsf@research.att.com). Landon Curt Noll (chongo@toad.com)
208 * later improved on their algorithm.
209 *
210 * The magic is in the interesting relationship between the special prime
211 * 16777619 (2^24 + 403) and 2^32 and 2^8.
212 *
213 * This hash produces the fewest collisions of any function that we've seen so
214 * far, and works well on both numbers and strings.
215 *
216 * PUBLIC: u_int32_t __ham_func5 __P((const void *, u_int32_t));
217 */
218 u_int32_t
__ham_func5(key,len)219 __ham_func5(key, len)
220 const void *key;
221 u_int32_t len;
222 {
223 const u_int8_t *k, *e;
224 u_int32_t h;
225
226 k = key;
227 e = k + len;
228 for (h = 0; k < e; ++k) {
229 h *= 16777619;
230 h ^= *k;
231 }
232 return (h);
233 }
234