Deque code cleanup and optimizations

Message ID a791fb74-878a-5e02-dbcb-d0c8bc0f8970@gmail.com
State New
Headers show
Series
  • Deque code cleanup and optimizations
Related show

Commit Message

François Dumont May 10, 2019, 4:58 a.m.
Hi

     This patch implements a number of simplifications and optimizations 
already done to other containers like std::vector

- Default default and move constructors

- The std::swap optimization

- The construction always equal allocator optimization

- Shortcuts on method calls.

     I remove several _M_map != nullptr checks cause in current 
implementation it can't be null. I have several patches following this 
one to support it but in this case we will be using a different code path.

     Now that we take shortcuts in several methods in C++11 there are 
some that are simply unused in C++11 mode. For the moment I kept them as 
long as we are not in versioned namespace scope in order to maintain abi 
compatibility, I wonder if I really need to consider abi 
backward-compatibility here ?

     * include/bits/stl_deque.h (_Deque_base(_Deque_base&&, false_type)):
     Make private.
     (_Deque_base(_Deque_base&&, true_type)): Likewise. Remove _M_map check.
     (_Deque_base(_Deque_base&&, const allocator_type&)): New.
     (_Deque_base(_Deque_base&&, const allocator_type&, size_t)): Remove
     _M_map check.
     (_Deque_base::_Deque_impl_data): New.
     (_Deque_base::_Deque_impl): Inherit latter.
     (_Deque_base::_Deque_impl::_M_swap_data): Move...
     (_Deque_base::_Deque_impl_data::_M_swap_data): ... here.
     (_Deque_base::_Deque_impl()): Add noexcept qualification.
     (_Deque_base::_Deque_impl(_Deque_impl&&, _Tp_alloc_type&&)): New.
     (_Deque_base::_Deque_impl::_M_get_Tp_allocator()): Remove static_cast.
     (_Deque_base::_Deque_impl::_M_move_impl()): Remove _M_impl._M_map 
check.
     (deque<>::deque()): Default.
     (deque<>::deque(deque&&)): Default.
     (deque<>::deque(deque&&, const allocator_type&, false_type)): New.
     (deque<>::deque(deque&&, const allocator_type&, true_type)): New.
     (deque<>::deque(deque&&, const allocator_type&)): Delegate to latters.
     (deque<>::deque<_It>(_It, _It, const allocator_type&)): Use
     _M_range_initialize.
     (deque<>::assign<_It>(_It, _It)): Use _M_assign_aux.
     (deque<>::resize(size_type, const value_type&)): Share a single
     implementation.
     (deque<>::insert<_It>(const_iterator, _It, _It)): Use
     _M_range_insert_aux.
     [__cplusplus >= 201103L && 
_GLIBCXX_INLINE_VERSION](_M_initialize_dispatch):
     Remove.
     [__cplusplus >= 201103L && 
_GLIBCXX_INLINE_VERSION](_M_assign_dispatch):
     Remove.
     [__cplusplus >= 201103L && 
_GLIBCXX_INLINE_VERSION](_M_insert_dispatch):
     Remove.
     * testsuite/23_containers/deque/allocator/default_init.cc: New.

Tested under Linux x86_64 normal and debug modes.

Ok to commit ?

François

Comments

Jonathan Wakely May 10, 2019, 1:38 p.m. | #1
This seems generally OK, but ...

On Fri, 10 May 2019, 05:59 François Dumont wrote:
>      I remove several _M_map != nullptr checks cause in current

> implementation it can't be null. I have several patches following this

> one to support it but in this case we will be using a different code path.



You can't remove those checks. If _M_map can ever be null now or in
the future, then we need the checks. Otherwise code compiled today
would break if passed a deque compiled with a future GCC that allows
the map to be null.

I'm curious how you plan to support it though, I don't think it's
possible without an ABI break.

>      (_Deque_base::_Deque_impl::_M_move_impl()): Remove _M_impl._M_map

> check.


_M_move_impl and the constructor that calls it can be removed
completely, because https://cplusplus.github.io/LWG/issue2593 means
that the same allocator can still be used after moving from it. That
function only exists to handle the case where an allocator changes
value after being moved from.
François Dumont May 14, 2019, 5:49 a.m. | #2
On 5/10/19 3:38 PM, Jonathan Wakely wrote:
> This seems generally OK, but ...

>

> On Fri, 10 May 2019, 05:59 François Dumont wrote:

>>       I remove several _M_map != nullptr checks cause in current

>> implementation it can't be null. I have several patches following this

>> one to support it but in this case we will be using a different code path.

>

> You can't remove those checks. If _M_map can ever be null now or in

> the future, then we need the checks. Otherwise code compiled today

> would break if passed a deque compiled with a future GCC that allows

> the map to be null.

>

> I'm curious how you plan to support it though, I don't think it's

> possible without an ABI break.


No miracle, I plan to propose it only in versioned namespace mode, it 
does break ABI.

But in this implementation those current checks are useless, I'll double 
check.

>

>>       (_Deque_base::_Deque_impl::_M_move_impl()): Remove _M_impl._M_map

