Commit | Line | Data |
---|---|---|
e2eaf477 | 1 | /* An expandable hash tables datatype. |
bb6a587d DD |
2 | Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004 |
3 | Free Software Foundation, Inc. | |
e2eaf477 ILT |
4 | Contributed by Vladimir Makarov (vmakarov@cygnus.com). |
5 | ||
6 | This file is part of the libiberty library. | |
7 | Libiberty is free software; you can redistribute it and/or | |
8 | modify it under the terms of the GNU Library General Public | |
9 | License as published by the Free Software Foundation; either | |
10 | version 2 of the License, or (at your option) any later version. | |
11 | ||
12 | Libiberty is distributed in the hope that it will be useful, | |
13 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
15 | Library General Public License for more details. | |
16 | ||
17 | You should have received a copy of the GNU Library General Public | |
18 | License along with libiberty; see the file COPYING.LIB. If | |
19 | not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, | |
20 | Boston, MA 02111-1307, USA. */ | |
21 | ||
22 | /* This package implements basic hash table functionality. It is possible | |
23 | to search for an entry, create an entry and destroy an entry. | |
24 | ||
25 | Elements in the table are generic pointers. | |
26 | ||
27 | The size of the table is not fixed; if the occupancy of the table | |
28 | grows too high the hash table will be expanded. | |
29 | ||
30 | The abstract data implementation is based on generalized Algorithm D | |
31 | from Knuth's book "The art of computer programming". Hash table is | |
32 | expanded by creation of new hash table and transferring elements from | |
33 | the old table to the new table. */ | |
34 | ||
35 | #ifdef HAVE_CONFIG_H | |
36 | #include "config.h" | |
37 | #endif | |
38 | ||
39 | #include <sys/types.h> | |
40 | ||
41 | #ifdef HAVE_STDLIB_H | |
42 | #include <stdlib.h> | |
43 | #endif | |
5c82d20a ZW |
44 | #ifdef HAVE_STRING_H |
45 | #include <string.h> | |
46 | #endif | |
5f73c378 DD |
47 | #ifdef HAVE_MALLOC_H |
48 | #include <malloc.h> | |
49 | #endif | |
bb6a587d DD |
50 | #ifdef HAVE_LIMITS_H |
51 | #include <limits.h> | |
52 | #endif | |
53 | #ifdef HAVE_STDINT_H | |
54 | #include <stdint.h> | |
55 | #endif | |
5f73c378 | 56 | |
e2eaf477 ILT |
57 | #include <stdio.h> |
58 | ||
59 | #include "libiberty.h" | |
bb6a587d | 60 | #include "ansidecl.h" |
e2eaf477 ILT |
61 | #include "hashtab.h" |
62 | ||
bb6a587d DD |
63 | #ifndef CHAR_BIT |
64 | #define CHAR_BIT 8 | |
65 | #endif | |
66 | ||
e2eaf477 ILT |
67 | /* This macro defines reserved value for empty table entry. */ |
68 | ||
e0f3df8f | 69 | #define EMPTY_ENTRY ((PTR) 0) |
e2eaf477 ILT |
70 | |
71 | /* This macro defines reserved value for table entry which contained | |
72 | a deleted element. */ | |
73 | ||
e0f3df8f | 74 | #define DELETED_ENTRY ((PTR) 1) |
e2eaf477 | 75 | |
bb6a587d DD |
76 | static unsigned int higher_prime_index PARAMS ((unsigned long)); |
77 | static hashval_t htab_mod_1 PARAMS ((hashval_t, hashval_t, hashval_t, int)); | |
78 | static hashval_t htab_mod PARAMS ((hashval_t, htab_t)); | |
79 | static hashval_t htab_mod_m2 PARAMS ((hashval_t, htab_t)); | |
eb383413 L |
80 | static hashval_t hash_pointer PARAMS ((const void *)); |
81 | static int eq_pointer PARAMS ((const void *, const void *)); | |
99a4c1bd | 82 | static int htab_expand PARAMS ((htab_t)); |
e0f3df8f | 83 | static PTR *find_empty_slot_for_expand PARAMS ((htab_t, hashval_t)); |
eb383413 L |
84 | |
85 | /* At some point, we could make these be NULL, and modify the | |
86 | hash-table routines to handle NULL specially; that would avoid | |
87 | function-call overhead for the common case of hashing pointers. */ | |
88 | htab_hash htab_hash_pointer = hash_pointer; | |
89 | htab_eq htab_eq_pointer = eq_pointer; | |
90 | ||
bb6a587d DD |
91 | /* Table of primes and multiplicative inverses. |
92 | ||
93 | Note that these are not minimally reduced inverses. Unlike when generating | |
94 | code to divide by a constant, we want to be able to use the same algorithm | |
95 | all the time. All of these inverses (are implied to) have bit 32 set. | |
96 | ||
97 | For the record, here's the function that computed the table; it's a | |
98 | vastly simplified version of the function of the same name from gcc. */ | |
99 | ||
100 | #if 0 | |
101 | unsigned int | |
102 | ceil_log2 (unsigned int x) | |
103 | { | |
104 | int i; | |
105 | for (i = 31; i >= 0 ; --i) | |
106 | if (x > (1u << i)) | |
107 | return i+1; | |
108 | abort (); | |
109 | } | |
e2eaf477 | 110 | |
bb6a587d DD |
111 | unsigned int |
112 | choose_multiplier (unsigned int d, unsigned int *mlp, unsigned char *shiftp) | |
113 | { | |
114 | unsigned long long mhigh; | |
115 | double nx; | |
116 | int lgup, post_shift; | |
117 | int pow, pow2; | |
118 | int n = 32, precision = 32; | |
119 | ||
120 | lgup = ceil_log2 (d); | |
121 | pow = n + lgup; | |
122 | pow2 = n + lgup - precision; | |
123 | ||
124 | nx = ldexp (1.0, pow) + ldexp (1.0, pow2); | |
125 | mhigh = nx / d; | |
126 | ||
127 | *shiftp = lgup - 1; | |
128 | *mlp = mhigh; | |
129 | return mhigh >> 32; | |
130 | } | |
131 | #endif | |
132 | ||
133 | struct prime_ent | |
134 | { | |
135 | hashval_t prime; | |
136 | hashval_t inv; | |
137 | hashval_t inv_m2; /* inverse of prime-2 */ | |
138 | hashval_t shift; | |
139 | }; | |
140 | ||
141 | static struct prime_ent const prime_tab[] = { | |
142 | { 7, 0x24924925, 0x9999999b, 2 }, | |
143 | { 13, 0x3b13b13c, 0x745d1747, 3 }, | |
144 | { 31, 0x08421085, 0x1a7b9612, 4 }, | |
145 | { 61, 0x0c9714fc, 0x15b1e5f8, 5 }, | |
146 | { 127, 0x02040811, 0x0624dd30, 6 }, | |
147 | { 251, 0x05197f7e, 0x073260a5, 7 }, | |
148 | { 509, 0x01824366, 0x02864fc8, 8 }, | |
149 | { 1021, 0x00c0906d, 0x014191f7, 9 }, | |
150 | { 2039, 0x0121456f, 0x0161e69e, 10 }, | |
151 | { 4093, 0x00300902, 0x00501908, 11 }, | |
152 | { 8191, 0x00080041, 0x00180241, 12 }, | |
153 | { 16381, 0x000c0091, 0x00140191, 13 }, | |
154 | { 32749, 0x002605a5, 0x002a06e6, 14 }, | |
155 | { 65521, 0x000f00e2, 0x00110122, 15 }, | |
156 | { 131071, 0x00008001, 0x00018003, 16 }, | |
157 | { 262139, 0x00014002, 0x0001c004, 17 }, | |
158 | { 524287, 0x00002001, 0x00006001, 18 }, | |
159 | { 1048573, 0x00003001, 0x00005001, 19 }, | |
160 | { 2097143, 0x00004801, 0x00005801, 20 }, | |
161 | { 4194301, 0x00000c01, 0x00001401, 21 }, | |
162 | { 8388593, 0x00001e01, 0x00002201, 22 }, | |
163 | { 16777213, 0x00000301, 0x00000501, 23 }, | |
164 | { 33554393, 0x00001381, 0x00001481, 24 }, | |
165 | { 67108859, 0x00000141, 0x000001c1, 25 }, | |
166 | { 134217689, 0x000004e1, 0x00000521, 26 }, | |
167 | { 268435399, 0x00000391, 0x000003b1, 27 }, | |
168 | { 536870909, 0x00000019, 0x00000029, 28 }, | |
169 | { 1073741789, 0x0000008d, 0x00000095, 29 }, | |
170 | { 2147483647, 0x00000003, 0x00000007, 30 }, | |
171 | /* Avoid "decimal constant so large it is unsigned" for 4294967291. */ | |
172 | { 0xfffffffb, 0x00000006, 0x00000008, 31 } | |
173 | }; | |
174 | ||
175 | /* The following function returns an index into the above table of the | |
176 | nearest prime number which is greater than N, and near a power of two. */ | |
177 | ||
178 | static unsigned int | |
179 | higher_prime_index (n) | |
b4fe2683 | 180 | unsigned long n; |
e2eaf477 | 181 | { |
bb6a587d DD |
182 | unsigned int low = 0; |
183 | unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]); | |
5ca0f83d DD |
184 | |
185 | while (low != high) | |
186 | { | |
bb6a587d DD |
187 | unsigned int mid = low + (high - low) / 2; |
188 | if (n > prime_tab[mid].prime) | |
5ca0f83d DD |
189 | low = mid + 1; |
190 | else | |
191 | high = mid; | |
192 | } | |
193 | ||
194 | /* If we've run out of primes, abort. */ | |
bb6a587d | 195 | if (n > prime_tab[low].prime) |
5ca0f83d DD |
196 | { |
197 | fprintf (stderr, "Cannot find prime bigger than %lu\n", n); | |
198 | abort (); | |
199 | } | |
200 | ||
bb6a587d | 201 | return low; |
e2eaf477 ILT |
202 | } |
203 | ||
eb383413 L |
204 | /* Returns a hash code for P. */ |
205 | ||
206 | static hashval_t | |
207 | hash_pointer (p) | |
e0f3df8f | 208 | const PTR p; |
eb383413 L |
209 | { |
210 | return (hashval_t) ((long)p >> 3); | |
211 | } | |
212 | ||
213 | /* Returns non-zero if P1 and P2 are equal. */ | |
214 | ||
215 | static int | |
216 | eq_pointer (p1, p2) | |
e0f3df8f HPN |
217 | const PTR p1; |
218 | const PTR p2; | |
eb383413 L |
219 | { |
220 | return p1 == p2; | |
221 | } | |
222 | ||
fe046a17 DD |
223 | /* Return the current size of given hash table. */ |
224 | ||
225 | inline size_t | |
226 | htab_size (htab) | |
227 | htab_t htab; | |
228 | { | |
229 | return htab->size; | |
230 | } | |
231 | ||
232 | /* Return the current number of elements in given hash table. */ | |
233 | ||
234 | inline size_t | |
235 | htab_elements (htab) | |
236 | htab_t htab; | |
237 | { | |
238 | return htab->n_elements - htab->n_deleted; | |
239 | } | |
240 | ||
bb6a587d DD |
241 | /* Return X % Y. */ |
242 | ||
243 | static inline hashval_t | |
244 | htab_mod_1 (x, y, inv, shift) | |
245 | hashval_t x, y, inv; | |
246 | int shift; | |
247 | { | |
248 | /* The multiplicative inverses computed above are for 32-bit types, and | |
249 | requires that we be able to compute a highpart multiply. */ | |
250 | #ifdef UNSIGNED_64BIT_TYPE | |
251 | __extension__ typedef UNSIGNED_64BIT_TYPE ull; | |
252 | if (sizeof (hashval_t) * CHAR_BIT <= 32) | |
253 | { | |
254 | hashval_t t1, t2, t3, t4, q, r; | |
255 | ||
256 | t1 = ((ull)x * inv) >> 32; | |
257 | t2 = x - t1; | |
258 | t3 = t2 >> 1; | |
259 | t4 = t1 + t3; | |
260 | q = t4 >> shift; | |
261 | r = x - (q * y); | |
262 | ||
263 | return r; | |
264 | } | |
265 | #endif | |
266 | ||
267 | /* Otherwise just use the native division routines. */ | |
268 | return x % y; | |
269 | } | |
270 | ||
fe046a17 DD |
271 | /* Compute the primary hash for HASH given HTAB's current size. */ |
272 | ||
273 | static inline hashval_t | |
274 | htab_mod (hash, htab) | |
275 | hashval_t hash; | |
276 | htab_t htab; | |
277 | { | |
bb6a587d DD |
278 | const struct prime_ent *p = &prime_tab[htab->size_prime_index]; |
279 | return htab_mod_1 (hash, p->prime, p->inv, p->shift); | |
fe046a17 DD |
280 | } |
281 | ||
282 | /* Compute the secondary hash for HASH given HTAB's current size. */ | |
283 | ||
284 | static inline hashval_t | |
285 | htab_mod_m2 (hash, htab) | |
286 | hashval_t hash; | |
287 | htab_t htab; | |
288 | { | |
bb6a587d DD |
289 | const struct prime_ent *p = &prime_tab[htab->size_prime_index]; |
290 | return 1 + htab_mod_1 (hash, p->prime - 2, p->inv_m2, p->shift); | |
fe046a17 DD |
291 | } |
292 | ||
e2eaf477 ILT |
293 | /* This function creates table with length slightly longer than given |
294 | source length. Created hash table is initiated as empty (all the | |
295 | hash table entries are EMPTY_ENTRY). The function returns the | |
18893690 | 296 | created hash table, or NULL if memory allocation fails. */ |
e2eaf477 | 297 | |
b4fe2683 | 298 | htab_t |
18893690 | 299 | htab_create_alloc (size, hash_f, eq_f, del_f, alloc_f, free_f) |
e2eaf477 | 300 | size_t size; |
b4fe2683 JM |
301 | htab_hash hash_f; |
302 | htab_eq eq_f; | |
303 | htab_del del_f; | |
18893690 DD |
304 | htab_alloc alloc_f; |
305 | htab_free free_f; | |
e2eaf477 | 306 | { |
b4fe2683 | 307 | htab_t result; |
bb6a587d DD |
308 | unsigned int size_prime_index; |
309 | ||
310 | size_prime_index = higher_prime_index (size); | |
311 | size = prime_tab[size_prime_index].prime; | |
e2eaf477 | 312 | |
18893690 DD |
313 | result = (htab_t) (*alloc_f) (1, sizeof (struct htab)); |
314 | if (result == NULL) | |
315 | return NULL; | |
316 | result->entries = (PTR *) (*alloc_f) (size, sizeof (PTR)); | |
317 | if (result->entries == NULL) | |
318 | { | |
319 | if (free_f != NULL) | |
320 | (*free_f) (result); | |
321 | return NULL; | |
322 | } | |
e2eaf477 | 323 | result->size = size; |
bb6a587d | 324 | result->size_prime_index = size_prime_index; |
b4fe2683 JM |
325 | result->hash_f = hash_f; |
326 | result->eq_f = eq_f; | |
327 | result->del_f = del_f; | |
18893690 DD |
328 | result->alloc_f = alloc_f; |
329 | result->free_f = free_f; | |
99a4c1bd HPN |
330 | return result; |
331 | } | |
332 | ||
5f9624e3 DJ |
333 | /* As above, but use the variants of alloc_f and free_f which accept |
334 | an extra argument. */ | |
335 | ||
336 | htab_t | |
337 | htab_create_alloc_ex (size, hash_f, eq_f, del_f, alloc_arg, alloc_f, | |
338 | free_f) | |
339 | size_t size; | |
340 | htab_hash hash_f; | |
341 | htab_eq eq_f; | |
342 | htab_del del_f; | |
343 | PTR alloc_arg; | |
344 | htab_alloc_with_arg alloc_f; | |
345 | htab_free_with_arg free_f; | |
346 | { | |
347 | htab_t result; | |
bb6a587d DD |
348 | unsigned int size_prime_index; |
349 | ||
350 | size_prime_index = higher_prime_index (size); | |
351 | size = prime_tab[size_prime_index].prime; | |
5f9624e3 | 352 | |
5f9624e3 DJ |
353 | result = (htab_t) (*alloc_f) (alloc_arg, 1, sizeof (struct htab)); |
354 | if (result == NULL) | |
355 | return NULL; | |
356 | result->entries = (PTR *) (*alloc_f) (alloc_arg, size, sizeof (PTR)); | |
357 | if (result->entries == NULL) | |
358 | { | |
359 | if (free_f != NULL) | |
360 | (*free_f) (alloc_arg, result); | |
361 | return NULL; | |
362 | } | |
363 | result->size = size; | |
bb6a587d | 364 | result->size_prime_index = size_prime_index; |
5f9624e3 DJ |
365 | result->hash_f = hash_f; |
366 | result->eq_f = eq_f; | |
367 | result->del_f = del_f; | |
368 | result->alloc_arg = alloc_arg; | |
369 | result->alloc_with_arg_f = alloc_f; | |
370 | result->free_with_arg_f = free_f; | |
371 | return result; | |
372 | } | |
373 | ||
374 | /* Update the function pointers and allocation parameter in the htab_t. */ | |
375 | ||
376 | void | |
377 | htab_set_functions_ex (htab, hash_f, eq_f, del_f, alloc_arg, alloc_f, free_f) | |
378 | htab_t htab; | |
379 | htab_hash hash_f; | |
380 | htab_eq eq_f; | |
381 | htab_del del_f; | |
382 | PTR alloc_arg; | |
383 | htab_alloc_with_arg alloc_f; | |
384 | htab_free_with_arg free_f; | |
385 | { | |
386 | htab->hash_f = hash_f; | |
387 | htab->eq_f = eq_f; | |
388 | htab->del_f = del_f; | |
389 | htab->alloc_arg = alloc_arg; | |
390 | htab->alloc_with_arg_f = alloc_f; | |
391 | htab->free_with_arg_f = free_f; | |
392 | } | |
393 | ||
18893690 | 394 | /* These functions exist solely for backward compatibility. */ |
99a4c1bd | 395 | |
18893690 | 396 | #undef htab_create |
99a4c1bd | 397 | htab_t |
18893690 | 398 | htab_create (size, hash_f, eq_f, del_f) |
99a4c1bd HPN |
399 | size_t size; |
400 | htab_hash hash_f; | |
401 | htab_eq eq_f; | |
402 | htab_del del_f; | |
403 | { | |
18893690 DD |
404 | return htab_create_alloc (size, hash_f, eq_f, del_f, xcalloc, free); |
405 | } | |
99a4c1bd | 406 | |
18893690 DD |
407 | htab_t |
408 | htab_try_create (size, hash_f, eq_f, del_f) | |
409 | size_t size; | |
410 | htab_hash hash_f; | |
411 | htab_eq eq_f; | |
412 | htab_del del_f; | |
413 | { | |
414 | return htab_create_alloc (size, hash_f, eq_f, del_f, calloc, free); | |
e2eaf477 ILT |
415 | } |
416 | ||
417 | /* This function frees all memory allocated for given hash table. | |
418 | Naturally the hash table must already exist. */ | |
419 | ||
420 | void | |
b4fe2683 JM |
421 | htab_delete (htab) |
422 | htab_t htab; | |
e2eaf477 | 423 | { |
fe046a17 DD |
424 | size_t size = htab_size (htab); |
425 | PTR *entries = htab->entries; | |
b4fe2683 | 426 | int i; |
eb383413 | 427 | |
b4fe2683 | 428 | if (htab->del_f) |
fe046a17 DD |
429 | for (i = size - 1; i >= 0; i--) |
430 | if (entries[i] != EMPTY_ENTRY && entries[i] != DELETED_ENTRY) | |
431 | (*htab->del_f) (entries[i]); | |
b4fe2683 | 432 | |
18893690 DD |
433 | if (htab->free_f != NULL) |
434 | { | |
fe046a17 | 435 | (*htab->free_f) (entries); |
18893690 DD |
436 | (*htab->free_f) (htab); |
437 | } | |
5f9624e3 DJ |
438 | else if (htab->free_with_arg_f != NULL) |
439 | { | |
fe046a17 | 440 | (*htab->free_with_arg_f) (htab->alloc_arg, entries); |
5f9624e3 DJ |
441 | (*htab->free_with_arg_f) (htab->alloc_arg, htab); |
442 | } | |
e2eaf477 ILT |
443 | } |
444 | ||
445 | /* This function clears all entries in the given hash table. */ | |
446 | ||
447 | void | |
b4fe2683 JM |
448 | htab_empty (htab) |
449 | htab_t htab; | |
450 | { | |
fe046a17 DD |
451 | size_t size = htab_size (htab); |
452 | PTR *entries = htab->entries; | |
b4fe2683 | 453 | int i; |
eb383413 | 454 | |
b4fe2683 | 455 | if (htab->del_f) |
fe046a17 DD |
456 | for (i = size - 1; i >= 0; i--) |
457 | if (entries[i] != EMPTY_ENTRY && entries[i] != DELETED_ENTRY) | |
458 | (*htab->del_f) (entries[i]); | |
b4fe2683 | 459 | |
fe046a17 | 460 | memset (entries, 0, size * sizeof (PTR)); |
b4fe2683 JM |
461 | } |
462 | ||
463 | /* Similar to htab_find_slot, but without several unwanted side effects: | |
464 | - Does not call htab->eq_f when it finds an existing entry. | |
465 | - Does not change the count of elements/searches/collisions in the | |
466 | hash table. | |
467 | This function also assumes there are no deleted entries in the table. | |
468 | HASH is the hash value for the element to be inserted. */ | |
eb383413 | 469 | |
e0f3df8f | 470 | static PTR * |
b4fe2683 JM |
471 | find_empty_slot_for_expand (htab, hash) |
472 | htab_t htab; | |
eb383413 | 473 | hashval_t hash; |
e2eaf477 | 474 | { |
fe046a17 DD |
475 | hashval_t index = htab_mod (hash, htab); |
476 | size_t size = htab_size (htab); | |
b1c933fc RH |
477 | PTR *slot = htab->entries + index; |
478 | hashval_t hash2; | |
479 | ||
480 | if (*slot == EMPTY_ENTRY) | |
481 | return slot; | |
482 | else if (*slot == DELETED_ENTRY) | |
483 | abort (); | |
b4fe2683 | 484 | |
fe046a17 | 485 | hash2 = htab_mod_m2 (hash, htab); |
b4fe2683 JM |
486 | for (;;) |
487 | { | |
b1c933fc RH |
488 | index += hash2; |
489 | if (index >= size) | |
490 | index -= size; | |
eb383413 | 491 | |
b1c933fc | 492 | slot = htab->entries + index; |
b4fe2683 JM |
493 | if (*slot == EMPTY_ENTRY) |
494 | return slot; | |
eb383413 | 495 | else if (*slot == DELETED_ENTRY) |
b4fe2683 | 496 | abort (); |
b4fe2683 | 497 | } |
e2eaf477 ILT |
498 | } |
499 | ||
500 | /* The following function changes size of memory allocated for the | |
501 | entries and repeatedly inserts the table elements. The occupancy | |
502 | of the table after the call will be about 50%. Naturally the hash | |
503 | table must already exist. Remember also that the place of the | |
99a4c1bd HPN |
504 | table entries is changed. If memory allocation failures are allowed, |
505 | this function will return zero, indicating that the table could not be | |
506 | expanded. If all goes well, it will return a non-zero value. */ | |
e2eaf477 | 507 | |
99a4c1bd | 508 | static int |
b4fe2683 JM |
509 | htab_expand (htab) |
510 | htab_t htab; | |
e2eaf477 | 511 | { |
e0f3df8f HPN |
512 | PTR *oentries; |
513 | PTR *olimit; | |
514 | PTR *p; | |
18893690 | 515 | PTR *nentries; |
bb6a587d DD |
516 | size_t nsize, osize, elts; |
517 | unsigned int oindex, nindex; | |
b4fe2683 JM |
518 | |
519 | oentries = htab->entries; | |
bb6a587d DD |
520 | oindex = htab->size_prime_index; |
521 | osize = htab->size; | |
522 | olimit = oentries + osize; | |
523 | elts = htab_elements (htab); | |
b4fe2683 | 524 | |
c4d8feb2 DD |
525 | /* Resize only when table after removal of unused elements is either |
526 | too full or too empty. */ | |
bb6a587d DD |
527 | if (elts * 2 > osize || (elts * 8 < osize && osize > 32)) |
528 | { | |
529 | nindex = higher_prime_index (elts * 2); | |
530 | nsize = prime_tab[nindex].prime; | |
531 | } | |
c4d8feb2 | 532 | else |
bb6a587d DD |
533 | { |
534 | nindex = oindex; | |
535 | nsize = osize; | |
536 | } | |
99a4c1bd | 537 | |
5f9624e3 DJ |
538 | if (htab->alloc_with_arg_f != NULL) |
539 | nentries = (PTR *) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize, | |
540 | sizeof (PTR *)); | |
541 | else | |
542 | nentries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *)); | |
18893690 DD |
543 | if (nentries == NULL) |
544 | return 0; | |
545 | htab->entries = nentries; | |
eed2b28c | 546 | htab->size = nsize; |
bb6a587d | 547 | htab->size_prime_index = nindex; |
b4fe2683 JM |
548 | htab->n_elements -= htab->n_deleted; |
549 | htab->n_deleted = 0; | |
550 | ||
551 | p = oentries; | |
552 | do | |
553 | { | |
e0f3df8f | 554 | PTR x = *p; |
eb383413 | 555 | |
b4fe2683 JM |
556 | if (x != EMPTY_ENTRY && x != DELETED_ENTRY) |
557 | { | |
e0f3df8f | 558 | PTR *q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x)); |
eb383413 | 559 | |
b4fe2683 JM |
560 | *q = x; |
561 | } | |
eb383413 | 562 | |
b4fe2683 JM |
563 | p++; |
564 | } | |
565 | while (p < olimit); | |
eb383413 | 566 | |
18893690 DD |
567 | if (htab->free_f != NULL) |
568 | (*htab->free_f) (oentries); | |
5f9624e3 DJ |
569 | else if (htab->free_with_arg_f != NULL) |
570 | (*htab->free_with_arg_f) (htab->alloc_arg, oentries); | |
99a4c1bd | 571 | return 1; |
e2eaf477 ILT |
572 | } |
573 | ||
b4fe2683 JM |
574 | /* This function searches for a hash table entry equal to the given |
575 | element. It cannot be used to insert or delete an element. */ | |
576 | ||
e0f3df8f | 577 | PTR |
b4fe2683 JM |
578 | htab_find_with_hash (htab, element, hash) |
579 | htab_t htab; | |
e0f3df8f | 580 | const PTR element; |
eb383413 | 581 | hashval_t hash; |
e2eaf477 | 582 | { |
fe046a17 | 583 | hashval_t index, hash2; |
b4fe2683 | 584 | size_t size; |
e0f3df8f | 585 | PTR entry; |
e2eaf477 | 586 | |
b4fe2683 | 587 | htab->searches++; |
fe046a17 DD |
588 | size = htab_size (htab); |
589 | index = htab_mod (hash, htab); | |
b4fe2683 | 590 | |
eb383413 L |
591 | entry = htab->entries[index]; |
592 | if (entry == EMPTY_ENTRY | |
593 | || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element))) | |
594 | return entry; | |
595 | ||
fe046a17 | 596 | hash2 = htab_mod_m2 (hash, htab); |
b4fe2683 | 597 | for (;;) |
e2eaf477 | 598 | { |
b4fe2683 JM |
599 | htab->collisions++; |
600 | index += hash2; | |
601 | if (index >= size) | |
602 | index -= size; | |
eb383413 L |
603 | |
604 | entry = htab->entries[index]; | |
605 | if (entry == EMPTY_ENTRY | |
606 | || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element))) | |
607 | return entry; | |
e2eaf477 | 608 | } |
b4fe2683 JM |
609 | } |
610 | ||
611 | /* Like htab_find_slot_with_hash, but compute the hash value from the | |
612 | element. */ | |
eb383413 | 613 | |
e0f3df8f | 614 | PTR |
b4fe2683 JM |
615 | htab_find (htab, element) |
616 | htab_t htab; | |
e0f3df8f | 617 | const PTR element; |
b4fe2683 JM |
618 | { |
619 | return htab_find_with_hash (htab, element, (*htab->hash_f) (element)); | |
620 | } | |
621 | ||
622 | /* This function searches for a hash table slot containing an entry | |
623 | equal to the given element. To delete an entry, call this with | |
624 | INSERT = 0, then call htab_clear_slot on the slot returned (possibly | |
625 | after doing some checks). To insert an entry, call this with | |
99a4c1bd HPN |
626 | INSERT = 1, then write the value you want into the returned slot. |
627 | When inserting an entry, NULL may be returned if memory allocation | |
628 | fails. */ | |
b4fe2683 | 629 | |
e0f3df8f | 630 | PTR * |
b4fe2683 JM |
631 | htab_find_slot_with_hash (htab, element, hash, insert) |
632 | htab_t htab; | |
e0f3df8f | 633 | const PTR element; |
eb383413 L |
634 | hashval_t hash; |
635 | enum insert_option insert; | |
b4fe2683 | 636 | { |
e0f3df8f | 637 | PTR *first_deleted_slot; |
fe046a17 | 638 | hashval_t index, hash2; |
b4fe2683 | 639 | size_t size; |
b1c933fc | 640 | PTR entry; |
b4fe2683 | 641 | |
fe046a17 DD |
642 | size = htab_size (htab); |
643 | if (insert == INSERT && size * 3 <= htab->n_elements * 4) | |
644 | { | |
645 | if (htab_expand (htab) == 0) | |
646 | return NULL; | |
647 | size = htab_size (htab); | |
648 | } | |
b4fe2683 | 649 | |
fe046a17 | 650 | index = htab_mod (hash, htab); |
b4fe2683 | 651 | |
e2eaf477 | 652 | htab->searches++; |
b4fe2683 JM |
653 | first_deleted_slot = NULL; |
654 | ||
b1c933fc RH |
655 | entry = htab->entries[index]; |
656 | if (entry == EMPTY_ENTRY) | |
657 | goto empty_entry; | |
658 | else if (entry == DELETED_ENTRY) | |
659 | first_deleted_slot = &htab->entries[index]; | |
660 | else if ((*htab->eq_f) (entry, element)) | |
661 | return &htab->entries[index]; | |
662 | ||
fe046a17 | 663 | hash2 = htab_mod_m2 (hash, htab); |
b4fe2683 | 664 | for (;;) |
e2eaf477 | 665 | { |
b1c933fc RH |
666 | htab->collisions++; |
667 | index += hash2; | |
668 | if (index >= size) | |
669 | index -= size; | |
670 | ||
671 | entry = htab->entries[index]; | |
b4fe2683 | 672 | if (entry == EMPTY_ENTRY) |
b1c933fc RH |
673 | goto empty_entry; |
674 | else if (entry == DELETED_ENTRY) | |
b4fe2683 JM |
675 | { |
676 | if (!first_deleted_slot) | |
677 | first_deleted_slot = &htab->entries[index]; | |
678 | } | |
b1c933fc | 679 | else if ((*htab->eq_f) (entry, element)) |
eb383413 | 680 | return &htab->entries[index]; |
e2eaf477 | 681 | } |
b1c933fc RH |
682 | |
683 | empty_entry: | |
684 | if (insert == NO_INSERT) | |
685 | return NULL; | |
686 | ||
b1c933fc RH |
687 | if (first_deleted_slot) |
688 | { | |
686e72d7 | 689 | htab->n_deleted--; |
b1c933fc RH |
690 | *first_deleted_slot = EMPTY_ENTRY; |
691 | return first_deleted_slot; | |
692 | } | |
693 | ||
686e72d7 | 694 | htab->n_elements++; |
b1c933fc | 695 | return &htab->entries[index]; |
e2eaf477 ILT |
696 | } |
697 | ||
b4fe2683 JM |
698 | /* Like htab_find_slot_with_hash, but compute the hash value from the |
699 | element. */ | |
eb383413 | 700 | |
e0f3df8f | 701 | PTR * |
b4fe2683 JM |
702 | htab_find_slot (htab, element, insert) |
703 | htab_t htab; | |
e0f3df8f | 704 | const PTR element; |
eb383413 | 705 | enum insert_option insert; |
b4fe2683 JM |
706 | { |
707 | return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element), | |
708 | insert); | |
709 | } | |
710 | ||
d6ea4e80 DD |
711 | /* This function deletes an element with the given value from hash |
712 | table (the hash is computed from the element). If there is no matching | |
713 | element in the hash table, this function does nothing. */ | |
714 | ||
715 | void | |
716 | htab_remove_elt (htab, element) | |
717 | htab_t htab; | |
718 | PTR element; | |
719 | { | |
720 | htab_remove_elt_with_hash (htab, element, (*htab->hash_f) (element)); | |
721 | } | |
722 | ||
723 | ||
b4fe2683 JM |
724 | /* This function deletes an element with the given value from hash |
725 | table. If there is no matching element in the hash table, this | |
726 | function does nothing. */ | |
e2eaf477 ILT |
727 | |
728 | void | |
d6ea4e80 | 729 | htab_remove_elt_with_hash (htab, element, hash) |
b4fe2683 | 730 | htab_t htab; |
e0f3df8f | 731 | PTR element; |
d6ea4e80 | 732 | hashval_t hash; |
e2eaf477 | 733 | { |
e0f3df8f | 734 | PTR *slot; |
b4fe2683 | 735 | |
d6ea4e80 | 736 | slot = htab_find_slot_with_hash (htab, element, hash, NO_INSERT); |
b4fe2683 JM |
737 | if (*slot == EMPTY_ENTRY) |
738 | return; | |
739 | ||
740 | if (htab->del_f) | |
741 | (*htab->del_f) (*slot); | |
e2eaf477 | 742 | |
b4fe2683 JM |
743 | *slot = DELETED_ENTRY; |
744 | htab->n_deleted++; | |
e2eaf477 ILT |
745 | } |
746 | ||
b4fe2683 JM |
747 | /* This function clears a specified slot in a hash table. It is |
748 | useful when you've already done the lookup and don't want to do it | |
749 | again. */ | |
e2eaf477 ILT |
750 | |
751 | void | |
b4fe2683 JM |
752 | htab_clear_slot (htab, slot) |
753 | htab_t htab; | |
e0f3df8f | 754 | PTR *slot; |
e2eaf477 | 755 | { |
fe046a17 | 756 | if (slot < htab->entries || slot >= htab->entries + htab_size (htab) |
e2eaf477 ILT |
757 | || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY) |
758 | abort (); | |
eb383413 | 759 | |
b4fe2683 JM |
760 | if (htab->del_f) |
761 | (*htab->del_f) (*slot); | |
eb383413 | 762 | |
e2eaf477 | 763 | *slot = DELETED_ENTRY; |
b4fe2683 | 764 | htab->n_deleted++; |
e2eaf477 ILT |
765 | } |
766 | ||
767 | /* This function scans over the entire hash table calling | |
768 | CALLBACK for each live entry. If CALLBACK returns false, | |
769 | the iteration stops. INFO is passed as CALLBACK's second | |
770 | argument. */ | |
771 | ||
772 | void | |
f77ed96c | 773 | htab_traverse_noresize (htab, callback, info) |
b4fe2683 JM |
774 | htab_t htab; |
775 | htab_trav callback; | |
e0f3df8f | 776 | PTR info; |
e2eaf477 | 777 | { |
c4d8feb2 DD |
778 | PTR *slot; |
779 | PTR *limit; | |
780 | ||
c4d8feb2 | 781 | slot = htab->entries; |
fe046a17 | 782 | limit = slot + htab_size (htab); |
eb383413 | 783 | |
b4fe2683 JM |
784 | do |
785 | { | |
e0f3df8f | 786 | PTR x = *slot; |
eb383413 | 787 | |
b4fe2683 JM |
788 | if (x != EMPTY_ENTRY && x != DELETED_ENTRY) |
789 | if (!(*callback) (slot, info)) | |
790 | break; | |
791 | } | |
792 | while (++slot < limit); | |
e2eaf477 ILT |
793 | } |
794 | ||
f77ed96c DD |
795 | /* Like htab_traverse_noresize, but does resize the table when it is |
796 | too empty to improve effectivity of subsequent calls. */ | |
797 | ||
798 | void | |
799 | htab_traverse (htab, callback, info) | |
800 | htab_t htab; | |
801 | htab_trav callback; | |
802 | PTR info; | |
803 | { | |
fe046a17 | 804 | if (htab_elements (htab) * 8 < htab_size (htab)) |
f77ed96c DD |
805 | htab_expand (htab); |
806 | ||
807 | htab_traverse_noresize (htab, callback, info); | |
808 | } | |
809 | ||
eb383413 L |
810 | /* Return the fraction of fixed collisions during all work with given |
811 | hash table. */ | |
e2eaf477 | 812 | |
b4fe2683 JM |
813 | double |
814 | htab_collisions (htab) | |
815 | htab_t htab; | |
e2eaf477 | 816 | { |
eb383413 | 817 | if (htab->searches == 0) |
b4fe2683 | 818 | return 0.0; |
eb383413 L |
819 | |
820 | return (double) htab->collisions / (double) htab->searches; | |
e2eaf477 | 821 | } |
8fc34799 | 822 | |
68a41de7 DD |
823 | /* Hash P as a null-terminated string. |
824 | ||
825 | Copied from gcc/hashtable.c. Zack had the following to say with respect | |
826 | to applicability, though note that unlike hashtable.c, this hash table | |
827 | implementation re-hashes rather than chain buckets. | |
828 | ||
829 | http://gcc.gnu.org/ml/gcc-patches/2001-08/msg01021.html | |
830 | From: Zack Weinberg <zackw@panix.com> | |
831 | Date: Fri, 17 Aug 2001 02:15:56 -0400 | |
832 | ||
833 | I got it by extracting all the identifiers from all the source code | |
834 | I had lying around in mid-1999, and testing many recurrences of | |
835 | the form "H_n = H_{n-1} * K + c_n * L + M" where K, L, M were either | |
836 | prime numbers or the appropriate identity. This was the best one. | |
837 | I don't remember exactly what constituted "best", except I was | |
838 | looking at bucket-length distributions mostly. | |
839 | ||
840 | So it should be very good at hashing identifiers, but might not be | |
841 | as good at arbitrary strings. | |
842 | ||
843 | I'll add that it thoroughly trounces the hash functions recommended | |
844 | for this use at http://burtleburtle.net/bob/hash/index.html, both | |
845 | on speed and bucket distribution. I haven't tried it against the | |
846 | function they just started using for Perl's hashes. */ | |
8fc34799 DD |
847 | |
848 | hashval_t | |
849 | htab_hash_string (p) | |
850 | const PTR p; | |
851 | { | |
852 | const unsigned char *str = (const unsigned char *) p; | |
853 | hashval_t r = 0; | |
854 | unsigned char c; | |
855 | ||
856 | while ((c = *str++) != 0) | |
857 | r = r * 67 + c - 113; | |
858 | ||
859 | return r; | |
860 | } | |
7108c5dc JM |
861 | |
862 | /* DERIVED FROM: | |
863 | -------------------------------------------------------------------- | |
864 | lookup2.c, by Bob Jenkins, December 1996, Public Domain. | |
865 | hash(), hash2(), hash3, and mix() are externally useful functions. | |
866 | Routines to test the hash are included if SELF_TEST is defined. | |
867 | You can use this free for any purpose. It has no warranty. | |
868 | -------------------------------------------------------------------- | |
869 | */ | |
870 | ||
871 | /* | |
872 | -------------------------------------------------------------------- | |
873 | mix -- mix 3 32-bit values reversibly. | |
874 | For every delta with one or two bit set, and the deltas of all three | |
875 | high bits or all three low bits, whether the original value of a,b,c | |
876 | is almost all zero or is uniformly distributed, | |
877 | * If mix() is run forward or backward, at least 32 bits in a,b,c | |
878 | have at least 1/4 probability of changing. | |
879 | * If mix() is run forward, every bit of c will change between 1/3 and | |
880 | 2/3 of the time. (Well, 22/100 and 78/100 for some 2-bit deltas.) | |
881 | mix() was built out of 36 single-cycle latency instructions in a | |
882 | structure that could supported 2x parallelism, like so: | |
883 | a -= b; | |
884 | a -= c; x = (c>>13); | |
885 | b -= c; a ^= x; | |
886 | b -= a; x = (a<<8); | |
887 | c -= a; b ^= x; | |
888 | c -= b; x = (b>>13); | |
889 | ... | |
890 | Unfortunately, superscalar Pentiums and Sparcs can't take advantage | |
891 | of that parallelism. They've also turned some of those single-cycle | |
892 | latency instructions into multi-cycle latency instructions. Still, | |
893 | this is the fastest good hash I could find. There were about 2^^68 | |
894 | to choose from. I only looked at a billion or so. | |
895 | -------------------------------------------------------------------- | |
896 | */ | |
897 | /* same, but slower, works on systems that might have 8 byte hashval_t's */ | |
898 | #define mix(a,b,c) \ | |
899 | { \ | |
900 | a -= b; a -= c; a ^= (c>>13); \ | |
901 | b -= c; b -= a; b ^= (a<< 8); \ | |
902 | c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \ | |
903 | a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \ | |
904 | b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \ | |
905 | c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \ | |
906 | a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \ | |
907 | b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \ | |
908 | c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \ | |
909 | } | |
910 | ||
911 | /* | |
912 | -------------------------------------------------------------------- | |
913 | hash() -- hash a variable-length key into a 32-bit value | |
914 | k : the key (the unaligned variable-length array of bytes) | |
915 | len : the length of the key, counting by bytes | |
916 | level : can be any 4-byte value | |
917 | Returns a 32-bit value. Every bit of the key affects every bit of | |
918 | the return value. Every 1-bit and 2-bit delta achieves avalanche. | |
919 | About 36+6len instructions. | |
920 | ||
921 | The best hash table sizes are powers of 2. There is no need to do | |
922 | mod a prime (mod is sooo slow!). If you need less than 32 bits, | |
923 | use a bitmask. For example, if you need only 10 bits, do | |
924 | h = (h & hashmask(10)); | |
925 | In which case, the hash table should have hashsize(10) elements. | |
926 | ||
927 | If you are hashing n strings (ub1 **)k, do it like this: | |
928 | for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h); | |
929 | ||
930 | By Bob Jenkins, 1996. bob_jenkins@burtleburtle.net. You may use this | |
931 | code any way you wish, private, educational, or commercial. It's free. | |
932 | ||
933 | See http://burtleburtle.net/bob/hash/evahash.html | |
934 | Use for hash table lookup, or anything where one collision in 2^32 is | |
935 | acceptable. Do NOT use for cryptographic purposes. | |
936 | -------------------------------------------------------------------- | |
937 | */ | |
938 | ||
eafaf5eb | 939 | hashval_t iterative_hash (k_in, length, initval) |
7108c5dc JM |
940 | const PTR k_in; /* the key */ |
941 | register size_t length; /* the length of the key */ | |
942 | register hashval_t initval; /* the previous hash, or an arbitrary value */ | |
943 | { | |
944 | register const unsigned char *k = (const unsigned char *)k_in; | |
945 | register hashval_t a,b,c,len; | |
946 | ||
947 | /* Set up the internal state */ | |
948 | len = length; | |
949 | a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */ | |
950 | c = initval; /* the previous hash value */ | |
951 | ||
952 | /*---------------------------------------- handle most of the key */ | |
953 | #ifndef WORDS_BIGENDIAN | |
954 | /* On a little-endian machine, if the data is 4-byte aligned we can hash | |
955 | by word for better speed. This gives nondeterministic results on | |
956 | big-endian machines. */ | |
957 | if (sizeof (hashval_t) == 4 && (((size_t)k)&3) == 0) | |
958 | while (len >= 12) /* aligned */ | |
959 | { | |
960 | a += *(hashval_t *)(k+0); | |
961 | b += *(hashval_t *)(k+4); | |
962 | c += *(hashval_t *)(k+8); | |
963 | mix(a,b,c); | |
964 | k += 12; len -= 12; | |
965 | } | |
966 | else /* unaligned */ | |
967 | #endif | |
968 | while (len >= 12) | |
969 | { | |
970 | a += (k[0] +((hashval_t)k[1]<<8) +((hashval_t)k[2]<<16) +((hashval_t)k[3]<<24)); | |
971 | b += (k[4] +((hashval_t)k[5]<<8) +((hashval_t)k[6]<<16) +((hashval_t)k[7]<<24)); | |
972 | c += (k[8] +((hashval_t)k[9]<<8) +((hashval_t)k[10]<<16)+((hashval_t)k[11]<<24)); | |
973 | mix(a,b,c); | |
974 | k += 12; len -= 12; | |
975 | } | |
976 | ||
977 | /*------------------------------------- handle the last 11 bytes */ | |
978 | c += length; | |
979 | switch(len) /* all the case statements fall through */ | |
980 | { | |
981 | case 11: c+=((hashval_t)k[10]<<24); | |
982 | case 10: c+=((hashval_t)k[9]<<16); | |
983 | case 9 : c+=((hashval_t)k[8]<<8); | |
984 | /* the first byte of c is reserved for the length */ | |
985 | case 8 : b+=((hashval_t)k[7]<<24); | |
986 | case 7 : b+=((hashval_t)k[6]<<16); | |
987 | case 6 : b+=((hashval_t)k[5]<<8); | |
988 | case 5 : b+=k[4]; | |
989 | case 4 : a+=((hashval_t)k[3]<<24); | |
990 | case 3 : a+=((hashval_t)k[2]<<16); | |
991 | case 2 : a+=((hashval_t)k[1]<<8); | |
992 | case 1 : a+=k[0]; | |
993 | /* case 0: nothing left to add */ | |
994 | } | |
995 | mix(a,b,c); | |
996 | /*-------------------------------------------- report the result */ | |
997 | return c; | |
998 | } |