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