← Back to branch summary

~ubuntu-branches/ubuntu/edgy/rpm/edgy

« back to all changes in this revision

Viewing changes to db/hash/hash_func.c

  • Committer: Bazaar Package Importer
  • Author(s): Joey Hess
  • Date: 2002-01-22 20:56:57 UTC
  • Revision ID: james.westby@ubuntu.com-20020122205657-l74j50mr9z8ofcl5
Tags: upstream-4.0.3
Import upstream version 4.0.3

Show diffs side-by-side

added added

removed removed

Lines of Context:
db/hash/hash_func.c
 
1
/*-
 
2
 * See the file LICENSE for redistribution information.
 
3
 *
 
4
 * Copyright (c) 1996-2001
 
5
 *      Sleepycat Software.  All rights reserved.
 
6
 */
 
7
/*
 
8
 * Copyright (c) 1990, 1993
 
9
 *      Margo Seltzer.  All rights reserved.
 
10
 */
 
11
/*
 
12
 * Copyright (c) 1990, 1993
 
13
 *      The Regents of the University of California.  All rights reserved.
 
14
 *
 
15
 * This code is derived from software contributed to Berkeley by
 
16
 * Margo Seltzer.
 
17
 *
 
18
 * Redistribution and use in source and binary forms, with or without
 
19
 * modification, are permitted provided that the following conditions
 
20
 * are met:
 
21
 * 1. Redistributions of source code must retain the above copyright
 
22
 *    notice, this list of conditions and the following disclaimer.
 
23
 * 2. Redistributions in binary form must reproduce the above copyright
 
24
 *    notice, this list of conditions and the following disclaimer in the
 
25
 *    documentation and/or other materials provided with the distribution.
 
26
 * 3. Neither the name of the University nor the names of its contributors
 
27
 *    may be used to endorse or promote products derived from this software
 
28
 *    without specific prior written permission.
 
29
 *
 
30
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 
31
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 
32
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 
33
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 
34
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 
35
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 
36
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 
37
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 
38
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 
39
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 
40
 * SUCH DAMAGE.
 
41
 */
 
42
 
 
43
#include "db_config.h"
 
44
 
 
45
#ifndef lint
 
46
static const char revid[] = "$Id: hash_func.c,v 11.9 2001/04/10 20:44:06 bostic Exp $";
 
47
#endif /* not lint */
 
48
 
 
49
#ifndef NO_SYSTEM_INCLUDES
 
50
#include <sys/types.h>
 
51
#endif
 
52
 
 
53
#include "db_int.h"
 
54
#include "db_page.h"
 
55
#include "hash.h"
 
56
 
 
57
/*
 
58
 * __ham_func2 --
 
59
 *      Phong Vo's linear congruential hash.
 
60
 *
 
61
 * PUBLIC: u_int32_t __ham_func2 __P((DB *, const void *, u_int32_t));
 
62
 */
 
63
#define DCHARHASH(h, c) ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c))
 
64
 
 
65
u_int32_t
 
66
__ham_func2(dbp, key, len)
 
67
        DB *dbp;
 
68
        const void *key;
 
69
        u_int32_t len;
 
70
{
 
71
        const u_int8_t *e, *k;
 
72
        u_int32_t h;
 
73
        u_int8_t c;
 
74
 
 
75
        if (dbp != NULL)
 
76
                COMPQUIET(dbp, NULL);
 
77
 
 
78
        k = key;
 
79
        e = k + len;
 
80
        for (h = 0; k != e;) {
 
81
                c = *k++;
 
82
                if (!c && k > e)
 
83
                        break;
 
84
                DCHARHASH(h, c);
 
85
        }
 
86
        return (h);
 
87
}
 
88
 
 
89
/*
 
90
 * __ham_func3 --
 
91
 *      Ozan Yigit's original sdbm hash.
 
92
 *
 
93
 * Ugly, but fast.  Break the string up into 8 byte units.  On the first time
 
94
 * through the loop get the "leftover bytes" (strlen % 8).  On every other
 
95
 * iteration, perform 8 HASHC's so we handle all 8 bytes.  Essentially, this
 
96
 * saves us 7 cmp & branch instructions.
 
97
 *
 
98
 * PUBLIC: u_int32_t __ham_func3 __P((DB *, const void *, u_int32_t));
 
99
 */
 
100
u_int32_t
 
101
__ham_func3(dbp, key, len)
 
102
        DB *dbp;
 
103
        const void *key;
 
104
        u_int32_t len;
 
