Branch data Line data Source code
1 : : /* A type-safe hash table template.
2 : : Copyright (C) 2012-2025 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 : 7408528309 : xcallocator <Type>::data_alloc (size_t count)
274 : : {
275 : 7408528309 : 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 : 7406515154 : xcallocator <Type>::data_free (Type *memory)
284 : : {
285 : 7406515154 : 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 : >19836*10^7 : mul_mod (hashval_t x, hashval_t y, hashval_t inv, int shift)
324 : : {
325 : >19836*10^7 : hashval_t t1, t2, t3, t4, q, r;
326 : :
327 : >19836*10^7 : t1 = ((uint64_t)x * inv) >> 32;
328 : >19836*10^7 : t2 = x - t1;
329 : >19836*10^7 : t3 = t2 >> 1;
330 : >19836*10^7 : t4 = t1 + t3;
331 : >19836*10^7 : q = t4 >> shift;
332 : >19836*10^7 : r = x - (q * y);
333 : :
334 : >19836*10^7 : return r;
335 : : }
336 : :
337 : : /* Compute the primary table index for HASH given current prime index. */
338 : :
339 : : inline hashval_t
340 : >12479*10^7 : hash_table_mod1 (hashval_t hash, unsigned int index)
341 : : {
342 : >12479*10^7 : const struct prime_ent *p = &prime_tab[index];
343 : >12479*10^7 : gcc_checking_assert (sizeof (hashval_t) * CHAR_BIT <= 32);
344 : >12479*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 : 73571230578 : hash_table_mod2 (hashval_t hash, unsigned int index)
351 : : {
352 : 73571230578 : const struct prime_ent *p = &prime_tab[index];
353 : 73571230578 : gcc_checking_assert (sizeof (hashval_t) * CHAR_BIT <= 32);
354 : 73571230578 : 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 : 46721325 : create_ggc (size_t n, bool sanitize_eq_and_hash = true CXX_MEM_STAT_INFO)
395 : : {
396 : 46721325 : hash_table *table = ggc_alloc<hash_table> ();
397 : 46721325 : new (table) hash_table (n, true, sanitize_eq_and_hash, GATHER_STATISTICS,
398 : : HASH_TABLE_ORIGIN PASS_MEM_STAT);
399 : 46721325 : return table;
400 : : }
401 : :
402 : : /* Current size (in entries) of the hash table. */
403 : 1032233194 : size_t size () const { return m_size; }
404 : :
405 : : /* Return the current number of elements in this hash table. */
406 : 1718378408 : 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 : 811964980 : void empty () { if (elements ()) empty_slow (); }
413 : :
414 : : /* Return true when there are no elements in this hash table. */
415 : 122450763 : 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 : 1474190802 : value_type &find (const value_type &value)
429 : : {
430 : 1474190802 : return find_with_hash (value, Descriptor::hash (value));
431 : : }
432 : :
433 : 2277625239 : value_type *find_slot (const value_type &value, insert_option insert)
434 : : {
435 : 2279980972 : 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 : 6091141 : void remove_elt (const value_type &value)
456 : : {
457 : 6091141 : remove_elt_with_hash (value, Descriptor::hash (value));
458 : 6089457 : }
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 : 2990623567 : iterator () : m_slot (NULL), m_limit (NULL) {}
477 : :
478 : 307770082 : iterator (value_type *slot, value_type *limit) :
479 : 307770082 : m_slot (slot), m_limit (limit) {}
480 : :
481 : 7645633 : inline value_type &operator * () { return *m_slot; }
482 : : void slide ();
483 : : inline iterator &operator ++ ();
484 : 4799075894 : bool operator != (const iterator &other) const
485 : : {
486 : 1251754050 : 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 : 307770086 : iterator begin () const
495 : : {
496 : 8 : if (Lazy && m_entries == NULL)
497 : 4 : return iterator ();
498 : 307770082 : check_complete_insertion ();
499 : 307770082 : iterator iter (m_entries, m_entries + m_size);
500 : 307770082 : iter.slide ();
501 : 307770082 : return iter;
502 : : }
503 : :
504 : 2514103254 : iterator end () const { return iterator (); }
505 : :
506 : 286 : double collisions () const
507 : : {
508 : 286 : 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 : >57250*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 : >57250*10^7 : gcc_checking_assert (!Descriptor::is_empty (v));
542 : >57250*10^7 : return Descriptor::is_deleted (v);
543 : : }
544 : :
545 : >14448*10^8 : static bool is_empty (value_type &v)
546 : : {
547 : >22710*10^7 : return Descriptor::is_empty (v);
548 : : }
549 : :
550 : 659977197 : static void mark_deleted (value_type &v)
551 : : {
552 : 659977197 : 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 : 2147104 : }
559 : :
560 : 1859809479 : static void mark_empty (value_type &v)
561 : : {
562 : 1859809479 : Descriptor::mark_empty (v);
563 : : }
564 : :
565 : : public:
566 : >10909*10^7 : void check_complete_insertion () const
567 : : {
568 : : #if CHECKING_P
569 : >10909*10^7 : if (!m_inserting_slot)
570 : : return;
571 : :
572 : 36809872117 : gcc_checking_assert (m_inserting_slot >= &m_entries[0]
573 : : && m_inserting_slot < &m_entries[m_size]);
574 : :
575 : 36809872117 : if (!is_empty (*m_inserting_slot))
576 : 36809872117 : m_inserting_slot = NULL;
577 : : else
578 : 0 : gcc_unreachable ();
579 : : #endif
580 : : }
581 : :
582 : : private:
583 : 36400932142 : value_type *check_insert_slot (value_type *ret)
584 : : {
585 : : #if CHECKING_P
586 : 5681969735 : gcc_checking_assert (is_empty (*ret));
587 : 36821518533 : m_inserting_slot = ret;
588 : : #endif
589 : 50709 : 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 : : extern mem_alloc_description<mem_usage>& hash_table_usage (void);
640 : :
641 : : /* Support function for statistics. */
642 : : extern void dump_hash_table_loc_statistics (void);
643 : :
644 : : template<typename Descriptor, bool Lazy,
645 : : template<typename Type> class Allocator>
646 : 6640897968 : hash_table<Descriptor, Lazy, Allocator>::hash_table (size_t size, bool ggc,
647 : : bool sanitize_eq_and_hash,
648 : : bool gather_mem_stats
649 : : ATTRIBUTE_UNUSED,
650 : : mem_alloc_origin origin
651 : : MEM_STAT_DECL) :
652 : : #if CHECKING_P
653 : 6640897968 : m_inserting_slot (0),
654 : : #endif
655 : 6640897968 : m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0),
656 : 6640897968 : m_ggc (ggc), m_sanitize_eq_and_hash (sanitize_eq_and_hash)
657 : : #if GATHER_STATISTICS
658 : : , m_gather_mem_stats (gather_mem_stats)
659 : : #endif
660 : : {
661 : : unsigned int size_prime_index;
662 : :
663 : 6640897968 : size_prime_index = hash_table_higher_prime_index (size);
664 : 6640897968 : size = prime_tab[size_prime_index].prime;
665 : :
666 : : if (m_gather_mem_stats)
667 : : hash_table_usage ().register_descriptor (this, origin, ggc
668 : : FINAL_PASS_MEM_STAT);
669 : :
670 : : if (Lazy)
671 : 1626520 : m_entries = NULL;
672 : : else
673 : 6639271448 : m_entries = alloc_entries (size PASS_MEM_STAT);
674 : 6640897968 : m_size = size;
675 : 6640897968 : m_size_prime_index = size_prime_index;
676 : 6639271448 : }
677 : :
678 : : template<typename Descriptor, bool Lazy,
679 : : template<typename Type> class Allocator>
680 : 52307848 : hash_table<Descriptor, Lazy, Allocator>::hash_table (const hash_table &h,
681 : : bool ggc,
682 : : bool sanitize_eq_and_hash,
683 : : bool gather_mem_stats
684 : : ATTRIBUTE_UNUSED,
685 : : mem_alloc_origin origin
686 : : MEM_STAT_DECL) :
687 : : #if CHECKING_P
688 : 52307848 : m_inserting_slot (0),
689 : : #endif
690 : 52307848 : m_n_elements (h.m_n_elements), m_n_deleted (h.m_n_deleted),
691 : 52307848 : m_searches (0), m_collisions (0), m_ggc (ggc),
692 : 52307848 : m_sanitize_eq_and_hash (sanitize_eq_and_hash)
693 : : #if GATHER_STATISTICS
694 : : , m_gather_mem_stats (gather_mem_stats)
695 : : #endif
696 : : {
697 : 52307848 : h.check_complete_insertion ();
698 : :
699 : 52307848 : size_t size = h.m_size;
700 : :
701 : : if (m_gather_mem_stats)
702 : : hash_table_usage ().register_descriptor (this, origin, ggc
703 : : FINAL_PASS_MEM_STAT);
704 : :
705 : : if (Lazy && h.m_entries == NULL)
706 : : m_entries = NULL;
707 : : else
708 : : {
709 : 52307848 : value_type *nentries = alloc_entries (size PASS_MEM_STAT);
710 : 734599514 : for (size_t i = 0; i < size; ++i)
711 : : {
712 : 682291666 : value_type &entry = h.m_entries[i];
713 : 682291666 : if (is_empty (entry))
714 : 641820156 : continue;
715 : 40471510 : else if (is_deleted (entry))
716 : 2142684 : mark_deleted (nentries[i]);
717 : : else
718 : 38328826 : new ((void*) (nentries + i)) value_type (entry);
719 : : }
720 : 52307848 : m_entries = nentries;
721 : : }
722 : 52307848 : m_size = size;
723 : 52307848 : m_size_prime_index = h.m_size_prime_index;
724 : 52307848 : }
725 : :
726 : : template<typename Descriptor, bool Lazy,
727 : : template<typename Type> class Allocator>
728 : 6650918035 : hash_table<Descriptor, Lazy, Allocator>::~hash_table ()
729 : : {
730 : 6650918035 : check_complete_insertion ();
731 : :
732 : 1626520 : if (!Lazy || m_entries)
733 : : {
734 : >14787*10^7 : for (size_t i = m_size - 1; i < m_size; i--)
735 : >14122*10^7 : if (!is_empty (m_entries[i]) && !is_deleted (m_entries[i]))
736 : 1548870324 : Descriptor::remove (m_entries[i]);
737 : :
738 : 6649685259 : if (!m_ggc)
739 : 6621913775 : Allocator <value_type> ::data_free (m_entries);
740 : : else
741 : 27771484 : ggc_free (m_entries);
742 : : if (m_gather_mem_stats)
743 : : hash_table_usage ().release_instance_overhead (this,
744 : : sizeof (value_type)
745 : : * m_size, true);
746 : : }
747 : : else if (m_gather_mem_stats)
748 : : hash_table_usage ().unregister_descriptor (this);
749 : 6650918035 : }
750 : :
751 : : /* This function returns an array of empty hash table elements. */
752 : :
753 : : template<typename Descriptor, bool Lazy,
754 : : template<typename Type> class Allocator>
755 : : inline typename hash_table<Descriptor, Lazy, Allocator>::value_type *
756 : 7496365769 : hash_table<Descriptor, Lazy,
757 : : Allocator>::alloc_entries (size_t n MEM_STAT_DECL) const
758 : : {
759 : : value_type *nentries;
760 : :
761 : : if (m_gather_mem_stats)
762 : : hash_table_usage ().register_instance_overhead (sizeof (value_type) * n, this);
763 : :
764 : 7496365769 : if (!m_ggc)
765 : 7408528309 : nentries = Allocator <value_type> ::data_alloc (n);
766 : : else
767 : 87837460 : nentries = ::ggc_cleared_vec_alloc<value_type> (n PASS_MEM_STAT);
768 : :
769 : 115895640 : gcc_assert (nentries != NULL);
770 : : if (!Descriptor::empty_zero_p)
771 : 1631265902 : for (size_t i = 0; i < n; i++)
772 : 1602248128 : mark_empty (nentries[i]);
773 : :
774 : 7496365769 : return nentries;
775 : : }
776 : :
777 : : /* Similar to find_slot, but without several unwanted side effects:
778 : : - Does not call equal when it finds an existing entry.
779 : : - Does not change the count of elements/searches/collisions in the
780 : : hash table.
781 : : This function also assumes there are no deleted entries in the table.
782 : : HASH is the hash value for the element to be inserted. */
783 : :
784 : : template<typename Descriptor, bool Lazy,
785 : : template<typename Type> class Allocator>
786 : : typename hash_table<Descriptor, Lazy, Allocator>::value_type *
787 : 23916156736 : hash_table<Descriptor, Lazy,
788 : : Allocator>::find_empty_slot_for_expand (hashval_t hash)
789 : : {
790 : 23916156736 : hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
791 : 23916156736 : size_t size = m_size;
792 : 23916156736 : value_type *slot = m_entries + index;
793 : : hashval_t hash2;
794 : :
795 : 23916166777 : if (is_empty (*slot))
796 : : return slot;
797 : 3732971542 : gcc_checking_assert (!is_deleted (*slot));
798 : :
799 : 3732971542 : hash2 = hash_table_mod2 (hash, m_size_prime_index);
800 : : for (;;)
801 : : {
802 : 5280172203 : index += hash2;
803 : 5280172203 : if (index >= size)
804 : 2498606510 : index -= size;
805 : :
806 : 5280172203 : slot = m_entries + index;
807 : 5280214572 : if (is_empty (*slot))
808 : : return slot;
809 : 1547200661 : gcc_checking_assert (!is_deleted (*slot));
810 : : }
811 : : }
812 : :
813 : : /* Return true if the current table is excessively big for ELTS elements. */
814 : :
815 : : template<typename Descriptor, bool Lazy,
816 : : template<typename Type> class Allocator>
817 : : inline bool
818 : 401791813 : hash_table<Descriptor, Lazy, Allocator>::too_empty_p (unsigned int elts)
819 : : {
820 : 204356674 : return elts * 8 < m_size && m_size > 32;
821 : : }
822 : :
823 : : /* The following function changes size of memory allocated for the
824 : : entries and repeatedly inserts the table elements. The occupancy
825 : : of the table after the call will be about 50%. Naturally the hash
826 : : table must already exist. Remember also that the place of the
827 : : table entries is changed. If memory allocation fails, this function
828 : : will abort. */
829 : :
830 : : template<typename Descriptor, bool Lazy,
831 : : template<typename Type> class Allocator>
832 : : void
833 : 798959650 : hash_table<Descriptor, Lazy, Allocator>::expand ()
834 : : {
835 : 798959650 : check_complete_insertion ();
836 : :
837 : 798959650 : value_type *oentries = m_entries;
838 : 798959650 : unsigned int oindex = m_size_prime_index;
839 : 798959650 : size_t osize = size ();
840 : 798959650 : value_type *olimit = oentries + osize;
841 : 798959650 : size_t elts = elements ();
842 : :
843 : : /* Resize only when table after removal of unused elements is either
844 : : too full or too empty. */
845 : : unsigned int nindex;
846 : : size_t nsize;
847 : 798959650 : if (elts * 2 > osize || too_empty_p (elts))
848 : : {
849 : 791528462 : nindex = hash_table_higher_prime_index (elts * 2);
850 : 791528462 : nsize = prime_tab[nindex].prime;
851 : : }
852 : : else
853 : : {
854 : : nindex = oindex;
855 : : nsize = osize;
856 : : }
857 : :
858 : 798959650 : value_type *nentries = alloc_entries (nsize);
859 : :
860 : : if (m_gather_mem_stats)
861 : : hash_table_usage ().release_instance_overhead (this, sizeof (value_type)
862 : : * osize);
863 : :
864 : 798959650 : size_t n_deleted = m_n_deleted;
865 : :
866 : 798959650 : m_entries = nentries;
867 : 798959650 : m_size = nsize;
868 : 798959650 : m_size_prime_index = nindex;
869 : 798959650 : m_n_elements -= m_n_deleted;
870 : 798959650 : m_n_deleted = 0;
871 : :
872 : 798959650 : size_t n_elements = m_n_elements;
873 : :
874 : 798959650 : value_type *p = oentries;
875 : : do
876 : : {
877 : 32087553794 : value_type &x = *p;
878 : :
879 : 32087606204 : if (is_empty (x))
880 : : ;
881 : 24116719739 : else if (is_deleted (x))
882 : 200563003 : n_deleted--;
883 : : else
884 : : {
885 : 23916156736 : n_elements--;
886 : 23917882390 : value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
887 : 23916156736 : new ((void*) q) value_type (std::move (x));
888 : : /* After the resources of 'x' have been moved to a new object at 'q',
889 : : we now have to destroy the 'x' object, to end its lifetime. */
890 : 23916156736 : x.~value_type ();
891 : : }
892 : :
893 : 32087553794 : p++;
894 : : }
895 : 32087553794 : while (p < olimit);
896 : :
897 : 798959650 : gcc_checking_assert (!n_elements && !n_deleted);
898 : :
899 : 798959650 : if (!m_ggc)
900 : 783668735 : Allocator <value_type> ::data_free (oentries);
901 : : else
902 : 15290915 : ggc_free (oentries);
903 : 798959650 : }
904 : :
905 : : /* Implements empty() in cases where it isn't a no-op. */
906 : :
907 : : template<typename Descriptor, bool Lazy,
908 : : template<typename Type> class Allocator>
909 : : void
910 : 133987504 : hash_table<Descriptor, Lazy, Allocator>::empty_slow ()
911 : : {
912 : 133987504 : check_complete_insertion ();
913 : :
914 : 133987504 : size_t size = m_size;
915 : 133987504 : size_t nsize = size;
916 : 133987504 : value_type *entries = m_entries;
917 : :
918 : 10013942392 : for (size_t i = size - 1; i < size; i--)
919 : 9879954888 : if (!is_empty (entries[i]) && !is_deleted (entries[i]))
920 : 41404361 : Descriptor::remove (entries[i]);
921 : :
922 : : /* Instead of clearing megabyte, downsize the table. */
923 : 133987504 : if (size > 1024*1024 / sizeof (value_type))
924 : : nsize = 1024 / sizeof (value_type);
925 : 133987490 : else if (too_empty_p (m_n_elements))
926 : 5433065 : nsize = m_n_elements * 2;
927 : :
928 : 133987490 : if (nsize != size)
929 : : {
930 : 5433079 : unsigned int nindex = hash_table_higher_prime_index (nsize);
931 : :
932 : 5433079 : nsize = prime_tab[nindex].prime;
933 : :
934 : 5433079 : if (!m_ggc)
935 : 932644 : Allocator <value_type> ::data_free (m_entries);
936 : : else
937 : 4500435 : ggc_free (m_entries);
938 : :
939 : 5433079 : m_entries = alloc_entries (nsize);
940 : 5433079 : m_size = nsize;
941 : 5433079 : m_size_prime_index = nindex;
942 : : }
943 : : else if (Descriptor::empty_zero_p)
944 : 128553446 : memset ((void *) entries, 0, size * sizeof (value_type));
945 : : else
946 : 13898 : for (size_t i = 0; i < size; i++)
947 : 12919 : mark_empty (entries[i]);
948 : :
949 : 133987504 : m_n_deleted = 0;
950 : 133987504 : m_n_elements = 0;
951 : 133987504 : }
952 : :
953 : : /* This function clears a specified SLOT in a hash table. It is
954 : : useful when you've already done the lookup and don't want to do it
955 : : again. */
956 : :
957 : : template<typename Descriptor, bool Lazy,
958 : : template<typename Type> class Allocator>
959 : : void
960 : 571586990 : hash_table<Descriptor, Lazy, Allocator>::clear_slot (value_type *slot)
961 : : {
962 : 571586990 : check_complete_insertion ();
963 : :
964 : 571586990 : gcc_checking_assert (!(slot < m_entries || slot >= m_entries + size ()
965 : : || is_empty (*slot) || is_deleted (*slot)));
966 : :
967 : 571586990 : Descriptor::remove (*slot);
968 : :
969 : 571586990 : mark_deleted (*slot);
970 : 571586990 : m_n_deleted++;
971 : 571586990 : }
972 : :
973 : : /* This function searches for a hash table entry equal to the given
974 : : COMPARABLE element starting with the given HASH value. It cannot
975 : : be used to insert or delete an element. */
976 : :
977 : : template<typename Descriptor, bool Lazy,
978 : : template<typename Type> class Allocator>
979 : : typename hash_table<Descriptor, Lazy, Allocator>::value_type &
980 : 42209472344 : hash_table<Descriptor, Lazy, Allocator>
981 : : ::find_with_hash (const compare_type &comparable, hashval_t hash)
982 : : {
983 : 42209472344 : m_searches++;
984 : 42209472344 : size_t size = m_size;
985 : 42209472344 : hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
986 : :
987 : : if (Lazy && m_entries == NULL)
988 : : m_entries = alloc_entries (size);
989 : :
990 : 42209472344 : check_complete_insertion ();
991 : :
992 : : #if CHECKING_P
993 : 42209472344 : if (m_sanitize_eq_and_hash)
994 : 42209472344 : verify (comparable, hash);
995 : : #endif
996 : :
997 : 42209472344 : value_type *entry = &m_entries[index];
998 : 42210500324 : if (is_empty (*entry)
999 : 42233470911 : || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
1000 : 925111585 : return *entry;
1001 : :
1002 : 11168508909 : hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
1003 : : for (;;)
1004 : : {
1005 : 22030262692 : m_collisions++;
1006 : 22030262692 : index += hash2;
1007 : 22030262692 : if (index >= size)
1008 : 10703957356 : index -= size;
1009 : :
1010 : 22030262692 : entry = &m_entries[index];
1011 : 22063849933 : if (is_empty (*entry)
1012 : 22069203880 : || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
1013 : : return *entry;
1014 : : }
1015 : : }
1016 : :
1017 : : /* This function searches for a hash table slot containing an entry
1018 : : equal to the given COMPARABLE element and starting with the given
1019 : : HASH. To delete an entry, call this with insert=NO_INSERT, then
1020 : : call clear_slot on the slot returned (possibly after doing some
1021 : : checks). To insert an entry, call this with insert=INSERT, then
1022 : : write the value you want into the returned slot. When inserting an
1023 : : entry, NULL may be returned if memory allocation fails. */
1024 : :
1025 : : template<typename Descriptor, bool Lazy,
1026 : : template<typename Type> class Allocator>
1027 : : typename hash_table<Descriptor, Lazy, Allocator>::value_type *
1028 : 58669750131 : hash_table<Descriptor, Lazy, Allocator>
1029 : : ::find_slot_with_hash (const compare_type &comparable, hashval_t hash,
1030 : : enum insert_option insert)
1031 : : {
1032 : 1386906 : if (Lazy && m_entries == NULL)
1033 : : {
1034 : 393748 : if (insert == INSERT)
1035 : 393744 : m_entries = alloc_entries (m_size);
1036 : : else
1037 : : return NULL;
1038 : : }
1039 : 58669750127 : if (insert == INSERT && m_size * 3 <= m_n_elements * 4)
1040 : 797778455 : expand ();
1041 : : else
1042 : 57871971672 : check_complete_insertion ();
1043 : :
1044 : : #if CHECKING_P
1045 : 58669750127 : if (m_sanitize_eq_and_hash)
1046 : 57877059779 : verify (comparable, hash);
1047 : : #endif
1048 : :
1049 : 58669750127 : m_searches++;
1050 : 58669750127 : value_type *first_deleted_slot = NULL;
1051 : 58669750127 : hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
1052 : 58669750127 : hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
1053 : 58669750127 : value_type *entry = &m_entries[index];
1054 : 58669750127 : size_t size = m_size;
1055 : 58669750127 : if (is_empty (*entry))
1056 : 32813430994 : goto empty_entry;
1057 : 25856319133 : else if (is_deleted (*entry))
1058 : 10945619 : first_deleted_slot = &m_entries[index];
1059 : 25590400301 : else if (Descriptor::equal (*entry, comparable))
1060 : 2290452940 : return &m_entries[index];
1061 : :
1062 : : for (;;)
1063 : : {
1064 : 32830720431 : m_collisions++;
1065 : 32830720431 : index += hash2;
1066 : 32830720431 : if (index >= size)
1067 : 15813818300 : index -= size;
1068 : :
1069 : 32830720431 : entry = &m_entries[index];
1070 : 32830720431 : if (is_empty (*entry))
1071 : 13004986882 : goto empty_entry;
1072 : 19825733549 : else if (is_deleted (*entry))
1073 : : {
1074 : 260948931 : if (!first_deleted_slot)
1075 : 16294343396 : first_deleted_slot = &m_entries[index];
1076 : : }
1077 : 19571694756 : else if (Descriptor::equal (*entry, comparable))
1078 : 955567647 : return &m_entries[index];
1079 : : }
1080 : :
1081 : 45818417876 : empty_entry:
1082 : 45818417876 : if (insert == NO_INSERT)
1083 : : return NULL;
1084 : :
1085 : 36821518533 : if (first_deleted_slot)
1086 : : {
1087 : 257548432 : m_n_deleted--;
1088 : 257548432 : mark_empty (*first_deleted_slot);
1089 : 257548432 : return check_insert_slot (first_deleted_slot);
1090 : : }
1091 : :
1092 : 36563970101 : m_n_elements++;
1093 : 36563970101 : return check_insert_slot (&m_entries[index]);
1094 : : }
1095 : :
1096 : : /* Verify that all existing elements in the hash table which are
1097 : : equal to COMPARABLE have an equal HASH value provided as argument.
1098 : : Also check that the hash table element counts are correct. */
1099 : :
1100 : : template<typename Descriptor, bool Lazy,
1101 : : template<typename Type> class Allocator>
1102 : : void
1103 : >10008*10^7 : hash_table<Descriptor, Lazy, Allocator>
1104 : : ::verify (const compare_type &comparable, hashval_t hash)
1105 : : {
1106 : >10008*10^7 : size_t n_elements = m_n_elements;
1107 : >10008*10^7 : size_t n_deleted = m_n_deleted;
1108 : >10980*10^8 : for (size_t i = 0; i < MIN (hash_table_sanitize_eq_limit, m_size); i++)
1109 : : {
1110 : >99799*10^7 : value_type *entry = &m_entries[i];
1111 : >99799*10^7 : if (!is_empty (*entry))
1112 : : {
1113 : >39368*10^7 : n_elements--;
1114 : >39368*10^7 : if (is_deleted (*entry))
1115 : 22801518641 : n_deleted--;
1116 : >37084*10^7 : else if (hash != Descriptor::hash (*entry)
1117 : >37200*10^7 : && Descriptor::equal (*entry, comparable))
1118 : 0 : hashtab_chk_error ();
1119 : : }
1120 : : }
1121 : >10008*10^7 : if (hash_table_sanitize_eq_limit >= m_size)
1122 : 343447769 : gcc_checking_assert (!n_elements && !n_deleted);
1123 : >10008*10^7 : }
1124 : :
1125 : : /* This function deletes an element with the given COMPARABLE value
1126 : : from hash table starting with the given HASH. If there is no
1127 : : matching element in the hash table, this function does nothing. */
1128 : :
1129 : : template<typename Descriptor, bool Lazy,
1130 : : template<typename Type> class Allocator>
1131 : : void
1132 : 237176916 : hash_table<Descriptor, Lazy, Allocator>
1133 : : ::remove_elt_with_hash (const compare_type &comparable, hashval_t hash)
1134 : : {
1135 : 237176916 : check_complete_insertion ();
1136 : :
1137 : 237176916 : value_type *slot = find_slot_with_hash (comparable, hash, NO_INSERT);
1138 : 237176916 : if (slot == NULL)
1139 : : return;
1140 : :
1141 : 86247547 : Descriptor::remove (*slot);
1142 : :
1143 : 86247547 : mark_deleted (*slot);
1144 : 86247547 : m_n_deleted++;
1145 : : }
1146 : :
1147 : : /* This function scans over the entire hash table calling CALLBACK for
1148 : : each live entry. If CALLBACK returns false, the iteration stops.
1149 : : ARGUMENT is passed as CALLBACK's second argument. */
1150 : :
1151 : : template<typename Descriptor, bool Lazy,
1152 : : template<typename Type> class Allocator>
1153 : : template<typename Argument,
1154 : : int (*Callback)
1155 : : (typename hash_table<Descriptor, Lazy, Allocator>::value_type *slot,
1156 : : Argument argument)>
1157 : : void
1158 : 259980235 : hash_table<Descriptor, Lazy, Allocator>::traverse_noresize (Argument argument)
1159 : : {
1160 : : if (Lazy && m_entries == NULL)
1161 : : return;
1162 : :
1163 : 259980235 : check_complete_insertion ();
1164 : :
1165 : 259980235 : value_type *slot = m_entries;
1166 : 259980235 : value_type *limit = slot + size ();
1167 : :
1168 : : do
1169 : : {
1170 : 13105063728 : value_type &x = *slot;
1171 : :
1172 : 13105063728 : if (!is_empty (x) && !is_deleted (x))
1173 : 4410972147 : if (! Callback (slot, argument))
1174 : : break;
1175 : : }
1176 : 13104857215 : while (++slot < limit);
1177 : : }
1178 : :
1179 : : /* Like traverse_noresize, but does resize the table when it is too empty
1180 : : to improve effectivity of subsequent calls. */
1181 : :
1182 : : template <typename Descriptor, bool Lazy,
1183 : : template <typename Type> class Allocator>
1184 : : template <typename Argument,
1185 : : int (*Callback)
1186 : : (typename hash_table<Descriptor, Lazy, Allocator>::value_type *slot,
1187 : : Argument argument)>
1188 : : void
1189 : 259129151 : hash_table<Descriptor, Lazy, Allocator>::traverse (Argument argument)
1190 : : {
1191 : 259129151 : if (too_empty_p (elements ()) && (!Lazy || m_entries))
1192 : 1181195 : expand ();
1193 : :
1194 : 259129151 : traverse_noresize <Argument, Callback> (argument);
1195 : 259129151 : }
1196 : :
1197 : : /* Slide down the iterator slots until an active entry is found. */
1198 : :
1199 : : template<typename Descriptor, bool Lazy,
1200 : : template<typename Type> class Allocator>
1201 : : void
1202 : 4799255469 : hash_table<Descriptor, Lazy, Allocator>::iterator::slide ()
1203 : : {
1204 : 17498931060 : for ( ; m_slot < m_limit; ++m_slot )
1205 : : {
1206 : 17192628218 : value_type &x = *m_slot;
1207 : 17192628218 : if (!is_empty (x) && !is_deleted (x))
1208 : 732830414 : return;
1209 : : }
1210 : 306302842 : m_slot = NULL;
1211 : 306302842 : m_limit = NULL;
1212 : : }
1213 : :
1214 : : /* Bump the iterator. */
1215 : :
1216 : : template<typename Descriptor, bool Lazy,
1217 : : template<typename Type> class Allocator>
1218 : : inline typename hash_table<Descriptor, Lazy, Allocator>::iterator &
1219 : 4491485387 : hash_table<Descriptor, Lazy, Allocator>::iterator::operator ++ ()
1220 : : {
1221 : 4491485387 : ++m_slot;
1222 : 2645832838 : slide ();
1223 : 3009230189 : return *this;
1224 : : }
1225 : :
1226 : :
1227 : : /* Iterate through the elements of hash_table HTAB,
1228 : : using hash_table <....>::iterator ITER,
1229 : : storing each element in RESULT, which is of type TYPE. */
1230 : :
1231 : : #define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \
1232 : : for ((ITER) = (HTAB).begin (); \
1233 : : (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \
1234 : : ++(ITER))
1235 : :
1236 : : /* ggc walking routines. */
1237 : :
1238 : : template<typename E>
1239 : : inline void
1240 : 74181695 : gt_ggc_mx (hash_table<E> *h)
1241 : : {
1242 : : typedef hash_table<E> table;
1243 : :
1244 : 74181695 : if (!ggc_test_and_set_mark (h->m_entries))
1245 : 0 : return;
1246 : :
1247 : 17717497536 : for (size_t i = 0; i < h->m_size; i++)
1248 : : {
1249 : 28720260586 : if (table::is_empty (h->m_entries[i])
1250 : 17643315722 : || table::is_deleted (h->m_entries[i]))
1251 : 12239147079 : continue;
1252 : :
1253 : : /* Use ggc_maxbe_mx so we don't mark right away for cache tables; we'll
1254 : : mark in gt_cleare_cache if appropriate. */
1255 : 3294399507 : E::ggc_maybe_mx (h->m_entries[i]);
1256 : : }
1257 : : }
1258 : :
1259 : : template<typename D>
1260 : : inline void
1261 : 17483 : hashtab_entry_note_pointers (void *obj, void *h, gt_pointer_operator op,
1262 : : void *cookie)
1263 : : {
1264 : 17483 : hash_table<D> *map = static_cast<hash_table<D> *> (h);
1265 : 17483 : gcc_checking_assert (map->m_entries == obj);
1266 : 6940494 : for (size_t i = 0; i < map->m_size; i++)
1267 : : {
1268 : : typedef hash_table<D> table;
1269 : 11863563 : if (table::is_empty (map->m_entries[i])
1270 : 6922633 : || table::is_deleted (map->m_entries[i]))
1271 : 5202284 : continue;
1272 : :
1273 : 1720699 : D::pch_nx (map->m_entries[i], op, cookie);
1274 : : }
1275 : 17483 : }
1276 : :
1277 : : template<typename D>
1278 : : void
1279 : 17483 : gt_pch_nx (hash_table<D> *h)
1280 : : {
1281 : 17483 : h->check_complete_insertion ();
1282 : 17483 : bool success
1283 : 17483 : = gt_pch_note_object (h->m_entries, h, hashtab_entry_note_pointers<D>);
1284 : 17483 : gcc_checking_assert (success);
1285 : 6940494 : for (size_t i = 0; i < h->m_size; i++)
1286 : : {
1287 : 11863563 : if (hash_table<D>::is_empty (h->m_entries[i])
1288 : 6922633 : || hash_table<D>::is_deleted (h->m_entries[i]))
1289 : 5202284 : continue;
1290 : :
1291 : 1720699 : D::pch_nx (h->m_entries[i]);
1292 : : }
1293 : 17483 : }
1294 : :
1295 : : template<typename D>
1296 : : inline void
1297 : 10363 : gt_pch_nx (hash_table<D> *h, gt_pointer_operator op, void *cookie)
1298 : : {
1299 : 10363 : op (&h->m_entries, NULL, cookie);
1300 : 10363 : }
1301 : :
1302 : : template<typename H>
1303 : : inline void
1304 : 13544046 : gt_cleare_cache (hash_table<H> *h)
1305 : : {
1306 : : typedef hash_table<H> table;
1307 : 13544046 : if (!h)
1308 : : return;
1309 : :
1310 : 3663949448 : for (typename table::iterator iter = h->begin (); iter != h->end (); ++iter)
1311 : 1948012603 : if (!table::is_empty (*iter) && !table::is_deleted (*iter))
1312 : : {
1313 : 2197011743 : int res = H::keep_cache_entry (*iter);
1314 : 1699013463 : if (res == 0)
1315 : 124297564 : h->clear_slot (&*iter);
1316 : : else if (res != -1)
1317 : 1614288829 : H::ggc_mx (*iter);
1318 : : }
1319 : : }
1320 : :
1321 : : #endif /* TYPED_HASHTAB_H */
|
