Debian Codegraph @

lib/hash.c

raw
1 /* hash - hashing table processing.
2
3 Copyright (C) 1998-2004, 2006-2007, 2009-2026 Free Software Foundation, Inc.
4
5 Written by Jim Meyering, 1992.
6
7 This file is free software: you can redistribute it and/or modify
8 it under the terms of the GNU Lesser General Public License as
9 published by the Free Software Foundation; either version 2.1 of the
10 License, or (at your option) any later version.
11
12 This file 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
15 GNU Lesser General Public License for more details.
16
17 You should have received a copy of the GNU Lesser General Public License
18 along with this program. If not, see <https://www.gnu.org/licenses/>. */
19
20 /* A generic hash table package. */
21
22 /* Define USE_OBSTACK to 1 if you want the allocator to use obstacks instead
23 of malloc. If you change USE_OBSTACK, you have to recompile! */
24
25 #include <config.h>
26
27 #include "hash.h"
28
29 #include "bitrotate.h"
30 #include "next-prime.h"
31 #include "xalloc-oversized.h"
32
33 #include <errno.h>
34 #include <stdint.h>
35 #include <stdio.h>
36 #include <stdlib.h>
37
38 #if USE_OBSTACK
39 # include "obstack.h"
40 # ifndef obstack_chunk_alloc
41 # define obstack_chunk_alloc malloc
42 # endif
43 # ifndef obstack_chunk_free
44 # define obstack_chunk_free free
45 # endif
46 #endif
47
48 struct hash_entry
49 {
50 void *data;
51 struct hash_entry *next;
52 /* Invariant: If DATA is NULL, this entry is an unused bucket head,
53 and therefore NEXT is NULL as well. */
54 };
55
56 struct hash_table
57 {
58 /* The array of buckets starts at BUCKET and extends to BUCKET_LIMIT-1,
59 for a possibility of N_BUCKETS. Among those, N_BUCKETS_USED buckets
60 are not empty, there are N_ENTRIES active entries in the table. */
61 struct hash_entry *bucket;
62 struct hash_entry const *bucket_limit;
63 size_t n_buckets;
64 size_t n_buckets_used;
65 size_t n_entries;
66
67 /* Tuning arguments, kept in a physically separate structure. */
68 const Hash_tuning *tuning;
69
70 /* Three functions are given to 'hash_initialize', see the documentation
71 block for this function. In a word, HASHER randomizes a user entry
72 into a number up from 0 up to some maximum minus 1; COMPARATOR returns
73 true if two user entries compare equally; and DATA_FREER is the cleanup
74 function for a user entry. */
75 Hash_hasher hasher;
76 Hash_comparator comparator;
77 Hash_data_freer data_freer;
78
79 /* A linked list of freed struct hash_entry structs. */
80 struct hash_entry *free_entry_list;
81
82 #if USE_OBSTACK
83 /* Whenever obstacks are used, it is possible to allocate all overflowed
84 entries into a single stack, so they all can be freed in a single
85 operation. It is not clear if the speedup is worth the trouble. */
86 struct obstack entry_stack;
87 #endif
88 };
89
90 /* A hash table contains many internal entries, each holding a pointer to
91 some user-provided data (also called a user entry). An entry indistinctly
92 refers to both the internal entry and its associated user entry. A user
93 entry contents may be hashed by a randomization function (the hashing
94 function, or just "hasher" for short) into a number (or "slot") between 0
95 and the current table size. At each slot position in the hash table,
96 starts a linked chain of entries for which the user data all hash to this
97 slot. A bucket is the collection of all entries hashing to the same slot.
98
99 A good "hasher" function will distribute entries rather evenly in buckets.
100 In the ideal case, the length of each bucket is roughly the number of
101 entries divided by the table size. Finding the slot for a data is usually
102 done in constant time by the "hasher", and the later finding of a precise
103 entry is linear in time with the size of the bucket. Consequently, a
104 larger hash table size (that is, a larger number of buckets) is prone to
105 yielding shorter chains, *given* the "hasher" function behaves properly.
106
107 Long buckets slow down the lookup algorithm. One might use big hash table
108 sizes in hope to reduce the average length of buckets, but this might
109 become inordinate, as unused slots in the hash table take some space. The
110 best bet is to make sure you are using a good "hasher" function (beware
111 that those are not that easy to write! :-), and to use a table size
112 larger than the actual number of entries. */
113
114 /* If an insertion makes the ratio of nonempty buckets to table size larger
115 than the growth threshold (a number between 0.0 and 1.0), then increase
116 the table size by multiplying by the growth factor (a number greater than
117 1.0). The growth threshold defaults to 0.8, and the growth factor
118 defaults to 1.414, meaning that the table will have doubled its size
119 every second time 80% of the buckets get used. */
120 #define DEFAULT_GROWTH_THRESHOLD 0.8f
121 #define DEFAULT_GROWTH_FACTOR 1.414f
122
123 /* If a deletion empties a bucket and causes the ratio of used buckets to
124 table size to become smaller than the shrink threshold (a number between
125 0.0 and 1.0), then shrink the table by multiplying by the shrink factor (a
126 number greater than the shrink threshold but smaller than 1.0). The shrink
127 threshold and factor default to 0.0 and 1.0, meaning that the table never
128 shrinks. */
129 #define DEFAULT_SHRINK_THRESHOLD 0.0f
130 #define DEFAULT_SHRINK_FACTOR 1.0f
131
132 /* Use this to initialize or reset a TUNING structure to
133 some sensible values. */
134 static const Hash_tuning default_tuning =
135 {
136 DEFAULT_SHRINK_THRESHOLD,
137 DEFAULT_SHRINK_FACTOR,
138 DEFAULT_GROWTH_THRESHOLD,
139 DEFAULT_GROWTH_FACTOR,
140 false
141 };
142
143 /* Information and lookup. */
144
145 size_t
146 hash_get_n_buckets (const Hash_table *table)
147 {
148 return table->n_buckets;
149 }
150
151 size_t
152 hash_get_n_buckets_used (const Hash_table *table)
153 {
154 return table->n_buckets_used;
155 }
156
157 size_t
158 hash_get_n_entries (const Hash_table *table)
159 {
160 return table->n_entries;
161 }
162
163 size_t
164 hash_get_max_bucket_length (const Hash_table *table)
165 {
166 size_t max_bucket_length = 0;
167
168 for (struct hash_entry const *bucket = table->bucket;
169 bucket < table->bucket_limit;
170 bucket++)
171 {
172 if (bucket->data)
173 {
174 struct hash_entry const *cursor = bucket;
175 size_t bucket_length = 1;
176
177 while (cursor = cursor->next, cursor)
178 bucket_length++;
179
180 if (bucket_length > max_bucket_length)
181 max_bucket_length = bucket_length;
182 }
183 }
184
185 return max_bucket_length;
186 }
187
188 bool
189 hash_table_ok (const Hash_table *table)
190 {
191 size_t n_buckets_used = 0;
192 size_t n_entries = 0;
193
194 for (struct hash_entry const *bucket = table->bucket;
195 bucket < table->bucket_limit;
196 bucket++)
197 {
198 if (bucket->data)
199 {
200 struct hash_entry const *cursor = bucket;
201
202 /* Count bucket head. */
203 n_buckets_used++;
204 n_entries++;
205
206 /* Count bucket overflow. */
207 while (cursor = cursor->next, cursor)
208 n_entries++;
209 }
210 }
211
212 if (n_buckets_used == table->n_buckets_used && n_entries == table->n_entries)
213 return true;
214
215 return false;
216 }
217
218 void
219 hash_print_statistics (const Hash_table *table, FILE *stream)
220 {
221 size_t n_entries = hash_get_n_entries (table);
222 size_t n_buckets = hash_get_n_buckets (table);
223 size_t n_buckets_used = hash_get_n_buckets_used (table);
224 size_t max_bucket_length = hash_get_max_bucket_length (table);
225
226 fprintf (stream, "# entries: %lu\n", (unsigned long int) n_entries);
227 fprintf (stream, "# buckets: %lu\n", (unsigned long int) n_buckets);
228 fprintf (stream, "# buckets used: %lu (%.2f%%)\n",
229 (unsigned long int) n_buckets_used,
230 (100.0 * n_buckets_used) / n_buckets);
231 fprintf (stream, "max bucket length: %lu\n",
232 (unsigned long int) max_bucket_length);
233 }
234
235 /* Hash KEY and return a pointer to the selected bucket.
236 If TABLE->hasher misbehaves, abort. */
237 static struct hash_entry *
238 safe_hasher (const Hash_table *table, const void *key)
239 {
240 size_t n = table->hasher (key, table->n_buckets);
241 if (! (n < table->n_buckets))
242 abort ();
243 return table->bucket + n;
244 }
245
246 void *
247 hash_lookup (const Hash_table *table, const void *entry)
248 {
249 struct hash_entry const *bucket = safe_hasher (table, entry);
250
251 if (bucket->data == NULL)
252 return NULL;
253
254 for (struct hash_entry const *cursor = bucket; cursor; cursor = cursor->next)
255 if (entry == cursor->data || table->comparator (entry, cursor->data))
256 return cursor->data;
257
258 return NULL;
259 }
260
261 /* Walking. */
262
263 void *
264 hash_get_first (const Hash_table *table)
265 {
266 if (table->n_entries == 0)
267 return NULL;
268
269 for (struct hash_entry const *bucket = table->bucket; ; bucket++)
270 if (! (bucket < table->bucket_limit))
271 abort ();
272 else if (bucket->data)
273 return bucket->data;
274 }
275
276 void *
277 hash_get_next (const Hash_table *table, const void *entry)
278 {
279 struct hash_entry const *bucket = safe_hasher (table, entry);
280
281 /* Find next entry in the same bucket. */
282 {
283 struct hash_entry const *cursor = bucket;
284 do
285 {
286 if (cursor->data == entry && cursor->next)
287 return cursor->next->data;
288 cursor = cursor->next;
289 }
290 while (cursor != NULL);
291 }
292
293 /* Find first entry in any subsequent bucket. */
294 while (++bucket < table->bucket_limit)
295 if (bucket->data)
296 return bucket->data;
297
298 /* None found. */
299 return NULL;
300 }
301
302 size_t
303 hash_get_entries (const Hash_table *table, void **buffer,
304 size_t buffer_size)
305 {
306 size_t counter = 0;
307
308 for (struct hash_entry const *bucket = table->bucket;
309 bucket < table->bucket_limit;
310 bucket++)
311 {
312 if (bucket->data)
313 {
314 for (struct hash_entry const *cursor = bucket; cursor; cursor = cursor->next)
315 {
316 if (counter >= buffer_size)
317 return counter;
318 buffer[counter++] = cursor->data;
319 }
320 }
321 }
322
323 return counter;
324 }
325
326 size_t
327 hash_do_for_each (const Hash_table *table, Hash_processor processor,
328 void *processor_data)
329 {
330 size_t counter = 0;
331
332 for (struct hash_entry const *bucket = table->bucket;
333 bucket < table->bucket_limit;
334 bucket++)
335 {
336 if (bucket->data)
337 {
338 for (struct hash_entry const *cursor = bucket; cursor; cursor = cursor->next)
339 {
340 if (! processor (cursor->data, processor_data))
341 return counter;
342 counter++;
343 }
344 }
345 }
346
347 return counter;
348 }
349
350
351 /* If the user passes a NULL hasher, we hash the raw pointer. */
352 static size_t
353 raw_hasher (const void *data, size_t n)
354 {
355 /* When hashing unique pointers, it is often the case that they were
356 generated by malloc and thus have the property that the low-order
357 bits are 0. As this tends to give poorer performance with small
358 tables, we rotate the pointer value before performing division,
359 in an attempt to improve hash quality. */
360 size_t val = rotr_sz ((size_t) data, 3);
361 return val % n;
362 }
363
364 /* If the user passes a NULL comparator, we use pointer comparison. */
365 static bool
366 raw_comparator (const void *a, const void *b)
367 {
368 return a == b;
369 }
370
371
372 /* Allocation and clean-up. */
373
374 void
375 hash_reset_tuning (Hash_tuning *tuning)
376 {
377 *tuning = default_tuning;
378 }
379
380 /* For the given hash TABLE, check the user supplied tuning structure for
381 reasonable values, and return true if there is no gross error with it.
382 Otherwise, definitively reset the TUNING field to some acceptable default
383 in the hash table (that is, the user loses the right of further modifying
384 tuning arguments), and return false. */
385
386 static bool
387 check_tuning (Hash_table *table)
388 {
389 const Hash_tuning *tuning = table->tuning;
390 if (tuning == &default_tuning)
391 return true;
392
393 /* Be a bit stricter than mathematics would require, so that
394 rounding errors in size calculations do not cause allocations to
395 fail to grow or shrink as they should. The smallest allocation
396 is 11 (due to next_prime's algorithm), so an epsilon of 0.1
397 should be good enough. */
398 float epsilon = 0.1f;
399
400 if (epsilon < tuning->growth_threshold
401 && tuning->growth_threshold < 1 - epsilon
402 && 1 + epsilon < tuning->growth_factor
403 && 0 <= tuning->shrink_threshold
404 && tuning->shrink_threshold + epsilon < tuning->shrink_factor
405 && tuning->shrink_factor <= 1
406 && tuning->shrink_threshold + epsilon < tuning->growth_threshold)
407 return true;
408
409 table->tuning = &default_tuning;
410 return false;
411 }
412
413 /* Compute the size of the bucket array for the given CANDIDATE and
414 TUNING, or return 0 if there is no possible way to allocate that
415 many entries. */
416
417 static size_t _GL_ATTRIBUTE_PURE
418 compute_bucket_size (size_t candidate, const Hash_tuning *tuning)
419 {
420 if (!tuning->is_n_buckets)
421 {
422 float new_candidate = candidate / tuning->growth_threshold;
423 if ((float) SIZE_MAX <= new_candidate)
424 goto nomem;
425 candidate = new_candidate;
426 }
427 candidate = next_prime (candidate);
428 if (xalloc_oversized (candidate, sizeof (struct hash_entry *)))
429 goto nomem;
430 return candidate;
431
432 nomem:
433 errno = ENOMEM;
434 return 0;
435 }
436
437 Hash_table *
438 hash_initialize (size_t candidate, const Hash_tuning *tuning,
439 Hash_hasher hasher, Hash_comparator comparator,
440 Hash_data_freer data_freer)
441 {
442 if (hasher == NULL)
443 hasher = raw_hasher;
444 if (comparator == NULL)
445 comparator = raw_comparator;
446
447 Hash_table *table = malloc (sizeof *table);
448 if (table == NULL)
449 return NULL;
450
451 if (!tuning)
452 tuning = &default_tuning;
453 table->tuning = tuning;
454 if (!check_tuning (table))
455 {
456 /* Fail if the tuning options are invalid. This is the only occasion
457 when the user gets some feedback about it. Once the table is created,
458 if the user provides invalid tuning options, we silently revert to
459 using the defaults, and ignore further request to change the tuning
460 options. */
461 errno = EINVAL;
462 goto fail;
463 }
464
465 table->n_buckets = compute_bucket_size (candidate, tuning);
466 if (!table->n_buckets)
467 goto fail;
468
469 table->bucket = calloc (table->n_buckets, sizeof *table->bucket);
470 if (table->bucket == NULL)
471 goto fail;
472 table->bucket_limit = table->bucket + table->n_buckets;
473 table->n_buckets_used = 0;
474 table->n_entries = 0;
475
476 table->hasher = hasher;
477 table->comparator = comparator;
478 table->data_freer = data_freer;
479
480 table->free_entry_list = NULL;
481 #if USE_OBSTACK
482 obstack_init (&table->entry_stack);
483 #endif
484 return table;
485
486 fail:
487 free (table);
488 return NULL;
489 }
490
491 void
492 hash_clear (Hash_table *table)
493 {
494 for (struct hash_entry *bucket = table->bucket;
495 bucket < table->bucket_limit;
496 bucket++)
497 {
498 if (bucket->data)
499 {
500 /* Free the bucket overflow. */
501 for (struct hash_entry *cursor = bucket->next; cursor; )
502 {
503 if (table->data_freer)
504 table->data_freer (cursor->data);
505 cursor->data = NULL;
506
507 struct hash_entry *next = cursor->next;
508 /* Relinking is done one entry at a time, as it is to be expected
509 that overflows are either rare or short. */
510 cursor->next = table->free_entry_list;
511 table->free_entry_list = cursor;
512
513 cursor = next;
514 }
515
516 /* Free the bucket head. */
517 if (table->data_freer)
518 table->data_freer (bucket->data);
519 bucket->data = NULL;
520 bucket->next = NULL;
521 }
522 }
523
524 table->n_buckets_used = 0;
525 table->n_entries = 0;
526 }
527
528 void
529 hash_free (Hash_table *table)
530 {
531 int saved_errno = errno;
532
533 /* Call the user data_freer function. */
534 if (table->data_freer && table->n_entries)
535 {
536 for (struct hash_entry *bucket = table->bucket;
537 bucket < table->bucket_limit;
538 bucket++)
539 {
540 if (bucket->data)
541 {
542 for (struct hash_entry *cursor = bucket; cursor; cursor = cursor->next)
543 table->data_freer (cursor->data);
544 }
545 }
546 }
547
548 #if USE_OBSTACK
549
550 obstack_free (&table->entry_stack, NULL);
551
552 #else
553
554 /* Free all bucket overflowed entries. */
555 for (struct hash_entry *bucket = table->bucket;
556 bucket < table->bucket_limit;
557 bucket++)
558 {
559 for (struct hash_entry *cursor = bucket->next; cursor; )
560 {
561 struct hash_entry *next = cursor->next;
562 free (cursor);
563 cursor = next;
564 }
565 }
566
567 /* Also reclaim the internal list of previously freed entries. */
568 for (struct hash_entry *cursor = table->free_entry_list; cursor; )
569 {
570 struct hash_entry *next = cursor->next;
571 free (cursor);
572 cursor = next;
573 }
574
575 #endif
576
577 /* Free the remainder of the hash table structure. */
578 free (table->bucket);
579 free (table);
580
581 errno = saved_errno;
582 }
583
584 /* Insertion and deletion. */
585
586 /* Get a new hash entry for a bucket overflow, possibly by recycling a
587 previously freed one. If this is not possible, allocate a new one. */
588
589 static struct hash_entry *
590 allocate_entry (Hash_table *table)
591 {
592 struct hash_entry *new;
593
594 if (table->free_entry_list)
595 {
596 new = table->free_entry_list;
597 table->free_entry_list = new->next;
598 }
599 else
600 {
601 #if USE_OBSTACK
602 new = obstack_alloc (&table->entry_stack, sizeof *new);
603 #else
604 new = malloc (sizeof *new);
605 #endif
606 }
607
608 return new;
609 }
610
611 /* Free a hash entry which was part of some bucket overflow,
612 saving it for later recycling. */
613
614 static void
615 free_entry (Hash_table *table, struct hash_entry *entry)
616 {
617 entry->data = NULL;
618 entry->next = table->free_entry_list;
619 table->free_entry_list = entry;
620 }
621
622 /* This private function is used to help with insertion and deletion. When
623 ENTRY matches an entry in the table, return a pointer to the corresponding
624 user data and set *BUCKET_HEAD to the head of the selected bucket.
625 Otherwise, return NULL. When DELETE is true and ENTRY matches an entry in
626 the table, unlink the matching entry. */
627
628 static void *
629 find_entry (Hash_table *table, const void *entry,
630 struct hash_entry **bucket_head, bool delete)
631 {
632 struct hash_entry *bucket = safe_hasher (table, entry);
633
634 *bucket_head = bucket;
635
636 /* Test for empty bucket. */
637 if (bucket->data == NULL)
638 return NULL;
639
640 /* See if the entry is the first in the bucket. */
641 if (entry == bucket->data || table->comparator (entry, bucket->data))
642 {
643 void *data = bucket->data;
644
645 if (delete)
646 {
647 if (bucket->next)
648 {
649 struct hash_entry *next = bucket->next;
650
651 /* Bump the first overflow entry into the bucket head, then save
652 the previous first overflow entry for later recycling. */
653 *bucket = *next;
654 free_entry (table, next);
655 }
656 else
657 {
658 bucket->data = NULL;
659 }
660 }
661
662 return data;
663 }
664
665 /* Scan the bucket overflow. */
666 for (struct hash_entry *cursor = bucket; cursor->next; cursor = cursor->next)
667 {
668 if (entry == cursor->next->data
669 || table->comparator (entry, cursor->next->data))
670 {
671 void *data = cursor->next->data;
672
673 if (delete)
674 {
675 struct hash_entry *next = cursor->next;
676
677 /* Unlink the entry to delete, then save the freed entry for later
678 recycling. */
679 cursor->next = next->next;
680 free_entry (table, next);
681 }
682
683 return data;
684 }
685 }
686
687 /* No entry found. */
688 return NULL;
689 }
690
691 /* Internal helper, to move entries from SRC to DST. Both tables must
692 share the same free entry list. If SAFE, only move overflow
693 entries, saving bucket heads for later, so that no allocations will
694 occur. Return false (setting errno) if the free entry list is
695 exhausted and an allocation fails. */
696
697 static bool
698 transfer_entries (Hash_table *dst, Hash_table *src, bool safe)
699 {
700 for (struct hash_entry *bucket = src->bucket; bucket < src->bucket_limit; bucket++)
701 if (bucket->data)
702 {
703 void *data;
704 struct hash_entry *new_bucket;
705
706 /* Within each bucket, transfer overflow entries first and
707 then the bucket head, to minimize memory pressure. After
708 all, the only time we might allocate is when moving the
709 bucket head, but moving overflow entries first may create
710 free entries that can be recycled by the time we finally
711 get to the bucket head. */
712 for (struct hash_entry *cursor = bucket->next; cursor; )
713 {
714 data = cursor->data;
715 new_bucket = safe_hasher (dst, data);
716
717 struct hash_entry *next = cursor->next;
718
719 if (new_bucket->data)
720 {
721 /* Merely relink an existing entry, when moving from a
722 bucket overflow into a bucket overflow. */
723 cursor->next = new_bucket->next;
724 new_bucket->next = cursor;
725 }
726 else
727 {
728 /* Free an existing entry, when moving from a bucket
729 overflow into a bucket header. */
730 new_bucket->data = data;
731 dst->n_buckets_used++;
732 free_entry (dst, cursor);
733 }
734
735 cursor = next;
736 }
737 /* Now move the bucket head. Be sure that if we fail due to
738 allocation failure that the src table is in a consistent
739 state. */
740 data = bucket->data;
741 bucket->next = NULL;
742 if (!safe)
743 {
744 new_bucket = safe_hasher (dst, data);
745
746 if (new_bucket->data)
747 {
748 /* Allocate or recycle an entry, when moving from a bucket
749 header into a bucket overflow. */
750 struct hash_entry *new_entry = allocate_entry (dst);
751
752 if (new_entry == NULL)
753 return false;
754
755 new_entry->data = data;
756 new_entry->next = new_bucket->next;
757 new_bucket->next = new_entry;
758 }
759 else
760 {
761 /* Move from one bucket header to another. */
762 new_bucket->data = data;
763 dst->n_buckets_used++;
764 }
765 bucket->data = NULL;
766 src->n_buckets_used--;
767 }
768 }
769 return true;
770 }
771
772 bool
773 hash_rehash (Hash_table *table, size_t candidate)
774 {
775 size_t new_size = compute_bucket_size (candidate, table->tuning);
776
777 if (!new_size)
778 return false;
779 if (new_size == table->n_buckets)
780 return true;
781
782 Hash_table storage;
783 Hash_table *new_table = &storage;
784 new_table->bucket = calloc (new_size, sizeof *new_table->bucket);
785 if (new_table->bucket == NULL)
786 return false;
787 new_table->n_buckets = new_size;
788 new_table->bucket_limit = new_table->bucket + new_size;
789 new_table->n_buckets_used = 0;
790 new_table->n_entries = 0;
791 new_table->tuning = table->tuning;
792 new_table->hasher = table->hasher;
793 new_table->comparator = table->comparator;
794 new_table->data_freer = table->data_freer;
795
796 /* In order for the transfer to successfully complete, we need
797 additional overflow entries when distinct buckets in the old
798 table collide into a common bucket in the new table. The worst
799 case possible is a hasher that gives a good spread with the old
800 size, but returns a constant with the new size; if we were to
801 guarantee table->n_buckets_used-1 free entries in advance, then
802 the transfer would be guaranteed to not allocate memory.
803 However, for large tables, a guarantee of no further allocation
804 introduces a lot of extra memory pressure, all for an unlikely
805 corner case (most rehashes reduce, rather than increase, the
806 number of overflow entries needed). So, we instead ensure that
807 the transfer process can be reversed if we hit a memory
808 allocation failure mid-transfer. */
809
810 /* Merely reuse the extra old space into the new table. */
811 #if USE_OBSTACK
812 new_table->entry_stack = table->entry_stack;
813 #endif
814 new_table->free_entry_list = table->free_entry_list;
815
816 if (transfer_entries (new_table, table, false))
817 {
818 /* Entries transferred successfully; tie up the loose ends. */
819 free (table->bucket);
820 table->bucket = new_table->bucket;
821 table->bucket_limit = new_table->bucket_limit;
822 table->n_buckets = new_table->n_buckets;
823 table->n_buckets_used = new_table->n_buckets_used;
824 table->free_entry_list = new_table->free_entry_list;
825 /* table->n_entries and table->entry_stack already hold their value. */
826 return true;
827 }
828
829 /* We've allocated new_table->bucket (and possibly some entries),
830 exhausted the free list, and moved some but not all entries into
831 new_table. We must undo the partial move before returning
832 failure. The only way to get into this situation is if new_table
833 uses fewer buckets than the old table, so we will reclaim some
834 free entries as overflows in the new table are put back into
835 distinct buckets in the old table.
836
837 There are some pathological cases where a single pass through the
838 table requires more intermediate overflow entries than using two
839 passes. Two passes give worse cache performance and takes
840 longer, but at this point, we're already out of memory, so slow
841 and safe is better than failure. */
842 int saved_errno = errno;
843 table->free_entry_list = new_table->free_entry_list;
844 if (! (transfer_entries (table, new_table, true)
845 && transfer_entries (table, new_table, false)))
846 abort ();
847 /* table->n_entries already holds its value. */
848 free (new_table->bucket);
849 errno = saved_errno;
850 return false;
851 }
852
853 int
854 hash_insert_if_absent (Hash_table *table, void const *entry,
855 void const **matched_ent)
856 {
857
858 /* The caller cannot insert a NULL entry, since hash_lookup returns NULL
859 to indicate "not found", and find_entry uses "bucket->data == NULL"
860 to indicate an empty bucket. */
861 if (! entry)
862 abort ();
863
864 /* If there's a matching entry already in the table, return that. */
865 struct hash_entry *bucket;
866 void *data = find_entry (table, entry, &bucket, false);
867 if (data != NULL)
868 {
869 if (matched_ent)
870 *matched_ent = data;
871 return 0;
872 }
873
874 /* If the growth threshold of the buckets in use has been reached, increase
875 the table size and rehash. There's no point in checking the number of
876 entries: if the hashing function is ill-conditioned, rehashing is not
877 likely to improve it. */
878
879 if (table->n_buckets_used
880 > table->tuning->growth_threshold * table->n_buckets)
881 {
882 /* Check more fully, before starting real work. If tuning arguments
883 became invalid, the second check will rely on proper defaults. */
884 check_tuning (table);
885 if (table->n_buckets_used
886 > table->tuning->growth_threshold * table->n_buckets)
887 {
888 const Hash_tuning *tuning = table->tuning;
889 float candidate =
890 (tuning->is_n_buckets
891 ? (table->n_buckets * tuning->growth_factor)
892 : (table->n_buckets * tuning->growth_factor
893 * tuning->growth_threshold));
894
895 if ((float) SIZE_MAX <= candidate)
896 {
897 errno = ENOMEM;
898 return -1;
899 }
900
901 /* If the rehash fails, arrange to return NULL. */
902 if (!hash_rehash (table, candidate))
903 return -1;
904
905 /* Update the bucket we are interested in. */
906 if (find_entry (table, entry, &bucket, false) != NULL)
907 abort ();
908 }
909 }
910
911 /* ENTRY is not matched, it should be inserted. */
912
913 if (bucket->data)
914 {
915 struct hash_entry *new_entry = allocate_entry (table);
916
917 if (new_entry == NULL)
918 return -1;
919
920 /* Add ENTRY in the overflow of the bucket. */
921
922 new_entry->data = (void *) entry;
923 new_entry->next = bucket->next;
924 bucket->next = new_entry;
925 table->n_entries++;
926 return 1;
927 }
928
929 /* Add ENTRY right in the bucket head. */
930
931 bucket->data = (void *) entry;
932 table->n_entries++;
933 table->n_buckets_used++;
934
935 return 1;
936 }
937
938 void *
939 hash_insert (Hash_table *table, void const *entry)
940 {
941 void const *matched_ent;
942 int err = hash_insert_if_absent (table, entry, &matched_ent);
943 return (err == -1
944 ? NULL
945 : (void *) (err == 0 ? matched_ent : entry));
946 }
947
948 void *
949 hash_remove (Hash_table *table, const void *entry)
950 {
951 struct hash_entry *bucket;
952 void *data = find_entry (table, entry, &bucket, true);
953 if (!data)
954 return NULL;
955
956 table->n_entries--;
957 if (!bucket->data)
958 {
959 table->n_buckets_used--;
960
961 /* If the shrink threshold of the buckets in use has been reached,
962 rehash into a smaller table. */
963
964 if (table->n_buckets_used
965 < table->tuning->shrink_threshold * table->n_buckets)
966 {
967 /* Check more fully, before starting real work. If tuning arguments
968 became invalid, the second check will rely on proper defaults. */
969 check_tuning (table);
970 if (table->n_buckets_used
971 < table->tuning->shrink_threshold * table->n_buckets)
972 {
973 const Hash_tuning *tuning = table->tuning;
974 size_t candidate =
975 (tuning->is_n_buckets
976 ? table->n_buckets * tuning->shrink_factor
977 : (table->n_buckets * tuning->shrink_factor
978 * tuning->growth_threshold));
979
980 if (!hash_rehash (table, candidate))
981 {
982 /* Failure to allocate memory in an attempt to
983 shrink the table is not fatal. But since memory
984 is low, we can at least be kind and free any
985 spare entries, rather than keeping them tied up
986 in the free entry list. */
987 #if ! USE_OBSTACK
988 struct hash_entry *cursor = table->free_entry_list;
989 struct hash_entry *next;
990 while (cursor)
991 {
992 next = cursor->next;
993 free (cursor);
994 cursor = next;
995 }
996 table->free_entry_list = NULL;
997 #endif
998 }
999 }
1000 }
1001 }
1002
1003 return data;
1004 }
1005
1006 /* Testing. */
1007
1008 #if TESTING
1009
1010 void
1011 hash_print (const Hash_table *table)
1012 {
1013 for (struct hash_entry *bucket = (struct hash_entry *) table->bucket;
1014 bucket < table->bucket_limit;
1015 bucket++)
1016 {
1017 if (bucket)
1018 printf ("%lu:\n", (unsigned long int) (bucket - table->bucket));
1019
1020 for (struct hash_entry *cursor = bucket; cursor; cursor = cursor->next)
1021 {
1022 char const *s = cursor->data;
1023 /* FIXME */
1024 if (s)
1025 printf (" %s\n", s);
1026 }
1027 }
1028 }
1029
1030 #endif /* TESTING */