Rb tree node recycling patch

[François Dumont]

Hi

     Here is a patch to add recycling of Rb tree nodes when possible.

     I replaced the _Rb_tree::_M_move_assign with a move assignment 
operator to benefit from:
- move of elements when the whole data structure cannot be moved
- faster data structure cloning rather than full regeneration of the 
tree when _M_move_assign was failing

     Note that this patch contains also a cleanup of a useless template 
parameter _Is_pod_comparator on _Rb_tree_impl. If you want to apply it 
quickly for 4.9 do not hesitate.

     I haven't done any specific test for this feature, existing ones 
looks good enough to me. If you want me to add some I will when back 
from vacation. I am mostly submitting this patch to show you that I 
worked on it and you do not need to do it yourself.

2013-12-27  François Dumont <fdumont@gcc.gnu.org>

     * include/bits/stl_tree.h (_Rb_tree_reuse_or_alloc_node<>): New.
     (_Rb_tree_alloc_node<>): Likewise.
     (_Rb_tree<>::_M_clone_node): Made template to take a node
     generator.
     (_Rb_tree_impl<>): Remove unused _Is_pod_comparator template
     value.
     (_Rb_tree<>::_M_move_assign): Replace by...
     (_Rb_tree<>::operator(_Rb_tree&&)): ...this.
     (_Rb_tree_impl<>::_M_reset): New.
     (_Rb_tree<>::_M_insert_): Add node generator parameter.
     (_Rb_tree<>::_M_copy): Add overload taking a node generator.
     (_Rb_tree<>::_M_insert_unique_): Add node generator parameter.
     (_Rb_tree<>::_M_insert_equal_): Add node generator parameter.
     (_Rb_tree<>::_M_assign_unique): New.
     (_Rb_tree<>::_M_assign_equal): New.
     (_Rb_tree<>): Adapt to use _Rb_tree_impl<>::_M_reset and reuse
     nodes as much as possible.
     * include/bits/stl_set.h (set<>::operator=(set<>&&): Adapt to use
     _Rb_tree move assignment operator.
     (set<>::operator=(initializer_list<>)): Adapt to use
     _Rb_tree<>::_M_assign_unique.
     * include/bits/stl_multiset.h
     (multiset<>::operator=(multiset<>&&)): Adapt to use
     _Rb_tree move assignment operator.
     (multiset<>::operator=(initializer_list<>)): Adapt to use
     _Rb_tree<>::_M_assign_equal.
     * include/bits/stl_map.h (map<>::operator=(map<>&&): Adapt to use
     _Rb_tree move assignment operator.
     (map<>::operator=(initializer_list<>)): Adapt to use
     _Rb_tree<>::_M_assign_unique.
     * include/bits/stl_multimap.h
     (multimap<>::operator=(multimap<>&&)): Adapt to use
     _Rb_tree move assignment operator.
     (multimap<>::operator=(initializer_list<>)): Adapt to use
     _Rb_tree<>::_M_assign_equal.

Tested under Linux x86_64.

Happy new year.

François

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