]> git.ipfire.org Git - thirdparty/binutils-gdb.git/blob - libiberty/hashtab.c
* hashtab.c (higher_prime_number): Use 7 as minimum.
[thirdparty/binutils-gdb.git] / libiberty / hashtab.c
1 /* An expandable hash tables datatype.
2 Copyright (C) 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov (vmakarov@cygnus.com).
4
5 This file is part of the libiberty library.
6 Libiberty is free software; you can redistribute it and/or
7 modify it under the terms of the GNU Library General Public
8 License as published by the Free Software Foundation; either
9 version 2 of the License, or (at your option) any later version.
10
11 Libiberty is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 Library General Public License for more details.
15
16 You should have received a copy of the GNU Library General Public
17 License along with libiberty; see the file COPYING.LIB. If
18 not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
20
21 /* This package implements basic hash table functionality. It is possible
22 to search for an entry, create an entry and destroy an entry.
23
24 Elements in the table are generic pointers.
25
26 The size of the table is not fixed; if the occupancy of the table
27 grows too high the hash table will be expanded.
28
29 The abstract data implementation is based on generalized Algorithm D
30 from Knuth's book "The art of computer programming". Hash table is
31 expanded by creation of new hash table and transferring elements from
32 the old table to the new table. */
33
34 #ifdef HAVE_CONFIG_H
35 #include "config.h"
36 #endif
37
38 #include <sys/types.h>
39
40 #ifdef HAVE_STDLIB_H
41 #include <stdlib.h>
42 #endif
43
44 #ifdef HAVE_STRING_H
45 #include <string.h>
46 #endif
47
48 #include <stdio.h>
49
50 #include "libiberty.h"
51 #include "hashtab.h"
52
53 /* This macro defines reserved value for empty table entry. */
54
55 #define EMPTY_ENTRY ((PTR) 0)
56
57 /* This macro defines reserved value for table entry which contained
58 a deleted element. */
59
60 #define DELETED_ENTRY ((PTR) 1)
61
62 static unsigned long higher_prime_number PARAMS ((unsigned long));
63 static hashval_t hash_pointer PARAMS ((const void *));
64 static int eq_pointer PARAMS ((const void *, const void *));
65 static int htab_expand PARAMS ((htab_t));
66 static PTR *find_empty_slot_for_expand PARAMS ((htab_t, hashval_t));
67
68 /* At some point, we could make these be NULL, and modify the
69 hash-table routines to handle NULL specially; that would avoid
70 function-call overhead for the common case of hashing pointers. */
71 htab_hash htab_hash_pointer = hash_pointer;
72 htab_eq htab_eq_pointer = eq_pointer;
73
74 /* The following function returns a nearest prime number which is
75 greater than N, and near a power of two. */
76
77 static unsigned long
78 higher_prime_number (n)
79 unsigned long n;
80 {
81 /* These are primes that are near, but slightly smaller than, a
82 power of two. */
83 static const unsigned long primes[] = {
84 (unsigned long) 7,
85 (unsigned long) 13,
86 (unsigned long) 31,
87 (unsigned long) 61,
88 (unsigned long) 127,
89 (unsigned long) 251,
90 (unsigned long) 509,
91 (unsigned long) 1021,
92 (unsigned long) 2039,
93 (unsigned long) 4093,
94 (unsigned long) 8191,
95 (unsigned long) 16381,
96 (unsigned long) 32749,
97 (unsigned long) 65521,
98 (unsigned long) 131071,
99 (unsigned long) 262139,
100 (unsigned long) 524287,
101 (unsigned long) 1048573,
102 (unsigned long) 2097143,
103 (unsigned long) 4194301,
104 (unsigned long) 8388593,
105 (unsigned long) 16777213,
106 (unsigned long) 33554393,
107 (unsigned long) 67108859,
108 (unsigned long) 134217689,
109 (unsigned long) 268435399,
110 (unsigned long) 536870909,
111 (unsigned long) 1073741789,
112 (unsigned long) 2147483647,
113 /* 4294967291L */
114 ((unsigned long) 2147483647) + ((unsigned long) 2147483644),
115 };
116
117 const unsigned long *low = &primes[0];
118 const unsigned long *high = &primes[sizeof(primes) / sizeof(primes[0])];
119
120 while (low != high)
121 {
122 const unsigned long *mid = low + (high - low) / 2;
123 if (n > *mid)
124 low = mid + 1;
125 else
126 high = mid;
127 }
128
129 /* If we've run out of primes, abort. */
130 if (n > *low)
131 {
132 fprintf (stderr, "Cannot find prime bigger than %lu\n", n);
133 abort ();
134 }
135
136 return *low;
137 }
138
139 /* Returns a hash code for P. */
140
141 static hashval_t
142 hash_pointer (p)
143 const PTR p;
144 {
145 return (hashval_t) ((long)p >> 3);
146 }
147
148 /* Returns non-zero if P1 and P2 are equal. */
149
150 static int
151 eq_pointer (p1, p2)
152 const PTR p1;
153 const PTR p2;
154 {
155 return p1 == p2;
156 }
157
158 /* This function creates table with length slightly longer than given
159 source length. Created hash table is initiated as empty (all the
160 hash table entries are EMPTY_ENTRY). The function returns the
161 created hash table. Memory allocation must not fail. */
162
163 htab_t
164 htab_create (size, hash_f, eq_f, del_f)
165 size_t size;
166 htab_hash hash_f;
167 htab_eq eq_f;
168 htab_del del_f;
169 {
170 htab_t result;
171
172 size = higher_prime_number (size);
173 result = (htab_t) xcalloc (1, sizeof (struct htab));
174 result->entries = (PTR *) xcalloc (size, sizeof (PTR));
175 result->size = size;
176 result->hash_f = hash_f;
177 result->eq_f = eq_f;
178 result->del_f = del_f;
179 result->return_allocation_failure = 0;
180 return result;
181 }
182
183 /* This function creates table with length slightly longer than given
184 source length. The created hash table is initiated as empty (all the
185 hash table entries are EMPTY_ENTRY). The function returns the created
186 hash table. Memory allocation may fail; it may return NULL. */
187
188 htab_t
189 htab_try_create (size, hash_f, eq_f, del_f)
190 size_t size;
191 htab_hash hash_f;
192 htab_eq eq_f;
193 htab_del del_f;
194 {
195 htab_t result;
196
197 size = higher_prime_number (size);
198 result = (htab_t) calloc (1, sizeof (struct htab));
199 if (result == NULL)
200 return NULL;
201
202 result->entries = (PTR *) calloc (size, sizeof (PTR));
203 if (result->entries == NULL)
204 {
205 free (result);
206 return NULL;
207 }
208
209 result->size = size;
210 result->hash_f = hash_f;
211 result->eq_f = eq_f;
212 result->del_f = del_f;
213 result->return_allocation_failure = 1;
214 return result;
215 }
216
217 /* This function frees all memory allocated for given hash table.
218 Naturally the hash table must already exist. */
219
220 void
221 htab_delete (htab)
222 htab_t htab;
223 {
224 int i;
225
226 if (htab->del_f)
227 for (i = htab->size - 1; i >= 0; i--)
228 if (htab->entries[i] != EMPTY_ENTRY
229 && htab->entries[i] != DELETED_ENTRY)
230 (*htab->del_f) (htab->entries[i]);
231
232 free (htab->entries);
233 free (htab);
234 }
235
236 /* This function clears all entries in the given hash table. */
237
238 void
239 htab_empty (htab)
240 htab_t htab;
241 {
242 int i;
243
244 if (htab->del_f)
245 for (i = htab->size - 1; i >= 0; i--)
246 if (htab->entries[i] != EMPTY_ENTRY
247 && htab->entries[i] != DELETED_ENTRY)
248 (*htab->del_f) (htab->entries[i]);
249
250 memset (htab->entries, 0, htab->size * sizeof (PTR));
251 }
252
253 /* Similar to htab_find_slot, but without several unwanted side effects:
254 - Does not call htab->eq_f when it finds an existing entry.
255 - Does not change the count of elements/searches/collisions in the
256 hash table.
257 This function also assumes there are no deleted entries in the table.
258 HASH is the hash value for the element to be inserted. */
259
260 static PTR *
261 find_empty_slot_for_expand (htab, hash)
262 htab_t htab;
263 hashval_t hash;
264 {
265 size_t size = htab->size;
266 unsigned int index = hash % size;
267 PTR *slot = htab->entries + index;
268 hashval_t hash2;
269
270 if (*slot == EMPTY_ENTRY)
271 return slot;
272 else if (*slot == DELETED_ENTRY)
273 abort ();
274
275 hash2 = 1 + hash % (size - 2);
276 for (;;)
277 {
278 index += hash2;
279 if (index >= size)
280 index -= size;
281
282 slot = htab->entries + index;
283 if (*slot == EMPTY_ENTRY)
284 return slot;
285 else if (*slot == DELETED_ENTRY)
286 abort ();
287 }
288 }
289
290 /* The following function changes size of memory allocated for the
291 entries and repeatedly inserts the table elements. The occupancy
292 of the table after the call will be about 50%. Naturally the hash
293 table must already exist. Remember also that the place of the
294 table entries is changed. If memory allocation failures are allowed,
295 this function will return zero, indicating that the table could not be
296 expanded. If all goes well, it will return a non-zero value. */
297
298 static int
299 htab_expand (htab)
300 htab_t htab;
301 {
302 PTR *oentries;
303 PTR *olimit;
304 PTR *p;
305
306 oentries = htab->entries;
307 olimit = oentries + htab->size;
308
309 htab->size = higher_prime_number (htab->size * 2);
310
311 if (htab->return_allocation_failure)
312 {
313 PTR *nentries = (PTR *) calloc (htab->size, sizeof (PTR *));
314 if (nentries == NULL)
315 return 0;
316 htab->entries = nentries;
317 }
318 else
319 htab->entries = (PTR *) xcalloc (htab->size, sizeof (PTR *));
320
321 htab->n_elements -= htab->n_deleted;
322 htab->n_deleted = 0;
323
324 p = oentries;
325 do
326 {
327 PTR x = *p;
328
329 if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
330 {
331 PTR *q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
332
333 *q = x;
334 }
335
336 p++;
337 }
338 while (p < olimit);
339
340 free (oentries);
341 return 1;
342 }
343
344 /* This function searches for a hash table entry equal to the given
345 element. It cannot be used to insert or delete an element. */
346
347 PTR
348 htab_find_with_hash (htab, element, hash)
349 htab_t htab;
350 const PTR element;
351 hashval_t hash;
352 {
353 unsigned int index;
354 hashval_t hash2;
355 size_t size;
356 PTR entry;
357
358 htab->searches++;
359 size = htab->size;
360 index = hash % size;
361
362 entry = htab->entries[index];
363 if (entry == EMPTY_ENTRY
364 || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
365 return entry;
366
367 hash2 = 1 + hash % (size - 2);
368
369 for (;;)
370 {
371 htab->collisions++;
372 index += hash2;
373 if (index >= size)
374 index -= size;
375
376 entry = htab->entries[index];
377 if (entry == EMPTY_ENTRY
378 || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
379 return entry;
380 }
381 }
382
383 /* Like htab_find_slot_with_hash, but compute the hash value from the
384 element. */
385
386 PTR
387 htab_find (htab, element)
388 htab_t htab;
389 const PTR element;
390 {
391 return htab_find_with_hash (htab, element, (*htab->hash_f) (element));
392 }
393
394 /* This function searches for a hash table slot containing an entry
395 equal to the given element. To delete an entry, call this with
396 INSERT = 0, then call htab_clear_slot on the slot returned (possibly
397 after doing some checks). To insert an entry, call this with
398 INSERT = 1, then write the value you want into the returned slot.
399 When inserting an entry, NULL may be returned if memory allocation
400 fails. */
401
402 PTR *
403 htab_find_slot_with_hash (htab, element, hash, insert)
404 htab_t htab;
405 const PTR element;
406 hashval_t hash;
407 enum insert_option insert;
408 {
409 PTR *first_deleted_slot;
410 unsigned int index;
411 hashval_t hash2;
412 size_t size;
413 PTR entry;
414
415 if (insert == INSERT && htab->size * 3 <= htab->n_elements * 4
416 && htab_expand (htab) == 0)
417 return NULL;
418
419 size = htab->size;
420 index = hash % size;
421
422 htab->searches++;
423 first_deleted_slot = NULL;
424
425 entry = htab->entries[index];
426 if (entry == EMPTY_ENTRY)
427 goto empty_entry;
428 else if (entry == DELETED_ENTRY)
429 first_deleted_slot = &htab->entries[index];
430 else if ((*htab->eq_f) (entry, element))
431 return &htab->entries[index];
432
433 hash2 = 1 + hash % (size - 2);
434 for (;;)
435 {
436 htab->collisions++;
437 index += hash2;
438 if (index >= size)
439 index -= size;
440
441 entry = htab->entries[index];
442 if (entry == EMPTY_ENTRY)
443 goto empty_entry;
444 else if (entry == DELETED_ENTRY)
445 {
446 if (!first_deleted_slot)
447 first_deleted_slot = &htab->entries[index];
448 }
449 else if ((*htab->eq_f) (entry, element))
450 return &htab->entries[index];
451 }
452
453 empty_entry:
454 if (insert == NO_INSERT)
455 return NULL;
456
457 htab->n_elements++;
458
459 if (first_deleted_slot)
460 {
461 *first_deleted_slot = EMPTY_ENTRY;
462 return first_deleted_slot;
463 }
464
465 return &htab->entries[index];
466 }
467
468 /* Like htab_find_slot_with_hash, but compute the hash value from the
469 element. */
470
471 PTR *
472 htab_find_slot (htab, element, insert)
473 htab_t htab;
474 const PTR element;
475 enum insert_option insert;
476 {
477 return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
478 insert);
479 }
480
481 /* This function deletes an element with the given value from hash
482 table. If there is no matching element in the hash table, this
483 function does nothing. */
484
485 void
486 htab_remove_elt (htab, element)
487 htab_t htab;
488 PTR element;
489 {
490 PTR *slot;
491
492 slot = htab_find_slot (htab, element, NO_INSERT);
493 if (*slot == EMPTY_ENTRY)
494 return;
495
496 if (htab->del_f)
497 (*htab->del_f) (*slot);
498
499 *slot = DELETED_ENTRY;
500 htab->n_deleted++;
501 }
502
503 /* This function clears a specified slot in a hash table. It is
504 useful when you've already done the lookup and don't want to do it
505 again. */
506
507 void
508 htab_clear_slot (htab, slot)
509 htab_t htab;
510 PTR *slot;
511 {
512 if (slot < htab->entries || slot >= htab->entries + htab->size
513 || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY)
514 abort ();
515
516 if (htab->del_f)
517 (*htab->del_f) (*slot);
518
519 *slot = DELETED_ENTRY;
520 htab->n_deleted++;
521 }
522
523 /* This function scans over the entire hash table calling
524 CALLBACK for each live entry. If CALLBACK returns false,
525 the iteration stops. INFO is passed as CALLBACK's second
526 argument. */
527
528 void
529 htab_traverse (htab, callback, info)
530 htab_t htab;
531 htab_trav callback;
532 PTR info;
533 {
534 PTR *slot = htab->entries;
535 PTR *limit = slot + htab->size;
536
537 do
538 {
539 PTR x = *slot;
540
541 if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
542 if (!(*callback) (slot, info))
543 break;
544 }
545 while (++slot < limit);
546 }
547
548 /* Return the current size of given hash table. */
549
550 size_t
551 htab_size (htab)
552 htab_t htab;
553 {
554 return htab->size;
555 }
556
557 /* Return the current number of elements in given hash table. */
558
559 size_t
560 htab_elements (htab)
561 htab_t htab;
562 {
563 return htab->n_elements - htab->n_deleted;
564 }
565
566 /* Return the fraction of fixed collisions during all work with given
567 hash table. */
568
569 double
570 htab_collisions (htab)
571 htab_t htab;
572 {
573 if (htab->searches == 0)
574 return 0.0;
575
576 return (double) htab->collisions / (double) htab->searches;
577 }
578
579 /* Hash P as a null-terminated string.
580
581 Copied from gcc/hashtable.c. Zack had the following to say with respect
582 to applicability, though note that unlike hashtable.c, this hash table
583 implementation re-hashes rather than chain buckets.
584
585 http://gcc.gnu.org/ml/gcc-patches/2001-08/msg01021.html
586 From: Zack Weinberg <zackw@panix.com>
587 Date: Fri, 17 Aug 2001 02:15:56 -0400
588
589 I got it by extracting all the identifiers from all the source code
590 I had lying around in mid-1999, and testing many recurrences of
591 the form "H_n = H_{n-1} * K + c_n * L + M" where K, L, M were either
592 prime numbers or the appropriate identity. This was the best one.
593 I don't remember exactly what constituted "best", except I was
594 looking at bucket-length distributions mostly.
595
596 So it should be very good at hashing identifiers, but might not be
597 as good at arbitrary strings.
598
599 I'll add that it thoroughly trounces the hash functions recommended
600 for this use at http://burtleburtle.net/bob/hash/index.html, both
601 on speed and bucket distribution. I haven't tried it against the
602 function they just started using for Perl's hashes. */
603
604 hashval_t
605 htab_hash_string (p)
606 const PTR p;
607 {
608 const unsigned char *str = (const unsigned char *) p;
609 hashval_t r = 0;
610 unsigned char c;
611
612 while ((c = *str++) != 0)
613 r = r * 67 + c - 113;
614
615 return r;
616 }