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

[François Dumont]

>>> 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).

I also prefer avoiding const_cast usually and for me _M_copy just mean 
that it copies the data structure either it is by moving its elements or 
copying them too. But if you prefer it this way I will do so.

>
>
>>     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.
>
>
Too bad.

New patch in a couple of day then.

François