]>
Commit | Line | Data |
---|---|---|
df4ef2ab | 1 | /* Implement simple hashing table with string based keys. |
a334319f | 2 | Copyright (C) 1994-1997, 2000, 2001, 2002 Free Software Foundation, Inc. |
41bdb6e2 | 3 | This file is part of the GNU C Library. |
0393dfd6 RM |
4 | Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, October 1994. |
5 | ||
a334319f UD |
6 | The GNU C Library is free software; you can redistribute it and/or |
7 | modify it under the terms of the GNU Lesser General Public | |
8 | License as published by the Free Software Foundation; either | |
9 | version 2.1 of the License, or (at your option) any later version. | |
0393dfd6 | 10 | |
a334319f | 11 | The GNU C Library is distributed in the hope that it will be useful, |
df4ef2ab | 12 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
a334319f UD |
13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
14 | Lesser General Public License for more details. | |
0393dfd6 | 15 | |
a334319f UD |
16 | You should have received a copy of the GNU Lesser General Public |
17 | License along with the GNU C Library; if not, write to the Free | |
18 | Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA | |
19 | 02111-1307 USA. */ | |
0393dfd6 RM |
20 | |
21 | #ifdef HAVE_CONFIG_H | |
22 | # include <config.h> | |
23 | #endif | |
24 | ||
25 | #include <stdio.h> | |
26 | #include <stdlib.h> | |
27 | #include <string.h> | |
28 | #include <sys/types.h> | |
29 | ||
30 | #if HAVE_OBSTACK | |
31 | # include <obstack.h> | |
32 | #else | |
33 | # include "obstack.h" | |
34 | #endif | |
35 | ||
36 | #ifdef HAVE_VALUES_H | |
37 | # include <values.h> | |
38 | #endif | |
39 | ||
40 | #include "simple-hash.h" | |
41 | ||
df4ef2ab | 42 | #define obstack_chunk_alloc malloc |
0393dfd6 RM |
43 | #define obstack_chunk_free free |
44 | ||
45 | #ifndef BITSPERBYTE | |
46 | # define BITSPERBYTE 8 | |
47 | #endif | |
48 | ||
0393dfd6 RM |
49 | #ifndef bcopy |
50 | # define bcopy(s, d, n) memcpy ((d), (s), (n)) | |
51 | #endif | |
52 | ||
a7b65cdc UD |
53 | #include "hashval.h" |
54 | ||
77e1d15a UD |
55 | extern void *xmalloc (size_t __n); |
56 | extern void *xcalloc (size_t __n, size_t __m); | |
0393dfd6 RM |
57 | |
58 | typedef struct hash_entry | |
59 | { | |
60 | unsigned long used; | |
61 | const void *key; | |
62 | size_t keylen; | |
63 | void *data; | |
64 | struct hash_entry *next; | |
65 | } | |
66 | hash_entry; | |
67 | ||
68 | /* Prototypes for local functions. */ | |
77e1d15a UD |
69 | static void insert_entry_2 (hash_table *htab, const void *key, size_t keylen, |
70 | unsigned long hval, size_t idx, void *data); | |
a352ab4c | 71 | static size_t lookup (const hash_table *htab, const void *key, size_t keylen, |
77e1d15a | 72 | unsigned long int hval); |
77e1d15a | 73 | static int is_prime (unsigned long int candidate); |
0393dfd6 RM |
74 | |
75 | ||
76 | int | |
77 | init_hash (htab, init_size) | |
78 | hash_table *htab; | |
79 | unsigned long int init_size; | |
80 | { | |
81 | /* We need the size to be a prime. */ | |
82 | init_size = next_prime (init_size); | |
83 | ||
84 | /* Initialize the data structure. */ | |
85 | htab->size = init_size; | |
86 | htab->filled = 0; | |
87 | htab->first = NULL; | |
77e1d15a | 88 | htab->table = (void *) xcalloc (init_size + 1, sizeof (hash_entry)); |
0393dfd6 RM |
89 | if (htab->table == NULL) |
90 | return -1; | |
91 | ||
0393dfd6 RM |
92 | obstack_init (&htab->mem_pool); |
93 | ||
94 | return 0; | |
95 | } | |
96 | ||
97 | ||
98 | int | |
99 | delete_hash (htab) | |
100 | hash_table *htab; | |
101 | { | |
102 | free (htab->table); | |
103 | obstack_free (&htab->mem_pool, NULL); | |
104 | return 0; | |
105 | } | |
106 | ||
107 | ||
108 | int | |
109 | insert_entry (htab, key, keylen, data) | |
110 | hash_table *htab; | |
111 | const void *key; | |
112 | size_t keylen; | |
113 | void *data; | |
114 | { | |
115 | unsigned long int hval = compute_hashval (key, keylen); | |
116 | hash_entry *table = (hash_entry *) htab->table; | |
117 | size_t idx = lookup (htab, key, keylen, hval); | |
118 | ||
119 | if (table[idx].used) | |
120 | /* We don't want to overwrite the old value. */ | |
121 | return -1; | |
122 | else | |
123 | { | |
124 | /* An empty bucket has been found. */ | |
125 | insert_entry_2 (htab, obstack_copy (&htab->mem_pool, key, keylen), | |
126 | keylen, hval, idx, data); | |
127 | return 0; | |
128 | } | |
129 | } | |
130 | ||
131 | static void | |
132 | insert_entry_2 (htab, key, keylen, hval, idx, data) | |
133 | hash_table *htab; | |
134 | const void *key; | |
135 | size_t keylen; | |
136 | unsigned long int hval; | |
137 | size_t idx; | |
138 | void *data; | |
139 | { | |
140 | hash_entry *table = (hash_entry *) htab->table; | |
141 | ||
142 | table[idx].used = hval; | |
143 | table[idx].key = key; | |
144 | table[idx].keylen = keylen; | |
145 | table[idx].data = data; | |
146 | ||
147 | /* List the new value in the list. */ | |
148 | if ((hash_entry *) htab->first == NULL) | |
149 | { | |
150 | table[idx].next = &table[idx]; | |
a334319f | 151 | *(hash_entry **) &htab->first = &table[idx]; |
0393dfd6 RM |
152 | } |
153 | else | |
154 | { | |
155 | table[idx].next = ((hash_entry *) htab->first)->next; | |
156 | ((hash_entry *) htab->first)->next = &table[idx]; | |
a334319f | 157 | *(hash_entry **) &htab->first = &table[idx]; |
0393dfd6 RM |
158 | } |
159 | ||
160 | ++htab->filled; | |
8e9b2075 | 161 | if (100 * htab->filled > 75 * htab->size) |
0393dfd6 | 162 | { |
8e9b2075 UD |
163 | /* Table is filled more than 75%. Resize the table. |
164 | Experiments have shown that for best performance, this threshold | |
165 | must lie between 40% and 85%. */ | |
0393dfd6 RM |
166 | unsigned long int old_size = htab->size; |
167 | ||
168 | htab->size = next_prime (htab->size * 2); | |
169 | htab->filled = 0; | |
170 | htab->first = NULL; | |
77e1d15a | 171 | htab->table = (void *) xcalloc (1 + htab->size, sizeof (hash_entry)); |
0393dfd6 RM |
172 | |
173 | for (idx = 1; idx <= old_size; ++idx) | |
174 | if (table[idx].used) | |
175 | insert_entry_2 (htab, table[idx].key, table[idx].keylen, | |
176 | table[idx].used, | |
cd0392d8 UD |
177 | lookup (htab, table[idx].key, table[idx].keylen, |
178 | table[idx].used), | |
0393dfd6 RM |
179 | table[idx].data); |
180 | ||
181 | free (table); | |
182 | } | |
183 | } | |
184 | ||
185 | ||
186 | int | |
187 | find_entry (htab, key, keylen, result) | |
a352ab4c | 188 | const hash_table *htab; |
0393dfd6 RM |
189 | const void *key; |
190 | size_t keylen; | |
191 | void **result; | |
192 | { | |
193 | hash_entry *table = (hash_entry *) htab->table; | |
194 | size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen)); | |
195 | ||
196 | if (table[idx].used == 0) | |
197 | return -1; | |
198 | ||
199 | *result = table[idx].data; | |
200 | return 0; | |
201 | } | |
202 | ||
203 | ||
204 | int | |
205 | set_entry (htab, key, keylen, newval) | |
206 | hash_table *htab; | |
207 | const void *key; | |
208 | size_t keylen; | |
209 | void *newval; | |
210 | { | |
211 | hash_entry *table = (hash_entry *) htab->table; | |
212 | size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen)); | |
213 | ||
214 | if (table[idx].used == 0) | |
215 | return -1; | |
216 | ||
217 | table[idx].data = newval; | |
218 | return 0; | |
219 | } | |
220 | ||
221 | ||
222 | int | |
223 | iterate_table (htab, ptr, key, keylen, data) | |
a352ab4c | 224 | const hash_table *htab; |
0393dfd6 RM |
225 | void **ptr; |
226 | const void **key; | |
227 | size_t *keylen; | |
228 | void **data; | |
229 | { | |
230 | if (*ptr == NULL) | |
231 | { | |
232 | if (htab->first == NULL) | |
233 | return -1; | |
234 | *ptr = (void *) ((hash_entry *) htab->first)->next; | |
235 | } | |
236 | else | |
237 | { | |
238 | if (*ptr == htab->first) | |
239 | return -1; | |
240 | *ptr = (void *) (((hash_entry *) *ptr)->next); | |
241 | } | |
242 | ||
243 | *key = ((hash_entry *) *ptr)->key; | |
244 | *keylen = ((hash_entry *) *ptr)->keylen; | |
245 | *data = ((hash_entry *) *ptr)->data; | |
246 | return 0; | |
247 | } | |
248 | ||
249 | ||
0393dfd6 RM |
250 | /* References: |
251 | [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986 | |
252 | [Knuth] The Art of Computer Programming, part3 (6.4) */ | |
253 | ||
254 | static size_t | |
cd0392d8 | 255 | lookup (htab, key, keylen, hval) |
a352ab4c | 256 | const hash_table *htab; |
0393dfd6 RM |
257 | const void *key; |
258 | size_t keylen; | |
259 | unsigned long int hval; | |
260 | { | |
261 | unsigned long int hash; | |
262 | size_t idx; | |
263 | hash_entry *table = (hash_entry *) htab->table; | |
264 | ||
265 | /* First hash function: simply take the modul but prevent zero. */ | |
266 | hash = 1 + hval % htab->size; | |
267 | ||
268 | idx = hash; | |
269 | ||
270 | if (table[idx].used) | |
271 | { | |
272 | if (table[idx].used == hval && table[idx].keylen == keylen | |
273 | && memcmp (table[idx].key, key, keylen) == 0) | |
274 | return idx; | |
275 | ||
276 | /* Second hash function as suggested in [Knuth]. */ | |
277 | hash = 1 + hval % (htab->size - 2); | |
278 | ||
279 | do | |
280 | { | |
281 | if (idx <= hash) | |
282 | idx = htab->size + idx - hash; | |
283 | else | |
284 | idx -= hash; | |
285 | ||
286 | /* If entry is found use it. */ | |
287 | if (table[idx].used == hval && table[idx].keylen == keylen | |
288 | && memcmp (table[idx].key, key, keylen) == 0) | |
289 | return idx; | |
290 | } | |
291 | while (table[idx].used); | |
292 | } | |
293 | return idx; | |
294 | } | |
295 | ||
296 | ||
a7b65cdc | 297 | unsigned long int |
0393dfd6 RM |
298 | next_prime (seed) |
299 | unsigned long int seed; | |
300 | { | |
301 | /* Make it definitely odd. */ | |
302 | seed |= 1; | |
303 | ||
304 | while (!is_prime (seed)) | |
305 | seed += 2; | |
306 | ||
307 | return seed; | |
308 | } | |
309 | ||
310 | ||
311 | static int | |
312 | is_prime (candidate) | |
313 | unsigned long int candidate; | |
314 | { | |
315 | /* No even number and none less than 10 will be passed here. */ | |
316 | unsigned long int divn = 3; | |
317 | unsigned long int sq = divn * divn; | |
318 | ||
319 | while (sq < candidate && candidate % divn != 0) | |
320 | { | |
321 | ++divn; | |
322 | sq += 4 * divn; | |
323 | ++divn; | |
324 | } | |
325 | ||
326 | return candidate % divn != 0; | |
327 | } |