Merge C++ conversion into trunk (4/6 - hash table rewrite)

[Lawrence Crowl]

On 9/28/12, Michael Matz <matz@suse.de> wrote:
> On Thu, 27 Sep 2012, Lawrence Crowl wrote:
> > > template <typename T>
> > > struct D : B<T>
> > > {
> > >   typedef typename B<T>::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 htab<tree>::value_type is tree, and
> htab<int>::value_type is int, and I would like to see it named
> htab<tree>::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