git.saurik.com Git - apple/libc.git/blame_incremental

... / ...

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