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>
281template <
typename Type>
285 return ::free (memory);
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);
655 m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (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),
697 h.check_complete_insertion ();
699 size_t size =
h.m_size;
710 for (
size_t i = 0;
i <
size; ++
i)
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]);
742 if (m_gather_mem_stats)
747 else if (m_gather_mem_stats)
761 if (m_gather_mem_stats)
770 if (!Descriptor::empty_zero_p)
771 for (
size_t i = 0;
i < n;
i++)
791 size_t size = m_size;
806 slot = m_entries + index;
820 return elts * 8 < m_size && m_size > 32;
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)
868 m_size_prime_index =
nindex;
869 m_n_elements -= m_n_deleted;
881 else if (is_deleted (x))
886 value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
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;
939 m_entries = alloc_entries (
nsize);
941 m_size_prime_index =
nindex;
943 else if (Descriptor::empty_zero_p)
946 for (
size_t i = 0;
i < size;
i++)
947 mark_empty (entries[
i]);
962 check_complete_insertion ();
967 Descriptor::remove (*
slot);
969 mark_deleted (*
slot);
984 size_t size = m_size;
988 m_entries = alloc_entries (size);
990 check_complete_insertion ();
993 if (m_sanitize_eq_and_hash)
999 || (!is_deleted (*entry) && Descriptor::equal (*entry,
comparable)))
1010 entry = &m_entries[index];
1012 || (!is_deleted (*entry) && Descriptor::equal (*entry,
comparable)))
1026 template<
typename Type>
class Allocator>
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)
1054 size_t size = m_size;
1057 else if (is_deleted (*entry))
1059 else if (Descriptor::equal (*entry,
comparable))
1060 return &m_entries[index];
1069 entry = &m_entries[index];
1072 else if (is_deleted (*entry))
1077 else if (Descriptor::equal (*entry,
comparable))
1078 return &m_entries[index];
1093 return check_insert_slot (&m_entries[index]);
1101 template<
typename Type>
class Allocator>
1114 if (is_deleted (*entry))
1116 else if (hash != Descriptor::hash (*entry)
1130 template<
typename Type>
class Allocator>
1135 check_complete_insertion ();
1141 Descriptor::remove (*
slot);
1143 mark_deleted (*
slot);
1152 template<
typename Type>
class Allocator>
1163 check_complete_insertion ();
1172 if (!
is_empty (x) && !is_deleted (x))
1176 while (++
slot < limit);
1183 template <
typename Type>
class Allocator>
1191 if (too_empty_p (elements ()) && (!
Lazy || m_entries))
1200 template<
typename Type>
class Allocator>
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; \
1247 for (
size_t i = 0;
i <
h->m_size;
i++)
1249 if (table::is_empty (
h->m_entries[
i])
1250 || table::is_deleted (
h->m_entries[
i]))
1255 E::ggc_maybe_mx (
h->m_entries[
i]);
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]))
1281 h->check_complete_insertion ();
1285 for (
size_t i = 0;
i <
h->m_size;
i++)
1291 D::pch_nx (
h->m_entries[
i]);
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);
1315 h->clear_slot (&*iter);
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
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 &)
Descriptor::value_type value_type
Definition hash-table.h:376
void remove_elt(const value_type &value)
Definition hash-table.h:455
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
Descriptor::compare_type compare_type
Definition hash-table.h:377
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
friend void hashtab_entry_note_pointers(void *, void *, gt_pointer_operator, void *)
Definition hash-table.h:1261
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 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 mem-stats.h:278
Definition mem-stats.h:128
Definition lra-spills.cc:101
void(* gt_pointer_operator)(void *, void *, void *)
Definition coretypes.h:462
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:72
bool operator!=(const nowarn_spec_t &lhs, const nowarn_spec_t &rhs)
Definition diagnostic-spec.h:132
#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
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:770
if(N >=2) for(unsigned int i
i
Definition poly-int.h:772
#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:3796
const T2 & y
Definition wide-int.h:3870