On Wed, 15 Aug 2012, Richard Guenther wrote:
> On Sun, 12 Aug 2012, Diego Novillo wrote:
>
> > This implements a new C++ hash table.
> >
> > See http://gcc.gnu.org/ml/gcc-patches/2012-08/msg00711.html for
> > details.
> >
> > Diego.
>
> Now as we see the result I'd have prefered a more C++-way instead
> of making the conversion simple ...
>
> Like
>
> template <typename Element>
> class hash_table
> {
> ...
> };
>
> template <typename Element>
> class pointer_hash
> {
> hashval_t hash ();
> int equal (const Element *);
> ~Element ();
> Element e;
> };
>
> and
>
> /* Hash table with all same_succ entries. */
>
> static hash_table <pointer_hash <struct same_succ_def> > same_succ_htab;
>
> The existing way is simply too ugly ... so, why did you not invent
> a "nice" C++ way?
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?
Thanks,
Richard.
> diffstat ~/p
coverage.c | 43 +++++-----
hash-table.h | 234
+++++++++++++++++++++--------------------------------------
2 files changed, 108 insertions(+), 169 deletions(-)
Index: gcc/hash-table.h
===================================================================
--- gcc/hash-table.h (revision 190410)
+++ gcc/hash-table.h (working copy)
@@ -199,45 +199,42 @@ struct hash_table_control
*/
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
{
+public:
+ typedef typename Element::Element_t Element_t;
private:
+ hash_table_control <Element_t> *htab;
- hash_table_control <Element> *htab;
-
- Element **find_empty_slot_for_expand (hashval_t hash);
+ 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 *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);
+ 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 **slot);
- void remove_elt (Element *comparable);
- void remove_elt_with_hash (Element *comparable, hashval_t hash);
+ 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 **slot, Argument argument)>
+ int (*Callback) (Element_t **slot, Argument argument)>
void traverse_noresize (Argument argument);
template <typename Argument,
- int (*Callback) (Element **slot, Argument argument)>
+ int (*Callback) (Element_t **slot, Argument argument)>
void traverse (Argument argument);
};
@@ -245,12 +242,9 @@ public:
/* 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 ()
+hash_table <Element, Allocator>::hash_table ()
: htab (NULL)
{
}
@@ -259,12 +253,9 @@ hash_table <Element, Hash, Equal, Remove
/* 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 ()
+hash_table <Element, Allocator>::is_created ()
{
return htab != NULL;
}
@@ -273,56 +264,44 @@ hash_table <Element, Hash, Equal, Remove
/* 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)
+inline typename Element::Element_t *
+hash_table <Element, Allocator>::find (Element_t *comparable)
{
- return find_with_hash (comparable, Hash (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,
- 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)
+ 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, Hash (comparable), 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,
- 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)
+hash_table <Element, Allocator>
+::remove_elt (Element_t *comparable)
{
- remove_elt_with_hash (comparable, Hash (comparable));
+ remove_elt_with_hash (comparable, Element::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()
+hash_table <Element, Allocator>::size()
{
return htab->size;
}
@@ -331,12 +310,9 @@ hash_table <Element, Hash, Equal, Remove
/* 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()
+hash_table <Element, Allocator>::elements()
{
return htab->n_elements - htab->n_deleted;
}
@@ -346,12 +322,9 @@ hash_table <Element, Hash, Equal, Remove
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()
+hash_table <Element, Allocator>::collisions()
{
if (htab->searches == 0)
return 0.0;
@@ -363,21 +336,18 @@ hash_table <Element, Hash, Equal, Remove
/* 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)
+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> > ::control_alloc (1);
+ htab = Allocator <hash_table_control <Element_t> > ::control_alloc (1);
gcc_assert (htab != NULL);
- htab->entries = Allocator <Element*> ::data_alloc (size);
+ htab->entries = Allocator <Element_t*> ::data_alloc (size);
gcc_assert (htab->entries != NULL);
htab->size = size;
htab->size_prime_index = size_prime_index;
@@ -388,22 +358,19 @@ hash_table <Element, Hash, Equal, Remove
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 ()
+hash_table <Element, Allocator>::dispose ()
{
size_t size = htab->size;
- Element **entries = htab->entries;
+ Element_t **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]);
+ Element::Remove (entries[i]);
- Allocator <Element *> ::data_free (entries);
- Allocator <hash_table_control <Element> > ::control_free (htab);
+ Allocator <Element_t *> ::data_free (entries);
+ Allocator <hash_table_control <Element_t> > ::control_free (htab);
htab = NULL;
}
@@ -416,17 +383,14 @@ hash_table <Element, Hash, Equal, Remove
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>
+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 **slot = htab->entries + index;
+ Element_t **slot = htab->entries + index;
hashval_t hash2;
if (*slot == HTAB_EMPTY_ENTRY)
@@ -458,17 +422,14 @@ hash_table <Element, Hash, Equal, Remove
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 ()
+hash_table <Element, Allocator>::expand ()
{
- Element **oentries;
- Element **olimit;
- Element **p;
- Element **nentries;
+ Element_t **oentries;
+ Element_t **olimit;
+ Element_t **p;
+ Element_t **nentries;
size_t nsize, osize, elts;
unsigned int oindex, nindex;
@@ -491,7 +452,7 @@ hash_table <Element, Hash, Equal, Remove
nsize = osize;
}
- nentries = Allocator <Element *> ::data_alloc (nsize);
+ nentries = Allocator <Element_t *> ::data_alloc (nsize);
gcc_assert (nentries != NULL);
htab->entries = nentries;
htab->size = nsize;
@@ -502,11 +463,11 @@ hash_table <Element, Hash, Equal, Remove
p = oentries;
do
{
- Element *x = *p;
+ Element_t *x = *p;
if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
{
- Element **q = find_empty_slot_for_expand (Hash (x));
+ Element_t **q = find_empty_slot_for_expand (Element::Hash (x));
*q = x;
}
@@ -515,7 +476,7 @@ hash_table <Element, Hash, Equal, Remove
}
while (p < olimit);
- Allocator <Element *> ::data_free (oentries);
+ Allocator <Element_t *> ::data_free (oentries);
}
@@ -524,17 +485,14 @@ hash_table <Element, Hash, Equal, Remove
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)
+ 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 *entry;
+ Element_t *entry;
htab->searches++;
size = htab->size;
@@ -542,7 +500,7 @@ hash_table <Element, Hash, Equal, Remove
entry = htab->entries[index];
if (entry == HTAB_EMPTY_ENTRY
- || (entry != HTAB_DELETED_ENTRY && Equal (entry, comparable)))
+ || (entry != HTAB_DELETED_ENTRY && Element::Equal (entry, comparable)))
return entry;
hash2 = hash_table_mod2 (hash, htab->size_prime_index);
@@ -555,7 +513,7 @@ hash_table <Element, Hash, Equal, Remove
entry = htab->entries[index];
if (entry == HTAB_EMPTY_ENTRY
- || (entry != HTAB_DELETED_ENTRY && Equal (entry, comparable)))
+ || (entry != HTAB_DELETED_ENTRY && Element::Equal (entry,
comparable)))
return entry;
}
}
@@ -570,19 +528,16 @@ hash_table <Element, Hash, Equal, Remove
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,
+ 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 **first_deleted_slot;
+ Element_t **first_deleted_slot;
hashval_t index, hash2;
size_t size;
- Element *entry;
+ Element_t *entry;
size = htab->size;
if (insert == INSERT && size * 3 <= htab->n_elements * 4)
@@ -601,7 +556,7 @@ hash_table <Element, Hash, Equal, Remove
goto empty_entry;
else if (entry == HTAB_DELETED_ENTRY)
first_deleted_slot = &htab->entries[index];
- else if (Equal (entry, comparable))
+ else if (Element::Equal (entry, comparable))
return &htab->entries[index];
hash2 = hash_table_mod2 (hash, htab->size_prime_index);
@@ -620,7 +575,7 @@ hash_table <Element, Hash, Equal, Remove
if (!first_deleted_slot)
first_deleted_slot = &htab->entries[index];
}
- else if (Equal (entry, comparable))
+ else if (Element::Equal (entry, comparable))
return &htab->entries[index];
}
@@ -631,7 +586,7 @@ hash_table <Element, Hash, Equal, Remove
if (first_deleted_slot)
{
htab->n_deleted--;
- *first_deleted_slot = static_cast <Element *> (HTAB_EMPTY_ENTRY);
+ *first_deleted_slot = static_cast <Element_t *> (HTAB_EMPTY_ENTRY);
return first_deleted_slot;
}
@@ -643,20 +598,17 @@ hash_table <Element, Hash, Equal, Remove
/* 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 ()
+hash_table <Element, Allocator>::empty ()
{
size_t size = htab_size (htab);
- Element **entries = htab->entries;
+ 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)
- Remove (entries[i]);
+ Element::Remove (entries[i]);
/* Instead of clearing megabyte, downsize the table. */
if (size > 1024*1024 / sizeof (PTR))
@@ -664,13 +616,13 @@ hash_table <Element, Hash, Equal, Remove
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);
+ 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 *));
+ memset (entries, 0, size * sizeof (Element_t *));
htab->n_deleted = 0;
htab->n_elements = 0;
}
@@ -681,19 +633,16 @@ hash_table <Element, Hash, Equal, Remove
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)
+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 ();
- Remove (*slot);
+ Element::Remove (*slot);
*slot = HTAB_DELETED_ENTRY;
htab->n_deleted++;
@@ -705,23 +654,20 @@ hash_table <Element, Hash, Equal, Remove
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)
+hash_table <Element, Allocator>
+::remove_elt_with_hash (Element_t *comparable, hashval_t hash)
{
- Element **slot;
+ Element_t **slot;
slot = find_slot_with_hash (comparable, hash, NO_INSERT);
if (*slot == HTAB_EMPTY_ENTRY)
return;
- Remove (*slot);
+ Element::Remove (*slot);
- *slot = static_cast <Element *> (HTAB_DELETED_ENTRY);
+ *slot = static_cast <Element_t *> (HTAB_DELETED_ENTRY);
htab->n_deleted++;
}
@@ -731,25 +677,22 @@ hash_table <Element, Hash, Equal, Remove
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)>
+ int (*Callback) (typename Element::Element_t **slot, Argument
argument)>
void
-hash_table <Element, Hash, Equal, Remove, Allocator>
+hash_table <Element, Allocator>
::traverse_noresize (Argument argument)
{
- Element **slot;
- Element **limit;
+ Element_t **slot;
+ Element_t **limit;
slot = htab->entries;
limit = slot + htab->size;
do
{
- Element *x = *slot;
+ Element_t *x = *slot;
if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
if (! Callback (slot, argument))
@@ -763,14 +706,11 @@ hash_table <Element, Hash, Equal, Remove
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)>
+ int (*Callback) (typename Element::Element_t **slot, Argument
argument)>
void
-hash_table <Element, Hash, Equal, Remove, Allocator>
+hash_table <Element, Allocator>
::traverse (Argument argument)
{
size_t size = htab->size;
Index: gcc/coverage.c
===================================================================
--- gcc/coverage.c (revision 190410)
+++ gcc/coverage.c (working copy)
@@ -143,30 +143,29 @@ get_gcov_unsigned_t (void)
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);
-}
+class coverage_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_t, coverage_counts_entry_hash,
- coverage_counts_entry_eq, coverage_counts_entry_del>
- counts_hash;
+static hash_table <coverage_hash> counts_hash;
/* Read in the counts file, if available. */
