1 /*-
2 * SPDX-License-Identifier: BSD-3-Clause
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/types.h>
36
37 #include <db.h>
38 #include "hash.h"
39 #include "page.h"
40 #include "extern.h"
41
42 #ifdef notdef
43 static u_int32_t hash1(const void *, size_t) __unused;
44 static u_int32_t hash2(const void *, size_t) __unused;
45 static u_int32_t hash3(const void *, size_t) __unused;
46 #endif
47 static u_int32_t hash4(const void *, size_t);
48
49 /* Default hash function. */
50 u_int32_t (*__default_hash)(const void *, size_t) = hash4;
51
52 #ifdef notdef
53 /*
54 * Assume that we've already split the bucket to which this key hashes,
55 * calculate that bucket, and check that in fact we did already split it.
56 *
57 * EJB's original hsearch hash.
58 */
59 #define PRIME1 37
60 #define PRIME2 1048583
61
62 u_int32_t
hash1(const void * key,size_t len)63 hash1(const void *key, size_t len)
64 {
65 u_int32_t h;
66 u_int8_t *k;
67
68 h = 0;
69 k = (u_int8_t *)key;
70 /* Convert string to integer */
71 while (len--)
72 h = h * PRIME1 ^ (*k++ - ' ');
73 h %= PRIME2;
74 return (h);
75 }
76
77 /*
78 * Phong Vo's linear congruential hash
79 */
80 #define dcharhash(h, c) ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c))
81
82 u_int32_t
hash2(const void * key,size_t len)83 hash2(const void *key, size_t len)
84 {
85 u_int32_t h;
86 u_int8_t *e, c, *k;
87
88 k = (u_int8_t *)key;
89 e = k + len;
90 for (h = 0; k != e;) {
91 c = *k++;
92 if (!c && k > e)
93 break;
94 dcharhash(h, c);
95 }
96 return (h);
97 }
98
99 /*
100 * This is INCREDIBLY ugly, but fast. We break the string up into 8 byte
101 * units. On the first time through the loop we get the "leftover bytes"
102 * (strlen % 8). On every other iteration, we perform 8 HASHC's so we handle
103 * all 8 bytes. Essentially, this saves us 7 cmp & branch instructions. If
104 * this routine is heavily used enough, it's worth the ugly coding.
105 *
106 * Ozan Yigit's original sdbm hash.
107 */
108 u_int32_t
hash3(const void * key,size_t len)109 hash3(const void *key, size_t len)
110 {
111 u_int32_t n, loop;
112 u_int8_t *k;
113
114 #define HASHC n = *k++ + 65599 * n
115
116 n = 0;
117 k = (u_int8_t *)key;
118 if (len > 0) {
119 loop = (len + 8 - 1) >> 3;
120
121 switch (len & (8 - 1)) {
122 case 0:
123 do { /* All fall throughs */
124 HASHC;
125 case 7:
126 HASHC;
127 case 6:
128 HASHC;
129 case 5:
130 HASHC;
131 case 4:
132 HASHC;
133 case 3:
134 HASHC;
135 case 2:
136 HASHC;
137 case 1:
138 HASHC;
139 } while (--loop);
140 }
141
142 }
143 return (n);
144 }
145 #endif /* notdef */
146
147 /* Chris Torek's hash function. */
148 u_int32_t
hash4(const void * key,size_t len)149 hash4(const void *key, size_t len)
150 {
151 u_int32_t h, loop;
152 const u_int8_t *k;
153
154 #define HASH4a h = (h << 5) - h + *k++;
155 #define HASH4b h = (h << 5) + h + *k++;
156 #define HASH4 HASH4b
157
158 h = 0;
159 k = key;
160 if (len > 0) {
161 loop = (len + 8 - 1) >> 3;
162
163 switch (len & (8 - 1)) {
164 case 0:
165 do { /* All fall throughs */
166 HASH4;
167 case 7:
168 HASH4;
169 case 6:
170 HASH4;
171 case 5:
172 HASH4;
173 case 4:
174 HASH4;
175 case 3:
176 HASH4;
177 case 2:
178 HASH4;
179 case 1:
180 HASH4;
181 } while (--loop);
182 }
183
184 }
185 return (h);
186 }
187