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