Line data Source code
1 : /* A type-safe hash table template.
2 : Copyright (C) 2012-2026 Free Software Foundation, Inc.
3 : Contributed by Lawrence Crowl <crowl@google.com>
4 :
5 : This file is part of GCC.
6 :
7 : GCC is free software; you can redistribute it and/or modify it under
8 : the terms of the GNU General Public License as published by the Free
9 : Software Foundation; either version 3, or (at your option) any later
10 : version.
11 :
12 : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 : WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 : for more details.
16 :
17 : You should have received a copy of the GNU General Public License
18 : along 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 :
255 : template<typename, typename, typename> class hash_map;
256 : template<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 :
261 : template <typename Type>
262 : struct 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 :
271 : template <typename Type>
272 : inline Type *
273 10454635328 : xcallocator <Type>::data_alloc (size_t count)
274 : {
275 10454635328 : return static_cast <Type *> (xcalloc (count, sizeof (Type)));
276 : }
277 :
278 :
279 : /* Free memory for data blocks. */
280 :
281 : template <typename Type>
282 : inline void
283 10452524144 : xcallocator <Type>::data_free (Type *memory)
284 : {
285 10452524144 : return ::free (memory);
286 : }
287 :
288 :
289 : /* Table of primes and their inversion information. */
290 :
291 : struct 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 :
299 : extern struct prime_ent const prime_tab[];
300 :
301 : /* Limit number of comparisons when calling hash_table<>::verify. */
302 : extern unsigned int hash_table_sanitize_eq_limit;
303 :
304 : /* Functions for computing hash table indexes. */
305 :
306 : extern unsigned int hash_table_higher_prime_index (unsigned long n)
307 : ATTRIBUTE_PURE;
308 :
309 : extern 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 :
322 : inline hashval_t
323 >27596*10^7 : mul_mod (hashval_t x, hashval_t y, hashval_t inv, int shift)
324 : {
325 >27596*10^7 : hashval_t t1, t2, t3, t4, q, r;
326 :
327 >27596*10^7 : t1 = ((uint64_t)x * inv) >> 32;
328 >27596*10^7 : t2 = x - t1;
329 >27596*10^7 : t3 = t2 >> 1;
330 >27596*10^7 : t4 = t1 + t3;
331 >27596*10^7 : q = t4 >> shift;
332 >27596*10^7 : r = x - (q * y);
333 :
334 >27596*10^7 : return r;
335 : }
336 :
337 : /* Compute the primary table index for HASH given current prime index. */
338 :
339 : inline hashval_t
340 >17174*10^7 : hash_table_mod1 (hashval_t hash, unsigned int index)
341 : {
342 >17174*10^7 : const struct prime_ent *p = &prime_tab[index];
343 >17174*10^7 : gcc_checking_assert (sizeof (hashval_t) * CHAR_BIT <= 32);
344 >17174*10^7 : 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 :
349 : inline hashval_t
350 >10422*10^7 : hash_table_mod2 (hashval_t hash, unsigned int index)
351 : {
352 >10422*10^7 : const struct prime_ent *p = &prime_tab[index];
353 >10422*10^7 : gcc_checking_assert (sizeof (hashval_t) * CHAR_BIT <= 32);
354 >10422*10^7 : return 1 + mul_mod (hash, p->prime - 2, p->inv_m2, p->shift);
355 : }
356 :
357 : class 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 : */
372 : template <typename Descriptor, bool Lazy = false,
373 : template<typename Type> class Allocator = xcallocator>
374 : class hash_table
375 : {
376 : typedef typename Descriptor::value_type value_type;
377 : typedef typename Descriptor::compare_type compare_type;
378 :
379 : public:
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 50240006 : create_ggc (size_t n, bool sanitize_eq_and_hash = true CXX_MEM_STAT_INFO)
395 : {
396 50240006 : hash_table *table = ggc_alloc<hash_table> ();
397 50240006 : new (table) hash_table (n, true, sanitize_eq_and_hash, GATHER_STATISTICS,
398 : HASH_TABLE_ORIGIN PASS_MEM_STAT);
399 50240006 : return table;
400 : }
401 :
402 : /* Current size (in entries) of the hash table. */
403 1420660275 : size_t size () const { return m_size; }
404 :
405 : /* Return the current number of elements in this hash table. */
406 2354103046 : 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 1060305497 : void empty () { if (elements ()) empty_slow (); }
413 :
414 : /* Return true when there are no elements in this hash table. */
415 141802140 : 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 2062732558 : value_type &find (const value_type &value)
429 : {
430 2062732558 : return find_with_hash (value, Descriptor::hash (value));
431 : }
432 :
433 3093495003 : value_type *find_slot (const value_type &value, insert_option insert)
434 : {
435 3095601182 : 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 613705 : void remove_elt (const value_type &value)
456 : {
457 613705 : remove_elt_with_hash (value, Descriptor::hash (value));
458 610976 : }
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 3870989400 : iterator () : m_slot (NULL), m_limit (NULL) {}
477 :
478 297446066 : iterator (value_type *slot, value_type *limit) :
479 297446066 : m_slot (slot), m_limit (limit) {}
480 :
481 7821126 : inline value_type &operator * () { return *m_slot; }
482 : void slide ();
483 : inline iterator &operator ++ ();
484 6173874375 : bool operator != (const iterator &other) const
485 : {
486 1521284050 : 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 297446070 : iterator begin () const
495 : {
496 8 : if (Lazy && m_entries == NULL)
497 4 : return iterator ();
498 297446066 : check_complete_insertion ();
499 297446066 : iterator iter (m_entries, m_entries + m_size);
500 297446066 : iter.slide ();
501 297446066 : return iter;
502 : }
503 :
504 2767107179 : iterator end () const { return iterator (); }
505 :
506 287 : double collisions () const
507 : {
508 287 : return m_searches ? static_cast <double> (m_collisions) / m_searches : 0;
509 : }
510 :
511 : private:
512 : /* FIXME: Make the class assignable. See pr90959. */
513 : void operator= (hash_table&);
514 :
515 : template<typename T> friend void gt_ggc_mx (hash_table<T> *);
516 : template<typename T> friend void gt_pch_nx (hash_table<T> *);
517 : template<typename T> friend void
518 : hashtab_entry_note_pointers (void *, void *, gt_pointer_operator, void *);
519 : template<typename T, typename U, typename V> friend void
520 : gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
521 : template<typename T, typename U>
522 : friend void gt_pch_nx (hash_set<T, false, U> *, gt_pointer_operator, void *);
523 : template<typename T> friend void gt_pch_nx (hash_table<T> *,
524 : gt_pointer_operator, void *);
525 :
526 : template<typename T> friend void gt_cleare_cache (hash_table<T> *);
527 :
528 : void empty_slow ();
529 :
530 : value_type *alloc_entries (size_t n CXX_MEM_STAT_INFO) const;
531 : value_type *find_empty_slot_for_expand (hashval_t);
532 : void verify (const compare_type &comparable, hashval_t hash);
533 : bool too_empty_p (unsigned int);
534 : void expand ();
535 >77942*10^7 : static bool is_deleted (value_type &v)
536 : {
537 : /* Traits are supposed to avoid recognizing elements as both empty
538 : and deleted, but to fail safe in case custom traits fail to do
539 : that, make sure we never test for is_deleted without having
540 : first ruled out is_empty. */
541 >77942*10^7 : gcc_checking_assert (!Descriptor::is_empty (v));
542 >77942*10^7 : return Descriptor::is_deleted (v);
543 : }
544 :
545 >19633*10^8 : static bool is_empty (value_type &v)
546 : {
547 >11953*10^7 : return Descriptor::is_empty (v);
548 : }
549 :
550 773983179 : static void mark_deleted (value_type &v)
551 : {
552 772089252 : Descriptor::mark_deleted (v);
553 : /* Traits are supposed to refuse to set elements as deleted if
554 : those would be indistinguishable from empty, but to fail safe
555 : in case custom traits fail to do that, check that the
556 : just-deleted element does not look empty. */
557 0 : gcc_checking_assert (!Descriptor::is_empty (v));
558 6330 : }
559 :
560 2019194736 : static void mark_empty (value_type &v)
561 : {
562 2019194736 : Descriptor::mark_empty (v);
563 : }
564 :
565 : public:
566 >14877*10^7 : void check_complete_insertion () const
567 : {
568 : #if CHECKING_P
569 >14877*10^7 : if (!m_inserting_slot)
570 : return;
571 :
572 53205452638 : gcc_checking_assert (m_inserting_slot >= &m_entries[0]
573 : && m_inserting_slot < &m_entries[m_size]);
574 :
575 53205452638 : if (!is_empty (*m_inserting_slot))
576 53205452638 : m_inserting_slot = NULL;
577 : else
578 0 : gcc_unreachable ();
579 : #endif
580 : }
581 :
582 : private:
583 52513195814 : value_type *check_insert_slot (value_type *ret)
584 : {
585 : #if CHECKING_P
586 8272442686 : gcc_checking_assert (is_empty (*ret));
587 53220753611 : m_inserting_slot = ret;
588 : #endif
589 74793 : return ret;
590 : }
591 :
592 : #if CHECKING_P
593 : mutable value_type *m_inserting_slot;
594 : #endif
595 :
596 : /* Table itself. */
597 : value_type *m_entries;
598 :
599 : size_t m_size;
600 :
601 : /* Current number of elements including also deleted elements. */
602 : size_t m_n_elements;
603 :
604 : /* Current number of deleted elements in the table. */
605 : size_t m_n_deleted;
606 :
607 : /* The following member is used for debugging. Its value is number
608 : of all calls of `htab_find_slot' for the hash table. */
609 : unsigned int m_searches;
610 :
611 : /* The following member is used for debugging. Its value is number
612 : of collisions fixed for time of work with the hash table. */
613 : unsigned int m_collisions;
614 :
615 : /* Current size (in entries) of the hash table, as an index into the
616 : table of primes. */
617 : unsigned int m_size_prime_index;
618 :
619 : /* if m_entries is stored in ggc memory. */
620 : bool m_ggc;
621 :
622 : /* True if the table should be sanitized for equal and hash functions. */
623 : bool m_sanitize_eq_and_hash;
624 :
625 : /* If we should gather memory statistics for the table. */
626 : #if GATHER_STATISTICS
627 : bool m_gather_mem_stats;
628 : #else
629 : static const bool m_gather_mem_stats = false;
630 : #endif
631 : };
632 :
633 : /* As mem-stats.h heavily utilizes hash maps (hash tables), we have to include
634 : mem-stats.h after hash_table declaration. */
635 :
636 : #include "mem-stats.h"
637 : #include "hash-map.h"
638 :
639 : inline auto &
640 : hash_table_usage ()
641 : {
642 : return mem_alloc_description<mem_usage>::instance<HASH_TABLE_ORIGIN> ();
643 : }
644 :
645 : /* Support function for statistics. */
646 : extern void dump_hash_table_loc_statistics (void);
647 :
648 : template<typename Descriptor, bool Lazy,
649 : template<typename Type> class Allocator>
650 9362398732 : hash_table<Descriptor, Lazy, Allocator>::hash_table (size_t size, bool ggc,
651 : bool sanitize_eq_and_hash,
652 : bool gather_mem_stats
653 : ATTRIBUTE_UNUSED,
654 : mem_alloc_origin origin
655 : MEM_STAT_DECL) :
656 : #if CHECKING_P
657 9362398732 : m_inserting_slot (0),
658 : #endif
659 9362398732 : m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0),
660 9362398732 : m_ggc (ggc), m_sanitize_eq_and_hash (sanitize_eq_and_hash)
661 : #if GATHER_STATISTICS
662 : , m_gather_mem_stats (gather_mem_stats)
663 : #endif
664 : {
665 : unsigned int size_prime_index;
666 :
667 9362398732 : size_prime_index = hash_table_higher_prime_index (size);
668 9362398732 : size = prime_tab[size_prime_index].prime;
669 :
670 : if (m_gather_mem_stats)
671 : hash_table_usage ().register_descriptor (this, origin, ggc
672 : FINAL_PASS_MEM_STAT);
673 :
674 : if (Lazy)
675 2786224 : m_entries = NULL;
676 : else
677 9359612508 : m_entries = alloc_entries (size PASS_MEM_STAT);
678 9362398732 : m_size = size;
679 9362398732 : m_size_prime_index = size_prime_index;
680 9359612508 : }
681 :
682 : template<typename Descriptor, bool Lazy,
683 : template<typename Type> class Allocator>
684 29285072 : hash_table<Descriptor, Lazy, Allocator>::hash_table (const hash_table &h,
685 : bool ggc,
686 : bool sanitize_eq_and_hash,
687 : bool gather_mem_stats
688 : ATTRIBUTE_UNUSED,
689 : mem_alloc_origin origin
690 : MEM_STAT_DECL) :
691 : #if CHECKING_P
692 29285072 : m_inserting_slot (0),
693 : #endif
694 29285072 : m_n_elements (h.m_n_elements), m_n_deleted (h.m_n_deleted),
695 29285072 : m_searches (0), m_collisions (0), m_ggc (ggc),
696 29285072 : m_sanitize_eq_and_hash (sanitize_eq_and_hash)
697 : #if GATHER_STATISTICS
698 : , m_gather_mem_stats (gather_mem_stats)
699 : #endif
700 : {
701 29285072 : h.check_complete_insertion ();
702 :
703 29285072 : size_t size = h.m_size;
704 :
705 : if (m_gather_mem_stats)
706 : hash_table_usage ().register_descriptor (this, origin, ggc
707 : FINAL_PASS_MEM_STAT);
708 :
709 : if (Lazy && h.m_entries == NULL)
710 : m_entries = NULL;
711 : else
712 : {
713 29285072 : value_type *nentries = alloc_entries (size PASS_MEM_STAT);
714 411215256 : for (size_t i = 0; i < size; ++i)
715 : {
716 381930184 : value_type &entry = h.m_entries[i];
717 381930184 : if (is_empty (entry))
718 360900331 : continue;
719 21029853 : else if (is_deleted (entry))
720 1738794 : mark_deleted (nentries[i]);
721 : else
722 19291059 : new ((void*) (nentries + i)) value_type (entry);
723 : }
724 29285072 : m_entries = nentries;
725 : }
726 29285072 : m_size = size;
727 29285072 : m_size_prime_index = h.m_size_prime_index;
728 29285072 : }
729 :
730 : template<typename Descriptor, bool Lazy,
731 : template<typename Type> class Allocator>
732 9341578121 : hash_table<Descriptor, Lazy, Allocator>::~hash_table ()
733 : {
734 9341578121 : check_complete_insertion ();
735 :
736 2786224 : if (!Lazy || m_entries)
737 : {
738 >19975*10^7 : for (size_t i = m_size - 1; i < m_size; i--)
739 >19041*10^7 : if (!is_empty (m_entries[i]) && !is_deleted (m_entries[i]))
740 1979858087 : Descriptor::remove (m_entries[i]);
741 :
742 9339373146 : if (!m_ggc)
743 9310300150 : Allocator <value_type> ::data_free (m_entries);
744 : else
745 29072996 : ggc_free (m_entries);
746 : if (m_gather_mem_stats)
747 : hash_table_usage ().release_instance_overhead (this,
748 : sizeof (value_type)
749 : * m_size, true);
750 : }
751 : else if (m_gather_mem_stats)
752 : hash_table_usage ().unregister_descriptor (this);
753 9341578121 : }
754 :
755 : /* This function returns an array of empty hash table elements. */
756 :
757 : template<typename Descriptor, bool Lazy,
758 : template<typename Type> class Allocator>
759 : inline typename hash_table<Descriptor, Lazy, Allocator>::value_type *
760 10567077267 : hash_table<Descriptor, Lazy,
761 : Allocator>::alloc_entries (size_t n MEM_STAT_DECL) const
762 : {
763 : value_type *nentries;
764 :
765 : if (m_gather_mem_stats)
766 : hash_table_usage ().register_instance_overhead (sizeof (value_type) * n, this);
767 :
768 10567077267 : if (!m_ggc)
769 10454635328 : nentries = Allocator <value_type> ::data_alloc (n);
770 : else
771 112441939 : nentries = ::ggc_cleared_vec_alloc<value_type> (n PASS_MEM_STAT);
772 :
773 147331175 : gcc_assert (nentries != NULL);
774 : if (!Descriptor::empty_zero_p)
775 1757622228 : for (size_t i = 0; i < n; i++)
776 1721691572 : mark_empty (nentries[i]);
777 :
778 10567077267 : return nentries;
779 : }
780 :
781 : /* Similar to find_slot, but without several unwanted side effects:
782 : - Does not call equal when it finds an existing entry.
783 : - Does not change the count of elements/searches/collisions in the
784 : hash table.
785 : This function also assumes there are no deleted entries in the table.
786 : HASH is the hash value for the element to be inserted. */
787 :
788 : template<typename Descriptor, bool Lazy,
789 : template<typename Type> class Allocator>
790 : typename hash_table<Descriptor, Lazy, Allocator>::value_type *
791 34146239968 : hash_table<Descriptor, Lazy,
792 : Allocator>::find_empty_slot_for_expand (hashval_t hash)
793 : {
794 34146239968 : hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
795 34146239968 : size_t size = m_size;
796 34146239968 : value_type *slot = m_entries + index;
797 : hashval_t hash2;
798 :
799 34146255275 : if (is_empty (*slot))
800 : return slot;
801 5397634003 : gcc_checking_assert (!is_deleted (*slot));
802 :
803 5397634003 : hash2 = hash_table_mod2 (hash, m_size_prime_index);
804 : for (;;)
805 : {
806 7599227779 : index += hash2;
807 7599227779 : if (index >= size)
808 3633256171 : index -= size;
809 :
810 7599227779 : slot = m_entries + index;
811 7599293375 : if (is_empty (*slot))
812 : return slot;
813 2201593776 : gcc_checking_assert (!is_deleted (*slot));
814 : }
815 : }
816 :
817 : /* Return true if the current table is excessively big for ELTS elements. */
818 :
819 : template<typename Descriptor, bool Lazy,
820 : template<typename Type> class Allocator>
821 : inline bool
822 540984157 : hash_table<Descriptor, Lazy, Allocator>::too_empty_p (unsigned int elts)
823 : {
824 264407337 : return elts * 8 < m_size && m_size > 32;
825 : }
826 :
827 : /* The following function changes size of memory allocated for the
828 : entries and repeatedly inserts the table elements. The occupancy
829 : of the table after the call will be about 50%. Naturally the hash
830 : table must already exist. Remember also that the place of the
831 : table entries is changed. If memory allocation fails, this function
832 : will abort. */
833 :
834 : template<typename Descriptor, bool Lazy,
835 : template<typename Type> class Allocator>
836 : void
837 1168965661 : hash_table<Descriptor, Lazy, Allocator>::expand ()
838 : {
839 1168965661 : check_complete_insertion ();
840 :
841 1168965661 : value_type *oentries = m_entries;
842 1168965661 : unsigned int oindex = m_size_prime_index;
843 1168965661 : size_t osize = size ();
844 1168965661 : value_type *olimit = oentries + osize;
845 1168965661 : size_t elts = elements ();
846 :
847 : /* Resize only when table after removal of unused elements is either
848 : too full or too empty. */
849 : unsigned int nindex;
850 : size_t nsize;
851 1168965661 : if (elts * 2 > osize || too_empty_p (elts))
852 : {
853 1160134610 : nindex = hash_table_higher_prime_index (elts * 2);
854 1160134610 : nsize = prime_tab[nindex].prime;
855 : }
856 : else
857 : {
858 : nindex = oindex;
859 : nsize = osize;
860 : }
861 :
862 1168965661 : value_type *nentries = alloc_entries (nsize);
863 :
864 : if (m_gather_mem_stats)
865 : hash_table_usage ().release_instance_overhead (this, sizeof (value_type)
866 : * osize);
867 :
868 1168965661 : size_t n_deleted = m_n_deleted;
869 :
870 1168965661 : m_entries = nentries;
871 1168965661 : m_size = nsize;
872 1168965661 : m_size_prime_index = nindex;
873 1168965661 : m_n_elements -= m_n_deleted;
874 1168965661 : m_n_deleted = 0;
875 :
876 1168965661 : size_t n_elements = m_n_elements;
877 :
878 1168965661 : value_type *p = oentries;
879 : do
880 : {
881 45640749229 : value_type &x = *p;
882 :
883 45640830132 : if (is_empty (x))
884 : ;
885 34390841946 : else if (is_deleted (x))
886 244601978 : n_deleted--;
887 : else
888 : {
889 34146239968 : n_elements--;
890 34147978706 : value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
891 34146239968 : new ((void*) q) value_type (std::move (x));
892 : /* After the resources of 'x' have been moved to a new object at 'q',
893 : we now have to destroy the 'x' object, to end its lifetime. */
894 34146239968 : x.~value_type ();
895 : }
896 :
897 45640749229 : p++;
898 : }
899 45640749229 : while (p < olimit);
900 :
901 1168965661 : gcc_checking_assert (!n_elements && !n_deleted);
902 :
903 1168965661 : if (!m_ggc)
904 1141219979 : Allocator <value_type> ::data_free (oentries);
905 : else
906 27745682 : ggc_free (oentries);
907 1168965661 : }
908 :
909 : /* Implements empty() in cases where it isn't a no-op. */
910 :
911 : template<typename Descriptor, bool Lazy,
912 : template<typename Type> class Allocator>
913 : void
914 243492719 : hash_table<Descriptor, Lazy, Allocator>::empty_slow ()
915 : {
916 243492719 : check_complete_insertion ();
917 :
918 243492719 : size_t size = m_size;
919 243492719 : size_t nsize = size;
920 243492719 : value_type *entries = m_entries;
921 :
922 17540861402 : for (size_t i = size - 1; i < size; i--)
923 17297368683 : if (!is_empty (entries[i]) && !is_deleted (entries[i]))
924 28758231 : Descriptor::remove (entries[i]);
925 :
926 : /* Instead of clearing megabyte, downsize the table. */
927 243492719 : if (size > 1024*1024 / sizeof (value_type))
928 : nsize = 1024 / sizeof (value_type);
929 243492696 : else if (too_empty_p (m_n_elements))
930 8632754 : nsize = m_n_elements * 2;
931 :
932 243492696 : if (nsize != size)
933 : {
934 8632777 : unsigned int nindex = hash_table_higher_prime_index (nsize);
935 :
936 8632777 : nsize = prime_tab[nindex].prime;
937 :
938 8632777 : if (!m_ggc)
939 1004015 : Allocator <value_type> ::data_free (m_entries);
940 : else
941 7628762 : ggc_free (m_entries);
942 :
943 8632777 : m_entries = alloc_entries (nsize);
944 8632777 : m_size = nsize;
945 8632777 : m_size_prime_index = nindex;
946 : }
947 : else if (Descriptor::empty_zero_p)
948 234858639 : memset ((void *) entries, 0, size * sizeof (value_type));
949 : else
950 18434 : for (size_t i = 0; i < size; i++)
951 17131 : mark_empty (entries[i]);
952 :
953 243492719 : m_n_deleted = 0;
954 243492719 : m_n_elements = 0;
955 243492719 : }
956 :
957 : /* This function clears a specified SLOT in a hash table. It is
958 : useful when you've already done the lookup and don't want to do it
959 : again. */
960 :
961 : template<typename Descriptor, bool Lazy,
962 : template<typename Type> class Allocator>
963 : void
964 661301524 : hash_table<Descriptor, Lazy, Allocator>::clear_slot (value_type *slot)
965 : {
966 661301524 : check_complete_insertion ();
967 :
968 661301524 : gcc_checking_assert (!(slot < m_entries || slot >= m_entries + size ()
969 : || is_empty (*slot) || is_deleted (*slot)));
970 :
971 661301524 : Descriptor::remove (*slot);
972 :
973 661301524 : mark_deleted (*slot);
974 661301524 : m_n_deleted++;
975 661301524 : }
976 :
977 : /* This function searches for a hash table entry equal to the given
978 : COMPARABLE element starting with the given HASH value. It cannot
979 : be used to insert or delete an element. */
980 :
981 : template<typename Descriptor, bool Lazy,
982 : template<typename Type> class Allocator>
983 : typename hash_table<Descriptor, Lazy, Allocator>::value_type &
984 53775819058 : hash_table<Descriptor, Lazy, Allocator>
985 : ::find_with_hash (const compare_type &comparable, hashval_t hash)
986 : {
987 53775819058 : m_searches++;
988 53775819058 : size_t size = m_size;
989 53775819058 : hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
990 :
991 : if (Lazy && m_entries == NULL)
992 : m_entries = alloc_entries (size);
993 :
994 53775819058 : check_complete_insertion ();
995 :
996 : #if CHECKING_P
997 53775819058 : if (m_sanitize_eq_and_hash)
998 53775819058 : verify (comparable, hash);
999 : #endif
1000 :
1001 53775819058 : value_type *entry = &m_entries[index];
1002 53777847110 : if (is_empty (*entry)
1003 53797333014 : || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
1004 : return *entry;
1005 :
1006 14998525857 : hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
1007 : for (;;)
1008 : {
1009 30946977952 : m_collisions++;
1010 30946977952 : index += hash2;
1011 30946977952 : if (index >= size)
1012 14996258501 : index -= size;
1013 :
1014 30946977952 : entry = &m_entries[index];
1015 30985445957 : if (is_empty (*entry)
1016 30977995076 : || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
1017 : return *entry;
1018 : }
1019 : }
1020 :
1021 : /* This function searches for a hash table slot containing an entry
1022 : equal to the given COMPARABLE element and starting with the given
1023 : HASH. To delete an entry, call this with insert=NO_INSERT, then
1024 : call clear_slot on the slot returned (possibly after doing some
1025 : checks). To insert an entry, call this with insert=INSERT, then
1026 : write the value you want into the returned slot. When inserting an
1027 : entry, NULL may be returned if memory allocation fails. */
1028 :
1029 : template<typename Descriptor, bool Lazy,
1030 : template<typename Type> class Allocator>
1031 : typename hash_table<Descriptor, Lazy, Allocator>::value_type *
1032 83824193219 : hash_table<Descriptor, Lazy, Allocator>
1033 : ::find_slot_with_hash (const compare_type &comparable, hashval_t hash,
1034 : enum insert_option insert)
1035 : {
1036 1929362 : if (Lazy && m_entries == NULL)
1037 : {
1038 581253 : if (insert == INSERT)
1039 581249 : m_entries = alloc_entries (m_size);
1040 : else
1041 : return NULL;
1042 : }
1043 83824193215 : if (insert == INSERT && m_size * 3 <= m_n_elements * 4)
1044 1167583426 : expand ();
1045 : else
1046 82656609789 : check_complete_insertion ();
1047 :
1048 : #if CHECKING_P
1049 83824193215 : if (m_sanitize_eq_and_hash)
1050 82961753764 : verify (comparable, hash);
1051 : #endif
1052 :
1053 83824193215 : m_searches++;
1054 83824193215 : value_type *first_deleted_slot = NULL;
1055 83824193215 : hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
1056 83824193215 : hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
1057 83824193215 : value_type *entry = &m_entries[index];
1058 83824193215 : size_t size = m_size;
1059 83824193215 : if (is_empty (*entry))
1060 47429707612 : goto empty_entry;
1061 36394485603 : else if (is_deleted (*entry))
1062 24261602527 : first_deleted_slot = &m_entries[index];
1063 36091107223 : else if (Descriptor::equal (*entry, comparable))
1064 2702603088 : return &m_entries[index];
1065 :
1066 : for (;;)
1067 : {
1068 47910620460 : m_collisions++;
1069 47910620460 : index += hash2;
1070 47910620460 : if (index >= size)
1071 22929893194 : index -= size;
1072 :
1073 47910620460 : entry = &m_entries[index];
1074 47910620460 : if (is_empty (*entry))
1075 18882079736 : goto empty_entry;
1076 29028540724 : else if (is_deleted (*entry))
1077 : {
1078 293381835 : if (!first_deleted_slot)
1079 23649017933 : first_deleted_slot = &m_entries[index];
1080 : }
1081 28734718437 : else if (Descriptor::equal (*entry, comparable))
1082 1353431539 : return &m_entries[index];
1083 : }
1084 :
1085 66311787348 : empty_entry:
1086 66311787348 : if (insert == NO_INSERT)
1087 : return NULL;
1088 :
1089 53220753611 : if (first_deleted_slot)
1090 : {
1091 297486033 : m_n_deleted--;
1092 297486033 : mark_empty (*first_deleted_slot);
1093 297486033 : return check_insert_slot (first_deleted_slot);
1094 : }
1095 :
1096 52923267578 : m_n_elements++;
1097 52923267578 : return check_insert_slot (&m_entries[index]);
1098 : }
1099 :
1100 : /* Verify that all existing elements in the hash table which are
1101 : equal to COMPARABLE have an equal HASH value provided as argument.
1102 : Also check that the hash table element counts are correct. */
1103 :
1104 : template<typename Descriptor, bool Lazy,
1105 : template<typename Type> class Allocator>
1106 : void
1107 >13673*10^7 : hash_table<Descriptor, Lazy, Allocator>
1108 : ::verify (const compare_type &comparable, hashval_t hash)
1109 : {
1110 >13673*10^7 : size_t n_elements = m_n_elements;
1111 >13673*10^7 : size_t n_deleted = m_n_deleted;
1112 >15008*10^8 : for (size_t i = 0; i < MIN (hash_table_sanitize_eq_limit, m_size); i++)
1113 : {
1114 >13640*10^8 : value_type *entry = &m_entries[i];
1115 >13640*10^8 : if (!is_empty (*entry))
1116 : {
1117 >53345*10^7 : n_elements--;
1118 >53345*10^7 : if (is_deleted (*entry))
1119 27713454320 : n_deleted--;
1120 >50569*10^7 : else if (hash != Descriptor::hash (*entry)
1121 >50726*10^7 : && Descriptor::equal (*entry, comparable))
1122 0 : hashtab_chk_error ();
1123 : }
1124 : }
1125 >13673*10^7 : if (hash_table_sanitize_eq_limit >= m_size)
1126 445320137 : gcc_checking_assert (!n_elements && !n_deleted);
1127 >13673*10^7 : }
1128 :
1129 : /* This function deletes an element with the given COMPARABLE value
1130 : from hash table starting with the given HASH. If there is no
1131 : matching element in the hash table, this function does nothing. */
1132 :
1133 : template<typename Descriptor, bool Lazy,
1134 : template<typename Type> class Allocator>
1135 : void
1136 308910673 : hash_table<Descriptor, Lazy, Allocator>
1137 : ::remove_elt_with_hash (const compare_type &comparable, hashval_t hash)
1138 : {
1139 308910673 : check_complete_insertion ();
1140 :
1141 308910673 : value_type *slot = find_slot_with_hash (comparable, hash, NO_INSERT);
1142 308910673 : if (slot == NULL)
1143 : return;
1144 :
1145 110942891 : Descriptor::remove (*slot);
1146 :
1147 110942891 : mark_deleted (*slot);
1148 110942891 : m_n_deleted++;
1149 : }
1150 :
1151 : /* This function scans over the entire hash table calling CALLBACK for
1152 : each live entry. If CALLBACK returns false, the iteration stops.
1153 : ARGUMENT is passed as CALLBACK's second argument. */
1154 :
1155 : template<typename Descriptor, bool Lazy,
1156 : template<typename Type> class Allocator>
1157 : template<typename Argument,
1158 : int (*Callback)
1159 : (typename hash_table<Descriptor, Lazy, Allocator>::value_type *slot,
1160 : Argument argument)>
1161 : void
1162 288372926 : hash_table<Descriptor, Lazy, Allocator>::traverse_noresize (Argument argument)
1163 : {
1164 : if (Lazy && m_entries == NULL)
1165 : return;
1166 :
1167 288372926 : check_complete_insertion ();
1168 :
1169 288372926 : value_type *slot = m_entries;
1170 288372926 : value_type *limit = slot + size ();
1171 :
1172 : do
1173 : {
1174 14322149250 : value_type &x = *slot;
1175 :
1176 14322149250 : if (!is_empty (x) && !is_deleted (x))
1177 4651808773 : if (! Callback (slot, argument))
1178 : break;
1179 : }
1180 14321922406 : while (++slot < limit);
1181 : }
1182 :
1183 : /* Like traverse_noresize, but does resize the table when it is too empty
1184 : to improve effectivity of subsequent calls. */
1185 :
1186 : template <typename Descriptor, bool Lazy,
1187 : template <typename Type> class Allocator>
1188 : template <typename Argument,
1189 : int (*Callback)
1190 : (typename hash_table<Descriptor, Lazy, Allocator>::value_type *slot,
1191 : Argument argument)>
1192 : void
1193 287207394 : hash_table<Descriptor, Lazy, Allocator>::traverse (Argument argument)
1194 : {
1195 287207394 : if (too_empty_p (elements ()) && (!Lazy || m_entries))
1196 1382235 : expand ();
1197 :
1198 287207394 : traverse_noresize <Argument, Callback> (argument);
1199 287207394 : }
1200 :
1201 : /* Slide down the iterator slots until an active entry is found. */
1202 :
1203 : template<typename Descriptor, bool Lazy,
1204 : template<typename Type> class Allocator>
1205 : void
1206 6174135940 : hash_table<Descriptor, Lazy, Allocator>::iterator::slide ()
1207 : {
1208 21068145559 : for ( ; m_slot < m_limit; ++m_slot )
1209 : {
1210 20772383801 : value_type &x = *m_slot;
1211 20772383801 : if (!is_empty (x) && !is_deleted (x))
1212 1041297533 : return;
1213 : }
1214 295761758 : m_slot = NULL;
1215 295761758 : m_limit = NULL;
1216 : }
1217 :
1218 : /* Bump the iterator. */
1219 :
1220 : template<typename Descriptor, bool Lazy,
1221 : template<typename Type> class Allocator>
1222 : inline typename hash_table<Descriptor, Lazy, Allocator>::iterator &
1223 5876627995 : hash_table<Descriptor, Lazy, Allocator>::iterator::operator ++ ()
1224 : {
1225 5876627995 : ++m_slot;
1226 3162341250 : slide ();
1227 : return *this;
1228 : }
1229 :
1230 :
1231 : /* Iterate through the elements of hash_table HTAB,
1232 : using hash_table <....>::iterator ITER,
1233 : storing each element in RESULT, which is of type TYPE. */
1234 :
1235 : #define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \
1236 : for ((ITER) = (HTAB).begin (); \
1237 : (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \
1238 : ++(ITER))
1239 :
1240 : /* ggc walking routines. */
1241 :
1242 : template<typename E>
1243 : inline void
1244 104692231 : gt_ggc_mx (hash_table<E> *h)
1245 : {
1246 : typedef hash_table<E> table;
1247 :
1248 104692231 : if (!ggc_test_and_set_mark (h->m_entries))
1249 : return;
1250 :
1251 23726002340 : for (size_t i = 0; i < h->m_size; i++)
1252 : {
1253 38048281400 : if (table::is_empty (h->m_entries[i])
1254 23621283291 : || table::is_deleted (h->m_entries[i]))
1255 16208312025 : continue;
1256 :
1257 : /* Use ggc_maxbe_mx so we don't mark right away for cache tables; we'll
1258 : mark in gt_cleare_cache if appropriate. */
1259 4315403959 : E::ggc_maybe_mx (h->m_entries[i]);
1260 : }
1261 : }
1262 :
1263 : template<typename D>
1264 : inline void
1265 19723 : hashtab_entry_note_pointers (void *obj, void *h, gt_pointer_operator op,
1266 : void *cookie)
1267 : {
1268 19723 : hash_table<D> *map = static_cast<hash_table<D> *> (h);
1269 19723 : gcc_checking_assert (map->m_entries == obj);
1270 7730080 : for (size_t i = 0; i < map->m_size; i++)
1271 : {
1272 : typedef hash_table<D> table;
1273 12964923 : if (table::is_empty (map->m_entries[i])
1274 7709979 : || table::is_deleted (map->m_entries[i]))
1275 5617841 : continue;
1276 :
1277 2092476 : D::pch_nx (map->m_entries[i], op, cookie);
1278 : }
1279 19723 : }
1280 :
1281 : template<typename D>
1282 : void
1283 19723 : gt_pch_nx (hash_table<D> *h)
1284 : {
1285 19723 : h->check_complete_insertion ();
1286 19723 : bool success
1287 19723 : = gt_pch_note_object (h->m_entries, h, hashtab_entry_note_pointers<D>);
1288 19723 : gcc_checking_assert (success);
1289 7730080 : for (size_t i = 0; i < h->m_size; i++)
1290 : {
1291 12964923 : if (hash_table<D>::is_empty (h->m_entries[i])
1292 7709979 : || hash_table<D>::is_deleted (h->m_entries[i]))
1293 5617841 : continue;
1294 :
1295 2092476 : D::pch_nx (h->m_entries[i]);
1296 : }
1297 19723 : }
1298 :
1299 : template<typename D>
1300 : inline void
1301 9835 : gt_pch_nx (hash_table<D> *h, gt_pointer_operator op, void *cookie)
1302 : {
1303 9835 : op (&h->m_entries, NULL, cookie);
1304 : }
1305 :
1306 : template<typename H>
1307 : inline void
1308 17020176 : gt_cleare_cache (hash_table<H> *h)
1309 : {
1310 : typedef hash_table<H> table;
1311 17020176 : if (!h)
1312 : return;
1313 :
1314 2872771828 : for (typename table::iterator iter = h->begin (); iter != h->end (); ++iter)
1315 2851340544 : if (!table::is_empty (*iter) && !table::is_deleted (*iter))
1316 : {
1317 3516365354 : int res = H::keep_cache_entry (*iter);
1318 2186315734 : if (res == 0)
1319 152736091 : h->clear_slot (&*iter);
1320 : else if (res != -1)
1321 2080256366 : H::ggc_mx (*iter);
1322 : }
1323 : }
1324 :
1325 : #endif /* TYPED_HASHTAB_H */
|
