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