1 /*-
2 * Copyright (c) 1990, 1993
3 * The Regents of the University of California. All rights reserved.
4 *
5 * This code is derived from software contributed to Berkeley by
6 * Margo Seltzer.
7 *
8 * %sccs.include.redist.c%
9 */
10
11 #if defined(LIBC_SCCS) && !defined(lint)
12 static char sccsid[] = "@(#)hash_func.c 8.2 (Berkeley) 02/21/94";
13 #endif /* LIBC_SCCS and not lint */
14
15 #include <sys/types.h>
16
17 #include <db.h>
18 #include "hash.h"
19 #include "page.h"
20 #include "extern.h"
21
22 static u_int32_t hash1 __P((const void *, size_t));
23 static u_int32_t hash2 __P((const void *, size_t));
24 static u_int32_t hash3 __P((const void *, size_t));
25 static u_int32_t hash4 __P((const void *, size_t));
26
27 /* Global default hash function */
28 u_int32_t (*__default_hash) __P((const void *, size_t)) = hash4;
29
30 /*
31 * HASH FUNCTIONS
32 *
33 * Assume that we've already split the bucket to which this key hashes,
34 * calculate that bucket, and check that in fact we did already split it.
35 *
36 * This came from ejb's hsearch.
37 */
38
39 #define PRIME1 37
40 #define PRIME2 1048583
41
42 static u_int32_t
hash1(keyarg,len)43 hash1(keyarg, len)
44 const void *keyarg;
45 register size_t len;
46 {
47 register const u_char *key;
48 register u_int32_t h;
49
50 /* Convert string to integer */
51 for (key = keyarg, h = 0; len--;)
52 h = h * PRIME1 ^ (*key++ - ' ');
53 h %= PRIME2;
54 return (h);
55 }
56
57 /*
58 * Phong's linear congruential hash
59 */
60 #define dcharhash(h, c) ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c))
61
62 static u_int32_t
hash2(keyarg,len)63 hash2(keyarg, len)
64 const void *keyarg;
65 size_t len;
66 {
67 register const u_char *e, *key;
68 register u_int32_t h;
69 register u_char c;
70
71 key = keyarg;
72 e = key + len;
73 for (h = 0; key != e;) {
74 c = *key++;
75 if (!c && key > e)
76 break;
77 dcharhash(h, c);
78 }
79 return (h);
80 }
81
82 /*
83 * This is INCREDIBLY ugly, but fast. We break the string up into 8 byte
84 * units. On the first time through the loop we get the "leftover bytes"
85 * (strlen % 8). On every other iteration, we perform 8 HASHC's so we handle
86 * all 8 bytes. Essentially, this saves us 7 cmp & branch instructions. If
87 * this routine is heavily used enough, it's worth the ugly coding.
88 *
89 * OZ's original sdbm hash
90 */
91 static u_int32_t
hash3(keyarg,len)92 hash3(keyarg, len)
93 const void *keyarg;
94 register size_t len;
95 {
96 register const u_char *key;
97 register size_t loop;
98 register u_int32_t h;
99
100 #define HASHC h = *key++ + 65599 * h
101
102 h = 0;
103 key = keyarg;
104 if (len > 0) {
105 loop = (len + 8 - 1) >> 3;
106
107 switch (len & (8 - 1)) {
108 case 0:
109 do {
110 HASHC;
111 /* FALLTHROUGH */
112 case 7:
113 HASHC;
114 /* FALLTHROUGH */
115 case 6:
116 HASHC;
117 /* FALLTHROUGH */
118 case 5:
119 HASHC;
120 /* FALLTHROUGH */
121 case 4:
122 HASHC;
123 /* FALLTHROUGH */
124 case 3:
125 HASHC;
126 /* FALLTHROUGH */
127 case 2:
128 HASHC;
129 /* FALLTHROUGH */
130 case 1:
131 HASHC;
132 } while (--loop);
133 }
134 }
135 return (h);
136 }
137
138 /* Hash function from Chris Torek. */
139 static u_int32_t
hash4(keyarg,len)140 hash4(keyarg, len)
141 const void *keyarg;
142 register size_t len;
143 {
144 register const u_char *key;
145 register size_t loop;
146 register u_int32_t h;
147
148 #define HASH4a h = (h << 5) - h + *key++;
149 #define HASH4b h = (h << 5) + h + *key++;
150 #define HASH4 HASH4b
151
152 h = 0;
153 key = keyarg;
154 if (len > 0) {
155 loop = (len + 8 - 1) >> 3;
156
157 switch (len & (8 - 1)) {
158 case 0:
159 do {
160 HASH4;
161 /* FALLTHROUGH */
162 case 7:
163 HASH4;
164 /* FALLTHROUGH */
165 case 6:
166 HASH4;
167 /* FALLTHROUGH */
168 case 5:
169 HASH4;
170 /* FALLTHROUGH */
171 case 4:
172 HASH4;
173 /* FALLTHROUGH */
174 case 3:
175 HASH4;
176 /* FALLTHROUGH */
177 case 2:
178 HASH4;
179 /* FALLTHROUGH */
180 case 1:
181 HASH4;
182 } while (--loop);
183 }
184 }
185 return (h);
186 }
187