Re: Default std::list default and move constructors

["François Dumont" <frs.dumont@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 5355 bytes --]

On 05/07/2017 17:22, Jonathan Wakely wrote:
> It's mostly good, but I'd like to make a few suggestions ...
>
>
>> diff --git a/libstdc++-v3/include/bits/stl_list.h 
>> b/libstdc++-v3/include/bits/stl_list.h
>> index 232885a..7ffffe5 100644
>> --- a/libstdc++-v3/include/bits/stl_list.h
>> +++ b/libstdc++-v3/include/bits/stl_list.h
>> @@ -82,6 +82,17 @@ namespace std _GLIBCXX_VISIBILITY(default)
>>       _List_node_base* _M_next;
>>       _List_node_base* _M_prev;
>>
>> +#if __cplusplus >= 201103L
>> +      _List_node_base() = default;
>> +#else
>> +      _List_node_base()
>> +      { }
>> +#endif
>> +
>> +      _List_node_base(_List_node_base* __next, _List_node_base* __prev)
>> +    : _M_next(__next), _M_prev(__prev)
>> +      { }
>> +
>
> I think I'd prefer to leave this struct with no user-defined
> constructors, instead of adding these.

My goal was to make sure that as much as possible instances are 
initialized through their initialization list. But it is still possible 
without it so I made the change.

>
>>       static void
>>       swap(_List_node_base& __x, _List_node_base& __y) 
>> _GLIBCXX_USE_NOEXCEPT;
>>
>> @@ -99,6 +110,79 @@ namespace std _GLIBCXX_VISIBILITY(default)
>>       _M_unhook() _GLIBCXX_USE_NOEXCEPT;
>>     };
>>
>> +    /// The %list node header.
>> +    struct _List_node_header : public _List_node_base
>> +    {
>> +    private:
>> +#if _GLIBCXX_USE_CXX11_ABI
>> +      std::size_t _M_size;
>> +#endif
>
> I don't think this needs to be private, because we don't have to worry
> about users accessing this member. It's an internal-only type, and the
> _M_next and _M_prev members are already public.

It's not internal-only as those members are exposed on std::list through 
inheritance. But I agree that consistency is more important here so I 
made it public.

>
> If it's public then the _List_base::_M_inc_size, _M_dec_size etc.
> could access it directly, and we don't need to add duplicates of those
> functions to _List_impl.
>
>> +
>> +      _List_node_base* _M_base() { return this; }
>
> Is this function necessary?

It is a nice replacement for calls to __addressof.

>
>> +    public:
>> +      _List_node_header() _GLIBCXX_NOEXCEPT
>> +      : _List_node_base(this, this)
>> +# if _GLIBCXX_USE_CXX11_ABI
>> +      , _M_size(0)
>> +# endif
>> +      { }
>
> This could be:
>
>      _List_node_header() _GLIBCXX_NOEXCEPT
>      { _M_init(); }

Sure, I was only interested in the initialization-list approach. As 
there is no default initialization of the members in _List_node_base for 
_M_prev/_M_next neither for _M_size I guess it will be super easy for 
the compiler to optimize it as if it was an initialization-list.

>
>
>> +#if __cplusplus >= 201103L
>> +      _List_node_header(_List_node_header&& __x) noexcept
>> +      : _List_node_base(__x._M_next, __x._M_prev)
>
> And this could use aggregate-initialization:
>
>      : _List_node_base{__x._M_next, __x._M_prev}

Nice.

>> +#if _GLIBCXX_USE_CXX11_ABI
>> +      size_t _M_get_size() const { return _M_size; }
>> +      void _M_set_size(size_t __n) { _M_size = __n; }
>> +      void _M_inc_size(size_t __n) { _M_size += __n; }
>> +      void _M_dec_size(size_t __n) { _M_size -= __n; }
>> +#else
>> +      // dummy implementations used when the size is not stored
>> +      size_t _M_get_size() const { return 0; }
>> +      void _M_set_size(size_t) { }
>> +      void _M_inc_size(size_t) { }
>> +      void _M_dec_size(size_t) { }
>> +#endif
>
> What do you think about only having _M_set_size() here?
> The other functions are not needed here (assuming _M_size is public).
>
> We could even get rid of _M_set_size and use #if in _M_init:
>
>> +      void
>> +      _M_init() _GLIBCXX_NOEXCEPT
>> +      {
>> +    this->_M_next = this->_M_prev = this;
> #if _GLIBCXX_USE_CXX11_ABI
>        _M_size = 0;
> #endif
>
>> +    _M_set_size(0);
>> +      }
>> +    };
>
> This replaces a #if and #else and four functions with a #if and no
> functions, which seems simpler to me.
> _List_impl _M_impl;
>>
>> -#if _GLIBCXX_USE_CXX11_ABI
>> -      size_t _M_get_size() const { return 
>> *_M_impl._M_node._M_valptr(); }
>> +      size_t
>> +      _M_get_size() const { return _M_impl._M_node._M_get_size(); }
>>
>> -      void _M_set_size(size_t __n) { *_M_impl._M_node._M_valptr() = 
>> __n; }
>> +      void
>> +      _M_set_size(size_t __n) { _M_impl._M_node._M_set_size(__n); }
>>
>> -      void _M_inc_size(size_t __n) { *_M_impl._M_node._M_valptr() += 
>> __n; }
>> +      void
>> +      _M_inc_size(size_t __n) { _M_impl._M_node._M_inc_size(__n); }
>>
>> -      void _M_dec_size(size_t __n) { *_M_impl._M_node._M_valptr() -= 
>> __n; }
>> +      void
>> +      _M_dec_size(size_t __n) { _M_impl._M_node._M_dec_size(__n); }
>
> These functions could just access _M_impl._M_size directly if it was
> public. Introducing new functions to _List_impl to be used here seems
> like unnecessary complication. We don't get rid of the #if because
> it's still needed for these functions anyway:
>
Yes, I wanted to manage as much as possible usage of C++11 abi in the 
new _List_node_header type.

