On Fri, Jun 20, 2014 at 12:52 PM, <tsaund...@mozilla.com> wrote:
> From: Trevor Saunders <tsaund...@mozilla.com>
>
> Hi,
>
> this patch allows you to define the type the hash table stores as elements
> instead of the type elements point at by having your hash descriptor define
> the
> type store_values_directly. It turns out trying to implement both cases with
> the same code is really confusing, so I ended up providing one partial
> specialization for each case. Its a lot of coppying, but I'm hoping the next
> patch will get rid of many direct users of hash_table, and the rest can all
> get
> converted to tell the hash table the type entries should have at which point
> the dupplication can be removed.
>
> bootstrapped + regtested without regression on x86_64-unknown-linux-gnu, ok?
Ok. I hope that de-duplication works out.
Thanks,
Richard.
> Trev
>
> gcc/
>
> * hash-table.h: Add a template arg to choose between storing values
> and storing pointers to values, and then provide partial
> specializations for both.
> * tree-browser.c (tree_upper_hasher): Provide the type the hash table
> should store, not the type values should point to.
> * tree-into-ssa.c (var_info_hasher): Likewise.
> * tree-ssa-dom.c (expr_elt_hasher): Likewise.
> * tree-complex.c: Adjust.
> * tree-hasher.h (int_tree_hasher): store int_tree_map in the hash
> table instead of int_tree_map *.
> * tree-parloops.c: Adjust.
> * tree-ssa-reassoc.c (ocount_hasher): Don't lie to hash_map about what
> type is being stored.
> * tree-vectorizer.c: Adjust.
>
> diff --git a/gcc/hash-table.h b/gcc/hash-table.h
> index 41cc19e..22af12f 100644
> --- a/gcc/hash-table.h
> +++ b/gcc/hash-table.h
> @@ -272,19 +272,18 @@ typed_noop_remove <Type>::remove (Type *p
> ATTRIBUTE_UNUSED)
> template <typename Type>
> struct pointer_hash : typed_noop_remove <Type>
> {
> - typedef Type value_type;
> - typedef Type compare_type;
> + typedef Type *value_type;
> + typedef Type *compare_type;
> + typedef int store_values_directly;
>
> - static inline hashval_t
> - hash (const value_type *);
> + static inline hashval_t hash (const value_type &);
>
> - static inline int
> - equal (const value_type *existing, const compare_type *candidate);
> + static inline bool equal (const value_type &existing, const compare_type
> &candidate);
> };
>
> template <typename Type>
> inline hashval_t
> -pointer_hash <Type>::hash (const value_type *candidate)
> +pointer_hash <Type>::hash (const value_type &candidate)
> {
> /* This is a really poor hash function, but it is what the current code
> uses,
> so I am reusing it to avoid an additional axis in testing. */
> @@ -292,9 +291,9 @@ pointer_hash <Type>::hash (const value_type *candidate)
> }
>
> template <typename Type>
> -inline int
> -pointer_hash <Type>::equal (const value_type *existing,
> - const compare_type *candidate)
> +inline bool
> +pointer_hash <Type>::equal (const value_type &existing,
> + const compare_type &candidate)
> {
> return existing == candidate;
> }
> @@ -319,10 +318,147 @@ extern unsigned int hash_table_higher_prime_index
> (unsigned long n);
> extern hashval_t hash_table_mod1 (hashval_t hash, unsigned int index);
> extern hashval_t hash_table_mod2 (hashval_t hash, unsigned int index);
>
> +/* The below is some template meta programming to decide if we should use the
> + hash table partial specialization that directly stores value_type instead
> of
> + pointers to value_type. If the Descriptor type defines the type
> + Descriptor::store_values_directly then values are stored directly
> otherwise
> + pointers to them are stored. */
> +template<typename T> struct notype { typedef void type; };
> +
> +template<typename T, typename = void>
> +struct storage_tester
> +{
> + static const bool value = false;
> +};
> +
> +template<typename T>
> +struct storage_tester<T, typename notype<typename
> + T::store_values_directly>::type>
> +{
> + static const bool value = true;
> +};
> +
> + template<typename Traits>
> + struct has_is_deleted
> +{
> + template<typename U, bool (*)(U &)> struct helper {};
> + template<typename U> static char test (helper<U, U::is_deleted> *);
> + template<typename U> static int test (...);
> + static const bool value = sizeof (test<Traits> (0)) == sizeof (char);
> +};
> +
> +template<typename Type, typename Traits, bool =
> has_is_deleted<Traits>::value>
> +struct is_deleted_helper
> +{
> + static inline bool
> + call (Type &v)
> + {
> + return Traits::is_deleted (v);
> + }
> +};
> +
> +template<typename Type, typename Traits>
> +struct is_deleted_helper<Type *, Traits, false>
> +{
> + static inline bool
> + call (Type *v)
> + {
> + return v == HTAB_DELETED_ENTRY;
> + }
> +};
> +
> + template<typename Traits>
> + struct has_is_empty
> +{
> + template<typename U, bool (*)(U &)> struct helper {};
> + template<typename U> static char test (helper<U, U::is_empty> *);
> + template<typename U> static int test (...);
> + static const bool value = sizeof (test<Traits> (0)) == sizeof (char);
> +};
> +
> +template<typename Type, typename Traits, bool =
> has_is_deleted<Traits>::value>
> +struct is_empty_helper
> +{
> + static inline bool
> + call (Type &v)
> + {
> + return Traits::is_empty (v);
> + }
> +};
> +
> +template<typename Type, typename Traits>
> +struct is_empty_helper<Type *, Traits, false>
> +{
> + static inline bool
> + call (Type *v)
> + {
> + return v == HTAB_EMPTY_ENTRY;
> + }
> +};
> +
> + template<typename Traits>
> + struct has_mark_deleted
> +{
> + template<typename U, void (*)(U &)> struct helper {};
> + template<typename U> static char test (helper<U, U::mark_deleted> *);
> + template<typename U> static int test (...);
> + static const bool value = sizeof (test<Traits> (0)) == sizeof (char);
> +};
> +
> +template<typename Type, typename Traits, bool =
> has_is_deleted<Traits>::value>
> +struct mark_deleted_helper
> +{
> + static inline void
> + call (Type &v)
> + {
> + Traits::mark_deleted (v);
> + }
> +};
> +
> +template<typename Type, typename Traits>
> +struct mark_deleted_helper<Type *, Traits, false>
> +{
> + static inline void
> + call (Type *&v)
> + {
> + v = static_cast<Type *> (HTAB_DELETED_ENTRY);
> + }
> +};
> +
> + template<typename Traits>
> + struct has_mark_empty
> +{
> + template<typename U, void (*)(U &)> struct helper {};
> + template<typename U> static char test (helper<U, U::mark_empty> *);
> + template<typename U> static int test (...);
> + static const bool value = sizeof (test<Traits> (0)) == sizeof (char);
> +};
> +
> +template<typename Type, typename Traits, bool =
> has_is_deleted<Traits>::value>
> +struct mark_empty_helper
> +{
> + static inline void
> + call (Type &v)
> + {
> + Traits::mark_empty (v);
> + }
> +};
> +
> +template<typename Type, typename Traits>
> +struct mark_empty_helper<Type *, Traits, false>
> +{
> + static inline void
> + call (Type *&v)
> + {
> + v = static_cast<Type *> (HTAB_EMPTY_ENTRY);
> + }
> +};
>
> /* User-facing hash table type.
>
> - The table stores elements of type Descriptor::value_type.
> + The table stores elements of type Descriptor::value_type, or pointers to
> + objects of type value_type if the descriptor does not define the type
> + store_values_directly.
>
> It hashes values with the hash member function.
> The table currently works with relatively weak hash functions.
> @@ -340,11 +476,21 @@ extern hashval_t hash_table_mod2 (hashval_t hash,
> unsigned int index);
> Specify the template Allocator to allocate and free memory.
> The default is xcallocator.
>
> + Storage is an implementation detail and should not be used outside the
> + hash table code.
> +
> */
> template <typename Descriptor,
> - template<typename Type> class Allocator= xcallocator>
> + template<typename Type> class Allocator= xcallocator,
> + bool Storage = storage_tester<Descriptor>::value>
> class hash_table
> {
> +};
> +
> +template <typename Descriptor,
> + template<typename Type> class Allocator>
> +class hash_table<Descriptor, Allocator, false>
> +{
> typedef typename Descriptor::value_type value_type;
> typedef typename Descriptor::compare_type compare_type;
>
> @@ -428,7 +574,7 @@ public:
> iterator (value_type **slot, value_type **limit) :
> m_slot (slot), m_limit (limit) {}
>
> - inline value_type &operator * () { return **m_slot; }
> + inline value_type *operator * () { return *m_slot; }
> void slide ();
> inline iterator &operator ++ ();
> bool operator != (const iterator &other) const
> @@ -485,7 +631,7 @@ private:
> };
>
> template<typename Descriptor, template<typename Type> class Allocator>
> -hash_table<Descriptor, Allocator>::hash_table (size_t size) :
> +hash_table<Descriptor, Allocator, false>::hash_table (size_t size) :
> m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0)
> {
> unsigned int size_prime_index;
> @@ -500,7 +646,7 @@ hash_table<Descriptor, Allocator>::hash_table (size_t
> size) :
> }
>
> template<typename Descriptor, template<typename Type> class Allocator>
> -hash_table<Descriptor, Allocator>::~hash_table ()
> +hash_table<Descriptor, Allocator, false>::~hash_table ()
> {
> for (size_t i = m_size - 1; i < m_size; i--)
> if (m_entries[i] != HTAB_EMPTY_ENTRY && m_entries[i] !=
> HTAB_DELETED_ENTRY)
> @@ -518,7 +664,8 @@ hash_table<Descriptor, Allocator>::~hash_table ()
>
> template<typename Descriptor, template<typename Type> class Allocator>
> typename Descriptor::value_type **
> -hash_table<Descriptor, Allocator>::find_empty_slot_for_expand (hashval_t
> hash)
> +hash_table<Descriptor, Allocator, false>
> +::find_empty_slot_for_expand (hashval_t hash)
> {
> hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
> size_t size = m_size;
> @@ -554,7 +701,7 @@ hash_table<Descriptor,
> Allocator>::find_empty_slot_for_expand (hashval_t hash)
>
> template<typename Descriptor, template<typename Type> class
> Allocator>
> void
> -hash_table<Descriptor, Allocator>::expand ()
> +hash_table<Descriptor, Allocator, false>::expand ()
> {
> value_type **oentries = m_entries;
> unsigned int oindex = m_size_prime_index;
> @@ -606,7 +753,7 @@ hash_table<Descriptor, Allocator>::expand ()
>
> template<typename Descriptor, template<typename Type> class Allocator>
> void
> -hash_table<Descriptor, Allocator>::empty ()
> +hash_table<Descriptor, Allocator, false>::empty ()
> {
> size_t size = m_size;
> value_type **entries = m_entries;
> @@ -639,7 +786,7 @@ hash_table<Descriptor, Allocator>::empty ()
>
> template<typename Descriptor, template<typename Type> class Allocator>
> void
> -hash_table<Descriptor, Allocator>::clear_slot (value_type **slot)
> +hash_table<Descriptor, Allocator, false>::clear_slot (value_type **slot)
> {
> if (slot < m_entries || slot >= m_entries + size ()
> || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)
> @@ -657,7 +804,7 @@ hash_table<Descriptor, Allocator>::clear_slot (value_type
> **slot)
>
> template<typename Descriptor, template<typename Type> class Allocator>
> typename Descriptor::value_type *
> -hash_table<Descriptor, Allocator>
> +hash_table<Descriptor, Allocator, false>
> ::find_with_hash (const compare_type *comparable, hashval_t hash)
> {
> m_searches++;
> @@ -695,7 +842,7 @@ hash_table<Descriptor, Allocator>
>
> template<typename Descriptor, template<typename Type> class Allocator>
> typename Descriptor::value_type **
> -hash_table<Descriptor, Allocator>
> +hash_table<Descriptor, Allocator, false>
> ::find_slot_with_hash (const compare_type *comparable, hashval_t hash,
> enum insert_option insert)
> {
> @@ -756,7 +903,7 @@ hash_table<Descriptor, Allocator>
>
> template<typename Descriptor, template<typename Type> class Allocator>
> void
> -hash_table<Descriptor, Allocator>
> +hash_table<Descriptor, Allocator, false>
> ::remove_elt_with_hash (const compare_type *comparable, hashval_t hash)
> {
> value_type **slot = find_slot_with_hash (comparable, hash, NO_INSERT);
> @@ -773,12 +920,11 @@ hash_table<Descriptor, Allocator>
> each live entry. If CALLBACK returns false, the iteration stops.
> ARGUMENT is passed as CALLBACK's second argument. */
>
> -template<typename Descriptor,
> - template<typename Type> class Allocator>
> +template<typename Descriptor, template<typename Type> class Allocator>
> template<typename Argument,
> int (*Callback) (typename Descriptor::value_type **slot, Argument
> argument)>
> void
> -hash_table<Descriptor, Allocator>::traverse_noresize (Argument argument)
> +hash_table<Descriptor, Allocator, false>::traverse_noresize (Argument
> argument)
> {
> value_type **slot = m_entries;
> value_type **limit = slot + size ();
> @@ -803,7 +949,7 @@ template <typename Argument,
> int (*Callback) (typename Descriptor::value_type **slot,
> Argument argument)>
> void
> -hash_table<Descriptor, Allocator>::traverse (Argument argument)
> +hash_table<Descriptor, Allocator, false>::traverse (Argument argument)
> {
> size_t size = m_size;
> if (elements () * 8 < size && size > 32)
> @@ -816,7 +962,7 @@ hash_table<Descriptor, Allocator>::traverse (Argument
> argument)
>
> template<typename Descriptor, template<typename Type> class Allocator>
> void
> -hash_table<Descriptor, Allocator>::iterator::slide ()
> +hash_table<Descriptor, Allocator, false>::iterator::slide ()
> {
> for ( ; m_slot < m_limit; ++m_slot )
> {
> @@ -831,8 +977,527 @@ hash_table<Descriptor, Allocator>::iterator::slide ()
> /* Bump the iterator. */
>
> template<typename Descriptor, template<typename Type> class Allocator>
> -inline typename hash_table<Descriptor, Allocator>::iterator &
> -hash_table<Descriptor, Allocator>::iterator::operator ++ ()
> +inline typename hash_table<Descriptor, Allocator, false>::iterator &
> +hash_table<Descriptor, Allocator, false>::iterator::operator ++ ()
> +{
> + ++m_slot;
> + slide ();
> + return *this;
> +}
> +
> +/* A partial specialization used when values should be stored directly. */
> +
> +template <typename Descriptor,
> + template<typename Type> class Allocator>
> +class hash_table<Descriptor, Allocator, true>
> +{
> + typedef typename Descriptor::value_type value_type;
> + typedef typename Descriptor::compare_type compare_type;
> +
> +public:
> + hash_table (size_t);
> + ~hash_table ();
> +
> + /* Current size (in entries) of the hash table. */
> + size_t size () const { return m_size; }
> +
> + /* Return the current number of elements in this hash table. */
> + size_t elements () const { return m_n_elements - m_n_deleted; }
> +
> + /* Return the current number of elements in this hash table. */
> + size_t elements_with_deleted () const { return m_n_elements; }
> +
> + /* This function clears all entries in the given hash table. */
> + void empty ();
> +
> + /* 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. */
> +
> + void clear_slot (value_type *);
> +
> + /* This function searches for a hash table entry equal to the given
> + COMPARABLE element starting with the given HASH value. It cannot
> + be used to insert or delete an element. */
> + value_type &find_with_hash (const compare_type &, hashval_t);
> +
> +/* Like find_slot_with_hash, but compute the hash value from the element. */
> + value_type &find (const value_type &value)
> + {
> + return find_with_hash (value, Descriptor::hash (value));
> + }
> +
> + value_type *find_slot (const value_type &value, insert_option insert)
> + {
> + return find_slot_with_hash (value, Descriptor::hash (value), insert);
> + }
> +
> + /* This function searches for a hash table slot containing an entry
> + equal to the given COMPARABLE element and starting with the given
> + HASH. To delete an entry, call this with insert=NO_INSERT, then
> + call clear_slot on the slot returned (possibly after doing some
> + checks). To insert an entry, call this with insert=INSERT, then
> + 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);
> +
> + /* 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. */
> + void remove_elt_with_hash (const compare_type &, hashval_t);
> +
> +/* Like remove_elt_with_hash, but compute the hash value from the element.
> */
> + void remove_elt (const value_type &value)
> + {
> + remove_elt_with_hash (value, Descriptor::hash (value));
> + }
> +
> + /* This function scans over the entire hash table calling CALLBACK for
> + each live entry. If CALLBACK returns false, the iteration stops.
> + ARGUMENT is passed as CALLBACK's second argument. */
> + template <typename Argument,
> + int (*Callback) (value_type *slot, Argument argument)>
> + void traverse_noresize (Argument argument);
> +
> + /* Like traverse_noresize, but does resize the table when it is too empty
> + to improve effectivity of subsequent calls. */
> + template <typename Argument,
> + int (*Callback) (value_type *slot, Argument argument)>
> + void traverse (Argument argument);
> +
> + class iterator
> + {
> + public:
> + iterator () : m_slot (NULL), m_limit (NULL) {}
> +
> + iterator (value_type *slot, value_type *limit) :
> + m_slot (slot), m_limit (limit) {}
> +
> + inline value_type &operator * () { return *m_slot; }
> + void slide ();
> + inline iterator &operator ++ ();
> + bool operator != (const iterator &other) const
> + {
> + return m_slot != other.m_slot || m_limit != other.m_limit;
> + }
> +
> + private:
> + value_type *m_slot;
> + value_type *m_limit;
> + };
> +
> + iterator begin () const
> + {
> + iterator iter (m_entries, m_entries + m_size);
> + iter.slide ();
> + return iter;
> + }
> +
> + iterator end () const { return iterator (); }
> +
> + double collisions () const
> + {
> + return m_searches ? static_cast <double> (m_collisions) / m_searches :
> 0;
> + }
> +
> +private:
> +
> + value_type *find_empty_slot_for_expand (hashval_t);
> + void expand ();
> + static bool is_deleted (value_type &v)
> + {
> + return is_deleted_helper<value_type, Descriptor>::call (v);
> + }
> + static bool is_empty (value_type &v)
> + {
> + return is_empty_helper<value_type, Descriptor>::call (v);
> + }
> +
> + static void mark_deleted (value_type &v)
> + {
> + return mark_deleted_helper<value_type, Descriptor>::call (v);
> + }
> +
> + static void mark_empty (value_type &v)
> + {
> + return mark_empty_helper<value_type, Descriptor>::call (v);
> + }
> +
> + /* Table itself. */
> + typename Descriptor::value_type *m_entries;
> +
> + size_t m_size;
> +
> + /* Current number of elements including also deleted elements. */
> + size_t m_n_elements;
> +
> + /* Current number of deleted elements in the table. */
> + size_t m_n_deleted;
> +
> + /* The following member is used for debugging. Its value is number
> + of all calls of `htab_find_slot' for the hash table. */
> + unsigned int m_searches;
> +
> + /* The following member is used for debugging. Its value is number
> + of collisions fixed for time of work with the hash table. */
> + unsigned int m_collisions;
> +
> + /* Current size (in entries) of the hash table, as an index into the
> + table of primes. */
> + unsigned int m_size_prime_index;
> +};
> +
> +template<typename Descriptor, template<typename Type> class Allocator>
> +hash_table<Descriptor, Allocator, true>::hash_table (size_t size) :
> + m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0)
> +{
> + unsigned int size_prime_index;
> +
> + size_prime_index = hash_table_higher_prime_index (size);
> + size = prime_tab[size_prime_index].prime;
> +
> + m_entries = Allocator <value_type> ::data_alloc (size);
> + gcc_assert (m_entries != NULL);
> + m_size = size;
> + m_size_prime_index = size_prime_index;
> +}
> +
> +template<typename Descriptor, template<typename Type> class Allocator>
> +hash_table<Descriptor, Allocator, true>::~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]);
> +
> + Allocator <value_type> ::data_free (m_entries);
> +}
> +
> +/* Similar to find_slot, but without several unwanted side effects:
> + - Does not call equal when it finds an existing entry.
> + - Does not change the count of elements/searches/collisions in the
> + hash table.
> + 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 Descriptor::value_type *
> +hash_table<Descriptor, Allocator, true>
> +::find_empty_slot_for_expand (hashval_t hash)
> +{
> + hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
> + size_t size = m_size;
> + value_type *slot = m_entries + index;
> + hashval_t hash2;
> +
> + if (is_empty (*slot))
> + return slot;
> + else if (is_deleted (*slot))
> + abort ();
> +
> + hash2 = hash_table_mod2 (hash, m_size_prime_index);
> + for (;;)
> + {
> + index += hash2;
> + if (index >= size)
> + index -= size;
> +
> + slot = m_entries + index;
> + if (is_empty (*slot))
> + return slot;
> + else if (is_deleted (*slot))
> + abort ();
> + }
> +}
> +
> +/* 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 must already exist. Remember also that the place of the
> + table entries is changed. If memory allocation fails, this function
> + will abort. */
> +
> + template<typename Descriptor, template<typename Type> class
> Allocator>
> +void
> +hash_table<Descriptor, Allocator, true>::expand ()
> +{
> + value_type *oentries = m_entries;
> + unsigned int oindex = m_size_prime_index;
> + size_t osize = size ();
> + value_type *olimit = oentries + osize;
> + size_t elts = elements ();
> +
> + /* Resize only when table after removal of unused elements is either
> + too full or too empty. */
> + unsigned int nindex;
> + size_t nsize;
> + if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
> + {
> + nindex = hash_table_higher_prime_index (elts * 2);
> + nsize = prime_tab[nindex].prime;
> + }
> + else
> + {
> + nindex = oindex;
> + nsize = osize;
> + }
> +
> + value_type *nentries = Allocator <value_type> ::data_alloc (nsize);
> + gcc_assert (nentries != NULL);
> + m_entries = nentries;
> + m_size = nsize;
> + m_size_prime_index = nindex;
> + m_n_elements -= m_n_deleted;
> + m_n_deleted = 0;
> +
> + value_type *p = oentries;
> + do
> + {
> + value_type &x = *p;
> +
> + if (!is_empty (x) && !is_deleted (x))
> + {
> + value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
> +
> + *q = x;
> + }
> +
> + p++;
> + }
> + while (p < olimit);
> +
> + Allocator <value_type> ::data_free (oentries);
> +}
> +
> +template<typename Descriptor, template<typename Type> class Allocator>
> +void
> +hash_table<Descriptor, Allocator, true>::empty ()
> +{
> + size_t size = m_size;
> + value_type *entries = m_entries;
> + int i;
> +
> + for (i = size - 1; i >= 0; i--)
> + if (!is_empty (entries[i]) && !is_deleted (entries[i]))
> + Descriptor::remove (entries[i]);
> +
> + /* Instead of clearing megabyte, downsize the table. */
> + if (size > 1024*1024 / sizeof (PTR))
> + {
> + int nindex = hash_table_higher_prime_index (1024 / sizeof (PTR));
> + int nsize = prime_tab[nindex].prime;
> +
> + Allocator <value_type> ::data_free (m_entries);
> + m_entries = Allocator <value_type> ::data_alloc (nsize);
> + m_size = nsize;
> + m_size_prime_index = nindex;
> + }
> + else
> + memset (entries, 0, size * sizeof (value_type));
> + m_n_deleted = 0;
> + m_n_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. */
> +
> +template<typename Descriptor, template<typename Type> class Allocator>
> +void
> +hash_table<Descriptor, Allocator, true>::clear_slot (value_type *slot)
> +{
> + if (slot < m_entries || slot >= m_entries + size ()
> + || is_empty (*slot) || is_deleted (*slot))
> + abort ();
> +
> + Descriptor::remove (*slot);
> +
> + mark_deleted (*slot);
> + m_n_deleted++;
> +}
> +
> +/* This function searches for a hash table entry equal to the given
> + 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 Descriptor::value_type &
> +hash_table<Descriptor, Allocator, true>
> +::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);
> +
> + value_type *entry = &m_entries[index];
> + if (is_empty (*entry)
> + || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
> + return *entry;
> +
> + hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
> + for (;;)
> + {
> + m_collisions++;
> + index += hash2;
> + if (index >= size)
> + index -= size;
> +
> + entry = &m_entries[index];
> + if (is_empty (*entry)
> + || (!is_deleted (*entry) && Descriptor::equal (*entry,
> comparable)))
> + return *entry;
> + }
> +}
> +
> +/* This function searches for a hash table slot containing an entry
> + equal to the given COMPARABLE element and starting with the given
> + HASH. To delete an entry, call this with insert=NO_INSERT, then
> + call clear_slot on the slot returned (possibly after doing some
> + checks). To insert an entry, call this with insert=INSERT, then
> + 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 Descriptor::value_type *
> +hash_table<Descriptor, Allocator, true>
> +::find_slot_with_hash (const compare_type &comparable, hashval_t hash,
> + enum insert_option insert)
> +{
> + if (insert == INSERT && m_size * 3 <= m_n_elements * 4)
> + expand ();
> +
> + 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);
> + value_type *entry = &m_entries[index];
> + size_t size = m_size;
> + if (is_empty (*entry))
> + goto empty_entry;
> + else if (is_deleted (*entry))
> + first_deleted_slot = &m_entries[index];
> + else if (Descriptor::equal (*entry, comparable))
> + return &m_entries[index];
> +
> + for (;;)
> + {
> + m_collisions++;
> + index += hash2;
> + if (index >= size)
> + index -= size;
> +
> + entry = &m_entries[index];
> + if (is_empty (*entry))
> + goto empty_entry;
> + else if (is_deleted (*entry))
> + {
> + if (!first_deleted_slot)
> + first_deleted_slot = &m_entries[index];
> + }
> + else if (Descriptor::equal (*entry, comparable))
> + return &m_entries[index];
> + }
> +
> + empty_entry:
> + if (insert == NO_INSERT)
> + return NULL;
> +
> + if (first_deleted_slot)
> + {
> + m_n_deleted--;
> + mark_empty (*first_deleted_slot);
> + return first_deleted_slot;
> + }
> +
> + m_n_elements++;
> + return &m_entries[index];
> +}
> +
> +/* 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>
> +void
> +hash_table<Descriptor, Allocator, true>
> +::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))
> + return;
> +
> + Descriptor::remove (*slot);
> +
> + mark_deleted (*slot);
> + m_n_deleted++;
> +}
> +
> +/* This function scans over the entire hash table calling CALLBACK for
> + each live entry. If CALLBACK returns false, the iteration stops.
> + ARGUMENT is passed as CALLBACK's second argument. */
> +
> +template<typename Descriptor,
> + template<typename Type> class Allocator>
> +template<typename Argument,
> + int (*Callback) (typename Descriptor::value_type *slot,
> + Argument argument)>
> +void
> +hash_table<Descriptor, Allocator, true>::traverse_noresize (Argument
> argument)
> +{
> + value_type *slot = m_entries;
> + value_type *limit = slot + size ();
> +
> + do
> + {
> + value_type &x = *slot;
> +
> + if (!is_empty (x) && !is_deleted (x))
> + if (! Callback (slot, argument))
> + break;
> + }
> + while (++slot < limit);
> +}
> +
> +/* Like traverse_noresize, but does resize the table when it is too empty
> + to improve effectivity of subsequent calls. */
> +
> +template <typename Descriptor,
> + template <typename Type> class Allocator>
> +template <typename Argument,
> + int (*Callback) (typename Descriptor::value_type *slot,
> + Argument argument)>
> +void
> +hash_table<Descriptor, Allocator, true>::traverse (Argument argument)
> +{
> + size_t size = m_size;
> + if (elements () * 8 < size && size > 32)
> + 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>
> +void
> +hash_table<Descriptor, Allocator, true>::iterator::slide ()
> +{
> + for ( ; m_slot < m_limit; ++m_slot )
> + {
> + value_type &x = *m_slot;
> + if (!is_empty (x) && !is_deleted (x))
> + return;
> + }
> + m_slot = NULL;
> + m_limit = NULL;
> +}
> +
> +/* Bump the iterator. */
> +
> +template<typename Descriptor, template<typename Type> class Allocator>
> +inline typename hash_table<Descriptor, Allocator, true>::iterator &
> +hash_table<Descriptor, Allocator, true>::iterator::operator ++ ()
> {
> ++m_slot;
> slide ();
> @@ -846,7 +1511,7 @@ hash_table<Descriptor, Allocator>::iterator::operator ++
> ()
>
> #define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \
> for ((ITER) = (HTAB).begin (); \
> - (ITER) != (HTAB).end () ? (RESULT = &*(ITER) , true) : false; \
> + (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \
> ++(ITER))
>
> #endif /* TYPED_HASHTAB_H */
> diff --git a/gcc/tree-browser.c b/gcc/tree-browser.c
> index 8c03550..2a4db1b 100644
> --- a/gcc/tree-browser.c
> +++ b/gcc/tree-browser.c
> @@ -102,22 +102,13 @@ static tree TB_history_prev (void);
> void browse_tree (tree);
>
> /* Hashtable helpers. */
> -struct tree_upper_hasher : typed_noop_remove <tree_node>
> +struct tree_upper_hasher : pointer_hash<tree_node>
> {
> - typedef tree_node value_type;
> - typedef tree_node compare_type;
> - static inline hashval_t hash (const value_type *);
> - static inline bool equal (const value_type *, const compare_type *);
> + static inline bool equal (const value_type &, const compare_type &);
> };
>
> -inline hashval_t
> -tree_upper_hasher::hash (const value_type *v)
> -{
> - return pointer_hash <value_type>::hash (v);
> -}
> -
> inline bool
> -tree_upper_hasher::equal (const value_type *parent, const compare_type *node)
> +tree_upper_hasher::equal (const value_type &parent, const compare_type &node)
> {
> if (parent == NULL || node == NULL)
> return 0;
> diff --git a/gcc/tree-complex.c b/gcc/tree-complex.c
> index 7b0115d..3ed403a 100644
> --- a/gcc/tree-complex.c
> +++ b/gcc/tree-complex.c
> @@ -83,10 +83,9 @@ static vec<tree> complex_ssa_name_components;
> static tree
> cvc_lookup (unsigned int uid)
> {
> - struct int_tree_map *h, in;
> + struct int_tree_map in;
> in.uid = uid;
> - h = complex_variable_components->find_with_hash (&in, uid);
> - return h ? h->to : NULL;
> + return complex_variable_components->find_with_hash (in, uid).to;
> }
>
> /* Insert the pair UID, TO into the complex_variable_components hashtable.
> */
> @@ -94,14 +93,13 @@ cvc_lookup (unsigned int uid)
> static void
> cvc_insert (unsigned int uid, tree to)
> {
> - struct int_tree_map *h;
> - int_tree_map **loc;
> + int_tree_map h;
> + int_tree_map *loc;
>
> - h = XNEW (struct int_tree_map);
> - h->uid = uid;
> - h->to = to;
> + h.uid = uid;
> loc = complex_variable_components->find_slot_with_hash (h, uid, INSERT);
> - *loc = h;
> + loc->uid = uid;
> + loc->to = to;
> }
>
> /* Return true if T is not a zero constant. In the case of real values,
> diff --git a/gcc/tree-hasher.h b/gcc/tree-hasher.h
> index 6b28008..ae56a84 100644
> --- a/gcc/tree-hasher.h
> +++ b/gcc/tree-hasher.h
> @@ -30,28 +30,37 @@ struct int_tree_map {
>
> /* Hashtable helpers. */
>
> -struct int_tree_hasher : typed_free_remove <int_tree_map>
> +struct int_tree_hasher
> {
> typedef int_tree_map value_type;
> typedef int_tree_map compare_type;
> - static inline hashval_t hash (const value_type *);
> - static inline bool equal (const value_type *, const compare_type *);
> + typedef int store_values_directly;
> + static inline hashval_t hash (const value_type &);
> + static inline bool equal (const value_type &, const compare_type &);
> + static bool is_deleted (const value_type &v)
> + {
> + return v.to == reinterpret_cast<tree> (1);
> + }
> + static void mark_deleted (value_type &v) { v.to = reinterpret_cast<tree>
> (0x1); }
> + static bool is_empty (const value_type &v) { return v.to == NULL; }
> + static void mark_empty (value_type &v) { v.to = NULL; }
> + static void remove (value_type &) {}
> };
>
> /* Hash a UID in a int_tree_map. */
>
> inline hashval_t
> -int_tree_hasher::hash (const value_type *item)
> +int_tree_hasher::hash (const value_type &item)
> {
> - return item->uid;
> + return item.uid;
> }
>
> /* Return true if the uid in both int tree maps are equal. */
>
> inline bool
> -int_tree_hasher::equal (const value_type *a, const compare_type *b)
> +int_tree_hasher::equal (const value_type &a, const compare_type &b)
> {
> - return (a->uid == b->uid);
> + return (a.uid == b.uid);
> }
>
> typedef hash_table <int_tree_hasher> int_tree_htab_type;
> diff --git a/gcc/tree-into-ssa.c b/gcc/tree-into-ssa.c
> index 1cdcc2f..96255f9 100644
> --- a/gcc/tree-into-ssa.c
> +++ b/gcc/tree-into-ssa.c
> @@ -203,20 +203,21 @@ typedef struct var_info_d *var_info_p;
>
> struct var_info_hasher : typed_free_remove <var_info_d>
> {
> - typedef var_info_d value_type;
> - typedef var_info_d compare_type;
> - static inline hashval_t hash (const value_type *);
> - static inline bool equal (const value_type *, const compare_type *);
> + typedef var_info_d *value_type;
> + typedef var_info_d *compare_type;
> + typedef int store_values_directly;
> + static inline hashval_t hash (const value_type &);
> + static inline bool equal (const value_type &, const compare_type &);
> };
>
> inline hashval_t
> -var_info_hasher::hash (const value_type *p)
> +var_info_hasher::hash (const value_type &p)
> {
> return DECL_UID (p->var);
> }
>
> inline bool
> -var_info_hasher::equal (const value_type *p1, const compare_type *p2)
> +var_info_hasher::equal (const value_type &p1, const compare_type &p2)
> {
> return p1->var == p2->var;
> }
> diff --git a/gcc/tree-parloops.c b/gcc/tree-parloops.c
> index 3ef4aa6..0c486bb 100644
> --- a/gcc/tree-parloops.c
> +++ b/gcc/tree-parloops.c
> @@ -489,8 +489,6 @@ take_address_of (tree obj, tree type, edge entry,
> int_tree_htab_type *decl_address, gimple_stmt_iterator *gsi)
> {
> int uid;
> - int_tree_map **dslot;
> - struct int_tree_map ielt, *nielt;
> tree *var_p, name, addr;
> gimple stmt;
> gimple_seq stmts;
> @@ -511,9 +509,10 @@ take_address_of (tree obj, tree type, edge entry,
> in the address and share it for all accesses and addresses based
> on it. */
> uid = DECL_UID (TREE_OPERAND (TREE_OPERAND (*var_p, 0), 0));
> - ielt.uid = uid;
> - dslot = decl_address->find_slot_with_hash (&ielt, uid, INSERT);
> - if (!*dslot)
> + int_tree_map elt;
> + elt.uid = uid;
> + int_tree_map *slot = decl_address->find_slot (elt, INSERT);
> + if (!slot->to)
> {
> if (gsi == NULL)
> return NULL;
> @@ -527,13 +526,11 @@ take_address_of (tree obj, tree type, edge entry,
> stmt = gimple_build_assign (name, addr);
> gsi_insert_on_edge_immediate (entry, stmt);
>
> - nielt = XNEW (struct int_tree_map);
> - nielt->uid = uid;
> - nielt->to = name;
> - *dslot = nielt;
> + slot->uid = uid;
> + slot->to = name;
> }
> else
> - name = (*dslot)->to;
> + name = slot->to;
>
> /* Express the address in terms of the canonical SSA name. */
> TREE_OPERAND (*var_p, 0) = name;
> @@ -822,10 +819,10 @@ separate_decls_in_region_name (tree name,
> name_to_copy_table_type *name_copies,
> {
> tree copy, var, var_copy;
> unsigned idx, uid, nuid;
> - struct int_tree_map ielt, *nielt;
> + struct int_tree_map ielt;
> struct name_to_copy_elt elt, *nelt;
> name_to_copy_elt **slot;
> - int_tree_map **dslot;
> + int_tree_map *dslot;
>
> if (TREE_CODE (name) != SSA_NAME)
> return name;
> @@ -858,29 +855,25 @@ separate_decls_in_region_name (tree name,
> name_to_copy_table_type *name_copies,
>
> uid = DECL_UID (var);
> ielt.uid = uid;
> - dslot = decl_copies->find_slot_with_hash (&ielt, uid, INSERT);
> - if (!*dslot)
> + dslot = decl_copies->find_slot_with_hash (ielt, uid, INSERT);
> + if (!dslot->to)
> {
> var_copy = create_tmp_var (TREE_TYPE (var), get_name (var));
> DECL_GIMPLE_REG_P (var_copy) = DECL_GIMPLE_REG_P (var);
> - nielt = XNEW (struct int_tree_map);
> - nielt->uid = uid;
> - nielt->to = var_copy;
> - *dslot = nielt;
> + dslot->uid = uid;
> + dslot->to = var_copy;
>
> /* Ensure that when we meet this decl next time, we won't duplicate
> it again. */
> nuid = DECL_UID (var_copy);
> ielt.uid = nuid;
> - dslot = decl_copies->find_slot_with_hash (&ielt, nuid, INSERT);
> - gcc_assert (!*dslot);
> - nielt = XNEW (struct int_tree_map);
> - nielt->uid = nuid;
> - nielt->to = var_copy;
> - *dslot = nielt;
> + dslot = decl_copies->find_slot_with_hash (ielt, nuid, INSERT);
> + gcc_assert (!dslot->to);
> + dslot->uid = nuid;
> + dslot->to = var_copy;
> }
> else
> - var_copy = ((struct int_tree_map *) *dslot)->to;
> + var_copy = dslot->to;
>
> replace_ssa_name_symbol (copy, var_copy);
> return copy;
> @@ -944,7 +937,7 @@ separate_decls_in_region_debug (gimple stmt,
> struct int_tree_map ielt;
> struct name_to_copy_elt elt;
> name_to_copy_elt **slot;
> - int_tree_map **dslot;
> + int_tree_map *dslot;
>
> if (gimple_debug_bind_p (stmt))
> var = gimple_debug_bind_get_var (stmt);
> @@ -956,13 +949,13 @@ separate_decls_in_region_debug (gimple stmt,
> return true;
> gcc_assert (DECL_P (var) && SSA_VAR_P (var));
> ielt.uid = DECL_UID (var);
> - dslot = decl_copies->find_slot_with_hash (&ielt, ielt.uid, NO_INSERT);
> + dslot = decl_copies->find_slot_with_hash (ielt, ielt.uid, NO_INSERT);
> if (!dslot)
> return true;
> if (gimple_debug_bind_p (stmt))
> - gimple_debug_bind_set_var (stmt, ((struct int_tree_map *) *dslot)->to);
> + gimple_debug_bind_set_var (stmt, dslot->to);
> else if (gimple_debug_source_bind_p (stmt))
> - gimple_debug_source_bind_set_var (stmt, ((struct int_tree_map *)
> *dslot)->to);
> + gimple_debug_source_bind_set_var (stmt, dslot->to);
>
> FOR_EACH_PHI_OR_STMT_USE (use, stmt, oi, SSA_OP_USE)
> {
> diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
> index 6c581ba..61e75b6 100644
> --- a/gcc/tree-ssa-dom.c
> +++ b/gcc/tree-ssa-dom.c
> @@ -158,21 +158,22 @@ static void free_expr_hash_elt (void *);
>
> struct expr_elt_hasher
> {
> - typedef expr_hash_elt value_type;
> - typedef expr_hash_elt compare_type;
> - static inline hashval_t hash (const value_type *);
> - static inline bool equal (const value_type *, const compare_type *);
> - static inline void remove (value_type *);
> + typedef expr_hash_elt *value_type;
> + typedef expr_hash_elt *compare_type;
> + typedef int store_values_directly;
> + static inline hashval_t hash (const value_type &);
> + static inline bool equal (const value_type &, const compare_type &);
> + static inline void remove (value_type &);
> };
>
> inline hashval_t
> -expr_elt_hasher::hash (const value_type *p)
> +expr_elt_hasher::hash (const value_type &p)
> {
> return p->hash;
> }
>
> inline bool
> -expr_elt_hasher::equal (const value_type *p1, const compare_type *p2)
> +expr_elt_hasher::equal (const value_type &p1, const compare_type &p2)
> {
> gimple stmt1 = p1->stmt;
> const struct hashable_expr *expr1 = &p1->expr;
> @@ -211,7 +212,7 @@ expr_elt_hasher::equal (const value_type *p1, const
> compare_type *p2)
> /* Delete an expr_hash_elt and reclaim its storage. */
>
> inline void
> -expr_elt_hasher::remove (value_type *element)
> +expr_elt_hasher::remove (value_type &element)
> {
> free_expr_hash_elt (element);
> }
> diff --git a/gcc/tree-ssa-reassoc.c b/gcc/tree-ssa-reassoc.c
> index 4d0d6c2..4903f48 100644
> --- a/gcc/tree-ssa-reassoc.c
> +++ b/gcc/tree-ssa-reassoc.c
> @@ -1023,32 +1023,36 @@ static vec<oecount> cvec;
>
> /* Oecount hashtable helpers. */
>
> -struct oecount_hasher : typed_noop_remove <void>
> +struct oecount_hasher
> {
> - /* Note that this hash table stores integers, not pointers.
> - So, observe the casting in the member functions. */
> - typedef void value_type;
> - typedef void compare_type;
> - static inline hashval_t hash (const value_type *);
> - static inline bool equal (const value_type *, const compare_type *);
> + typedef int value_type;
> + typedef int compare_type;
> + typedef int store_values_directly;
> + static inline hashval_t hash (const value_type &);
> + static inline bool equal (const value_type &, const compare_type &);
> + static bool is_deleted (int &v) { return v == 1; }
> + static void mark_deleted (int &e) { e = 1; }
> + static bool is_empty (int &v) { return v == 0; }
> + static void mark_empty (int &e) { e = 0; }
> + static void remove (int &) {}
> };
>
> /* Hash function for oecount. */
>
> inline hashval_t
> -oecount_hasher::hash (const value_type *p)
> +oecount_hasher::hash (const value_type &p)
> {
> - const oecount *c = &cvec[(size_t)p - 42];
> + const oecount *c = &cvec[p - 42];
> return htab_hash_pointer (c->op) ^ (hashval_t)c->oecode;
> }
>
> /* Comparison function for oecount. */
>
> inline bool
> -oecount_hasher::equal (const value_type *p1, const compare_type *p2)
> +oecount_hasher::equal (const value_type &p1, const compare_type &p2)
> {
> - const oecount *c1 = &cvec[(size_t)p1 - 42];
> - const oecount *c2 = &cvec[(size_t)p2 - 42];
> + const oecount *c1 = &cvec[p1 - 42];
> + const oecount *c2 = &cvec[p2 - 42];
> return (c1->oecode == c2->oecode
> && c1->op == c2->op);
> }
> @@ -1473,23 +1477,23 @@ undistribute_ops_list (enum tree_code opcode,
> FOR_EACH_VEC_ELT (subops[i], j, oe1)
> {
> oecount c;
> - void **slot;
> - size_t idx;
> + int *slot;
> + int idx;
> c.oecode = oecode;
> c.cnt = 1;
> c.id = next_oecount_id++;
> c.op = oe1->op;
> cvec.safe_push (c);
> idx = cvec.length () + 41;
> - slot = ctable.find_slot ((void *)idx, INSERT);
> + slot = ctable.find_slot (idx, INSERT);
> if (!*slot)
> {
> - *slot = (void *)idx;
> + *slot = idx;
> }
> else
> {
> cvec.pop ();
> - cvec[(size_t)*slot - 42].cnt++;
> + cvec[*slot - 42].cnt++;
> }
> }
> }
> diff --git a/gcc/tree-vectorizer.c b/gcc/tree-vectorizer.c
> index e553e28..0ad22c7 100644
> --- a/gcc/tree-vectorizer.c
> +++ b/gcc/tree-vectorizer.c
> @@ -548,14 +548,14 @@ vectorize_loops (void)
> for (hash_table<simd_array_to_simduid>::iterator iter
> = simd_array_to_simduid_htab->begin ();
> iter != simd_array_to_simduid_htab->end (); ++iter)
> - if ((*iter).simduid != -1U)
> + if ((*iter)->simduid != -1U)
> {
> - tree decl = (*iter).decl;
> + tree decl = (*iter)->decl;
> int vf = 1;
> if (simduid_to_vf_htab)
> {
> simduid_to_vf *p = NULL, data;
> - data.simduid = (*iter).simduid;
> + data.simduid = (*iter)->simduid;
> p = simduid_to_vf_htab->find (&data);
> if (p)
> vf = p->vf;
> --
> 2.0.0
>