>> check.

> _M_move_impl and the constructor that calls it can be removed

> completely, because https://cplusplus.github.io/LWG/issue2593 means

> that the same allocator can still be used after moving from it. That

> function only exists to handle the case where an allocator changes

> value after being moved from.

>

Good, I'll cleanup that and propose a new patch.

François
François Dumont May 17, 2019, 5:06 a.m. | #3
Here is the simplified patch. I put back the _M_map checks, we'll see 
later if those can be removed.

     * include/bits/stl_deque.h
     (_Deque_iterator<>::__ptr_to): Remove, use std::__ptr_rebind.
     (_Deque_base(_Deque_base&&, const allocator_type&)): New.
     (_Deque_base::_Deque_impl_data): New.
     (_Deque_base::_Deque_impl): Inherit latter.
     (_Deque_base::_Deque_impl::_M_swap_data): Move...
     (_Deque_base::_Deque_impl_data::_M_swap_data): ... here.
     (_Deque_base::_Deque_impl()): Add noexcept qualification.
     (_Deque_base::_Deque_impl(_Deque_impl&&, _Tp_alloc_type&&)): New.
     (_Deque_base::_Deque_impl::_M_get_Tp_allocator()): Remove static_cast.
     (deque<>::deque()): Default.
     (deque<>::deque(deque&&)): Default.
     (deque<>::deque(deque&&, const allocator_type&, false_type)): New.
     (deque<>::deque(deque&&, const allocator_type&, true_type)): New.
     (deque<>::deque(deque&&, const allocator_type&)): Delegate to latters.
     (deque<>::deque<_It>(_It, _It, const allocator_type&)): Use
     _M_range_initialize.
     (deque<>::assign<_It>(_It, _It)): Use _M_assign_aux.
     (deque<>::resize(size_type, const value_type&)): Share a single
     implementation.
     (deque<>::insert<_It>(const_iterator, _It, _It)): Use
     _M_range_insert_aux.
     [__cplusplus >= 201103L](_M_initialize_dispatch): Remove.
     [__cplusplus >= 201103L](_M_assign_dispatch): Remove.
     [__cplusplus >= 201103L](_M_insert_dispatch): Remove.
     * testsuite/23_containers/deque/allocator/default_init.cc: New.

Tested under Linux x86_64.

Ok to commit ?

François

On 5/10/19 3:38 PM, Jonathan Wakely wrote:
> This seems generally OK, but ...

>

> On Fri, 10 May 2019, 05:59 François Dumont wrote:

>>       I remove several _M_map != nullptr checks cause in current

>> implementation it can't be null. I have several patches following this

>> one to support it but in this case we will be using a different code path.

>

> You can't remove those checks. If _M_map can ever be null now or in

> the future, then we need the checks. Otherwise code compiled today

> would break if passed a deque compiled with a future GCC that allows

> the map to be null.

>

> I'm curious how you plan to support it though, I don't think it's

> possible without an ABI break.

>

>>       (_Deque_base::_Deque_impl::_M_move_impl()): Remove _M_impl._M_map

>> check.

> _M_move_impl and the constructor that calls it can be removed

> completely, because https://cplusplus.github.io/LWG/issue2593 means

> that the same allocator can still be used after moving from it. That

> function only exists to handle the case where an allocator changes

> value after being moved from.

>
diff --git a/libstdc++-v3/include/bits/stl_deque.h b/libstdc++-v3/include/bits/stl_deque.h
index 358bbda3902..22a7ac8da2e 100644
--- a/libstdc++-v3/include/bits/stl_deque.h
+++ b/libstdc++-v3/include/bits/stl_deque.h
@@ -115,15 +115,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       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>>;
+	using __iter = _Deque_iterator<_Tp, _CvTp&, __ptr_rebind<_Ptr, _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;
+      typedef __ptr_rebind<_Ptr, _Tp>			   _Elt_pointer;
+      typedef __ptr_rebind<_Ptr, _Elt_pointer>		   _Map_pointer;
 #endif
 
       static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT
@@ -401,7 +399,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	_Map_alloc_type;
       typedef __gnu_cxx::__alloc_traits<_Map_alloc_type> _Map_alloc_traits;
 
-    public:
       typedef _Alloc		  allocator_type;
 
       allocator_type
@@ -436,6 +433,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  this->_M_impl._M_swap_data(__x._M_impl);
       }
 