So here is the new patch limited to this evolution. Optimization for 
always equal allocator will come after along with another simplification 
to replace _S_distance with std::distance.

Tests running, ok to commit if successful ?

François


[-- Attachment #2: list.patch --]
[-- Type: text/x-patch, Size: 10314 bytes --]

diff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h
index 232885a..934b5ed 100644
--- a/libstdc++-v3/include/bits/stl_list.h
+++ b/libstdc++-v3/include/bits/stl_list.h
@@ -99,6 +99,65 @@ namespace std _GLIBCXX_VISIBILITY(default)
       _M_unhook() _GLIBCXX_USE_NOEXCEPT;
     };
 
+    /// The %list node header.
+    struct _List_node_header : public _List_node_base
+    {
+#if _GLIBCXX_USE_CXX11_ABI
+      std::size_t _M_size;
+#endif
+
+      _List_node_header() _GLIBCXX_NOEXCEPT
+      { _M_init(); }
+
+#if __cplusplus >= 201103L
+      _List_node_header(_List_node_header&& __x) noexcept
+      : _List_node_base{ __x._M_next, __x._M_prev }
+# if _GLIBCXX_USE_CXX11_ABI
+      , _M_size(__x._M_size)
+# endif
+      {
+	if (__x._M_base()->_M_next == __x._M_base())
+	  this->_M_next = this->_M_prev = this;
+	else
+	  {
+	    this->_M_next->_M_prev = this->_M_prev->_M_next = this->_M_base();
+	    __x._M_init();
+	  }
+      }
+
+      void
+      _M_move_nodes(_List_node_header&& __x)
+      {
+	_List_node_base* const __xnode = __x._M_base();
+	if (__xnode->_M_next == __xnode)
+	  _M_init();
+	else
+	  {
+	    _List_node_base* const __node = this->_M_base();
+	    __node->_M_next = __xnode->_M_next;
+	    __node->_M_prev = __xnode->_M_prev;
+	    __node->_M_next->_M_prev = __node->_M_prev->_M_next = __node;
+# if _GLIBCXX_USE_CXX11_ABI
+	    _M_size = __x._M_size;
+# endif
+	    __x._M_init();
+	  }
+      }
+#endif
+
+      void
+      _M_init() _GLIBCXX_NOEXCEPT
+      {
+	this->_M_next = this->_M_prev = this;
+#if _GLIBCXX_USE_CXX11_ABI
+	this->_M_size = 0;
+#endif
+      }
+
+    private:
+      _List_node_base* _M_base() { return this; }
+    };
+
   _GLIBCXX_END_NAMESPACE_VERSION
   } // namespace detail
 
