This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] libstdc++/29988 Rb_Tree reuse allocated nodes
- From: François Dumont <frs dot dumont at gmail dot com>
- To: "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>, gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: Wed, 11 Jun 2014 09:17:34 +0200
- Subject: [patch] libstdc++/29988 Rb_Tree reuse allocated nodes
- Authentication-results: sourceware.org; auth=none
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
Index: include/bits/stl_map.h
===================================================================
--- include/bits/stl_map.h (revision 211388)
+++ include/bits/stl_map.h (working copy)
@@ -297,28 +297,9 @@
}
#if __cplusplus >= 201103L
- /**
- * @brief %Map move assignment operator.
- * @param __x A %map of identical element and allocator types.
- *
- * The contents of @a __x are moved into this map (without copying
- * if the allocators compare equal or get moved on assignment).
- * Afterwards @a __x is in a valid, but unspecified state.
- */
+ /// Move assignment operator.
map&
- operator=(map&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
- {
- if (!_M_t._M_move_assign(__x._M_t))
- {
- // The rvalue's allocator cannot be moved and is not equal,
- // so we need to individually move each element.
- clear();
- insert(std::__make_move_if_noexcept_iterator(__x.begin()),
- std::__make_move_if_noexcept_iterator(__x.end()));
- __x.clear();
- }
- return *this;
- }
+ operator=(map&&) = default;
/**
* @brief %Map list assignment operator.
@@ -334,8 +315,7 @@
map&
operator=(initializer_list<value_type> __l)
{
- this->clear();
- this->insert(__l.begin(), __l.end());
+ _M_t._M_assign_unique(__l.begin(), __l.end());
return *this;
}
#endif
Index: include/bits/stl_multimap.h
===================================================================
--- include/bits/stl_multimap.h (revision 211388)
+++ include/bits/stl_multimap.h (working copy)
@@ -292,28 +292,9 @@
}
#if __cplusplus >= 201103L
- /**
- * @brief %Multimap move assignment operator.
- * @param __x A %multimap of identical element and allocator types.
- *
- * The contents of @a __x are moved into this multimap (without copying
- * if the allocators compare equal or get moved on assignment).
- * Afterwards @a __x is in a valid, but unspecified state.
- */
+ /// Move assignment operator.
multimap&
- operator=(multimap&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
- {
- if (!_M_t._M_move_assign(__x._M_t))
- {
- // The rvalue's allocator cannot be moved and is not equal,
- // so we need to individually move each element.
- clear();
- insert(std::__make_move_if_noexcept_iterator(__x.begin()),
- std::__make_move_if_noexcept_iterator(__x.end()));
- __x.clear();
- }
- return *this;
- }
+ operator=(multimap&&) = default;
/**
* @brief %Multimap list assignment operator.
@@ -329,8 +310,7 @@
multimap&
operator=(initializer_list<value_type> __l)
{
- this->clear();
- this->insert(__l.begin(), __l.end());
+ _M_t._M_assign_equal(__l.begin(), __l.end());
return *this;
}
#endif
Index: include/bits/stl_multiset.h
===================================================================
--- include/bits/stl_multiset.h (revision 211388)
+++ include/bits/stl_multiset.h (working copy)
@@ -263,28 +263,9 @@
}
#if __cplusplus >= 201103L
- /**
- * @brief %Multiset move assignment operator.
- * @param __x A %multiset of identical element and allocator types.
- *
- * The contents of @a __x are moved into this %multiset (without
- * copying if the allocators compare equal or get moved on assignment).
- * Afterwards @a __x is in a valid, but unspecified state.
- */
+ /// Move assignment operator.
multiset&
- operator=(multiset&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
- {
- if (!_M_t._M_move_assign(__x._M_t))
- {
- // The rvalue's allocator cannot be moved and is not equal,
- // so we need to individually move each element.
- clear();
- insert(std::__make_move_if_noexcept_iterator(__x._M_t.begin()),
- std::__make_move_if_noexcept_iterator(__x._M_t.end()));
- __x.clear();
- }
- return *this;
- }
+ operator=(multiset&&) = default;
/**
* @brief %Multiset list assignment operator.
@@ -300,8 +281,7 @@
multiset&
operator=(initializer_list<value_type> __l)
{
- this->clear();
- this->insert(__l.begin(), __l.end());
+ _M_t._M_assign_equal(__l.begin(), __l.end());
return *this;
}
#endif
Index: include/bits/stl_set.h
===================================================================
--- include/bits/stl_set.h (revision 211388)
+++ include/bits/stl_set.h (working copy)
@@ -267,28 +267,9 @@
}
#if __cplusplus >= 201103L
- /**
- * @brief %Set move assignment operator.
- * @param __x A %set of identical element and allocator types.
- *
- * The contents of @a __x are moved into this %set (without copying
- * if the allocators compare equal or get moved on assignment).
- * Afterwards @a __x is in a valid, but unspecified state.
- */
+ /// Move assignment operator.
set&
- operator=(set&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
- {
- if (!_M_t._M_move_assign(__x._M_t))
- {
- // The rvalue's allocator cannot be moved and is not equal,
- // so we need to individually move each element.
- clear();
- insert(std::__make_move_if_noexcept_iterator(__x._M_t.begin()),
- std::__make_move_if_noexcept_iterator(__x._M_t.end()));
- __x.clear();
- }
- return *this;
- }
+ operator=(set&&) = default;
/**
* @brief %Set list assignment operator.
@@ -304,8 +285,7 @@
set&
operator=(initializer_list<value_type> __l)
{
- this->clear();
- this->insert(__l.begin(), __l.end());
+ _M_t._M_assign_unique(__l.begin(), __l.end());
return *this;
}
#endif
Index: include/bits/stl_tree.h
===================================================================
--- include/bits/stl_tree.h (revision 211388)
+++ include/bits/stl_tree.h (working copy)
@@ -330,6 +330,111 @@
const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT
{ return __x._M_node != __y._M_node; }
+ // Functor recycling a pool of nodes and using allocation once the pool is
+ // empty.
+ template<typename _RbTree>
+ struct _Rb_tree_reuse_or_alloc_node
+ {
+ private:
+ typedef _RbTree __rb_tree;
+ typedef _Rb_tree_node<typename _RbTree::value_type> __node_type;
+
+ public:
+ _Rb_tree_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)
+ {
+ if (_M_root)
+ _M_root->_M_parent = 0;
+ else
+ _M_nodes = 0;
+ }
+
+ ~_Rb_tree_reuse_or_alloc_node()
+ { _M_t._M_erase(static_cast<__node_type*>(_M_root)); }
+
+ template<typename _Arg>
+ __node_type*
+#if __cplusplus < 201103L
+ operator()(const _Arg& __arg) const
+#else
+ operator()(_Arg&& __arg) const
+#endif
+ {
+ __node_type* __node = static_cast<__node_type*>(_M_extract());
+ if (__node)
+ {
+ _M_t._M_destroy_node(__node);
+ _M_t._M_construct_node(__node, _GLIBCXX_FORWARD(_Arg, __arg));
+ return __node;
+ }
+
+ return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg));
+ }
+
+ private:
+ typedef _Rb_tree_node_base __node_base;
+
+ __node_base*
+ _M_extract() const
+ {
+ if (!_M_nodes)
+ return _M_nodes;
+
+ __node_base* __node = _M_nodes;
+ _M_nodes = _M_nodes->_M_parent;
+ if (_M_nodes)
+ {
+ if (_M_nodes->_M_right == __node)
+ {
+ _M_nodes->_M_right = 0;
+
+ if (_M_nodes->_M_left)
+ {
+ _M_nodes = _M_nodes->_M_left;
+
+ while (_M_nodes->_M_right)
+ _M_nodes = _M_nodes->_M_right;
+ }
+ }
+ else // __node is on the left.
+ _M_nodes->_M_left = 0;
+ }
+ else
+ _M_root = 0;
+
+ return __node;
+ }
+
+ mutable __node_base* _M_root;
+ mutable __node_base* _M_nodes;
+ _RbTree& _M_t;
+ };
+
+ // Functor similar to the previous one but without any pool of node to recycle.
+ template<typename _RbTree>
+ struct _Rb_tree_alloc_node
+ {
+ private:
+ typedef _Rb_tree_node<typename _RbTree::value_type> __node_type;
+
+ public:
+ _Rb_tree_alloc_node(_RbTree& __t)
+ : _M_t(__t) { }
+
+ template<typename _Arg>
+ __node_type*
+#if __cplusplus < 201103L
+ operator()(const _Arg& __arg) const
+#else
+ operator()(_Arg&& __arg) const
+#endif
+ { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); }
+
+ private:
+ _RbTree& _M_t;
+ };
+
void
_Rb_tree_insert_and_rebalance(const bool __insert_left,
_Rb_tree_node_base* __x,
@@ -349,6 +454,12 @@
rebind<_Rb_tree_node<_Val> >::other _Node_allocator;
typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits;
+ template<typename _RT>
+ friend struct _Rb_tree_alloc_node;
+ typedef _Rb_tree_alloc_node<_Rb_tree> __alloc_node_t;
+ template<typename _RT>
+ friend struct _Rb_tree_reuse_or_alloc_node;
+ typedef _Rb_tree_reuse_or_alloc_node<_Rb_tree> __reuse_or_alloc_node_t;
protected:
typedef _Rb_tree_node_base* _Base_ptr;
@@ -389,44 +500,55 @@
{ _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); }
#if __cplusplus < 201103L
- _Link_type
- _M_create_node(const value_type& __x)
+ void
+ _M_construct_node(_Link_type __node, const value_type& __x)
{
- _Link_type __tmp = _M_get_node();
__try
- { get_allocator().construct(__tmp->_M_valptr(), __x); }
+ { get_allocator().construct(__node->_M_valptr(), __x); }
__catch(...)
{
- _M_put_node(__tmp);
+ _M_put_node(__node);
__throw_exception_again;
}
+ }
+
+ _Link_type
+ _M_create_node(const value_type& __x)
+ {
+ _Link_type __tmp = _M_get_node();
+ _M_construct_node(__tmp, __x);
return __tmp;
}
void
_M_destroy_node(_Link_type __p)
- {
- get_allocator().destroy(__p->_M_valptr());
- _M_put_node(__p);
- }
+ { get_allocator().destroy(__p->_M_valptr()); }
#else
template<typename... _Args>
- _Link_type
- _M_create_node(_Args&&... __args)
+ void
+ _M_construct_node(_Link_type __node, _Args&&... __args)
{
- _Link_type __tmp = _M_get_node();
__try
{
- ::new(__tmp) _Rb_tree_node<_Val>;
+ ::new(__node) _Rb_tree_node<_Val>();
_Alloc_traits::construct(_M_get_Node_allocator(),
- __tmp->_M_valptr(),
+ __node->_M_valptr(),
std::forward<_Args>(__args)...);
}
__catch(...)
{
- _M_put_node(__tmp);
+ __node->~_Rb_tree_node<_Val>();
+ _M_put_node(__node);
__throw_exception_again;
}
+ }
+
+ template<typename... _Args>
+ _Link_type
+ _M_create_node(_Args&&... __args)
+ {
+ _Link_type __tmp = _M_get_node();
+ _M_construct_node(__tmp, std::forward<_Args>(__args)...);
return __tmp;
}
@@ -435,23 +557,29 @@
{
_Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr());
__p->~_Rb_tree_node<_Val>();
- _M_put_node(__p);
}
#endif
- _Link_type
- _M_clone_node(_Const_Link_type __x)
+ void
+ _M_drop_node(_Link_type __p) _GLIBCXX_NOEXCEPT
{
- _Link_type __tmp = _M_create_node(*__x->_M_valptr());
- __tmp->_M_color = __x->_M_color;
- __tmp->_M_left = 0;
- __tmp->_M_right = 0;
- return __tmp;
+ _M_destroy_node(__p);
+ _M_put_node(__p);
}
+ template<typename _NodeGen>
+ _Link_type
+ _M_clone_node(_Link_type __x, const _NodeGen& __node_gen)
+ {
+ _Link_type __tmp = __node_gen(*__x->_M_valptr());
+ __tmp->_M_color = __x->_M_color;
+ __tmp->_M_left = 0;
+ __tmp->_M_right = 0;
+ return __tmp;
+ }
+
protected:
- template<typename _Key_compare,
- bool _Is_pod_comparator = __is_pod(_Key_compare)>
+ template<typename _Key_compare>
struct _Rb_tree_impl : public _Node_allocator
{
_Key_compare _M_key_compare;
@@ -475,6 +603,15 @@
{ _M_initialize(); }
#endif
+ void
+ _M_reset()
+ {
+ this->_M_header._M_parent = 0;
+ this->_M_header._M_left = &this->_M_header;
+ this->_M_header._M_right = &this->_M_header;
+ this->_M_node_count = 0;
+ }
+
private:
void
_M_initialize()
@@ -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); }
_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
@@ -603,9 +740,9 @@
const key_type& __k);
#if __cplusplus >= 201103L
- template<typename _Arg>
+ template<typename _Arg, typename _NodeGen>
iterator
- _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v);
+ _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, const _NodeGen&);
iterator
_M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z);
@@ -624,9 +761,10 @@
iterator
_M_insert_equal_lower_node(_Link_type __z);
#else
- iterator
- _M_insert_(_Base_ptr __x, _Base_ptr __y,
- const value_type& __v);
+ template<typename _NodeGen>
+ iterator
+ _M_insert_(_Base_ptr __x, _Base_ptr __y,
+ const value_type& __v, const _NodeGen&);
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 233. Insertion hints in associative containers.
@@ -637,8 +775,13 @@
_M_insert_equal_lower(const value_type& __x);
#endif
+ template<typename _NodeGen>
+ _Link_type
+ _M_copy(_Link_type __x, _Link_type __p, const _NodeGen&);
+
_Link_type
- _M_copy(_Const_Link_type __x, _Link_type __p);
+ _M_copy(_Link_type __x, _Link_type __p)
+ { return _M_copy(__x, __p, __alloc_node_t(*this)); }
void
_M_erase(_Link_type __x);
@@ -688,7 +831,7 @@
_Rb_tree(const _Rb_tree& __x, const allocator_type& __a)
: _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a))
{
- if (__x._M_root() != 0)
+ if (__x._M_root() != nullptr)
{
_M_root() = _M_copy(__x._M_begin(), _M_end());
_M_leftmost() = _S_minimum(_M_root());
@@ -792,14 +935,30 @@
iterator
_M_insert_equal(_Arg&& __x);
- template<typename _Arg>
+ template<typename _Arg, typename _NodeGen>
iterator
- _M_insert_unique_(const_iterator __position, _Arg&& __x);
+ _M_insert_unique_(const_iterator __pos, _Arg&& __x, const _NodeGen&);
template<typename _Arg>
- iterator
- _M_insert_equal_(const_iterator __position, _Arg&& __x);
+ iterator
+ _M_insert_unique_(const_iterator __pos, _Arg&& __x)
+ {
+ return _M_insert_unique_(__pos, std::forward<_Arg>(__x),
+ __alloc_node_t(*this));
+ }
+ template<typename _Arg, typename _NodeGen>
+ iterator
+ _M_insert_equal_(const_iterator __pos, _Arg&& __x, const _NodeGen&);
+
+ template<typename _Arg>
+ iterator
+ _M_insert_equal_(const_iterator __pos, _Arg&& __x)
+ {
+ return _M_insert_equal_(__pos, std::forward<_Arg>(__x),
+ __alloc_node_t(*this));
+ }
+
template<typename... _Args>
pair<iterator, bool>
_M_emplace_unique(_Args&&... __args);
@@ -822,11 +981,22 @@
iterator
_M_insert_equal(const value_type& __x);
+ template<typename _NodeGen>
+ iterator
+ _M_insert_unique_(const_iterator __pos, const value_type& __x,
+ const _NodeGen&);
+
iterator
- _M_insert_unique_(const_iterator __position, const value_type& __x);
+ _M_insert_unique_(const_iterator __pos, const value_type& __x)
+ { return _M_insert_unique_(__pos, __x, __alloc_node_t(*this)); }
+ template<typename _NodeGen>
+ iterator
+ _M_insert_equal_(const_iterator __pos, const value_type& __x,
+ const _NodeGen&);
iterator
- _M_insert_equal_(const_iterator __position, const value_type& __x);
+ _M_insert_equal_(const_iterator __pos, const value_type& __x)
+ { return _M_insert_equal_(__pos, __x, __alloc_node_t(*this)); }
#endif
template<typename _InputIterator>
@@ -906,10 +1076,7 @@
clear() _GLIBCXX_NOEXCEPT
{
_M_erase(_M_begin());
- _M_leftmost() = _M_end();
- _M_root() = 0;
- _M_rightmost() = _M_end();
- _M_impl._M_node_count = 0;
+ _M_impl._M_reset();
}
// Set operations.
@@ -928,7 +1095,7 @@
const_iterator
lower_bound(const key_type& __k) const
- { return _M_lower_bound(_M_begin(), _M_end(), __k); }
+ { return _M_lower_bound(_M_cbegin(), _M_cend(), __k); }
iterator
upper_bound(const key_type& __k)
@@ -936,7 +1103,7 @@
const_iterator
upper_bound(const key_type& __k) const
- { return _M_upper_bound(_M_begin(), _M_end(), __k); }
+ { return _M_upper_bound(_M_cbegin(), _M_cend(), __k); }
pair<iterator, iterator>
equal_range(const key_type& __k);
@@ -949,9 +1116,17 @@
__rb_verify() const;
#if __cplusplus >= 201103L
- bool
- _M_move_assign(_Rb_tree&);
+ _Rb_tree&
+ operator=(_Rb_tree&&) noexcept(_Alloc_traits::_S_nothrow_move());
+ template<typename _Iterator>
+ void
+ _M_assign_unique(_Iterator, _Iterator);
+
+ template<typename _Iterator>
+ void
+ _M_assign_equal(_Iterator, _Iterator);
+
private:
// Move elements from container with equal allocator.
void
@@ -1027,7 +1202,7 @@
: _M_impl(__x._M_impl._M_key_compare, std::move(__a))
{
using __eq = integral_constant<bool, _Alloc_traits::_S_always_equal()>;
- if (__x._M_root() != 0)
+ if (__x._M_root() != nullptr)
_M_move_data(__x, __eq());
}
@@ -1060,7 +1235,10 @@
_M_move_data(__x, std::true_type());
else
{
- _M_root() = _M_copy(__x._M_begin(), _M_end());
+ __alloc_node_t __an(*this);
+ _M_root() = _M_copy(__x._M_begin(), _M_end(),
+ [&__an](value_type& __val)
+ { return __an(std::move_if_noexcept(__val)); });
_M_leftmost() = _S_minimum(_M_root());
_M_rightmost() = _S_maximum(_M_root());
_M_impl._M_node_count = __x._M_impl._M_node_count;
@@ -1069,9 +1247,10 @@
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
- bool
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
- _M_move_assign(_Rb_tree& __x)
+ operator=(_Rb_tree&& __x)
+ noexcept(_Alloc_traits::_S_nothrow_move())
{
_M_impl._M_key_compare = __x._M_impl._M_key_compare;
if (_Alloc_traits::_S_propagate_on_move_assign()
@@ -1079,14 +1258,55 @@
|| _M_get_Node_allocator() == __x._M_get_Node_allocator())
{
clear();
- if (__x._M_root() != 0)
+ if (__x._M_root() != nullptr)
_M_move_data(__x, std::true_type());
std::__alloc_on_move(_M_get_Node_allocator(),
__x._M_get_Node_allocator());
- return true;
+ return *this;
}
- return false;
+
+ // Try to move each node reusing existing nodes and copying __x nodes
+ // structure.
+ __reuse_or_alloc_node_t __roan(_M_impl._M_header, *this);
+ _M_impl._M_reset();
+ if (__x._M_root() != nullptr)
+ {
+ _M_root() = _M_copy(__x._M_begin(), _M_end(),
+ [&__roan](value_type& __val)
+ { return __roan(std::move_if_noexcept(__val)); });
+ _M_leftmost() = _S_minimum(_M_root());
+ _M_rightmost() = _S_maximum(_M_root());
+ _M_impl._M_node_count = __x._M_impl._M_node_count;
+ __x.clear();
+ }
+ return *this;
}
+
+ template<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ template<typename _Iterator>
+ void
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _M_assign_unique(_Iterator __first, _Iterator __last)
+ {
+ __reuse_or_alloc_node_t __roan(this->_M_impl._M_header, *this);
+ _M_impl._M_reset();
+ for (; __first != __last; ++__first)
+ _M_insert_unique_(end(), *__first, __roan);
+ }
+
+ template<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ template<typename _Iterator>
+ void
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _M_assign_equal(_Iterator __first, _Iterator __last)
+ {
+ __reuse_or_alloc_node_t __roan(this->_M_impl._M_header, *this);
+ _M_impl._M_reset();
+ for (; __first != __last; ++__first)
+ _M_insert_equal_(end(), *__first, __roan);
+ }
#endif
template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -1098,7 +1318,6 @@
if (this != &__x)
{
// Note that _Key may be a constant type.
- clear();
#if __cplusplus >= 201103L
if (_Alloc_traits::_S_propagate_on_copy_assign())
{
@@ -1107,19 +1326,26 @@
if (!_Alloc_traits::_S_always_equal()
&& __this_alloc != __that_alloc)
{
+ // Replacement allocator cannot free existing storage, we need
+ // to erase nodes first.
+ clear();
std::__alloc_on_copy(__this_alloc, __that_alloc);
}
}
#endif
+
+ __reuse_or_alloc_node_t __roan(this->_M_impl._M_header, *this);
+ _M_impl._M_reset();
_M_impl._M_key_compare = __x._M_impl._M_key_compare;
if (__x._M_root() != 0)
{
- _M_root() = _M_copy(__x._M_begin(), _M_end());
+ _M_root() = _M_copy(__x._M_begin(), _M_end(), __roan);
_M_leftmost() = _S_minimum(_M_root());
_M_rightmost() = _S_maximum(_M_root());
_M_impl._M_node_count = __x._M_impl._M_node_count;
}
}
+
return *this;
}
@@ -1126,27 +1352,31 @@
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
#if __cplusplus >= 201103L
- template<typename _Arg>
+ template<typename _Arg, typename _NodeGen>
+#else
+ template<typename _NodeGen>
#endif
- typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
- _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _M_insert_(_Base_ptr __x, _Base_ptr __p,
#if __cplusplus >= 201103L
- _M_insert_(_Base_ptr __x, _Base_ptr __p, _Arg&& __v)
+ _Arg&& __v,
#else
- _M_insert_(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
+ const _Val& __v,
#endif
- {
- bool __insert_left = (__x != 0 || __p == _M_end()
- || _M_impl._M_key_compare(_KeyOfValue()(__v),
- _S_key(__p)));
+ const _NodeGen& __node_gen)
+ {
+ bool __insert_left = (__x != 0 || __p == _M_end()
+ || _M_impl._M_key_compare(_KeyOfValue()(__v),
+ _S_key(__p)));
- _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
+ _Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v));
- _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
- this->_M_impl._M_header);
- ++_M_impl._M_node_count;
- return iterator(__z);
- }
+ _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
+ this->_M_impl._M_header);
+ ++_M_impl._M_node_count;
+ return iterator(__z);
+ }
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
@@ -1198,40 +1428,41 @@
}
template<typename _Key, typename _Val, typename _KoV,
- typename _Compare, typename _Alloc>
- typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
- _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
- _M_copy(_Const_Link_type __x, _Link_type __p)
- {
- // Structural copy. __x and __p must be non-null.
- _Link_type __top = _M_clone_node(__x);
- __top->_M_parent = __p;
+ typename _Compare, typename _Alloc>
+ template<typename _NodeGen>
+ typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
+ _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
+ _M_copy(_Link_type __x, _Link_type __p, const _NodeGen& __node_gen)
+ {
+ // Structural copy. __x and __p must be non-null.
+ _Link_type __top = _M_clone_node(__x, __node_gen);
+ __top->_M_parent = __p;
- __try
- {
- if (__x->_M_right)
- __top->_M_right = _M_copy(_S_right(__x), __top);
- __p = __top;
- __x = _S_left(__x);
+ __try
+ {
+ if (__x->_M_right)
+ __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen);
+ __p = __top;
+ __x = _S_left(__x);
- while (__x != 0)
- {
- _Link_type __y = _M_clone_node(__x);
- __p->_M_left = __y;
- __y->_M_parent = __p;
- if (__x->_M_right)
- __y->_M_right = _M_copy(_S_right(__x), __y);
- __p = __y;
- __x = _S_left(__x);
- }
- }
- __catch(...)
- {
- _M_erase(__top);
- __throw_exception_again;
- }
- return __top;
- }
+ while (__x != 0)
+ {
+ _Link_type __y = _M_clone_node(__x, __node_gen);
+ __p->_M_left = __y;
+ __y->_M_parent = __p;
+ if (__x->_M_right)
+ __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen);
+ __p = __y;
+ __x = _S_left(__x);
+ }
+ }
+ __catch(...)
+ {
+ _M_erase(__top);
+ __throw_exception_again;
+ }
+ return __top;
+ }
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
@@ -1244,7 +1475,7 @@
{
_M_erase(_S_right(__x));
_Link_type __y = _S_left(__x);
- _M_destroy_node(__x);
+ _M_drop_node(__x);
__x = __y;
}
}
@@ -1353,8 +1584,8 @@
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
equal_range(const _Key& __k) const
{
- _Const_Link_type __x = _M_begin();
- _Const_Link_type __y = _M_end();
+ _Const_Link_type __x = _M_cbegin();
+ _Const_Link_type __y = _M_cend();
while (__x != 0)
{
if (_M_impl._M_key_compare(_S_key(__x), __k))
@@ -1392,10 +1623,9 @@
_M_leftmost() = __t._M_leftmost();
_M_rightmost() = __t._M_rightmost();
_M_root()->_M_parent = _M_end();
+ _M_impl._M_node_count = __t._M_impl._M_node_count;
- __t._M_root() = 0;
- __t._M_leftmost() = __t._M_end();
- __t._M_rightmost() = __t._M_end();
+ __t._M_impl._M_reset();
}
}
else if (__t._M_root() == 0)
@@ -1404,10 +1634,9 @@
__t._M_leftmost() = _M_leftmost();
__t._M_rightmost() = _M_rightmost();
__t._M_root()->_M_parent = __t._M_end();
+ __t._M_impl._M_node_count = _M_impl._M_node_count;
- _M_root() = 0;
- _M_leftmost() = _M_end();
- _M_rightmost() = _M_end();
+ _M_impl._M_reset();
}
else
{
@@ -1417,9 +1646,9 @@
_M_root()->_M_parent = _M_end();
__t._M_root()->_M_parent = __t._M_end();
+ std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
}
// No need to swap header's color as it does not change.
- std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
_Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
@@ -1498,9 +1727,12 @@
= _M_get_insert_unique_pos(_KeyOfValue()(__v));
if (__res.second)
- return _Res(_M_insert_(__res.first, __res.second,
- _GLIBCXX_FORWARD(_Arg, __v)),
- true);
+ {
+ __alloc_node_t __an(*this);
+ return _Res(_M_insert_(__res.first, __res.second,
+ _GLIBCXX_FORWARD(_Arg, __v), __an),
+ true);
+ }
return _Res(iterator(static_cast<_Link_type>(__res.first)), false);
}
@@ -1520,7 +1752,9 @@
{
pair<_Base_ptr, _Base_ptr> __res
= _M_get_insert_equal_pos(_KeyOfValue()(__v));
- return _M_insert_(__res.first, __res.second, _GLIBCXX_FORWARD(_Arg, __v));
+ __alloc_node_t __an(*this);
+ return _M_insert_(__res.first, __res.second,
+ _GLIBCXX_FORWARD(_Arg, __v), __an);
}
template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -1585,15 +1819,19 @@
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
#if __cplusplus >= 201103L
- template<typename _Arg>
+ template<typename _Arg, typename _NodeGen>
+#else
+ template<typename _NodeGen>
#endif
- typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
- _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _M_insert_unique_(const_iterator __position,
#if __cplusplus >= 201103L
- _M_insert_unique_(const_iterator __position, _Arg&& __v)
+ _Arg&& __v,
#else
- _M_insert_unique_(const_iterator __position, const _Val& __v)
+ const _Val& __v,
#endif
+ const _NodeGen& __node_gen)
{
pair<_Base_ptr, _Base_ptr> __res
= _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v));
@@ -1600,7 +1838,8 @@
if (__res.second)
return _M_insert_(__res.first, __res.second,
- _GLIBCXX_FORWARD(_Arg, __v));
+ _GLIBCXX_FORWARD(_Arg, __v),
+ __node_gen);
return iterator(static_cast<_Link_type>(__res.first));
}
@@ -1662,25 +1901,30 @@
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
#if __cplusplus >= 201103L
- template<typename _Arg>
+ template<typename _Arg, typename _NodeGen>
+#else
+ template<typename _NodeGen>
#endif
- typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
- _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _M_insert_equal_(const_iterator __position,
#if __cplusplus >= 201103L
- _M_insert_equal_(const_iterator __position, _Arg&& __v)
+ _Arg&& __v,
#else
- _M_insert_equal_(const_iterator __position, const _Val& __v)
+ const _Val& __v,
#endif
- {
- pair<_Base_ptr, _Base_ptr> __res
- = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
+ const _NodeGen& __node_gen)
+ {
+ pair<_Base_ptr, _Base_ptr> __res
+ = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
- if (__res.second)
- return _M_insert_(__res.first, __res.second,
- _GLIBCXX_FORWARD(_Arg, __v));
+ if (__res.second)
+ return _M_insert_(__res.first, __res.second,
+ _GLIBCXX_FORWARD(_Arg, __v),
+ __node_gen);
- return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
- }
+ return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
+ }
#if __cplusplus >= 201103L
template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -1749,12 +1993,12 @@
if (__res.second)
return _Res(_M_insert_node(__res.first, __res.second, __z), true);
- _M_destroy_node(__z);
+ _M_drop_node(__z);
return _Res(iterator(static_cast<_Link_type>(__res.first)), false);
}
__catch(...)
{
- _M_destroy_node(__z);
+ _M_drop_node(__z);
__throw_exception_again;
}
}
@@ -1775,7 +2019,7 @@
}
__catch(...)
{
- _M_destroy_node(__z);
+ _M_drop_node(__z);
__throw_exception_again;
}
}
@@ -1796,12 +2040,12 @@
if (__res.second)
return _M_insert_node(__res.first, __res.second, __z);
- _M_destroy_node(__z);
+ _M_drop_node(__z);
return iterator(static_cast<_Link_type>(__res.first));
}
__catch(...)
{
- _M_destroy_node(__z);
+ _M_drop_node(__z);
__throw_exception_again;
}
}
@@ -1826,7 +2070,7 @@
}
__catch(...)
{
- _M_destroy_node(__z);
+ _M_drop_node(__z);
__throw_exception_again;
}
}
@@ -1839,8 +2083,9 @@
_Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
_M_insert_unique(_II __first, _II __last)
{
+ __alloc_node_t __an(*this);
for (; __first != __last; ++__first)
- _M_insert_unique_(end(), *__first);
+ _M_insert_unique_(end(), *__first, __an);
}
template<typename _Key, typename _Val, typename _KoV,
@@ -1850,8 +2095,9 @@
_Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
_M_insert_equal(_II __first, _II __last)
{
+ __alloc_node_t __an(*this);
for (; __first != __last; ++__first)
- _M_insert_equal_(end(), *__first);
+ _M_insert_equal_(end(), *__first, __an);
}
template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -1864,7 +2110,7 @@
static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
(const_cast<_Base_ptr>(__position._M_node),
this->_M_impl._M_header));
- _M_destroy_node(__y);
+ _M_drop_node(__y);
--_M_impl._M_node_count;
}
@@ -1923,7 +2169,7 @@
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
find(const _Key& __k) const
{
- const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
+ const_iterator __j = _M_lower_bound(_M_cbegin(), _M_cend(), __k);
return (__j == end()
|| _M_impl._M_key_compare(__k,
_S_key(__j._M_node))) ? end() : __j;
Index: testsuite/23_containers/map/allocator/copy_assign.cc
===================================================================
--- testsuite/23_containers/map/allocator/copy_assign.cc (revision 211388)
+++ testsuite/23_containers/map/allocator/copy_assign.cc (working copy)
@@ -59,9 +59,33 @@
VERIFY(1 == v2.get_allocator().get_personality());
}
+void test03()
+{
+ bool test __attribute__((unused)) = true;
+
+ using namespace __gnu_test;
+
+ typedef tracker_allocator<std::pair<const int, int>> alloc_type;
+ typedef std::map<int, int, std::less<int>, alloc_type> test_type;
+
+ tracker_allocator_counter::reset();
+
+ test_type v1 = { { 0, 0 }, { 1, 1 } };
+ test_type v2 = { { 2, 2 }, { 3, 3 } };
+
+ auto allocs = tracker_allocator_counter::get_allocation_count();
+ auto constructs = tracker_allocator_counter::get_construct_count();
+
+ v1 = v2;
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == allocs );
+ VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 );
+}
+
int main()
{
test01();
test02();
+ test03();
return 0;
}
Index: testsuite/23_containers/map/allocator/init-list.cc
===================================================================
--- testsuite/23_containers/map/allocator/init-list.cc (revision 0)
+++ testsuite/23_containers/map/allocator/init-list.cc (working copy)
@@ -0,0 +1,55 @@
+// Copyright (C) 2014 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+//
+
+// { dg-options "-std=gnu++11" }
+
+#include <map>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+
+ using namespace __gnu_test;
+
+ typedef tracker_allocator<std::pair<const int, int>> alloc_type;
+ typedef std::map<int, int, std::less<int>, alloc_type> test_type;
+
+ tracker_allocator_counter::reset();
+
+ test_type v1;
+ v1 = { { 0, 0 }, { 1, 1 } };
+
+ auto allocs = tracker_allocator_counter::get_allocation_count();
+ auto constructs = tracker_allocator_counter::get_construct_count();
+
+ VERIFY( allocs != 0 );
+ VERIFY( constructs != 0 );
+
+ // Check no allocation on list initialization.
+ v1 = { { 4, 4 }, { 5, 5 } };
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == allocs );
+ VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 );
+}
+
+int main()
+{
+ test01();
+}
Property changes on: testsuite/23_containers/map/allocator/init-list.cc
___________________________________________________________________
Added: svn:executable
## -0,0 +1 ##
+*
\ No newline at end of property
Index: testsuite/23_containers/map/allocator/move_assign.cc
===================================================================
--- testsuite/23_containers/map/allocator/move_assign.cc (revision 211388)
+++ testsuite/23_containers/map/allocator/move_assign.cc (working copy)
@@ -43,8 +43,8 @@
v2 = { test_type::value_type{} };
v2 = std::move(v1);
- VERIFY(1 == v1.get_allocator().get_personality());
- VERIFY(2 == v2.get_allocator().get_personality());
+ VERIFY( 1 == v1.get_allocator().get_personality() );
+ VERIFY( 2 == v2.get_allocator().get_personality() );
}
void test02()
@@ -60,14 +60,47 @@
v2 = { test_type::value_type{} };
v2 = std::move(v1);
- VERIFY(0 == v1.get_allocator().get_personality());
- VERIFY(1 == v2.get_allocator().get_personality());
+ VERIFY( 0 == v1.get_allocator().get_personality() );
+ VERIFY( 1 == v2.get_allocator().get_personality() );
VERIFY( it == v2.begin() );
}
+void test03()
+{
+ bool test __attribute__((unused)) = true;
+
+ using namespace __gnu_test;
+
+ typedef propagating_allocator<std::pair<const int, int>, false,
+ tracker_allocator<std::pair<const int, int>>>
+ alloc_type;
+ typedef std::map<int, int, std::less<int>, alloc_type> test_type;
+
+ tracker_allocator_counter::reset();
+
+ test_type v1(alloc_type(1));
+ v1 = { { 0, 0 }, { 1, 1 } };
+
+ test_type v2(alloc_type(2));
+ v2 = { { 2, 2 }, { 3, 3 } };
+
+ auto allocs = tracker_allocator_counter::get_allocation_count();
+ auto constructs = tracker_allocator_counter::get_construct_count();
+
+ // Check no allocation on move assignment with non propagating allocators.
+ v1 = std::move(v2);
+
+ VERIFY( 1 == v1.get_allocator().get_personality() );
+ VERIFY( 2 == v2.get_allocator().get_personality() );
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == allocs );
+ VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 );
+}
+
int main()
{
test01();
test02();
+ test03();
return 0;
}
Index: testsuite/util/testsuite_allocator.h
===================================================================
--- testsuite/util/testsuite_allocator.h (revision 211388)
+++ testsuite/util/testsuite_allocator.h (working copy)
@@ -244,26 +244,30 @@
}
};
- template<typename Tp>
+ template<typename Tp, typename _Alloc = std::allocator<Tp> >
class uneq_allocator
- : private uneq_allocator_base
+ : private uneq_allocator_base,
+ public _Alloc
{
public:
- typedef std::size_t size_type;
- typedef std::ptrdiff_t difference_type;
- typedef Tp* pointer;
- typedef const Tp* const_pointer;
- typedef Tp& reference;
- typedef const Tp& const_reference;
- typedef Tp value_type;
+ typedef typename _Alloc::size_type size_type;
+ typedef typename _Alloc::difference_type difference_type;
+ typedef typename _Alloc::pointer pointer;
+ typedef typename _Alloc::const_pointer const_pointer;
+ typedef typename _Alloc::reference reference;
+ typedef typename _Alloc::const_reference const_reference;
+ typedef typename _Alloc::value_type value_type;
#if __cplusplus >= 201103L
- typedef std::true_type propagate_on_container_swap;
+ typedef std::true_type propagate_on_container_swap;
#endif
template<typename Tp1>
- struct rebind
- { typedef uneq_allocator<Tp1> other; };
+ struct rebind
+ {
+ typedef uneq_allocator<Tp1,
+ typename _Alloc::template rebind<Tp1>::other> other;
+ };
uneq_allocator() _GLIBCXX_USE_NOEXCEPT
: personality(0) { }
@@ -272,7 +276,9 @@
: personality(person) { }
template<typename Tp1>
- uneq_allocator(const uneq_allocator<Tp1>& b) _GLIBCXX_USE_NOEXCEPT
+ uneq_allocator(const uneq_allocator<Tp1,
+ typename _Alloc::template rebind<Tp1>::other>& b)
+ _GLIBCXX_USE_NOEXCEPT
: personality(b.get_personality()) { }
~uneq_allocator() _GLIBCXX_USE_NOEXCEPT
@@ -281,20 +287,9 @@
int get_personality() const { return personality; }
pointer
- address(reference x) const _GLIBCXX_NOEXCEPT
- { return std::__addressof(x); }
-
- const_pointer
- address(const_reference x) const _GLIBCXX_NOEXCEPT
- { return std::__addressof(x); }
-
- pointer
- allocate(size_type n, const void* = 0)
+ allocate(size_type n, const void* hint = 0)
{
- if (__builtin_expect(n > this->max_size(), false))
- std::__throw_bad_alloc();
-
- pointer p = static_cast<Tp*>(::operator new(n * sizeof(Tp)));
+ pointer p = _Alloc::allocate(n, hint);
try
{
get_map().insert(map_type::value_type(reinterpret_cast<void*>(p),
@@ -302,7 +297,7 @@
}
catch(...)
{
- ::operator delete(p);
+ _Alloc::deallocate(p, n);
__throw_exception_again;
}
return p;
@@ -309,7 +304,7 @@
}
void
- deallocate(pointer p, size_type)
+ deallocate(pointer p, size_type n)
{
bool test __attribute__((unused)) = true;
@@ -323,34 +318,14 @@
VERIFY( it->second == personality );
get_map().erase(it);
- ::operator delete(p);
+ _Alloc::deallocate(p, n);
}
- size_type
- max_size() const _GLIBCXX_USE_NOEXCEPT
- { return size_type(-1) / sizeof(Tp); }
-
#if __cplusplus >= 201103L
- template<typename U, typename... Args>
- void
- construct(U* p, Args&&... args)
- { ::new((void *)p) U(std::forward<Args>(args)...); }
-
- template<typename U>
- void
- destroy(U* p) { p->~U(); }
-
// Not copy assignable...
uneq_allocator&
operator=(const uneq_allocator&) = delete;
#else
- void
- construct(pointer p, const Tp& val)
- { ::new((void *)p) Tp(val); }
-
- void
- destroy(pointer p) { p->~Tp(); }
-
private:
// Not assignable...
uneq_allocator&
@@ -364,15 +339,14 @@
swap(uneq_allocator& a, uneq_allocator& b)
{ std::swap(a.personality, b.personality); }
- template<typename Tp1>
- friend inline bool
- operator==(const uneq_allocator& a, const uneq_allocator<Tp1>& b)
- { return a.personality == b.personality; }
+ friend inline bool
+ operator==(const uneq_allocator& a,
+ const uneq_allocator& b)
+ { return a.personality == b.personality; }
- template<typename Tp1>
- friend inline bool
- operator!=(const uneq_allocator& a, const uneq_allocator<Tp1>& b)
- { return !(a == b); }
+ friend inline bool
+ operator!=(const uneq_allocator& a, const uneq_allocator& b)
+ { return !(a == b); }
int personality;
};
@@ -379,10 +353,10 @@
#if __cplusplus >= 201103L
// An uneq_allocator which can be used to test allocator propagation.
- template<typename Tp, bool Propagate>
- class propagating_allocator : public uneq_allocator<Tp>
+ template<typename Tp, bool Propagate, typename _Alloc = std::allocator<Tp>>
+ class propagating_allocator : public uneq_allocator<Tp, _Alloc>
{
- typedef uneq_allocator<Tp> base_alloc;
+ typedef uneq_allocator<Tp, _Alloc> base_alloc;
base_alloc& base() { return *this; }
const base_alloc& base() const { return *this; }
void swap_base(base_alloc& b) { swap(b, this->base()); }
@@ -393,7 +367,11 @@
// default allocator_traits::rebind_alloc would select
// uneq_allocator::rebind so we must define rebind here
template<typename Up>
- struct rebind { typedef propagating_allocator<Up, Propagate> other; };
+ struct rebind
+ {
+ typedef propagating_allocator<Up, Propagate,
+ typename _Alloc::template rebind<Up>::other> other;
+ };
propagating_allocator(int i) noexcept
: base_alloc(i)
@@ -400,8 +378,9 @@
{ }
template<typename Up>
- propagating_allocator(const propagating_allocator<Up, Propagate>& a)
- noexcept
+ propagating_allocator(const propagating_allocator<Up, Propagate,
+ typename _Alloc::template rebind<Up>::other>& a)
+ noexcept
: base_alloc(a)
{ }
Index: testsuite/23_containers/set/allocator/copy_assign.cc
===================================================================
--- testsuite/23_containers/set/allocator/copy_assign.cc (revision 211388)
+++ testsuite/23_containers/set/allocator/copy_assign.cc (working copy)
@@ -57,9 +57,33 @@
VERIFY(1 == v2.get_allocator().get_personality());
}
+void test03()
+{
+ bool test __attribute__((unused)) = true;
+
+ using namespace __gnu_test;
+
+ typedef tracker_allocator<int> alloc_type;
+ typedef std::set<int, std::less<int>, alloc_type> test_type;
+
+ tracker_allocator_counter::reset();
+
+ test_type v1 = { 0, 1 };
+ test_type v2 = { 2, 3 };
+
+ auto allocs = tracker_allocator_counter::get_allocation_count();
+ auto constructs = tracker_allocator_counter::get_construct_count();
+
+ v1 = v2;
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == allocs );
+ VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 );
+}
+
int main()
{
test01();
test02();
+ test03();
return 0;
}
Index: testsuite/23_containers/set/allocator/init-list.cc
===================================================================
--- testsuite/23_containers/set/allocator/init-list.cc (revision 0)
+++ testsuite/23_containers/set/allocator/init-list.cc (working copy)
@@ -0,0 +1,55 @@
+// Copyright (C) 2014 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+//
+
+// { dg-options "-std=gnu++11" }
+
+#include <set>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+
+ using namespace __gnu_test;
+
+ typedef tracker_allocator<int> alloc_type;
+ typedef std::set<int, std::less<int>, alloc_type> test_type;
+
+ tracker_allocator_counter::reset();
+
+ test_type v1;
+ v1 = { 0, 1 };
+
+ auto allocs = tracker_allocator_counter::get_allocation_count();
+ auto constructs = tracker_allocator_counter::get_construct_count();
+
+ VERIFY( allocs != 0 );
+ VERIFY( constructs != 0 );
+
+ // Check no allocation on list initialization.
+ v1 = { 4, 5 };
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == allocs );
+ VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 );
+}
+
+int main()
+{
+ test01();
+}
Property changes on: testsuite/23_containers/set/allocator/init-list.cc
___________________________________________________________________
Added: svn:executable
## -0,0 +1 ##
+*
\ No newline at end of property
Index: testsuite/23_containers/set/allocator/move_assign.cc
===================================================================
--- testsuite/23_containers/set/allocator/move_assign.cc (revision 211388)
+++ testsuite/23_containers/set/allocator/move_assign.cc (working copy)
@@ -59,9 +59,40 @@
VERIFY( it == v2.begin() );
}
+void test03()
+{
+ bool test __attribute__((unused)) = true;
+
+ using namespace __gnu_test;
+
+ typedef propagating_allocator<int, false, tracker_allocator<int>> alloc_type;
+ typedef std::set<int, std::less<int>, alloc_type> test_type;
+
+ tracker_allocator_counter::reset();
+
+ test_type v1(alloc_type(1));
+ v1 = { 0, 1 };
+
+ test_type v2(alloc_type(2));
+ v2 = { 2, 3 };
+
+ auto allocs = tracker_allocator_counter::get_allocation_count();
+ auto constructs = tracker_allocator_counter::get_construct_count();
+
+ // Check no allocation on move assignment with non propagating allocators.
+ v1 = std::move(v2);
+
+ VERIFY( 1 == v1.get_allocator().get_personality() );
+ VERIFY( 2 == v2.get_allocator().get_personality() );
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == allocs );
+ VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 );
+}
+
int main()
{
test01();
test02();
+ test03();
return 0;
}
Index: testsuite/23_containers/multimap/allocator/copy_assign.cc
===================================================================
--- testsuite/23_containers/multimap/allocator/copy_assign.cc (revision 211388)
+++ testsuite/23_containers/multimap/allocator/copy_assign.cc (working copy)
@@ -59,9 +59,33 @@
VERIFY(1 == v2.get_allocator().get_personality());
}
+void test03()
+{
+ bool test __attribute__((unused)) = true;
+
+ using namespace __gnu_test;
+
+ typedef tracker_allocator<std::pair<const int, int>> alloc_type;
+ typedef std::multimap<int, int, std::less<int>, alloc_type> test_type;
+
+ tracker_allocator_counter::reset();
+
+ test_type v1 = { { 1, 1 }, { 1, 1 } };
+ test_type v2 = { { 2, 2 }, { 2, 2 } };
+
+ auto allocs = tracker_allocator_counter::get_allocation_count();
+ auto constructs = tracker_allocator_counter::get_construct_count();
+
+ v1 = v2;
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == allocs );
+ VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 );
+}
+
int main()
{
test01();
test02();
+ test03();
return 0;
}
Index: testsuite/23_containers/multimap/allocator/init-list.cc
===================================================================
--- testsuite/23_containers/multimap/allocator/init-list.cc (revision 0)
+++ testsuite/23_containers/multimap/allocator/init-list.cc (working copy)
@@ -0,0 +1,55 @@
+// Copyright (C) 2014 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+//
+
+// { dg-options "-std=gnu++11" }
+
+#include <map>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+
+ using namespace __gnu_test;
+
+ typedef tracker_allocator<std::pair<const int, int>> alloc_type;
+ typedef std::multimap<int, int, std::less<int>, alloc_type> test_type;
+
+ tracker_allocator_counter::reset();
+
+ test_type v1;
+ v1 = { { 0, 0 }, { 0, 0 } };
+
+ auto allocs = tracker_allocator_counter::get_allocation_count();
+ auto constructs = tracker_allocator_counter::get_construct_count();
+
+ VERIFY( allocs != 0 );
+ VERIFY( constructs != 0 );
+
+ // Check no allocation on list initialization.
+ v1 = { { 1, 1 }, { 1, 1 } };
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == allocs );
+ VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 );
+}
+
+int main()
+{
+ test01();
+}
Property changes on: testsuite/23_containers/multimap/allocator/init-list.cc
___________________________________________________________________
Added: svn:executable
## -0,0 +1 ##
+*
\ No newline at end of property
Index: testsuite/23_containers/multimap/allocator/move_assign.cc
===================================================================
--- testsuite/23_containers/multimap/allocator/move_assign.cc (revision 211388)
+++ testsuite/23_containers/multimap/allocator/move_assign.cc (working copy)
@@ -61,9 +61,42 @@
VERIFY( it == v2.begin() );
}
+void test03()
+{
+ bool test __attribute__((unused)) = true;
+
+ using namespace __gnu_test;
+
+ typedef propagating_allocator<std::pair<const int, int>, false,
+ tracker_allocator<std::pair<const int, int>>>
+ alloc_type;
+ typedef std::multimap<int, int, std::less<int>, alloc_type> test_type;
+
+ tracker_allocator_counter::reset();
+
+ test_type v1(alloc_type(1));
+ v1 = { { 1, 1 }, { 1, 1 } };
+
+ test_type v2(alloc_type(2));
+ v2 = { { 2, 2 }, { 2, 2 } };
+
+ auto allocs = tracker_allocator_counter::get_allocation_count();
+ auto constructs = tracker_allocator_counter::get_construct_count();
+
+ // Check no allocation on move assignment with non propagating allocators.
+ v1 = std::move(v2);
+
+ VERIFY( 1 == v1.get_allocator().get_personality() );
+ VERIFY( 2 == v2.get_allocator().get_personality() );
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == allocs );
+ VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 );
+}
+
int main()
{
test01();
test02();
+ test03();
return 0;
}
Index: testsuite/23_containers/multiset/allocator/copy_assign.cc
===================================================================
--- testsuite/23_containers/multiset/allocator/copy_assign.cc (revision 211388)
+++ testsuite/23_containers/multiset/allocator/copy_assign.cc (working copy)
@@ -57,9 +57,33 @@
VERIFY(1 == v2.get_allocator().get_personality());
}
+void test03()
+{
+ bool test __attribute__((unused)) = true;
+
+ using namespace __gnu_test;
+
+ typedef tracker_allocator<int> alloc_type;
+ typedef std::multiset<int, std::less<int>, alloc_type> test_type;
+
+ tracker_allocator_counter::reset();
+
+ test_type v1 = { 0, 0 };
+ test_type v2 = { 1, 1 };
+
+ auto allocs = tracker_allocator_counter::get_allocation_count();
+ auto constructs = tracker_allocator_counter::get_construct_count();
+
+ v1 = v2;
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == allocs );
+ VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 );
+}
+
int main()
{
test01();
test02();
+ test03();
return 0;
}
Index: testsuite/23_containers/multiset/allocator/init-list.cc
===================================================================
--- testsuite/23_containers/multiset/allocator/init-list.cc (revision 0)
+++ testsuite/23_containers/multiset/allocator/init-list.cc (working copy)
@@ -0,0 +1,55 @@
+// Copyright (C) 2014 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+//
+
+// { dg-options "-std=gnu++11" }
+
+#include <set>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+
+ using namespace __gnu_test;
+
+ typedef tracker_allocator<int> alloc_type;
+ typedef std::multiset<int, std::less<int>, alloc_type> test_type;
+
+ tracker_allocator_counter::reset();
+
+ test_type v1;
+ v1 = { 0, 0 };
+
+ auto allocs = tracker_allocator_counter::get_allocation_count();
+ auto constructs = tracker_allocator_counter::get_construct_count();
+
+ VERIFY( allocs != 0 );
+ VERIFY( constructs != 0 );
+
+ // Check no allocation on list initialization.
+ v1 = { 1, 1 };
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == allocs );
+ VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 );
+}
+
+int main()
+{
+ test01();
+}
Property changes on: testsuite/23_containers/multiset/allocator/init-list.cc
___________________________________________________________________
Added: svn:executable
## -0,0 +1 ##
+*
\ No newline at end of property
Index: testsuite/23_containers/multiset/allocator/move_assign.cc
===================================================================
--- testsuite/23_containers/multiset/allocator/move_assign.cc (revision 211388)
+++ testsuite/23_containers/multiset/allocator/move_assign.cc (working copy)
@@ -59,9 +59,40 @@
VERIFY( it == v2.begin() );
}
+void test03()
+{
+ bool test __attribute__((unused)) = true;
+
+ using namespace __gnu_test;
+
+ typedef propagating_allocator<int, false, tracker_allocator<int>> alloc_type;
+ typedef std::multiset<int, std::less<int>, alloc_type> test_type;
+
+ tracker_allocator_counter::reset();
+
+ test_type v1(alloc_type(1));
+ v1 = { 0, 0 };
+
+ test_type v2(alloc_type(2));
+ v2 = { 2, 2 };
+
+ auto allocs = tracker_allocator_counter::get_allocation_count();
+ auto constructs = tracker_allocator_counter::get_construct_count();
+
+ // Check no allocation on move assignment with non propagating allocators.
+ v1 = std::move(v2);
+
+ VERIFY( 1 == v1.get_allocator().get_personality() );
+ VERIFY( 2 == v2.get_allocator().get_personality() );
+
+ VERIFY( tracker_allocator_counter::get_allocation_count() == allocs );
+ VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 );
+}
+
int main()
{
test01();
test02();
+ test03();
return 0;
}