Re: [patch] libstdc++/29988 Rb_Tree reuse allocated nodes

[Jonathan Wakely <jwakely at redhat dot com>]

On 30/07/14 23:39 +0200, François Dumont wrote:
> On 16/06/2014 22:23, François Dumont wrote:
> > Hi
> >
> >    Here is another proposal taking into account your remarks except
> > the one below.
> >
> >    In fact I had no problem with lambda, I just needed to store them
> > in a variable, lambda do not need to be made mutable.

You could also change _M_copy's _NodeGen& parameter to _NodeGen&& for
C++11 mode, then you don't need to use lvalues for the lambdas. I
looks as though _M_copy is the only function affected, as the other
functions with a _NodeGen template parameter are passed lvalues
anyway.

That's not important though, just passing lvalues works OK too.

> > On 11/06/2014 14:02, Jonathan Wakely wrote:
> > > > @@ -514,11 +651,11 @@
> > > >      { return this->_M_impl._M_header._M_right; }
> > > >
> > > >      _Link_type
> > > > -      _M_begin() _GLIBCXX_NOEXCEPT
> > > > +      _M_begin() const _GLIBCXX_NOEXCEPT
> > > >      { return
> > > > static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
> > >
> > > What's the purpose of this change?
> > > Although it can be 'const' it is consistent with the usual
> > > begin()/end() functions that the functions returning a mutable iterator
> > > are non-const and the functions returning a constant iterator are const.

I'm still concerned about this part, especially as _M_end() isn't made
const!

> > > >      _Const_Link_type
> > > > -      _M_begin() const _GLIBCXX_NOEXCEPT
> > > > +      _M_cbegin() const _GLIBCXX_NOEXCEPT
> > > >      {
> > > >    return static_cast<_Const_Link_type>
> > > >      (this->_M_impl._M_header._M_parent);
> > > > @@ -529,7 +666,7 @@
> > > >      { return
> > > > reinterpret_cast<_Link_type>(&this->_M_impl._M_header); }
> > > >
> > > >      _Const_Link_type
> > > > -      _M_end() const _GLIBCXX_NOEXCEPT
> > > > +      _M_cend() const _GLIBCXX_NOEXCEPT
> > > >      { return
> > > > reinterpret_cast<_Const_Link_type>(&this->_M_impl._M_header); }
> > > >
> > > >      static const_reference
> > >
> > > I'm not very comfortable with this renaming.
> > >
> > > Having consistent _M_begin() functions allows using them in template
> > > code that doesn't care if it's using the const or non-const version.
> > I try to revert this part and so remember why I did it in the first
> > place.
> >
> > I needed to change _M_copy signature to:
> >
> >      _Link_type
> >      _M_copy(_Link_type __x, _Link_type __p)
> >
> >    because I now use this method to also move the elements of the
> > data structure, I cannot move from a _Const_Like_type so I change
> > first parameter to _Link_type. I see that there are some code
> > duplications to deal with _Const_Link_type and _Link_type in 2
> > different part of the code but I didn't want to duplicate again here
> > and simply made _M_copy more flexible by taking a _Link_type rather
> > than a _Const_Link_type.
> >
> >    I don't really see interest of the existing code duplications so I
> > prefer to not do the same and write the code only once.

There are alternatives to duplicating the code. _M_copy could be:

 template<typename _Ptr, typename _NodeGen>
   _Link_type
   _M_copy(_Ptr, _Link_type, _NodeGen&&);

I've been experimenting with a patch that does this instead:

       _M_root() = _M_copy(__x._M_begin(), _M_end(),
           [&__an](const value_type& __val) {
             auto& __nc_val = const_cast<value_type&>(__val);
             return __an(std::move_if_noexcept(__nc_val));
           });

I'm not very happy about having to use a const_cast, but then I'm also
not very happy having a function called _M_copy which takes a
non-const pointer because it might alter the thing it's copying.

At least with the const_cast the _M_copy function is logically doing a
non-modifying copy, but the caller can decide to pass in a lambda that
moves instead of copying, if it knows that it's OK to modify the
source object (because it's known to have been an rvalue).


>     protected:
> -      template<typename _Key_compare, 
> -	       bool _Is_pod_comparator = __is_pod(_Key_compare)>
> +      template<typename _Key_compare>
>         struct _Rb_tree_impl : public _Node_allocator

I don't think we should remove this parameter, it alters the mangled
name for _Rb_tree_impl symbols, which means users can get two
different symbols in their program and the linker will keep both.

It's redundant, but doesn't actually cause any harm. Maybe just rename
the parameter to _Unused or something, but leave it there, with the
same default argument.