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 | |
49b1fae4 DD |
76 | static unsigned int higher_prime_index (unsigned long); |
77 | static hashval_t htab_mod_1 (hashval_t, hashval_t, hashval_t, int); | |
78 | static hashval_t htab_mod (hashval_t, htab_t); | |
79 | static hashval_t htab_mod_m2 (hashval_t, htab_t); | |
80 | static hashval_t hash_pointer (const void *); | |
81 | static int eq_pointer (const void *, const void *); | |
82 | static int htab_expand (htab_t); | |
83 | static PTR *find_empty_slot_for_expand (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 | |
49b1fae4 | 179 | higher_prime_index (unsigned long n) |
e2eaf477 | 180 | { |
bb6a587d DD |
181 | unsigned int low = 0; |
182 | unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]); | |
5ca0f83d DD |
183 | |
184 | while (low != high) | |
185 | { | |
bb6a587d DD |
186 | unsigned int mid = low + (high - low) / 2; |
187 | if (n > prime_tab[mid].prime) | |
5ca0f83d DD |
188 | low = mid + 1; |
189 | else | |
190 | high = mid; | |
191 | } | |
192 | ||
193 | /* If we've run out of primes, abort. */ | |
bb6a587d | 194 | if (n > prime_tab[low].prime) |
5ca0f83d DD |
195 | { |
196 | fprintf (stderr, "Cannot find prime bigger than %lu\n", n); | |
197 | abort (); | |
198 | } | |
199 | ||
bb6a587d | 200 | return low; |
e2eaf477 ILT |
201 | } |
202 | ||
eb383413 L |
203 | /* Returns a hash code for P. */ |
204 | ||
205 | static hashval_t | |
49b1fae4 | 206 | hash_pointer (const PTR p) |
eb383413 L |
207 | { |
208 | return (hashval_t) ((long)p >> 3); | |
209 | } | |
210 | ||
211 | /* Returns non-zero if P1 and P2 are equal. */ | |
212 | ||
213 | static int | |
49b1fae4 | 214 | eq_pointer (const PTR p1, const PTR p2) |
eb383413 L |
215 | { |
216 | return p1 == p2; | |
217 | } | |
218 | ||
fe046a17 DD |
219 | /* Return the current size of given hash table. */ |
220 | ||
221 | inline size_t | |
49b1fae4 | 222 | htab_size (htab_t htab) |
fe046a17 DD |
223 | { |
224 | return htab->size; | |
225 | } | |
226 | ||
227 | /* Return the current number of elements in given hash table. */ | |
228 | ||
229 | inline size_t | |
49b1fae4 | 230 | htab_elements (htab_t htab) |
fe046a17 DD |
231 | { |
232 | return htab->n_elements - htab->n_deleted; | |
233 | } | |
234 | ||
bb6a587d DD |
235 | /* Return X % Y. */ |
236 | ||
237 | static inline hashval_t | |
49b1fae4 | 238 | htab_mod_1 (hashval_t x, hashval_t y, hashval_t inv, int shift) |
bb6a587d DD |
239 | { |
240 | /* The multiplicative inverses computed above are for 32-bit types, and | |
241 | requires that we be able to compute a highpart multiply. */ | |
242 | #ifdef UNSIGNED_64BIT_TYPE | |
243 | __extension__ typedef UNSIGNED_64BIT_TYPE ull; | |
244 | if (sizeof (hashval_t) * CHAR_BIT <= 32) | |
245 | { | |
246 | hashval_t t1, t2, t3, t4, q, r; | |
247 | ||
248 | t1 = ((ull)x * inv) >> 32; | |
249 | t2 = x - t1; | |
250 | t3 = t2 >> 1; | |
251 | t4 = t1 + t3; | |
252 | q = t4 >> shift; | |
253 | r = x - (q * y); | |
254 | ||
255 | return r; | |
256 | } | |
257 | #endif | |
258 | ||
259 | /* Otherwise just use the native division routines. */ | |
260 | return x % y; | |
261 | } | |
262 | ||
fe046a17 DD |
263 | /* Compute the primary hash for HASH given HTAB's current size. */ |
264 | ||
265 | static inline hashval_t | |
49b1fae4 | 266 | htab_mod (hashval_t hash, htab_t htab) |
fe046a17 | 267 | { |
bb6a587d DD |
268 | const struct prime_ent *p = &prime_tab[htab->size_prime_index]; |
269 | return htab_mod_1 (hash, p->prime, p->inv, p->shift); | |
fe046a17 DD |
270 | } |
271 | ||
272 | /* Compute the secondary hash for HASH given HTAB's current size. */ | |
273 | ||
274 | static inline hashval_t | |
49b1fae4 | 275 | htab_mod_m2 (hashval_t hash, htab_t htab) |
fe046a17 | 276 | { |
bb6a587d DD |
277 | const struct prime_ent *p = &prime_tab[htab->size_prime_index]; |
278 | return 1 + htab_mod_1 (hash, p->prime - 2, p->inv_m2, p->shift); | |
fe046a17 DD |
279 | } |
280 | ||
e2eaf477 ILT |
281 | /* This function creates table with length slightly longer than given |
282 | source length. Created hash table is initiated as empty (all the | |
283 | hash table entries are EMPTY_ENTRY). The function returns the | |
18893690 | 284 | created hash table, or NULL if memory allocation fails. */ |
e2eaf477 | 285 | |
b4fe2683 | 286 | htab_t |
49b1fae4 DD |
287 | htab_create_alloc (size_t size, htab_hash hash_f, htab_eq eq_f, |
288 | htab_del del_f, htab_alloc alloc_f, htab_free free_f) | |
e2eaf477 | 289 | { |
b4fe2683 | 290 | htab_t result; |
bb6a587d DD |
291 | unsigned int size_prime_index; |
292 | ||
293 | size_prime_index = higher_prime_index (size); | |
294 | size = prime_tab[size_prime_index].prime; | |
e2eaf477 | 295 | |
18893690 DD |
296 | result = (htab_t) (*alloc_f) (1, sizeof (struct htab)); |
297 | if (result == NULL) | |
298 | return NULL; | |
299 | result->entries = (PTR *) (*alloc_f) (size, sizeof (PTR)); | |
300 | if (result->entries == NULL) | |
301 | { | |
302 | if (free_f != NULL) | |
303 | (*free_f) (result); | |
304 | return NULL; | |
305 | } | |
e2eaf477 | 306 | result->size = size; |
bb6a587d | 307 | result->size_prime_index = size_prime_index; |
b4fe2683 JM |
308 | result->hash_f = hash_f; |
309 | result->eq_f = eq_f; | |
310 | result->del_f = del_f; | |
18893690 DD |
311 | result->alloc_f = alloc_f; |
312 | result->free_f = free_f; | |
99a4c1bd HPN |
313 | return result; |
314 | } | |
315 | ||
5f9624e3 DJ |
316 | /* As above, but use the variants of alloc_f and free_f which accept |
317 | an extra argument. */ | |
318 | ||
319 | htab_t | |
320 | htab_create_alloc_ex (size, hash_f, eq_f, del_f, alloc_arg, alloc_f, | |
321 | free_f) | |
322 | size_t size; | |
323 | htab_hash hash_f; | |
324 | htab_eq eq_f; | |
325 | htab_del del_f; | |
326 | PTR alloc_arg; | |
327 | htab_alloc_with_arg alloc_f; | |
328 | htab_free_with_arg free_f; | |
329 | { | |
330 | htab_t result; | |
bb6a587d DD |
331 | unsigned int size_prime_index; |
332 | ||
333 | size_prime_index = higher_prime_index (size); | |
334 | size = prime_tab[size_prime_index].prime; | |
5f9624e3 | 335 | |
5f9624e3 DJ |
336 | result = (htab_t) (*alloc_f) (alloc_arg, 1, sizeof (struct htab)); |
337 | if (result == NULL) | |
338 | return NULL; | |
339 | result->entries = (PTR *) (*alloc_f) (alloc_arg, size, sizeof (PTR)); | |
340 | if (result->entries == NULL) | |
341 | { | |
342 | if (free_f != NULL) | |
343 | (*free_f) (alloc_arg, result); | |
344 | return NULL; | |
345 | } | |
346 | result->size = size; | |
bb6a587d | 347 | result->size_prime_index = size_prime_index; |
5f9624e3 DJ |
348 | result->hash_f = hash_f; |
349 | result->eq_f = eq_f; | |
350 | result->del_f = del_f; | |
351 | result->alloc_arg = alloc_arg; | |
352 | result->alloc_with_arg_f = alloc_f; | |
353 | result->free_with_arg_f = free_f; | |
354 | return result; | |
355 | } | |
356 | ||
357 | /* Update the function pointers and allocation parameter in the htab_t. */ | |
358 | ||
359 | void | |
49b1fae4 DD |
360 | htab_set_functions_ex (htab_t htab, htab_hash hash_f, htab_eq eq_f, |
361 | htab_del del_f, PTR alloc_arg, | |
362 | htab_alloc_with_arg alloc_f, htab_free_with_arg free_f) | |
5f9624e3 DJ |
363 | { |
364 | htab->hash_f = hash_f; | |
365 | htab->eq_f = eq_f; | |
366 | htab->del_f = del_f; | |
367 | htab->alloc_arg = alloc_arg; | |
368 | htab->alloc_with_arg_f = alloc_f; | |
369 | htab->free_with_arg_f = free_f; | |
370 | } | |
371 | ||
18893690 | 372 | /* These functions exist solely for backward compatibility. */ |
99a4c1bd | 373 | |
18893690 | 374 | #undef htab_create |
99a4c1bd | 375 | htab_t |
49b1fae4 | 376 | htab_create (size_t size, htab_hash hash_f, htab_eq eq_f, htab_del del_f) |
99a4c1bd | 377 | { |
18893690 DD |
378 | return htab_create_alloc (size, hash_f, eq_f, del_f, xcalloc, free); |
379 | } | |
99a4c1bd | 380 | |
18893690 | 381 | htab_t |
49b1fae4 | 382 | htab_try_create (size_t size, htab_hash hash_f, htab_eq eq_f, htab_del del_f) |
18893690 DD |
383 | { |
384 | return htab_create_alloc (size, hash_f, eq_f, del_f, calloc, free); | |
e2eaf477 ILT |
385 | } |
386 | ||
387 | /* This function frees all memory allocated for given hash table. | |
388 | Naturally the hash table must already exist. */ | |
389 | ||
390 | void | |
49b1fae4 | 391 | htab_delete (htab_t htab) |
e2eaf477 | 392 | { |
fe046a17 DD |
393 | size_t size = htab_size (htab); |
394 | PTR *entries = htab->entries; | |
b4fe2683 | 395 | int i; |
eb383413 | 396 | |
b4fe2683 | 397 | if (htab->del_f) |
fe046a17 DD |
398 | for (i = size - 1; i >= 0; i--) |
399 | if (entries[i] != EMPTY_ENTRY && entries[i] != DELETED_ENTRY) | |
400 | (*htab->del_f) (entries[i]); | |
b4fe2683 | 401 | |
18893690 DD |
402 | if (htab->free_f != NULL) |
403 | { | |
fe046a17 | 404 | (*htab->free_f) (entries); |
18893690 DD |
405 | (*htab->free_f) (htab); |
406 | } | |
5f9624e3 DJ |
407 | else if (htab->free_with_arg_f != NULL) |
408 | { | |
fe046a17 | 409 | (*htab->free_with_arg_f) (htab->alloc_arg, entries); |
5f9624e3 DJ |
410 | (*htab->free_with_arg_f) (htab->alloc_arg, htab); |
411 | } | |
e2eaf477 ILT |
412 | } |
413 | ||
414 | /* This function clears all entries in the given hash table. */ | |
415 | ||
416 | void | |
49b1fae4 | 417 | htab_empty (htab_t htab) |
b4fe2683 | 418 | { |
fe046a17 DD |
419 | size_t size = htab_size (htab); |
420 | PTR *entries = htab->entries; | |
b4fe2683 | 421 | int i; |
eb383413 | 422 | |
b4fe2683 | 423 | if (htab->del_f) |
fe046a17 DD |
424 | for (i = size - 1; i >= 0; i--) |
425 | if (entries[i] != EMPTY_ENTRY && entries[i] != DELETED_ENTRY) | |
426 | (*htab->del_f) (entries[i]); | |
b4fe2683 | 427 | |
fe046a17 | 428 | memset (entries, 0, size * sizeof (PTR)); |
b4fe2683 JM |
429 | } |
430 | ||
431 | /* Similar to htab_find_slot, but without several unwanted side effects: | |
432 | - Does not call htab->eq_f when it finds an existing entry. | |
433 | - Does not change the count of elements/searches/collisions in the | |
434 | hash table. | |
435 | This function also assumes there are no deleted entries in the table. | |
436 | HASH is the hash value for the element to be inserted. */ | |
eb383413 | 437 | |
e0f3df8f | 438 | static PTR * |
49b1fae4 | 439 | find_empty_slot_for_expand (htab_t htab, hashval_t hash) |
e2eaf477 | 440 | { |
fe046a17 DD |
441 | hashval_t index = htab_mod (hash, htab); |
442 | size_t size = htab_size (htab); | |
b1c933fc RH |
443 | PTR *slot = htab->entries + index; |
444 | hashval_t hash2; | |
445 | ||
446 | if (*slot == EMPTY_ENTRY) | |
447 | return slot; | |
448 | else if (*slot == DELETED_ENTRY) | |
449 | abort (); | |
b4fe2683 | 450 | |
fe046a17 | 451 | hash2 = htab_mod_m2 (hash, htab); |
b4fe2683 JM |
452 | for (;;) |
453 | { | |
b1c933fc RH |
454 | index += hash2; |
455 | if (index >= size) | |
456 | index -= size; | |
eb383413 | 457 | |
b1c933fc | 458 | slot = htab->entries + index; |
b4fe2683 JM |
459 | if (*slot == EMPTY_ENTRY) |
460 | return slot; | |
eb383413 | 461 | else if (*slot == DELETED_ENTRY) |
b4fe2683 | 462 | abort (); |
b4fe2683 | 463 | } |
e2eaf477 ILT |
464 | } |
465 | ||
466 | /* The following function changes size of memory allocated for the | |
467 | entries and repeatedly inserts the table elements. The occupancy | |
468 | of the table after the call will be about 50%. Naturally the hash | |
469 | table must already exist. Remember also that the place of the | |
99a4c1bd HPN |
470 | table entries is changed. If memory allocation failures are allowed, |
471 | this function will return zero, indicating that the table could not be | |
472 | expanded. If all goes well, it will return a non-zero value. */ | |
e2eaf477 | 473 | |
99a4c1bd | 474 | static int |
49b1fae4 | 475 | htab_expand (htab_t htab) |
e2eaf477 | 476 | { |
e0f3df8f HPN |
477 | PTR *oentries; |
478 | PTR *olimit; | |
479 | PTR *p; | |
18893690 | 480 | PTR *nentries; |
bb6a587d DD |
481 | size_t nsize, osize, elts; |
482 | unsigned int oindex, nindex; | |
b4fe2683 JM |
483 | |
484 | oentries = htab->entries; | |
bb6a587d DD |
485 | oindex = htab->size_prime_index; |
486 | osize = htab->size; | |
487 | olimit = oentries + osize; | |
488 | elts = htab_elements (htab); | |
b4fe2683 | 489 | |
c4d8feb2 DD |
490 | /* Resize only when table after removal of unused elements is either |
491 | too full or too empty. */ | |
bb6a587d DD |
492 | if (elts * 2 > osize || (elts * 8 < osize && osize > 32)) |
493 | { | |
494 | nindex = higher_prime_index (elts * 2); | |
495 | nsize = prime_tab[nindex].prime; | |
496 | } | |
c4d8feb2 | 497 | else |
bb6a587d DD |
498 | { |
499 | nindex = oindex; | |
500 | nsize = osize; | |
501 | } | |
99a4c1bd | 502 | |
5f9624e3 DJ |
503 | if (htab->alloc_with_arg_f != NULL) |
504 | nentries = (PTR *) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize, | |
505 | sizeof (PTR *)); | |
506 | else | |
507 | nentries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *)); | |
18893690 DD |
508 | if (nentries == NULL) |
509 | return 0; | |
510 | htab->entries = nentries; | |
eed2b28c | 511 | htab->size = nsize; |
bb6a587d | 512 | htab->size_prime_index = nindex; |
b4fe2683 JM |
513 | htab->n_elements -= htab->n_deleted; |
514 | htab->n_deleted = 0; | |
515 | ||
516 | p = oentries; | |
517 | do | |
518 | { | |
e0f3df8f | 519 | PTR x = *p; |
eb383413 | 520 | |
b4fe2683 JM |
521 | if (x != EMPTY_ENTRY && x != DELETED_ENTRY) |
522 | { | |
e0f3df8f | 523 | PTR *q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x)); |
eb383413 | 524 | |
b4fe2683 JM |
525 | *q = x; |
526 | } | |
eb383413 | 527 | |
b4fe2683 JM |
528 | p++; |
529 | } | |
530 | while (p < olimit); | |
eb383413 | 531 | |
18893690 DD |
532 | if (htab->free_f != NULL) |
533 | (*htab->free_f) (oentries); | |
5f9624e3 DJ |
534 | else if (htab->free_with_arg_f != NULL) |
535 | (*htab->free_with_arg_f) (htab->alloc_arg, oentries); | |
99a4c1bd | 536 | return 1; |
e2eaf477 ILT |
537 | } |
538 | ||
b4fe2683 JM |
539 | /* This function searches for a hash table entry equal to the given |
540 | element. It cannot be used to insert or delete an element. */ | |
541 | ||
e0f3df8f | 542 | PTR |
49b1fae4 | 543 | htab_find_with_hash (htab_t htab, const PTR element, hashval_t hash) |
e2eaf477 | 544 | { |
fe046a17 | 545 | hashval_t index, hash2; |
b4fe2683 | 546 | size_t size; |
e0f3df8f | 547 | PTR entry; |
e2eaf477 | 548 | |
b4fe2683 | 549 | htab->searches++; |
fe046a17 DD |
550 | size = htab_size (htab); |
551 | index = htab_mod (hash, htab); | |
b4fe2683 | 552 | |
eb383413 L |
553 | entry = htab->entries[index]; |
554 | if (entry == EMPTY_ENTRY | |
555 | || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element))) | |
556 | return entry; | |
557 | ||
fe046a17 | 558 | hash2 = htab_mod_m2 (hash, htab); |
b4fe2683 | 559 | for (;;) |
e2eaf477 | 560 | { |
b4fe2683 JM |
561 | htab->collisions++; |
562 | index += hash2; | |
563 | if (index >= size) | |
564 | index -= size; | |
eb383413 L |
565 | |
566 | entry = htab->entries[index]; | |
567 | if (entry == EMPTY_ENTRY | |
568 | || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element))) | |
569 | return entry; | |
e2eaf477 | 570 | } |
b4fe2683 JM |
571 | } |
572 | ||
573 | /* Like htab_find_slot_with_hash, but compute the hash value from the | |
574 | element. */ | |
eb383413 | 575 | |
e0f3df8f | 576 | PTR |
49b1fae4 | 577 | htab_find (htab_t htab, const PTR element) |
b4fe2683 JM |
578 | { |
579 | return htab_find_with_hash (htab, element, (*htab->hash_f) (element)); | |
580 | } | |
581 | ||
582 | /* This function searches for a hash table slot containing an entry | |
583 | equal to the given element. To delete an entry, call this with | |
bac7199c DD |
584 | insert=NO_INSERT, then call htab_clear_slot on the slot returned |
585 | (possibly after doing some checks). To insert an entry, call this | |
586 | with insert=INSERT, then write the value you want into the returned | |
587 | slot. When inserting an entry, NULL may be returned if memory | |
588 | allocation fails. */ | |
b4fe2683 | 589 | |
e0f3df8f | 590 | PTR * |
49b1fae4 DD |
591 | htab_find_slot_with_hash (htab_t htab, const PTR element, |
592 | hashval_t hash, enum insert_option insert) | |
b4fe2683 | 593 | { |
e0f3df8f | 594 | PTR *first_deleted_slot; |
fe046a17 | 595 | hashval_t index, hash2; |
b4fe2683 | 596 | size_t size; |
b1c933fc | 597 | PTR entry; |
b4fe2683 | 598 | |
fe046a17 DD |
599 | size = htab_size (htab); |
600 | if (insert == INSERT && size * 3 <= htab->n_elements * 4) | |
601 | { | |
602 | if (htab_expand (htab) == 0) | |
603 | return NULL; | |
604 | size = htab_size (htab); | |
605 | } | |
b4fe2683 | 606 | |
fe046a17 | 607 | index = htab_mod (hash, htab); |
b4fe2683 | 608 | |
e2eaf477 | 609 | htab->searches++; |
b4fe2683 JM |
610 | first_deleted_slot = NULL; |
611 | ||
b1c933fc RH |
612 | entry = htab->entries[index]; |
613 | if (entry == EMPTY_ENTRY) | |
614 | goto empty_entry; | |
615 | else if (entry == DELETED_ENTRY) | |
616 | first_deleted_slot = &htab->entries[index]; | |
617 | else if ((*htab->eq_f) (entry, element)) | |
618 | return &htab->entries[index]; | |
619 | ||
fe046a17 | 620 | hash2 = htab_mod_m2 (hash, htab); |
b4fe2683 | 621 | for (;;) |
e2eaf477 | 622 | { |
b1c933fc RH |
623 | htab->collisions++; |
624 | index += hash2; | |
625 | if (index >= size) | |
626 | index -= size; | |
627 | ||
628 | entry = htab->entries[index]; | |
b4fe2683 | 629 | if (entry == EMPTY_ENTRY) |
b1c933fc RH |
630 | goto empty_entry; |
631 | else if (entry == DELETED_ENTRY) | |
b4fe2683 JM |
632 | { |
633 | if (!first_deleted_slot) | |
634 | first_deleted_slot = &htab->entries[index]; | |
635 | } | |
b1c933fc | 636 | else if ((*htab->eq_f) (entry, element)) |
eb383413 | 637 | return &htab->entries[index]; |
e2eaf477 | 638 | } |
b1c933fc RH |
639 | |
640 | empty_entry: | |
641 | if (insert == NO_INSERT) | |
642 | return NULL; | |
643 | ||
b1c933fc RH |
644 | if (first_deleted_slot) |
645 | { | |
686e72d7 | 646 | htab->n_deleted--; |
b1c933fc RH |
647 | *first_deleted_slot = EMPTY_ENTRY; |
648 | return first_deleted_slot; | |
649 | } | |
650 | ||
686e72d7 | 651 | htab->n_elements++; |
b1c933fc | 652 | return &htab->entries[index]; |
e2eaf477 ILT |
653 | } |
654 | ||
b4fe2683 JM |
655 | /* Like htab_find_slot_with_hash, but compute the hash value from the |
656 | element. */ | |
eb383413 | 657 | |
e0f3df8f | 658 | PTR * |
49b1fae4 | 659 | htab_find_slot (htab_t htab, const PTR element, enum insert_option insert) |
b4fe2683 JM |
660 | { |
661 | return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element), | |
662 | insert); | |
663 | } | |
664 | ||
d6ea4e80 DD |
665 | /* This function deletes an element with the given value from hash |
666 | table (the hash is computed from the element). If there is no matching | |
667 | element in the hash table, this function does nothing. */ | |
668 | ||
669 | void | |
49b1fae4 | 670 | htab_remove_elt (htab_t htab, PTR element) |
d6ea4e80 DD |
671 | { |
672 | htab_remove_elt_with_hash (htab, element, (*htab->hash_f) (element)); | |
673 | } | |
674 | ||
675 | ||
b4fe2683 JM |
676 | /* This function deletes an element with the given value from hash |
677 | table. If there is no matching element in the hash table, this | |
678 | function does nothing. */ | |
e2eaf477 ILT |
679 | |
680 | void | |
49b1fae4 | 681 | htab_remove_elt_with_hash (htab_t htab, PTR element, hashval_t hash) |
e2eaf477 | 682 | { |
e0f3df8f | 683 | PTR *slot; |
b4fe2683 | 684 | |
d6ea4e80 | 685 | slot = htab_find_slot_with_hash (htab, element, hash, NO_INSERT); |
b4fe2683 JM |
686 | if (*slot == EMPTY_ENTRY) |
687 | return; | |
688 | ||
689 | if (htab->del_f) | |
690 | (*htab->del_f) (*slot); | |
e2eaf477 | 691 | |
b4fe2683 JM |
692 | *slot = DELETED_ENTRY; |
693 | htab->n_deleted++; | |
e2eaf477 ILT |
694 | } |
695 | ||
b4fe2683 JM |
696 | /* This function clears a specified slot in a hash table. It is |
697 | useful when you've already done the lookup and don't want to do it | |
698 | again. */ | |
e2eaf477 ILT |
699 | |
700 | void | |
49b1fae4 | 701 | htab_clear_slot (htab_t htab, PTR *slot) |
e2eaf477 | 702 | { |
fe046a17 | 703 | if (slot < htab->entries || slot >= htab->entries + htab_size (htab) |
e2eaf477 ILT |
704 | || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY) |
705 | abort (); | |
eb383413 | 706 | |
b4fe2683 JM |
707 | if (htab->del_f) |
708 | (*htab->del_f) (*slot); | |
eb383413 | 709 | |
e2eaf477 | 710 | *slot = DELETED_ENTRY; |
b4fe2683 | 711 | htab->n_deleted++; |
e2eaf477 ILT |
712 | } |
713 | ||
714 | /* This function scans over the entire hash table calling | |
715 | CALLBACK for each live entry. If CALLBACK returns false, | |
716 | the iteration stops. INFO is passed as CALLBACK's second | |
717 | argument. */ | |
718 | ||
719 | void | |
49b1fae4 | 720 | htab_traverse_noresize (htab_t htab, htab_trav callback, PTR info) |
e2eaf477 | 721 | { |
c4d8feb2 DD |
722 | PTR *slot; |
723 | PTR *limit; | |
724 | ||
c4d8feb2 | 725 | slot = htab->entries; |
fe046a17 | 726 | limit = slot + htab_size (htab); |
eb383413 | 727 | |
b4fe2683 JM |
728 | do |
729 | { | |
e0f3df8f | 730 | PTR x = *slot; |
eb383413 | 731 | |
b4fe2683 JM |
732 | if (x != EMPTY_ENTRY && x != DELETED_ENTRY) |
733 | if (!(*callback) (slot, info)) | |
734 | break; | |
735 | } | |
736 | while (++slot < limit); | |
e2eaf477 ILT |
737 | } |
738 | ||
f77ed96c DD |
739 | /* Like htab_traverse_noresize, but does resize the table when it is |
740 | too empty to improve effectivity of subsequent calls. */ | |
741 | ||
742 | void | |
49b1fae4 | 743 | htab_traverse (htab_t htab, htab_trav callback, PTR info) |
f77ed96c | 744 | { |
fe046a17 | 745 | if (htab_elements (htab) * 8 < htab_size (htab)) |
f77ed96c DD |
746 | htab_expand (htab); |
747 | ||
748 | htab_traverse_noresize (htab, callback, info); | |
749 | } | |
750 | ||
eb383413 L |
751 | /* Return the fraction of fixed collisions during all work with given |
752 | hash table. */ | |
e2eaf477 | 753 | |
b4fe2683 | 754 | double |
49b1fae4 | 755 | htab_collisions (htab_t htab) |
e2eaf477 | 756 | { |
eb383413 | 757 | if (htab->searches == 0) |
b4fe2683 | 758 | return 0.0; |
eb383413 L |
759 | |
760 | return (double) htab->collisions / (double) htab->searches; | |
e2eaf477 | 761 | } |
8fc34799 | 762 | |
68a41de7 DD |
763 | /* Hash P as a null-terminated string. |
764 | ||
765 | Copied from gcc/hashtable.c. Zack had the following to say with respect | |
766 | to applicability, though note that unlike hashtable.c, this hash table | |
767 | implementation re-hashes rather than chain buckets. | |
768 | ||
769 | http://gcc.gnu.org/ml/gcc-patches/2001-08/msg01021.html | |
770 | From: Zack Weinberg <zackw@panix.com> | |
771 | Date: Fri, 17 Aug 2001 02:15:56 -0400 | |
772 | ||
773 | I got it by extracting all the identifiers from all the source code | |
774 | I had lying around in mid-1999, and testing many recurrences of | |
775 | the form "H_n = H_{n-1} * K + c_n * L + M" where K, L, M were either | |
776 | prime numbers or the appropriate identity. This was the best one. | |
777 | I don't remember exactly what constituted "best", except I was | |
778 | looking at bucket-length distributions mostly. | |
779 | ||
780 | So it should be very good at hashing identifiers, but might not be | |
781 | as good at arbitrary strings. | |
782 | ||
783 | I'll add that it thoroughly trounces the hash functions recommended | |
784 | for this use at http://burtleburtle.net/bob/hash/index.html, both | |
785 | on speed and bucket distribution. I haven't tried it against the | |
786 | function they just started using for Perl's hashes. */ | |
8fc34799 DD |
787 | |
788 | hashval_t | |
49b1fae4 | 789 | htab_hash_string (const PTR p) |
8fc34799 DD |
790 | { |
791 | const unsigned char *str = (const unsigned char *) p; | |
792 | hashval_t r = 0; | |
793 | unsigned char c; | |
794 | ||
795 | while ((c = *str++) != 0) | |
796 | r = r * 67 + c - 113; | |
797 | ||
798 | return r; | |
799 | } | |
7108c5dc JM |
800 | |
801 | /* DERIVED FROM: | |
802 | -------------------------------------------------------------------- | |
803 | lookup2.c, by Bob Jenkins, December 1996, Public Domain. | |
804 | hash(), hash2(), hash3, and mix() are externally useful functions. | |
805 | Routines to test the hash are included if SELF_TEST is defined. | |
806 | You can use this free for any purpose. It has no warranty. | |
807 | -------------------------------------------------------------------- | |
808 | */ | |
809 | ||
810 | /* | |
811 | -------------------------------------------------------------------- | |
812 | mix -- mix 3 32-bit values reversibly. | |
813 | For every delta with one or two bit set, and the deltas of all three | |
814 | high bits or all three low bits, whether the original value of a,b,c | |
815 | is almost all zero or is uniformly distributed, | |
816 | * If mix() is run forward or backward, at least 32 bits in a,b,c | |
817 | have at least 1/4 probability of changing. | |
818 | * If mix() is run forward, every bit of c will change between 1/3 and | |
819 | 2/3 of the time. (Well, 22/100 and 78/100 for some 2-bit deltas.) | |
820 | mix() was built out of 36 single-cycle latency instructions in a | |
821 | structure that could supported 2x parallelism, like so: | |
822 | a -= b; | |
823 | a -= c; x = (c>>13); | |
824 | b -= c; a ^= x; | |
825 | b -= a; x = (a<<8); | |
826 | c -= a; b ^= x; | |
827 | c -= b; x = (b>>13); | |
828 | ... | |
829 | Unfortunately, superscalar Pentiums and Sparcs can't take advantage | |
830 | of that parallelism. They've also turned some of those single-cycle | |
831 | latency instructions into multi-cycle latency instructions. Still, | |
832 | this is the fastest good hash I could find. There were about 2^^68 | |
833 | to choose from. I only looked at a billion or so. | |
834 | -------------------------------------------------------------------- | |
835 | */ | |
836 | /* same, but slower, works on systems that might have 8 byte hashval_t's */ | |
837 | #define mix(a,b,c) \ | |
838 | { \ | |
839 | a -= b; a -= c; a ^= (c>>13); \ | |
840 | b -= c; b -= a; b ^= (a<< 8); \ | |
841 | c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \ | |
842 | a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \ | |
843 | b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \ | |
844 | c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \ | |
845 | a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \ | |
846 | b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \ | |
847 | c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \ | |
848 | } | |
849 | ||
850 | /* | |
851 | -------------------------------------------------------------------- | |
852 | hash() -- hash a variable-length key into a 32-bit value | |
853 | k : the key (the unaligned variable-length array of bytes) | |
854 | len : the length of the key, counting by bytes | |
855 | level : can be any 4-byte value | |
856 | Returns a 32-bit value. Every bit of the key affects every bit of | |
857 | the return value. Every 1-bit and 2-bit delta achieves avalanche. | |
858 | About 36+6len instructions. | |
859 | ||
860 | The best hash table sizes are powers of 2. There is no need to do | |
861 | mod a prime (mod is sooo slow!). If you need less than 32 bits, | |
862 | use a bitmask. For example, if you need only 10 bits, do | |
863 | h = (h & hashmask(10)); | |
864 | In which case, the hash table should have hashsize(10) elements. | |
865 | ||
866 | If you are hashing n strings (ub1 **)k, do it like this: | |
867 | for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h); | |
868 | ||
869 | By Bob Jenkins, 1996. bob_jenkins@burtleburtle.net. You may use this | |
870 | code any way you wish, private, educational, or commercial. It's free. | |
871 | ||
872 | See http://burtleburtle.net/bob/hash/evahash.html | |
873 | Use for hash table lookup, or anything where one collision in 2^32 is | |
874 | acceptable. Do NOT use for cryptographic purposes. | |
875 | -------------------------------------------------------------------- | |
876 | */ | |
877 | ||
49b1fae4 DD |
878 | hashval_t |
879 | iterative_hash (const PTR k_in /* the key */, | |
880 | register size_t length /* the length of the key */, | |
881 | register hashval_t initval /* the previous hash, or | |
882 | an arbitrary value */) | |
7108c5dc JM |
883 | { |
884 | register const unsigned char *k = (const unsigned char *)k_in; | |
885 | register hashval_t a,b,c,len; | |
886 | ||
887 | /* Set up the internal state */ | |
888 | len = length; | |
889 | a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */ | |
890 | c = initval; /* the previous hash value */ | |
891 | ||
892 | /*---------------------------------------- handle most of the key */ | |
893 | #ifndef WORDS_BIGENDIAN | |
894 | /* On a little-endian machine, if the data is 4-byte aligned we can hash | |
895 | by word for better speed. This gives nondeterministic results on | |
896 | big-endian machines. */ | |
897 | if (sizeof (hashval_t) == 4 && (((size_t)k)&3) == 0) | |
898 | while (len >= 12) /* aligned */ | |
899 | { | |
900 | a += *(hashval_t *)(k+0); | |
901 | b += *(hashval_t *)(k+4); | |
902 | c += *(hashval_t *)(k+8); | |
903 | mix(a,b,c); | |
904 | k += 12; len -= 12; | |
905 | } | |
906 | else /* unaligned */ | |
907 | #endif | |
908 | while (len >= 12) | |
909 | { | |
910 | a += (k[0] +((hashval_t)k[1]<<8) +((hashval_t)k[2]<<16) +((hashval_t)k[3]<<24)); | |
911 | b += (k[4] +((hashval_t)k[5]<<8) +((hashval_t)k[6]<<16) +((hashval_t)k[7]<<24)); | |
912 | c += (k[8] +((hashval_t)k[9]<<8) +((hashval_t)k[10]<<16)+((hashval_t)k[11]<<24)); | |
913 | mix(a,b,c); | |
914 | k += 12; len -= 12; | |
915 | } | |
916 | ||
917 | /*------------------------------------- handle the last 11 bytes */ | |
918 | c += length; | |
919 | switch(len) /* all the case statements fall through */ | |
920 | { | |
921 | case 11: c+=((hashval_t)k[10]<<24); | |
922 | case 10: c+=((hashval_t)k[9]<<16); | |
923 | case 9 : c+=((hashval_t)k[8]<<8); | |
924 | /* the first byte of c is reserved for the length */ | |
925 | case 8 : b+=((hashval_t)k[7]<<24); | |
926 | case 7 : b+=((hashval_t)k[6]<<16); | |
927 | case 6 : b+=((hashval_t)k[5]<<8); | |
928 | case 5 : b+=k[4]; | |
929 | case 4 : a+=((hashval_t)k[3]<<24); | |
930 | case 3 : a+=((hashval_t)k[2]<<16); | |
931 | case 2 : a+=((hashval_t)k[1]<<8); | |
932 | case 1 : a+=k[0]; | |
933 | /* case 0: nothing left to add */ | |
934 | } | |
935 | mix(a,b,c); | |
936 | /*-------------------------------------------- report the result */ | |
937 | return c; | |
938 | } |