Re: Merge C++ conversion into trunk (4/6 - hash table rewrite)
Hi,
On Thu, 27 Sep 2012, Lawrence Crowl wrote:
template typename T
struct D : BT
{
typedef typename BT::E E; // element_type
E getme (int index);
}
Inside that struct, lets say we have a field of type E. Do we name
it F or f?
IMHO only for types, not for any other decls.
Do you have an alternate suggestion, one that does not confuse
template parameters and dependent names?
Upper last character? Just kidding :) Too many detailed rules
for conventions are the death of them, use rules of thumbs,
my one would be somehow depends on template args - has upper
character in name, where somehow depends on includes is a.
Ah, but there is a problem. That typedef name does not necessarily
depend on a template parameter.
It is common practice to have
struct Q
{
typedef int E;
E getme (int index);
};
Easy: I wouldn't make a typedef for Q::E that merely is int. The reason
is that it makes knowing what getme really returns harder. You have to
look it up always (or know the class already). In fact that's one of my
gripes with the standard library, much too much indirection through
entities merely referring to other entities. Might be only important for
the libraries implementors but I sure hope that we don't start down that
road in GCC.
In fact, one place is in the hash table code we are discussing.
The hash descriptor type may not itself be a template. I believe
that few of them will actually be templates.
Then I don't see the need for class-local typedefs.
So, if E implies comes from template, the implication is wrong.
If we were to follow C++ standard library conventions, we would call it
value_type.
Well, but value_type surely does depend on the hashtables type argument,
doesn't it? After all it is a typedef from 'Key'.
I would expect that htabtree::value_type is tree, and
htabint::value_type is int, and I would like to see it named
htabtree::T or ::E.
That would be my preference. However, if folks want a shorter name,
I'll live with that too. But as it stands, the current name is very
confusing.
I would even prefer 'e' over value_type. It's scoped, the context always
will be clear, no need to be verbose in that name. I find the long names
inelegant, as most of the standard libs conventions.
Ciao,
Michael.
Re: Merge C++ conversion into trunk (4/6 - hash table rewrite)
On Fri, Sep 28, 2012 at 8:18 AM, Michael Matz m...@suse.de wrote:
It is common practice to have
struct Q
{
typedef int E;
E getme (int index);
};
Easy: I wouldn't make a typedef for Q::E that merely is int. The reason
is that it makes knowing what getme really returns harder.
The point of these nested type is precisely to allow a *uniform* access
to associated from within a template (e.g. a container) -- irrespective of
what those types happen to resolve to, builtin or not.
-- Gaby
Re: Merge C++ conversion into trunk (4/6 - hash table rewrite)
On 9/28/12, Michael Matz m...@suse.de wrote:
On Thu, 27 Sep 2012, Lawrence Crowl wrote:
template typename T
struct D : BT
{
typedef typename BT::E E; // element_type
E getme (int index);
}
Inside that struct, lets say we have a field of type E. Do we name
it F or f?
IMHO only for types, not for any other decls.
Do you have an alternate suggestion, one that does not confuse
template parameters and dependent names?
Upper last character? Just kidding :) Too many detailed rules
for conventions are the death of them, use rules of thumbs,
my one would be somehow depends on template args - has upper
character in name, where somehow depends on includes is a.
Ah, but there is a problem. That typedef name does not necessarily
depend on a template parameter.
It is common practice to have
struct Q
{
typedef int E;
E getme (int index);
};
Easy: I wouldn't make a typedef for Q::E that merely is int. The reason
is that it makes knowing what getme really returns harder. You have to
look it up always (or know the class already). In fact that's one of my
gripes with the standard library, much too much indirection through
entities merely referring to other entities. Might be only important for
the libraries implementors but I sure hope that we don't start down that
road in GCC.
In fact, one place is in the hash table code we are discussing.
The hash descriptor type may not itself be a template. I believe
that few of them will actually be templates.
Then I don't see the need for class-local typedefs.
So, if E implies comes from template, the implication is wrong.
If we were to follow C++ standard library conventions, we would call it
value_type.
Well, but value_type surely does depend on the hashtables
type argument, doesn't it? After all it is a typedef from
'Key'. I would expect that htabtree::value_type is tree, and
htabint::value_type is int, and I would like to see it named
htabtree::T or ::E.
One declares a hash table as follows.
hash_table hash_descriptor variable;
The type stored in the hash table is not part of the declaration.
It is part of the descriptor, along with other things like the
hash function. The hash table essentially queries the descriptor
for the value type. For example,
template Descriptor class hash_table {
typename Descriptor::value_type *storage;
...
More typically though, the typedef is repeated inside the class to
avoid excess verbosity, and more importantly, to reexport the name.
template Descriptor class hash_table {
typedef typename Descriptor::value_type value_type;
value_type *storage;
...
Using these typedef names is an essential component of the
abstraction. Without it, we end up going to void* and loosing all
type safety.
That would be my preference. However, if folks want a shorter name,
I'll live with that too. But as it stands, the current name is very
confusing.
I would even prefer 'e' over value_type. It's scoped, the context always
will be clear, no need to be verbose in that name. I find the long names
inelegant, as most of the standard libs conventions.
We need some convention. If we choose a convention different from
the standard library, then we are essentially saying that we do not
intend to interoperate with the standard library. I do not think
that is the intent of the community, but I could be wrong about that.
--
Lawrence Crowl
Re: Merge C++ conversion into trunk (4/6 - hash table rewrite)
On Fri, Sep 28, 2012 at 12:40 PM, Lawrence Crowl cr...@google.com wrote: On 9/28/12, Michael Matz m...@suse.de wrote: I would even prefer 'e' over value_type. It's scoped, the context always will be clear, no need to be verbose in that name. I find the long names inelegant, as most of the standard libs conventions. We need some convention. If we choose a convention different from the standard library, then we are essentially saying that we do not intend to interoperate with the standard library. I do not think that is the intent of the community, but I could be wrong about that. I agree. If there already exists a convention that is widely known and recognized, then we should use it. There is negative value in inventing a new convention. We need to lower barriers to adoption, not raise them. Using the standard library convention seems to me like the best thing to do here. Diego.
Re: Merge C++ conversion into trunk (4/6 - hash table rewrite)
On 9/28/12, Gabriel Dos Reis g...@integrable-solutions.net wrote:
On Fri, Sep 28, 2012 at 8:18 AM, Michael Matz m...@suse.de wrote:
It is common practice to have
struct Q
{
typedef int E;
E getme (int index);
};
Easy: I wouldn't make a typedef for Q::E that merely is int. The reason
is that it makes knowing what getme really returns harder.
The point of these nested type is precisely to allow a *uniform* access
to associated from within a template (e.g. a container) -- irrespective of
what those types happen to resolve to, builtin or not.
Perhaps an analogy might be helpful. If I say Tim's father you know
role of that person without knowing exactly who it is. The typedef
convention serves the same purpose. It is important that we use the
same term for father, or we wouldn't be able to communicate.
--
Lawrence Crowl
Re: Merge C++ conversion into trunk (4/6 - hash table rewrite)
Hi,
On Wed, 26 Sep 2012, Lawrence Crowl wrote:
A lower-case type name indicates to me a non-changing type,
i.e. nothing that depends on a template. In C we only had
such types so we used lower-case names everywhere. With C++
and templates I think we should start using upper case for some
very specific use cases, like first letter of dependend types.
How would you distinguish them from template parameter names,
which by convention have an upper case first letter?
I wouldn't. If the distinction becomes so important that authors need to
see the speciality immediately by having a different convention how to
spell names, then I think we did something wrong, and we should simplify
the code.
What about non-type dependent names?
I'm not sure what you're asking. Let's make an example:
template typename T
struct D : BT
{
typedef typename BT::E E; // element_type
E getme (int index);
}
In fact, as BT::E would probably be defined like typedef typename T E,
I would even have no issue to call the above E also T. The distinction
between the template arg name and the typedef would be blurred, and I say,
so what; one is a typedef of the other and hence mostly equivalent for
practical purposes. (And if they aren't, then again, we did something too
complicated with the switch to C++).
The advantage to following them is that they will surprise no one.
They will surprise everyone used to different conventions, for instance
Qt, so that's not a reason.
Do you have an alternate suggestion, one that does not confuse template
parameters and dependent names?
Upper last character? Just kidding :) Too many detailed rules for
conventions are the death of them, use rules of thumbs, my one would be
somehow depends on template args - has upper character in name, where
somehow depends on includes is a.
Ciao,
Michael.
Re: Merge C++ conversion into trunk (4/6 - hash table rewrite)
On Thu, Sep 27, 2012 at 7:12 AM, Michael Matz m...@suse.de wrote: (And if they aren't, then again, we did something too complicated with the switch to C++). or we are doing something by insisting not to use standard notation.
Re: Merge C++ conversion into trunk (4/6 - hash table rewrite)
On 9/27/12, Michael Matz m...@suse.de wrote:
On Wed, 26 Sep 2012, Lawrence Crowl wrote:
A lower-case type name indicates to me a non-changing type,
i.e. nothing that depends on a template. In C we only had
such types so we used lower-case names everywhere. With C++
and templates I think we should start using upper case for some
very specific use cases, like first letter of dependend types.
How would you distinguish them from template parameter names,
which by convention have an upper case first letter?
I wouldn't. If the distinction becomes so important that authors
need to see the speciality immediately by having a different
convention how to spell names, then I think we did something wrong,
and we should simplify the code.
What about non-type dependent names?
I'm not sure what you're asking. Let's make an example:
template typename T
struct D : BT
{
typedef typename BT::E E; // element_type
E getme (int index);
}
Inside that struct, lets say we have a field of type E. Do we name
it F or f?
In fact, as BT::E would probably be defined like typedef
typename T E, I would even have no issue to call the above E
also T. The distinction between the template arg name and the
typedef would be blurred, and I say, so what; one is a typedef
of the other and hence mostly equivalent for practical purposes.
(And if they aren't, then again, we did something too complicated
with the switch to C++).
The advantage to following them is that they will surprise
no one.
They will surprise everyone used to different conventions, for
instance Qt, so that's not a reason.
Anyone using the standard library will not be surprised if we follow
the conventions of the standard library. I'd guess that the number
standard library programmers outnumbers the Qt programmers by 100
to 1. I'd guess that the number of Qt programmers that do not know
the standard library is a minority.
Do you have an alternate suggestion, one that does not confuse
template parameters and dependent names?
Upper last character? Just kidding :) Too many detailed rules
for conventions are the death of them, use rules of thumbs,
my one would be somehow depends on template args - has upper
character in name, where somehow depends on includes is a.
Ah, but there is a problem. That typedef name does not necessarily
depend on a template parameter.
It is common practice to have
struct Q
{
typedef int E;
E getme (int index);
};
and use it in exactly the same places you would use Dsomething.
In fact, one place is in the hash table code we are discussing.
The hash descriptor type may not itself be a template. I believe
that few of them will actually be templates.
So, if E implies comes from template, the implication is wrong.
If we were to follow C++ standard library conventions, we would call
it value_type. That would be my preference. However, if folks
want a shorter name, I'll live with that too. But as it stands,
the current name is very confusing.
--
Lawrence Crowl
Re: Merge C++ conversion into trunk (4/6 - hash table rewrite)
On Thu, Sep 27, 2012 at 1:35 PM, Lawrence Crowl cr...@google.com wrote: If we were to follow C++ standard library conventions, we would call it value_type. That would be my preference. However, if folks want a shorter name, I'll live with that too. But as it stands, the current name is very confusing. Yes, and there appears to be no good reason to let it stand. -- Gaby
Re: Merge C++ conversion into trunk (4/6 - hash table rewrite)
Hi, On Tue, 25 Sep 2012, Lawrence Crowl wrote: On 8/15/12, Richard Henderson r...@redhat.com wrote: On 2012-08-15 07:29, Richard Guenther wrote: + typedef typename Element::Element_t Element_t; Can we use something less ugly than Element_t? Such as typedef typename Element::T T; ? Given that this name is scoped anyway... I've been finding the use of T as a typedef confusing. Why? As type placeholder in templates it's quite customary, as the most interesting to users of this template. I would have no trouble at all to see declarations like T x = getme(); in a function. In some way I even prefer that to some lower-case variant, because it reminds me that this specific T is actually variant. A lower-case type name indicates to me a non-changing type, i.e. nothing that depends on a template. In C we only had such types so we used lower-case names everywhere. With C++ and templates I think we should start using upper case for some very specific use cases, like first letter of dependend types. It sort of flies in the face of all existing convention. If you talk about the conventions used for the c++ standard library, then they are IMHO quite ugly and we should not follow them. Ciao, Michael.
Re: Merge C++ conversion into trunk (4/6 - hash table rewrite)
On Tue, Sep 25, 2012 at 4:30 PM, Lawrence Crowl cr...@google.com wrote: On 8/15/12, Richard Henderson r...@redhat.com wrote: On 2012-08-15 07:29, Richard Guenther wrote: + typedef typename Element::Element_t Element_t; Can we use something less ugly than Element_t? Such as typedef typename Element::T T; ? Given that this name is scoped anyway... I've been finding the use of T as a typedef confusing. It sort of flies in the face of all existing convention. The C++ standard would use either element_type or value_type. I suggest a rename, but I'm guessing that folks don't want something as verbose as element_type. How about elemtype? Any objections to me changing it to that? In general, we would be better off following standard convention. It does not seem to me that we have enough reasons and benefits in building our own universe around this issue. Consequently, I would suggest that we use value_type or element_type in the interface -- which is better served being readable: this is the *interface*. I am pretty sure that people will quickly resort to local typedefs that are more readable even if we adopt a short (therefore cryptic) abbreviations such as T in the interface. It is one more hurdle that has no reason to be. -- Gaby
Re: Merge C++ conversion into trunk (4/6 - hash table rewrite)
On 9/26/12, Michael Matz m...@suse.de wrote: On Tue, 25 Sep 2012, Lawrence Crowl wrote: On 8/15/12, Richard Henderson r...@redhat.com wrote: On 2012-08-15 07:29, Richard Guenther wrote: typedef typename Element::Element_t Element_t; Can we use something less ugly than Element_t? Such as typedef typename Element::T T; ? Given that this name is scoped anyway... I've been finding the use of T as a typedef confusing. Why? As type placeholder in templates it's quite customary, as the most interesting to users of this template. I would have no trouble at all to see declarations like T x = getme(); in a function. In some way I even prefer that to some lower-case variant, because it reminds me that this specific T is actually variant. The problem is that while T is customary as a template parameter, I have never seen it used as a typedef name. And that's the situation that we are in now. A lower-case type name indicates to me a non-changing type, i.e. nothing that depends on a template. In C we only had such types so we used lower-case names everywhere. With C++ and templates I think we should start using upper case for some very specific use cases, like first letter of dependend types. How would you distinguish them from template parameter names, which by convention have an upper case first letter? What about non-type dependent names? I think we really do need a separate convention for the two, because dependent members of class templates often need special access syntax. It sort of flies in the face of all existing convention. If you talk about the conventions used for the c++ standard library, then they are IMHO quite ugly and we should not follow them. The advantage to following them is that they will surprise no one. Do you have an alternate suggestion, one that does not confuse template parameters and dependent names? -- Lawrence Crowl
Re: Merge C++ conversion into trunk (4/6 - hash table rewrite)
On Wed, Sep 26, 2012 at 1:09 PM, Lawrence Crowl cr...@google.com wrote: The problem is that while T is customary as a template parameter, I have never seen it used as a typedef name. And that's the situation that we are in now. this should be a no-brainer: T should be reserved for the name of the template parameter. [...] I think we really do need a separate convention for the two, because dependent members of class templates often need special access syntax. Yes. -- Gaby
Re: Merge C++ conversion into trunk (4/6 - hash table rewrite)
On 8/15/12, Richard Henderson r...@redhat.com wrote: On 2012-08-15 07:29, Richard Guenther wrote: + typedef typename Element::Element_t Element_t; Can we use something less ugly than Element_t? Such as typedef typename Element::T T; ? Given that this name is scoped anyway... I've been finding the use of T as a typedef confusing. It sort of flies in the face of all existing convention. The C++ standard would use either element_type or value_type. I suggest a rename, but I'm guessing that folks don't want something as verbose as element_type. How about elemtype? Any objections to me changing it to that? -- Lawrence Crowl
Re: Merge C++ conversion into trunk (4/6 - hash table rewrite)
On Wed, 15 Aug 2012, Lawrence Crowl wrote:
On 8/15/12, Richard Henderson r...@redhat.com wrote:
On 2012-08-15 07:29, Richard Guenther wrote:
+ typedef typename Element::Element_t Element_t;
Can we use something less ugly than Element_t?
Such as
typedef typename Element::T T;
? Given that this name is scoped anyway...
I do not much like _t names either.
The following is what I'm testing now, it also integrates the
hashtable support functions and typedef within the existing local
data types which is IMHO cleaner. (it also shows we can do with
a janitorial cleanup replacing typedef struct foo_d {} foo; with
struct foo {}; and the likes)
Bootstrap and regtest ongoing on x86_64-unknown-linux-gnu, ok?
Thanks,
Richard.
2012-08-16 Richard Guenther rguent...@suse.de
* hash-table.h (class hash_table): Use a descriptor template
argument instead of decomposed element type and support
functions.
(struct pointer_hash): New generic typed pointer-hash.
(struct typed_free_remove, struct typed_noop_remove): Generic
hash_table support pieces.
* coverage.c (struct counts_entry): Add hash_table support
members.
* tree-ssa-ccp.c (gimple_htab): Use pointer_hash.
* tree-ssa-coalesce.c (struct ssa_name_var_hash): New generic
SSA name by SSA_NAME_VAR hash.
(coalesce_ssa_name): Use it.
* tree-ssa-pre.c (struct pre_expr_d): Add hash_table support.
(expression_to_id): Adjust.
(struct expr_pred_trans_d): Add hash_table support.
(phi_translate_table): Adjust.
(phi_trans_lookup): Likewise.
(phi_trans_add): Likewise.
(do_regular_insertion): Likewise.
* tree-ssa-tail-merge.c (struct same_succ_def): Add hash_table
support.
(same_succ_htab): Adjust.
(find_same_succ_bb): Likewise.
(find_same_succ): Likewise.
(update_worklist): Likewise.
* tree-ssa-threadupdate.c (struct redirection_data): Add hash_table
support.
(redirection_data): Adjust.
Index: gcc/hash-table.h
===
*** gcc/hash-table.h.orig 2012-08-16 10:33:59.0 +0200
--- gcc/hash-table.h2012-08-16 11:08:36.311277498 +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,134
}
! /* Remove method dispatching to free. */
template typename Element
! struct typed_free_remove
{
! static inline void remove (Element *p) { free (p); }
! };
! /* No-op remove method. */
template typename Element
! struct typed_noop_remove
{
! static inline void remove (Element *) {}
! };
! /* Pointer hash with a no-op remove method. */
template typename Element
! struct pointer_hash : typed_noop_remove Element
{
! typedef Element T;
+ static inline hashval_t
+ hash (const T *);
! static inline int
! equal (const T *existing, const T * candidate);
! };
template typename Element
! inline hashval_t
! pointer_hashElement::hash (const 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_hashElement::equal (const T *existing,
! const T *candidate)
! {
! return existing == candidate;
}
*** extern hashval_t hash_table_mod2 (hashva
*** 147,157
/* Internal implementation type. */
! template typename Element
struct hash_table_control
{
/* Table itself. */
! Element **entries;
/* Current size (in entries) of the hash table. */
size_t size;
--- 154,164
/* Internal implementation type. */
! template typename T
struct hash_table_control
{
/* Table itself.
Re: Merge C++ conversion into trunk (4/6 - hash table rewrite)
Hi,
I have another out of curiosity-type question ;)
On 08/16/2012 11:19 AM, Richard Guenther wrote:
!
! template typename Element
! inline int
! pointer_hashElement::equal (const T *existing,
! const T *candidate)
! {
! return existing == candidate;
}
are these uses in the new code of int instead of bool intended or
historical? Seem weird, definitely from the C++ (but even from the C)
point of view.
Paolo.
Re: Merge C++ conversion into trunk (4/6 - hash table rewrite)
On Thu, 16 Aug 2012, Paolo Carlini wrote:
Hi,
I have another out of curiosity-type question ;)
On 08/16/2012 11:19 AM, Richard Guenther wrote:
!
! template typename Element
! inline int
! pointer_hashElement::equal (const T *existing,
! const T *candidate)
! {
! return existing == candidate;
}
are these uses in the new code of int instead of bool intended or
historical? Seem weird, definitely from the C++ (but even from the C) point
of view.
Historical, copying what libiberty htab did.
Richard.
Re: Merge C++ conversion into trunk (4/6 - hash table rewrite)
On 8/16/12, Richard Guenther rguent...@suse.de wrote:
On Wed, 15 Aug 2012, Lawrence Crowl wrote:
On 8/15/12, Richard Henderson r...@redhat.com wrote:
On 2012-08-15 07:29, Richard Guenther wrote:
+ typedef typename Element::Element_t Element_t;
Can we use something less ugly than Element_t?
Such as
typedef typename Element::T T;
? Given that this name is scoped anyway...
I do not much like _t names either.
The following is what I'm testing now, it also integrates the
hashtable support functions and typedef within the existing local
data types which is IMHO cleaner. (it also shows we can do with
a janitorial cleanup replacing typedef struct foo_d {} foo; with
struct foo {}; and the likes)
Yes.
Bootstrap and regtest ongoing on x86_64-unknown-linux-gnu, ok?
Looks good to me.
I would have prefered the Element-T rename in a separate patch
so that it is easier to see the core difference.
--
Lawrence Crowl
Re: Merge C++ conversion into trunk (4/6 - hash table rewrite)
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)
Re: Merge C++ conversion into trunk (4/6 - hash table rewrite)
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. Ciao, Michael.
Re: Merge C++ conversion into trunk (4/6 - hash table rewrite)
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.0 +0200
--- gcc/hash-table.h2012-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_hashElement::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_hashElement::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
*/
Re: Merge C++ conversion into trunk (4/6 - hash table rewrite)
On 2012-08-15 07:29, Richard Guenther wrote: + typedef typename Element::Element_t Element_t; Can we use something less ugly than Element_t? Such as typedef typename Element::T T; ? Given that this name is scoped anyway... r~
Re: Merge C++ conversion into trunk (4/6 - hash table rewrite)
On 8/15/12, Richard Guenther rguent...@suse.de 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.
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? (please consider reverting the hashtable patch)
We are trying to balance several factors. Sometimes we're going
to pick multiple steps rather than a single step. In some cases,
as here, the intent was to make the client code changes minimal and
unsurprising while still getting the type safety and efficiency.
Other times, it may be a minor technical issue. In particular,
I prefer to avoid steps that might cause very poor matching of
lines in the diff. Others may choose differently. Together we
will learn where the tradeoffs lie.
More in a later response.
--
Lawrence Crowl
Re: Merge C++ conversion into trunk (4/6 - hash table rewrite)
On 8/15/12, Richard Guenther rguent...@suse.de wrote: On Wed, 15 Aug 2012, Michael Matz wrote: 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). 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. Your conversion is a better abstraction, and something I'd wanted to get to eventually, so I support your conversion. BTW, the conding conventions say to put member function definitions out of line. -- Lawrence Crowl
Re: Merge C++ conversion into trunk (4/6 - hash table rewrite)
On 8/15/12, Richard Henderson r...@redhat.com wrote: On 2012-08-15 07:29, Richard Guenther wrote: + typedef typename Element::Element_t Element_t; Can we use something less ugly than Element_t? Such as typedef typename Element::T T; ? Given that this name is scoped anyway... I do not much like _t names either. -- Lawrence Crowl
Re: Merge C++ conversion into trunk (4/6 - hash table rewrite)
On Wed, Aug 15, 2012 at 2:58 PM, Lawrence Crowl cr...@google.com wrote: I do not much like _t names either. Also, names ending in _t are reserved by POSIX if you #include sys/types.h. Though that may only apply to global names, not to types defined in classes or namespaces. Ian
