← Back to branch summary

~ubuntu-branches/ubuntu/maverick/evolution-data-server/maverick-proposed

« back to all changes in this revision

Viewing changes to libdb/hash/hash_func.c

  • Committer: Bazaar Package Importer
  • Author(s): Didier Roche
  • Date: 2010-05-17 17:02:06 UTC
  • mfrom: (1.1.79 upstream) (1.6.12 experimental)
  • Revision ID: james.westby@ubuntu.com-20100517170206-4ufr52vwrhh26yh0
Tags: 2.30.1-1ubuntu1
https://launchpad.net/bugs/42199
https://launchpad.net/bugs/229669
https://launchpad.net/bugs/173703
https://launchpad.net/bugs/360344
https://launchpad.net/bugs/508494
* Merge from debian experimental. Remaining change:
  (LP: #42199, #229669, #173703, #360344, #508494)
  + debian/control:
    - add Vcs-Bzr tag
    - don't use libgnome
    - Use Breaks instead of Conflicts against evolution 2.25 and earlier.
  + debian/evolution-data-server.install,
    debian/patches/45_libcamel_providers_version.patch:
    - use the upstream versioning, not a Debian-specific one 
  + debian/libedata-book1.2-dev.install, debian/libebackend-1.2-dev.install,
    debian/libcamel1.2-dev.install, debian/libedataserverui1.2-dev.install:
    - install html documentation
  + debian/rules:
    - don't build documentation it's shipped with the tarball

Show diffs side-by-side

added added

removed removed

Lines of Context:
libdb/hash/hash_func.c
1
 
/*-
2
 
 * See the file LICENSE for redistribution information.
3
 
 *
4
 
 * Copyright (c) 1996-2002
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$";
47
 
#endif /* not lint */
48
 
 
49
 
#ifndef NO_SYSTEM_INCLUDES
50
 
#include <sys/types.h>
51
 
#endif
52
 
 
53
 
#include "db_int.h"
54
 
 
55
 
/*
56
 
 * __ham_func2 --
57
 
 *      Phong Vo's linear congruential hash.
58
 
 *
59
 
 * PUBLIC: u_int32_t __ham_func2 __P((DB *, const void *, u_int32_t));
60
 
 */
61
 
#define DCHARHASH(h, c) ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c))
62
 
 
63
 
u_int32_t
64
 
__ham_func2(dbp, key, len)
65
 
        DB *dbp;
66
 
        const void *key;
67
 
        u_int32_t len;
68
 
{
69
 
        const u_int8_t *e, *k;
70
 
        u_int32_t h;
71
 
        u_int8_t c;
72
 
 
73
 
        if (dbp != NULL)
74
 
                COMPQUIET(dbp, NULL);
75
 
 
76
 
        k = key;
77
 
        e = k + len;
78
 
        for (h = 0; k != e;) {
79
 
                c = *k++;
80
 
                if (!c && k > e)
81
 
                        break;
82
 
                DCHARHASH(h, c);
83
 
        }
84
 
        return (h);
85
 
}
86
 
 
87
 
/*
88
 
 * __ham_func3 --
89
 
 *      Ozan Yigit's original sdbm hash.
90
 
 *
91
 
 * Ugly, but fast.  Break the string up into 8 byte units.  On the first time
92
 
 * through the loop get the "leftover bytes" (strlen % 8).  On every other
93
 
 * iteration, perform 8 HASHC's so we handle all 8 bytes.  Essentially, this
94
 
 * saves us 7 cmp & branch instructions.
95
 
 *
96
 
 * PUBLIC: u_int32_t __ham_func3 __P((DB *, const void *, u_int32_t));
97
 
 */
98
 
u_int32_t
99
 
__ham_func3(dbp, key, len)
100
 
        DB *dbp;
101
 
        const void *key;
102
 
        u_int32_t len;
103
 
{
104
 
        const u_int8_t *k;
105
 
        u_int32_t n, loop;
106
 
 
107
 
        if (dbp != NULL)
108
 
                COMPQUIET(dbp, NULL);
109
 
 
110
 
        if (len == 0)
111
 
                return (0);
112
 
 
113
 
#define HASHC   n = *k++ + 65599 * n
114
 
        n = 0;
115
 
        k = key;
116
 
 
117
 
        loop = (len + 8 - 1) >> 3;
118
 
        switch (len & (8 - 1)) {
119
 
        case 0:
120
 
                do {
121
 
                        HASHC;
122
 
        case 7:
123
 
                        HASHC;
124
 
        case 6:
125
 
                        HASHC;
126
 
        case 5:
127
 
                        HASHC;
128
 
        case 4:
129
 
                        HASHC;
130
 
        case 3:
131
 
                        HASHC;
132
 
        case 2:
133
 
                        HASHC;
134
 
        case 1:
135
 
                        HASHC;
136
 
                } while (--loop);
137
 
        }
138
 
        return (n);
139
 
}
140
 
 
141
 
/*
142
 
 * __ham_func4 --
143
 
 *      Chris Torek's hash function.  Although this function performs only
144
 
 *      slightly worse than __ham_func5 on strings, it performs horribly on
145
 
 *      numbers.
146
 
 *
147
 
 * PUBLIC: u_int32_t __ham_func4 __P((DB *, const void *, u_int32_t));
148
 
 */
149
 
u_int32_t
150
 
__ham_func4(dbp, key, len)
151
 
        DB *dbp;
152
 
        const void *key;
153
 
        u_int32_t len;
154
 
{
155
 
        const u_int8_t *k;
156
 
        u_int32_t h, loop;
157
 
 
158
 
        if (dbp != NULL)
159
 
                COMPQUIET(dbp, NULL);
160
 
 
161
 
        if (len == 0)
162
 
                return (0);
163
 
 
164
 
#define HASH4a  h = (h << 5) - h + *k++;
165
 
#define HASH4b  h = (h << 5) + h + *k++;
166
 
#define HASH4   HASH4b
167
 
        h = 0;
168
 
        k = key;
169
 
 
170
 
        loop = (len + 8 - 1) >> 3;
171
 
        switch (len & (8 - 1)) {
172
 
        case 0:
173
 
                do {
174
 
                        HASH4;
175
 
        case 7:
176
 
                        HASH4;
177
 
        case 6:
178
 
                        HASH4;
179
 
        case 5:
180
 
                        HASH4;
181
 
        case 4:
182
 
                        HASH4;
183
 
        case 3:
184
 
                        HASH4;
185
 
        case 2:
186
 
                        HASH4;
187
 
        case 1:
188
 
                        HASH4;
189
 
                } while (--loop);
190
 
        }
191
 
        return (h);
192
 
}
193
 
 
194
 
/*
195
 
 * Fowler/Noll/Vo hash
196
 
 *
197
 
 * The basis of the hash algorithm was taken from an idea sent by email to the
198
 
 * IEEE Posix P1003.2 mailing list from Phong Vo (kpv@research.att.com) and
199
 
 * Glenn Fowler (gsf@research.att.com).  Landon Curt Noll (chongo@toad.com)
200
 
 * later improved on their algorithm.
201
 
 *
202
 
 * The magic is in the interesting relationship between the special prime
203
 
 * 16777619 (2^24 + 403) and 2^32 and 2^8.
204
 
 *
205
 
 * This hash produces the fewest collisions of any function that we've seen so
206
 
 * far, and works well on both numbers and strings.
207
 
 *
208
 
 * PUBLIC: u_int32_t __ham_func5 __P((DB *, const void *, u_int32_t));
209
 
 */
210
 
u_int32_t
211
 
__ham_func5(dbp, key, len)
212
 
        DB *dbp;
213
 
        const void *key;
214
 
        u_int32_t len;
215
 
{
216
 
        const u_int8_t *k, *e;
217
 
        u_int32_t h;
218
 
 
219
 
        if (dbp != NULL)
220
 
                COMPQUIET(dbp, NULL);
221
 
 
222
 
        k = key;
223
 
        e = k + len;
224
 
        for (h = 0; k < e; ++k) {
225
 
                h *= 16777619;
226
 
                h ^= *k;
227
 
        }
228
 
        return (h);
229
 
}
230
 
 
231
 
/*
232
 
 * __ham_test --
233
 
 *
234
 
 * PUBLIC: u_int32_t __ham_test __P((DB *, const void *, u_int32_t));
235
 
 */
236
 
u_int32_t
237
 
__ham_test(dbp, key, len)
238
 
        DB *dbp;
239
 
        const void *key;
240
 
        u_int32_t len;
241
 
{
242
 
        COMPQUIET(dbp, NULL);
243
 
        COMPQUIET(len, 0);
244
 
        return ((u_int32_t)*(char *)key);
245
 
}