OLD | NEW |
1 /*- | 1 /*- |
2 * Copyright (c) 1990, 1993 | 2 * Copyright (c) 1990, 1993 |
3 * The Regents of the University of California. All rights reserved. | 3 * The Regents of the University of California. All rights reserved. |
4 * | 4 * |
5 * This code is derived from software contributed to Berkeley by | 5 * This code is derived from software contributed to Berkeley by |
6 * Margo Seltzer. | 6 * Margo Seltzer. |
7 * | 7 * |
8 * Redistribution and use in source and binary forms, with or without | 8 * Redistribution and use in source and binary forms, with or without |
9 * modification, are permitted provided that the following conditions | 9 * modification, are permitted provided that the following conditions |
10 * are met: | 10 * are met: |
11 * 1. Redistributions of source code must retain the above copyright | 11 * 1. Redistributions of source code must retain the above copyright |
12 * notice, this list of conditions and the following disclaimer. | 12 * notice, this list of conditions and the following disclaimer. |
13 * 2. Redistributions in binary form must reproduce the above copyright | 13 * 2. Redistributions in binary form must reproduce the above copyright |
14 * notice, this list of conditions and the following disclaimer in the | 14 * notice, this list of conditions and the following disclaimer in the |
15 * documentation and/or other materials provided with the distribution. | 15 * documentation and/or other materials provided with the distribution. |
16 * 3. ***REMOVED*** - see | 16 * 3. ***REMOVED*** - see |
17 * ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change | 17 * ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change |
18 * 4. Neither the name of the University nor the names of its contributors | 18 * 4. Neither the name of the University nor the names of its contributors |
19 * may be used to endorse or promote products derived from this software | 19 * may be used to endorse or promote products derived from this software |
20 * without specific prior written permission. | 20 * without specific prior written permission. |
21 * | 21 * |
22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND | 22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND |
23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | 23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | 24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE | 25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE |
26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | 26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
(...skipping 18 matching lines...) Expand all Loading... |
45 /* #include "extern.h" */ | 45 /* #include "extern.h" */ |
46 | 46 |
47 #if 0 | 47 #if 0 |
48 static uint32 hash1 __P((const void *, size_t)); | 48 static uint32 hash1 __P((const void *, size_t)); |
49 static uint32 hash2 __P((const void *, size_t)); | 49 static uint32 hash2 __P((const void *, size_t)); |
50 static uint32 hash3 __P((const void *, size_t)); | 50 static uint32 hash3 __P((const void *, size_t)); |
51 #endif | 51 #endif |
52 static uint32 hash4 __P((const void *, size_t)); | 52 static uint32 hash4 __P((const void *, size_t)); |
53 | 53 |
54 /* Global default hash function */ | 54 /* Global default hash function */ |
55 uint32 (*__default_hash) __P((const void *, size_t)) = hash4; | 55 uint32(*__default_hash) __P((const void *, size_t)) = hash4; |
56 | 56 |
57 /* | 57 /* |
58 * HASH FUNCTIONS | 58 * HASH FUNCTIONS |
59 * | 59 * |
60 * Assume that we've already split the bucket to which this key hashes, | 60 * Assume that we've already split the bucket to which this key hashes, |
61 * calculate that bucket, and check that in fact we did already split it. | 61 * calculate that bucket, and check that in fact we did already split it. |
62 * | 62 * |
63 * This came from ejb's hsearch. | 63 * This came from ejb's hsearch. |
64 */ | 64 */ |
65 | 65 |
66 #define PRIME1» » 37 | 66 #define PRIME1 37 |
67 #define PRIME2» » 1048583 | 67 #define PRIME2 1048583 |
68 | 68 |
69 #if 0 | 69 #if 0 |
70 static uint32 | 70 static uint32 |
71 hash1(const void *keyarg, register size_t len) | 71 hash1(const void *keyarg, register size_t len) |
72 { | 72 { |
73 register const uint8 *key; | 73 register const uint8 *key; |
74 register uint32 h; | 74 register uint32 h; |
75 | 75 |
76 /* Convert string to integer */ | 76 /* Convert string to integer */ |
77 for (key = (const uint8 *)keyarg, h = 0; len--;) | 77 for (key = (const uint8 *)keyarg, h = 0; len--;) |
78 h = h * PRIME1 ^ (*key++ - ' '); | 78 h = h * PRIME1 ^ (*key++ - ' '); |
79 h %= PRIME2; | 79 h %= PRIME2; |
80 return (h); | 80 return (h); |
81 } | 81 } |
82 | 82 |
83 /* | 83 /* |
84 * Phong's linear congruential hash | 84 * Phong's linear congruential hash |
85 */ | 85 */ |
86 #define dcharhash(h, c)»((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c)) | 86 #define dcharhash(h, c) ((h) = 0x63c63cd9 * (h) + 0x9c39c33d + (c)) |
87 | 87 |
88 static uint32 | 88 static uint32 |
89 hash2(const void *keyarg, size_t len) | 89 hash2(const void *keyarg, size_t len) |
90 { | 90 { |
91 register const uint8 *e, *key; | 91 register const uint8 *e, *key; |
92 register uint32 h; | 92 register uint32 h; |
93 register uint8 c; | 93 register uint8 c; |
94 | 94 |
95 key = (const uint8 *)keyarg; | 95 key = (const uint8 *)keyarg; |
96 e = key + len; | 96 e = key + len; |
(...skipping 15 matching lines...) Expand all Loading... |
112 * | 112 * |
113 * OZ's original sdbm hash | 113 * OZ's original sdbm hash |
114 */ | 114 */ |
115 static uint32 | 115 static uint32 |
116 hash3(const void *keyarg, register size_t len) | 116 hash3(const void *keyarg, register size_t len) |
117 { | 117 { |
118 register const uint8 *key; | 118 register const uint8 *key; |
119 register size_t loop; | 119 register size_t loop; |
120 register uint32 h; | 120 register uint32 h; |
121 | 121 |
122 #define HASHC h = *key++ + 65599 * h | 122 #define HASHC h = *key++ + 65599 * h |
123 | 123 |
124 h = 0; | 124 h = 0; |
125 key = (const uint8 *)keyarg; | 125 key = (const uint8 *)keyarg; |
126 if (len > 0) { | 126 if (len > 0) { |
127 loop = (len + 8 - 1) >> 3; | 127 loop = (len + 8 - 1) >> 3; |
128 | 128 |
129 switch (len & (8 - 1)) { | 129 switch (len & (8 - 1)) { |
130 case 0: | 130 case 0: |
131 do { | 131 do { |
132 HASHC; | 132 HASHC; |
(...skipping 19 matching lines...) Expand all Loading... |
152 case 1: | 152 case 1: |
153 HASHC; | 153 HASHC; |
154 } while (--loop); | 154 } while (--loop); |
155 } | 155 } |
156 } | 156 } |
157 return (h); | 157 return (h); |
158 } | 158 } |
159 #endif /* 0 */ | 159 #endif /* 0 */ |
160 | 160 |
161 /* Hash function from Chris Torek. */ | 161 /* Hash function from Chris Torek. */ |
162 static uint32 | 162 static uint32 hash4(const void *keyarg, register size_t len) { |
163 hash4(const void *keyarg, register size_t len) | 163 register const uint8 *key; |
164 { | 164 register size_t loop; |
165 » register const uint8 *key; | 165 register uint32 h; |
166 » register size_t loop; | |
167 » register uint32 h; | |
168 | 166 |
169 #define HASH4a h = (h << 5) - h + *key++; | 167 #define HASH4a h = (h << 5) - h + *key++; |
170 #define HASH4b h = (h << 5) + h + *key++; | 168 #define HASH4b h = (h << 5) + h + *key++; |
171 #define HASH4 HASH4b | 169 #define HASH4 HASH4b |
172 | 170 |
173 » h = 0; | 171 h = 0; |
174 » key = (const uint8 *)keyarg; | 172 key = (const uint8 *)keyarg; |
175 » if (len > 0) { | 173 if (len > 0) { |
176 » » loop = (len + 8 - 1) >> 3; | 174 loop = (len + 8 - 1) >> 3; |
177 | 175 |
178 » » switch (len & (8 - 1)) { | 176 switch (len & (8 - 1)) { |
179 » » case 0: | 177 case 0: |
180 » » » do { | 178 do { |
181 » » » » HASH4; | 179 HASH4; |
182 » » » » /* FALLTHROUGH */ | 180 /* FALLTHROUGH */ |
183 » » case 7: | 181 case 7: |
184 » » » » HASH4; | 182 HASH4; |
185 » » » » /* FALLTHROUGH */ | 183 /* FALLTHROUGH */ |
186 » » case 6: | 184 case 6: |
187 » » » » HASH4; | 185 HASH4; |
188 » » » » /* FALLTHROUGH */ | 186 /* FALLTHROUGH */ |
189 » » case 5: | 187 case 5: |
190 » » » » HASH4; | 188 HASH4; |
191 » » » » /* FALLTHROUGH */ | 189 /* FALLTHROUGH */ |
192 » » case 4: | 190 case 4: |
193 » » » » HASH4; | 191 HASH4; |
194 » » » » /* FALLTHROUGH */ | 192 /* FALLTHROUGH */ |
195 » » case 3: | 193 case 3: |
196 » » » » HASH4; | 194 HASH4; |
197 » » » » /* FALLTHROUGH */ | 195 /* FALLTHROUGH */ |
198 » » case 2: | 196 case 2: |
199 » » » » HASH4; | 197 HASH4; |
200 » » » » /* FALLTHROUGH */ | 198 /* FALLTHROUGH */ |
201 » » case 1: | 199 case 1: |
202 » » » » HASH4; | 200 HASH4; |
203 » » » } while (--loop); | 201 } while (--loop); |
204 » » } | 202 } |
205 » } | 203 } |
206 » return (h); | 204 return (h); |
207 } | 205 } |
OLD | NEW |