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

[François Dumont]

Still no feedback regarding this proposal ?

On 19/08/2014 22:14, François Dumont wrote:
> Any news regarding this proposal ?
>
> Thanks
>
> François
>
>
> On 30/07/2014 23:39, François Dumont wrote:
>> Hi
>>
>>        Now that patch on testsuite allocator is in I would like to 
>> reactivate this one. Here it is again.
>>
>>        See previous answer below regarding modification of 
>> _M_begin/_M_cbegin.
>>
>> 2014-07-30  François Dumont  <fdumont@gcc.gnu.org>
>>
>>        PR libstdc++/29988
>>        * include/bits/stl_tree.h (_Rb_tree_reuse_or_alloc_node<>): New.
>>        (_Rb_tree_alloc_node<>): New.
>>        (_Rb_tree_impl<>): Remove unused _Is_pod_comparator template 
>> parameter.
>> (_Rb_tree<>::operator=(_Rb_tree<>&&)): New.
>>        (_Rb_tree<>::_M_assign_unique): New.
>>        (_Rb_tree<>::_M_assign_equal): New.
>>        (_Rb_tree<>): Adapt to reuse allocated nodes as much as possible.
>>        * include/bits/stl_map.h
>> (std::map<>::operator=(std::map<>&&)): Default implementation.
>>        (std::map<>::operator=(initializer_list<>)): Adapt to use
>>        _Rb_tree::_M_assign_unique.
>>        * include/bits/stl_multimap.h
>> (std::multimap<>::operator=(std::multimap<>&&)): Default implementation.
>> (std::multimap<>::operator=(initializer_list<>)): Adapt to use
>>        _Rb_tree::_M_assign_equal.
>>        * include/bits/stl_set.h
>> (std::set<>::operator=(std::set<>&&)): Default implementation.
>>        (std::set<>::operator=(initializer_list<>)): Adapt to use
>>        _Rb_tree::_M_assign_unique.
>>        * include/bits/stl_multiset.h
>> (std::multiset<>::operator=(std::multiset<>&&)): Default implementation.
>> (std::multiset<>::operator=(initializer_list<>)): Adapt to use
>>        _Rb_tree::_M_assign_equal.
>>        * testsuite/23_containers/map/allocator/copy_assign.cc 
>> (test03): New.
>>        * testsuite/23_containers/map/allocator/init-list.cc: New.
>>        * testsuite/23_containers/map/allocator/move_assign.cc 
>> (test03): New.
>>        * testsuite/23_containers/multimap/allocator/copy_assign.cc
>>        (test03): New.
>>        * testsuite/23_containers/multimap/allocator/init-list.cc: New.
>>        * testsuite/23_containers/multimap/allocator/move_assign.cc
>>        (test03): New.
>>        * testsuite/23_containers/multiset/allocator/copy_assign.cc
>>        (test03): New.
>>        * testsuite/23_containers/multiset/allocator/init-list.cc: New.
>>        * testsuite/23_containers/multiset/allocator/move_assign.cc
>>        (test03): New.
>>        * testsuite/23_containers/set/allocator/copy_assign.cc 
>> (test03): New.
>>        * testsuite/23_containers/set/allocator/init-list.cc: New.
>>        * testsuite/23_containers/set/allocator/move_assign.cc 
>> (test03): New.
>>
>> Tested under linux x86_64.
>>
>> Ok to commit ?
>>
>> François
>>
>>
>> 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.
>>>
>>> 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.
>>>>
>>>>>       _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.
>>>
>>> François
>>>
>>
>>
>>
>>
>