1 /* A type-safe hash table template.
2 Copyright (C) 2012-2023 Free Software Foundation, Inc.
3 Contributed by Lawrence Crowl <crowl@google.com>
5 This file is part of GCC.
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
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
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/>. */
22 /* This file implements a typed hash table.
23 The implementation borrows from libiberty's htab_t in hashtab.h.
28 Users of the hash table generally need to be aware of three types.
30 1. The type being placed into the hash table. This type is called
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
37 - A typedef named 'value_type' to the value type (from above).
38 Provided a suitable Descriptor class it may be a user-defined,
41 - A static member function named 'hash' that takes a value_type
42 (or 'const value_type &') and returns a hashval_t value.
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.
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
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).
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.
69 3. The type of the hash table itself. (More later.)
71 In very special circumstances, users may need to know about a fourth type.
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:
77 - A static member function named 'data_alloc'. This function
78 allocates the data elements in the table.
80 - A static member function named 'data_free'. This function
81 deallocates the data elements in the table.
83 Hash table are instantiated with two type arguments.
85 * The descriptor type, (2) above.
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.
92 DEFINING A DESCRIPTOR TYPE
94 The first task in using the hash table is to describe the element type.
95 We compose this into a few steps.
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
101 * typed_free_remove implements the static 'remove' member function
104 * typed_noop_remove implements the static 'remove' member function
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
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.
119 You can use these policies by simply deriving the descriptor type
120 from one of those class template, with the appropriate argument.
122 Otherwise, you need to write the static 'remove' member function
123 in the descriptor class.
125 2. Choose a hash function. Write the static 'hash' member function.
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
131 4. Choose an equality testing function 'equal' that compares a value_type
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
138 AN EXAMPLE DESCRIPTOR TYPE
140 Suppose you want to put some_type into the hash table. You could define
141 the descriptor type as follows.
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.
147 static inline hashval_t hash (const value_type *);
148 static inline bool equal (const value_type *, const compare_type *);
152 some_type_hasher::hash (const value_type *e)
153 { ... compute and return a hash value for E ... }
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' ... }
160 AN EXAMPLE HASH_TABLE DECLARATION
162 To instantiate a hash table for some_type:
164 hash_table <some_type_hasher> some_type_hash_table;
166 There is no need to mention some_type directly, as the hash table will
167 obtain it using some_type_hasher::value_type.
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
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
177 hash_table <some_type_hasher, true> some_type_hash_table;
179 which will cause whatever methods actually need the allocated entries
180 array to allocate it later.
183 EASY DESCRIPTORS FOR POINTERS
185 There are four descriptors for pointer elements, one for each of
186 the removal policies above:
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)
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:
197 hash_table <nofree_ptr_hash <whatever_type> > whatever_type_hash_table;
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:
205 extern void consume (some_info *);
207 We define a convenience typedef and the hash table:
209 typedef hash_table <some_info_hasher> info_table_type;
210 info_table_type info_table;
212 Then we write the loop in typical C++ style:
214 for (info_table_type::iterator iter = info_table.begin ();
215 iter != info_table.end ();
217 if ((*iter).status == INFO_READY)
220 Or with common sub-expression elimination:
222 for (info_table_type::iterator iter = info_table.begin ();
223 iter != info_table.end ();
226 some_info &elem = *iter;
227 if (elem.status == INFO_READY)
231 One can also use a more typical GCC style:
233 typedef some_info *some_info_p;
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)
243 #ifndef TYPED_HASHTAB_H
244 #define TYPED_HASHTAB_H
246 #include "statistics.h"
251 #include "mem-stats-traits.h"
252 #include "hash-traits.h"
253 #include "hash-map-traits.h"
255 template<typename
, typename
, typename
> class hash_map
;
256 template<typename
, bool, typename
> class hash_set
;
258 /* The ordinary memory allocator. */
259 /* FIXME (crowl): This allocator may be extracted for wider sharing later. */
261 template <typename Type
>
264 static Type
*data_alloc (size_t count
);
265 static void data_free (Type
*memory
);
269 /* Allocate memory for COUNT data blocks. */
271 template <typename Type
>
273 xcallocator
<Type
>::data_alloc (size_t count
)
275 return static_cast <Type
*> (xcalloc (count
, sizeof (Type
)));
279 /* Free memory for data blocks. */
281 template <typename Type
>
283 xcallocator
<Type
>::data_free (Type
*memory
)
285 return ::free (memory
);
289 /* Table of primes and their inversion information. */
295 hashval_t inv_m2
; /* inverse of prime-2 */
299 extern struct prime_ent
const prime_tab
[];
301 /* Limit number of comparisons when calling hash_table<>::verify. */
302 extern unsigned int hash_table_sanitize_eq_limit
;
304 /* Functions for computing hash table indexes. */
306 extern unsigned int hash_table_higher_prime_index (unsigned long n
)
309 extern ATTRIBUTE_NORETURN ATTRIBUTE_COLD
void hashtab_chk_error ();
311 /* Return X % Y using multiplicative inverse values INV and SHIFT.
313 The multiplicative inverses computed above are for 32-bit types,
314 and requires that we be able to compute a highpart multiply.
316 FIX: I am not at all convinced that
317 3 loads, 2 multiplications, 3 shifts, and 3 additions
320 on modern systems running a compiler. */
323 mul_mod (hashval_t x
, hashval_t y
, hashval_t inv
, int shift
)
325 hashval_t t1
, t2
, t3
, t4
, q
, r
;
327 t1
= ((uint64_t)x
* inv
) >> 32;
337 /* Compute the primary table index for HASH given current prime index. */
340 hash_table_mod1 (hashval_t hash
, unsigned int index
)
342 const struct prime_ent
*p
= &prime_tab
[index
];
343 gcc_checking_assert (sizeof (hashval_t
) * CHAR_BIT
<= 32);
344 return mul_mod (hash
, p
->prime
, p
->inv
, p
->shift
);
347 /* Compute the secondary table index for HASH given current prime index. */
350 hash_table_mod2 (hashval_t hash
, unsigned int index
)
352 const struct prime_ent
*p
= &prime_tab
[index
];
353 gcc_checking_assert (sizeof (hashval_t
) * CHAR_BIT
<= 32);
354 return 1 + mul_mod (hash
, p
->prime
- 2, p
->inv_m2
, p
->shift
);
359 /* User-facing hash table type.
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.
365 Specify the template Allocator to allocate and free memory.
366 The default is xcallocator.
368 Storage is an implementation detail and should not be used outside the
372 template <typename Descriptor
, bool Lazy
= false,
373 template<typename Type
> class Allocator
= xcallocator
>
376 typedef typename
Descriptor::value_type value_type
;
377 typedef typename
Descriptor::compare_type compare_type
;
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
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
392 /* Create a hash_table in gc memory. */
394 create_ggc (size_t n
, bool sanitize_eq_and_hash
= true CXX_MEM_STAT_INFO
)
396 hash_table
*table
= ggc_alloc
<hash_table
> ();
397 new (table
) hash_table (n
, true, sanitize_eq_and_hash
, GATHER_STATISTICS
,
398 HASH_TABLE_ORIGIN PASS_MEM_STAT
);
402 /* Current size (in entries) of the hash table. */
403 size_t size () const { return m_size
; }
405 /* Return the current number of elements in this hash table. */
406 size_t elements () const { return m_n_elements
- m_n_deleted
; }
408 /* Return the current number of elements in this hash table. */
409 size_t elements_with_deleted () const { return m_n_elements
; }
411 /* This function clears all entries in this hash table. */
412 void empty () { if (elements ()) empty_slow (); }
414 /* Return true when there are no elements in this hash table. */
415 bool is_empty () const { return elements () == 0; }
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
420 void clear_slot (value_type
*);
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
);
427 /* Like find_slot_with_hash, but compute the hash value from the element. */
428 value_type
&find (const value_type
&value
)
430 return find_with_hash (value
, Descriptor::hash (value
));
433 value_type
*find_slot (const value_type
&value
, insert_option insert
)
435 return find_slot_with_hash (value
, Descriptor::hash (value
), insert
);
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
);
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
);
453 /* Like remove_elt_with_hash, but compute the hash value from the
455 void remove_elt (const value_type
&value
)
457 remove_elt_with_hash (value
, Descriptor::hash (value
));
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
);
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
);
476 iterator () : m_slot (NULL
), m_limit (NULL
) {}
478 iterator (value_type
*slot
, value_type
*limit
) :
479 m_slot (slot
), m_limit (limit
) {}
481 inline value_type
&operator * () { return *m_slot
; }
483 inline iterator
&operator ++ ();
484 bool operator != (const iterator
&other
) const
486 return m_slot
!= other
.m_slot
|| m_limit
!= other
.m_limit
;
494 iterator
begin () const
496 if (Lazy
&& m_entries
== NULL
)
498 check_complete_insertion ();
499 iterator
iter (m_entries
, m_entries
+ m_size
);
504 iterator
end () const { return iterator (); }
506 double collisions () const
508 return m_searches
? static_cast <double> (m_collisions
) / m_searches
: 0;
512 /* FIXME: Make the class assignable. See pr90959. */
513 void operator= (hash_table
&);
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 *);
526 template<typename T
> friend void gt_cleare_cache (hash_table
<T
> *);
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);
535 static bool is_deleted (value_type
&v
)
537 return Descriptor::is_deleted (v
);
540 static bool is_empty (value_type
&v
)
542 return Descriptor::is_empty (v
);
545 static void mark_deleted (value_type
&v
)
547 Descriptor::mark_deleted (v
);
550 static void mark_empty (value_type
&v
)
552 Descriptor::mark_empty (v
);
556 void check_complete_insertion () const
559 if (!m_inserting_slot
)
562 gcc_checking_assert (m_inserting_slot
>= &m_entries
[0]
563 && m_inserting_slot
< &m_entries
[m_size
]);
565 if (!is_empty (*m_inserting_slot
))
566 m_inserting_slot
= NULL
;
573 value_type
*check_insert_slot (value_type
*ret
)
576 gcc_checking_assert (is_empty (*ret
));
577 m_inserting_slot
= ret
;
583 mutable value_type
*m_inserting_slot
;
587 value_type
*m_entries
;
591 /* Current number of elements including also deleted elements. */
594 /* Current number of deleted elements in the table. */
597 /* The following member is used for debugging. Its value is number
598 of all calls of `htab_find_slot' for the hash table. */
599 unsigned int m_searches
;
601 /* The following member is used for debugging. Its value is number
602 of collisions fixed for time of work with the hash table. */
603 unsigned int m_collisions
;
605 /* Current size (in entries) of the hash table, as an index into the
607 unsigned int m_size_prime_index
;
609 /* if m_entries is stored in ggc memory. */
612 /* True if the table should be sanitized for equal and hash functions. */
613 bool m_sanitize_eq_and_hash
;
615 /* If we should gather memory statistics for the table. */
616 #if GATHER_STATISTICS
617 bool m_gather_mem_stats
;
619 static const bool m_gather_mem_stats
= false;
623 /* As mem-stats.h heavily utilizes hash maps (hash tables), we have to include
624 mem-stats.h after hash_table declaration. */
626 #include "mem-stats.h"
627 #include "hash-map.h"
629 extern mem_alloc_description
<mem_usage
>& hash_table_usage (void);
631 /* Support function for statistics. */
632 extern void dump_hash_table_loc_statistics (void);
634 template<typename Descriptor
, bool Lazy
,
635 template<typename Type
> class Allocator
>
636 hash_table
<Descriptor
, Lazy
, Allocator
>::hash_table (size_t size
, bool ggc
,
637 bool sanitize_eq_and_hash
,
638 bool gather_mem_stats
640 mem_alloc_origin origin
643 m_inserting_slot (0),
645 m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0),
646 m_ggc (ggc
), m_sanitize_eq_and_hash (sanitize_eq_and_hash
)
647 #if GATHER_STATISTICS
648 , m_gather_mem_stats (gather_mem_stats
)
651 unsigned int size_prime_index
;
653 size_prime_index
= hash_table_higher_prime_index (size
);
654 size
= prime_tab
[size_prime_index
].prime
;
656 if (m_gather_mem_stats
)
657 hash_table_usage ().register_descriptor (this, origin
, ggc
658 FINAL_PASS_MEM_STAT
);
663 m_entries
= alloc_entries (size PASS_MEM_STAT
);
665 m_size_prime_index
= size_prime_index
;
668 template<typename Descriptor
, bool Lazy
,
669 template<typename Type
> class Allocator
>
670 hash_table
<Descriptor
, Lazy
, Allocator
>::hash_table (const hash_table
&h
,
672 bool sanitize_eq_and_hash
,
673 bool gather_mem_stats
675 mem_alloc_origin origin
678 m_inserting_slot (0),
680 m_n_elements (h
.m_n_elements
), m_n_deleted (h
.m_n_deleted
),
681 m_searches (0), m_collisions (0), m_ggc (ggc
),
682 m_sanitize_eq_and_hash (sanitize_eq_and_hash
)
683 #if GATHER_STATISTICS
684 , m_gather_mem_stats (gather_mem_stats
)
687 h
.check_complete_insertion ();
689 size_t size
= h
.m_size
;
691 if (m_gather_mem_stats
)
692 hash_table_usage ().register_descriptor (this, origin
, ggc
693 FINAL_PASS_MEM_STAT
);
695 if (Lazy
&& h
.m_entries
== NULL
)
699 value_type
*nentries
= alloc_entries (size PASS_MEM_STAT
);
700 for (size_t i
= 0; i
< size
; ++i
)
702 value_type
&entry
= h
.m_entries
[i
];
703 if (is_deleted (entry
))
704 mark_deleted (nentries
[i
]);
705 else if (!is_empty (entry
))
706 new ((void*) (nentries
+ i
)) value_type (entry
);
708 m_entries
= nentries
;
711 m_size_prime_index
= h
.m_size_prime_index
;
714 template<typename Descriptor
, bool Lazy
,
715 template<typename Type
> class Allocator
>
716 hash_table
<Descriptor
, Lazy
, Allocator
>::~hash_table ()
718 check_complete_insertion ();
720 if (!Lazy
|| m_entries
)
722 for (size_t i
= m_size
- 1; i
< m_size
; i
--)
723 if (!is_empty (m_entries
[i
]) && !is_deleted (m_entries
[i
]))
724 Descriptor::remove (m_entries
[i
]);
727 Allocator
<value_type
> ::data_free (m_entries
);
729 ggc_free (m_entries
);
730 if (m_gather_mem_stats
)
731 hash_table_usage ().release_instance_overhead (this,
735 else if (m_gather_mem_stats
)
736 hash_table_usage ().unregister_descriptor (this);
739 /* This function returns an array of empty hash table elements. */
741 template<typename Descriptor
, bool Lazy
,
742 template<typename Type
> class Allocator
>
743 inline typename hash_table
<Descriptor
, Lazy
, Allocator
>::value_type
*
744 hash_table
<Descriptor
, Lazy
,
745 Allocator
>::alloc_entries (size_t n MEM_STAT_DECL
) const
747 value_type
*nentries
;
749 if (m_gather_mem_stats
)
750 hash_table_usage ().register_instance_overhead (sizeof (value_type
) * n
, this);
753 nentries
= Allocator
<value_type
> ::data_alloc (n
);
755 nentries
= ::ggc_cleared_vec_alloc
<value_type
> (n PASS_MEM_STAT
);
757 gcc_assert (nentries
!= NULL
);
758 if (!Descriptor::empty_zero_p
)
759 for (size_t i
= 0; i
< n
; i
++)
760 mark_empty (nentries
[i
]);
765 /* Similar to find_slot, but without several unwanted side effects:
766 - Does not call equal when it finds an existing entry.
767 - Does not change the count of elements/searches/collisions in the
769 This function also assumes there are no deleted entries in the table.
770 HASH is the hash value for the element to be inserted. */
772 template<typename Descriptor
, bool Lazy
,
773 template<typename Type
> class Allocator
>
774 typename hash_table
<Descriptor
, Lazy
, Allocator
>::value_type
*
775 hash_table
<Descriptor
, Lazy
,
776 Allocator
>::find_empty_slot_for_expand (hashval_t hash
)
778 hashval_t index
= hash_table_mod1 (hash
, m_size_prime_index
);
779 size_t size
= m_size
;
780 value_type
*slot
= m_entries
+ index
;
783 if (is_empty (*slot
))
785 gcc_checking_assert (!is_deleted (*slot
));
787 hash2
= hash_table_mod2 (hash
, m_size_prime_index
);
794 slot
= m_entries
+ index
;
795 if (is_empty (*slot
))
797 gcc_checking_assert (!is_deleted (*slot
));
801 /* Return true if the current table is excessively big for ELTS elements. */
803 template<typename Descriptor
, bool Lazy
,
804 template<typename Type
> class Allocator
>
806 hash_table
<Descriptor
, Lazy
, Allocator
>::too_empty_p (unsigned int elts
)
808 return elts
* 8 < m_size
&& m_size
> 32;
811 /* The following function changes size of memory allocated for the
812 entries and repeatedly inserts the table elements. The occupancy
813 of the table after the call will be about 50%. Naturally the hash
814 table must already exist. Remember also that the place of the
815 table entries is changed. If memory allocation fails, this function
818 template<typename Descriptor
, bool Lazy
,
819 template<typename Type
> class Allocator
>
821 hash_table
<Descriptor
, Lazy
, Allocator
>::expand ()
823 check_complete_insertion ();
825 value_type
*oentries
= m_entries
;
826 unsigned int oindex
= m_size_prime_index
;
827 size_t osize
= size ();
828 value_type
*olimit
= oentries
+ osize
;
829 size_t elts
= elements ();
831 /* Resize only when table after removal of unused elements is either
832 too full or too empty. */
835 if (elts
* 2 > osize
|| too_empty_p (elts
))
837 nindex
= hash_table_higher_prime_index (elts
* 2);
838 nsize
= prime_tab
[nindex
].prime
;
846 value_type
*nentries
= alloc_entries (nsize
);
848 if (m_gather_mem_stats
)
849 hash_table_usage ().release_instance_overhead (this, sizeof (value_type
)
852 m_entries
= nentries
;
854 m_size_prime_index
= nindex
;
855 m_n_elements
-= m_n_deleted
;
858 value_type
*p
= oentries
;
863 if (!is_empty (x
) && !is_deleted (x
))
865 value_type
*q
= find_empty_slot_for_expand (Descriptor::hash (x
));
866 new ((void*) q
) value_type (std::move (x
));
867 /* After the resources of 'x' have been moved to a new object at 'q',
868 we now have to destroy the 'x' object, to end its lifetime. */
877 Allocator
<value_type
> ::data_free (oentries
);
882 /* Implements empty() in cases where it isn't a no-op. */
884 template<typename Descriptor
, bool Lazy
,
885 template<typename Type
> class Allocator
>
887 hash_table
<Descriptor
, Lazy
, Allocator
>::empty_slow ()
889 check_complete_insertion ();
891 size_t size
= m_size
;
893 value_type
*entries
= m_entries
;
895 for (size_t i
= size
- 1; i
< size
; i
--)
896 if (!is_empty (entries
[i
]) && !is_deleted (entries
[i
]))
897 Descriptor::remove (entries
[i
]);
899 /* Instead of clearing megabyte, downsize the table. */
900 if (size
> 1024*1024 / sizeof (value_type
))
901 nsize
= 1024 / sizeof (value_type
);
902 else if (too_empty_p (m_n_elements
))
903 nsize
= m_n_elements
* 2;
907 unsigned int nindex
= hash_table_higher_prime_index (nsize
);
909 nsize
= prime_tab
[nindex
].prime
;
912 Allocator
<value_type
> ::data_free (m_entries
);
914 ggc_free (m_entries
);
916 m_entries
= alloc_entries (nsize
);
918 m_size_prime_index
= nindex
;
920 else if (Descriptor::empty_zero_p
)
921 memset ((void *) entries
, 0, size
* sizeof (value_type
));
923 for (size_t i
= 0; i
< size
; i
++)
924 mark_empty (entries
[i
]);
930 /* This function clears a specified SLOT in a hash table. It is
931 useful when you've already done the lookup and don't want to do it
934 template<typename Descriptor
, bool Lazy
,
935 template<typename Type
> class Allocator
>
937 hash_table
<Descriptor
, Lazy
, Allocator
>::clear_slot (value_type
*slot
)
939 check_complete_insertion ();
941 gcc_checking_assert (!(slot
< m_entries
|| slot
>= m_entries
+ size ()
942 || is_empty (*slot
) || is_deleted (*slot
)));
944 Descriptor::remove (*slot
);
946 mark_deleted (*slot
);
950 /* This function searches for a hash table entry equal to the given
951 COMPARABLE element starting with the given HASH value. It cannot
952 be used to insert or delete an element. */
954 template<typename Descriptor
, bool Lazy
,
955 template<typename Type
> class Allocator
>
956 typename hash_table
<Descriptor
, Lazy
, Allocator
>::value_type
&
957 hash_table
<Descriptor
, Lazy
, Allocator
>
958 ::find_with_hash (const compare_type
&comparable
, hashval_t hash
)
961 size_t size
= m_size
;
962 hashval_t index
= hash_table_mod1 (hash
, m_size_prime_index
);
964 if (Lazy
&& m_entries
== NULL
)
965 m_entries
= alloc_entries (size
);
967 check_complete_insertion ();
970 if (m_sanitize_eq_and_hash
)
971 verify (comparable
, hash
);
974 value_type
*entry
= &m_entries
[index
];
975 if (is_empty (*entry
)
976 || (!is_deleted (*entry
) && Descriptor::equal (*entry
, comparable
)))
979 hashval_t hash2
= hash_table_mod2 (hash
, m_size_prime_index
);
987 entry
= &m_entries
[index
];
988 if (is_empty (*entry
)
989 || (!is_deleted (*entry
) && Descriptor::equal (*entry
, comparable
)))
994 /* This function searches for a hash table slot containing an entry
995 equal to the given COMPARABLE element and starting with the given
996 HASH. To delete an entry, call this with insert=NO_INSERT, then
997 call clear_slot on the slot returned (possibly after doing some
998 checks). To insert an entry, call this with insert=INSERT, then
999 write the value you want into the returned slot. When inserting an
1000 entry, NULL may be returned if memory allocation fails. */
1002 template<typename Descriptor
, bool Lazy
,
1003 template<typename Type
> class Allocator
>
1004 typename hash_table
<Descriptor
, Lazy
, Allocator
>::value_type
*
1005 hash_table
<Descriptor
, Lazy
, Allocator
>
1006 ::find_slot_with_hash (const compare_type
&comparable
, hashval_t hash
,
1007 enum insert_option insert
)
1009 if (Lazy
&& m_entries
== NULL
)
1011 if (insert
== INSERT
)
1012 m_entries
= alloc_entries (m_size
);
1016 if (insert
== INSERT
&& m_size
* 3 <= m_n_elements
* 4)
1019 check_complete_insertion ();
1022 if (m_sanitize_eq_and_hash
)
1023 verify (comparable
, hash
);
1027 value_type
*first_deleted_slot
= NULL
;
1028 hashval_t index
= hash_table_mod1 (hash
, m_size_prime_index
);
1029 hashval_t hash2
= hash_table_mod2 (hash
, m_size_prime_index
);
1030 value_type
*entry
= &m_entries
[index
];
1031 size_t size
= m_size
;
1032 if (is_empty (*entry
))
1034 else if (is_deleted (*entry
))
1035 first_deleted_slot
= &m_entries
[index
];
1036 else if (Descriptor::equal (*entry
, comparable
))
1037 return &m_entries
[index
];
1046 entry
= &m_entries
[index
];
1047 if (is_empty (*entry
))
1049 else if (is_deleted (*entry
))
1051 if (!first_deleted_slot
)
1052 first_deleted_slot
= &m_entries
[index
];
1054 else if (Descriptor::equal (*entry
, comparable
))
1055 return &m_entries
[index
];
1059 if (insert
== NO_INSERT
)
1062 if (first_deleted_slot
)
1065 mark_empty (*first_deleted_slot
);
1066 return check_insert_slot (first_deleted_slot
);
1070 return check_insert_slot (&m_entries
[index
]);
1073 /* Verify that all existing elements in th hash table which are
1074 equal to COMPARABLE have an equal HASH value provided as argument. */
1076 template<typename Descriptor
, bool Lazy
,
1077 template<typename Type
> class Allocator
>
1079 hash_table
<Descriptor
, Lazy
, Allocator
>
1080 ::verify (const compare_type
&comparable
, hashval_t hash
)
1082 for (size_t i
= 0; i
< MIN (hash_table_sanitize_eq_limit
, m_size
); i
++)
1084 value_type
*entry
= &m_entries
[i
];
1085 if (!is_empty (*entry
) && !is_deleted (*entry
)
1086 && hash
!= Descriptor::hash (*entry
)
1087 && Descriptor::equal (*entry
, comparable
))
1088 hashtab_chk_error ();
1092 /* This function deletes an element with the given COMPARABLE value
1093 from hash table starting with the given HASH. If there is no
1094 matching element in the hash table, this function does nothing. */
1096 template<typename Descriptor
, bool Lazy
,
1097 template<typename Type
> class Allocator
>
1099 hash_table
<Descriptor
, Lazy
, Allocator
>
1100 ::remove_elt_with_hash (const compare_type
&comparable
, hashval_t hash
)
1102 check_complete_insertion ();
1104 value_type
*slot
= find_slot_with_hash (comparable
, hash
, NO_INSERT
);
1108 Descriptor::remove (*slot
);
1110 mark_deleted (*slot
);
1114 /* This function scans over the entire hash table calling CALLBACK for
1115 each live entry. If CALLBACK returns false, the iteration stops.
1116 ARGUMENT is passed as CALLBACK's second argument. */
1118 template<typename Descriptor
, bool Lazy
,
1119 template<typename Type
> class Allocator
>
1120 template<typename Argument
,
1122 (typename hash_table
<Descriptor
, Lazy
, Allocator
>::value_type
*slot
,
1125 hash_table
<Descriptor
, Lazy
, Allocator
>::traverse_noresize (Argument argument
)
1127 if (Lazy
&& m_entries
== NULL
)
1130 check_complete_insertion ();
1132 value_type
*slot
= m_entries
;
1133 value_type
*limit
= slot
+ size ();
1137 value_type
&x
= *slot
;
1139 if (!is_empty (x
) && !is_deleted (x
))
1140 if (! Callback (slot
, argument
))
1143 while (++slot
< limit
);
1146 /* Like traverse_noresize, but does resize the table when it is too empty
1147 to improve effectivity of subsequent calls. */
1149 template <typename Descriptor
, bool Lazy
,
1150 template <typename Type
> class Allocator
>
1151 template <typename Argument
,
1153 (typename hash_table
<Descriptor
, Lazy
, Allocator
>::value_type
*slot
,
1156 hash_table
<Descriptor
, Lazy
, Allocator
>::traverse (Argument argument
)
1158 if (too_empty_p (elements ()) && (!Lazy
|| m_entries
))
1161 traverse_noresize
<Argument
, Callback
> (argument
);
1164 /* Slide down the iterator slots until an active entry is found. */
1166 template<typename Descriptor
, bool Lazy
,
1167 template<typename Type
> class Allocator
>
1169 hash_table
<Descriptor
, Lazy
, Allocator
>::iterator::slide ()
1171 for ( ; m_slot
< m_limit
; ++m_slot
)
1173 value_type
&x
= *m_slot
;
1174 if (!is_empty (x
) && !is_deleted (x
))
1181 /* Bump the iterator. */
1183 template<typename Descriptor
, bool Lazy
,
1184 template<typename Type
> class Allocator
>
1185 inline typename hash_table
<Descriptor
, Lazy
, Allocator
>::iterator
&
1186 hash_table
<Descriptor
, Lazy
, Allocator
>::iterator::operator ++ ()
1194 /* Iterate through the elements of hash_table HTAB,
1195 using hash_table <....>::iterator ITER,
1196 storing each element in RESULT, which is of type TYPE. */
1198 #define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \
1199 for ((ITER) = (HTAB).begin (); \
1200 (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \
1203 /* ggc walking routines. */
1205 template<typename E
>
1207 gt_ggc_mx (hash_table
<E
> *h
)
1209 typedef hash_table
<E
> table
;
1211 if (!ggc_test_and_set_mark (h
->m_entries
))
1214 for (size_t i
= 0; i
< h
->m_size
; i
++)
1216 if (table::is_empty (h
->m_entries
[i
])
1217 || table::is_deleted (h
->m_entries
[i
]))
1220 /* Use ggc_maxbe_mx so we don't mark right away for cache tables; we'll
1221 mark in gt_cleare_cache if appropriate. */
1222 E::ggc_maybe_mx (h
->m_entries
[i
]);
1226 template<typename D
>
1228 hashtab_entry_note_pointers (void *obj
, void *h
, gt_pointer_operator op
,
1231 hash_table
<D
> *map
= static_cast<hash_table
<D
> *> (h
);
1232 gcc_checking_assert (map
->m_entries
== obj
);
1233 for (size_t i
= 0; i
< map
->m_size
; i
++)
1235 typedef hash_table
<D
> table
;
1236 if (table::is_empty (map
->m_entries
[i
])
1237 || table::is_deleted (map
->m_entries
[i
]))
1240 D::pch_nx (map
->m_entries
[i
], op
, cookie
);
1244 template<typename D
>
1246 gt_pch_nx (hash_table
<D
> *h
)
1248 h
->check_complete_insertion ();
1250 = gt_pch_note_object (h
->m_entries
, h
, hashtab_entry_note_pointers
<D
>);
1251 gcc_checking_assert (success
);
1252 for (size_t i
= 0; i
< h
->m_size
; i
++)
1254 if (hash_table
<D
>::is_empty (h
->m_entries
[i
])
1255 || hash_table
<D
>::is_deleted (h
->m_entries
[i
]))
1258 D::pch_nx (h
->m_entries
[i
]);
1262 template<typename D
>
1264 gt_pch_nx (hash_table
<D
> *h
, gt_pointer_operator op
, void *cookie
)
1266 op (&h
->m_entries
, NULL
, cookie
);
1269 template<typename H
>
1271 gt_cleare_cache (hash_table
<H
> *h
)
1273 typedef hash_table
<H
> table
;
1277 for (typename
table::iterator iter
= h
->begin (); iter
!= h
->end (); ++iter
)
1278 if (!table::is_empty (*iter
) && !table::is_deleted (*iter
))
1280 int res
= H::keep_cache_entry (*iter
);
1282 h
->clear_slot (&*iter
);
1288 #endif /* TYPED_HASHTAB_H */