hash_func.c revision 190498
1300903Sallanjude/*- 2300903Sallanjude * Copyright (c) 1990, 1993 3300903Sallanjude * The Regents of the University of California. All rights reserved. 4300903Sallanjude * 5300903Sallanjude * This code is derived from software contributed to Berkeley by 6300903Sallanjude * Margo Seltzer. 7300903Sallanjude * 8300903Sallanjude * Redistribution and use in source and binary forms, with or without 9300903Sallanjude * modification, are permitted provided that the following conditions 10300903Sallanjude * are met: 11300903Sallanjude * 1. Redistributions of source code must retain the above copyright 12300903Sallanjude * notice, this list of conditions and the following disclaimer. 13300903Sallanjude * 2. Redistributions in binary form must reproduce the above copyright 14300903Sallanjude * notice, this list of conditions and the following disclaimer in the 15300903Sallanjude * documentation and/or other materials provided with the distribution. 16300903Sallanjude * 4. Neither the name of the University nor the names of its contributors 17300903Sallanjude * may be used to endorse or promote products derived from this software 18300903Sallanjude * without specific prior written permission. 19300903Sallanjude * 20300903Sallanjude * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 21300903Sallanjude * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 22300903Sallanjude * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 23300903Sallanjude * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 24300903Sallanjude * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 25300903Sallanjude * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 26300903Sallanjude * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27300903Sallanjude * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28300903Sallanjude * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29300903Sallanjude * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30300903Sallanjude * SUCH DAMAGE. 31300903Sallanjude */ 32300903Sallanjude 33300903Sallanjude#if defined(LIBC_SCCS) && !defined(lint) 34300903Sallanjudestatic char sccsid[] = "@(#)hash_func.c 8.2 (Berkeley) 2/21/94"; 35300903Sallanjude#endif /* LIBC_SCCS and not lint */ 36300903Sallanjude#include <sys/cdefs.h> 37300903Sallanjude__FBSDID("$FreeBSD: head/lib/libc/db/hash/hash_func.c 190498 2009-03-28 07:31:02Z delphij $"); 38300903Sallanjude 39300903Sallanjude#include <sys/types.h> 40300903Sallanjude 41300903Sallanjude#include <db.h> 42300903Sallanjude#include "hash.h" 43300903Sallanjude#include "page.h" 44300903Sallanjude#include "extern.h" 45300903Sallanjude 46300903Sallanjude#ifdef notdef 47300903Sallanjudestatic u_int32_t hash1(const void *, size_t) __unused; 48300903Sallanjudestatic u_int32_t hash2(const void *, size_t) __unused; 49300903Sallanjudestatic u_int32_t hash3(const void *, size_t) __unused; 50300903Sallanjude#endif 51300903Sallanjudestatic u_int32_t hash4(const void *, size_t); 52300903Sallanjude 53300903Sallanjude/* Default hash function. */ 54300903Sallanjudeu_int32_t (*__default_hash)(const void *, size_t) = hash4; 55300903Sallanjude 56300903Sallanjude#ifdef notdef 57300903Sallanjude/* 58300903Sallanjude * Assume that we've already split the bucket to which this key hashes, 59300903Sallanjude * calculate that bucket, and check that in fact we did already split it. 60300903Sallanjude * 61300903Sallanjude * EJB's original hsearch hash. 62300903Sallanjude */ 63300903Sallanjude#define PRIME1 37 64300903Sallanjude#define PRIME2 1048583 65300903Sallanjude 66300903Sallanjudeu_int32_t 67300903Sallanjudehash1(const void *key, size_t len) 68300903Sallanjude{ 69300903Sallanjude u_int32_t h; 70300903Sallanjude u_int8_t *k; 71300903Sallanjude 72300903Sallanjude h = 0; 73300903Sallanjude k = (u_int8_t *)key; 74300903Sallanjude /* Convert string to integer */ 75300903Sallanjude while (len--) 76300903Sallanjude h = h * PRIME1 ^ (*k++ - ' '); 77300903Sallanjude h %= PRIME2; 78300903Sallanjude return (h); 79300903Sallanjude} 80300903Sallanjude 81300903Sallanjude/* 82300903Sallanjude * Phong Vo's linear congruential hash 83300903Sallanjude */ 84300903Sallanjude#define dcharhash(h, c) ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c)) 85300903Sallanjude 86300903Sallanjudeu_int32_t 87300903Sallanjudehash2(const void *key, size_t len) 88300903Sallanjude{ 89300903Sallanjude u_int32_t h; 90300903Sallanjude u_int8_t *e, c, *k; 91300903Sallanjude 92300903Sallanjude k = (u_int8_t *)key; 93300903Sallanjude e = k + len; 94300903Sallanjude for (h = 0; k != e;) { 95300903Sallanjude c = *k++; 96300903Sallanjude if (!c && k > e) 97300903Sallanjude break; 98300903Sallanjude dcharhash(h, c); 99300903Sallanjude } 100300903Sallanjude return (h); 101300903Sallanjude} 102300903Sallanjude 103300903Sallanjude/* 104300903Sallanjude * This is INCREDIBLY ugly, but fast. We break the string up into 8 byte 105300903Sallanjude * units. On the first time through the loop we get the "leftover bytes" 106300903Sallanjude * (strlen % 8). On every other iteration, we perform 8 HASHC's so we handle 107300903Sallanjude * all 8 bytes. Essentially, this saves us 7 cmp & branch instructions. If 108300903Sallanjude * this routine is heavily used enough, it's worth the ugly coding. 109300903Sallanjude * 110300903Sallanjude * Ozan Yigit's original sdbm hash. 111300903Sallanjude */ 112300903Sallanjudeu_int32_t 113300903Sallanjudehash3(const void *key, size_t len) 114300903Sallanjude{ 115300903Sallanjude u_int32_t n, loop; 116300903Sallanjude u_int8_t *k; 117300903Sallanjude 118300903Sallanjude#define HASHC n = *k++ + 65599 * n 119300903Sallanjude 120300903Sallanjude n = 0; 121300903Sallanjude k = (u_int8_t *)key; 122300903Sallanjude if (len > 0) { 123300903Sallanjude loop = (len + 8 - 1) >> 3; 124300903Sallanjude 125300903Sallanjude switch (len & (8 - 1)) { 126 case 0: 127 do { /* All fall throughs */ 128 HASHC; 129 case 7: 130 HASHC; 131 case 6: 132 HASHC; 133 case 5: 134 HASHC; 135 case 4: 136 HASHC; 137 case 3: 138 HASHC; 139 case 2: 140 HASHC; 141 case 1: 142 HASHC; 143 } while (--loop); 144 } 145 146 } 147 return (n); 148} 149#endif /* notdef */ 150 151/* Chris Torek's hash function. */ 152u_int32_t 153hash4(const void *key, size_t len) 154{ 155 u_int32_t h, loop; 156 const u_int8_t *k; 157 158#define HASH4a h = (h << 5) - h + *k++; 159#define HASH4b h = (h << 5) + h + *k++; 160#define HASH4 HASH4b 161 162 h = 0; 163 k = key; 164 if (len > 0) { 165 loop = (len + 8 - 1) >> 3; 166 167 switch (len & (8 - 1)) { 168 case 0: 169 do { /* All fall throughs */ 170 HASH4; 171 case 7: 172 HASH4; 173 case 6: 174 HASH4; 175 case 5: 176 HASH4; 177 case 4: 178 HASH4; 179 case 3: 180 HASH4; 181 case 2: 182 HASH4; 183 case 1: 184 HASH4; 185 } while (--loop); 186 } 187 188 } 189 return (h); 190} 191