Re: C++ edge_iterator (was: Re: [SH] PR 53976 - Add RTL pass to eliminate clrt, sett insns)

[Oleg Endo <oleg dot endo at t-online dot de>]

On Mon, 2013-12-16 at 09:57 -0500, Trevor Saunders wrote:
> > 
> > BTW, if you look at the patch, I haven't overloaded any ++ operators:
> > 
> > Index: gcc/vec.h
> > ===================================================================
> > --- gcc/vec.h	(revision 205866)
> > +++ gcc/vec.h	(working copy)
> > @@ -482,6 +482,15 @@
> >    void quick_grow (unsigned len);
> >    void quick_grow_cleared (unsigned len);
> >  
> > +  /* STL like iterator interface.  */
> > +  typedef T* iterator;
> > +  typedef const T* const_iterator;
> > +
> > +  iterator begin (void) { return &m_vecdata[0]; }
> > +  iterator end (void) { return &m_vecdata[m_vecpfx.m_num]; }
> > +  const_iterator begin (void) const { return &m_vecdata[0]; }
> > +  const_iterator end (void) const { &m_vecdata[m_vecpfx.m_num]; }
> > 
> > This is because raw pointers can be used as random access iterators.

> yeah, somehow didn't occur to me T* just works (not that it wouldn't be
> easier to see if the type had * in it)
> 

Actually, it's the other way around.  (STL) Iterators behave like
pointers.  The only difference is that depending on the iterator
capabilities (which depend on the container type), the amount of pointer
arithmetic that can be done with an iterator is restricted, where a
random access iterator is a like a raw pointer.

> actually what I really want to do is make returning a const vector part
> of the api for getting the edge list from a basic block and then just
> write
> 
> for (edge *e = vec.begin (); e != vec.end (); e++)
> 
> which imo makes it clear what's happening and is short, but I guess
> richi doesn't like the interface being that a vector is returned :/

The above usage assumes that the container stores elements in contiguous
memory.  I know it's highly hypothetical in this case, but if one day
somebody wanted to try out a more suitable container to store edges in
basic blocks (let's say a linked list), it would be slightly impossible
to replace it without touching all the code.
Apart from that, I guess iteration over a linked list or some kind of
tree would look totally different.  I think iteration should look the
same regardless of the container type being used.  It makes it easier to
jump into foreign code and helps focusing on the actual problem the code
is trying to solve.


> > but that means, that there can be only one type of edge container ever.
> 
> gcc seems to have survived for a long time with a single edge_iterator
> so I don't see much reason to worry about allowing
> basic_block::edge_iterator and foobar::edge_iterator.

Yes, having one freestanding edge_iterator type is probably sufficient
for the near future.  I just didn't want to break existing code.

> well, I meant edge_iterator instead of basic_block::edge_iterator which
> afaik is what you proposed?

Yes, I was proposing to have a basic_block::edge_iterator or
basic_block::edge_container::iterator or something similar.

> I know doing this for pointer wrappers is common and I think that's
> fine.  However I'm not really convinced we need to or should make
> basic_block a pointer wrapper class, I'd wrather see basic_block_def
> become basic_block, and use basic_block * all over.

That could also be an option.  Although having pointer wrappers already
in place might open some other opportunities in the future.  For
instance it would make it relatively easy to try out reducing the number
of garbage collected objects by adding smart pointer functionality to
the pointer wrapper.

> 
> > Overloading "operator ->" is also required in iterators.  See
> > http://www.cplusplus.com/reference/iterator/
> > If raw pointers are used as iterators (as in my example patch), there's
> > nothing to overload for those of course.
> 
> yeah, I'm not really a fan of that style of iterator :/

But in the end, that iterator style allows writing code as you suggested
above:

> for (edge *e = vec.begin (); e != vec.end (); e++)

The only difference is that you don't write "edge*" but e.g.
"vec<edge>::iterator e", or just "auto" in C++11.

Cheers,
Oleg