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