From c6195f588b1b8980b07d53394edaaa2cd6807588 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Fran=C3=A7ois=20Dumont?= Date: Wed, 24 Sep 2014 19:55:35 +0000 Subject: [PATCH] re PR libstdc++/29988 (More stl_tree.h enhancements: improving operator=) MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit 2014-09-24 François Dumont PR libstdc++/29988 * include/bits/stl_tree.h (_Rb_tree_reuse_or_alloc_node<>): New. (_Rb_tree_alloc_node<>): New. (_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. From-SVN: r215568 --- libstdc++-v3/ChangeLog | 42 ++ libstdc++-v3/include/bits/stl_map.h | 26 +- libstdc++-v3/include/bits/stl_multimap.h | 26 +- libstdc++-v3/include/bits/stl_multiset.h | 26 +- libstdc++-v3/include/bits/stl_set.h | 26 +- libstdc++-v3/include/bits/stl_tree.h | 538 +++++++++++++----- .../map/allocator/copy_assign.cc | 24 + .../23_containers/map/allocator/init-list.cc | 55 ++ .../map/allocator/move_assign.cc | 41 +- .../multimap/allocator/copy_assign.cc | 24 + .../multimap/allocator/init-list.cc | 55 ++ .../multimap/allocator/move_assign.cc | 33 ++ .../multiset/allocator/copy_assign.cc | 24 + .../multiset/allocator/init-list.cc | 55 ++ .../multiset/allocator/move_assign.cc | 31 + .../set/allocator/copy_assign.cc | 24 + .../23_containers/set/allocator/init-list.cc | 55 ++ .../set/allocator/move_assign.cc | 31 + 18 files changed, 897 insertions(+), 239 deletions(-) create mode 100644 libstdc++-v3/testsuite/23_containers/map/allocator/init-list.cc create mode 100644 libstdc++-v3/testsuite/23_containers/multimap/allocator/init-list.cc create mode 100644 libstdc++-v3/testsuite/23_containers/multiset/allocator/init-list.cc create mode 100644 libstdc++-v3/testsuite/23_containers/set/allocator/init-list.cc diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 2f8abd7dbf7..630b116f33f 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,45 @@ +2014-09-24 François Dumont + + PR libstdc++/29988 + * include/bits/stl_tree.h (_Rb_tree_reuse_or_alloc_node<>): New. + (_Rb_tree_alloc_node<>): New. + (_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. + 2014-09-24 Jonathan Wakely PR libstdc++/63353 diff --git a/libstdc++-v3/include/bits/stl_map.h b/libstdc++-v3/include/bits/stl_map.h index 405d4b8f33a..899f063d4a4 100644 --- a/libstdc++-v3/include/bits/stl_map.h +++ b/libstdc++-v3/include/bits/stl_map.h @@ -297,28 +297,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } #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 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER map& operator=(initializer_list __l) { - this->clear(); - this->insert(__l.begin(), __l.end()); + _M_t._M_assign_unique(__l.begin(), __l.end()); return *this; } #endif diff --git a/libstdc++-v3/include/bits/stl_multimap.h b/libstdc++-v3/include/bits/stl_multimap.h index a73164e8910..ab0c59bf6c3 100644 --- a/libstdc++-v3/include/bits/stl_multimap.h +++ b/libstdc++-v3/include/bits/stl_multimap.h @@ -292,28 +292,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } #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 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER multimap& operator=(initializer_list __l) { - this->clear(); - this->insert(__l.begin(), __l.end()); + _M_t._M_assign_equal(__l.begin(), __l.end()); return *this; } #endif diff --git a/libstdc++-v3/include/bits/stl_multiset.h b/libstdc++-v3/include/bits/stl_multiset.h index f379aef2737..8b0dba1b00c 100644 --- a/libstdc++-v3/include/bits/stl_multiset.h +++ b/libstdc++-v3/include/bits/stl_multiset.h @@ -263,28 +263,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } #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 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER multiset& operator=(initializer_list __l) { - this->clear(); - this->insert(__l.begin(), __l.end()); + _M_t._M_assign_equal(__l.begin(), __l.end()); return *this; } #endif diff --git a/libstdc++-v3/include/bits/stl_set.h b/libstdc++-v3/include/bits/stl_set.h index 48dc761dc39..53938eae33a 100644 --- a/libstdc++-v3/include/bits/stl_set.h +++ b/libstdc++-v3/include/bits/stl_set.h @@ -267,28 +267,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } #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 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER set& operator=(initializer_list __l) { - this->clear(); - this->insert(__l.begin(), __l.end()); + _M_t._M_assign_unique(__l.begin(), __l.end()); return *this; } #endif diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h index cc9bf9442ea..258579d31db 100644 --- a/libstdc++-v3/include/bits/stl_tree.h +++ b/libstdc++-v3/include/bits/stl_tree.h @@ -355,6 +355,106 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION protected: typedef _Rb_tree_node_base* _Base_ptr; typedef const _Rb_tree_node_base* _Const_Base_ptr; + typedef _Rb_tree_node<_Val>* _Link_type; + typedef const _Rb_tree_node<_Val>* _Const_Link_type; + + private: + // 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) + { + if (_M_root) + _M_root->_M_parent = 0; + else + _M_nodes = 0; + } + +#if __cplusplus >= 201103L + _Reuse_or_alloc_node(const _Reuse_or_alloc_node&) = delete; +#endif + + ~_Reuse_or_alloc_node() + { _M_t._M_erase(static_cast<_Link_type>(_M_root)); } + + template + _Link_type +#if __cplusplus < 201103L + operator()(const _Arg& __arg) +#else + operator()(_Arg&& __arg) +#endif + { + _Link_type __node = static_cast<_Link_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: + _Base_ptr + _M_extract() + { + if (!_M_nodes) + return _M_nodes; + + _Base_ptr __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; + } + + _Base_ptr _M_root; + _Base_ptr _M_nodes; + _Rb_tree& _M_t; + }; + + // Functor similar to the previous one but without any pool of node to + // recycle. + struct _Alloc_node + { + _Alloc_node(_Rb_tree& __t) + : _M_t(__t) { } + + template + _Link_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: + _Rb_tree& _M_t; + }; public: typedef _Key key_type; @@ -363,8 +463,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typedef const value_type* const_pointer; typedef value_type& reference; typedef const value_type& const_reference; - typedef _Rb_tree_node<_Val>* _Link_type; - typedef const _Rb_tree_node<_Val>* _Const_Link_type; typedef size_t size_type; typedef ptrdiff_t difference_type; typedef _Alloc allocator_type; @@ -391,44 +489,55 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { _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 - _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 + _Link_type + _M_create_node(_Args&&... __args) + { + _Link_type __tmp = _M_get_node(); + _M_construct_node(__tmp, std::forward<_Args>(__args)...); return __tmp; } @@ -437,23 +546,31 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { _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 + _Link_type + _M_clone_node(_Const_Link_type __x, _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 + // Unused _Is_pod_comparator is kept as it is part of mangled name. + template struct _Rb_tree_impl : public _Node_allocator { _Key_compare _M_key_compare; @@ -477,6 +594,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { _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() @@ -605,9 +731,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION const key_type& __k); #if __cplusplus >= 201103L - template + template iterator - _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v); + _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&); iterator _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z); @@ -626,9 +752,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION iterator _M_insert_equal_lower_node(_Link_type __z); #else - iterator - _M_insert_(_Base_ptr __x, _Base_ptr __y, - const value_type& __v); + template + iterator + _M_insert_(_Base_ptr __x, _Base_ptr __y, + const value_type& __v, _NodeGen&); // _GLIBCXX_RESOLVE_LIB_DEFECTS // 233. Insertion hints in associative containers. @@ -639,8 +766,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_insert_equal_lower(const value_type& __x); #endif + template + _Link_type + _M_copy(_Const_Link_type __x, _Link_type __p, _NodeGen&); + _Link_type - _M_copy(_Const_Link_type __x, _Link_type __p); + _M_copy(_Const_Link_type __x, _Link_type __p) + { + _Alloc_node __an(*this); + return _M_copy(__x, __p, __an); + } void _M_erase(_Link_type __x); @@ -690,7 +825,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _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()); @@ -794,13 +929,29 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION iterator _M_insert_equal(_Arg&& __x); - template + template iterator - _M_insert_unique_(const_iterator __position, _Arg&& __x); + _M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&); template - iterator - _M_insert_equal_(const_iterator __position, _Arg&& __x); + iterator + _M_insert_unique_(const_iterator __pos, _Arg&& __x) + { + _Alloc_node __an(*this); + return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an); + } + + template + iterator + _M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&); + + template + iterator + _M_insert_equal_(const_iterator __pos, _Arg&& __x) + { + _Alloc_node __an(*this); + return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an); + } template pair @@ -824,11 +975,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION iterator _M_insert_equal(const value_type& __x); + template + iterator + _M_insert_unique_(const_iterator __pos, const value_type& __x, + _NodeGen&); + iterator - _M_insert_unique_(const_iterator __position, const value_type& __x); + _M_insert_unique_(const_iterator __pos, const value_type& __x) + { + _Alloc_node __an(*this); + return _M_insert_unique_(__pos, __x, __an); + } + template + iterator + _M_insert_equal_(const_iterator __pos, const value_type& __x, + _NodeGen&); iterator - _M_insert_equal_(const_iterator __position, const value_type& __x); + _M_insert_equal_(const_iterator __pos, const value_type& __x) + { + _Alloc_node __an(*this); + return _M_insert_equal_(__pos, __x, __an); + } #endif template @@ -908,10 +1076,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION 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. @@ -951,8 +1116,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __rb_verify() const; #if __cplusplus >= 201103L - bool - _M_move_assign(_Rb_tree&); + _Rb_tree& + operator=(_Rb_tree&&) noexcept(_Alloc_traits::_S_nothrow_move()); + + template + void + _M_assign_unique(_Iterator, _Iterator); + + template + void + _M_assign_equal(_Iterator, _Iterator); private: // Move elements from container with equal allocator. @@ -1029,7 +1202,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION : _M_impl(__x._M_impl._M_key_compare, std::move(__a)) { using __eq = integral_constant; - if (__x._M_root() != 0) + if (__x._M_root() != nullptr) _M_move_data(__x, __eq()); } @@ -1062,7 +1235,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_move_data(__x, std::true_type()); else { - _M_root() = _M_copy(__x._M_begin(), _M_end()); + _Alloc_node __an(*this); + auto __lbd = + [&__an](const value_type& __cval) + { + auto& __val = const_cast(__cval); + return __an(std::move_if_noexcept(__val)); + }; + _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd); _M_leftmost() = _S_minimum(_M_root()); _M_rightmost() = _S_maximum(_M_root()); _M_impl._M_node_count = __x._M_impl._M_node_count; @@ -1071,9 +1251,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template - 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() @@ -1081,14 +1262,59 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION || _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; + } + + // Try to move each node reusing existing nodes and copying __x nodes + // structure. + _Reuse_or_alloc_node __roan(_M_impl._M_header, *this); + _M_impl._M_reset(); + if (__x._M_root() != nullptr) + { + auto __lbd = + [&__roan](const value_type& __cval) + { + auto& __val = const_cast(__cval); + return __roan(std::move_if_noexcept(__val)); + }; + _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd); + _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 false; + return *this; } + + template + template + void + _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); + _M_impl._M_reset(); + for (; __first != __last; ++__first) + _M_insert_unique_(end(), *__first, __roan); + } + + template + template + void + _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); + _M_impl._M_reset(); + for (; __first != __last; ++__first) + _M_insert_equal_(end(), *__first, __roan); + } #endif template= 201103L if (_Alloc_traits::_S_propagate_on_copy_assign()) { @@ -1109,46 +1334,57 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION 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 __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; } template #if __cplusplus >= 201103L - template + template +#else + template #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))); + _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 @@ -1200,40 +1436,41 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template - 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; - - __try - { - if (__x->_M_right) - __top->_M_right = _M_copy(_S_right(__x), __top); - __p = __top; - __x = _S_left(__x); + typename _Compare, typename _Alloc> + template + 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, _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; - 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; - } + __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, __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 @@ -1246,7 +1483,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { _M_erase(_S_right(__x)); _Link_type __y = _S_left(__x); - _M_destroy_node(__x); + _M_drop_node(__x); __x = __y; } } @@ -1394,10 +1631,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _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) @@ -1406,10 +1642,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __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 { @@ -1419,9 +1654,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _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(), @@ -1500,9 +1735,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION = _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 __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); } @@ -1522,7 +1760,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { 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 __an(*this); + return _M_insert_(__res.first, __res.second, + _GLIBCXX_FORWARD(_Arg, __v), __an); } template #if __cplusplus >= 201103L - template + template +#else + template #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 + _NodeGen& __node_gen) { pair<_Base_ptr, _Base_ptr> __res = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v)); 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)); } @@ -1664,25 +1909,30 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template #if __cplusplus >= 201103L - template + template +#else + template #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)); + _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(__res.first)), false); } __catch(...) { - _M_destroy_node(__z); + _M_drop_node(__z); __throw_exception_again; } } @@ -1777,7 +2027,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } __catch(...) { - _M_destroy_node(__z); + _M_drop_node(__z); __throw_exception_again; } } @@ -1798,12 +2048,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION 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; } } @@ -1828,7 +2078,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } __catch(...) { - _M_destroy_node(__z); + _M_drop_node(__z); __throw_exception_again; } } @@ -1841,8 +2091,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: _M_insert_unique(_II __first, _II __last) { + _Alloc_node __an(*this); for (; __first != __last; ++__first) - _M_insert_unique_(end(), *__first); + _M_insert_unique_(end(), *__first, __an); } template:: _M_insert_equal(_II __first, _II __last) { + _Alloc_node __an(*this); for (; __first != __last; ++__first) - _M_insert_equal_(end(), *__first); + _M_insert_equal_(end(), *__first, __an); } template(_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; } diff --git a/libstdc++-v3/testsuite/23_containers/map/allocator/copy_assign.cc b/libstdc++-v3/testsuite/23_containers/map/allocator/copy_assign.cc index 2dc69eaf8ea..ea914cb89d6 100644 --- a/libstdc++-v3/testsuite/23_containers/map/allocator/copy_assign.cc +++ b/libstdc++-v3/testsuite/23_containers/map/allocator/copy_assign.cc @@ -59,9 +59,33 @@ void test02() VERIFY(1 == v2.get_allocator().get_personality()); } +void test03() +{ + bool test __attribute__((unused)) = true; + + using namespace __gnu_test; + + typedef tracker_allocator> alloc_type; + typedef std::map, 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; } diff --git a/libstdc++-v3/testsuite/23_containers/map/allocator/init-list.cc b/libstdc++-v3/testsuite/23_containers/map/allocator/init-list.cc new file mode 100644 index 00000000000..d33d10deab8 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/map/allocator/init-list.cc @@ -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 +// . +// + +// { dg-options "-std=gnu++11" } + +#include +#include +#include + +void test01() +{ + bool test __attribute__((unused)) = true; + + using namespace __gnu_test; + + typedef tracker_allocator> alloc_type; + typedef std::map, 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(); +} diff --git a/libstdc++-v3/testsuite/23_containers/map/allocator/move_assign.cc b/libstdc++-v3/testsuite/23_containers/map/allocator/move_assign.cc index 3a8f1f1c832..167e87dd36a 100644 --- a/libstdc++-v3/testsuite/23_containers/map/allocator/move_assign.cc +++ b/libstdc++-v3/testsuite/23_containers/map/allocator/move_assign.cc @@ -43,8 +43,8 @@ void test01() 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 @@ void test02() 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, false, + tracker_allocator>> + alloc_type; + typedef std::map, 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; } diff --git a/libstdc++-v3/testsuite/23_containers/multimap/allocator/copy_assign.cc b/libstdc++-v3/testsuite/23_containers/multimap/allocator/copy_assign.cc index 4c9c3710453..ee841a3320f 100644 --- a/libstdc++-v3/testsuite/23_containers/multimap/allocator/copy_assign.cc +++ b/libstdc++-v3/testsuite/23_containers/multimap/allocator/copy_assign.cc @@ -59,9 +59,33 @@ void test02() VERIFY(1 == v2.get_allocator().get_personality()); } +void test03() +{ + bool test __attribute__((unused)) = true; + + using namespace __gnu_test; + + typedef tracker_allocator> alloc_type; + typedef std::multimap, 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; } diff --git a/libstdc++-v3/testsuite/23_containers/multimap/allocator/init-list.cc b/libstdc++-v3/testsuite/23_containers/multimap/allocator/init-list.cc new file mode 100644 index 00000000000..c2241b41089 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/multimap/allocator/init-list.cc @@ -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 +// . +// + +// { dg-options "-std=gnu++11" } + +#include +#include +#include + +void test01() +{ + bool test __attribute__((unused)) = true; + + using namespace __gnu_test; + + typedef tracker_allocator> alloc_type; + typedef std::multimap, 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(); +} diff --git a/libstdc++-v3/testsuite/23_containers/multimap/allocator/move_assign.cc b/libstdc++-v3/testsuite/23_containers/multimap/allocator/move_assign.cc index 6b1386120ac..11b5e357531 100644 --- a/libstdc++-v3/testsuite/23_containers/multimap/allocator/move_assign.cc +++ b/libstdc++-v3/testsuite/23_containers/multimap/allocator/move_assign.cc @@ -61,9 +61,42 @@ void test02() VERIFY( it == v2.begin() ); } +void test03() +{ + bool test __attribute__((unused)) = true; + + using namespace __gnu_test; + + typedef propagating_allocator, false, + tracker_allocator>> + alloc_type; + typedef std::multimap, 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; } diff --git a/libstdc++-v3/testsuite/23_containers/multiset/allocator/copy_assign.cc b/libstdc++-v3/testsuite/23_containers/multiset/allocator/copy_assign.cc index 140af8c4f6b..f5921ab59b0 100644 --- a/libstdc++-v3/testsuite/23_containers/multiset/allocator/copy_assign.cc +++ b/libstdc++-v3/testsuite/23_containers/multiset/allocator/copy_assign.cc @@ -57,9 +57,33 @@ void test02() VERIFY(1 == v2.get_allocator().get_personality()); } +void test03() +{ + bool test __attribute__((unused)) = true; + + using namespace __gnu_test; + + typedef tracker_allocator alloc_type; + typedef std::multiset, 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; } diff --git a/libstdc++-v3/testsuite/23_containers/multiset/allocator/init-list.cc b/libstdc++-v3/testsuite/23_containers/multiset/allocator/init-list.cc new file mode 100644 index 00000000000..a657ae0f6cf --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/multiset/allocator/init-list.cc @@ -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 +// . +// + +// { dg-options "-std=gnu++11" } + +#include +#include +#include + +void test01() +{ + bool test __attribute__((unused)) = true; + + using namespace __gnu_test; + + typedef tracker_allocator alloc_type; + typedef std::multiset, 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(); +} diff --git a/libstdc++-v3/testsuite/23_containers/multiset/allocator/move_assign.cc b/libstdc++-v3/testsuite/23_containers/multiset/allocator/move_assign.cc index 956f885462c..405aff1d3d6 100644 --- a/libstdc++-v3/testsuite/23_containers/multiset/allocator/move_assign.cc +++ b/libstdc++-v3/testsuite/23_containers/multiset/allocator/move_assign.cc @@ -59,9 +59,40 @@ void test02() VERIFY( it == v2.begin() ); } +void test03() +{ + bool test __attribute__((unused)) = true; + + using namespace __gnu_test; + + typedef propagating_allocator> alloc_type; + typedef std::multiset, 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; } diff --git a/libstdc++-v3/testsuite/23_containers/set/allocator/copy_assign.cc b/libstdc++-v3/testsuite/23_containers/set/allocator/copy_assign.cc index 0e13d15ed3e..1176a700e7e 100644 --- a/libstdc++-v3/testsuite/23_containers/set/allocator/copy_assign.cc +++ b/libstdc++-v3/testsuite/23_containers/set/allocator/copy_assign.cc @@ -57,9 +57,33 @@ void test02() VERIFY(1 == v2.get_allocator().get_personality()); } +void test03() +{ + bool test __attribute__((unused)) = true; + + using namespace __gnu_test; + + typedef tracker_allocator alloc_type; + typedef std::set, 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; } diff --git a/libstdc++-v3/testsuite/23_containers/set/allocator/init-list.cc b/libstdc++-v3/testsuite/23_containers/set/allocator/init-list.cc new file mode 100644 index 00000000000..1c39da204af --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/set/allocator/init-list.cc @@ -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 +// . +// + +// { dg-options "-std=gnu++11" } + +#include +#include +#include + +void test01() +{ + bool test __attribute__((unused)) = true; + + using namespace __gnu_test; + + typedef tracker_allocator alloc_type; + typedef std::set, 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(); +} diff --git a/libstdc++-v3/testsuite/23_containers/set/allocator/move_assign.cc b/libstdc++-v3/testsuite/23_containers/set/allocator/move_assign.cc index 416e0b44315..f4d02e898ac 100644 --- a/libstdc++-v3/testsuite/23_containers/set/allocator/move_assign.cc +++ b/libstdc++-v3/testsuite/23_containers/set/allocator/move_assign.cc @@ -59,9 +59,40 @@ void test02() VERIFY( it == v2.begin() ); } +void test03() +{ + bool test __attribute__((unused)) = true; + + using namespace __gnu_test; + + typedef propagating_allocator> alloc_type; + typedef std::set, 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; } -- 2.30.2