/* A type-safe hash table template.
- Copyright (C) 2012-2016 Free Software Foundation, Inc.
+ Copyright (C) 2012-2019 Free Software Foundation, Inc.
Contributed by Lawrence Crowl <crowl@google.com>
This file is part of GCC.
See hash_table for details. The interface is very similar to libiberty's
htab_t.
+ If a hash table is used only in some rare cases, it is possible
+ to construct the hash_table lazily before first use. This is done
+ through:
+
+ hash_table <some_type_hasher, true> some_type_hash_table;
+
+ which will cause whatever methods actually need the allocated entries
+ array to allocate it later.
+
EASY DESCRIPTORS FOR POINTERS
#include "hash-map-traits.h"
template<typename, typename, typename> class hash_map;
-template<typename, typename> class hash_set;
+template<typename, bool, typename> class hash_set;
/* The ordinary memory allocator. */
/* FIXME (crowl): This allocator may be extracted for wider sharing later. */
extern struct prime_ent const prime_tab[];
+/* Limit number of comparisons when calling hash_table<>::verify. */
+extern unsigned int hash_table_sanitize_eq_limit;
/* Functions for computing hash table indexes. */
{
const struct prime_ent *p = &prime_tab[index];
gcc_checking_assert (sizeof (hashval_t) * CHAR_BIT <= 32);
- return mul_mod (hash, p->prime, p->inv, p->shift);
+ return mul_mod (hash, p->prime, p->inv, p->shift);
}
/* Compute the secondary table index for HASH given current prime index. */
hash table code.
*/
-template <typename Descriptor,
- template<typename Type> class Allocator = xcallocator>
+template <typename Descriptor, bool Lazy = false,
+ template<typename Type> class Allocator = xcallocator>
class hash_table
{
typedef typename Descriptor::value_type value_type;
public:
explicit 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);
explicit 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);
/* Create a hash_table in gc memory. */
static hash_table *
- create_ggc (size_t n CXX_MEM_STAT_INFO)
+ create_ggc (size_t n, bool sanitize_eq_and_hash = true CXX_MEM_STAT_INFO)
{
hash_table *table = ggc_alloc<hash_table> ();
- new (table) hash_table (n, true, GATHER_STATISTICS,
+ new (table) hash_table (n, true, sanitize_eq_and_hash, GATHER_STATISTICS,
HASH_TABLE_ORIGIN PASS_MEM_STAT);
return table;
}
/* This function clears all entries in this hash table. */
void empty () { if (elements ()) empty_slow (); }
+ /* Return true when there are no elements in this hash table. */
+ bool is_empty () const { return elements () == 0; }
+
/* This function clears a specified SLOT in a hash table. It is
useful when you've already done the lookup and don't want to do it
again. */
write the value you want into the returned slot. When inserting an
entry, NULL may be returned if memory allocation fails. */
value_type *find_slot_with_hash (const compare_type &comparable,
- hashval_t hash, enum insert_option insert);
+ hashval_t hash, enum insert_option insert);
/* This function deletes an element with the given COMPARABLE value
from hash table starting with the given HASH. If there is no
iterator begin () const
{
+ if (Lazy && m_entries == NULL)
+ return iterator ();
iterator iter (m_entries, m_entries + m_size);
iter.slide ();
return iter;
hashtab_entry_note_pointers (void *, void *, gt_pointer_operator, void *);
template<typename T, typename U, typename V> friend void
gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
- template<typename T, typename U> friend void gt_pch_nx (hash_set<T, U> *,
- gt_pointer_operator,
- void *);
+ template<typename T, typename U>
+ friend void gt_pch_nx (hash_set<T, false, U> *, gt_pointer_operator, void *);
template<typename T> friend void gt_pch_nx (hash_table<T> *,
gt_pointer_operator, void *);
value_type *alloc_entries (size_t n CXX_MEM_STAT_INFO) const;
value_type *find_empty_slot_for_expand (hashval_t);
+ void verify (const compare_type &comparable, hashval_t hash);
+ bool too_empty_p (unsigned int);
void expand ();
static bool is_deleted (value_type &v)
{
/* if m_entries is stored in ggc memory. */
bool m_ggc;
+ /* True if the table should be sanitized for equal and hash functions. */
+ bool m_sanitize_eq_and_hash;
+
/* If we should gather memory statistics for the table. */
+#if GATHER_STATISTICS
bool m_gather_mem_stats;
+#else
+ static const bool m_gather_mem_stats = false;
+#endif
};
/* As mem-stats.h heavily utilizes hash maps (hash tables), we have to include
#include "mem-stats.h"
#include "hash-map.h"
-extern mem_alloc_description<mem_usage> hash_table_usage;
+extern mem_alloc_description<mem_usage>& hash_table_usage (void);
/* Support function for statistics. */
extern void dump_hash_table_loc_statistics (void);
-template<typename Descriptor, template<typename Type> class Allocator>
-hash_table<Descriptor, Allocator>::hash_table (size_t size, bool ggc, bool
- gather_mem_stats,
- mem_alloc_origin origin
- MEM_STAT_DECL) :
+template<typename Descriptor, bool Lazy,
+ template<typename Type> class Allocator>
+hash_table<Descriptor, Lazy, Allocator>::hash_table (size_t size, bool ggc,
+ bool sanitize_eq_and_hash,
+ bool gather_mem_stats
+ ATTRIBUTE_UNUSED,
+ mem_alloc_origin origin
+ MEM_STAT_DECL) :
m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0),
- m_ggc (ggc), m_gather_mem_stats (gather_mem_stats)
+ m_ggc (ggc), m_sanitize_eq_and_hash (sanitize_eq_and_hash)
+#if GATHER_STATISTICS
+ , m_gather_mem_stats (gather_mem_stats)
+#endif
{
unsigned int size_prime_index;
size = prime_tab[size_prime_index].prime;
if (m_gather_mem_stats)
- hash_table_usage.register_descriptor (this, origin, ggc
- FINAL_PASS_MEM_STAT);
+ hash_table_usage ().register_descriptor (this, origin, ggc
+ FINAL_PASS_MEM_STAT);
- m_entries = alloc_entries (size PASS_MEM_STAT);
+ if (Lazy)
+ m_entries = NULL;
+ else
+ m_entries = alloc_entries (size PASS_MEM_STAT);
m_size = size;
m_size_prime_index = size_prime_index;
}
-template<typename Descriptor, template<typename Type> class Allocator>
-hash_table<Descriptor, Allocator>::hash_table (const hash_table &h, bool ggc,
- bool gather_mem_stats,
- mem_alloc_origin origin
- MEM_STAT_DECL) :
+template<typename Descriptor, bool Lazy,
+ template<typename Type> class Allocator>
+hash_table<Descriptor, Lazy, Allocator>::hash_table (const hash_table &h,
+ bool ggc,
+ bool sanitize_eq_and_hash,
+ bool gather_mem_stats
+ ATTRIBUTE_UNUSED,
+ mem_alloc_origin origin
+ MEM_STAT_DECL) :
m_n_elements (h.m_n_elements), m_n_deleted (h.m_n_deleted),
m_searches (0), m_collisions (0), m_ggc (ggc),
- m_gather_mem_stats (gather_mem_stats)
+ m_sanitize_eq_and_hash (sanitize_eq_and_hash)
+#if GATHER_STATISTICS
+ , m_gather_mem_stats (gather_mem_stats)
+#endif
{
size_t size = h.m_size;
if (m_gather_mem_stats)
- hash_table_usage.register_descriptor (this, origin, ggc
+ hash_table_usage ().register_descriptor (this, origin, ggc
FINAL_PASS_MEM_STAT);
- value_type *nentries = alloc_entries (size PASS_MEM_STAT);
- for (size_t i = 0; i < size; ++i)
+ if (Lazy && h.m_entries == NULL)
+ m_entries = NULL;
+ else
{
- value_type &entry = h.m_entries[i];
- if (is_deleted (entry))
- mark_deleted (nentries[i]);
- else if (!is_empty (entry))
- nentries[i] = entry;
+ value_type *nentries = alloc_entries (size PASS_MEM_STAT);
+ for (size_t i = 0; i < size; ++i)
+ {
+ value_type &entry = h.m_entries[i];
+ if (is_deleted (entry))
+ mark_deleted (nentries[i]);
+ else if (!is_empty (entry))
+ nentries[i] = entry;
+ }
+ m_entries = nentries;
}
- m_entries = nentries;
m_size = size;
m_size_prime_index = h.m_size_prime_index;
}
-template<typename Descriptor, template<typename Type> class Allocator>
-hash_table<Descriptor, Allocator>::~hash_table ()
+template<typename Descriptor, bool Lazy,
+ template<typename Type> class Allocator>
+hash_table<Descriptor, Lazy, Allocator>::~hash_table ()
{
- for (size_t i = m_size - 1; i < m_size; i--)
- if (!is_empty (m_entries[i]) && !is_deleted (m_entries[i]))
- Descriptor::remove (m_entries[i]);
-
- if (!m_ggc)
- Allocator <value_type> ::data_free (m_entries);
- else
- ggc_free (m_entries);
+ if (!Lazy || m_entries)
+ {
+ for (size_t i = m_size - 1; i < m_size; i--)
+ if (!is_empty (m_entries[i]) && !is_deleted (m_entries[i]))
+ Descriptor::remove (m_entries[i]);
- if (m_gather_mem_stats)
- hash_table_usage.release_instance_overhead (this,
- sizeof (value_type) * m_size,
- true);
+ if (!m_ggc)
+ Allocator <value_type> ::data_free (m_entries);
+ else
+ ggc_free (m_entries);
+ if (m_gather_mem_stats)
+ hash_table_usage ().release_instance_overhead (this,
+ sizeof (value_type)
+ * m_size, true);
+ }
+ else if (m_gather_mem_stats)
+ hash_table_usage ().unregister_descriptor (this);
}
/* This function returns an array of empty hash table elements. */
-template<typename Descriptor, template<typename Type> class Allocator>
-inline typename hash_table<Descriptor, Allocator>::value_type *
-hash_table<Descriptor, Allocator>::alloc_entries (size_t n MEM_STAT_DECL) const
+template<typename Descriptor, bool Lazy,
+ template<typename Type> class Allocator>
+inline typename hash_table<Descriptor, Lazy, Allocator>::value_type *
+hash_table<Descriptor, Lazy,
+ Allocator>::alloc_entries (size_t n MEM_STAT_DECL) const
{
value_type *nentries;
if (m_gather_mem_stats)
- hash_table_usage.register_instance_overhead (sizeof (value_type) * n, this);
+ hash_table_usage ().register_instance_overhead (sizeof (value_type) * n, this);
if (!m_ggc)
nentries = Allocator <value_type> ::data_alloc (n);
This function also assumes there are no deleted entries in the table.
HASH is the hash value for the element to be inserted. */
-template<typename Descriptor, template<typename Type> class Allocator>
-typename hash_table<Descriptor, Allocator>::value_type *
-hash_table<Descriptor, Allocator>::find_empty_slot_for_expand (hashval_t hash)
+template<typename Descriptor, bool Lazy,
+ template<typename Type> class Allocator>
+typename hash_table<Descriptor, Lazy, Allocator>::value_type *
+hash_table<Descriptor, Lazy,
+ Allocator>::find_empty_slot_for_expand (hashval_t hash)
{
hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
size_t size = m_size;
}
}
+/* Return true if the current table is excessively big for ELTS elements. */
+
+template<typename Descriptor, bool Lazy,
+ template<typename Type> class Allocator>
+inline bool
+hash_table<Descriptor, Lazy, Allocator>::too_empty_p (unsigned int elts)
+{
+ return elts * 8 < m_size && m_size > 32;
+}
+
/* The following function changes size of memory allocated for the
entries and repeatedly inserts the table elements. The occupancy
of the table after the call will be about 50%. Naturally the hash
table entries is changed. If memory allocation fails, this function
will abort. */
-template<typename Descriptor, template<typename Type> class Allocator>
+template<typename Descriptor, bool Lazy,
+ template<typename Type> class Allocator>
void
-hash_table<Descriptor, Allocator>::expand ()
+hash_table<Descriptor, Lazy, Allocator>::expand ()
{
value_type *oentries = m_entries;
unsigned int oindex = m_size_prime_index;
too full or too empty. */
unsigned int nindex;
size_t nsize;
- if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
+ if (elts * 2 > osize || too_empty_p (elts))
{
nindex = hash_table_higher_prime_index (elts * 2);
nsize = prime_tab[nindex].prime;
value_type *nentries = alloc_entries (nsize);
if (m_gather_mem_stats)
- hash_table_usage.release_instance_overhead (this, sizeof (value_type)
+ hash_table_usage ().release_instance_overhead (this, sizeof (value_type)
* osize);
m_entries = nentries;
/* Implements empty() in cases where it isn't a no-op. */
-template<typename Descriptor, template<typename Type> class Allocator>
+template<typename Descriptor, bool Lazy,
+ template<typename Type> class Allocator>
void
-hash_table<Descriptor, Allocator>::empty_slow ()
+hash_table<Descriptor, Lazy, Allocator>::empty_slow ()
{
size_t size = m_size;
+ size_t nsize = size;
value_type *entries = m_entries;
int i;
Descriptor::remove (entries[i]);
/* Instead of clearing megabyte, downsize the table. */
- if (size > 1024*1024 / sizeof (PTR))
+ if (size > 1024*1024 / sizeof (value_type))
+ nsize = 1024 / sizeof (value_type);
+ else if (too_empty_p (m_n_elements))
+ nsize = m_n_elements * 2;
+
+ if (nsize != size)
{
- int nindex = hash_table_higher_prime_index (1024 / sizeof (PTR));
+ int nindex = hash_table_higher_prime_index (nsize);
int nsize = prime_tab[nindex].prime;
if (!m_ggc)
m_size_prime_index = nindex;
}
else
- memset (entries, 0, size * sizeof (value_type));
+ {
+#ifndef BROKEN_VALUE_INITIALIZATION
+ for ( ; size; ++entries, --size)
+ *entries = value_type ();
+#else
+ memset (entries, 0, size * sizeof (value_type));
+#endif
+ }
m_n_deleted = 0;
m_n_elements = 0;
}
useful when you've already done the lookup and don't want to do it
again. */
-template<typename Descriptor, template<typename Type> class Allocator>
+template<typename Descriptor, bool Lazy,
+ template<typename Type> class Allocator>
void
-hash_table<Descriptor, Allocator>::clear_slot (value_type *slot)
+hash_table<Descriptor, Lazy, Allocator>::clear_slot (value_type *slot)
{
gcc_checking_assert (!(slot < m_entries || slot >= m_entries + size ()
|| is_empty (*slot) || is_deleted (*slot)));
COMPARABLE element starting with the given HASH value. It cannot
be used to insert or delete an element. */
-template<typename Descriptor, template<typename Type> class Allocator>
-typename hash_table<Descriptor, Allocator>::value_type &
-hash_table<Descriptor, Allocator>
+template<typename Descriptor, bool Lazy,
+ template<typename Type> class Allocator>
+typename hash_table<Descriptor, Lazy, Allocator>::value_type &
+hash_table<Descriptor, Lazy, Allocator>
::find_with_hash (const compare_type &comparable, hashval_t hash)
{
m_searches++;
size_t size = m_size;
hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
+ if (Lazy && m_entries == NULL)
+ m_entries = alloc_entries (size);
value_type *entry = &m_entries[index];
if (is_empty (*entry)
|| (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
entry = &m_entries[index];
if (is_empty (*entry)
|| (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
- return *entry;
+ {
+#if CHECKING_P
+ if (m_sanitize_eq_and_hash)
+ verify (comparable, hash);
+#endif
+ return *entry;
+ }
}
}
write the value you want into the returned slot. When inserting an
entry, NULL may be returned if memory allocation fails. */
-template<typename Descriptor, template<typename Type> class Allocator>
-typename hash_table<Descriptor, Allocator>::value_type *
-hash_table<Descriptor, Allocator>
+template<typename Descriptor, bool Lazy,
+ template<typename Type> class Allocator>
+typename hash_table<Descriptor, Lazy, Allocator>::value_type *
+hash_table<Descriptor, Lazy, Allocator>
::find_slot_with_hash (const compare_type &comparable, hashval_t hash,
enum insert_option insert)
{
+ if (Lazy && m_entries == NULL)
+ {
+ if (insert == INSERT)
+ m_entries = alloc_entries (m_size);
+ else
+ return NULL;
+ }
if (insert == INSERT && m_size * 3 <= m_n_elements * 4)
expand ();
- m_searches++;
+#if CHECKING_P
+ if (m_sanitize_eq_and_hash)
+ verify (comparable, hash);
+#endif
+ m_searches++;
value_type *first_deleted_slot = NULL;
hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
return &m_entries[index];
}
+/* Report a hash table checking error. */
+
+ATTRIBUTE_NORETURN ATTRIBUTE_COLD
+static void
+hashtab_chk_error ()
+{
+ fprintf (stderr, "hash table checking failed: "
+ "equal operator returns true for a pair "
+ "of values with a different hash value\n");
+ gcc_unreachable ();
+}
+
+/* Verify that all existing elements in th hash table which are
+ equal to COMPARABLE have an equal HASH value provided as argument. */
+
+template<typename Descriptor, bool Lazy,
+ template<typename Type> class Allocator>
+void
+hash_table<Descriptor, Lazy, Allocator>
+::verify (const compare_type &comparable, hashval_t hash)
+{
+ for (size_t i = 0; i < MIN (hash_table_sanitize_eq_limit, m_size); i++)
+ {
+ value_type *entry = &m_entries[i];
+ if (!is_empty (*entry) && !is_deleted (*entry)
+ && hash != Descriptor::hash (*entry)
+ && Descriptor::equal (*entry, comparable))
+ hashtab_chk_error ();
+ }
+}
+
/* This function deletes an element with the given COMPARABLE value
from hash table starting with the given HASH. If there is no
matching element in the hash table, this function does nothing. */
-template<typename Descriptor, template<typename Type> class Allocator>
+template<typename Descriptor, bool Lazy,
+ template<typename Type> class Allocator>
void
-hash_table<Descriptor, Allocator>
+hash_table<Descriptor, Lazy, Allocator>
::remove_elt_with_hash (const compare_type &comparable, hashval_t hash)
{
value_type *slot = find_slot_with_hash (comparable, hash, NO_INSERT);
- if (is_empty (*slot))
+ if (slot == NULL)
return;
Descriptor::remove (*slot);
each live entry. If CALLBACK returns false, the iteration stops.
ARGUMENT is passed as CALLBACK's second argument. */
-template<typename Descriptor,
+template<typename Descriptor, bool Lazy,
template<typename Type> class Allocator>
template<typename Argument,
- int (*Callback)
- (typename hash_table<Descriptor, Allocator>::value_type *slot,
- Argument argument)>
+ int (*Callback)
+ (typename hash_table<Descriptor, Lazy, Allocator>::value_type *slot,
+ Argument argument)>
void
-hash_table<Descriptor, Allocator>::traverse_noresize (Argument argument)
+hash_table<Descriptor, Lazy, Allocator>::traverse_noresize (Argument argument)
{
+ if (Lazy && m_entries == NULL)
+ return;
+
value_type *slot = m_entries;
value_type *limit = slot + size ();
/* Like traverse_noresize, but does resize the table when it is too empty
to improve effectivity of subsequent calls. */
-template <typename Descriptor,
+template <typename Descriptor, bool Lazy,
template <typename Type> class Allocator>
template <typename Argument,
int (*Callback)
- (typename hash_table<Descriptor, Allocator>::value_type *slot,
- Argument argument)>
+ (typename hash_table<Descriptor, Lazy, Allocator>::value_type *slot,
+ Argument argument)>
void
-hash_table<Descriptor, Allocator>::traverse (Argument argument)
+hash_table<Descriptor, Lazy, Allocator>::traverse (Argument argument)
{
- size_t size = m_size;
- if (elements () * 8 < size && size > 32)
+ if (too_empty_p (elements ()) && (!Lazy || m_entries))
expand ();
traverse_noresize <Argument, Callback> (argument);
/* Slide down the iterator slots until an active entry is found. */
-template<typename Descriptor, template<typename Type> class Allocator>
+template<typename Descriptor, bool Lazy,
+ template<typename Type> class Allocator>
void
-hash_table<Descriptor, Allocator>::iterator::slide ()
+hash_table<Descriptor, Lazy, Allocator>::iterator::slide ()
{
for ( ; m_slot < m_limit; ++m_slot )
{
/* Bump the iterator. */
-template<typename Descriptor, template<typename Type> class Allocator>
-inline typename hash_table<Descriptor, Allocator>::iterator &
-hash_table<Descriptor, Allocator>::iterator::operator ++ ()
+template<typename Descriptor, bool Lazy,
+ template<typename Type> class Allocator>
+inline typename hash_table<Descriptor, Lazy, Allocator>::iterator &
+hash_table<Descriptor, Lazy, Allocator>::iterator::operator ++ ()
{
++m_slot;
slide ();
|| table::is_deleted (h->m_entries[i]))
continue;
- E::ggc_mx (h->m_entries[i]);
+ /* Use ggc_maxbe_mx so we don't mark right away for cache tables; we'll
+ mark in gt_cleare_cache if appropriate. */
+ E::ggc_maybe_mx (h->m_entries[i]);
}
}
inline void
gt_cleare_cache (hash_table<H> *h)
{
- extern void gt_ggc_mx (typename H::value_type &t);
typedef hash_table<H> table;
if (!h)
return;
if (res == 0)
h->clear_slot (&*iter);
else if (res != -1)
- gt_ggc_mx (*iter);
+ H::ggc_mx (*iter);
}
}
projects / thirdparty / gcc.git / blobdiff