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