1 #pragma ident "%Z%%M% %I% %E% SMI"
2
3 /*-
4 * Copyright (c) 1990, 1993
5 * The Regents of the University of California. All rights reserved.
6 *
7 * This code is derived from software contributed to Berkeley by
8 * Margo Seltzer.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 * 3. All advertising materials mentioning features or use of this software
19 * must display the following acknowledgement:
20 * This product includes software developed by the University of
21 * California, Berkeley and its contributors.
22 * 4. Neither the name of the University nor the names of its contributors
23 * may be used to endorse or promote products derived from this software
24 * without specific prior written permission.
25 *
26 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
27 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
29 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
30 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
31 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
32 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
33 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
34 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
35 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
36 * SUCH DAMAGE.
37 */
38
39 #if defined(LIBC_SCCS) && !defined(lint)
40 static char sccsid[] = "@(#)hash_func.c 8.4 (Berkeley) 11/7/95";
41 #endif /* LIBC_SCCS and not lint */
42
43 #include <sys/types.h>
44
45 #include "db-int.h"
46 #include "hash.h"
47 #include "page.h"
48 #include "extern.h"
49
50 #if 0
51 static u_int32_t hash1 __P((const void *, size_t));
52 static u_int32_t hash2 __P((const void *, size_t));
53 static u_int32_t hash3 __P((const void *, size_t));
54 #endif
55 static u_int32_t hash4 __P((const void *, size_t));
56
57 /* Default hash function. */
58 u_int32_t (*__default_hash) __P((const void *, size_t)) = hash4;
59
60 /*
61 * Assume that we've already split the bucket to which this key hashes,
62 * calculate that bucket, and check that in fact we did already split it.
63 *
64 * EJB's original hsearch hash.
65 */
66 #define PRIME1 37
67 #define PRIME2 1048583
68
69 #if 0
70 static u_int32_t
71 hash1(key, len)
72 const void *key;
73 size_t len;
74 {
75 u_int32_t h;
76 u_int8_t *k;
77
78 h = 0;
79 k = (u_int8_t *)key;
80 /* Convert string to integer */
81 while (len--)
82 h = h * PRIME1 ^ (*k++ - ' ');
83 h %= PRIME2;
84 return (h);
85 }
86
87 /*
88 * Phong Vo's linear congruential hash
89 */
90 #define dcharhash(h, c) ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c))
91
92 static u_int32_t
93 hash2(key, len)
94 const void *key;
95 size_t len;
96 {
97 u_int32_t h;
98 u_int8_t *e, c, *k;
99
100 k = (u_int8_t *)key;
101 e = k + len;
102 for (h = 0; k != e;) {
103 c = *k++;
104 if (!c && k > e)
105 break;
106 dcharhash(h, c);
107 }
108 return (h);
109 }
110
111 /*
112 * This is INCREDIBLY ugly, but fast. We break the string up into 8 byte
113 * units. On the first time through the loop we get the "leftover bytes"
114 * (strlen % 8). On every other iteration, we perform 8 HASHC's so we handle
115 * all 8 bytes. Essentially, this saves us 7 cmp & branch instructions. If
116 * this routine is heavily used enough, it's worth the ugly coding.
117 *
118 * Ozan Yigit's original sdbm hash.
119 */
120 static u_int32_t
121 hash3(key, len)
122 const void *key;
123 size_t len;
124 {
125 u_int32_t n, loop;
126 u_int8_t *k;
127
128 #define HASHC n = *k++ + 65599 * n
129
130 n = 0;
131 k = (u_int8_t *)key;
132 if (len > 0) {
133 loop = (len + 8 - 1) >> 3;
134
135 switch (len & (8 - 1)) {
136 case 0:
137 do { /* All fall throughs */
138 HASHC;
139 case 7:
140 HASHC;
141 case 6:
142 HASHC;
143 case 5:
144 HASHC;
145 case 4:
146 HASHC;
147 case 3:
148 HASHC;
149 case 2:
150 HASHC;
151 case 1:
152 HASHC;
153 } while (--loop);
154 }
155
156 }
157 return (n);
158 }
159 #endif
160
161
162 /* Chris Torek's hash function. */
163 static u_int32_t
hash4(key,len)164 hash4(key, len)
165 const void *key;
166 size_t len;
167 {
168 u_int32_t h, loop;
169 const u_int8_t *k;
170
171 #define HASH4a h = (h << 5) - h + *k++;
172 #define HASH4b h = (h << 5) + h + *k++;
173 #define HASH4 HASH4b
174
175 h = 0;
176 k = (const u_int8_t *)key;
177 if (len > 0) {
178 loop = (len + 8 - 1) >> 3;
179
180 switch (len & (8 - 1)) {
181 case 0:
182 do { /* All fall throughs */
183 HASH4;
184 case 7:
185 HASH4;
186 case 6:
187 HASH4;
188 case 5:
189 HASH4;
190 case 4:
191 HASH4;
192 case 3:
193 HASH4;
194 case 2:
195 HASH4;
196 case 1:
197 HASH4;
198 } while (--loop);
199 }
200
201 }
202 return (h);
203 }
204