Home | History | Annotate | Line # | Download | only in hash
hash_func.c revision 1.1 
      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  * Redistribution and use in source and binary forms, with or without
      9  * modification, are permitted provided that the following conditions
     10  * are met:
     11  * 1. Redistributions of source code must retain the above copyright
     12  *    notice, this list of conditions and the following disclaimer.
     13  * 2. Redistributions in binary form must reproduce the above copyright
     14  *    notice, this list of conditions and the following disclaimer in the
     15  *    documentation and/or other materials provided with the distribution.
     16  * 3. All advertising materials mentioning features or use of this software
     17  *    must display the following acknowledgement:
     18  *	This product includes software developed by the University of
     19  *	California, Berkeley and its contributors.
     20  * 4. Neither the name of the University nor the names of its contributors
     21  *    may be used to endorse or promote products derived from this software
     22  *    without specific prior written permission.
     23  *
     24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
     25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
     28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     34  * SUCH DAMAGE.
     35  */
     36 
     37 #if defined(LIBC_SCCS) && !defined(lint)
     38 static char sccsid[] = "@(#)hash_func.c	8.1 (Berkeley) 6/4/93";
     39 #endif /* LIBC_SCCS and not lint */
     40 
     41 #include <sys/types.h>
     42 
     43 #include <db.h>
     44 #include "hash.h"
     45 #include "page.h"
     46 #include "extern.h"
     47 
     48 static int hash1 __P((u_char *, int));
     49 static int hash2 __P((u_char *, int));
     50 static int hash3 __P((u_char *, int));
     51 static int hash4 __P((u_char *, int));
     52 
     53 /* Global default hash function */
     54 int (*__default_hash) __P((u_char *, int)) = hash4;
     55 
     56 /******************************* HASH FUNCTIONS **************************/
     57 /*
     58  * Assume that we've already split the bucket to which this key hashes,
     59  * calculate that bucket, and check that in fact we did already split it.
     60  *
     61  * This came from ejb's hsearch.
     62  */
     63 
     64 #define PRIME1		37
     65 #define PRIME2		1048583
     66 
     67 static int
     68 hash1(key, len)
     69 	register u_char *key;
     70 	register int len;
     71 {
     72 	register int h;
     73 
     74 	h = 0;
     75 	/* Convert string to integer */
     76 	while (len--)
     77 		h = h * PRIME1 ^ (*key++ - ' ');
     78 	h %= PRIME2;
     79 	return (h);
     80 }
     81 
     82 /*
     83  * Phong's linear congruential hash
     84  */
     85 #define dcharhash(h, c)	((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c))
     86 
     87 static int
     88 hash2(key, len)
     89 	register u_char *key;
     90 	int len;
     91 {
     92 	register u_char *e, c;
     93 	register int h;
     94 
     95 	e = key + len;
     96 	for (h = 0; key != e;) {
     97 		c = *key++;
     98 		if (!c && key > e)
     99 			break;
    100 		dcharhash(h, c);
    101 	}
    102 	return (h);
    103 }
    104 
    105 /*
    106  * This is INCREDIBLY ugly, but fast.  We break the string up into 8 byte
    107  * units.  On the first time through the loop we get the "leftover bytes"
    108  * (strlen % 8).  On every other iteration, we perform 8 HASHC's so we handle
    109  * all 8 bytes.  Essentially, this saves us 7 cmp & branch instructions.  If
    110  * this routine is heavily used enough, it's worth the ugly coding.
    111  *
    112  * OZ's original sdbm hash
    113  */
    114 static int
    115 hash3(key, len)
    116 	register u_char *key;
    117 	register int len;
    118 {
    119 	register int n, loop;
    120 
    121 #define HASHC   n = *key++ + 65599 * n
    122 
    123 	n = 0;
    124 	if (len > 0) {
    125 		loop = (len + 8 - 1) >> 3;
    126 
    127 		switch (len & (8 - 1)) {
    128 		case 0:
    129 			do {	/* All fall throughs */
    130 				HASHC;
    131 		case 7:
    132 				HASHC;
    133 		case 6:
    134 				HASHC;
    135 		case 5:
    136 				HASHC;
    137 		case 4:
    138 				HASHC;
    139 		case 3:
    140 				HASHC;
    141 		case 2:
    142 				HASHC;
    143 		case 1:
    144 				HASHC;
    145 			} while (--loop);
    146 		}
    147 
    148 	}
    149 	return (n);
    150 }
    151 
    152 /* Hash function from Chris Torek. */
    153 static int
    154 hash4(key, len)
    155 	register u_char *key;
    156 	register int len;
    157 {
    158 	register int h, loop;
    159 
    160 #define HASH4a   h = (h << 5) - h + *key++;
    161 #define HASH4b   h = (h << 5) + h + *key++;
    162 #define HASH4 HASH4b
    163 
    164 	h = 0;
    165 	if (len > 0) {
    166 		loop = (len + 8 - 1) >> 3;
    167 
    168 		switch (len & (8 - 1)) {
    169 		case 0:
    170 			do {	/* All fall throughs */
    171 				HASH4;
    172 		case 7:
    173 				HASH4;
    174 		case 6:
    175 				HASH4;
    176 		case 5:
    177 				HASH4;
    178 		case 4:
    179 				HASH4;
    180 		case 3:
    181 				HASH4;
    182 		case 2:
    183 				HASH4;
    184 		case 1:
    185 				HASH4;
    186 			} while (--loop);
    187 		}
    188 
    189 	}
    190 	return (h);
    191 }
    192