OpenCores
URL https://opencores.org/ocsvn/openrisc_me/openrisc_me/trunk

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [newlib-1.18.0/] [newlib/] [libc/] [search/] [hash_func.c] - Blame information for rev 207

Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.