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