@@ -323,23 +382,21 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
       struct _List_impl
       : public _Node_alloc_type
       {
-#if _GLIBCXX_USE_CXX11_ABI
-	_List_node<size_t> _M_node;
-#else
-	__detail::_List_node_base _M_node;
-#endif
+	__detail::_List_node_header _M_node;
 
-	_List_impl() _GLIBCXX_NOEXCEPT
-	: _Node_alloc_type(), _M_node()
+	_List_impl() _GLIBCXX_NOEXCEPT_IF( noexcept(_Node_alloc_type()) )
+	: _Node_alloc_type()
 	{ }
 
 	_List_impl(const _Node_alloc_type& __a) _GLIBCXX_NOEXCEPT
-	: _Node_alloc_type(__a), _M_node()
+	: _Node_alloc_type(__a)
 	{ }
 
 #if __cplusplus >= 201103L
+	_List_impl(_List_impl&&) = default;
+
 	_List_impl(_Node_alloc_type&& __a) noexcept
-	: _Node_alloc_type(std::move(__a)), _M_node()
+	: _Node_alloc_type(std::move(__a))
 	{ }
 #endif
       };
@@ -347,13 +404,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_valptr(); }
+      size_t _M_get_size() const { return _M_impl._M_node._M_size; }
 
-      void _M_set_size(size_t __n) { *_M_impl._M_node._M_valptr() = __n; }
+      void _M_set_size(size_t __n) { _M_impl._M_node._M_size = __n; }
 
-      void _M_inc_size(size_t __n) { *_M_impl._M_node._M_valptr() += __n; }
+      void _M_inc_size(size_t __n) { _M_impl._M_node._M_size += __n; }
 
-      void _M_dec_size(size_t __n) { *_M_impl._M_node._M_valptr() -= __n; }
+      void _M_dec_size(size_t __n) { _M_impl._M_node._M_size -= __n; }
 
       size_t
       _M_distance(const __detail::_List_node_base* __first,
@@ -361,7 +418,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_valptr(); }
+      size_t _M_node_count() const { return _M_get_size(); }
 #else
       // dummy implementations used when the size is not stored
       size_t _M_get_size() const { return 0; }
@@ -397,44 +454,30 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
       _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
       { return _M_impl; }
 
-      _List_base()
-      : _M_impl()
-      { _M_init(); }
+#if __cplusplus >= 201103L
+      _List_base() = default;
+#else
+      _List_base() { }
+#endif
 
       _List_base(const _Node_alloc_type& __a) _GLIBCXX_NOEXCEPT
       : _M_impl(__a)
-      { _M_init(); }
+      { }
 
 #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&&) = default;
 
       _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.
+	// else 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)
-	  _M_init();
-	else
-	  {
-	    auto* const __node = std::__addressof(_M_impl._M_node);
-	    __node->_M_next = __xnode->_M_next;
-	    __node->_M_prev = __xnode->_M_prev;
-	    __node->_M_next->_M_prev = __node->_M_prev->_M_next = __node;
-	    _M_set_size(__x._M_get_size());
-	    __x._M_init();
-	  }
-      }
+      { _M_impl._M_node._M_move_nodes(std::move(__x._M_impl._M_node)); }
 #endif
 
       // This is what actually destroys the list.
