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