+      _Deque_base(_Deque_base&& __x, const allocator_type& __a)
+      : _M_impl(std::move(__x._M_impl), _Tp_alloc_type(__a))
+      { __x._M_initialize_map(0); }
+
       _Deque_base(_Deque_base&& __x, const allocator_type& __a, size_t __n)
       : _M_impl(__a)
       {
@@ -456,56 +457,73 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       ~_Deque_base() _GLIBCXX_NOEXCEPT;
 
-    protected:
       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
-      //for empty allocators.
-      struct _Deque_impl
-      : public _Tp_alloc_type
+      struct _Deque_impl_data
       {
 	_Map_pointer _M_map;
 	size_t _M_map_size;
 	iterator _M_start;
 	iterator _M_finish;
 
-	_Deque_impl()
-	: _Tp_alloc_type(), _M_map(), _M_map_size(0),
-	  _M_start(), _M_finish()
+	_Deque_impl_data() _GLIBCXX_NOEXCEPT
+	: _M_map(), _M_map_size(), _M_start(), _M_finish()
+	{ }
+
+#if __cplusplus >= 201103L
+	_Deque_impl_data(const _Deque_impl_data&) = default;
+	_Deque_impl_data&
+	operator=(const _Deque_impl_data&) = default;
+
+	_Deque_impl_data(_Deque_impl_data&& __x) noexcept
+	: _Deque_impl_data(__x)
+	{ __x = _Deque_impl_data(); }
+#endif
+
+	void
+	_M_swap_data(_Deque_impl_data& __x) _GLIBCXX_NOEXCEPT
+	{
+	  // Do not use std::swap(_M_start, __x._M_start), etc as it loses
+	  // information used by TBAA.
+	  std::swap(*this, __x);
+	}
+      };
+
+      // This struct encapsulates the implementation of the std::deque
+      // standard container and at the same time makes use of the EBO
+      // for empty allocators.
+      struct _Deque_impl
+      : public _Tp_alloc_type, public _Deque_impl_data
+      {
+	_Deque_impl() _GLIBCXX_NOEXCEPT_IF(
+	  is_nothrow_default_constructible<_Tp_alloc_type>::value)
+	: _Tp_alloc_type()
 	{ }
 
 	_Deque_impl(const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
-	: _Tp_alloc_type(__a), _M_map(), _M_map_size(0),
-	  _M_start(), _M_finish()
+	: _Tp_alloc_type(__a)
 	{ }
 
 #if __cplusplus >= 201103L
 	_Deque_impl(_Deque_impl&&) = default;
 
 	_Deque_impl(_Tp_alloc_type&& __a) noexcept
-	: _Tp_alloc_type(std::move(__a)), _M_map(), _M_map_size(0),
-	  _M_start(), _M_finish()
+	: _Tp_alloc_type(std::move(__a))
 	{ }
-#endif
 
-	void _M_swap_data(_Deque_impl& __x) _GLIBCXX_NOEXCEPT
-	{
-	  using std::swap;
-	  swap(this->_M_start, __x._M_start);
-	  swap(this->_M_finish, __x._M_finish);
-	  swap(this->_M_map, __x._M_map);
-	  swap(this->_M_map_size, __x._M_map_size);
-	}
+	_Deque_impl(_Deque_impl&& __d, _Tp_alloc_type&& __a)
+	: _Tp_alloc_type(std::move(__a)), _Deque_impl_data(std::move(__d))
+	{ }
+#endif
       };
 
       _Tp_alloc_type&
       _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
-      { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); }
+      { return this->_M_impl; }
 
       const _Tp_alloc_type&
       _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT
-      { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); }
+      { return this->_M_impl; }
 
       _Map_alloc_type
       _M_get_map_allocator() const _GLIBCXX_NOEXCEPT
@@ -539,7 +557,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	_Map_alloc_traits::deallocate(__map_alloc, __p, __n);
       }
 