105
{
 
106
        const u_int8_t *k;
 
107
        u_int32_t n, loop;
 
108
 
 
109
        if (dbp != NULL)
 
110
                COMPQUIET(dbp, NULL);
 
111
 
 
112
        if (len == 0)
 
113
                return (0);
 
114
 
 
115
#define HASHC   n = *k++ + 65599 * n
 
116
        n = 0;
 
117
        k = key;
 
118
 
 
119
        loop = (len + 8 - 1) >> 3;
 
120
        switch (len & (8 - 1)) {
 
121
        case 0:
 
122
                do {
 
123
                        HASHC;
 
124
        case 7:
 
125
                        HASHC;
 
126
        case 6:
 
127
                        HASHC;
 
128
        case 5:
 
129
                        HASHC;
 
130
        case 4:
 
131
                        HASHC;
 
132
        case 3:
 
133
                        HASHC;
 
134
        case 2:
 
135
                        HASHC;
 
136
        case 1:
 
137
                        HASHC;
 
138
                } while (--loop);
 
139
        }
 
140
        return (n);
 
141
}
 
142
 
 
143
/*
 
144
 * __ham_func4 --
 
145
 *      Chris Torek's hash function.  Although this function performs only
 
146
 *      slightly worse than __ham_func5 on strings, it performs horribly on
 
147
 *      numbers.
 
148
 *
 
149
 * PUBLIC: u_int32_t __ham_func4 __P((DB *, const void *, u_int32_t));
 
150
 */
 
151
u_int32_t
 
152
__ham_func4(dbp, key, len)
 
153
        DB *dbp;
 
154
        const void *key;
 
155
        u_int32_t len;
 
156
{
 
157
        const u_int8_t *k;
 
158
        u_int32_t h, loop;
 
159
 
 
160
        if (dbp != NULL)
 
161
                COMPQUIET(dbp, NULL);
 
162
 
 
163
        if (len == 0)
 
164
                return (0);
 
165
 
 
166
#define HASH4a  h = (h << 5) - h + *k++;
 
167
#define HASH4b  h = (h << 5) + h + *k++;
 
168
#define HASH4   HASH4b
 
169
        h = 0;
 
170
        k = key;
 
171
 
 
172
        loop = (len + 8 - 1) >> 3;
 
173
        switch (len & (8 - 1)) {
 
174
        case 0:
 
175
                do {
 
176
                        HASH4;
 
177
        case 7:
 
178
                        HASH4;
 
179
        case 6:
 
180
                        HASH4;
 
181
        case 5:
 
182
                        HASH4;
 
183
        case 4:
 
184
                        HASH4;
 
185
        case 3:
 
186
                        HASH4;
 
187
        case 2:
 
188
                        HASH4;
 
189
        case 1:
 
190
                        HASH4;
 
191
                } while (--loop);
 
192
        }
 
193
        return (h);
 
194
}
 
195
 
 
196
/*
 
197
 * Fowler/Noll/Vo hash
 
198
 *
 
199
 * The basis of the hash algorithm was taken from an idea sent by email to the
 
200
 * IEEE Posix P1003.2 mailing list from Phong Vo (kpv@research.att.com) and
 
201
 * Glenn Fowler (gsf@research.att.com).  Landon Curt Noll (chongo@toad.com)
 
202
 * later improved on their algorithm.
 
203
 *
 
204
 * The magic is in the interesting relationship between the special prime
 
205
 * 16777619 (2^24 + 403) and 2^32 and 2^8.
 
206
 *
 
207
 * This hash produces the fewest collisions of any function that we've seen so
 
208
 * far, and works well on both numbers and strings.
 
209
 *
 
210
 * PUBLIC: u_int32_t __ham_func5 __P((DB *, const void *, u_int32_t));
 
211
 */
 
212
u_int32_t
 
213
__ham_func5(dbp, key, len)
 
214
        DB *dbp;
 
215
        const void *key;
 
216
        u_int32_t len;
 
217
{
 
218
        const u_int8_t *k, *e;
 
219
        u_int32_t h;
 
220
 
 
221
        if (dbp != NULL)
 
222
                COMPQUIET(dbp, NULL);
 
223
 
 
224
        k = key;
 
225
        e = k + len;
 
226
        for (h = 0; k < e; ++k) {
 
227
                h *= 16777619;
 
228
                h ^= *k;
 
229
        }
 
230
        return (h);
 
231
}
 
232
 
 
233
/*
 
234
 * __ham_test --
 
235
 *
 
236
 * PUBLIC: u_int32_t __ham_test __P((DB *, const void *, u_int32_t));
 
237
 */
 
238
u_int32_t
 
239
__ham_test(dbp, key, len)
 
240
        DB *dbp;
 
241
        const void *key;
 
242
        u_int32_t len;
 
243
{
 
244
        COMPQUIET(dbp, NULL);
 
245
        COMPQUIET(len, 0);
 
246
        return ((u_int32_t)*(char *)key);
 
247
}