| t2ex/bsd_source/lib/libc/src_bsd/search/hash_func.c | bare source | permlink (0.01 seconds) |
1: /* $OpenBSD: hash_func.c,v 1.10 2005/08/05 13:03:00 espie Exp $ */ 2: 3: /*- 4: * Copyright (c) 1990, 1993 5: * The Regents of the University of California. All rights reserved. 6: * 7: * This code is derived from software contributed to Berkeley by 8: * Margo Seltzer. 9: * 10: * Redistribution and use in source and binary forms, with or without 11: * modification, are permitted provided that the following conditions 12: * are met: 13: * 1. Redistributions of source code must retain the above copyright 14: * notice, this list of conditions and the following disclaimer. 15: * 2. Redistributions in binary form must reproduce the above copyright 16: * notice, this list of conditions and the following disclaimer in the 17: * documentation and/or other materials provided with the distribution. 18: * 3. Neither the name of the University nor the names of its contributors 19: * may be used to endorse or promote products derived from this software 20: * without specific prior written permission. 21: * 22: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 23: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 24: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 25: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 26: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 27: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 28: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 29: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 31: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32: * SUCH DAMAGE. 33: */ 34: 35: #include <sys/types.h> 36: 37: #include <db.h> 38: #include "hash.h" 39: #include "page.h" 40: #include "extern.h" 41: 42: #ifdef notdef 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: #endif 47: static u_int32_t hash4(const void *, size_t); 48: 49: /* Default hash function. */ 50: u_int32_t (*__default_hash)(const void *, size_t) = hash4; 51: 52: #ifdef notdef 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: * EJB's original hsearch hash. 58: */ 59: #define PRIME1 37 60: #define PRIME2 1048583 61: 62: u_int32_t 63: hash1(const void *key, size_t len) 64: { 65: u_int32_t h; 66: u_int8_t *k; 67: 68: h = 0; 69: k = (u_int8_t *)key; 70: /* Convert string to integer */ 71: while (len--) 72: h = h * PRIME1 ^ (*k++ - ' '); 73: h %= PRIME2; 74: return (h); 75: } 76: 77: /* 78: * Phong Vo's linear congruential hash 79: */ 80: #define dcharhash(h, c) ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c)) 81: 82: u_int32_t 83: hash2(const void *key, size_t len) 84: { 85: u_int32_t h; 86: u_int8_t *e, c, *k; 87: 88: k = (u_int8_t *)key; 89: e = k + len; 90: for (h = 0; k != e;) { 91: c = *k++; 92: if (!c && k > e) 93: break; 94: dcharhash(h, c); 95: } 96: return (h); 97: } 98: 99: /* 100: * This is INCREDIBLY ugly, but fast. We break the string up into 8 byte 101: * units. On the first time through the loop we get the "leftover bytes" 102: * (strlen % 8). On every other iteration, we perform 8 HASHC's so we handle 103: * all 8 bytes. Essentially, this saves us 7 cmp & branch instructions. If 104: * this routine is heavily used enough, it's worth the ugly coding. 105: * 106: * Ozan Yigit's original sdbm hash. 107: */ 108: u_int32_t 109: hash3(const void *key, size_t len) 110: { 111: u_int32_t n, loop; 112: u_int8_t *k; 113: 114: #define HASHC n = *k++ + 65599 * n 115: 116: n = 0; 117: k = (u_int8_t *)key; 118: if (len > 0) { 119: loop = (len + 8 - 1) >> 3; 120: 121: switch (len & (8 - 1)) { 122: case 0: 123: do { /* All fall throughs */ 124: HASHC; 125: case 7: 126: HASHC; 127: case 6: 128: HASHC; 129: case 5: 130: HASHC; 131: case 4: 132: HASHC; 133: case 3: 134: HASHC; 135: case 2: 136: HASHC; 137: case 1: 138: HASHC; 139: } while (--loop); 140: } 141: 142: } 143: return (n); 144: } 145: #endif /* notdef */ 146: 147: /* Chris Torek's hash function. */ 148: u_int32_t 149: hash4(const void *key, size_t len) 150: { 151: u_int32_t h, loop; 152: u_int8_t *k; 153: 154: #define HASH4a h = (h << 5) - h + *k++; 155: #define HASH4b h = (h << 5) + h + *k++; 156: #define HASH4 HASH4b 157: 158: h = 0; 159: k = (u_int8_t *)key; 160: if (len > 0) { 161: loop = (len + 8 - 1) >> 3; 162: 163: switch (len & (8 - 1)) { 164: case 0: 165: do { /* All fall throughs */ 166: HASH4; 167: case 7: 168: HASH4; 169: case 6: 170: HASH4; 171: case 5: 172: HASH4; 173: case 4: 174: HASH4; 175: case 3: 176: HASH4; 177: case 2: 178: HASH4; 179: case 1: 180: HASH4; 181: } while (--loop); 182: } 183: 184: } 185: return (h); 186: }