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 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 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 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 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