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