On Wed, 15 Aug 2012, Michael Matz wrote:
> Hi,
>
> On Wed, 15 Aug 2012, Richard Guenther wrote:
>
> > Like the following, only the coverage.c use is converted. I've never
> > seen template function arguments anywhere and having to repeat them all
> > over the place is really really ugly (yes, even if only in the
> > implementation).
> >
> > This goes with static member functions and not wrapping any data. It
> > goes away with the requirement of having externally visible global
> > functions for the hash/compare functions as well (which was ugly
> > anyway).
> >
> > Comments?
>
> Well, it looks nicer than what's there currently. As the element
> functions now are scoped and normal member functions, they should be named
> with lower case characters of course. I do like that the hash table would
> then only have one real template argument; the Allocator, well, no better
> idea comes to my mind.
Yeah. Updated patch below, all users converted. I probably missed
to revert some of the globalizations of hash/compare fns.
Comments?
Richard.
Index: gcc/hash-table.h
===================================================================
*** gcc/hash-table.h.orig 2012-08-15 15:39:34.000000000 +0200
--- gcc/hash-table.h 2012-08-15 16:17:06.613628039 +0200
*************** xcallocator <Type>::data_free (Type *mem
*** 83,127 ****
}
- /* A common function for hashing a CANDIDATE typed pointer. */
-
template <typename Element>
! inline hashval_t
! typed_pointer_hash (const Element *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. */
! return (hashval_t) ((intptr_t)candidate >> 3);
! }
- /* A common function for comparing an EXISTING and CANDIDATE typed pointers
- for equality. */
template <typename Element>
! inline int
! typed_pointer_equal (const Element *existing, const Element * candidate)
{
! return existing == candidate;
! }
! /* A common function for doing nothing on removing a RETIRED slot. */
template <typename Element>
! inline void
! typed_null_remove (Element *retired ATTRIBUTE_UNUSED)
{
}
-
- /* A common function for using free on removing a RETIRED slot. */
-
template <typename Element>
! inline void
! typed_free_remove (Element *retired)
{
! free (retired);
}
--- 83,132 ----
}
template <typename Element>
! class typed_free_remove
{
! public:
! static inline void remove (Element *p) { free (p); }
! };
+ template <typename Element>
+ class typed_noop_remove
+ {
+ public:
+ static inline void remove (Element *) {}
+ };
+ /* Pointer hash. */
template <typename Element>
! class pointer_hash : public typed_noop_remove <Element>
{
! public:
! typedef Element Element_t;
+ static inline hashval_t
+ hash (const Element_t *);
! static inline int
! equal (const Element_t *existing, const Element_t * candidate);
! };
template <typename Element>
! inline hashval_t
! pointer_hash<Element>::hash (const Element_t *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. */
+ return (hashval_t) ((intptr_t)candidate >> 3);
}
template <typename Element>
! inline int
! pointer_hash<Element>::equal (const Element_t *existing,
! const Element_t *candidate)
{
! return existing == candidate;
}
*************** struct hash_table_control
*** 180,194 ****
The table stores elements of type Element.
! It hashes elements with the Hash function.
The table currently works with relatively weak hash functions.
Use typed_pointer_hash <Element> when hashing pointers instead of
objects.
! It compares elements with the Equal function.
Two elements with the same hash may not be equal.
Use typed_pointer_equal <Element> when hashing pointers instead of
objects.
! It removes elements with the Remove function.
This feature is useful for freeing memory.
Use typed_null_remove <Element> when not freeing objects.
Use typed_free_remove <Element> when doing a simple object free.
--- 185,199 ----
The table stores elements of type Element.
! It hashes elements with the hash function.
The table currently works with relatively weak hash functions.
Use typed_pointer_hash <Element> when hashing pointers instead of
objects.
! It compares elements with the equal function.
Two elements with the same hash may not be equal.
Use typed_pointer_equal <Element> when hashing pointers instead of
objects.
! It removes elements with the remove function.
This feature is useful for freeing memory.
Use typed_null_remove <Element> when not freeing objects.
Use typed_free_remove <Element> when doing a simple object free.
*************** struct hash_table_control
*** 199,243 ****
*/
template <typename Element,
- hashval_t (*Hash) (const Element *candidate),
- int (*Equal) (const Element *existing, const Element * candidate),
- void (*Remove) (Element *retired),
template <typename Type> class Allocator = xcallocator>
class hash_table
{
private:
! hash_table_control <Element> *htab;
!
! Element **find_empty_slot_for_expand (hashval_t hash);
void expand ();
public:
-
hash_table ();
void create (size_t initial_slots);
bool is_created ();
void dispose ();
! Element *find (Element *comparable);
! Element *find_with_hash (Element *comparable, hashval_t hash);
! Element **find_slot (Element *comparable, enum insert_option insert);
! Element **find_slot_with_hash (Element *comparable, hashval_t hash,
! enum insert_option insert);
void empty ();
! void clear_slot (Element **slot);
! void remove_elt (Element *comparable);
! void remove_elt_with_hash (Element *comparable, hashval_t hash);
size_t size();
size_t elements();
double collisions();
template <typename Argument,
! int (*Callback) (Element **slot, Argument argument)>
void traverse_noresize (Argument argument);
template <typename Argument,
! int (*Callback) (Element **slot, Argument argument)>
void traverse (Argument argument);
};
--- 204,245 ----
*/
template <typename Element,
template <typename Type> class Allocator = xcallocator>
class hash_table
{
+ public:
+ typedef typename Element::Element_t Element_t;
private:
+ hash_table_control <Element_t> *htab;
! Element_t **find_empty_slot_for_expand (hashval_t hash);
void expand ();
public:
hash_table ();
void create (size_t initial_slots);
bool is_created ();
void dispose ();
! Element_t *find (Element_t *comparable);
! Element_t *find_with_hash (Element_t *comparable, hashval_t hash);
! Element_t **find_slot (Element_t *comparable, enum insert_option insert);
! Element_t **find_slot_with_hash (Element_t *comparable, hashval_t hash,
! enum insert_option insert);
void empty ();
! void clear_slot (Element_t **slot);
! void remove_elt (Element_t *comparable);
! void remove_elt_with_hash (Element_t *comparable, hashval_t hash);
size_t size();
size_t elements();
double collisions();
template <typename Argument,
! int (*Callback) (Element_t **slot, Argument argument)>
void traverse_noresize (Argument argument);
template <typename Argument,
! int (*Callback) (Element_t **slot, Argument argument)>
void traverse (Argument argument);
};
*************** public:
*** 245,256 ****
/* Construct the hash table. The only useful operation next is create. */
template <typename Element,
- hashval_t (*Hash) (const Element *candidate),
- int (*Equal) (const Element *existing, const Element * candidate),
- void (*Remove) (Element *retired),
template <typename Type> class Allocator>
inline
! hash_table <Element, Hash, Equal, Remove, Allocator>::hash_table ()
: htab (NULL)
{
}
--- 247,255 ----
/* Construct the hash table. The only useful operation next is create. */
template <typename Element,
template <typename Type> class Allocator>
inline
! hash_table <Element, Allocator>::hash_table ()
: htab (NULL)
{
}
*************** hash_table <Element, Hash, Equal, Remove
*** 259,270 ****
/* See if the table has been created, as opposed to constructed. */
template <typename Element,
- hashval_t (*Hash) (const Element *candidate),
- int (*Equal) (const Element *existing, const Element * candidate),
- void (*Remove) (Element *retired),
template <typename Type> class Allocator>
inline bool
! hash_table <Element, Hash, Equal, Remove, Allocator>::is_created ()
{
return htab != NULL;
}
--- 258,266 ----
/* See if the table has been created, as opposed to constructed. */
template <typename Element,
template <typename Type> class Allocator>
inline bool
! hash_table <Element, Allocator>::is_created ()
{
return htab != NULL;
}
*************** hash_table <Element, Hash, Equal, Remove
*** 273,328 ****
/* Like find_with_hash, but compute the hash value from the element. */
template <typename Element,
- hashval_t (*Hash) (const Element *candidate),
- int (*Equal) (const Element *existing, const Element * candidate),
- void (*Remove) (Element *retired),
template <typename Type> class Allocator>
! inline Element *
! hash_table <Element, Hash, Equal, Remove, Allocator>::find (Element
*comparable)
{
! return find_with_hash (comparable, Hash (comparable));
}
/* Like find_slot_with_hash, but compute the hash value from the element. */
template <typename Element,
! hashval_t (*Hash) (const Element *candidate),
! int (*Equal) (const Element *existing, const Element * candidate),
! void (*Remove) (Element *retired),
! template <typename Type> class Allocator>
! inline Element **
! hash_table <Element, Hash, Equal, Remove, Allocator>
! ::find_slot (Element *comparable, enum insert_option insert)
{
! return find_slot_with_hash (comparable, Hash (comparable), insert);
}
/* Like remove_elt_with_hash, but compute the hash value from the element. */
template <typename Element,
- hashval_t (*Hash) (const Element *candidate),
- int (*Equal) (const Element *existing, const Element * candidate),
- void (*Remove) (Element *retired),
template <typename Type> class Allocator>
inline void
! hash_table <Element, Hash, Equal, Remove, Allocator>
! ::remove_elt (Element *comparable)
{
! remove_elt_with_hash (comparable, Hash (comparable));
}
/* Return the current size of this hash table. */
template <typename Element,
- hashval_t (*Hash) (const Element *candidate),
- int (*Equal) (const Element *existing, const Element * candidate),
- void (*Remove) (Element *retired),
template <typename Type> class Allocator>
inline size_t
! hash_table <Element, Hash, Equal, Remove, Allocator>::size()
{
return htab->size;
}
--- 269,312 ----
/* Like find_with_hash, but compute the hash value from the element. */
template <typename Element,
template <typename Type> class Allocator>
! inline typename Element::Element_t *
! hash_table <Element, Allocator>::find (Element_t *comparable)
{
! return find_with_hash (comparable, Element::hash (comparable));
}
/* Like find_slot_with_hash, but compute the hash value from the element. */
template <typename Element,
! template <typename Type> class Allocator>
! inline typename Element::Element_t **
! hash_table <Element, Allocator>
! ::find_slot (Element_t *comparable, enum insert_option insert)
{
! return find_slot_with_hash (comparable, Element::hash (comparable), insert);
}
/* Like remove_elt_with_hash, but compute the hash value from the element. */
template <typename Element,
template <typename Type> class Allocator>
inline void
! hash_table <Element, Allocator>
! ::remove_elt (Element_t *comparable)
{
! remove_elt_with_hash (comparable, Element::hash (comparable));
}
/* Return the current size of this hash table. */
template <typename Element,
template <typename Type> class Allocator>
inline size_t
! hash_table <Element, Allocator>::size()
{
return htab->size;
}
*************** hash_table <Element, Hash, Equal, Remove
*** 331,342 ****
/* Return the current number of elements in this hash table. */
template <typename Element,
- hashval_t (*Hash) (const Element *candidate),
- int (*Equal) (const Element *existing, const Element * candidate),
- void (*Remove) (Element *retired),
template <typename Type> class Allocator>
inline size_t
! hash_table <Element, Hash, Equal, Remove, Allocator>::elements()
{
return htab->n_elements - htab->n_deleted;
}
--- 315,323 ----
/* Return the current number of elements in this hash table. */
template <typename Element,
template <typename Type> class Allocator>
inline size_t
! hash_table <Element, Allocator>::elements()
{
return htab->n_elements - htab->n_deleted;
}
*************** hash_table <Element, Hash, Equal, Remove
*** 346,357 ****
hash table. */
template <typename Element,
- hashval_t (*Hash) (const Element *candidate),
- int (*Equal) (const Element *existing, const Element * candidate),
- void (*Remove) (Element *retired),
template <typename Type> class Allocator>
inline double
! hash_table <Element, Hash, Equal, Remove, Allocator>::collisions()
{
if (htab->searches == 0)
return 0.0;
--- 327,335 ----
hash table. */
template <typename Element,
template <typename Type> class Allocator>
inline double
! hash_table <Element, Allocator>::collisions()
{
if (htab->searches == 0)
return 0.0;
*************** hash_table <Element, Hash, Equal, Remove
*** 363,383 ****
/* Create a hash table with at least the given number of INITIAL_SLOTS. */
template <typename Element,
- hashval_t (*Hash) (const Element *candidate),
- int (*Equal) (const Element *existing, const Element * candidate),
- void (*Remove) (Element *retired),
template <typename Type> class Allocator>
void
! hash_table <Element, Hash, Equal, Remove, Allocator>::create (size_t size)
{
unsigned int size_prime_index;
size_prime_index = hash_table_higher_prime_index (size);
size = prime_tab[size_prime_index].prime;
! htab = Allocator <hash_table_control <Element> > ::control_alloc (1);
gcc_assert (htab != NULL);
! htab->entries = Allocator <Element*> ::data_alloc (size);
gcc_assert (htab->entries != NULL);
htab->size = size;
htab->size_prime_index = size_prime_index;
--- 341,358 ----
/* Create a hash table with at least the given number of INITIAL_SLOTS. */
template <typename Element,
template <typename Type> class Allocator>
void
! hash_table <Element, Allocator>::create (size_t size)
{
unsigned int size_prime_index;
size_prime_index = hash_table_higher_prime_index (size);
size = prime_tab[size_prime_index].prime;
! htab = Allocator <hash_table_control <Element_t> > ::control_alloc (1);
gcc_assert (htab != NULL);
! htab->entries = Allocator <Element_t*> ::data_alloc (size);
gcc_assert (htab->entries != NULL);
htab->size = size;
htab->size_prime_index = size_prime_index;
*************** hash_table <Element, Hash, Equal, Remove
*** 388,432 ****
the non-created state. Naturally the hash table must already exist. */
template <typename Element,
- hashval_t (*Hash) (const Element *candidate),
- int (*Equal) (const Element *existing, const Element * candidate),
- void (*Remove) (Element *retired),
template <typename Type> class Allocator>
void
! hash_table <Element, Hash, Equal, Remove, Allocator>::dispose ()
{
size_t size = htab->size;
! Element **entries = htab->entries;
for (int i = size - 1; i >= 0; i--)
if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
! Remove (entries[i]);
! Allocator <Element *> ::data_free (entries);
! Allocator <hash_table_control <Element> > ::control_free (htab);
htab = NULL;
}
/* 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 Element,
- hashval_t (*Hash) (const Element *candidate),
- int (*Equal) (const Element *existing, const Element * candidate),
- void (*Remove) (Element *retired),
template <typename Type> class Allocator>
! Element **
! hash_table <Element, Hash, Equal, Remove, Allocator>
::find_empty_slot_for_expand (hashval_t hash)
{
hashval_t index = hash_table_mod1 (hash, htab->size_prime_index);
size_t size = htab->size;
! Element **slot = htab->entries + index;
hashval_t hash2;
if (*slot == HTAB_EMPTY_ENTRY)
--- 363,401 ----
the non-created state. Naturally the hash table must already exist. */
template <typename Element,
template <typename Type> class Allocator>
void
! hash_table <Element, Allocator>::dispose ()
{
size_t size = htab->size;
! Element_t **entries = htab->entries;
for (int i = size - 1; i >= 0; i--)
if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
! Element::remove (entries[i]);
! Allocator <Element_t *> ::data_free (entries);
! Allocator <hash_table_control <Element_t> > ::control_free (htab);
htab = NULL;
}
/* 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 Element,
template <typename Type> class Allocator>
! typename Element::Element_t **
! hash_table <Element, Allocator>
::find_empty_slot_for_expand (hashval_t hash)
{
hashval_t index = hash_table_mod1 (hash, htab->size_prime_index);
size_t size = htab->size;
! Element_t **slot = htab->entries + index;
hashval_t hash2;
if (*slot == HTAB_EMPTY_ENTRY)
*************** hash_table <Element, Hash, Equal, Remove
*** 458,474 ****
will abort. */
template <typename Element,
- hashval_t (*Hash) (const Element *candidate),
- int (*Equal) (const Element *existing, const Element * candidate),
- void (*Remove) (Element *retired),
template <typename Type> class Allocator>
void
! hash_table <Element, Hash, Equal, Remove, Allocator>::expand ()
{
! Element **oentries;
! Element **olimit;
! Element **p;
! Element **nentries;
size_t nsize, osize, elts;
unsigned int oindex, nindex;
--- 427,440 ----
will abort. */
template <typename Element,
template <typename Type> class Allocator>
void
! hash_table <Element, Allocator>::expand ()
{
! Element_t **oentries;
! Element_t **olimit;
! Element_t **p;
! Element_t **nentries;
size_t nsize, osize, elts;
unsigned int oindex, nindex;
*************** hash_table <Element, Hash, Equal, Remove
*** 491,497 ****
nsize = osize;
}
! nentries = Allocator <Element *> ::data_alloc (nsize);
gcc_assert (nentries != NULL);
htab->entries = nentries;
htab->size = nsize;
--- 457,463 ----
nsize = osize;
}
! nentries = Allocator <Element_t *> ::data_alloc (nsize);
gcc_assert (nentries != NULL);
htab->entries = nentries;
htab->size = nsize;
*************** hash_table <Element, Hash, Equal, Remove
*** 502,512 ****
p = oentries;
do
{
! Element *x = *p;
if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
{
! Element **q = find_empty_slot_for_expand (Hash (x));
*q = x;
}
--- 468,478 ----
p = oentries;
do
{
! Element_t *x = *p;
if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
{
! Element_t **q = find_empty_slot_for_expand (Element::hash (x));
*q = x;
}
*************** hash_table <Element, Hash, Equal, Remove
*** 515,521 ****
}
while (p < olimit);
! Allocator <Element *> ::data_free (oentries);
}
--- 481,487 ----
}
while (p < olimit);
! Allocator <Element_t *> ::data_free (oentries);
}
*************** hash_table <Element, Hash, Equal, Remove
*** 524,540 ****
be used to insert or delete an element. */
template <typename Element,
! hashval_t (*Hash) (const Element *candidate),
! int (*Equal) (const Element *existing, const Element * candidate),
! void (*Remove) (Element *retired),
! template <typename Type> class Allocator>
! Element *
! hash_table <Element, Hash, Equal, Remove, Allocator>
! ::find_with_hash (Element *comparable, hashval_t hash)
{
hashval_t index, hash2;
size_t size;
! Element *entry;
htab->searches++;
size = htab->size;
--- 490,503 ----
be used to insert or delete an element. */
template <typename Element,
! template <typename Type> class Allocator>
! typename Element::Element_t *
! hash_table <Element, Allocator>
! ::find_with_hash (Element_t *comparable, hashval_t hash)
{
hashval_t index, hash2;
size_t size;
! Element_t *entry;
htab->searches++;
size = htab->size;
*************** hash_table <Element, Hash, Equal, Remove
*** 542,548 ****
entry = htab->entries[index];
if (entry == HTAB_EMPTY_ENTRY
! || (entry != HTAB_DELETED_ENTRY && Equal (entry, comparable)))
return entry;
hash2 = hash_table_mod2 (hash, htab->size_prime_index);
--- 505,511 ----
entry = htab->entries[index];
if (entry == HTAB_EMPTY_ENTRY
! || (entry != HTAB_DELETED_ENTRY && Element::equal (entry, comparable)))
return entry;
hash2 = hash_table_mod2 (hash, htab->size_prime_index);
*************** hash_table <Element, Hash, Equal, Remove
*** 555,561 ****
entry = htab->entries[index];
if (entry == HTAB_EMPTY_ENTRY
! || (entry != HTAB_DELETED_ENTRY && Equal (entry, comparable)))
return entry;
}
}
--- 518,524 ----
entry = htab->entries[index];
if (entry == HTAB_EMPTY_ENTRY
! || (entry != HTAB_DELETED_ENTRY && Element::equal (entry,
comparable)))
return entry;
}
}
*************** hash_table <Element, Hash, Equal, Remove
*** 570,588 ****
entry, NULL may be returned if memory allocation fails. */
template <typename Element,
! hashval_t (*Hash) (const Element *candidate),
! int (*Equal) (const Element *existing, const Element * candidate),
! void (*Remove) (Element *retired),
! template <typename Type> class Allocator>
! Element **
! hash_table <Element, Hash, Equal, Remove, Allocator>
! ::find_slot_with_hash (Element *comparable, hashval_t hash,
enum insert_option insert)
{
! Element **first_deleted_slot;
hashval_t index, hash2;
size_t size;
! Element *entry;
size = htab->size;
if (insert == INSERT && size * 3 <= htab->n_elements * 4)
--- 533,548 ----
entry, NULL may be returned if memory allocation fails. */
template <typename Element,
! template <typename Type> class Allocator>
! typename Element::Element_t **
! hash_table <Element, Allocator>
! ::find_slot_with_hash (Element_t *comparable, hashval_t hash,
enum insert_option insert)
{
! Element_t **first_deleted_slot;
hashval_t index, hash2;
size_t size;
! Element_t *entry;
size = htab->size;
if (insert == INSERT && size * 3 <= htab->n_elements * 4)
*************** hash_table <Element, Hash, Equal, Remove
*** 601,607 ****
goto empty_entry;
else if (entry == HTAB_DELETED_ENTRY)
first_deleted_slot = &htab->entries[index];
! else if (Equal (entry, comparable))
return &htab->entries[index];
hash2 = hash_table_mod2 (hash, htab->size_prime_index);
--- 561,567 ----
goto empty_entry;
else if (entry == HTAB_DELETED_ENTRY)
first_deleted_slot = &htab->entries[index];
! else if (Element::equal (entry, comparable))
return &htab->entries[index];
hash2 = hash_table_mod2 (hash, htab->size_prime_index);
*************** hash_table <Element, Hash, Equal, Remove
*** 620,626 ****
if (!first_deleted_slot)
first_deleted_slot = &htab->entries[index];
}
! else if (Equal (entry, comparable))
return &htab->entries[index];
}
--- 580,586 ----
if (!first_deleted_slot)
first_deleted_slot = &htab->entries[index];
}
! else if (Element::equal (entry, comparable))
return &htab->entries[index];
}
*************** hash_table <Element, Hash, Equal, Remove
*** 631,637 ****
if (first_deleted_slot)
{
htab->n_deleted--;
! *first_deleted_slot = static_cast <Element *> (HTAB_EMPTY_ENTRY);
return first_deleted_slot;
}
--- 591,597 ----
if (first_deleted_slot)
{
htab->n_deleted--;
! *first_deleted_slot = static_cast <Element_t *> (HTAB_EMPTY_ENTRY);
return first_deleted_slot;
}
*************** hash_table <Element, Hash, Equal, Remove
*** 643,662 ****
/* This function clears all entries in the given hash table. */
template <typename Element,
- hashval_t (*Hash) (const Element *candidate),
- int (*Equal) (const Element *existing, const Element * candidate),
- void (*Remove) (Element *retired),
template <typename Type> class Allocator>
void
! hash_table <Element, Hash, Equal, Remove, Allocator>::empty ()
{
size_t size = htab_size (htab);
! Element **entries = htab->entries;
int i;
for (i = size - 1; i >= 0; i--)
if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
! Remove (entries[i]);
/* Instead of clearing megabyte, downsize the table. */
if (size > 1024*1024 / sizeof (PTR))
--- 603,619 ----
/* This function clears all entries in the given hash table. */
template <typename Element,
template <typename Type> class Allocator>
void
! hash_table <Element, Allocator>::empty ()
{
size_t size = htab_size (htab);
! Element_t **entries = htab->entries;
int i;
for (i = size - 1; i >= 0; i--)
if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
! Element::remove (entries[i]);
/* Instead of clearing megabyte, downsize the table. */
if (size > 1024*1024 / sizeof (PTR))
*************** hash_table <Element, Hash, Equal, Remove
*** 664,676 ****
int nindex = hash_table_higher_prime_index (1024 / sizeof (PTR));
int nsize = prime_tab[nindex].prime;
! Allocator <Element *> ::data_free (htab->entries);
! htab->entries = Allocator <Element *> ::data_alloc (nsize);
htab->size = nsize;
htab->size_prime_index = nindex;
}
else
! memset (entries, 0, size * sizeof (Element *));
htab->n_deleted = 0;
htab->n_elements = 0;
}
--- 621,633 ----
int nindex = hash_table_higher_prime_index (1024 / sizeof (PTR));
int nsize = prime_tab[nindex].prime;
! Allocator <Element_t *> ::data_free (htab->entries);
! htab->entries = Allocator <Element_t *> ::data_alloc (nsize);
htab->size = nsize;
htab->size_prime_index = nindex;
}
else
! memset (entries, 0, size * sizeof (Element_t *));
htab->n_deleted = 0;
htab->n_elements = 0;
}
*************** hash_table <Element, Hash, Equal, Remove
*** 681,699 ****
again. */
template <typename Element,
- hashval_t (*Hash) (const Element *candidate),
- int (*Equal) (const Element *existing, const Element * candidate),
- void (*Remove) (Element *retired),
template <typename Type> class Allocator>
void
! hash_table <Element, Hash, Equal, Remove, Allocator>
! ::clear_slot (Element **slot)
{
if (slot < htab->entries || slot >= htab->entries + htab->size
|| *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)
abort ();
! Remove (*slot);
*slot = HTAB_DELETED_ENTRY;
htab->n_deleted++;
--- 638,653 ----
again. */
template <typename Element,
template <typename Type> class Allocator>
void
! hash_table <Element, Allocator>
! ::clear_slot (Element_t **slot)
{
if (slot < htab->entries || slot >= htab->entries + htab->size
|| *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)
abort ();
! Element::remove (*slot);
*slot = HTAB_DELETED_ENTRY;
htab->n_deleted++;
*************** hash_table <Element, Hash, Equal, Remove
*** 705,727 ****
matching element in the hash table, this function does nothing. */
template <typename Element,
- hashval_t (*Hash) (const Element *candidate),
- int (*Equal) (const Element *existing, const Element * candidate),
- void (*Remove) (Element *retired),
template <typename Type> class Allocator>
void
! hash_table <Element, Hash, Equal, Remove, Allocator>
! ::remove_elt_with_hash (Element *comparable, hashval_t hash)
{
! Element **slot;
slot = find_slot_with_hash (comparable, hash, NO_INSERT);
if (*slot == HTAB_EMPTY_ENTRY)
return;
! Remove (*slot);
! *slot = static_cast <Element *> (HTAB_DELETED_ENTRY);
htab->n_deleted++;
}
--- 659,678 ----
matching element in the hash table, this function does nothing. */
template <typename Element,
template <typename Type> class Allocator>
void
! hash_table <Element, Allocator>
! ::remove_elt_with_hash (Element_t *comparable, hashval_t hash)
{
! Element_t **slot;
slot = find_slot_with_hash (comparable, hash, NO_INSERT);
if (*slot == HTAB_EMPTY_ENTRY)
return;
! Element::remove (*slot);
! *slot = static_cast <Element_t *> (HTAB_DELETED_ENTRY);
htab->n_deleted++;
}
*************** hash_table <Element, Hash, Equal, Remove
*** 731,755 ****
ARGUMENT is passed as CALLBACK's second argument. */
template <typename Element,
- hashval_t (*Hash) (const Element *candidate),
- int (*Equal) (const Element *existing, const Element * candidate),
- void (*Remove) (Element *retired),
template <typename Type> class Allocator>
template <typename Argument,
! int (*Callback) (Element **slot, Argument argument)>
void
! hash_table <Element, Hash, Equal, Remove, Allocator>
::traverse_noresize (Argument argument)
{
! Element **slot;
! Element **limit;
slot = htab->entries;
limit = slot + htab->size;
do
{
! Element *x = *slot;
if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
if (! Callback (slot, argument))
--- 682,703 ----
ARGUMENT is passed as CALLBACK's second argument. */
template <typename Element,
template <typename Type> class Allocator>
template <typename Argument,
! int (*Callback) (typename Element::Element_t **slot, Argument
argument)>
void
! hash_table <Element, Allocator>
::traverse_noresize (Argument argument)
{
! Element_t **slot;
! Element_t **limit;
slot = htab->entries;
limit = slot + htab->size;
do
{
! Element_t *x = *slot;
if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
if (! Callback (slot, argument))
*************** hash_table <Element, Hash, Equal, Remove
*** 763,776 ****
to improve effectivity of subsequent calls. */
template <typename Element,
- hashval_t (*Hash) (const Element *candidate),
- int (*Equal) (const Element *existing, const Element * candidate),
- void (*Remove) (Element *retired),
template <typename Type> class Allocator>
template <typename Argument,
! int (*Callback) (Element **slot, Argument argument)>
void
! hash_table <Element, Hash, Equal, Remove, Allocator>
::traverse (Argument argument)
{
size_t size = htab->size;
--- 711,721 ----
to improve effectivity of subsequent calls. */
template <typename Element,
template <typename Type> class Allocator>
template <typename Argument,
! int (*Callback) (typename Element::Element_t **slot, Argument
argument)>
void
! hash_table <Element, Allocator>
::traverse (Argument argument)
{
size_t size = htab->size;
Index: gcc/coverage.c
===================================================================
*** gcc/coverage.c.orig 2012-08-15 15:39:34.000000000 +0200
--- gcc/coverage.c 2012-08-15 16:12:58.471636654 +0200
*************** get_gcov_unsigned_t (void)
*** 143,172 ****
return lang_hooks.types.type_for_mode (mode, true);
}
! inline hashval_t
! coverage_counts_entry_hash (const counts_entry_t *entry)
! {
! return entry->ident * GCOV_COUNTERS + entry->ctr;
! }
!
! inline int
! coverage_counts_entry_eq (const counts_entry_t *entry1,
! const counts_entry_t *entry2)
! {
! return entry1->ident == entry2->ident && entry1->ctr == entry2->ctr;
! }
!
! inline void
! coverage_counts_entry_del (counts_entry_t *entry)
! {
! free (entry->counts);
! free (entry);
! }
/* Hash table of count data. */
! static hash_table <counts_entry_t, coverage_counts_entry_hash,
! coverage_counts_entry_eq, coverage_counts_entry_del>
! counts_hash;
/* Read in the counts file, if available. */
--- 143,172 ----
return lang_hooks.types.type_for_mode (mode, true);
}
! /* Hash functions for counts_entry. */
! class counts_entry_hash {
! public:
! typedef counts_entry_t Element_t;
! static inline int equal (const counts_entry_t *entry1,
! const counts_entry_t *entry2)
! {
! return entry1->ident == entry2->ident && entry1->ctr == entry2->ctr;
! }
! static inline hashval_t
! hash (const counts_entry_t *entry)
! {
! return entry->ident * GCOV_COUNTERS + entry->ctr;
! }
! static inline void
! remove (counts_entry_t *entry)
! {
! free (entry->counts);
! free (entry);
! }
! };
/* Hash table of count data. */
! static hash_table <counts_entry_hash> counts_hash;
/* Read in the counts file, if available. */
Index: gcc/tree-ssa-ccp.c
===================================================================
*** gcc/tree-ssa-ccp.c.orig 2012-08-15 10:20:31.000000000 +0200
--- gcc/tree-ssa-ccp.c 2012-08-15 15:45:45.896693215 +0200
*************** evaluate_stmt (gimple stmt)
*** 1688,1697 ****
return val;
}
! typedef hash_table <gimple_statement_d,
typed_pointer_hash<gimple_statement_d>,
! typed_pointer_equal<gimple_statement_d>,
! typed_null_remove<gimple_statement_d> >
! gimple_htab;
/* Given a BUILT_IN_STACK_SAVE value SAVED_VAL, insert a clobber of VAR before
each matching BUILT_IN_STACK_RESTORE. Mark visited phis in VISITED. */
--- 1688,1694 ----
return val;
}
! typedef hash_table <pointer_hash <gimple_statement_d> > gimple_htab;
/* Given a BUILT_IN_STACK_SAVE value SAVED_VAL, insert a clobber of VAR before
each matching BUILT_IN_STACK_RESTORE. Mark visited phis in VISITED. */
Index: gcc/tree-ssa-coalesce.c
===================================================================
*** gcc/tree-ssa-coalesce.c.orig 2012-08-15 10:20:33.000000000 +0200
--- gcc/tree-ssa-coalesce.c 2012-08-15 16:14:56.051632549 +0200
*************** coalesce_partitions (var_map map, ssa_co
*** 1258,1278 ****
}
}
! /* Returns a hash code for N. */
!
! inline hashval_t
! hash_ssa_name_by_var (const_tree n)
! {
! return (hashval_t) htab_hash_pointer (SSA_NAME_VAR (n));
! }
!
! /* Returns nonzero if N1 and N2 are equal. */
!
! inline int
! eq_ssa_name_by_var (const_tree n1, const_tree n2)
! {
! return SSA_NAME_VAR (n1) == SSA_NAME_VAR (n2);
! }
/* Reduce the number of copies by coalescing variables in the function.
Return
a partition map with the resulting coalesces. */
--- 1258,1276 ----
}
}
! /* SSA_NAME_VAR hash. */
! class ssa_name_var_hash : public typed_noop_remove <union tree_node> {
! public:
! typedef union tree_node Element_t;
! static inline hashval_t hash (const_tree n)
! {
! return DECL_UID (SSA_NAME_VAR (n));
! }
! static inline int equal (const_tree n1, const_tree n2)
! {
! return SSA_NAME_VAR (n1) == SSA_NAME_VAR (n2);
! }
! };
/* Reduce the number of copies by coalescing variables in the function.
Return
a partition map with the resulting coalesces. */
*************** coalesce_ssa_name (void)
*** 1286,1294 ****
bitmap used_in_copies = BITMAP_ALLOC (NULL);
var_map map;
unsigned int i;
! static hash_table <tree_node, hash_ssa_name_by_var, eq_ssa_name_by_var,
! typed_null_remove<tree_node> >
! ssa_name_hash;
cl = create_coalesce_list ();
map = create_outofssa_var_map (cl, used_in_copies);
--- 1284,1290 ----
bitmap used_in_copies = BITMAP_ALLOC (NULL);
var_map map;
unsigned int i;
! static hash_table <ssa_name_var_hash> ssa_name_hash;
cl = create_coalesce_list ();
map = create_outofssa_var_map (cl, used_in_copies);
Index: gcc/tree-ssa-pre.c
===================================================================
*** gcc/tree-ssa-pre.c.orig 2012-08-15 10:20:33.000000000 +0200
--- gcc/tree-ssa-pre.c 2012-08-15 16:16:11.339629977 +0200
*************** static unsigned int next_expression_id;
*** 229,237 ****
DEF_VEC_P (pre_expr);
DEF_VEC_ALLOC_P (pre_expr, heap);
static VEC(pre_expr, heap) *expressions;
! static hash_table <pre_expr_d, ssa_pre_expr_hash, ssa_pre_expr_eq,
! typed_null_remove <pre_expr_d> >
! expression_to_id;
static VEC(unsigned, heap) *name_to_id;
/* Allocate an expression id for EXPR. */
--- 229,247 ----
DEF_VEC_P (pre_expr);
DEF_VEC_ALLOC_P (pre_expr, heap);
static VEC(pre_expr, heap) *expressions;
! struct pre_expr_hash : public typed_noop_remove <pre_expr_d> {
! typedef pre_expr_d Element_t;
! static inline hashval_t hash (const struct pre_expr_d *e)
! {
! return ssa_pre_expr_hash (e);
! }
! static inline int equal (const struct pre_expr_d *e1,
! const struct pre_expr_d *e2)
! {
! return ssa_pre_expr_eq (e1, e2);
! }
! };
! static hash_table <pre_expr_hash> expression_to_id;
static VEC(unsigned, heap) *name_to_id;
/* Allocate an expression id for EXPR. */
*************** typedef struct expr_pred_trans_d
*** 500,537 ****
} *expr_pred_trans_t;
typedef const struct expr_pred_trans_d *const_expr_pred_trans_t;
- /* Return the hash value for a phi translation table entry. */
-
- inline hashval_t
- ssa_expr_pred_trans_hash (const expr_pred_trans_d *ve)
- {
- return ve->hashcode;
- }
-
- /* Return true if two phi translation table entries are the same.
- P1 and P2 should point to the expr_pred_trans_t's to be compared.*/
-
- inline int
- ssa_expr_pred_trans_eq (const expr_pred_trans_d *ve1,
- const expr_pred_trans_d *ve2)
- {
- basic_block b1 = ve1->pred;
- basic_block b2 = ve2->pred;
-
- /* If they are not translations for the same basic block, they can't
- be equal. */
- if (b1 != b2)
- return false;
- return ssa_pre_expr_eq (ve1->e, ve2->e);
- }
-
/* The phi_translate_table caches phi translations for a given
expression and predecessor. */
!
! static hash_table <expr_pred_trans_d, ssa_expr_pred_trans_hash,
! ssa_expr_pred_trans_eq,
! typed_free_remove <expr_pred_trans_d> >
! phi_translate_table;
/* Search in the phi translation table for the translation of
expression E in basic block PRED.
--- 510,537 ----
} *expr_pred_trans_t;
typedef const struct expr_pred_trans_d *const_expr_pred_trans_t;
/* The phi_translate_table caches phi translations for a given
expression and predecessor. */
! struct expr_pred_trans_hash : public typed_free_remove<expr_pred_trans_d>
! {
! typedef expr_pred_trans_d Element_t;
! static inline hashval_t hash (const Element_t *e)
! {
! return e->hashcode;
! }
! static inline int equal (const Element_t *ve1, const Element_t *ve2)
! {
! basic_block b1 = ve1->pred;
! basic_block b2 = ve2->pred;
!
! /* If they are not translations for the same basic block, they can't
! be equal. */
! if (b1 != b2)
! return false;
! return ssa_pre_expr_eq (ve1->e, ve2->e);
! }
! };
! static hash_table <expr_pred_trans_hash> phi_translate_table;
/* Search in the phi translation table for the translation of
expression E in basic block PRED.
Index: gcc/tree-ssa-tail-merge.c
===================================================================
*** gcc/tree-ssa-tail-merge.c.orig 2012-08-15 10:20:26.000000000 +0200
--- gcc/tree-ssa-tail-merge.c 2012-08-15 16:24:46.219612235 +0200
*************** stmt_update_dep_bb (gimple stmt)
*** 415,422 ****
/* Calculates hash value for same_succ VE. */
! hashval_t
! ssa_same_succ_hash (const_same_succ e)
{
hashval_t hashval = bitmap_hash (e->succs);
int flags;
--- 415,422 ----
/* Calculates hash value for same_succ VE. */
! static hashval_t
! same_succ_hash (const_same_succ e)
{
hashval_t hashval = bitmap_hash (e->succs);
int flags;
*************** inverse_flags (const_same_succ e1, const
*** 511,520 ****
return (f1a & mask) == (f2a & mask) && (f1b & mask) == (f2b & mask);
}
/* Compares SAME_SUCCs VE1 and VE2. */
int
! ssa_same_succ_equal (const_same_succ e1, const_same_succ e2)
{
unsigned int i, first1, first2;
gimple_stmt_iterator gsi1, gsi2;
--- 511,572 ----
return (f1a & mask) == (f2a & mask) && (f1b & mask) == (f2b & mask);
}
+ /* Alloc and init a new SAME_SUCC. */
+
+ static same_succ
+ same_succ_alloc (void)
+ {
+ same_succ same = XNEW (struct same_succ_def);
+
+ same->bbs = BITMAP_ALLOC (NULL);
+ same->succs = BITMAP_ALLOC (NULL);
+ same->inverse = BITMAP_ALLOC (NULL);
+ same->succ_flags = VEC_alloc (int, heap, 10);
+ same->in_worklist = false;
+
+ return same;
+ }
+
+ /* Delete same_succ VE. */
+
+ static inline void
+ same_succ_delete (same_succ e)
+ {
+ BITMAP_FREE (e->bbs);
+ BITMAP_FREE (e->succs);
+ BITMAP_FREE (e->inverse);
+ VEC_free (int, heap, e->succ_flags);
+
+ XDELETE (e);
+ }
+
+ /* Reset same_succ SAME. */
+
+ static void
+ same_succ_reset (same_succ same)
+ {
+ bitmap_clear (same->bbs);
+ bitmap_clear (same->succs);
+ bitmap_clear (same->inverse);
+ VEC_truncate (int, same->succ_flags, 0);
+ }
+
+ /* Hash table with all same_succ entries. */
+
+ struct same_succ_hashtable {
+ typedef same_succ_def Element_t;
+ static inline hashval_t hash (const same_succ_def *e) { return e->hashval; }
+ static int equal (const_same_succ, const_same_succ);
+ static inline void remove (Element_t *e1)
+ {
+ same_succ_delete (e1);
+ }
+ };
+
/* Compares SAME_SUCCs VE1 and VE2. */
int
! same_succ_hashtable::equal (const_same_succ e1, const_same_succ e2)
{
unsigned int i, first1, first2;
gimple_stmt_iterator gsi1, gsi2;
*************** ssa_same_succ_equal (const_same_succ e1,
*** 568,618 ****
return 1;
}
! /* Alloc and init a new SAME_SUCC. */
!
! static same_succ
! same_succ_alloc (void)
! {
! same_succ same = XNEW (struct same_succ_def);
!
! same->bbs = BITMAP_ALLOC (NULL);
! same->succs = BITMAP_ALLOC (NULL);
! same->inverse = BITMAP_ALLOC (NULL);
! same->succ_flags = VEC_alloc (int, heap, 10);
! same->in_worklist = false;
!
! return same;
! }
!
! /* Delete same_succ VE. */
!
! inline void
! ssa_same_succ_delete (same_succ e)
! {
! BITMAP_FREE (e->bbs);
! BITMAP_FREE (e->succs);
! BITMAP_FREE (e->inverse);
! VEC_free (int, heap, e->succ_flags);
!
! XDELETE (e);
! }
!
! /* Reset same_succ SAME. */
!
! static void
! same_succ_reset (same_succ same)
! {
! bitmap_clear (same->bbs);
! bitmap_clear (same->succs);
! bitmap_clear (same->inverse);
! VEC_truncate (int, same->succ_flags, 0);
! }
!
! /* Hash table with all same_succ entries. */
!
! static hash_table <struct same_succ_def, ssa_same_succ_hash,
! ssa_same_succ_equal, ssa_same_succ_delete>
! same_succ_htab;
/* Array that is used to store the edge flags for a successor. */
--- 620,626 ----
return 1;
}
! static hash_table <same_succ_hashtable> same_succ_htab;
/* Array that is used to store the edge flags for a successor. */
*************** find_same_succ_bb (basic_block bb, same_
*** 692,698 ****
EXECUTE_IF_SET_IN_BITMAP (same->succs, 0, j, bj)
VEC_safe_push (int, heap, same->succ_flags, same_succ_edge_flags[j]);
! same->hashval = ssa_same_succ_hash (same);
slot = same_succ_htab.find_slot_with_hash (same, same->hashval, INSERT);
if (*slot == NULL)
--- 700,706 ----
EXECUTE_IF_SET_IN_BITMAP (same->succs, 0, j, bj)
VEC_safe_push (int, heap, same->succ_flags, same_succ_edge_flags[j]);
! same->hashval = same_succ_hash (same);
slot = same_succ_htab.find_slot_with_hash (same, same->hashval, INSERT);
if (*slot == NULL)
*************** find_same_succ (void)
*** 728,734 ****
same = same_succ_alloc ();
}
! ssa_same_succ_delete (same);
}
/* Initializes worklist administration. */
--- 736,742 ----
same = same_succ_alloc ();
}
! same_succ_delete (same);
}
/* Initializes worklist administration. */
*************** update_worklist (void)
*** 860,866 ****
if (same == NULL)
same = same_succ_alloc ();
}
! ssa_same_succ_delete (same);
bitmap_clear (deleted_bb_preds);
}
--- 868,874 ----
if (same == NULL)
same = same_succ_alloc ();
}
! same_succ_delete (same);
bitmap_clear (deleted_bb_preds);
}
Index: gcc/tree-ssa-threadupdate.c
===================================================================
*** gcc/tree-ssa-threadupdate.c.orig 2012-08-15 10:20:26.000000000 +0200
--- gcc/tree-ssa-threadupdate.c 2012-08-15 16:27:19.144606857 +0200
*************** create_block_for_threading (basic_block
*** 218,248 ****
}
/* Hashing and equality routines for our hash table. */
- inline hashval_t
- ssa_redirection_data_hash (const struct redirection_data *p)
- {
- edge e = p->outgoing_edge;
- return e->dest->index;
- }
! inline int
! ssa_redirection_data_eq (const struct redirection_data *p1,
! const struct redirection_data *p2)
{
! edge e1 = p1->outgoing_edge;
! edge e2 = p2->outgoing_edge;
! edge e3 = p1->intermediate_edge;
! edge e4 = p2->intermediate_edge;
!
! return e1 == e2 && e3 == e4;
! }
/* Main data structure to hold information for duplicates of BB. */
! static hash_table <struct redirection_data, ssa_redirection_data_hash,
! ssa_redirection_data_eq,
! typed_free_remove<struct redirection_data> >
! redirection_data;
/* Given an outgoing edge E lookup and return its entry in our hash table.
--- 218,251 ----
}
/* Hashing and equality routines for our hash table. */
! struct ssa_redirection_data_hash
! : public typed_free_remove<struct redirection_data>
{
! typedef redirection_data Element_t;
! static inline hashval_t
! hash (const struct redirection_data *p)
! {
! edge e = p->outgoing_edge;
! return e->dest->index;
! }
!
! static inline int
! equal (const struct redirection_data *p1,
! const struct redirection_data *p2)
! {
! edge e1 = p1->outgoing_edge;
! edge e2 = p2->outgoing_edge;
! edge e3 = p1->intermediate_edge;
! edge e4 = p2->intermediate_edge;
!
! return e1 == e2 && e3 == e4;
! }
! };
/* Main data structure to hold information for duplicates of BB. */
! static hash_table <ssa_redirection_data_hash> redirection_data;
/* Given an outgoing edge E lookup and return its entry in our hash table.
