From cc7f3d0eeef05fb8fc11384a9a29afae10a54cc7 Mon Sep 17 00:00:00 2001 From: Jonathan Wakely Date: Wed, 17 Jun 2015 21:36:42 +0100 Subject: [PATCH] C++11 allocator support for std::list. PR libstdc++/55409 * include/bits/list.tcc (_List_base::_M_clear()): Use allocator traits. (list::list(const list&)): Use allocator propagation trait. Use _M_assign_dispatch to copy elements. * include/bits/stl_list.h (_List_node): Use __aligned_membuf in C++11. (_List_node::_M_valptr()): Add accessor for stored value. (_List_iterator, _List_const_iterator, _List_base): Use _M_valptr(). (_List_base, list): Use allocator traits. (_List_base::_M_get_Tp_allocator, _List_base::get_allocator): Remove. (_List_base::_M_move_nodes): New function. (_List_base(_List_base&&)): Use _M_move_nodes. (_List_base(_List_base&&, _Node_alloc_type&&)): New constructor. (list::_M_create_node, list::_M_erase, list::max_size): Use allocator traits. (list(size_type)): Add allocator parameter. (list(const list&)): Use allocator propagation trait. (list(const list&, const allocator_type&)): New constructor. (list(list&&, const allocator_type&)): Likewise. (list::operator=(list&&), list::swap(list&)): Use allocator propagation traits. (list::_M_move_assign): New functions. * include/debug/list: Add allocator-extended constructors. * include/profile/list: Likewise. * python/libstdcxx/v6/printers.py (get_value_from_list_node): New function to get value from _List_node. (StdListPrinter): Use get_value_from_list_node. * testsuite/23_containers/list/allocator/copy.cc: New. * testsuite/23_containers/list/allocator/copy_assign.cc: New. * testsuite/23_containers/list/allocator/minimal.cc: New. * testsuite/23_containers/list/allocator/move.cc: New. * testsuite/23_containers/list/allocator/move_assign.cc: New. * testsuite/23_containers/list/allocator/noexcept.cc: New. * testsuite/23_containers/list/allocator/swap.cc: New. * testsuite/23_containers/list/requirements/dr438/assign_neg.cc: Adjust dg-prune-output line number. * testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc: Likewise. * testsuite/23_containers/list/requirements/dr438/insert_neg.cc: Likewise. From-SVN: r224580 --- libstdc++-v3/ChangeLog | 40 ++++ libstdc++-v3/include/bits/list.tcc | 31 ++- libstdc++-v3/include/bits/stl_list.h | 226 +++++++++++------- libstdc++-v3/include/debug/list | 10 +- libstdc++-v3/include/profile/list | 10 +- libstdc++-v3/python/libstdcxx/v6/printers.py | 24 +- .../23_containers/list/allocator/copy.cc | 70 ++++++ .../list/allocator/copy_assign.cc | 61 +++++ .../23_containers/list/allocator/minimal.cc | 48 ++++ .../23_containers/list/allocator/move.cc | 59 +++++ .../list/allocator/move_assign.cc | 63 +++++ .../23_containers/list/allocator/noexcept.cc | 66 +++++ .../23_containers/list/allocator/swap.cc | 80 +++++++ .../list/requirements/dr438/assign_neg.cc | 2 +- .../requirements/dr438/constructor_1_neg.cc | 2 +- .../list/requirements/dr438/insert_neg.cc | 2 +- 16 files changed, 681 insertions(+), 113 deletions(-) create mode 100644 libstdc++-v3/testsuite/23_containers/list/allocator/copy.cc create mode 100644 libstdc++-v3/testsuite/23_containers/list/allocator/copy_assign.cc create mode 100644 libstdc++-v3/testsuite/23_containers/list/allocator/minimal.cc create mode 100644 libstdc++-v3/testsuite/23_containers/list/allocator/move.cc create mode 100644 libstdc++-v3/testsuite/23_containers/list/allocator/move_assign.cc create mode 100644 libstdc++-v3/testsuite/23_containers/list/allocator/noexcept.cc create mode 100644 libstdc++-v3/testsuite/23_containers/list/allocator/swap.cc diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index ea0a60d4b9e..345bf945ded 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,5 +1,45 @@ 2015-06-17 Jonathan Wakely + PR libstdc++/55409 + * include/bits/list.tcc (_List_base::_M_clear()): Use allocator traits. + (list::list(const list&)): Use allocator propagation trait. Use + _M_assign_dispatch to copy elements. + * include/bits/stl_list.h (_List_node): Use __aligned_membuf in C++11. + (_List_node::_M_valptr()): Add accessor for stored value. + (_List_iterator, _List_const_iterator, _List_base): Use _M_valptr(). + (_List_base, list): Use allocator traits. + (_List_base::_M_get_Tp_allocator, _List_base::get_allocator): Remove. + (_List_base::_M_move_nodes): New function. + (_List_base(_List_base&&)): Use _M_move_nodes. + (_List_base(_List_base&&, _Node_alloc_type&&)): New constructor. + (list::_M_create_node, list::_M_erase, list::max_size): Use allocator + traits. + (list(size_type)): Add allocator parameter. + (list(const list&)): Use allocator propagation trait. + (list(const list&, const allocator_type&)): New constructor. + (list(list&&, const allocator_type&)): Likewise. + (list::operator=(list&&), list::swap(list&)): Use allocator + propagation traits. + (list::_M_move_assign): New functions. + * include/debug/list: Add allocator-extended constructors. + * include/profile/list: Likewise. + * python/libstdcxx/v6/printers.py (get_value_from_list_node): New + function to get value from _List_node. + (StdListPrinter): Use get_value_from_list_node. + * testsuite/23_containers/list/allocator/copy.cc: New. + * testsuite/23_containers/list/allocator/copy_assign.cc: New. + * testsuite/23_containers/list/allocator/minimal.cc: New. + * testsuite/23_containers/list/allocator/move.cc: New. + * testsuite/23_containers/list/allocator/move_assign.cc: New. + * testsuite/23_containers/list/allocator/noexcept.cc: New. + * testsuite/23_containers/list/allocator/swap.cc: New. + * testsuite/23_containers/list/requirements/dr438/assign_neg.cc: + Adjust dg-prune-output line number. + * testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc: + Likewise. + * testsuite/23_containers/list/requirements/dr438/insert_neg.cc: + Likewise. + * include/bits/forward_list.h (_Fwd_list_base(const _Node_alloc_type&)): Change parameter to rvalue-reference. diff --git a/libstdc++-v3/include/bits/list.tcc b/libstdc++-v3/include/bits/list.tcc index 95193c19a24..714d9b522a7 100644 --- a/libstdc++-v3/include/bits/list.tcc +++ b/libstdc++-v3/include/bits/list.tcc @@ -71,10 +71,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { _Node* __tmp = static_cast<_Node*>(__cur); __cur = __tmp->_M_next; + _Tp* __val = __tmp->_M_valptr(); #if __cplusplus >= 201103L - _M_get_Node_allocator().destroy(__tmp); + _Node_alloc_traits::destroy(_M_get_Node_allocator(), __val); #else - _M_get_Tp_allocator().destroy(std::__addressof(__tmp->_M_data)); + _Tp_alloc_type(_M_get_Node_allocator()).destroy(__val); #endif _M_put_node(__tmp); } @@ -267,17 +268,21 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { if (this != std::__addressof(__x)) { - iterator __first1 = begin(); - iterator __last1 = end(); - const_iterator __first2 = __x.begin(); - const_iterator __last2 = __x.end(); - for (; __first1 != __last1 && __first2 != __last2; - ++__first1, ++__first2) - *__first1 = *__first2; - if (__first2 == __last2) - erase(__first1, __last1); - else - insert(__last1, __first2, __last2); +#if __cplusplus >= 201103L + if (_Node_alloc_traits::_S_propagate_on_copy_assign()) + { + auto& __this_alloc = this->_M_get_Node_allocator(); + auto& __that_alloc = __x._M_get_Node_allocator(); + if (!_Node_alloc_traits::_S_always_equal() + && __this_alloc != __that_alloc) + { + // replacement allocator cannot free existing storage + clear(); + } + std::__alloc_on_copy(__this_alloc, __that_alloc); + } +#endif + _M_assign_dispatch(__x.begin(), __x.end(), __false_type()); } return *this; } diff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h index a498de5d3a6..6a729fb992e 100644 --- a/libstdc++-v3/include/bits/stl_list.h +++ b/libstdc++-v3/include/bits/stl_list.h @@ -57,8 +57,11 @@ #define _STL_LIST_H 1 #include +#include #if __cplusplus >= 201103L #include +#include +#include #endif namespace std _GLIBCXX_VISIBILITY(default) @@ -105,14 +108,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER template struct _List_node : public __detail::_List_node_base { - ///< User's data. - _Tp _M_data; - #if __cplusplus >= 201103L - template - _List_node(_Args&&... __args) - : __detail::_List_node_base(), _M_data(std::forward<_Args>(__args)...) - { } + __gnu_cxx::__aligned_membuf<_Tp> _M_storage; + _Tp* _M_valptr() { return _M_storage._M_ptr(); } + _Tp const* _M_valptr() const { return _M_storage._M_ptr(); } +#else + _Tp _M_data; + _Tp* _M_valptr() { return std::__addressof(_M_data); } + _Tp const* _M_valptr() const { return std::__addressof(_M_data); } #endif }; @@ -144,14 +147,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _M_const_cast() const _GLIBCXX_NOEXCEPT { return *this; } - // Must downcast from _List_node_base to _List_node to get to _M_data. + // Must downcast from _List_node_base to _List_node to get to value. reference operator*() const _GLIBCXX_NOEXCEPT - { return static_cast<_Node*>(_M_node)->_M_data; } + { return *static_cast<_Node*>(_M_node)->_M_valptr(); } pointer operator->() const _GLIBCXX_NOEXCEPT - { return std::__addressof(static_cast<_Node*>(_M_node)->_M_data); } + { return static_cast<_Node*>(_M_node)->_M_valptr(); } _Self& operator++() _GLIBCXX_NOEXCEPT @@ -228,15 +231,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _M_const_cast() const _GLIBCXX_NOEXCEPT { return iterator(const_cast<__detail::_List_node_base*>(_M_node)); } - // Must downcast from List_node_base to _List_node to get to - // _M_data. + // Must downcast from List_node_base to _List_node to get to value. reference operator*() const _GLIBCXX_NOEXCEPT - { return static_cast<_Node*>(_M_node)->_M_data; } + { return *static_cast<_Node*>(_M_node)->_M_valptr(); } pointer operator->() const _GLIBCXX_NOEXCEPT - { return std::__addressof(static_cast<_Node*>(_M_node)->_M_data); } + { return static_cast<_Node*>(_M_node)->_M_valptr(); } _Self& operator++() _GLIBCXX_NOEXCEPT @@ -298,23 +300,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 class _List_base { protected: - // NOTA BENE - // The stored instance is not actually of "allocator_type"'s - // type. Instead we rebind the type to - // Allocator>, which according to [20.1.5]/4 - // should probably be the same. List_node is not the same - // size as Tp (it's two pointers larger), and specializations on - // Tp may go unused because List_node is being bound - // instead. - // - // We put this to the test in the constructors and in - // get_allocator, where we use conversions between - // allocator_type and _Node_alloc_type. The conversion is - // required by table 32 in [20.1.5]. - typedef typename _Alloc::template rebind<_List_node<_Tp> >::other - _Node_alloc_type; - - typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type; + typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template + rebind<_Tp>::other _Tp_alloc_type; + typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tp_alloc_traits; + typedef typename _Tp_alloc_traits::template + rebind<_List_node<_Tp> >::other _Node_alloc_type; + typedef __gnu_cxx::__alloc_traits<_Node_alloc_type> _Node_alloc_traits; static size_t _S_distance(const __detail::_List_node_base* __first, @@ -338,7 +329,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 __detail::_List_node_base _M_node; #endif - _List_impl() + _List_impl() _GLIBCXX_NOEXCEPT : _Node_alloc_type(), _M_node() { } @@ -347,7 +338,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 { } #if __cplusplus >= 201103L - _List_impl(_Node_alloc_type&& __a) _GLIBCXX_NOEXCEPT + _List_impl(_Node_alloc_type&& __a) noexcept : _Node_alloc_type(std::move(__a)), _M_node() { } #endif @@ -356,13 +347,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 _List_impl _M_impl; #if _GLIBCXX_USE_CXX11_ABI - size_t _M_get_size() const { return _M_impl._M_node._M_data; } + size_t _M_get_size() const { return *_M_impl._M_node._M_valptr(); } - void _M_set_size(size_t __n) { _M_impl._M_node._M_data = __n; } + void _M_set_size(size_t __n) { *_M_impl._M_node._M_valptr() = __n; } - void _M_inc_size(size_t __n) { _M_impl._M_node._M_data += __n; } + void _M_inc_size(size_t __n) { *_M_impl._M_node._M_valptr() += __n; } - void _M_dec_size(size_t __n) { _M_impl._M_node._M_data -= __n; } + void _M_dec_size(size_t __n) { *_M_impl._M_node._M_valptr() -= __n; } size_t _M_distance(const __detail::_List_node_base* __first, @@ -370,7 +361,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 { return _S_distance(__first, __last); } // return the stored size - size_t _M_node_count() const { return _M_impl._M_node._M_data; } + size_t _M_node_count() const { return *_M_impl._M_node._M_valptr(); } #else // dummy implementations used when the size is not stored size_t _M_get_size() const { return 0; } @@ -387,32 +378,24 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 } #endif - _List_node<_Tp>* + typename _Node_alloc_traits::pointer _M_get_node() - { return _M_impl._Node_alloc_type::allocate(1); } + { return _Node_alloc_traits::allocate(_M_impl, 1); } void - _M_put_node(_List_node<_Tp>* __p) _GLIBCXX_NOEXCEPT - { _M_impl._Node_alloc_type::deallocate(__p, 1); } + _M_put_node(typename _Node_alloc_traits::pointer __p) _GLIBCXX_NOEXCEPT + { _Node_alloc_traits::deallocate(_M_impl, __p, 1); } public: typedef _Alloc allocator_type; _Node_alloc_type& _M_get_Node_allocator() _GLIBCXX_NOEXCEPT - { return *static_cast<_Node_alloc_type*>(&_M_impl); } + { return _M_impl; } const _Node_alloc_type& _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT - { return *static_cast(&_M_impl); } - - _Tp_alloc_type - _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT - { return _Tp_alloc_type(_M_get_Node_allocator()); } - - allocator_type - get_allocator() const _GLIBCXX_NOEXCEPT - { return allocator_type(_M_get_Node_allocator()); } + { return _M_impl; } _List_base() : _M_impl() @@ -425,6 +408,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 #if __cplusplus >= 201103L _List_base(_List_base&& __x) noexcept : _M_impl(std::move(__x._M_get_Node_allocator())) + { _M_move_nodes(std::move(__x)); } + + _List_base(_List_base&& __x, _Node_alloc_type&& __a) + : _M_impl(std::move(__a)) + { + if (__x._M_get_Node_allocator() == _M_get_Node_allocator()) + _M_move_nodes(std::move(__x)); + else + _M_init(); // Caller must move individual elements. + } + + void + _M_move_nodes(_List_base&& __x) { auto* const __xnode = std::__addressof(__x._M_impl._M_node); if (__xnode->_M_next == __xnode) @@ -513,16 +509,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 typedef _List_base<_Tp, _Alloc> _Base; typedef typename _Base::_Tp_alloc_type _Tp_alloc_type; + typedef typename _Base::_Tp_alloc_traits _Tp_alloc_traits; typedef typename _Base::_Node_alloc_type _Node_alloc_type; + typedef typename _Base::_Node_alloc_traits _Node_alloc_traits; public: typedef _Tp value_type; - typedef typename _Tp_alloc_type::pointer pointer; - typedef typename _Tp_alloc_type::const_pointer const_pointer; - typedef typename _Tp_alloc_type::reference reference; - typedef typename _Tp_alloc_type::const_reference const_reference; - typedef _List_iterator<_Tp> iterator; - typedef _List_const_iterator<_Tp> const_iterator; + typedef typename _Tp_alloc_traits::pointer pointer; + typedef typename _Tp_alloc_traits::const_pointer const_pointer; + typedef typename _Tp_alloc_traits::reference reference; + typedef typename _Tp_alloc_traits::const_reference const_reference; + typedef _List_iterator<_Tp> iterator; + typedef _List_const_iterator<_Tp> const_iterator; typedef std::reverse_iterator const_reverse_iterator; typedef std::reverse_iterator reverse_iterator; typedef size_t size_type; @@ -537,7 +535,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 using _Base::_M_impl; using _Base::_M_put_node; using _Base::_M_get_node; - using _Base::_M_get_Tp_allocator; using _Base::_M_get_Node_allocator; /** @@ -553,8 +550,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 _Node* __p = this->_M_get_node(); __try { - _M_get_Tp_allocator().construct - (std::__addressof(__p->_M_data), __x); + _Tp_alloc_type __alloc(_M_get_Node_allocator()); + __alloc.construct(__p->_M_valptr(), __x); } __catch(...) { @@ -568,17 +565,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 _Node* _M_create_node(_Args&&... __args) { - _Node* __p = this->_M_get_node(); - __try - { - _M_get_Node_allocator().construct(__p, - std::forward<_Args>(__args)...); - } - __catch(...) - { - _M_put_node(__p); - __throw_exception_again; - } + auto __p = this->_M_get_node(); + auto& __alloc = _M_get_Node_allocator(); + __allocated_ptr<_Node_alloc_type> __guard{__alloc, __p}; + _Node_alloc_traits::construct(__alloc, __p->_M_valptr(), + std::forward<_Args>(__args)...); + __guard = nullptr; return __p; } #endif @@ -608,13 +600,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 /** * @brief Creates a %list with default constructed elements. * @param __n The number of elements to initially create. + * @param __a An allocator object. * * This constructor fills the %list with @a __n default * constructed elements. */ explicit - list(size_type __n) - : _Base() + list(size_type __n, const allocator_type& __a = allocator_type()) + : _Base(_Node_alloc_type(__a)) { _M_default_initialize(__n); } /** @@ -653,7 +646,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 * by @a __x. */ list(const list& __x) - : _Base(__x._M_get_Node_allocator()) + : _Base(_Node_alloc_traits:: + _S_select_on_copy(__x._M_get_Node_allocator())) { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); } #if __cplusplus >= 201103L @@ -679,6 +673,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 const allocator_type& __a = allocator_type()) : _Base(_Node_alloc_type(__a)) { _M_initialize_dispatch(__l.begin(), __l.end(), __false_type()); } + + list(const list& __x, const allocator_type& __a) + : _Base(_Node_alloc_type(__a)) + { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); } + + list(list&& __x, const allocator_type& __a) + noexcept(_Node_alloc_traits::_S_always_equal()) + : _Base(std::move(__x), _Node_alloc_type(__a)) + { + // If __x is not empty it means its allocator is not equal to __a, + // so we need to move from each element individually. + insert(begin(), std::__make_move_if_noexcept_iterator(__x.begin()), + std::__make_move_if_noexcept_iterator(__x.end())); + } #endif /** @@ -738,11 +746,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 */ list& operator=(list&& __x) + noexcept(_Node_alloc_traits::_S_nothrow_move()) { - // NB: DR 1204. - // NB: DR 675. - this->clear(); - this->swap(__x); + constexpr bool __move_storage = + _Node_alloc_traits::_S_propagate_on_move_assign() + || _Node_alloc_traits::_S_always_equal(); + _M_move_assign(std::move(__x), + integral_constant()); return *this; } @@ -820,7 +830,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 /// Get a copy of the memory allocation object. allocator_type get_allocator() const _GLIBCXX_NOEXCEPT - { return _Base::get_allocator(); } + { return allocator_type(_Base::_M_get_Node_allocator()); } // iterators /** @@ -949,7 +959,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 /** Returns the size() of the largest possible %list. */ size_type max_size() const _GLIBCXX_NOEXCEPT - { return _M_get_Node_allocator().max_size(); } + { return _Node_alloc_traits::max_size(_M_get_Node_allocator()); } #if __cplusplus >= 201103L /** @@ -1342,18 +1352,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 */ void swap(list& __x) +#if __cplusplus >= 201103L + noexcept(_Node_alloc_traits::_S_nothrow_swap()) +#endif { - __detail::_List_node_base::swap(this->_M_impl._M_node, - __x._M_impl._M_node); + __detail::_List_node_base::swap(this->_M_impl._M_node, + __x._M_impl._M_node); size_t __xsize = __x._M_get_size(); __x._M_set_size(this->_M_get_size()); this->_M_set_size(__xsize); - // _GLIBCXX_RESOLVE_LIB_DEFECTS - // 431. Swapping containers with unequal allocators. - std::__alloc_swap:: - _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator()); + _Node_alloc_traits::_S_on_swap(this->_M_get_Node_allocator(), + __x._M_get_Node_allocator()); } /** @@ -1774,10 +1785,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 __position._M_node->_M_unhook(); _Node* __n = static_cast<_Node*>(__position._M_node); #if __cplusplus >= 201103L - _M_get_Node_allocator().destroy(__n); + _Node_alloc_traits::destroy(_M_get_Node_allocator(), __n->_M_valptr()); #else - _M_get_Tp_allocator().destroy(std::__addressof(__n->_M_data)); + _Tp_alloc_type(_M_get_Node_allocator()).destroy(__n->_M_valptr()); #endif + _M_put_node(__n); } @@ -1793,6 +1805,40 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 // Used to implement resize. const_iterator _M_resize_pos(size_type& __new_size) const; + +#if __cplusplus >= 201103L + void + _M_move_assign(list&& __x, true_type) noexcept + { + this->_M_clear(); + if (__x.empty()) + this->_M_init(); + else + { + this->_M_impl._M_node._M_next = __x._M_impl._M_node._M_next; + this->_M_impl._M_node._M_next->_M_prev = &this->_M_impl._M_node; + this->_M_impl._M_node._M_prev = __x._M_impl._M_node._M_prev; + this->_M_impl._M_node._M_prev->_M_next = &this->_M_impl._M_node; + this->_M_set_size(__x._M_get_size()); + __x._M_init(); + } + std::__alloc_on_move(this->_M_get_Node_allocator(), + __x._M_get_Node_allocator()); + } + + void + _M_move_assign(list&& __x, false_type) + { + if (__x._M_get_Node_allocator() == this->_M_get_Node_allocator()) + _M_move_assign(std::move(__x), true_type{}); + else + // The rvalue's allocator cannot be moved, or is not equal, + // so we need to individually move each element. + _M_assign_dispatch(std::__make_move_if_noexcept_iterator(__x.begin()), + std::__make_move_if_noexcept_iterator(__x.end()), + __false_type{}); + } +#endif }; _GLIBCXX_END_NAMESPACE_CXX11 @@ -1903,7 +1949,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION ++__beyond; bool __whole = __first == __beyond; if (__builtin_constant_p (__whole) && __whole) - return static_cast(__last._M_node)->_M_data; + return *static_cast(__last._M_node)->_M_valptr(); ptrdiff_t __n = 0; while (__first != __last) diff --git a/libstdc++-v3/include/debug/list b/libstdc++-v3/include/debug/list index 9f4c9c0a974..1562946311b 100644 --- a/libstdc++-v3/include/debug/list +++ b/libstdc++-v3/include/debug/list @@ -94,6 +94,12 @@ namespace __debug : _Base(__l, __a) { } ~list() = default; + + list(const list& __x, const allocator_type& __a) + : _Base(__x, __a) { } + + list(list&& __x, const allocator_type& __a) + : _Base(std::move(__x), __a) { } #endif explicit @@ -102,8 +108,8 @@ namespace __debug #if __cplusplus >= 201103L explicit - list(size_type __n) - : _Base(__n) { } + list(size_type __n, const allocator_type& __a = allocator_type()) + : _Base(__n, __a) { } list(size_type __n, const _Tp& __value, const _Allocator& __a = _Allocator()) diff --git a/libstdc++-v3/include/profile/list b/libstdc++-v3/include/profile/list index e21244c015b..b5943ee6dfc 100644 --- a/libstdc++-v3/include/profile/list +++ b/libstdc++-v3/include/profile/list @@ -145,6 +145,12 @@ namespace __profile list(initializer_list __l, const allocator_type& __a = allocator_type()) : _Base(__l, __a) { } + + list(const list& __x, const allocator_type& __a) + : _Base(__x, __a) { } + + list(list&& __x, const allocator_type& __a) + : _Base(std::move(__x), __a) { } #endif explicit @@ -153,8 +159,8 @@ namespace __profile #if __cplusplus >= 201103L explicit - list(size_type __n) - : _Base(__n) { } + list(size_type __n, const allocator_type& __a = allocator_type()) + : _Base(__n, __a) { } list(size_type __n, const _Tp& __value, const _Allocator& __a = _Allocator()) diff --git a/libstdc++-v3/python/libstdcxx/v6/printers.py b/libstdc++-v3/python/libstdcxx/v6/printers.py index 2b6e4096ae4..2d167863ad3 100644 --- a/libstdc++-v3/python/libstdcxx/v6/printers.py +++ b/libstdc++-v3/python/libstdcxx/v6/printers.py @@ -128,6 +128,22 @@ class UniquePointerPrinter: return ('std::unique_ptr<%s> containing %s' % (str(v.type.target()), str(v))) +def get_value_from_list_node(node): + """Returns the value held in an _List_node<_Val>""" + try: + member = node.type.fields()[1].name + if member == '_M_data': + # C++03 implementation, node contains the value as a member + return node['_M_data'] + elif member == '_M_storage': + # C++11 implementation, node stores value in __aligned_membuf + p = node['_M_storage']['_M_storage'].address + p = p.cast(node.type.template_argument(0).pointer()) + return p.dereference() + except: + pass + raise ValueError("Unsupported implementation for %s" % str(node.type)) + class StdListPrinter: "Print a std::list" @@ -148,7 +164,8 @@ class StdListPrinter: self.base = elt['_M_next'] count = self.count self.count = self.count + 1 - return ('[%d]' % count, elt['_M_data']) + val = get_value_from_list_node(elt) + return ('[%d]' % count, val) def __init__(self, typename, val): self.typename = typename @@ -174,7 +191,8 @@ class StdListIteratorPrinter: def to_string(self): nodetype = find_type(self.val.type, '_Node') nodetype = nodetype.strip_typedefs().pointer() - return self.val['_M_node'].cast(nodetype).dereference()['_M_data'] + node = self.val['_M_node'].cast(nodetype).dereference() + return get_value_from_list_node(node) class StdSlistPrinter: "Print a __gnu_cxx::slist" @@ -440,7 +458,7 @@ def get_value_from_Rb_tree_node(node): # C++03 implementation, node contains the value as a member return node['_M_value_field'] elif member == '_M_storage': - # C++11 implementation, node stores value in __aligned_buffer + # C++11 implementation, node stores value in __aligned_membuf p = node['_M_storage']['_M_storage'].address p = p.cast(node.type.template_argument(0).pointer()) return p.dereference() diff --git a/libstdc++-v3/testsuite/23_containers/list/allocator/copy.cc b/libstdc++-v3/testsuite/23_containers/list/allocator/copy.cc new file mode 100644 index 00000000000..8346deee307 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/list/allocator/copy.cc @@ -0,0 +1,70 @@ +// Copyright (C) 2015 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 + +struct T { int i; }; + +using __gnu_test::propagating_allocator; + +void test01() +{ + bool test __attribute__((unused)) = true; + typedef propagating_allocator alloc_type; + typedef std::list test_type; + test_type v1(alloc_type(1)); + v1.push_front(T()); + test_type v2(v1); + VERIFY(1 == v1.get_allocator().get_personality()); + VERIFY(0 == v2.get_allocator().get_personality()); +} + +void test02() +{ + bool test __attribute__((unused)) = true; + typedef propagating_allocator alloc_type; + typedef std::list test_type; + test_type v1(alloc_type(1)); + v1.push_front(T()); + test_type v2(v1); + VERIFY(1 == v1.get_allocator().get_personality()); + VERIFY(1 == v2.get_allocator().get_personality()); +} + +void test03() +{ + bool test __attribute__((unused)) = true; + typedef propagating_allocator alloc_type; + typedef std::list test_type; + test_type v1(alloc_type(1)); + v1.push_front(T()); + test_type v2(v1, alloc_type(2)); + VERIFY(1 == v1.get_allocator().get_personality()); + VERIFY(2 == v2.get_allocator().get_personality()); +} + +int main() +{ + test01(); + test02(); + test03(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/list/allocator/copy_assign.cc b/libstdc++-v3/testsuite/23_containers/list/allocator/copy_assign.cc new file mode 100644 index 00000000000..1a2aa0a8e2f --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/list/allocator/copy_assign.cc @@ -0,0 +1,61 @@ +// Copyright (C) 2015 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 + +struct T { int i; }; + +using __gnu_test::propagating_allocator; + +void test01() +{ + bool test __attribute__((unused)) = true; + typedef propagating_allocator alloc_type; + typedef std::list test_type; + test_type v1(alloc_type(1)); + v1.push_front(T()); + test_type v2(alloc_type(2)); + v2.push_front(T()); + v2 = v1; + VERIFY(1 == v1.get_allocator().get_personality()); + VERIFY(2 == v2.get_allocator().get_personality()); +} + +void test02() +{ + bool test __attribute__((unused)) = true; + typedef propagating_allocator alloc_type; + typedef std::list test_type; + test_type v1(alloc_type(1)); + v1.push_front(T()); + test_type v2(alloc_type(2)); + v2.push_front(T()); + v2 = v1; + VERIFY(1 == v1.get_allocator().get_personality()); + VERIFY(1 == v2.get_allocator().get_personality()); +} + +int main() +{ + test01(); + test02(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/list/allocator/minimal.cc b/libstdc++-v3/testsuite/23_containers/list/allocator/minimal.cc new file mode 100644 index 00000000000..f9dbdac4a14 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/list/allocator/minimal.cc @@ -0,0 +1,48 @@ +// Copyright (C) 2015 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 +#include + +struct T { int i; }; +bool operator==(const T& l, const T& r) { return l.i == r.i; } +bool operator<(const T& l, const T& r) { return l.i < r.i; } + +using __gnu_test::SimpleAllocator; + +template class std::list>; + +void test01() +{ + bool test __attribute__((unused)) = true; + typedef SimpleAllocator alloc_type; + typedef std::allocator_traits traits_type; + typedef std::list test_type; + test_type v(alloc_type{}); + v.push_front(T()); + VERIFY( v.max_size() < traits_type::max_size(v.get_allocator()) ); +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/list/allocator/move.cc b/libstdc++-v3/testsuite/23_containers/list/allocator/move.cc new file mode 100644 index 00000000000..c43c1900bee --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/list/allocator/move.cc @@ -0,0 +1,59 @@ +// Copyright (C) 2015 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 + +struct T { int i; }; + +using __gnu_test::uneq_allocator; + +void test01() +{ + bool test __attribute__((unused)) = true; + typedef uneq_allocator alloc_type; + typedef std::list test_type; + test_type v1(alloc_type(1)); + v1 = { T() }; + auto it = v1.begin(); + test_type v2(std::move(v1)); + VERIFY(1 == v1.get_allocator().get_personality()); + VERIFY(1 == v2.get_allocator().get_personality()); + VERIFY( it == v2.begin() ); +} + +void test02() +{ + bool test __attribute__((unused)) = true; + typedef uneq_allocator alloc_type; + typedef std::list test_type; + test_type v1(alloc_type(1)); + v1 = { T() }; + test_type v2(std::move(v1), alloc_type(2)); + VERIFY(1 == v1.get_allocator().get_personality()); + VERIFY(2 == v2.get_allocator().get_personality()); +} + +int main() +{ + test01(); + test02(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/list/allocator/move_assign.cc b/libstdc++-v3/testsuite/23_containers/list/allocator/move_assign.cc new file mode 100644 index 00000000000..5bf1b34b76e --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/list/allocator/move_assign.cc @@ -0,0 +1,63 @@ +// Copyright (C) 2015 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 + +struct T { int i; }; + +using __gnu_test::propagating_allocator; + +void test01() +{ + bool test __attribute__((unused)) = true; + typedef propagating_allocator alloc_type; + typedef std::list test_type; + test_type v1(alloc_type(1)); + v1.push_front(T()); + test_type v2(alloc_type(2)); + v2.push_front(T()); + v2 = std::move(v1); + VERIFY(1 == v1.get_allocator().get_personality()); + VERIFY(2 == v2.get_allocator().get_personality()); +} + +void test02() +{ + bool test __attribute__((unused)) = true; + typedef propagating_allocator alloc_type; + typedef std::list test_type; + test_type v1(alloc_type(1)); + v1.push_front(T()); + auto it = v1.begin(); + test_type v2(alloc_type(2)); + v2.push_front(T()); + v2 = std::move(v1); + VERIFY(0 == v1.get_allocator().get_personality()); + VERIFY(1 == v2.get_allocator().get_personality()); + VERIFY( it == v2.begin() ); +} + +int main() +{ + test01(); + test02(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/list/allocator/noexcept.cc b/libstdc++-v3/testsuite/23_containers/list/allocator/noexcept.cc new file mode 100644 index 00000000000..4a84fceb540 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/list/allocator/noexcept.cc @@ -0,0 +1,66 @@ +// Copyright (C) 2015 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-do compile } +// { dg-options "-std=gnu++11" } + +#include +#include + +struct T { int i; }; + +namespace __gnu_test +{ + template + inline void + swap(propagating_allocator& l, propagating_allocator& r) + noexcept(false) + { } +} + +using __gnu_test::propagating_allocator; + +void test01() +{ + typedef std::allocator alloc_type; + typedef std::list test_type; + test_type v1; + test_type v2; + // this is a GNU extension for std::allocator + static_assert( noexcept( v1 = std::move(v2) ), "Move assign cannot throw" ); + static_assert( noexcept( v1.swap(v2) ), "Swap cannot throw" ); +} + +void test02() +{ + typedef propagating_allocator alloc_type; + typedef std::list test_type; + test_type v1(alloc_type(1)); + test_type v2(alloc_type(2)); + static_assert( !noexcept( v1 = std::move(v2) ), "Move assign can throw" ); + static_assert( noexcept( v1.swap(v2) ), "Swap cannot throw" ); +} + +void test03() +{ + typedef propagating_allocator alloc_type; + typedef std::list test_type; + test_type v1(alloc_type(1)); + test_type v2(alloc_type(2)); + static_assert( noexcept( v1 = std::move(v2) ), "Move assign cannot throw" ); + static_assert( !noexcept( v1.swap(v2) ), "Swap can throw" ); +} diff --git a/libstdc++-v3/testsuite/23_containers/list/allocator/swap.cc b/libstdc++-v3/testsuite/23_containers/list/allocator/swap.cc new file mode 100644 index 00000000000..2ba08fdfb84 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/list/allocator/swap.cc @@ -0,0 +1,80 @@ +// Copyright (C) 2015 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 + +struct T { int i; }; + +using __gnu_test::propagating_allocator; + +// It is undefined behaviour to swap() containers wth unequal allocators +// if the allocator doesn't propagate, so ensure the allocators compare +// equal, while still being able to test propagation via get_personality(). +bool +operator==(const propagating_allocator&, + const propagating_allocator&) +{ + return true; +} + +bool +operator!=(const propagating_allocator&, + const propagating_allocator&) +{ + return false; +} + +void test01() +{ + bool test __attribute__((unused)) = true; + typedef propagating_allocator alloc_type; + typedef std::list test_type; + test_type v1(alloc_type(1)); + v1.push_front(T()); + test_type v2(alloc_type(2)); + v2.push_front(T()); + std::swap(v1, v2); + VERIFY(1 == v1.get_allocator().get_personality()); + VERIFY(2 == v2.get_allocator().get_personality()); + // swap back so assertions in uneq_allocator::deallocate don't fail + std::swap(v1, v2); +} + +void test02() +{ + bool test __attribute__((unused)) = true; + typedef propagating_allocator alloc_type; + typedef std::list test_type; + test_type v1(alloc_type(1)); + v1.push_front(T()); + test_type v2(alloc_type(2)); + v2.push_front(T()); + std::swap(v1, v2); + VERIFY(2 == v1.get_allocator().get_personality()); + VERIFY(1 == v2.get_allocator().get_personality()); +} + +int main() +{ + test01(); + test02(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/assign_neg.cc b/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/assign_neg.cc index 0a60dd78e6d..84c74734806 100644 --- a/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/assign_neg.cc +++ b/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/assign_neg.cc @@ -18,7 +18,7 @@ // . // { dg-do compile } -// { dg-prune-output 1730 } +// { dg-prune-output 1741 } #include diff --git a/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc b/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc index 8de8b1ad0ad..947029c043f 100644 --- a/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc +++ b/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc @@ -18,7 +18,7 @@ // . // { dg-do compile } -// { dg-prune-output 1682 } +// { dg-prune-output 1693 } #include diff --git a/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/insert_neg.cc b/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/insert_neg.cc index c927735ff8d..54e89328ce0 100644 --- a/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/insert_neg.cc +++ b/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/insert_neg.cc @@ -18,7 +18,7 @@ // . // { dg-do compile } -// { dg-prune-output 1682 } +// { dg-prune-output 1693 } #include -- 2.30.2