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