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 * 3. 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 * @(#)hash_func.c 8.2 (Berkeley) 2/21/94 33 * $DragonFly: src/lib/libc/db/hash/hash_func.c,v 1.6 2005/09/19 09:20:37 asmodai Exp $ 34 */ 35 36 #include <sys/types.h> 37 38 #include <db.h> 39 #include "hash.h" 40 #include "page.h" 41 #include "extern.h" 42 43 static u_int32_t hash1 (const void *, size_t); 44 static u_int32_t hash2 (const void *, size_t); 45 static u_int32_t hash3 (const void *, size_t); 46 static u_int32_t hash4 (const void *, size_t); 47 48 /* Global default hash function */ 49 u_int32_t (*__default_hash) (const void *, size_t) = hash4; 50 51 /* 52 * HASH FUNCTIONS 53 * 54 * Assume that we've already split the bucket to which this key hashes, 55 * calculate that bucket, and check that in fact we did already split it. 56 * 57 * This came from ejb's hsearch. 58 */ 59 60 #define PRIME1 37 61 #define PRIME2 1048583 62 63 static u_int32_t 64 hash1(keyarg, len) 65 const void *keyarg; 66 size_t len; 67 { 68 const u_char *key; 69 u_int32_t h; 70 71 /* Convert string to integer */ 72 for (key = keyarg, h = 0; len--;) 73 h = h * PRIME1 ^ (*key++ - ' '); 74 h %= PRIME2; 75 return (h); 76 } 77 78 /* 79 * Phong's linear congruential hash 80 */ 81 #define dcharhash(h, c) ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c)) 82 83 static u_int32_t 84 hash2(keyarg, len) 85 const void *keyarg; 86 size_t len; 87 { 88 const u_char *e, *key; 89 u_int32_t h; 90 u_char c; 91 92 key = keyarg; 93 e = key + len; 94 for (h = 0; key != e;) { 95 c = *key++; 96 if (!c && key > e) 97 break; 98 dcharhash(h, c); 99 } 100 return (h); 101 } 102 103 /* 104 * This is INCREDIBLY ugly, but fast. We break the string up into 8 byte 105 * units. On the first time through the loop we get the "leftover bytes" 106 * (strlen % 8). On every other iteration, we perform 8 HASHC's so we handle 107 * all 8 bytes. Essentially, this saves us 7 cmp & branch instructions. If 108 * this routine is heavily used enough, it's worth the ugly coding. 109 * 110 * OZ's original sdbm hash 111 */ 112 static u_int32_t 113 hash3(keyarg, len) 114 const void *keyarg; 115 size_t len; 116 { 117 const u_char *key; 118 size_t loop; 119 u_int32_t h; 120 121 #define HASHC h = *key++ + 65599 * h 122 123 h = 0; 124 key = keyarg; 125 if (len > 0) { 126 loop = (len + 8 - 1) >> 3; 127 128 switch (len & (8 - 1)) { 129 case 0: 130 do { 131 HASHC; 132 /* FALLTHROUGH */ 133 case 7: 134 HASHC; 135 /* FALLTHROUGH */ 136 case 6: 137 HASHC; 138 /* FALLTHROUGH */ 139 case 5: 140 HASHC; 141 /* FALLTHROUGH */ 142 case 4: 143 HASHC; 144 /* FALLTHROUGH */ 145 case 3: 146 HASHC; 147 /* FALLTHROUGH */ 148 case 2: 149 HASHC; 150 /* FALLTHROUGH */ 151 case 1: 152 HASHC; 153 } while (--loop); 154 } 155 } 156 return (h); 157 } 158 159 /* Hash function from Chris Torek. */ 160 static u_int32_t 161 hash4(keyarg, len) 162 const void *keyarg; 163 size_t len; 164 { 165 const u_char *key; 166 size_t loop; 167 u_int32_t h; 168 169 #define HASH4a h = (h << 5) - h + *key++; 170 #define HASH4b h = (h << 5) + h + *key++; 171 #define HASH4 HASH4b 172 173 h = 0; 174 key = keyarg; 175 if (len > 0) { 176 loop = (len + 8 - 1) >> 3; 177 178 switch (len & (8 - 1)) { 179 case 0: 180 do { 181 HASH4; 182 /* FALLTHROUGH */ 183 case 7: 184 HASH4; 185 /* FALLTHROUGH */ 186 case 6: 187 HASH4; 188 /* FALLTHROUGH */ 189 case 5: 190 HASH4; 191 /* FALLTHROUGH */ 192 case 4: 193 HASH4; 194 /* FALLTHROUGH */ 195 case 3: 196 HASH4; 197 /* FALLTHROUGH */ 198 case 2: 199 HASH4; 200 /* FALLTHROUGH */ 201 case 1: 202 HASH4; 203 } while (--loop); 204 } 205 } 206 return (h); 207 } 208