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

[François Dumont]

Hi

     Here is the patch to reuse allocated nodes in the _Rb_tree 
implementation like it is done in the _Hashtable. I have associated it 
to bugzilla 29988 even if my patch also cover the new C++11 move assign 
operator and assignment from initialization list. I took a look to the 
code proposed in 29988 and it is more or less what I have done even if I 
benefit from C++11 lambdas to reuse more code.

     I have changed propagating_allocator so that we can combine it with 
any other allocator. I combined it with the tracker_allocator so that I 
can control propagation of the allocator and at the same time track 
allocations.

2014-06-11  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<>&&)): Use 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<>&&)): Use 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<>&&)): Use 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<>&&)): Use default
     implementation.
     (std::multiset<>::operator=(initializer_list<>)): Adapt to use
     _Rb_tree::_M_assign_equal.
     * testsuite/util/testsuite_allocator.h (__gnu_test::uneq_allocator<>):
     Add _Alloc template parameter, default is std::allocator. Inherit from
     _Alloc.
     (__gnu_test::propagating_allocator<>): Add _Alloc template parameter,
     default is std::allocator.
     * 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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: tree.patch
Type: text/x-patch
Size: 59010 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20140611/9c94079d/attachment.bin>