-    protected:
       void _M_initialize_map(size_t);
       void _M_create_nodes(_Map_pointer __nstart, _Map_pointer __nfinish);
       void _M_destroy_nodes(_Map_pointer __nstart,
@@ -760,7 +777,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       typedef ptrdiff_t					difference_type;
       typedef _Alloc					allocator_type;
 
-    protected:
+    private:
       static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT
       { return __deque_buf_size(sizeof(_Tp)); }
 
@@ -787,7 +804,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       /**
        *  @brief  Creates a %deque with no elements.
        */
-      deque() : _Base() { }
+#if __cplusplus >= 201103L
+      deque() = default;
+#else
+      deque() { }
+#endif
 
       /**
        *  @brief  Creates a %deque with no elements.
@@ -856,13 +877,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #if __cplusplus >= 201103L
       /**
        *  @brief  %Deque move constructor.
-       *  @param  __x  A %deque of identical element and allocator types.
        *
-       *  The newly-created %deque contains the exact contents of @a __x.
-       *  The contents of @a __x are a valid, but unspecified %deque.
+       *  The newly-created %deque contains the exact contents of the
+       *  moved instance.
+       *  The contents of the moved instance are a valid, but unspecified
+       *  %deque.
        */
-      deque(deque&& __x)
-      : _Base(std::move(__x)) { }
+      deque(deque&&) = default;
 
       /// Copy constructor with alternative allocator
       deque(const deque& __x, const allocator_type& __a)
@@ -873,9 +894,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /// Move constructor with alternative allocator
       deque(deque&& __x, const allocator_type& __a)
+      : deque(std::move(__x), __a, typename _Alloc_traits::is_always_equal{})
+      { }
+
+    private:
+      deque(deque&& __x, const allocator_type& __a, true_type)
+      : _Base(std::move(__x), __a)
+      { }
+
+      deque(deque&& __x, const allocator_type& __a, false_type)
       : _Base(std::move(__x), __a, __x.size())
       {
-	if (__x.get_allocator() != __a)
+	if (__x.get_allocator() != __a && !__x.empty())
 	  {
 	    std::__uninitialized_move_a(__x.begin(), __x.end(),
 					this->_M_impl._M_start,
@@ -884,6 +914,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  }
       }
 
+    public:
       /**
        *  @brief  Builds a %deque from an initializer list.
        *  @param  __l  An initializer_list.
@@ -925,7 +956,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	deque(_InputIterator __first, _InputIterator __last,
 	      const allocator_type& __a = allocator_type())
 	: _Base(__a)
-	{ _M_initialize_dispatch(__first, __last, __false_type()); }
+	{
+	  _M_range_initialize(__first, __last,
+			      std::__iterator_category(__first));
+	}
 #else
       template<typename _InputIterator>
 	deque(_InputIterator __first, _InputIterator __last,
@@ -1026,7 +1060,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	       typename = std::_RequireInputIter<_InputIterator>>
 	void
 	assign(_InputIterator __first, _InputIterator __last)
-	{ _M_assign_dispatch(__first, __last, __false_type()); }
+	{ _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
 #else
       template<typename _InputIterator>
 	void
@@ -1212,14 +1246,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       void
       resize(size_type __new_size, const value_type& __x)
-      {
-	const size_type __len = size();
-	if (__new_size > __len)
-	  _M_fill_insert(this->_M_impl._M_finish, __new_size - __len, __x);
-	else if (__new_size < __len)
-	  _M_erase_at_end(this->_M_impl._M_start
-			  + difference_type(__new_size));
-      }
 #else
       /**
        *  @brief  Resizes the %deque to the specified number of elements.
@@ -1234,6 +1260,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       void
       resize(size_type __new_size, value_type __x = value_type())
+#endif
       {
 	const size_type __len = size();
 	if (__new_size > __len)
@@ -1242,7 +1269,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  _M_erase_at_end(this->_M_impl._M_start
 			  + difference_type(__new_size));
       }
-#endif
 
 #if __cplusplus >= 201103L
       /**  A non-binding request to reduce memory use.  */
@@ -1483,7 +1509,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	if (this->_M_impl._M_start._M_cur
 	    != this->_M_impl._M_start._M_last - 1)
 	  {
-	    _Alloc_traits::destroy(this->_M_impl,
+	    _Alloc_traits::destroy(_M_get_Tp_allocator(),
 				   this->_M_impl._M_start._M_cur);
 	    ++this->_M_impl._M_start._M_cur;
 	  }
@@ -1507,7 +1533,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	    != this->_M_impl._M_finish._M_first)
 	  {
 	    --this->_M_impl._M_finish._M_cur;
-	    _Alloc_traits::destroy(this->_M_impl,
+	    _Alloc_traits::destroy(_M_get_Tp_allocator(),
 				   this->_M_impl._M_finish._M_cur);
 	  }
 	else
@@ -1571,6 +1597,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        *  @brief  Inserts an initializer list into the %deque.
        *  @param  __p  An iterator into the %deque.
        *  @param  __l  An initializer_list.
+       *  @return  An iterator that points to the inserted data.
        *
        *  This function will insert copies of the data in the
        *  initializer_list @a __l into the %deque before the location
@@ -1584,9 +1611,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 			    std::random_access_iterator_tag());
 	return begin() + __offset;
       }
-#endif
 
-#if __cplusplus >= 201103L
       /**
        *  @brief  Inserts a number of copies of given data into the %deque.
        *  @param  __position  A const_iterator into the %deque.
@@ -1638,8 +1663,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	       _InputIterator __last)
 	{
 	  difference_type __offset = __position - cbegin();
-	  _M_insert_dispatch(__position._M_const_cast(),
-			     __first, __last, __false_type());
+	  _M_range_insert_aux(__position._M_const_cast(), __first, __last,
+			      std::__iterator_category(__first));
 	  return begin() + __offset;
 	}
 #else
@@ -1745,6 +1770,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     protected:
       // Internal constructor functions follow.
 
+#if __cplusplus < 201103L
       // called by the range constructor to implement [23.1.1]/9
 
       // _GLIBCXX_RESOLVE_LIB_DEFECTS
@@ -1758,6 +1784,17 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  _M_fill_initialize(__x);
 	}
 
+      // called by the range constructor to implement [23.1.1]/9
+      template<typename _InputIterator>
+	void
+	_M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
+			       __false_type)
+	{
+	  _M_range_initialize(__first, __last,
+			      std::__iterator_category(__first));
+	}
+#endif
+
       static size_t
       _S_check_init_len(size_t __n, const allocator_type& __a)
       {
@@ -1775,16 +1812,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	return (std::min)(__diffmax, __allocmax);
       }
 
-      // called by the range constructor to implement [23.1.1]/9
-      template<typename _InputIterator>
-	void
-	_M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
-			       __false_type)
-	{
-	  _M_range_initialize(__first, __last,
-			      std::__iterator_category(__first));
-	}
-
       // called by the second initialize_dispatch above
       //@{
       /**
@@ -1831,6 +1858,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       // Internal assign functions follow.  The *_aux functions do the actual
       // assignment work for the range versions.
 
+#if __cplusplus < 201103L
       // called by the range assign to implement [23.1.1]/9
 
       // _GLIBCXX_RESOLVE_LIB_DEFECTS
@@ -1846,6 +1874,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	_M_assign_dispatch(_InputIterator __first, _InputIterator __last,
 			   __false_type)
 	{ _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
+#endif
 
       // called by the second assign_dispatch above
       template<typename _InputIterator>
@@ -1911,6 +1940,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       // Internal insert functions follow.  The *_aux functions do the actual
       // insertion work when all shortcuts fail.
 
+#if __cplusplus < 201103L
       // called by the range insert to implement [23.1.1]/9
 
       // _GLIBCXX_RESOLVE_LIB_DEFECTS
@@ -1931,6 +1961,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  _M_range_insert_aux(__pos, __first, __last,
 			      std::__iterator_category(__first));
 	}
+#endif
 
       // called by the second insert_dispatch above
       template<typename _InputIterator>
diff --git a/libstdc++-v3/testsuite/23_containers/deque/allocator/default_init.cc b/libstdc++-v3/testsuite/23_containers/deque/allocator/default_init.cc
new file mode 100644
index 00000000000..f6cc61e1fb8
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/allocator/default_init.cc
@@ -0,0 +1,67 @@
+// Copyright (C) 2019 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do run { target c++11 } }
+// { dg-options "-O0" }
+// { dg-xfail-run-if "PR c++/65816" { *-*-* } }
+
+#include <deque>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+#include <ext/aligned_buffer.h>
+
+using T = int;
+
+using __gnu_test::default_init_allocator;
+
+void test01()
+{
+  typedef default_init_allocator<T> alloc_type;
+  typedef std::deque<T, alloc_type> test_type;
+
+  __gnu_cxx::__aligned_buffer<test_type> buf;
+  __builtin_memset(buf._M_addr(), ~0, sizeof(test_type));
+
+  test_type *tmp = ::new(buf._M_addr()) test_type;
+
+  VERIFY( tmp->get_allocator().state == 0 );
+
+  tmp->~test_type();
+}
+
+void test02()
+{
+  typedef default_init_allocator<T> alloc_type;
+  typedef std::deque<T, alloc_type> test_type;
+
+  __gnu_cxx::__aligned_buffer<test_type> buf;
+  __builtin_memset(buf._M_addr(), ~0, sizeof(test_type));
+
+  test_type *tmp = ::new(buf._M_addr()) test_type();
+
+  VERIFY( tmp->get_allocator().state == 0 );
+
+  tmp->~test_type();
+}
+
+int main()
+{
+  test01();
+  test02();
+  return 0;
+}
Jonathan Wakely May 17, 2019, 12:40 p.m. | #4
On 17/05/19 07:06 +0200, François Dumont wrote:
>Here is the simplified patch. I put back the _M_map checks, we'll see 

>later if those can be removed.

>

>    * include/bits/stl_deque.h

>    (_Deque_iterator<>::__ptr_to): Remove, use std::__ptr_rebind.

>    (_Deque_base(_Deque_base&&, const allocator_type&)): New.

>    (_Deque_base::_Deque_impl_data): New.

>    (_Deque_base::_Deque_impl): Inherit latter.

>    (_Deque_base::_Deque_impl::_M_swap_data): Move...

>    (_Deque_base::_Deque_impl_data::_M_swap_data): ... here.

>    (_Deque_base::_Deque_impl()): Add noexcept qualification.

>    (_Deque_base::_Deque_impl(_Deque_impl&&, _Tp_alloc_type&&)): New.

>    (_Deque_base::_Deque_impl::_M_get_Tp_allocator()): Remove static_cast.

>    (deque<>::deque()): Default.

>    (deque<>::deque(deque&&)): Default.

>    (deque<>::deque(deque&&, const allocator_type&, false_type)): New.

>    (deque<>::deque(deque&&, const allocator_type&, true_type)): New.

>    (deque<>::deque(deque&&, const allocator_type&)): Delegate to latters.

>    (deque<>::deque<_It>(_It, _It, const allocator_type&)): Use

>    _M_range_initialize.

>    (deque<>::assign<_It>(_It, _It)): Use _M_assign_aux.

>    (deque<>::resize(size_type, const value_type&)): Share a single

>    implementation.

>    (deque<>::insert<_It>(const_iterator, _It, _It)): Use

>    _M_range_insert_aux.

>    [__cplusplus >= 201103L](_M_initialize_dispatch): Remove.

>    [__cplusplus >= 201103L](_M_assign_dispatch): Remove.

>    [__cplusplus >= 201103L](_M_insert_dispatch): Remove.

>    * testsuite/23_containers/deque/allocator/default_init.cc: New.

>

>Tested under Linux x86_64.

>

>Ok to commit ?


OK for trunk, thanks.

Patch

diff --git a/libstdc++-v3/include/bits/stl_deque.h b/libstdc++-v3/include/bits/stl_deque.h
index c050d1bf023..92c34207baa 100644
--- a/libstdc++-v3/include/bits/stl_deque.h
+++ b/libstdc++-v3/include/bits/stl_deque.h
@@ -401,7 +401,6 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	_Map_alloc_type;
       typedef __gnu_cxx::__alloc_traits<_Map_alloc_type> _Map_alloc_traits;
 
-    public:
       typedef _Alloc		  allocator_type;
 
       allocator_type
@@ -428,6 +427,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       { /* Caller must initialize map. */ }
 
 #if __cplusplus >= 201103L
