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