243#ifndef TYPED_HASHTAB_H
244#define TYPED_HASHTAB_H
255template<
typename,
typename,
typename>
class hash_map;
256template<
typename,
bool,
typename>
class hash_set;
261template <
typename Type>
271template <
typename Type>
275 return static_cast <Type *
> (xcalloc (
count,
sizeof (Type)));
281template <
typename Type>
285 return ::free (memory);
325 hashval_t t1, t2, t3, t4, q,
r;
327 t1 = ((uint64_t)x *
inv) >> 32;
372template <
typename Descriptor,
bool Lazy =
false,
373 template<
typename Type>
class Allocator =
xcallocator>
381 bool sanitize_eq_and_hash =
true,
382 bool gather_mem_stats = GATHER_STATISTICS,
386 bool sanitize_eq_and_hash =
true,
387 bool gather_mem_stats = GATHER_STATISTICS,
397 new (
table)
hash_table (n,
true, sanitize_eq_and_hash, GATHER_STATISTICS,
446 hashval_t hash,
enum insert_option
insert);
463 template <
typename Argument,
469 template <
typename Argument,
479 m_slot (
slot), m_limit (limit) {}
483 inline iterator &operator ++ ();
517 template<
typename T>
friend void
519 template<
typename T,
typename U,
typename V>
friend void
521 template<
typename T,
typename U>
542 return Descriptor::is_deleted (v);
547 return Descriptor::is_empty (v);
552 Descriptor::mark_deleted (v);
562 Descriptor::mark_empty (v);
569 if (!m_inserting_slot)
576 m_inserting_slot =
NULL;
587 m_inserting_slot = ret;
644template<
typename Descriptor,
bool Lazy,
645 template<
typename Type>
class Allocator>
647 bool sanitize_eq_and_hash,
648 bool gather_mem_stats
653 m_inserting_slot (0),
655 m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0),
656 m_ggc (ggc), m_sanitize_eq_and_hash (sanitize_eq_and_hash)
658 , m_gather_mem_stats (gather_mem_stats)
661 unsigned int size_prime_index;
678template<
typename Descriptor,
bool Lazy,
679 template<
typename Type>
class Allocator>
682 bool sanitize_eq_and_hash,
683 bool gather_mem_stats
688 m_inserting_slot (0),
690 m_n_elements (h.m_n_elements), m_n_deleted (h.m_n_deleted),
691 m_searches (0), m_collisions (0), m_ggc (ggc),
692 m_sanitize_eq_and_hash (sanitize_eq_and_hash)
694 , m_gather_mem_stats (gather_mem_stats)
709 value_type *nentries = alloc_entries (size PASS_MEM_STAT);
710 for (size_t i = 0; i < size; ++i)
712 value_type &entry = h.m_entries[i];
713 if (is_empty (entry))
715 else if (is_deleted (entry))
716 mark_deleted (nentries[i]);
718 new ((void*) (nentries + i)) value_type (entry);
723 m_size_prime_index = h.m_size_prime_index;
726template<
typename Descriptor,
bool Lazy,
727 template<
typename Type>
class Allocator>
730 check_complete_insertion ();
732 if (!Lazy || m_entries)
734 for (
size_t i = m_size - 1;
i < m_size;
i--)
735 if (!
is_empty (m_entries[
i]) && !is_deleted (m_entries[
i]))
736 Descriptor::remove (m_entries[
i]);
739 Allocator <value_type> ::data_free (m_entries);
742 if (m_gather_mem_stats)
747 else if (m_gather_mem_stats)
753template<
typename Descriptor,
bool Lazy,
754 template<
typename Type>
class Allocator>
761 if (m_gather_mem_stats)
765 nentries = Allocator <value_type> ::data_alloc (n);
770 if (!Descriptor::empty_zero_p)
771 for (
size_t i = 0;
i < n;
i++)
772 mark_empty (nentries[
i]);
784template<
typename Descriptor,
bool Lazy,
785 template<
typename Type>
class Allocator>
788 Allocator>::find_empty_slot_for_expand (hashval_t hash)
791 size_t size = m_size;
806 slot = m_entries + index;
815template<
typename Descriptor,
bool Lazy,
816 template<
typename Type>
class Allocator>
820 return elts * 8 < m_size && m_size > 32;
830template<
typename Descriptor,
bool Lazy,
831 template<
typename Type>
class Allocator>
835 check_complete_insertion ();
838 unsigned int oindex = m_size_prime_index;
839 size_t osize = size ();
841 size_t elts = elements ();
847 if (elts * 2 > osize || too_empty_p (elts))
860 if (m_gather_mem_stats)
864 size_t n_deleted = m_n_deleted;
866 m_entries = nentries;
868 m_size_prime_index = nindex;
869 m_n_elements -= m_n_deleted;
872 size_t n_elements = m_n_elements;
881 else if (is_deleted (x))
886 value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
900 Allocator <value_type> ::data_free (oentries);
907template<
typename Descriptor,
bool Lazy,
908 template<
typename Type>
class Allocator>
912 check_complete_insertion ();
914 size_t size = m_size;
918 for (
size_t i = size - 1;
i < size;
i--)
919 if (!
is_empty (entries[
i]) && !is_deleted (entries[
i]))
920 Descriptor::remove (entries[
i]);
925 else if (too_empty_p (m_n_elements))
926 nsize = m_n_elements * 2;
935 Allocator <value_type> ::data_free (m_entries);
939 m_entries = alloc_entries (nsize);
941 m_size_prime_index = nindex;
943 else if (Descriptor::empty_zero_p)
944 memset ((
void *) entries, 0, size *
sizeof (
value_type));
946 for (
size_t i = 0;
i < size;
i++)
947 mark_empty (entries[
i]);
957template<
typename Descriptor,
bool Lazy,
958 template<
typename Type>
class Allocator>
962 check_complete_insertion ();
967 Descriptor::remove (*
slot);
969 mark_deleted (*
slot);
977template<
typename Descriptor,
bool Lazy,
978 template<
typename Type>
class Allocator>
984 size_t size = m_size;
987 if (Lazy && m_entries ==
NULL)
988 m_entries = alloc_entries (size);
990 check_complete_insertion ();
993 if (m_sanitize_eq_and_hash)
994 verify (comparable, hash);
999 || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
1010 entry = &m_entries[index];
1012 || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
1025template<
typename Descriptor,
bool Lazy,
1026 template<
typename Type>
class Allocator>
1030 enum insert_option
insert)
1032 if (Lazy && m_entries ==
NULL)
1035 m_entries = alloc_entries (m_size);
1039 if (
insert == INSERT && m_size * 3 <= m_n_elements * 4)
1042 check_complete_insertion ();
1045 if (m_sanitize_eq_and_hash)
1046 verify (comparable, hash);
1054 size_t size = m_size;
1057 else if (is_deleted (*entry))
1058 first_deleted_slot = &m_entries[index];
1059 else if (Descriptor::equal (*entry, comparable))
1060 return &m_entries[index];
1069 entry = &m_entries[index];
1072 else if (is_deleted (*entry))
1074 if (!first_deleted_slot)
1075 first_deleted_slot = &m_entries[index];
1077 else if (Descriptor::equal (*entry, comparable))
1078 return &m_entries[index];
1085 if (first_deleted_slot)
1088 mark_empty (*first_deleted_slot);
1089 return check_insert_slot (first_deleted_slot);
1093 return check_insert_slot (&m_entries[index]);
1100template<
typename Descriptor,
bool Lazy,
1101 template<
typename Type>
class Allocator>
1106 size_t n_elements = m_n_elements;
1107 size_t n_deleted = m_n_deleted;
1114 if (is_deleted (*entry))
1116 else if (hash != Descriptor::hash (*entry)
1117 && Descriptor::equal (*entry, comparable))
1129template<
typename Descriptor,
bool Lazy,
1130 template<
typename Type>
class Allocator>
1135 check_complete_insertion ();
1137 value_type *
slot = find_slot_with_hash (comparable, hash, NO_INSERT);
1141 Descriptor::remove (*
slot);
1143 mark_deleted (*
slot);
1151template<
typename Descriptor,
bool Lazy,
1152 template<
typename Type>
class Allocator>
1153template<
typename Argument,
1160 if (Lazy && m_entries ==
NULL)
1163 check_complete_insertion ();
1172 if (!
is_empty (x) && !is_deleted (x))
1173 if (! Callback (
slot, argument))
1176 while (++
slot < limit);
1182template <
typename Descriptor,
bool Lazy,
1183 template <
typename Type>
class Allocator>
1184template <
typename Argument,
1191 if (too_empty_p (elements ()) && (!Lazy || m_entries))
1194 traverse_noresize <Argument, Callback> (argument);
1199template<
typename Descriptor,
bool Lazy,
1200 template<
typename Type>
class Allocator>
1216template<
typename Descriptor,
bool Lazy,
1217 template<
typename Type>
class Allocator>
1231#define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \
1232 for ((ITER) = (HTAB).begin (); \
1233 (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \
1266 for (
size_t i = 0;
i <
map->m_size;
i++)
1269 if (table::is_empty (
map->m_entries[
i])
1270 || table::is_deleted (
map->m_entries[
i]))
1273 D::pch_nx (
map->m_entries[
i], op, cookie);
1310 for (
typename table::iterator iter = h->
begin (); iter != h->
end (); ++iter)
1311 if (!table::is_empty (*iter) && !table::is_deleted (*iter))
1313 int res = H::keep_cache_entry (*iter);
Definition tree-ssa-alias.h:77
Definition hash-table.h:474
value_type * m_slot
Definition hash-table.h:490
void slide()
Definition hash-table.h:1202
iterator()
Definition hash-table.h:476
value_type * m_limit
Definition hash-table.h:491
iterator(value_type *slot, value_type *limit)
Definition hash-table.h:478
iterator & operator++()
Definition hash-table.h:1219
Definition hash-table.h:375
bool m_ggc
Definition hash-table.h:620
static bool is_empty(value_type &v)
Definition hash-table.h:545
void remove_elt_with_hash(const compare_type &, hashval_t)
Definition hash-table.h:1133
void traverse_noresize(Argument argument)
Definition hash-table.h:1158
size_t m_n_deleted
Definition hash-table.h:605
Descriptor::compare_type compare_type
Definition hash-table.h:377
size_t m_size
Definition hash-table.h:599
static const bool m_gather_mem_stats
Definition hash-table.h:629
void empty()
Definition hash-table.h:412
friend void gt_cleare_cache(hash_table< T > *)
value_type & find_with_hash(const compare_type &, hashval_t)
Definition hash-table.h:981
value_type * find_slot_with_hash(const compare_type &comparable, hashval_t hash, enum insert_option insert)
Definition hash-table.h:1029
void traverse(Argument argument)
Definition hash-table.h:1189
size_t size() const
Definition hash-table.h:403
friend void gt_pch_nx(hash_table< T > *, gt_pointer_operator, void *)
static void mark_deleted(value_type &v)
Definition hash-table.h:550
value_type & find(const value_type &value)
Definition hash-table.h:428
void operator=(hash_table &)
void remove_elt(const value_type &value)
Definition hash-table.h:455
Descriptor::value_type value_type
Definition hash-table.h:376
iterator end() const
Definition hash-table.h:504
hash_table(const hash_table &, bool ggc=false, bool sanitize_eq_and_hash=true, bool gather_mem_stats=GATHER_STATISTICS, mem_alloc_origin origin=HASH_TABLE_ORIGIN CXX_MEM_STAT_INFO)
Definition hash-table.h:680
friend void gt_pch_nx(hash_table< T > *)
bool is_empty() const
Definition hash-table.h:415
double collisions() const
Definition hash-table.h:506
size_t m_n_elements
Definition hash-table.h:602
void check_complete_insertion() const
Definition hash-table.h:566
unsigned int m_size_prime_index
Definition hash-table.h:617
void expand()
Definition hash-table.h:833
iterator begin() const
Definition hash-table.h:494
value_type * find_empty_slot_for_expand(hashval_t)
Definition hash-table.h:788
friend void gt_ggc_mx(hash_table< T > *)
hash_table(size_t, bool ggc=false, bool sanitize_eq_and_hash=true, bool gather_mem_stats=GATHER_STATISTICS, mem_alloc_origin origin=HASH_TABLE_ORIGIN CXX_MEM_STAT_INFO)
Definition hash-table.h:646
size_t elements() const
Definition hash-table.h:406
bool too_empty_p(unsigned int)
Definition hash-table.h:818
static void mark_empty(value_type &v)
Definition hash-table.h:560
value_type * m_entries
Definition hash-table.h:597
friend void gt_pch_nx(hash_map< T, U, V > *, gt_pointer_operator, void *)
value_type * check_insert_slot(value_type *ret)
Definition hash-table.h:583
bool m_sanitize_eq_and_hash
Definition hash-table.h:623
void empty_slow()
Definition hash-table.h:910
value_type * alloc_entries(size_t n CXX_MEM_STAT_INFO) const
Definition hash-table.h:757
void verify(const compare_type &comparable, hashval_t hash)
Definition hash-table.h:1104
static hash_table * create_ggc(size_t n, bool sanitize_eq_and_hash=true CXX_MEM_STAT_INFO)
Definition hash-table.h:394
unsigned int m_collisions
Definition hash-table.h:613
static bool is_deleted(value_type &v)
Definition hash-table.h:535
unsigned int m_searches
Definition hash-table.h:609
value_type * find_slot(const value_type &value, insert_option insert)
Definition hash-table.h:433
void clear_slot(value_type *)
Definition hash-table.h:960
friend void hashtab_entry_note_pointers(void *, void *, gt_pointer_operator, void *)
Definition hash-table.h:1261
friend void gt_pch_nx(hash_set< T, false, U > *, gt_pointer_operator, void *)
size_t elements_with_deleted() const
Definition hash-table.h:409
~hash_table()
Definition hash-table.h:728
Definition tree-ssa-loop-im.cc:119
Definition mem-stats.h:278
Definition mem-stats.h:128
Definition lra-spills.cc:101
void(* gt_pointer_operator)(void *, void *, void *)
Definition coretypes.h:472
static struct table_elt * table[HASH_SIZE]
Definition cse.cc:470
static unsigned int count[debug_counter_number_of_counters]
Definition dbgcnt.cc:50
static struct string2counter_map map[debug_counter_number_of_counters]
Definition dbgcnt.cc:39
void ATTRIBUTE_NORETURN
Definition diagnostic-core.h:93
bool operator!=(const nowarn_spec_t &lhs, const nowarn_spec_t &rhs)
Definition diagnostic-spec.h:139
#define CHAR_BIT
Definition genautomata.cc:120
void ggc_free(void *)
Definition genmatch.cc:42
int gt_pch_note_object(void *obj, void *note_ptr_cookie, gt_note_pointers note_ptr_fn, size_t length_override)
Definition ggc-common.cc:267
unsigned int shift
Definition ggc-page.cc:233
#define ggc_test_and_set_mark(EXPR)
Definition ggc.h:81
T * ggc_alloc(ALONE_CXX_MEM_STAT_INFO)
Definition ggc.h:184
T * ggc_cleared_vec_alloc(size_t c CXX_MEM_STAT_INFO)
Definition ggc.h:233
void dump_hash_table_loc_statistics(void)
Definition hash-table.cc:116
ATTRIBUTE_NORETURN ATTRIBUTE_COLD void hashtab_chk_error()
Definition hash-table.cc:132
hashval_t mul_mod(hashval_t x, hashval_t y, hashval_t inv, int shift)
Definition hash-table.h:323
unsigned int hash_table_higher_prime_index(unsigned long n) ATTRIBUTE_PURE
Definition hash-table.cc:84
hashval_t hash_table_mod1(hashval_t hash, unsigned int index)
Definition hash-table.h:340
struct prime_ent const prime_tab[]
Definition hash-table.cc:43
hashval_t hash_table_mod2(hashval_t hash, unsigned int index)
Definition hash-table.h:350
mem_alloc_description< mem_usage > & hash_table_usage(void)
Definition hash-table.cc:109
unsigned int hash_table_sanitize_eq_limit
Definition hash-table.cc:78
static bool is_empty(queue_type *queue_list)
Definition mcf.cc:742
mem_alloc_origin
Definition mem-stats-traits.h:26
@ HASH_TABLE_ORIGIN
Definition mem-stats-traits.h:27
poly_int< N, C > r
Definition poly-int.h:774
if(N >=2) for(unsigned int i
i
Definition poly-int.h:776
#define PASS_MEM_STAT
Definition statistics.h:54
#define MEM_STAT_DECL
Definition statistics.h:52
#define FINAL_PASS_MEM_STAT
Definition statistics.h:55
#define CXX_MEM_STAT_INFO
Definition statistics.h:58
Definition hash-table.h:292
hashval_t inv_m2
Definition hash-table.h:295
hashval_t prime
Definition hash-table.h:293
hashval_t inv
Definition hash-table.h:294
hashval_t shift
Definition hash-table.h:296
Definition hash-table.h:263
static Type * data_alloc(size_t count)
Definition hash-table.h:273
static void data_free(Type *memory)
Definition hash-table.h:283
#define NULL
Definition system.h:50
#define gcc_assert(EXPR)
Definition system.h:821
#define gcc_unreachable()
Definition system.h:848
#define MIN(X, Y)
Definition system.h:392
#define gcc_checking_assert(EXPR)
Definition system.h:828
static void insert(void)
Definition tree-ssa-pre.cc:3800
const T2 & y
Definition wide-int.h:3870