+    private:
       _Deque_base(_Deque_base&& __x, false_type)
       : _M_impl(__x._M_move_impl())
       { }
@@ -436,84 +436,100 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       : _M_impl(std::move(__x._M_get_Tp_allocator()))
       {
 	_M_initialize_map(0);
-	if (__x._M_impl._M_map)
 	this->_M_impl._M_swap_data(__x._M_impl);
       }
 
+    protected:
       _Deque_base(_Deque_base&& __x)
       : _Deque_base(std::move(__x), typename _Alloc_traits::is_always_equal{})
       { }
 
+      _Deque_base(_Deque_base&& __x, const allocator_type& __a)
+      : _M_impl(std::move(__x._M_impl), _Tp_alloc_type(__a))
+      { __x._M_initialize_map(0); }
+
       _Deque_base(_Deque_base&& __x, const allocator_type& __a, size_t __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
 
       ~_Deque_base() _GLIBCXX_NOEXCEPT;
 
-    protected:
       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
-      //for empty allocators.
-      struct _Deque_impl
-      : public _Tp_alloc_type
+      struct _Deque_impl_data
       {
 	_Map_pointer _M_map;
 	size_t _M_map_size;
 	iterator _M_start;
 	iterator _M_finish;
 
-	_Deque_impl()
-	: _Tp_alloc_type(), _M_map(), _M_map_size(0),
-	  _M_start(), _M_finish()
+	_Deque_impl_data() _GLIBCXX_NOEXCEPT
+	: _M_map(), _M_map_size(), _M_start(), _M_finish()
+	{ }
+
+#if __cplusplus >= 201103L
+	_Deque_impl_data(const _Deque_impl_data&) = default;
+	_Deque_impl_data&
+	operator=(const _Deque_impl_data&) = default;
+
+	_Deque_impl_data(_Deque_impl_data&& __x) noexcept
+	: _Deque_impl_data(__x)
+	{ __x = _Deque_impl_data(); }
+#endif
+
+	void
+	_M_swap_data(_Deque_impl_data& __x) _GLIBCXX_NOEXCEPT
+	{
+	  // Do not use std::swap(_M_start, __x._M_start), etc as it loses
+	  // information used by TBAA.
+	  std::swap(*this, __x);
+	}
+      };
+
+      // This struct encapsulates the implementation of the std::deque
+      // standard container and at the same time makes use of the EBO
+      // for empty allocators.
+      struct _Deque_impl
+      : public _Tp_alloc_type, public _Deque_impl_data
+      {
+	_Deque_impl() _GLIBCXX_NOEXCEPT_IF(
+	  is_nothrow_default_constructible<_Tp_alloc_type>::value)
+	: _Tp_alloc_type()
 	{ }
 
 	_Deque_impl(const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
-	: _Tp_alloc_type(__a), _M_map(), _M_map_size(0),
-	  _M_start(), _M_finish()
+	: _Tp_alloc_type(__a)
 	{ }
 
 #if __cplusplus >= 201103L
 	_Deque_impl(_Deque_impl&&) = default;
 
 	_Deque_impl(_Tp_alloc_type&& __a) noexcept
-	: _Tp_alloc_type(std::move(__a)), _M_map(), _M_map_size(0),
-	  _M_start(), _M_finish()
+	: _Tp_alloc_type(std::move(__a))
 	{ }
-#endif
 
-	void _M_swap_data(_Deque_impl& __x) _GLIBCXX_NOEXCEPT
-	{
-	  using std::swap;
-	  swap(this->_M_start, __x._M_start);
-	  swap(this->_M_finish, __x._M_finish);
-	  swap(this->_M_map, __x._M_map);
-	  swap(this->_M_map_size, __x._M_map_size);
-	}
+	_Deque_impl(_Deque_impl&& __d, _Tp_alloc_type&& __a)
+	: _Tp_alloc_type(std::move(__a)), _Deque_impl_data(std::move(__d))
+	{ }
+#endif
       };
 
       _Tp_alloc_type&
       _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
-      { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); }
+      { return this->_M_impl; }
 
       const _Tp_alloc_type&
       _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT
-      { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); }
+      { return this->_M_impl; }
 
       _Map_alloc_type
       _M_get_map_allocator() const _GLIBCXX_NOEXCEPT
