Asterisk - The Open Source Telephony Project GIT-master-2de1a68
hash_func.c
Go to the documentation of this file.
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. 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)
38static char sccsid[] = "@(#)hash_func.c 8.2 (Berkeley) 2/21/94";
39#endif /* LIBC_SCCS and not lint */
40
41#include <sys/types.h>
42
43#include "../include/db.h"
44#include "hash.h"
45#include "page.h"
46#include "extern.h"
47
48/* only one of these can be defined */
49/* #define HASH1_EJB 1 */
50/* #define HASH2_PHONG 1 */
51/* #define HASH3_SDBM 1 */
52#define HASH4_TOREK 1
53
54static u_int32_t hashfunc __P((const void *, size_t));
55
56/* Global default hash function */
57u_int32_t (*__default_hash) __P((const void *, size_t)) = hashfunc;
58
59/*
60 * HASH FUNCTIONS
61 *
62 * Assume that we've already split the bucket to which this key hashes,
63 * calculate that bucket, and check that in fact we did already split it.
64 *
65 * This came from ejb's hsearch.
66 */
67
68#ifdef HASH1_EJB
69
70#define PRIME1 37
71#define PRIME2 1048583
72
73static u_int32_t
74hashfunc(keyarg, len)
75 const void *keyarg;
76 register size_t len;
77{
78 register const u_char *key;
79 register u_int32_t h;
80
81 /* Convert string to integer */
82 for (key = keyarg, h = 0; len--;)
83 h = h * PRIME1 ^ (*key++ - ' ');
84 h %= PRIME2;
85 return (h);
86}
87
88#endif
89
90#ifdef HASH2_PHONG
91/*
92 * Phong's linear congruential hash
93 */
94#define dcharhash(h, c) ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c))
95
96static u_int32_t
97hashfunc(keyarg, len)
98 const void *keyarg;
99 size_t len;
100{
101 register const u_char *e, *key;
102 register u_int32_t h;
103 register u_char c;
104
105 key = keyarg;
106 e = key + len;
107 for (h = 0; key != e;) {
108 c = *key++;
109 if (!c && key > e)
110 break;
111 dcharhash(h, c);
112 }
113 return (h);
114}
115#endif
116
117#ifdef HASH3_SDBM
118/*
119 * This is INCREDIBLY ugly, but fast. We break the string up into 8 byte
120 * units. On the first time through the loop we get the "leftover bytes"
121 * (strlen % 8). On every other iteration, we perform 8 HASHC's so we handle
122 * all 8 bytes. Essentially, this saves us 7 cmp & branch instructions. If
123 * this routine is heavily used enough, it's worth the ugly coding.
124 *
125 * OZ's original sdbm hash
126 */
127static u_int32_t
128hashfunc(keyarg, len)
129 const void *keyarg;
130 register size_t len;
131{
132 register const u_char *key;
133 register size_t loop;
134 register u_int32_t h;
135
136#define HASHC h = *key++ + 65599 * h
137
138 h = 0;
139 key = keyarg;
140 if (len > 0) {
141 loop = (len + 8 - 1) >> 3;
142
143 switch (len & (8 - 1)) {
144 case 0:
145 do {
146 HASHC;
147 /* FALLTHROUGH */
148 case 7:
149 HASHC;
150 /* FALLTHROUGH */
151 case 6:
152 HASHC;
153 /* FALLTHROUGH */
154 case 5:
155 HASHC;
156 /* FALLTHROUGH */
157 case 4:
158 HASHC;
159 /* FALLTHROUGH */
160 case 3:
161 HASHC;
162 /* FALLTHROUGH */
163 case 2:
164 HASHC;
165 /* FALLTHROUGH */
166 case 1:
167 HASHC;
168 } while (--loop);
169 }
170 }
171 return (h);
172}
173#endif
174
175#ifdef HASH4_TOREK
176/* Hash function from Chris Torek. */
177static u_int32_t
178hashfunc(keyarg, len)
179 const void *keyarg;
180 register size_t len;
181{
182 register const u_char *key;
183 register size_t loop;
184 register u_int32_t h;
185
186#define HASH4a h = (h << 5) - h + *key++;
187#define HASH4b h = (h << 5) + h + *key++;
188#define HASH4 HASH4b
189
190 h = 0;
191 key = keyarg;
192 if (len > 0) {
193 loop = (len + 8 - 1) >> 3;
194
195 switch (len & (8 - 1)) {
196 case 0:
197 do {
198 HASH4;
199 /* FALLTHROUGH */
200 case 7:
201 HASH4;
202 /* FALLTHROUGH */
203 case 6:
204 HASH4;
205 /* FALLTHROUGH */
206 case 5:
207 HASH4;
208 /* FALLTHROUGH */
209 case 4:
210 HASH4;
211 /* FALLTHROUGH */
212 case 3:
213 HASH4;
214 /* FALLTHROUGH */
215 case 2:
216 HASH4;
217 /* FALLTHROUGH */
218 case 1:
219 HASH4;
220 } while (--loop);
221 }
222 }
223 return (h);
224}
225#endif
static int len(struct ast_channel *chan, const char *cmd, char *data, char *buf, size_t buflen)
static u_int32_t hashfunc(void *keyarg, size_t len) const
Definition: hash_func.c:178
#define HASH4
static u_int32_t hashfunc __P((const void *, size_t))
unsigned int u_int32_t
static struct test_val c