diff options
Diffstat (limited to 'libstdc++-v3/include/bits/stl_deque.h')
| -rw-r--r-- | libstdc++-v3/include/bits/stl_deque.h | 316 |
1 files changed, 242 insertions, 74 deletions
diff --git a/libstdc++-v3/include/bits/stl_deque.h b/libstdc++-v3/include/bits/stl_deque.h index add8742a102..acb7715f717 100644 --- a/libstdc++-v3/include/bits/stl_deque.h +++ b/libstdc++-v3/include/bits/stl_deque.h @@ -85,7 +85,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER #define _GLIBCXX_DEQUE_BUF_SIZE 512 #endif - inline size_t + _GLIBCXX_CONSTEXPR inline size_t __deque_buf_size(size_t __size) { return (__size < _GLIBCXX_DEQUE_BUF_SIZE ? size_t(_GLIBCXX_DEQUE_BUF_SIZE / __size) : size_t(1)); } @@ -105,8 +105,23 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER template<typename _Tp, typename _Ref, typename _Ptr> struct _Deque_iterator { +#if __cplusplus < 201103L typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator; typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; + typedef _Tp* _Elt_pointer; + typedef _Tp** _Map_pointer; +#else + private: + template<typename _Up> + using __ptr_to = typename pointer_traits<_Ptr>::template rebind<_Up>; + template<typename _CvTp> + using __iter = _Deque_iterator<_Tp, _CvTp&, __ptr_to<_CvTp>>; + public: + typedef __iter<_Tp> iterator; + typedef __iter<const _Tp> const_iterator; + typedef __ptr_to<_Tp> _Elt_pointer; + typedef __ptr_to<_Elt_pointer> _Map_pointer; +#endif static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT { return __deque_buf_size(sizeof(_Tp)); } @@ -117,20 +132,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER typedef _Ref reference; typedef size_t size_type; typedef ptrdiff_t difference_type; - typedef _Tp** _Map_pointer; typedef _Deque_iterator _Self; - _Tp* _M_cur; - _Tp* _M_first; - _Tp* _M_last; + _Elt_pointer _M_cur; + _Elt_pointer _M_first; + _Elt_pointer _M_last; _Map_pointer _M_node; - _Deque_iterator(_Tp* __x, _Map_pointer __y) _GLIBCXX_NOEXCEPT + _Deque_iterator(_Elt_pointer __x, _Map_pointer __y) _GLIBCXX_NOEXCEPT : _M_cur(__x), _M_first(*__y), _M_last(*__y + _S_buffer_size()), _M_node(__y) { } _Deque_iterator() _GLIBCXX_NOEXCEPT - : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) { } + : _M_cur(), _M_first(), _M_last(), _M_node() { } _Deque_iterator(const iterator& __x) _GLIBCXX_NOEXCEPT : _M_cur(__x._M_cur), _M_first(__x._M_first), @@ -443,15 +457,33 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER template<typename _Tp, typename _Alloc> class _Deque_base { + protected: + typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template + rebind<_Tp>::other _Tp_alloc_type; + typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Alloc_traits; + +#if __cplusplus < 201103L + typedef _Tp* _Ptr; + typedef const _Tp* _Ptr_const; +#else + typedef typename _Alloc_traits::pointer _Ptr; + typedef typename _Alloc_traits::const_pointer _Ptr_const; +#endif + + typedef typename _Alloc_traits::template rebind<_Ptr>::other + _Map_alloc_type; + typedef __gnu_cxx::__alloc_traits<_Map_alloc_type> _Map_alloc_traits; + public: typedef _Alloc allocator_type; + typedef typename _Alloc_traits::size_type size_type; allocator_type get_allocator() const _GLIBCXX_NOEXCEPT { return allocator_type(_M_get_Tp_allocator()); } - typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator; - typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; + typedef _Deque_iterator<_Tp, _Tp&, _Ptr> iterator; + typedef _Deque_iterator<_Tp, const _Tp&, _Ptr_const> const_iterator; _Deque_base() : _M_impl() @@ -467,19 +499,43 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _Deque_base(const allocator_type& __a) : _M_impl(__a) - { } + { /* Caller must initialize map. */ } #if __cplusplus >= 201103L _Deque_base(_Deque_base&& __x) : _M_impl(std::move(__x._M_get_Tp_allocator())) { - _M_initialize_map(0); if (__x._M_impl._M_map) { - std::swap(this->_M_impl._M_start, __x._M_impl._M_start); - std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish); - std::swap(this->_M_impl._M_map, __x._M_impl._M_map); - std::swap(this->_M_impl._M_map_size, __x._M_impl._M_map_size); + this->_M_impl._M_swap_data(__x._M_impl); + __try + { + // Re-initialize __x using its moved-from allocator. + __x._M_initialize_map(0); + } + __catch (...) + { + this->_M_impl._M_swap_data(__x._M_impl); + __x._M_get_Tp_allocator() = std::move(_M_get_Tp_allocator()); + __throw_exception_again; + } + } + } + + _Deque_base(_Deque_base&& __x, const allocator_type& __a, size_type __n) + : _M_impl(__a) + { + if (__x.get_allocator() == __a) + { + if (__x._M_impl._M_map) + { + _M_initialize_map(0); + this->_M_impl._M_swap_data(__x._M_impl); + } + } + else + { + _M_initialize_map(__n); } } #endif @@ -487,9 +543,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER ~_Deque_base() _GLIBCXX_NOEXCEPT; protected: - typedef typename _Alloc::template rebind<_Tp*>::other _Map_alloc_type; - - typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type; + typedef typename iterator::_Map_pointer _Map_pointer; //This struct encapsulates the implementation of the std::deque //standard container and at the same time makes use of the EBO @@ -497,27 +551,35 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER struct _Deque_impl : public _Tp_alloc_type { - _Tp** _M_map; + _Map_pointer _M_map; size_t _M_map_size; iterator _M_start; iterator _M_finish; _Deque_impl() - : _Tp_alloc_type(), _M_map(0), _M_map_size(0), + : _Tp_alloc_type(), _M_map(), _M_map_size(0), _M_start(), _M_finish() { } _Deque_impl(const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT - : _Tp_alloc_type(__a), _M_map(0), _M_map_size(0), + : _Tp_alloc_type(__a), _M_map(), _M_map_size(0), _M_start(), _M_finish() { } #if __cplusplus >= 201103L _Deque_impl(_Tp_alloc_type&& __a) _GLIBCXX_NOEXCEPT - : _Tp_alloc_type(std::move(__a)), _M_map(0), _M_map_size(0), + : _Tp_alloc_type(std::move(__a)), _M_map(), _M_map_size(0), _M_start(), _M_finish() { } #endif + + void _M_swap_data(_Deque_impl& __x) + { + std::swap(this->_M_start, __x._M_start); + std::swap(this->_M_finish, __x._M_finish); + std::swap(this->_M_map, __x._M_map); + std::swap(this->_M_map_size, __x._M_map_size); + } }; _Tp_alloc_type& @@ -532,30 +594,39 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _M_get_map_allocator() const _GLIBCXX_NOEXCEPT { return _Map_alloc_type(_M_get_Tp_allocator()); } - _Tp* + _Ptr _M_allocate_node() { - return _M_impl._Tp_alloc_type::allocate(__deque_buf_size(sizeof(_Tp))); + typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Traits; + return _Traits::allocate(_M_impl, __deque_buf_size(sizeof(_Tp))); } void - _M_deallocate_node(_Tp* __p) _GLIBCXX_NOEXCEPT + _M_deallocate_node(_Ptr __p) _GLIBCXX_NOEXCEPT { - _M_impl._Tp_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp))); + typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Traits; + _Traits::deallocate(_M_impl, __p, __deque_buf_size(sizeof(_Tp))); } - _Tp** + _Map_pointer _M_allocate_map(size_t __n) - { return _M_get_map_allocator().allocate(__n); } + { + _Map_alloc_type __map_alloc = _M_get_map_allocator(); + return _Map_alloc_traits::allocate(__map_alloc, __n); + } void - _M_deallocate_map(_Tp** __p, size_t __n) _GLIBCXX_NOEXCEPT - { _M_get_map_allocator().deallocate(__p, __n); } + _M_deallocate_map(_Map_pointer __p, size_t __n) _GLIBCXX_NOEXCEPT + { + _Map_alloc_type __map_alloc = _M_get_map_allocator(); + _Map_alloc_traits::deallocate(__map_alloc, __p, __n); + } protected: void _M_initialize_map(size_t); - void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish); - void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish) _GLIBCXX_NOEXCEPT; + void _M_create_nodes(_Map_pointer __nstart, _Map_pointer __nfinish); + void _M_destroy_nodes(_Map_pointer __nstart, + _Map_pointer __nfinish) _GLIBCXX_NOEXCEPT; enum { _S_initial_map_size = 8 }; _Deque_impl _M_impl; @@ -576,7 +647,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER /** * @brief Layout storage. * @param __num_elements The count of T's for which to allocate space - * at first. + * at first. * @return Nothing. * * The initial underlying memory layout is a bit complicated... @@ -598,16 +669,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER // the beginning of _M_map, but for small maps it may be as far in as // _M_map+3. - _Tp** __nstart = (this->_M_impl._M_map - + (this->_M_impl._M_map_size - __num_nodes) / 2); - _Tp** __nfinish = __nstart + __num_nodes; + _Map_pointer __nstart = (this->_M_impl._M_map + + (this->_M_impl._M_map_size - __num_nodes) / 2); + _Map_pointer __nfinish = __nstart + __num_nodes; __try { _M_create_nodes(__nstart, __nfinish); } __catch(...) { _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size); - this->_M_impl._M_map = 0; + this->_M_impl._M_map = _Map_pointer(); this->_M_impl._M_map_size = 0; __throw_exception_again; } @@ -623,9 +694,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER template<typename _Tp, typename _Alloc> void _Deque_base<_Tp, _Alloc>:: - _M_create_nodes(_Tp** __nstart, _Tp** __nfinish) + _M_create_nodes(_Map_pointer __nstart, _Map_pointer __nfinish) { - _Tp** __cur; + _Map_pointer __cur; __try { for (__cur = __nstart; __cur < __nfinish; ++__cur) @@ -641,9 +712,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER template<typename _Tp, typename _Alloc> void _Deque_base<_Tp, _Alloc>:: - _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish) _GLIBCXX_NOEXCEPT + _M_destroy_nodes(_Map_pointer __nstart, + _Map_pointer __nfinish) _GLIBCXX_NOEXCEPT { - for (_Tp** __n = __nstart; __n < __nfinish; ++__n) + for (_Map_pointer __n = __nstart; __n < __nfinish; ++__n) _M_deallocate_node(*__n); } @@ -739,15 +811,17 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER __glibcxx_class_requires(_Tp, _SGIAssignableConcept) __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept) - typedef _Deque_base<_Tp, _Alloc> _Base; - typedef typename _Base::_Tp_alloc_type _Tp_alloc_type; + typedef _Deque_base<_Tp, _Alloc> _Base; + typedef typename _Base::_Tp_alloc_type _Tp_alloc_type; + typedef typename _Base::_Alloc_traits _Alloc_traits; + typedef typename _Base::_Map_pointer _Map_pointer; 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 typename _Alloc_traits::pointer pointer; + typedef typename _Alloc_traits::const_pointer const_pointer; + typedef typename _Alloc_traits::reference reference; + typedef typename _Alloc_traits::const_reference const_reference; typedef typename _Base::iterator iterator; typedef typename _Base::const_iterator const_iterator; typedef std::reverse_iterator<const_iterator> const_reverse_iterator; @@ -757,8 +831,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER typedef _Alloc allocator_type; protected: - typedef pointer* _Map_pointer; - static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT { return __deque_buf_size(sizeof(_Tp)); } @@ -804,8 +876,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * constructed elements. */ explicit - deque(size_type __n) - : _Base(__n) + deque(size_type __n, const allocator_type& __a = allocator_type()) + : _Base(__a, __n) { _M_default_initialize(); } /** @@ -844,7 +916,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * by @a __x. */ deque(const deque& __x) - : _Base(__x._M_get_Tp_allocator(), __x.size()) + : _Base(_Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator()), + __x.size()) { std::__uninitialized_copy_a(__x.begin(), __x.end(), this->_M_impl._M_start, _M_get_Tp_allocator()); } @@ -860,6 +933,26 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER deque(deque&& __x) : _Base(std::move(__x)) { } + /// Copy constructor with alternative allocator + deque(const deque& __x, const allocator_type& __a) + : _Base(__a, __x.size()) + { std::__uninitialized_copy_a(__x.begin(), __x.end(), + this->_M_impl._M_start, + _M_get_Tp_allocator()); } + + /// Move constructor with alternative allocator + deque(deque&& __x, const allocator_type& __a) + : _Base(std::move(__x), __a, __x.size()) + { + if (__x.get_allocator() != __a) + { + std::__uninitialized_move_a(__x.begin(), __x.end(), + this->_M_impl._M_start, + _M_get_Tp_allocator()); + __x.clear(); + } + } + /** * @brief Builds a %deque from an initializer list. * @param __l An initializer_list. @@ -919,7 +1012,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * themselves are pointers, the pointed-to memory is not touched in any * way. Managing the pointer is the user's responsibility. */ - ~deque() _GLIBCXX_NOEXCEPT + ~deque() { _M_destroy_data(begin(), end(), _M_get_Tp_allocator()); } /** @@ -937,16 +1030,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * @brief %Deque move assignment operator. * @param __x A %deque of identical element and allocator types. * - * The contents of @a __x are moved into this deque (without copying). + * The contents of @a __x are moved into this deque (without copying, + * if the allocators permit it). * @a __x is a valid, but unspecified %deque. */ deque& - operator=(deque&& __x) noexcept + operator=(deque&& __x) noexcept(_Alloc_traits::_S_always_equal()) { - // NB: DR 1204. - // NB: DR 675. - this->clear(); - this->swap(__x); + constexpr bool __always_equal = _Alloc_traits::_S_always_equal(); + _M_move_assign1(std::move(__x), + integral_constant<bool, __always_equal>()); return *this; } @@ -1150,7 +1243,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER /** Returns the size() of the largest possible %deque. */ size_type max_size() const _GLIBCXX_NOEXCEPT - { return _M_get_Tp_allocator().max_size(); } + { return _Alloc_traits::max_size(_M_get_Tp_allocator()); } #if __cplusplus >= 201103L /** @@ -1368,7 +1461,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first) { - this->_M_impl.construct(this->_M_impl._M_start._M_cur - 1, __x); + _Alloc_traits::construct(this->_M_impl, + this->_M_impl._M_start._M_cur - 1, + __x); --this->_M_impl._M_start._M_cur; } else @@ -1400,7 +1495,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER if (this->_M_impl._M_finish._M_cur != this->_M_impl._M_finish._M_last - 1) { - this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __x); + _Alloc_traits::construct(this->_M_impl, + this->_M_impl._M_finish._M_cur, __x); ++this->_M_impl._M_finish._M_cur; } else @@ -1431,7 +1527,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_last - 1) { - this->_M_impl.destroy(this->_M_impl._M_start._M_cur); + _Alloc_traits::destroy(this->_M_impl, + this->_M_impl._M_start._M_cur); ++this->_M_impl._M_start._M_cur; } else @@ -1453,7 +1550,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER != this->_M_impl._M_finish._M_first) { --this->_M_impl._M_finish._M_cur; - this->_M_impl.destroy(this->_M_impl._M_finish._M_cur); + _Alloc_traits::destroy(this->_M_impl, + this->_M_impl._M_finish._M_cur); } else _M_pop_back_aux(); @@ -1659,17 +1757,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * std::swap(d1,d2) will feed to this function. */ void - swap(deque& __x) _GLIBCXX_NOEXCEPT + swap(deque& __x) +#if __cplusplus >= 201103L + noexcept(_Alloc_traits::_S_nothrow_swap()) +#endif { - std::swap(this->_M_impl._M_start, __x._M_impl._M_start); - std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish); - std::swap(this->_M_impl._M_map, __x._M_impl._M_map); - std::swap(this->_M_impl._M_map_size, __x._M_impl._M_map_size); - - // _GLIBCXX_RESOLVE_LIB_DEFECTS - // 431. Swapping containers with unequal allocators. - std::__alloc_swap<_Tp_alloc_type>::_S_do_it(_M_get_Tp_allocator(), - __x._M_get_Tp_allocator()); + _M_impl._M_swap_data(__x._M_impl); + _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(), + __x._M_get_Tp_allocator()); } /** @@ -2011,6 +2106,79 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front); //@} + +#if __cplusplus >= 201103L + // Constant-time, nothrow move assignment when source object's memory + // can be moved because the allocators are equal. + void + _M_move_assign1(deque&& __x, /* always equal: */ true_type) noexcept + { + this->_M_impl._M_swap_data(__x._M_impl); + __x.clear(); + std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator()); + } + + void + _M_move_assign1(deque&& __x, /* always equal: */ false_type) + { + constexpr bool __move_storage = + _Alloc_traits::_S_propagate_on_move_assign(); + _M_move_assign2(std::move(__x), + integral_constant<bool, __move_storage>()); + } + + // Destroy all elements and deallocate all memory, then replace + // with elements created from __args. + template<typename... _Args> + void + _M_replace_map(_Args&&... __args) + { + // Create new data first, so if allocation fails there are no effects. + deque __newobj(std::forward<_Args>(__args)...); + // Free existing storage using existing allocator. + clear(); + _M_deallocate_node(*begin()._M_node); // one node left after clear() + _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size); + this->_M_impl._M_map = nullptr; + this->_M_impl._M_map_size = 0; + // Take ownership of replacement memory. + this->_M_impl._M_swap_data(__newobj._M_impl); + } + + // Do move assignment when the allocator propagates. + void + _M_move_assign2(deque&& __x, /* propagate: */ true_type) + { + // Make a copy of the original allocator state. + auto __alloc = __x._M_get_Tp_allocator(); + // The allocator propagates so storage can be moved from __x, + // leaving __x in a valid empty state with a moved-from allocator. + _M_replace_map(std::move(__x)); + // Move the corresponding allocator state too. + _M_get_Tp_allocator() = std::move(__alloc); + } + + // Do move assignment when it may not be possible to move source + // object's memory, resulting in a linear-time operation. + void + _M_move_assign2(deque&& __x, /* propagate: */ false_type) + { + if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator()) + { + // The allocators are equal so storage can be moved from __x, + // leaving __x in a valid empty state with its current allocator. + _M_replace_map(std::move(__x), __x.get_allocator()); + } + else + { + // The rvalue's allocator cannot be moved and is not equal, + // so we need to individually move each element. + this->assign(std::__make_move_if_noexcept_iterator(__x.begin()), + std::__make_move_if_noexcept_iterator(__x.end())); + __x.clear(); + } + } +#endif }; |