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

[François Dumont]

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
>




-------------- next part --------------
A non-text attachment was scrubbed...
Name: tree.patch
Type: text/x-patch
Size: 51498 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20140730/52a31746/attachment.bin>