@@ -547,7 +563,6 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	_Map_alloc_traits::deallocate(__map_alloc, __p, __n);
       }
 
-    protected:
       void _M_initialize_map(size_t);
       void _M_create_nodes(_Map_pointer __nstart, _Map_pointer __nfinish);
       void _M_destroy_nodes(_Map_pointer __nstart,
@@ -561,9 +576,6 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       _Deque_impl
       _M_move_impl()
       {
-	if (!_M_impl._M_map)
-	  return std::move(_M_impl);
-
 	// Create a copy of the current allocator.
 	_Tp_alloc_type __alloc{_M_get_Tp_allocator()};
 	// Put that copy in a moved-from state.
@@ -791,7 +803,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       typedef ptrdiff_t					difference_type;
       typedef _Alloc					allocator_type;
 
-    protected:
+    private:
       static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT
       { return __deque_buf_size(sizeof(_Tp)); }
 
@@ -818,7 +830,11 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       /**
        *  @brief  Creates a %deque with no elements.
        */
-      deque() : _Base() { }
+#if __cplusplus >= 201103L
+      deque() = default;
+#else
+      deque() { }
+#endif
 
       /**
        *  @brief  Creates a %deque with no elements.
@@ -887,13 +903,13 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #if __cplusplus >= 201103L
       /**
        *  @brief  %Deque move constructor.
-       *  @param  __x  A %deque of identical element and allocator types.
        *
-       *  The newly-created %deque contains the exact contents of @a __x.
-       *  The contents of @a __x are a valid, but unspecified %deque.
+       *  The newly-created %deque contains the exact contents of the
+       *  moved instance.
+       *  The contents of the moved instance are a valid, but unspecified
+       *  %deque.
        */
-      deque(deque&& __x)
-      : _Base(std::move(__x)) { }
+      deque(deque&&) = default;
 
       /// Copy constructor with alternative allocator
       deque(const deque& __x, const allocator_type& __a)
@@ -904,9 +920,18 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /// Move constructor with alternative allocator
       deque(deque&& __x, const allocator_type& __a)
+      : deque(std::move(__x), __a, typename _Alloc_traits::is_always_equal{})
+      { }
+
+    private:
+      deque(deque&& __x, const allocator_type& __a, true_type)
+      : _Base(std::move(__x), __a)
+      { }
+
+      deque(deque&& __x, const allocator_type& __a, false_type)
       : _Base(std::move(__x), __a, __x.size())
       {
-	if (__x.get_allocator() != __a)
+	if (__x.get_allocator() != __a && !__x.empty())
 	  {
 	    std::__uninitialized_move_a(__x.begin(), __x.end(),
 					this->_M_impl._M_start,
@@ -915,6 +940,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  }
       }
 
+    public:
       /**
        *  @brief  Builds a %deque from an initializer list.
        *  @param  __l  An initializer_list.
@@ -956,7 +982,10 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	deque(_InputIterator __first, _InputIterator __last,
 	      const allocator_type& __a = allocator_type())
 	: _Base(__a)
-	{ _M_initialize_dispatch(__first, __last, __false_type()); }
+	{
+	  _M_range_initialize(__first, __last,
+			      std::__iterator_category(__first));
+	}
 #else
       template<typename _InputIterator>
 	deque(_InputIterator __first, _InputIterator __last,
@@ -1057,7 +1086,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	       typename = std::_RequireInputIter<_InputIterator>>
 	void
 	assign(_InputIterator __first, _InputIterator __last)
-	{ _M_assign_dispatch(__first, __last, __false_type()); }
+	{ _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
 #else
       template<typename _InputIterator>
 	void
@@ -1243,14 +1272,6 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       void
       resize(size_type __new_size, const value_type& __x)
-      {
-	const size_type __len = size();
-	if (__new_size > __len)
-	  _M_fill_insert(this->_M_impl._M_finish, __new_size - __len, __x);
-	else if (__new_size < __len)
-	  _M_erase_at_end(this->_M_impl._M_start
-			  + difference_type(__new_size));
-      }
 #else
       /**
        *  @brief  Resizes the %deque to the specified number of elements.
@@ -1265,6 +1286,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       void
       resize(size_type __new_size, value_type __x = value_type())
+#endif
       {
 	const size_type __len = size();
 	if (__new_size > __len)
@@ -1273,7 +1295,6 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  _M_erase_at_end(this->_M_impl._M_start
 			  + difference_type(__new_size));
       }
-#endif
 
 #if __cplusplus >= 201103L
       /**  A non-binding request to reduce memory use.  */
@@ -1514,7 +1535,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	if (this->_M_impl._M_start._M_cur
 	    != this->_M_impl._M_start._M_last - 1)
 	  {
-	    _Alloc_traits::destroy(this->_M_impl,
+	    _Alloc_traits::destroy(_M_get_Tp_allocator(),
 				   this->_M_impl._M_start._M_cur);
 	    ++this->_M_impl._M_start._M_cur;
 	  }
@@ -1538,7 +1559,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	    != this->_M_impl._M_finish._M_first)
 	  {
 	    --this->_M_impl._M_finish._M_cur;
-	    _Alloc_traits::destroy(this->_M_impl,
+	    _Alloc_traits::destroy(_M_get_Tp_allocator(),
 				   this->_M_impl._M_finish._M_cur);
 	  }
 	else
@@ -1602,6 +1623,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        *  @brief  Inserts an initializer list into the %deque.
        *  @param  __p  An iterator into the %deque.
        *  @param  __l  An initializer_list.
+       *  @return  An iterator that points to the inserted data.
        *
        *  This function will insert copies of the data in the
        *  initializer_list @a __l into the %deque before the location
@@ -1615,9 +1637,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 			    std::random_access_iterator_tag());
 	return begin() + __offset;
       }
-#endif
 
-#if __cplusplus >= 201103L
       /**
        *  @brief  Inserts a number of copies of given data into the %deque.
        *  @param  __position  A const_iterator into the %deque.
@@ -1669,8 +1689,8 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	       _InputIterator __last)
 	{
 	  difference_type __offset = __position - cbegin();
-	  _M_insert_dispatch(__position._M_const_cast(),
-			     __first, __last, __false_type());
+	  _M_range_insert_aux(__position._M_const_cast(), __first, __last,
+			      std::__iterator_category(__first));
 	  return begin() + __offset;
 	}
 #else
@@ -1776,6 +1796,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     protected:
       // Internal constructor functions follow.
 
+#if __cplusplus < 201103L || !_GLIBCXX_INLINE_VERSION
       // called by the range constructor to implement [23.1.1]/9
 
       // _GLIBCXX_RESOLVE_LIB_DEFECTS
@@ -1789,6 +1810,17 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  _M_fill_initialize(__x);
 	}
 
+      // called by the range constructor to implement [23.1.1]/9
+      template<typename _InputIterator>
+	void
+	_M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
+			       __false_type)
+	{
+	  _M_range_initialize(__first, __last,
+			      std::__iterator_category(__first));
+	}
+#endif
+
       static size_t
       _S_check_init_len(size_t __n, const allocator_type& __a)
       {
@@ -1806,16 +1838,6 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	return (std::min)(__diffmax, __allocmax);
       }
 
-      // called by the range constructor to implement [23.1.1]/9
-      template<typename _InputIterator>
-	void
-	_M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
-			       __false_type)
-	{
-	  _M_range_initialize(__first, __last,
-			      std::__iterator_category(__first));
-	}
-
       // called by the second initialize_dispatch above
       //@{
       /**
@@ -1862,6 +1884,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       // Internal assign functions follow.  The *_aux functions do the actual
       // assignment work for the range versions.
 
+#if __cplusplus < 201103L || !_GLIBCXX_INLINE_VERSION
       // called by the range assign to implement [23.1.1]/9
 
       // _GLIBCXX_RESOLVE_LIB_DEFECTS
@@ -1877,6 +1900,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	_M_assign_dispatch(_InputIterator __first, _InputIterator __last,
 			   __false_type)
 	{ _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
+#endif
 
       // called by the second assign_dispatch above
       template<typename _InputIterator>
@@ -1942,6 +1966,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       // Internal insert functions follow.  The *_aux functions do the actual
       // insertion work when all shortcuts fail.
 
+#if __cplusplus < 201103L || !_GLIBCXX_INLINE_VERSION
       // called by the range insert to implement [23.1.1]/9
 
       // _GLIBCXX_RESOLVE_LIB_DEFECTS
@@ -1962,6 +1987,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  _M_range_insert_aux(__pos, __first, __last,
 			      std::__iterator_category(__first));
 	}
+#endif
 
       // called by the second insert_dispatch above
       template<typename _InputIterator>
diff --git a/libstdc++-v3/testsuite/23_containers/deque/allocator/default_init.cc b/libstdc++-v3/testsuite/23_containers/deque/allocator/default_init.cc
new file mode 100644
index 00000000000..f6cc61e1fb8
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/allocator/default_init.cc
@@ -0,0 +1,67 @@ 
+// Copyright (C) 2019 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do run { target c++11 } }
+// { dg-options "-O0" }
+// { dg-xfail-run-if "PR c++/65816" { *-*-* } }
+
+#include <deque>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+#include <ext/aligned_buffer.h>
+
+using T = int;
+
+using __gnu_test::default_init_allocator;
+
+void test01()
+{
+  typedef default_init_allocator<T> alloc_type;
+  typedef std::deque<T, alloc_type> test_type;
+
+  __gnu_cxx::__aligned_buffer<test_type> buf;
+  __builtin_memset(buf._M_addr(), ~0, sizeof(test_type));
+
+  test_type *tmp = ::new(buf._M_addr()) test_type;
+
+  VERIFY( tmp->get_allocator().state == 0 );
+
+  tmp->~test_type();
+}
+
+void test02()
+{
+  typedef default_init_allocator<T> alloc_type;
+  typedef std::deque<T, alloc_type> test_type;
+
+  __gnu_cxx::__aligned_buffer<test_type> buf;
+  __builtin_memset(buf._M_addr(), ~0, sizeof(test_type));
+
+  test_type *tmp = ::new(buf._M_addr()) test_type();
+
+  VERIFY( tmp->get_allocator().state == 0 );
+
+  tmp->~test_type();
+}
+
+int main()
+{
+  test01();
+  test02();
+  return 0;
+}