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
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;
+}
