1/* A type-safe hash table template.
2 Copyright (C) 2012-2022 Free Software Foundation, Inc.
3 Contributed by Lawrence Crowl <crowl@google.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21
22/* This file implements a typed hash table.
23 The implementation borrows from libiberty's htab_t in hashtab.h.
24
25
26 INTRODUCTION TO TYPES
27
28 Users of the hash table generally need to be aware of three types.
29
30 1. The type being placed into the hash table. This type is called
31 the value type.
32
33 2. The type used to describe how to handle the value type within
34 the hash table. This descriptor type provides the hash table with
35 several things.
36
37 - A typedef named 'value_type' to the value type (from above).
38 Provided a suitable Descriptor class it may be a user-defined,
39 non-POD type.
40
41 - A static member function named 'hash' that takes a value_type
42 (or 'const value_type &') and returns a hashval_t value.
43
44 - A typedef named 'compare_type' that is used to test when a value
45 is found. This type is the comparison type. Usually, it will be
46 the same as value_type and may be a user-defined, non-POD type.
47 If it is not the same type, you must generally explicitly compute
48 hash values and pass them to the hash table.
49
50 - A static member function named 'equal' that takes a value_type
51 and a compare_type, and returns a bool. Both arguments can be
52 const references.
53
54 - A static function named 'remove' that takes an value_type pointer
55 and frees the memory allocated by it. This function is used when
56 individual elements of the table need to be disposed of (e.g.,
57 when deleting a hash table, removing elements from the table, etc).
58
59 - An optional static function named 'keep_cache_entry'. This
60 function is provided only for garbage-collected elements that
61 are not marked by the normal gc mark pass. It describes what
62 what should happen to the element at the end of the gc mark phase.
63 The return value should be:
64 - 0 if the element should be deleted
65 - 1 if the element should be kept and needs to be marked
66 - -1 if the element should be kept and is already marked.
67 Returning -1 rather than 1 is purely an optimization.
68
69 3. The type of the hash table itself. (More later.)
70
71 In very special circumstances, users may need to know about a fourth type.
72
73 4. The template type used to describe how hash table memory
74 is allocated. This type is called the allocator type. It is
75 parameterized on the value type. It provides two functions:
76
77 - A static member function named 'data_alloc'. This function
78 allocates the data elements in the table.
79
80 - A static member function named 'data_free'. This function
81 deallocates the data elements in the table.
82
83 Hash table are instantiated with two type arguments.
84
85 * The descriptor type, (2) above.
86
87 * The allocator type, (4) above. In general, you will not need to
88 provide your own allocator type. By default, hash tables will use
89 the class template xcallocator, which uses malloc/free for allocation.
90
91
92 DEFINING A DESCRIPTOR TYPE
93
94 The first task in using the hash table is to describe the element type.
95 We compose this into a few steps.
96
97 1. Decide on a removal policy for values stored in the table.
98 hash-traits.h provides class templates for the four most common
99 policies:
100
101 * typed_free_remove implements the static 'remove' member function
102 by calling free().
103
104 * typed_noop_remove implements the static 'remove' member function
105 by doing nothing.
106
107 * ggc_remove implements the static 'remove' member by doing nothing,
108 but instead provides routines for gc marking and for PCH streaming.
109 Use this for garbage-collected data that needs to be preserved across
110 collections.
111
112 * ggc_cache_remove is like ggc_remove, except that it does not
113 mark the entries during the normal gc mark phase. Instead it
114 uses 'keep_cache_entry' (described above) to keep elements that
115 were not collected and delete those that were. Use this for
116 garbage-collected caches that should not in themselves stop
117 the data from being collected.
118
119 You can use these policies by simply deriving the descriptor type
120 from one of those class template, with the appropriate argument.
121
122 Otherwise, you need to write the static 'remove' member function
123 in the descriptor class.
124
125 2. Choose a hash function. Write the static 'hash' member function.
126
127 3. Decide whether the lookup function should take as input an object
128 of type value_type or something more restricted. Define compare_type
129 accordingly.
130
131 4. Choose an equality testing function 'equal' that compares a value_type
132 and a compare_type.
133
134 If your elements are pointers, it is usually easiest to start with one
135 of the generic pointer descriptors described below and override the bits
136 you need to change.
137
138 AN EXAMPLE DESCRIPTOR TYPE
139
140 Suppose you want to put some_type into the hash table. You could define
141 the descriptor type as follows.
142
143 struct some_type_hasher : nofree_ptr_hash <some_type>
144 // Deriving from nofree_ptr_hash means that we get a 'remove' that does
145 // nothing. This choice is good for raw values.
146 {
147 static inline hashval_t hash (const value_type *);
148 static inline bool equal (const value_type *, const compare_type *);
149 };
150
151 inline hashval_t
152 some_type_hasher::hash (const value_type *e)
153 { ... compute and return a hash value for E ... }
154
155 inline bool
156 some_type_hasher::equal (const value_type *p1, const compare_type *p2)
157 { ... compare P1 vs P2. Return true if they are the 'same' ... }
158
159
160 AN EXAMPLE HASH_TABLE DECLARATION
161
162 To instantiate a hash table for some_type:
163
164 hash_table <some_type_hasher> some_type_hash_table;
165
166 There is no need to mention some_type directly, as the hash table will
167 obtain it using some_type_hasher::value_type.
168
169 You can then use any of the functions in hash_table's public interface.
170 See hash_table for details. The interface is very similar to libiberty's
171 htab_t.
172
173 If a hash table is used only in some rare cases, it is possible
174 to construct the hash_table lazily before first use. This is done
175 through:
176
177 hash_table <some_type_hasher, true> some_type_hash_table;
178
179 which will cause whatever methods actually need the allocated entries
180 array to allocate it later.
181
182
183 EASY DESCRIPTORS FOR POINTERS
184
185 There are four descriptors for pointer elements, one for each of
186 the removal policies above:
187
188 * nofree_ptr_hash (based on typed_noop_remove)
189 * free_ptr_hash (based on typed_free_remove)
190 * ggc_ptr_hash (based on ggc_remove)
191 * ggc_cache_ptr_hash (based on ggc_cache_remove)
192
193 These descriptors hash and compare elements by their pointer value,
194 rather than what they point to. So, to instantiate a hash table over
195 pointers to whatever_type, without freeing the whatever_types, use:
196
197 hash_table <nofree_ptr_hash <whatever_type> > whatever_type_hash_table;
198
199
200 HASH TABLE ITERATORS
201
202 The hash table provides standard C++ iterators. For example, consider a
203 hash table of some_info. We wish to consume each element of the table:
204
205 extern void consume (some_info *);
206
207 We define a convenience typedef and the hash table:
208
209 typedef hash_table <some_info_hasher> info_table_type;
210 info_table_type info_table;
211
212 Then we write the loop in typical C++ style:
213
214 for (info_table_type::iterator iter = info_table.begin ();
215 iter != info_table.end ();
216 ++iter)
217 if ((*iter).status == INFO_READY)
218 consume (&*iter);
219
220 Or with common sub-expression elimination:
221
222 for (info_table_type::iterator iter = info_table.begin ();
223 iter != info_table.end ();
224 ++iter)
225 {
226 some_info &elem = *iter;
227 if (elem.status == INFO_READY)
228 consume (&elem);
229 }
230
231 One can also use a more typical GCC style:
232
233 typedef some_info *some_info_p;
234 some_info *elem_ptr;
235 info_table_type::iterator iter;
236 FOR_EACH_HASH_TABLE_ELEMENT (info_table, elem_ptr, some_info_p, iter)
237 if (elem_ptr->status == INFO_READY)
238 consume (elem_ptr);
239
240*/
241
242
243#ifndef TYPED_HASHTAB_H
244#define TYPED_HASHTAB_H
245
246#include "statistics.h"
247#include "ggc.h"
248#include "vec.h"
249#include "hashtab.h"
250#include "inchash.h"
251#include "mem-stats-traits.h"
252#include "hash-traits.h"
253#include "hash-map-traits.h"
254
255template<typename, typename, typename> class hash_map;
256template<typename, bool, typename> class hash_set;
257
258/* The ordinary memory allocator. */
259/* FIXME (crowl): This allocator may be extracted for wider sharing later. */
260
261template <typename Type>
262struct xcallocator
263{
264 static Type *data_alloc (size_t count);
265 static void data_free (Type *memory);
266};
267
268
269/* Allocate memory for COUNT data blocks. */
270
271template <typename Type>
272inline Type *
273xcallocator <Type>::data_alloc (size_t count)
274{
275 return static_cast <Type *> (xcalloc (count, sizeof (Type)));
276}
277
278
279/* Free memory for data blocks. */
280
281template <typename Type>
282inline void
283xcallocator <Type>::data_free (Type *memory)
284{
285 return ::free (memory);
286}
287
288
289/* Table of primes and their inversion information. */
290
291struct prime_ent
292{
293 hashval_t prime;
294 hashval_t inv;
295 hashval_t inv_m2; /* inverse of prime-2 */
296 hashval_t shift;
297};
298
299extern struct prime_ent const prime_tab[];
300
301/* Limit number of comparisons when calling hash_table<>::verify. */
302extern unsigned int hash_table_sanitize_eq_limit;
303
304/* Functions for computing hash table indexes. */
305
306extern unsigned int hash_table_higher_prime_index (unsigned long n)
307 ATTRIBUTE_PURE;
308
309extern ATTRIBUTE_NORETURN ATTRIBUTE_COLD void hashtab_chk_error ();
310
311/* Return X % Y using multiplicative inverse values INV and SHIFT.
312
313 The multiplicative inverses computed above are for 32-bit types,
314 and requires that we be able to compute a highpart multiply.
315
316 FIX: I am not at all convinced that
317 3 loads, 2 multiplications, 3 shifts, and 3 additions
318 will be faster than
319 1 load and 1 modulus
320 on modern systems running a compiler. */
321
322inline hashval_t
323mul_mod (hashval_t x, hashval_t y, hashval_t inv, int shift)
324{
325 hashval_t t1, t2, t3, t4, q, r;
326
327 t1 = ((uint64_t)x * inv) >> 32;
328 t2 = x - t1;
329 t3 = t2 >> 1;
330 t4 = t1 + t3;
331 q = t4 >> shift;
332 r = x - (q * y);
333
334 return r;
335}
336
337/* Compute the primary table index for HASH given current prime index. */
338
339inline hashval_t
340hash_table_mod1 (hashval_t hash, unsigned int index)
341{
342 const struct prime_ent *p = &prime_tab[index];
343 gcc_checking_assert (sizeof (hashval_t) * CHAR_BIT <= 32);
344 return mul_mod (hash, p->prime, p->inv, p->shift);
345}
346
347/* Compute the secondary table index for HASH given current prime index. */
348
349inline hashval_t
350hash_table_mod2 (hashval_t hash, unsigned int index)
351{
352 const struct prime_ent *p = &prime_tab[index];
353 gcc_checking_assert (sizeof (hashval_t) * CHAR_BIT <= 32);
354 return 1 + mul_mod (hash, p->prime - 2, p->inv_m2, p->shift);
355}
356
357class mem_usage;
358
359/* User-facing hash table type.
360
361 The table stores elements of type Descriptor::value_type and uses
362 the static descriptor functions described at the top of the file
363 to hash, compare and remove elements.
364
365 Specify the template Allocator to allocate and free memory.
366 The default is xcallocator.
367
368 Storage is an implementation detail and should not be used outside the
369 hash table code.
370
371*/
372template <typename Descriptor, bool Lazy = false,
373 template<typename Type> class Allocator = xcallocator>
374class hash_table
375{
376 typedef typename Descriptor::value_type value_type;
377 typedef typename Descriptor::compare_type compare_type;
378
379public:
380 explicit hash_table (size_t, bool ggc = false,
381 bool sanitize_eq_and_hash = true,
382 bool gather_mem_stats = GATHER_STATISTICS,
383 mem_alloc_origin origin = HASH_TABLE_ORIGIN
384 CXX_MEM_STAT_INFO);
385 explicit hash_table (const hash_table &, bool ggc = false,
386 bool sanitize_eq_and_hash = true,
387 bool gather_mem_stats = GATHER_STATISTICS,
388 mem_alloc_origin origin = HASH_TABLE_ORIGIN
389 CXX_MEM_STAT_INFO);
390 ~hash_table ();
391
392 /* Create a hash_table in gc memory. */
393 static hash_table *
394 create_ggc (size_t n, bool sanitize_eq_and_hash = true CXX_MEM_STAT_INFO)
395 {
396 hash_table *table = ggc_alloc<hash_table> ();
397 new (table) hash_table (n, true, sanitize_eq_and_hash, GATHER_STATISTICS,
398 HASH_TABLE_ORIGIN PASS_MEM_STAT);
399 return table;
400 }
401
402 /* Current size (in entries) of the hash table. */
403 size_t size () const { return m_size; }
404
405 /* Return the current number of elements in this hash table. */
406 size_t elements () const { return m_n_elements - m_n_deleted; }
407
408 /* Return the current number of elements in this hash table. */
409 size_t elements_with_deleted () const { return m_n_elements; }
410
411 /* This function clears all entries in this hash table. */
412 void empty () { if (elements ()) empty_slow (); }
413
414 /* Return true when there are no elements in this hash table. */
415 bool is_empty () const { return elements () == 0; }
416
417 /* This function clears a specified SLOT in a hash table. It is
418 useful when you've already done the lookup and don't want to do it
419 again. */
420 void clear_slot (value_type *);
421
422 /* This function searches for a hash table entry equal to the given
423 COMPARABLE element starting with the given HASH value. It cannot
424 be used to insert or delete an element. */
425 value_type &find_with_hash (const compare_type &, hashval_t);
426
427 /* Like find_slot_with_hash, but compute the hash value from the element. */
428 value_type &find (const value_type &value)
429 {
430 return find_with_hash (value, Descriptor::hash (value));
431 }
432
433 value_type *find_slot (const value_type &value, insert_option insert)
434 {
435 return find_slot_with_hash (value, Descriptor::hash (value), insert);
436 }
437
438 /* This function searches for a hash table slot containing an entry
439 equal to the given COMPARABLE element and starting with the given
440 HASH. To delete an entry, call this with insert=NO_INSERT, then
441 call clear_slot on the slot returned (possibly after doing some
442 checks). To insert an entry, call this with insert=INSERT, then
443 write the value you want into the returned slot. When inserting an
444 entry, NULL may be returned if memory allocation fails. */
445 value_type *find_slot_with_hash (const compare_type &comparable,
446 hashval_t hash, enum insert_option insert);
447
448 /* This function deletes an element with the given COMPARABLE value
449 from hash table starting with the given HASH. If there is no
450 matching element in the hash table, this function does nothing. */
451 void remove_elt_with_hash (const compare_type &, hashval_t);
452
453 /* Like remove_elt_with_hash, but compute the hash value from the
454 element. */
455 void remove_elt (const value_type &value)
456 {
457 remove_elt_with_hash (value, Descriptor::hash (value));
458 }
459
460 /* This function scans over the entire hash table calling CALLBACK for
461 each live entry. If CALLBACK returns false, the iteration stops.
462 ARGUMENT is passed as CALLBACK's second argument. */
463 template <typename Argument,
464 int (*Callback) (value_type *slot, Argument argument)>
465 void traverse_noresize (Argument argument);
466
467 /* Like traverse_noresize, but does resize the table when it is too empty
468 to improve effectivity of subsequent calls. */
469 template <typename Argument,
470 int (*Callback) (value_type *slot, Argument argument)>
471 void traverse (Argument argument);
472
473 class iterator
474 {
475 public:
476 iterator () : m_slot (NULL), m_limit (NULL) {}
477
478 iterator (value_type *slot, value_type *limit) :
479 m_slot (slot), m_limit (limit) {}
480
481 inline value_type &operator * () { return *m_slot; }
482 void slide ();
483 inline iterator &operator ++ ();
484 bool operator != (const iterator &other) const
485 {
486 return m_slot != other.m_slot || m_limit != other.m_limit;
487 }
488
489 private:
490 value_type *m_slot;
491 value_type *m_limit;
492 };
493
494 iterator begin () const
495 {
496 if (Lazy && m_entries == NULL)
497 return iterator ();
498 iterator iter (m_entries, m_entries + m_size);
499 iter.slide ();
500 return iter;
501 }
502
503 iterator end () const { return iterator (); }
504
505 double collisions () const
506 {
507 return m_searches ? static_cast <double> (m_collisions) / m_searches : 0;
508 }
509
510private:
511 /* FIXME: Make the class assignable. See pr90959. */
512 void operator= (hash_table&);
513
514 template<typename T> friend void gt_ggc_mx (hash_table<T> *);
515 template<typename T> friend void gt_pch_nx (hash_table<T> *);
516 template<typename T> friend void
517 hashtab_entry_note_pointers (void *, void *, gt_pointer_operator, void *);
518 template<typename T, typename U, typename V> friend void
519 gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
520 template<typename T, typename U>
521 friend void gt_pch_nx (hash_set<T, false, U> *, gt_pointer_operator, void *);
522 template<typename T> friend void gt_pch_nx (hash_table<T> *,
523 gt_pointer_operator, void *);
524
525 template<typename T> friend void gt_cleare_cache (hash_table<T> *);
526
527 void empty_slow ();
528
529 value_type *alloc_entries (size_t n CXX_MEM_STAT_INFO) const;
530 value_type *find_empty_slot_for_expand (hashval_t);
531 void verify (const compare_type &comparable, hashval_t hash);
532 bool too_empty_p (unsigned int);
533 void expand ();
534 static bool is_deleted (value_type &v)
535 {
536 return Descriptor::is_deleted (v);
537 }
538
539 static bool is_empty (value_type &v)
540 {
541 return Descriptor::is_empty (v);
542 }
543
544 static void mark_deleted (value_type &v)
545 {
546 Descriptor::mark_deleted (v);
547 }
548
549 static void mark_empty (value_type &v)
550 {
551 Descriptor::mark_empty (v);
552 }
553
554 /* Table itself. */
555 typename Descriptor::value_type *m_entries;
556
557 size_t m_size;
558
559 /* Current number of elements including also deleted elements. */
560 size_t m_n_elements;
561
562 /* Current number of deleted elements in the table. */
563 size_t m_n_deleted;
564
565 /* The following member is used for debugging. Its value is number
566 of all calls of `htab_find_slot' for the hash table. */
567 unsigned int m_searches;
568
569 /* The following member is used for debugging. Its value is number
570 of collisions fixed for time of work with the hash table. */
571 unsigned int m_collisions;
572
573 /* Current size (in entries) of the hash table, as an index into the
574 table of primes. */
575 unsigned int m_size_prime_index;
576
577 /* if m_entries is stored in ggc memory. */
578 bool m_ggc;
579
580 /* True if the table should be sanitized for equal and hash functions. */
581 bool m_sanitize_eq_and_hash;
582
583 /* If we should gather memory statistics for the table. */
584#if GATHER_STATISTICS
585 bool m_gather_mem_stats;
586#else
587 static const bool m_gather_mem_stats = false;
588#endif
589};
590
591/* As mem-stats.h heavily utilizes hash maps (hash tables), we have to include
592 mem-stats.h after hash_table declaration. */
593
594#include "mem-stats.h"
595#include "hash-map.h"
596
597extern mem_alloc_description<mem_usage>& hash_table_usage (void);
598
599/* Support function for statistics. */
600extern void dump_hash_table_loc_statistics (void);
601
602template<typename Descriptor, bool Lazy,
603 template<typename Type> class Allocator>
604hash_table<Descriptor, Lazy, Allocator>::hash_table (size_t size, bool ggc,
605 bool sanitize_eq_and_hash,
606 bool gather_mem_stats
607 ATTRIBUTE_UNUSED,
608 mem_alloc_origin origin
609 MEM_STAT_DECL) :
610 m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0),
611 m_ggc (ggc), m_sanitize_eq_and_hash (sanitize_eq_and_hash)
612#if GATHER_STATISTICS
613 , m_gather_mem_stats (gather_mem_stats)
614#endif
615{
616 unsigned int size_prime_index;
617
618 size_prime_index = hash_table_higher_prime_index (size);
619 size = prime_tab[size_prime_index].prime;
620
621 if (m_gather_mem_stats)
622 hash_table_usage ().register_descriptor (this, origin, ggc
623 FINAL_PASS_MEM_STAT);
624
625 if (Lazy)
626 m_entries = NULL;
627 else
628 m_entries = alloc_entries (size PASS_MEM_STAT);
629 m_size = size;
630 m_size_prime_index = size_prime_index;
631}
632
633template<typename Descriptor, bool Lazy,
634 template<typename Type> class Allocator>
635hash_table<Descriptor, Lazy, Allocator>::hash_table (const hash_table &h,
636 bool ggc,
637 bool sanitize_eq_and_hash,
638 bool gather_mem_stats
639 ATTRIBUTE_UNUSED,
640 mem_alloc_origin origin
641 MEM_STAT_DECL) :
642 m_n_elements (h.m_n_elements), m_n_deleted (h.m_n_deleted),
643 m_searches (0), m_collisions (0), m_ggc (ggc),
644 m_sanitize_eq_and_hash (sanitize_eq_and_hash)
645#if GATHER_STATISTICS
646 , m_gather_mem_stats (gather_mem_stats)
647#endif
648{
649 size_t size = h.m_size;
650
651 if (m_gather_mem_stats)
652 hash_table_usage ().register_descriptor (this, origin, ggc
653 FINAL_PASS_MEM_STAT);
654
655 if (Lazy && h.m_entries == NULL)
656 m_entries = NULL;
657 else
658 {
659 value_type *nentries = alloc_entries (size PASS_MEM_STAT);
660 for (size_t i = 0; i < size; ++i)
661 {
662 value_type &entry = h.m_entries[i];
663 if (is_deleted (entry))
664 mark_deleted (nentries[i]);
665 else if (!is_empty (entry))
666 new ((void*) (nentries + i)) value_type (entry);
667 }
668 m_entries = nentries;
669 }
670 m_size = size;
671 m_size_prime_index = h.m_size_prime_index;
672}
673
674template<typename Descriptor, bool Lazy,
675 template<typename Type> class Allocator>
676hash_table<Descriptor, Lazy, Allocator>::~hash_table ()
677{
678 if (!Lazy || m_entries)
679 {
680 for (size_t i = m_size - 1; i < m_size; i--)
681 if (!is_empty (m_entries[i]) && !is_deleted (m_entries[i]))
682 Descriptor::remove (m_entries[i]);
683
684 if (!m_ggc)
685 Allocator <value_type> ::data_free (m_entries);
686 else
687 ggc_free (m_entries);
688 if (m_gather_mem_stats)
689 hash_table_usage ().release_instance_overhead (this,
690 sizeof (value_type)
691 * m_size, true);
692 }
693 else if (m_gather_mem_stats)
694 hash_table_usage ().unregister_descriptor (this);
695}
696
697/* This function returns an array of empty hash table elements. */
698
699template<typename Descriptor, bool Lazy,
700 template<typename Type> class Allocator>
701inline typename hash_table<Descriptor, Lazy, Allocator>::value_type *
702hash_table<Descriptor, Lazy,
703 Allocator>::alloc_entries (size_t n MEM_STAT_DECL) const
704{
705 value_type *nentries;
706
707 if (m_gather_mem_stats)
708 hash_table_usage ().register_instance_overhead (sizeof (value_type) * n, this);
709
710 if (!m_ggc)
711 nentries = Allocator <value_type> ::data_alloc (n);
712 else
713 nentries = ::ggc_cleared_vec_alloc<value_type> (n PASS_MEM_STAT);
714
715 gcc_assert (nentries != NULL);
716 if (!Descriptor::empty_zero_p)
717 for (size_t i = 0; i < n; i++)
718 mark_empty (nentries[i]);
719
720 return nentries;
721}
722
723/* Similar to find_slot, but without several unwanted side effects:
724 - Does not call equal when it finds an existing entry.
725 - Does not change the count of elements/searches/collisions in the
726 hash table.
727 This function also assumes there are no deleted entries in the table.
728 HASH is the hash value for the element to be inserted. */
729
730template<typename Descriptor, bool Lazy,
731 template<typename Type> class Allocator>
732typename hash_table<Descriptor, Lazy, Allocator>::value_type *
733hash_table<Descriptor, Lazy,
734 Allocator>::find_empty_slot_for_expand (hashval_t hash)
735{
736 hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
737 size_t size = m_size;
738 value_type *slot = m_entries + index;
739 hashval_t hash2;
740
741 if (is_empty (*slot))
742 return slot;
743 gcc_checking_assert (!is_deleted (*slot));
744
745 hash2 = hash_table_mod2 (hash, m_size_prime_index);
746 for (;;)
747 {
748 index += hash2;
749 if (index >= size)
750 index -= size;
751
752 slot = m_entries + index;
753 if (is_empty (*slot))
754 return slot;
755 gcc_checking_assert (!is_deleted (*slot));
756 }
757}
758
759/* Return true if the current table is excessively big for ELTS elements. */
760
761template<typename Descriptor, bool Lazy,
762 template<typename Type> class Allocator>
763inline bool
764hash_table<Descriptor, Lazy, Allocator>::too_empty_p (unsigned int elts)
765{
766 return elts * 8 < m_size && m_size > 32;
767}
768
769/* The following function changes size of memory allocated for the
770 entries and repeatedly inserts the table elements. The occupancy
771 of the table after the call will be about 50%. Naturally the hash
772 table must already exist. Remember also that the place of the
773 table entries is changed. If memory allocation fails, this function
774 will abort. */
775
776template<typename Descriptor, bool Lazy,
777 template<typename Type> class Allocator>
778void
779hash_table<Descriptor, Lazy, Allocator>::expand ()
780{
781 value_type *oentries = m_entries;
782 unsigned int oindex = m_size_prime_index;
783 size_t osize = size ();
784 value_type *olimit = oentries + osize;
785 size_t elts = elements ();
786
787 /* Resize only when table after removal of unused elements is either
788 too full or too empty. */
789 unsigned int nindex;
790 size_t nsize;
791 if (elts * 2 > osize || too_empty_p (elts))
792 {
793 nindex = hash_table_higher_prime_index (elts * 2);
794 nsize = prime_tab[nindex].prime;
795 }
796 else
797 {
798 nindex = oindex;
799 nsize = osize;
800 }
801
802 value_type *nentries = alloc_entries (nsize);
803
804 if (m_gather_mem_stats)
805 hash_table_usage ().release_instance_overhead (this, sizeof (value_type)
806 * osize);
807
808 m_entries = nentries;
809 m_size = nsize;
810 m_size_prime_index = nindex;
811 m_n_elements -= m_n_deleted;
812 m_n_deleted = 0;
813
814 value_type *p = oentries;
815 do
816 {
817 value_type &x = *p;
818
819 if (!is_empty (x) && !is_deleted (x))
820 {
821 value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
822 new ((void*) q) value_type (std::move (x));
823 /* After the resources of 'x' have been moved to a new object at 'q',
824 we now have to destroy the 'x' object, to end its lifetime. */
825 x.~value_type ();
826 }
827
828 p++;
829 }
830 while (p < olimit);
831
832 if (!m_ggc)
833 Allocator <value_type> ::data_free (oentries);
834 else
835 ggc_free (oentries);
836}
837
838/* Implements empty() in cases where it isn't a no-op. */
839
840template<typename Descriptor, bool Lazy,
841 template<typename Type> class Allocator>
842void
843hash_table<Descriptor, Lazy, Allocator>::empty_slow ()
844{
845 size_t size = m_size;
846 size_t nsize = size;
847 value_type *entries = m_entries;
848
849 for (size_t i = size - 1; i < size; i--)
850 if (!is_empty (entries[i]) && !is_deleted (entries[i]))
851 Descriptor::remove (entries[i]);
852
853 /* Instead of clearing megabyte, downsize the table. */
854 if (size > 1024*1024 / sizeof (value_type))
855 nsize = 1024 / sizeof (value_type);
856 else if (too_empty_p (m_n_elements))
857 nsize = m_n_elements * 2;
858
859 if (nsize != size)
860 {
861 unsigned int nindex = hash_table_higher_prime_index (nsize);
862
863 nsize = prime_tab[nindex].prime;
864
865 if (!m_ggc)
866 Allocator <value_type> ::data_free (m_entries);
867 else
868 ggc_free (m_entries);
869
870 m_entries = alloc_entries (nsize);
871 m_size = nsize;
872 m_size_prime_index = nindex;
873 }
874 else if (Descriptor::empty_zero_p)
875 memset ((void *) entries, 0, size * sizeof (value_type));
876 else
877 for (size_t i = 0; i < size; i++)
878 mark_empty (entries[i]);
879
880 m_n_deleted = 0;
881 m_n_elements = 0;
882}
883
884/* This function clears a specified SLOT in a hash table. It is
885 useful when you've already done the lookup and don't want to do it
886 again. */
887
888template<typename Descriptor, bool Lazy,
889 template<typename Type> class Allocator>
890void
891hash_table<Descriptor, Lazy, Allocator>::clear_slot (value_type *slot)
892{
893 gcc_checking_assert (!(slot < m_entries || slot >= m_entries + size ()
894 || is_empty (*slot) || is_deleted (*slot)));
895
896 Descriptor::remove (*slot);
897
898 mark_deleted (*slot);
899 m_n_deleted++;
900}
901
902/* This function searches for a hash table entry equal to the given
903 COMPARABLE element starting with the given HASH value. It cannot
904 be used to insert or delete an element. */
905
906template<typename Descriptor, bool Lazy,
907 template<typename Type> class Allocator>
908typename hash_table<Descriptor, Lazy, Allocator>::value_type &
909hash_table<Descriptor, Lazy, Allocator>
910::find_with_hash (const compare_type &comparable, hashval_t hash)
911{
912 m_searches++;
913 size_t size = m_size;
914 hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
915
916 if (Lazy && m_entries == NULL)
917 m_entries = alloc_entries (size);
918
919#if CHECKING_P
920 if (m_sanitize_eq_and_hash)
921 verify (comparable, hash);
922#endif
923
924 value_type *entry = &m_entries[index];
925 if (is_empty (*entry)
926 || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
927 return *entry;
928
929 hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
930 for (;;)
931 {
932 m_collisions++;
933 index += hash2;
934 if (index >= size)
935 index -= size;
936
937 entry = &m_entries[index];
938 if (is_empty (*entry)
939 || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
940 return *entry;
941 }
942}
943
944/* This function searches for a hash table slot containing an entry
945 equal to the given COMPARABLE element and starting with the given
946 HASH. To delete an entry, call this with insert=NO_INSERT, then
947 call clear_slot on the slot returned (possibly after doing some
948 checks). To insert an entry, call this with insert=INSERT, then
949 write the value you want into the returned slot. When inserting an
950 entry, NULL may be returned if memory allocation fails. */
951
952template<typename Descriptor, bool Lazy,
953 template<typename Type> class Allocator>
954typename hash_table<Descriptor, Lazy, Allocator>::value_type *
955hash_table<Descriptor, Lazy, Allocator>
956::find_slot_with_hash (const compare_type &comparable, hashval_t hash,
957 enum insert_option insert)
958{
959 if (Lazy && m_entries == NULL)
960 {
961 if (insert == INSERT)
962 m_entries = alloc_entries (m_size);
963 else
964 return NULL;
965 }
966 if (insert == INSERT && m_size * 3 <= m_n_elements * 4)
967 expand ();
968
969#if CHECKING_P
970 if (m_sanitize_eq_and_hash)
971 verify (comparable, hash);
972#endif
973
974 m_searches++;
975 value_type *first_deleted_slot = NULL;
976 hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
977 hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
978 value_type *entry = &m_entries[index];
979 size_t size = m_size;
980 if (is_empty (*entry))
981 goto empty_entry;
982 else if (is_deleted (*entry))
983 first_deleted_slot = &m_entries[index];
984 else if (Descriptor::equal (*entry, comparable))
985 return &m_entries[index];
986
987 for (;;)
988 {
989 m_collisions++;
990 index += hash2;
991 if (index >= size)
992 index -= size;
993
994 entry = &m_entries[index];
995 if (is_empty (*entry))
996 goto empty_entry;
997 else if (is_deleted (*entry))
998 {
999 if (!first_deleted_slot)
1000 first_deleted_slot = &m_entries[index];
1001 }
1002 else if (Descriptor::equal (*entry, comparable))
1003 return &m_entries[index];
1004 }
1005
1006 empty_entry:
1007 if (insert == NO_INSERT)
1008 return NULL;
1009
1010 if (first_deleted_slot)
1011 {
1012 m_n_deleted--;
1013 mark_empty (*first_deleted_slot);
1014 return first_deleted_slot;
1015 }
1016
1017 m_n_elements++;
1018 return &m_entries[index];
1019}
1020
1021/* Verify that all existing elements in th hash table which are
1022 equal to COMPARABLE have an equal HASH value provided as argument. */
1023
1024template<typename Descriptor, bool Lazy,
1025 template<typename Type> class Allocator>
1026void
1027hash_table<Descriptor, Lazy, Allocator>
1028::verify (const compare_type &comparable, hashval_t hash)
1029{
1030 for (size_t i = 0; i < MIN (hash_table_sanitize_eq_limit, m_size); i++)
1031 {
1032 value_type *entry = &m_entries[i];
1033 if (!is_empty (*entry) && !is_deleted (*entry)
1034 && hash != Descriptor::hash (*entry)
1035 && Descriptor::equal (*entry, comparable))
1036 hashtab_chk_error ();
1037 }
1038}
1039
1040/* This function deletes an element with the given COMPARABLE value
1041 from hash table starting with the given HASH. If there is no
1042 matching element in the hash table, this function does nothing. */
1043
1044template<typename Descriptor, bool Lazy,
1045 template<typename Type> class Allocator>
1046void
1047hash_table<Descriptor, Lazy, Allocator>
1048::remove_elt_with_hash (const compare_type &comparable, hashval_t hash)
1049{
1050 value_type *slot = find_slot_with_hash (comparable, hash, NO_INSERT);
1051 if (slot == NULL)
1052 return;
1053
1054 Descriptor::remove (*slot);
1055
1056 mark_deleted (*slot);
1057 m_n_deleted++;
1058}
1059
1060/* This function scans over the entire hash table calling CALLBACK for
1061 each live entry. If CALLBACK returns false, the iteration stops.
1062 ARGUMENT is passed as CALLBACK's second argument. */
1063
1064template<typename Descriptor, bool Lazy,
1065 template<typename Type> class Allocator>
1066template<typename Argument,
1067 int (*Callback)
1068 (typename hash_table<Descriptor, Lazy, Allocator>::value_type *slot,
1069 Argument argument)>
1070void
1071hash_table<Descriptor, Lazy, Allocator>::traverse_noresize (Argument argument)
1072{
1073 if (Lazy && m_entries == NULL)
1074 return;
1075
1076 value_type *slot = m_entries;
1077 value_type *limit = slot + size ();
1078
1079 do
1080 {
1081 value_type &x = *slot;
1082
1083 if (!is_empty (x) && !is_deleted (x))
1084 if (! Callback (slot, argument))
1085 break;
1086 }
1087 while (++slot < limit);
1088}
1089
1090/* Like traverse_noresize, but does resize the table when it is too empty
1091 to improve effectivity of subsequent calls. */
1092
1093template <typename Descriptor, bool Lazy,
1094 template <typename Type> class Allocator>
1095template <typename Argument,
1096 int (*Callback)
1097 (typename hash_table<Descriptor, Lazy, Allocator>::value_type *slot,
1098 Argument argument)>
1099void
1100hash_table<Descriptor, Lazy, Allocator>::traverse (Argument argument)
1101{
1102 if (too_empty_p (elements ()) && (!Lazy || m_entries))
1103 expand ();
1104
1105 traverse_noresize <Argument, Callback> (argument);
1106}
1107
1108/* Slide down the iterator slots until an active entry is found. */
1109
1110template<typename Descriptor, bool Lazy,
1111 template<typename Type> class Allocator>
1112void
1113hash_table<Descriptor, Lazy, Allocator>::iterator::slide ()
1114{
1115 for ( ; m_slot < m_limit; ++m_slot )
1116 {
1117 value_type &x = *m_slot;
1118 if (!is_empty (x) && !is_deleted (x))
1119 return;
1120 }
1121 m_slot = NULL;
1122 m_limit = NULL;
1123}
1124
1125/* Bump the iterator. */
1126
1127template<typename Descriptor, bool Lazy,
1128 template<typename Type> class Allocator>
1129inline typename hash_table<Descriptor, Lazy, Allocator>::iterator &
1130hash_table<Descriptor, Lazy, Allocator>::iterator::operator ++ ()
1131{
1132 ++m_slot;
1133 slide ();
1134 return *this;
1135}
1136
1137
1138/* Iterate through the elements of hash_table HTAB,
1139 using hash_table <....>::iterator ITER,
1140 storing each element in RESULT, which is of type TYPE. */
1141
1142#define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \
1143 for ((ITER) = (HTAB).begin (); \
1144 (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \
1145 ++(ITER))
1146
1147/* ggc walking routines. */
1148
1149template<typename E>
1150static inline void
1151gt_ggc_mx (hash_table<E> *h)
1152{
1153 typedef hash_table<E> table;
1154
1155 if (!ggc_test_and_set_mark (h->m_entries))
1156 return;
1157
1158 for (size_t i = 0; i < h->m_size; i++)
1159 {
1160 if (table::is_empty (h->m_entries[i])
1161 || table::is_deleted (h->m_entries[i]))
1162 continue;
1163
1164 /* Use ggc_maxbe_mx so we don't mark right away for cache tables; we'll
1165 mark in gt_cleare_cache if appropriate. */
1166 E::ggc_maybe_mx (h->m_entries[i]);
1167 }
1168}
1169
1170template<typename D>
1171static inline void
1172hashtab_entry_note_pointers (void *obj, void *h, gt_pointer_operator op,
1173 void *cookie)
1174{
1175 hash_table<D> *map = static_cast<hash_table<D> *> (h);
1176 gcc_checking_assert (map->m_entries == obj);
1177 for (size_t i = 0; i < map->m_size; i++)
1178 {
1179 typedef hash_table<D> table;
1180 if (table::is_empty (map->m_entries[i])
1181 || table::is_deleted (map->m_entries[i]))
1182 continue;
1183
1184 D::pch_nx (map->m_entries[i], op, cookie);
1185 }
1186}
1187
1188template<typename D>
1189static void
1190gt_pch_nx (hash_table<D> *h)
1191{
1192 bool success
1193 = gt_pch_note_object (h->m_entries, h, hashtab_entry_note_pointers<D>);
1194 gcc_checking_assert (success);
1195 for (size_t i = 0; i < h->m_size; i++)
1196 {
1197 if (hash_table<D>::is_empty (h->m_entries[i])
1198 || hash_table<D>::is_deleted (h->m_entries[i]))
1199 continue;
1200
1201 D::pch_nx (h->m_entries[i]);
1202 }
1203}
1204
1205template<typename D>
1206static inline void
1207gt_pch_nx (hash_table<D> *h, gt_pointer_operator op, void *cookie)
1208{
1209 op (&h->m_entries, NULL, cookie);
1210}
1211
1212template<typename H>
1213inline void
1214gt_cleare_cache (hash_table<H> *h)
1215{
1216 typedef hash_table<H> table;
1217 if (!h)
1218 return;
1219
1220 for (typename table::iterator iter = h->begin (); iter != h->end (); ++iter)
1221 if (!table::is_empty (*iter) && !table::is_deleted (*iter))
1222 {
1223 int res = H::keep_cache_entry (*iter);
1224 if (res == 0)
1225 h->clear_slot (&*iter);
1226 else if (res != -1)
1227 H::ggc_mx (*iter);
1228 }
1229}
1230
1231#endif /* TYPED_HASHTAB_H */
1232

source code of gcc/hash-table.h