@@ -446,11 +489,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
 
       void
       _M_init() _GLIBCXX_NOEXCEPT
-      {
-	this->_M_impl._M_node._M_next = &this->_M_impl._M_node;
-	this->_M_impl._M_node._M_prev = &this->_M_impl._M_node;
-	_M_set_size(0);
-      }
+      { this->_M_impl._M_node._M_init(); }
     };
 
   /**
@@ -586,11 +625,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
       /**
        *  @brief  Creates a %list with no elements.
        */
-      list()
 #if __cplusplus >= 201103L
-      noexcept(is_nothrow_default_constructible<_Node_alloc_type>::value)
+      list() = default;
+#else
+      list() { }
 #endif
-      : _Base() { }
 
       /**
        *  @brief  Creates a %list with no elements.
@@ -657,13 +696,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
 #if __cplusplus >= 201103L
       /**
        *  @brief  %List move constructor.
-       *  @param  __x  A %list of identical element and allocator types.
        *
-       *  The newly-created %list contains the exact contents of @a __x.
-       *  The contents of @a __x are a valid, but unspecified %list.
+       *  The newly-created %list contains the exact contents of the moved
+       *  instance. The contents of the moved instance are a valid, but
+       *  unspecified %list.
        */
-      list(list&& __x) noexcept
-      : _Base(std::move(__x)) { }
+      list(list&&) = default;
 
       /**
        *  @brief  Builds a %list from an initializer_list
@@ -1838,17 +1876,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
       _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();
-	  }
+	this->_M_move_nodes(std::move(__x));
 	std::__alloc_on_move(this->_M_get_Node_allocator(),
 			     __x._M_get_Node_allocator());
       }
@@ -1983,12 +2011,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	       _GLIBCXX_STD_C::_List_const_iterator<_Tp> __last,
 	       input_iterator_tag)
     {
-      typedef _GLIBCXX_STD_C::_List_node<size_t> _Sentinel;
+      typedef __detail::_List_node_header _Sentinel;
       _GLIBCXX_STD_C::_List_const_iterator<_Tp> __beyond = __last;
       ++__beyond;
       bool __whole = __first == __beyond;
       if (__builtin_constant_p (__whole) && __whole)
-	return *static_cast<const _Sentinel*>(__last._M_node)->_M_valptr();
+	return static_cast<const _Sentinel*>(__last._M_node)->_M_size;
 
       ptrdiff_t __n = 0;
       while (__first != __last)
diff --git a/libstdc++-v3/testsuite/23_containers/list/allocator/default_init.cc b/libstdc++-v3/testsuite/23_containers/list/allocator/default_init.cc
new file mode 100644
index 0000000..0604e06
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/list/allocator/default_init.cc
@@ -0,0 +1,71 @@
+// Copyright (C) 2017 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 <list>
+#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::list<T, alloc_type> test_type;
+
+  __gnu_cxx::__aligned_buffer<test_type> buf;
+  __builtin_memset(buf._M_addr(), ~0, sizeof(test_type));
+
+  VERIFY( buf._M_ptr()->get_allocator().state != 0 );
+
+  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::list<T, alloc_type> test_type;
+
+  __gnu_cxx::__aligned_buffer<test_type> buf;
+  __builtin_memset(buf._M_addr(), ~0, sizeof(test_type));
+
+  VERIFY( buf._M_ptr()->get_allocator().state != 0 );
+
+  test_type *tmp = ::new(buf._M_addr()) test_type;
+
+  VERIFY( tmp->get_allocator().state == 0 );
+
+  tmp->~test_type();
+}
+
+int main()
+{
+  test01();
+  test02();
+  return 0;
+}