/* A type-safe hash set.
- Copyright (C) 2014-2015 Free Software Foundation, Inc.
+ Copyright (C) 2014-2020 Free Software Foundation, Inc.
This file is part of GCC.
#ifndef hash_set_h
#define hash_set_h
-#include "hash-table.h"
-
-/* implement default behavior for traits when types allow it. */
-
-struct default_hashset_traits
+/* Class hash_set is a hash-value based container for objects of
+ KeyId type.
+ KeyId may be a non-trivial (non-POD) type provided a suitabe Traits
+ class. Default Traits specializations are provided for basic types
+ such as integers, pointers, and std::pair. Inserted elements are
+ value-initialized either to zero for POD types or by invoking their
+ default ctor. Removed elements are destroyed by invoking their dtor.
+ On hash_set destruction all elements are removed. Objects of
+ hash_set type are copy-constructible but not assignable. */
+
+template<typename KeyId, bool Lazy = false,
+ typename Traits = default_hash_traits<KeyId> >
+class hash_set
{
- /* Hashes the passed in key. */
-
- template<typename T>
- static hashval_t
- hash (T *p)
- {
- return uintptr_t(p) >> 3;
- }
-
- template<typename T> static hashval_t hash(const T &v) { return v; }
+public:
+ typedef typename Traits::value_type Key;
+ explicit hash_set (size_t n = 13, bool ggc = false CXX_MEM_STAT_INFO)
+ : m_table (n, ggc, true, GATHER_STATISTICS, HASH_SET_ORIGIN PASS_MEM_STAT) {}
- /* Return true if the two keys passed as arguments are equal. */
+ /* Create a hash_set in gc memory with space for at least n elements. */
- template<typename T>
- static bool
- equal (const T &a, const T &b)
+ static hash_set *
+ create_ggc (size_t n)
{
- return a == b;
+ hash_set *set = ggc_alloc<hash_set> ();
+ new (set) hash_set (n, true);
+ return set;
}
- /* Called to dispose of the key before marking the entry as deleted. */
-
- template<typename T> static void remove (T &v) { v.~T (); }
-
- /* Mark the passed in entry as being deleted. */
+ /* If key k isn't already in the map add it to the map, and
+ return false. Otherwise return true. */
- template<typename T>
- static void
- mark_deleted (T *&e)
+ bool add (const Key &k)
{
- e = reinterpret_cast<void *> (1);
- }
-
- /* Mark the passed in entry as being empty. */
+ Key *e = m_table.find_slot_with_hash (k, Traits::hash (k), INSERT);
+ bool existed = !Traits::is_empty (*e);
+ if (!existed)
+ new (e) Key (k);
- template<typename T>
- static void
- mark_empty (T *&e)
- {
- e = NULL;
+ return existed;
}
- /* Return true if the passed in entry is marked as deleted. */
+ /* if the passed in key is in the map return its value otherwise NULL. */
- template<typename T>
- static bool
- is_deleted (T *e)
+ bool contains (const Key &k)
{
- return e == reinterpret_cast<void *> (1);
+ if (Lazy)
+ return (m_table.find_slot_with_hash (k, Traits::hash (k), NO_INSERT)
+ != NULL);
+ Key &e = m_table.find_with_hash (k, Traits::hash (k));
+ return !Traits::is_empty (e);
}
- /* Return true if the passed in entry is marked as empty. */
-
- template<typename T> static bool is_empty (T *e) { return e == NULL; }
-
- /* ggc walking routine, mark all objects refered to by this one. */
-
- template<typename T>
- static void
- ggc_mx (T &x)
+ void remove (const Key &k)
{
- extern void gt_ggc_mx (T &);
- gt_ggc_mx (x);
+ m_table.remove_elt_with_hash (k, Traits::hash (k));
}
- /* pch walking routine, note all objects refered to by this element. */
+ /* Call the call back on each pair of key and value with the passed in
+ arg. */
- template<typename T>
- static void
- pch_nx (T &x)
+ template<typename Arg, bool (*f)(const typename Traits::value_type &, Arg)>
+ void traverse (Arg a) const
{
- extern void gt_pch_nx (T &);
- gt_pch_nx (x);
+ for (typename hash_table<Traits, Lazy>::iterator iter = m_table.begin ();
+ iter != m_table.end (); ++iter)
+ f (*iter, a);
}
-};
-
-template<typename Key, typename Traits = default_hashset_traits>
-class hash_set
-{
- struct hash_entry
- {
- Key m_key;
- typedef hash_entry value_type;
- typedef Key compare_type;
- typedef int store_values_directly;
+ /* Return the number of elements in the set. */
- static hashval_t hash (const hash_entry &e)
- {
- return Traits::hash (e.m_key);
- }
+ size_t elements () const { return m_table.elements (); }
- static bool equal (const hash_entry &a, const Key &b)
- {
- return Traits::equal (a.m_key, b);
- }
+ /* Clear the hash table. */
- static void remove (hash_entry &e) { Traits::remove (e.m_key); }
+ void empty () { m_table.empty (); }
- static void
- mark_deleted (hash_entry &e)
- {
- Traits::mark_deleted (e.m_key);
- }
+ /* Return true when there are no elements in this hash set. */
+ bool is_empty () const { return m_table.is_empty (); }
- static bool is_deleted (const hash_entry &e)
- {
- return Traits::is_deleted (e.m_key);
- }
-
- static void
- mark_empty (hash_entry &e)
- {
- Traits::mark_empty (e.m_key);
- }
-
- static bool
- is_empty (const hash_entry &e)
- {
- return Traits::is_empty (e.m_key);
- }
+ class iterator
+ {
+ public:
+ explicit iterator (const typename hash_table<Traits,
+ Lazy>::iterator &iter) :
+ m_iter (iter) {}
- static void ggc_mx (hash_entry &e)
+ iterator &operator++ ()
{
- Traits::ggc_mx (e.m_key);
+ ++m_iter;
+ return *this;
}
- static void pch_nx (hash_entry &e)
+ Key
+ operator* ()
{
- Traits::pch_nx (e.m_key);
+ return *m_iter;
}
- static void pch_nx (hash_entry &e, gt_pointer_operator op, void *c)
+ bool
+ operator != (const iterator &other) const
{
- pch_nx_helper (e.m_key, op, c);
+ return m_iter != other.m_iter;
}
private:
- template<typename T>
- static void
- pch_nx_helper (T &x, gt_pointer_operator op, void *cookie)
- {
- gt_pch_nx (&x, op, cookie);
- }
-
- template<typename T>
- static void
- pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie)
- {
- op (&x, cookie);
- }
+ typename hash_table<Traits, Lazy>::iterator m_iter;
};
-public:
- explicit hash_set (size_t n = 13, bool ggc = false) : m_table (n, ggc) {}
+ /* Standard iterator retrieval methods. */
- /* Create a hash_set in gc memory with space for at least n elements. */
+ iterator begin () const { return iterator (m_table.begin ()); }
+ iterator end () const { return iterator (m_table.end ()); }
- static hash_set *
- create_ggc (size_t n)
- {
- hash_set *set = ggc_alloc<hash_set> ();
- new (set) hash_set (n, true);
- return set;
- }
- /* If key k isn't already in the map add it to the map, and
- return false. Otherwise return true. */
+private:
- bool add (const Key &k)
- {
- hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
- INSERT);
- bool existed = !hash_entry::is_empty (*e);
- if (!existed)
- e->m_key = k;
+ template<typename T, typename U>
+ friend void gt_ggc_mx (hash_set<T, false, U> *);
+ template<typename T, typename U>
+ friend void gt_pch_nx (hash_set<T, false, U> *);
+ template<typename T, typename U>
+ friend void gt_pch_nx (hash_set<T, false, U> *, gt_pointer_operator, void *);
- return existed;
- }
+ hash_table<Traits, Lazy> m_table;
+};
- /* if the passed in key is in the map return its value otherwise NULL. */
+/* Generic hash_set<TYPE> debug helper.
- bool contains (const Key &k)
- {
- hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
- return !Traits::is_empty (e.m_key);
- }
+ This needs to be instantiated for each hash_set<TYPE> used throughout
+ the compiler like this:
- /* Call the call back on each pair of key and value with the passed in
- arg. */
+ DEFINE_DEBUG_HASH_SET (TYPE)
- template<typename Arg, bool (*f)(const Key &, Arg)>
- void traverse (Arg a) const
+ The reason we have a debug_helper() is because GDB can't
+ disambiguate a plain call to debug(some_hash), and it must be called
+ like debug<TYPE>(some_hash). */
+template<typename T>
+void
+debug_helper (hash_set<T> &ref)
+{
+ for (typename hash_set<T>::iterator it = ref.begin ();
+ it != ref.end (); ++it)
{
- for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
- iter != m_table.end (); ++iter)
- f ((*iter).m_key, a);
+ debug_slim (*it);
+ fputc ('\n', stderr);
}
+}
- /* Return the number of elements in the set. */
-
- size_t elements () const { return m_table.elements (); }
-
-private:
-
- template<typename T, typename U> friend void gt_ggc_mx (hash_set<T, U> *);
- template<typename T, typename U> friend void gt_pch_nx (hash_set<T, U> *);
- template<typename T, typename U> friend void gt_pch_nx (hash_set<T, U> *, gt_pointer_operator, void *);
-
- hash_table<hash_entry> m_table;
-};
+#define DEFINE_DEBUG_HASH_SET(T) \
+ template void debug_helper (hash_set<T> &); \
+ DEBUG_FUNCTION void \
+ debug (hash_set<T> &ref) \
+ { \
+ debug_helper <T> (ref); \
+ } \
+ DEBUG_FUNCTION void \
+ debug (hash_set<T> *ptr) \
+ { \
+ if (ptr) \
+ debug (*ptr); \
+ else \
+ fprintf (stderr, "<nil>\n"); \
+ }
/* ggc marking routines. */
template<typename K, typename H>
static inline void
-gt_ggc_mx (hash_set<K, H> *h)
+gt_ggc_mx (hash_set<K, false, H> *h)
{
gt_ggc_mx (&h->m_table);
}
template<typename K, typename H>
static inline void
-gt_pch_nx (hash_set<K, H> *h)
+gt_pch_nx (hash_set<K, false, H> *h)
{
gt_pch_nx (&h->m_table);
}
template<typename K, typename H>
static inline void
-gt_pch_nx (hash_set<K, H> *h, gt_pointer_operator op, void *cookie)
+gt_pch_nx (hash_set<K, false, H> *h, gt_pointer_operator op, void *cookie)
{
op (&h->m_table.m_entries, cookie);
}
projects / platform / upstream / gcc.git / blobdiff