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