11573Srgrimes/*- 21573Srgrimes * Copyright (c) 1990, 1993 31573Srgrimes * The Regents of the University of California. All rights reserved. 41573Srgrimes * 51573Srgrimes * This code is derived from software contributed to Berkeley by 61573Srgrimes * Margo Seltzer. 71573Srgrimes * 81573Srgrimes * Redistribution and use in source and binary forms, with or without 91573Srgrimes * modification, are permitted provided that the following conditions 101573Srgrimes * are met: 111573Srgrimes * 1. Redistributions of source code must retain the above copyright 121573Srgrimes * notice, this list of conditions and the following disclaimer. 131573Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 141573Srgrimes * notice, this list of conditions and the following disclaimer in the 151573Srgrimes * documentation and/or other materials provided with the distribution. 161573Srgrimes * 4. Neither the name of the University nor the names of its contributors 171573Srgrimes * may be used to endorse or promote products derived from this software 181573Srgrimes * without specific prior written permission. 191573Srgrimes * 201573Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 211573Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 221573Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 231573Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 241573Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 251573Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 261573Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 271573Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 281573Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 291573Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 301573Srgrimes * SUCH DAMAGE. 311573Srgrimes */ 321573Srgrimes 331573Srgrimes#if defined(LIBC_SCCS) && !defined(lint) 341573Srgrimesstatic char sccsid[] = "@(#)hash_func.c 8.2 (Berkeley) 2/21/94"; 351573Srgrimes#endif /* LIBC_SCCS and not lint */ 3692889Sobrien#include <sys/cdefs.h> 3792889Sobrien__FBSDID("$FreeBSD: releng/10.3/lib/libc/db/hash/hash_func.c 190498 2009-03-28 07:31:02Z delphij $"); 381573Srgrimes 391573Srgrimes#include <sys/types.h> 401573Srgrimes 411573Srgrimes#include <db.h> 421573Srgrimes#include "hash.h" 431573Srgrimes#include "page.h" 441573Srgrimes#include "extern.h" 451573Srgrimes 46190498Sdelphij#ifdef notdef 47111010Snectarstatic u_int32_t hash1(const void *, size_t) __unused; 48111010Snectarstatic u_int32_t hash2(const void *, size_t) __unused; 49111010Snectarstatic u_int32_t hash3(const void *, size_t) __unused; 50190498Sdelphij#endif 5192905Sobrienstatic u_int32_t hash4(const void *, size_t); 521573Srgrimes 53190498Sdelphij/* Default hash function. */ 5492941Sobrienu_int32_t (*__default_hash)(const void *, size_t) = hash4; 551573Srgrimes 56190498Sdelphij#ifdef notdef 571573Srgrimes/* 581573Srgrimes * Assume that we've already split the bucket to which this key hashes, 591573Srgrimes * calculate that bucket, and check that in fact we did already split it. 601573Srgrimes * 61190498Sdelphij * EJB's original hsearch hash. 621573Srgrimes */ 631573Srgrimes#define PRIME1 37 641573Srgrimes#define PRIME2 1048583 651573Srgrimes 66190498Sdelphiju_int32_t 67190498Sdelphijhash1(const void *key, size_t len) 681573Srgrimes{ 6992889Sobrien u_int32_t h; 70190498Sdelphij u_int8_t *k; 711573Srgrimes 72190498Sdelphij h = 0; 73190498Sdelphij k = (u_int8_t *)key; 741573Srgrimes /* Convert string to integer */ 75190498Sdelphij while (len--) 76190498Sdelphij h = h * PRIME1 ^ (*k++ - ' '); 771573Srgrimes h %= PRIME2; 781573Srgrimes return (h); 791573Srgrimes} 801573Srgrimes 811573Srgrimes/* 82190498Sdelphij * Phong Vo's linear congruential hash 831573Srgrimes */ 841573Srgrimes#define dcharhash(h, c) ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c)) 851573Srgrimes 86190498Sdelphiju_int32_t 87190498Sdelphijhash2(const void *key, size_t len) 881573Srgrimes{ 8992889Sobrien u_int32_t h; 90190498Sdelphij u_int8_t *e, c, *k; 911573Srgrimes 92190498Sdelphij k = (u_int8_t *)key; 93190498Sdelphij e = k + len; 94190498Sdelphij for (h = 0; k != e;) { 95190498Sdelphij c = *k++; 96190498Sdelphij if (!c && k > e) 971573Srgrimes break; 981573Srgrimes dcharhash(h, c); 991573Srgrimes } 1001573Srgrimes return (h); 1011573Srgrimes} 1021573Srgrimes 1031573Srgrimes/* 1041573Srgrimes * This is INCREDIBLY ugly, but fast. We break the string up into 8 byte 1051573Srgrimes * units. On the first time through the loop we get the "leftover bytes" 1061573Srgrimes * (strlen % 8). On every other iteration, we perform 8 HASHC's so we handle 1071573Srgrimes * all 8 bytes. Essentially, this saves us 7 cmp & branch instructions. If 1081573Srgrimes * this routine is heavily used enough, it's worth the ugly coding. 1091573Srgrimes * 110190498Sdelphij * Ozan Yigit's original sdbm hash. 1111573Srgrimes */ 112190498Sdelphiju_int32_t 113190498Sdelphijhash3(const void *key, size_t len) 1141573Srgrimes{ 115190498Sdelphij u_int32_t n, loop; 116190498Sdelphij u_int8_t *k; 1171573Srgrimes 118190498Sdelphij#define HASHC n = *k++ + 65599 * n 1191573Srgrimes 120190498Sdelphij n = 0; 121190498Sdelphij k = (u_int8_t *)key; 1221573Srgrimes if (len > 0) { 1231573Srgrimes loop = (len + 8 - 1) >> 3; 1241573Srgrimes 1251573Srgrimes switch (len & (8 - 1)) { 1261573Srgrimes case 0: 127190498Sdelphij do { /* All fall throughs */ 1281573Srgrimes HASHC; 1291573Srgrimes case 7: 1301573Srgrimes HASHC; 1311573Srgrimes case 6: 1321573Srgrimes HASHC; 1331573Srgrimes case 5: 1341573Srgrimes HASHC; 1351573Srgrimes case 4: 1361573Srgrimes HASHC; 1371573Srgrimes case 3: 1381573Srgrimes HASHC; 1391573Srgrimes case 2: 1401573Srgrimes HASHC; 1411573Srgrimes case 1: 1421573Srgrimes HASHC; 1431573Srgrimes } while (--loop); 1441573Srgrimes } 145190498Sdelphij 1461573Srgrimes } 147190498Sdelphij return (n); 1481573Srgrimes} 149190498Sdelphij#endif /* notdef */ 1501573Srgrimes 151190498Sdelphij/* Chris Torek's hash function. */ 152190498Sdelphiju_int32_t 153190498Sdelphijhash4(const void *key, size_t len) 1541573Srgrimes{ 155190498Sdelphij u_int32_t h, loop; 156190498Sdelphij const u_int8_t *k; 1571573Srgrimes 158190498Sdelphij#define HASH4a h = (h << 5) - h + *k++; 159190498Sdelphij#define HASH4b h = (h << 5) + h + *k++; 1601573Srgrimes#define HASH4 HASH4b 1611573Srgrimes 1621573Srgrimes h = 0; 163190498Sdelphij k = key; 1641573Srgrimes if (len > 0) { 1651573Srgrimes loop = (len + 8 - 1) >> 3; 1661573Srgrimes 1671573Srgrimes switch (len & (8 - 1)) { 1681573Srgrimes case 0: 169190498Sdelphij do { /* All fall throughs */ 1701573Srgrimes HASH4; 1711573Srgrimes case 7: 1721573Srgrimes HASH4; 1731573Srgrimes case 6: 1741573Srgrimes HASH4; 1751573Srgrimes case 5: 1761573Srgrimes HASH4; 1771573Srgrimes case 4: 1781573Srgrimes HASH4; 1791573Srgrimes case 3: 1801573Srgrimes HASH4; 1811573Srgrimes case 2: 1821573Srgrimes HASH4; 1831573Srgrimes case 1: 1841573Srgrimes HASH4; 1851573Srgrimes } while (--loop); 1861573Srgrimes } 187190498Sdelphij 1881573Srgrimes } 1891573Srgrimes return (h); 1901573Srgrimes} 191