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