- Fix several compilation warnings.
[dragonfly.git] / lib / libc / db / hash / hash_func.c
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. 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  * @(#)hash_func.c      8.2 (Berkeley) 2/21/94
33  * $DragonFly: src/lib/libc/db/hash/hash_func.c,v 1.8 2005/11/19 20:46:32 swildner Exp $
34  */
35
36 #include <sys/types.h>
37
38 #include <db.h>
39 #include "hash.h"
40 #include "page.h"
41 #include "extern.h"
42
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 static u_int32_t hash4 (const void *, size_t);
47
48 /* Global default hash function */
49 u_int32_t (*__default_hash) (const void *, size_t) = hash4;
50
51 /*
52  * HASH FUNCTIONS
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  * This came from ejb's hsearch.
58  */
59
60 #define PRIME1          37
61 #define PRIME2          1048583
62
63 static u_int32_t
64 hash1(const void *keyarg, size_t len)
65 {
66         const u_char *key;
67         u_int32_t h;
68
69         /* Convert string to integer */
70         for (key = keyarg, h = 0; len--;)
71                 h = h * PRIME1 ^ (*key++ - ' ');
72         h %= PRIME2;
73         return (h);
74 }
75
76 /*
77  * Phong's linear congruential hash
78  */
79 #define dcharhash(h, c) ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c))
80
81 static u_int32_t
82 hash2(const void *keyarg, size_t len)
83 {
84         const u_char *e, *key;
85         u_int32_t h;
86         u_char c;
87
88         key = keyarg;
89         e = key + len;
90         for (h = 0; key != e;) {
91                 c = *key++;
92                 if (!c && key > 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  * OZ's original sdbm hash
107  */
108 static u_int32_t
109 hash3(const void *keyarg, size_t len)
110 {
111         const u_char *key;
112         size_t loop;
113         u_int32_t h;
114
115 #define HASHC   h = *key++ + 65599 * h
116
117         h = 0;
118         key = keyarg;
119         if (len > 0) {
120                 loop = (len + 8 - 1) >> 3;
121
122                 switch (len & (8 - 1)) {
123                 case 0:
124                         do {
125                                 HASHC;
126                                 /* FALLTHROUGH */
127                 case 7:
128                                 HASHC;
129                                 /* FALLTHROUGH */
130                 case 6:
131                                 HASHC;
132                                 /* FALLTHROUGH */
133                 case 5:
134                                 HASHC;
135                                 /* FALLTHROUGH */
136                 case 4:
137                                 HASHC;
138                                 /* FALLTHROUGH */
139                 case 3:
140                                 HASHC;
141                                 /* FALLTHROUGH */
142                 case 2:
143                                 HASHC;
144                                 /* FALLTHROUGH */
145                 case 1:
146                                 HASHC;
147                         } while (--loop);
148                 }
149         }
150         return (h);
151 }
152
153 /* Hash function from Chris Torek. */
154 static u_int32_t
155 hash4(const void *keyarg, size_t len)
156 {
157         const u_char *key;
158         size_t loop;
159         u_int32_t h;
160
161 #define HASH4a   h = (h << 5) - h + *key++;
162 #define HASH4b   h = (h << 5) + h + *key++;
163 #define HASH4 HASH4b
164
165         h = 0;
166         key = keyarg;
167         if (len > 0) {
168                 loop = (len + 8 - 1) >> 3;
169
170                 switch (len & (8 - 1)) {
171                 case 0:
172                         do {
173                                 HASH4;
174                                 /* FALLTHROUGH */
175                 case 7:
176                                 HASH4;
177                                 /* FALLTHROUGH */
178                 case 6:
179                                 HASH4;
180                                 /* FALLTHROUGH */
181                 case 5:
182                                 HASH4;
183                                 /* FALLTHROUGH */
184                 case 4:
185                                 HASH4;
186                                 /* FALLTHROUGH */
187                 case 3:
188                                 HASH4;
189                                 /* FALLTHROUGH */
190                 case 2:
191                                 HASH4;
192                                 /* FALLTHROUGH */
193                 case 1:
194                                 HASH4;
195                         } while (--loop);
196                 }
197         }
198         return (h);
199 }