Hi
Here is more or less the patch proposed on the ticket with the test
case also provided in the ticket.
2014-11-04 François Dumont fdum...@gcc.gnu.org
Jonathan Wakely jwak...@redhat.com
PR libstdc++/63698
* include/bits/stl_tree.h (_Reuse_or_alloc_node): Simplify constructor.
Always move to the left node if there is one.
* testsuite/23_containers/set/allocator/move_assign.cc (test04): New.
Tested under Linux x86_64, ok to commit ?
François
Index: include/bits/stl_tree.h
===
--- include/bits/stl_tree.h (revision 217101)
+++ include/bits/stl_tree.h (working copy)
@@ -359,16 +359,20 @@
typedef const _Rb_tree_node_Val* _Const_Link_type;
private:
- // Functor recycling a pool of nodes and using allocation once the pool is
- // empty.
+ // Functor recycling a pool of nodes and using allocation once the pool
+ // is empty.
struct _Reuse_or_alloc_node
{
- _Reuse_or_alloc_node(const _Rb_tree_node_base __header,
- _Rb_tree __t)
- : _M_root(__header._M_parent), _M_nodes(__header._M_right), _M_t(__t)
+ _Reuse_or_alloc_node(_Rb_tree __t)
+ : _M_root(__t._M_root()), _M_nodes(__t._M_rightmost()), _M_t(__t)
{
if (_M_root)
- _M_root-_M_parent = 0;
+ {
+ _M_root-_M_parent = 0;
+
+ if (_M_nodes-_M_left)
+ _M_nodes = _M_nodes-_M_left;
+ }
else
_M_nodes = 0;
}
@@ -420,6 +424,9 @@
while (_M_nodes-_M_right)
_M_nodes = _M_nodes-_M_right;
+
+ if (_M_nodes-_M_left)
+ _M_nodes = _M_nodes-_M_left;
}
}
else // __node is on the left.
@@ -436,7 +443,7 @@
_Rb_tree _M_t;
};
- // Functor similar to the previous one but without any pool of node to
+ // Functor similar to the previous one but without any pool of nodes to
// recycle.
struct _Alloc_node
{
@@ -1271,7 +1278,7 @@
// Try to move each node reusing existing nodes and copying __x nodes
// structure.
- _Reuse_or_alloc_node __roan(_M_impl._M_header, *this);
+ _Reuse_or_alloc_node __roan(*this);
_M_impl._M_reset();
if (__x._M_root() != nullptr)
{
@@ -1297,7 +1304,7 @@
_Rb_tree_Key, _Val, _KeyOfValue, _Compare, _Alloc::
_M_assign_unique(_Iterator __first, _Iterator __last)
{
- _Reuse_or_alloc_node __roan(this-_M_impl._M_header, *this);
+ _Reuse_or_alloc_node __roan(*this);
_M_impl._M_reset();
for (; __first != __last; ++__first)
_M_insert_unique_(end(), *__first, __roan);
@@ -1310,7 +1317,7 @@
_Rb_tree_Key, _Val, _KeyOfValue, _Compare, _Alloc::
_M_assign_equal(_Iterator __first, _Iterator __last)
{
- _Reuse_or_alloc_node __roan(this-_M_impl._M_header, *this);
+ _Reuse_or_alloc_node __roan(*this);
_M_impl._M_reset();
for (; __first != __last; ++__first)
_M_insert_equal_(end(), *__first, __roan);
@@ -1342,7 +1349,7 @@
}
#endif
- _Reuse_or_alloc_node __roan(this-_M_impl._M_header, *this);
+ _Reuse_or_alloc_node __roan(*this);
_M_impl._M_reset();
_M_impl._M_key_compare = __x._M_impl._M_key_compare;
if (__x._M_root() != 0)
Index: testsuite/23_containers/set/allocator/move_assign.cc
===
--- testsuite/23_containers/set/allocator/move_assign.cc (revision 217101)
+++ testsuite/23_containers/set/allocator/move_assign.cc (working copy)
@@ -18,6 +18,8 @@
// { dg-options -std=gnu++11 }
#include set
+#include random
+
#include testsuite_hooks.h
#include testsuite_allocator.h
@@ -89,10 +91,43 @@
VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 );
}
+void test04()
+{
+ bool test __attribute__((unused)) = true;
+
+ using namespace __gnu_test;
+
+ typedef tracker_allocatorint alloc_type;
+ typedef std::setint, std::lessint, alloc_type test_type;
+
+ std::mt19937 rng;
+ std::uniform_int_distributionint d;
+ std::uniform_int_distributionint::param_type p{0, 100};
+ std::uniform_int_distributionint::param_type x{0, 1000};
+
+ for (int i = 0; i 10; ++i)
+ {
+test_type l, r;
+for (int n = d(rng, p); n 0; --n)
+{
+ int i = d(rng, x);
+ l.insert(i);
+ r.insert(i);
+
+ tracker_allocator_counter::reset();
+
+ l = r;
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == 0 );
+}
+ }
+}
+
int main()
{
test01();
test02();
test03();
+ test04();
return 0;
}
