[PATCH 3/3 v2] libstdc++: Add fancy pointer support to std::list [PR57272]

Jonathan Wakely jwakely@redhat.com
Sat Nov 16 23:14:36 GMT 2024


Currently std::list uses raw pointers to connect its nodes, which is
non-conforming. We should use the allocator's pointer type everywhere
that a "pointer" is needed.

Because the existing types like _List_node<T> are part of the ABI now,
we can't change them. To support nodes that are connected by fancy
pointers we need a parallel hierarchy of node types. This change
introduces new class templates parameterized on the allocator's
void_pointer type, __list::_Node_base and __list::_Node_header, and new
class templates parameterized on the allocator's pointer type,
__list::Node, __list::_Iterator. The iterator class template is used for
both iterator and const_iterator. Whether std::list<T, A> should use the
old _List_node<T> or new _list::_Node<A::pointer> type family internally
is controlled by a new __list::_Node_traits traits template.

Because std::pointer_traits and std::__to_address are not defined for
C++98, there is no way to support fancy pointers in C++98. For C++98 the
_Node_traits traits always choose the old _List_node family.

In case anybody is currently using std::list with an allocator that has
a fancy pointer, this change would be an ABI break, because their
std::list instantiations would start to (correctly) use the fancy
pointer type. If the fancy pointer just contains a single pointer and so
has the same size, layout, and object represenation as a raw pointer,
the code might still work (despite being an ODR violation). But if their
fancy pointer has a different representation, they would need to
recompile all their code using that allocator with std::list. Because
std::list will never use fancy pointers in C++98 mode, recompiling
everything to use fancy pointers isn't even possible if mixing C++98 and
C++11 code that uses std::list. To alleviate this problem, compiling
with -D_GLIBCXX_USE_ALLOC_PTR_FOR_LIST=0 will force std::list to have
the old, non-conforming behaviour and use raw pointers internally. For
testing purposes, compiling with -D_GLIBCXX_USE_ALLOC_PTR_FOR_LIST=9001
will force std::list to always use the new node types.  This macro is
currently undocumented, which needs to be fixed.

The original _List_node<T> type is trivially constructible and trivially
destructible, but the new __list::_Node<Ptr> type might not be,
depending on the fancy pointer data members in _Node_base. This means
that std::list needs to explicitly construct and destroy the node
object, not just the value that it contains. This commit adds a new
__allocated_obj helper which wraps an __allocated_ptr and additionally
constructs and destroys an object in the allocated storage.

Pretty printers for std::list need to be updated to handle the new node
types.

libstdc++-v3/ChangeLog:

	PR libstdc++/57272
	PR libstdc++/110952
	* include/bits/allocated_ptr.h (__allocated_ptr::get): Add
	const.
	(__allocated_ptr::operator bool, __allocated_ptr::release): New
	member functions.
	(__allocate_guarded): Add inline.
	(__allocated_obj): New class template.
	(__allocate_guarded_obj): New function template.
	* include/bits/list.tcc (_List_base::_M_clear()): Replace uses
	of raw pointers. Use _M_destroy_node.
	(list::emplace, list::insert): Likewise.
	(list::sort): Adjust check for 0 or 1 wsize. Use template
	argument list for _Scratch_list.
	* include/bits/stl_list.h (_GLIBCXX_USE_ALLOC_PTR_FOR_LIST):
	Define.
	(_List_node_base::_Base_ptr): New typedef.
	(_List_node_base::_M_base): New member functions.
	(_List_node_header::_M_base): Make public and add
	using-declaration for base class overload.
	(__list::_Node_traits, __list::_Node_base)
	(__list::_Node_header, __list::_Node, __list::_Iterator): New
	class templates.
	(_Scratch_list): Turn class into class template. Use _Base_ptr
	typedef instead of _List_node_base*.
	(_List_node::_Node_ptr): New typedef.
	(_List_node::_M_node_ptr): New member function.
	(_List_base, _List_impl): Use _Node_traits to get node types.
	(_List_base::_M_put_node): Convert to fancy pointer if needed.
	(_List_base::_M_destroy_node): New member function.
	(_List_base(_List_base&&, _Node_alloc_type&&)): Use if constexpr
	to make function a no-op for fancy pointers.
	(_List_base::_S_distance, _List_base::_M_distance)
	(_List_base::_M_node_count): Likewise.
	(list): Use _Node_traits to get iterator, node and pointer
	types.
	(list::_M_create_node): Use _Node_ptr typedef instead of _Node*.
	Use __allocate_guarded_obj instead of _M_get_node.
	(list::end, list::cend, list::empty): Use node header's
	_M_base() function instead of taking its address.
	(list::swap): Use _Node_traits to get node base type.
	(list::_M_create_node, list::_M_insert): Use _Node_ptr instead
	of _Node*.
	(list::_M_erase): Likewise. Use _M_destroy_node.
	(__distance): Overload for __list::_Iterator.
	(_Node_base::swap, _Node_base::_M_transfer): Define non-inline
	member functions of class templates.
	(_Node_header::_M_reverse): Likewise.
	* testsuite/23_containers/list/capacity/29134.cc: Check max_size
	for allocator of new node type.
	* testsuite/23_containers/list/capacity/node_sizes.cc: New test.
	* testsuite/23_containers/list/requirements/explicit_instantiation/alloc_ptr.cc:
	New test.
	* testsuite/23_containers/list/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
	New test.
---

Tested x86_64-linux.

I found some bugs while testing the first version of [PATCH 3/3] which
are fixed in this v2:

- Incomplete value types no longer worked, because I was accessing
  members of _Node like _Node::_Base_ptr, which requires _Node to be
  complete, which requires the value_type to be complete. Replaced all
  those with _Node_base::_Base_ptr or __ptr_rebind<Ptr, _Node_base> or
  similar.
- The _Node that uses fancy pointers is not necessarily trivially
  constructible or trivially destructible, so needs to be properly
  initialized when storage for a node is allocated, and destroyed when
  storage is deallocated. Added __allocated_guarded_obj and
  _M_destroy_node to make that simpler.

Not bugs, but improvements:

- Renamed the _GLIBCXX_LIST_USE_ALLOC_PTR macro to
  _GLIBCXX_USE_ALLOC_PTR_FOR_LIST. Since I'm adding a similar macro for
  forward_list, I thought it was better for the two macros names to only
  differ at the end, not in the middle.
- Defining that macro to a value over 9000 now forces the use of the new
  node types even for non-fancy pointers. This is mostly useful for
  testing, so we can use all the existing tests for the new node
  hierarchy.
- Reordered the definitions of the new class templates.


 libstdc++-v3/include/bits/allocated_ptr.h     |  44 +-
 libstdc++-v3/include/bits/list.tcc            |  52 +-
 libstdc++-v3/include/bits/stl_list.h          | 598 ++++++++++++++++--
 .../23_containers/list/capacity/29134.cc      |   5 +
 .../23_containers/list/capacity/node_sizes.cc |  24 +
 .../list/requirements/completeness.cc         |  19 +
 .../explicit_instantiation/alloc_ptr.cc       |  87 +++
 .../alloc_ptr_ignored.cc                      |   4 +
 8 files changed, 744 insertions(+), 89 deletions(-)
 create mode 100644 libstdc++-v3/testsuite/23_containers/list/capacity/node_sizes.cc
 create mode 100644 libstdc++-v3/testsuite/23_containers/list/requirements/completeness.cc
 create mode 100644 libstdc++-v3/testsuite/23_containers/list/requirements/explicit_instantiation/alloc_ptr.cc
 create mode 100644 libstdc++-v3/testsuite/23_containers/list/requirements/explicit_instantiation/alloc_ptr_ignored.cc

diff --git a/libstdc++-v3/include/bits/allocated_ptr.h b/libstdc++-v3/include/bits/allocated_ptr.h
index 26a07a1d34f..3d0f62bfa9f 100644
--- a/libstdc++-v3/include/bits/allocated_ptr.h
+++ b/libstdc++-v3/include/bits/allocated_ptr.h
@@ -82,22 +82,60 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	return *this;
       }
 
+      explicit operator bool() const noexcept { return (bool)_M_ptr; }
+
       /// Get the address that the owned pointer refers to.
-      value_type* get() { return std::__to_address(_M_ptr); }
+      value_type* get() const { return std::__to_address(_M_ptr); }
+
+      pointer release() { return std::__exchange(_M_ptr, nullptr); }
 
     private:
       _Alloc* _M_alloc;
       pointer _M_ptr;
     };
 
-  /// Allocate space for a single object using __a
+  /// Allocate space for a single object using __a.
   template<typename _Alloc>
-    __allocated_ptr<_Alloc>
+    inline __allocated_ptr<_Alloc>
     __allocate_guarded(_Alloc& __a)
     {
       return { __a, std::allocator_traits<_Alloc>::allocate(__a, 1) };
     }
 
+  /// RAII type for constructing/destroying an object with an allocated pointer
+  template<typename _Alloc>
+    struct __allocated_obj : __allocated_ptr<_Alloc>
+    {
+      using value_type = typename __allocated_ptr<_Alloc>::value_type;
+
+      __allocated_obj(__allocated_obj<_Alloc>&&) = default;
+
+      // Default-initialize a value_type at *__ptr
+      __allocated_obj(__allocated_ptr<_Alloc>&& __ptr)
+      : __allocated_ptr<_Alloc>(std::move(__ptr))
+      { ::new ((void*)this->get()) value_type; }
+
+      // Call the destructor if an object is owned.
+      ~__allocated_obj()
+      {
+	if (static_cast<bool>(*this))
+	  this->get()->~value_type();
+      }
+
+      using __allocated_ptr<_Alloc>::operator=;
+
+      value_type& operator*() const { return *this->get(); }
+      value_type* operator->() const { return this->get(); }
+    };
+
+  /// Construct an object in storage allocated using __a.
+  template<typename _Alloc>
+    inline __allocated_obj<_Alloc>
+    __allocate_guarded_obj(_Alloc& __a)
+    {
+      return { std::__allocate_guarded(__a) };
+    }
+
 /// @endcond
 _GLIBCXX_END_NAMESPACE_VERSION
 } // namespace std
diff --git a/libstdc++-v3/include/bits/list.tcc b/libstdc++-v3/include/bits/list.tcc
index 65835c1379f..2102e15eec2 100644
--- a/libstdc++-v3/include/bits/list.tcc
+++ b/libstdc++-v3/include/bits/list.tcc
@@ -66,19 +66,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     _List_base<_Tp, _Alloc>::
     _M_clear() _GLIBCXX_NOEXCEPT
     {
-      typedef _List_node<_Tp>  _Node;
-      __detail::_List_node_base* __cur = _M_impl._M_node._M_next;
-      while (__cur != &_M_impl._M_node)
+      typedef typename _Node_traits::_Node  _Node;
+      typedef typename _Node_traits::_Node_base  _Node_base;
+      typename _Node_base::_Base_ptr __cur = _M_impl._M_node._M_next;
+      while (__cur != _M_impl._M_node._M_base())
 	{
-	  _Node* __tmp = static_cast<_Node*>(__cur);
-	  __cur = __tmp->_M_next;
-	  _Tp* __val = __tmp->_M_valptr();
-#if __cplusplus >= 201103L
-	  _Node_alloc_traits::destroy(_M_get_Node_allocator(), __val);
-#else
-	  _Tp_alloc_type(_M_get_Node_allocator()).destroy(__val);
-#endif
-	  _M_put_node(__tmp);
+	  _Node& __tmp = static_cast<_Node&>(*__cur);
+	  __cur = __tmp._M_next;
+	  this->_M_destroy_node(__tmp._M_node_ptr());
 	}
     }
 
@@ -89,10 +84,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       list<_Tp, _Alloc>::
       emplace(const_iterator __position, _Args&&... __args)
       {
-	_Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
+	_Node_ptr __tmp = _M_create_node(std::forward<_Args>(__args)...);
 	__tmp->_M_hook(__position._M_const_cast()._M_node);
 	this->_M_inc_size(1);
-	return iterator(__tmp);
+	return iterator(__tmp->_M_base());
       }
 #endif
 
@@ -105,10 +100,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     insert(iterator __position, const value_type& __x)
 #endif
     {
-      _Node* __tmp = _M_create_node(__x);
+      _Node_ptr __tmp = _M_create_node(__x);
       __tmp->_M_hook(__position._M_const_cast()._M_node);
       this->_M_inc_size(1);
-      return iterator(__tmp);
+      return iterator(__tmp->_M_base());
     }
 
 #if __cplusplus >= 201103L
@@ -482,10 +477,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     sort()
     {
       // Do nothing if the list has length 0 or 1.
-      if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
-	  && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
+      if (empty() || ++begin() == end())
+	return;
+
       {
-	using __detail::_Scratch_list;
+	typedef __list::_Scratch_list<typename _Node_traits::_Node_base>
+	  _Scratch_list;
+
 	// The algorithm used here is largely unchanged from the SGI STL
 	// and is described in The C++ Standard Template Library by Plauger,
 	// Stepanov, Lee, Musser.
@@ -499,7 +497,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	_Scratch_list* __fill = __tmp;
 	_Scratch_list* __counter;
 
-	_Scratch_list::_Ptr_cmp<iterator, void> __ptr_comp;
+	typename _Scratch_list::template _Ptr_cmp<iterator, void> __ptr_comp;
 
 	__try
 	  {
@@ -614,17 +612,21 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       sort(_StrictWeakOrdering __comp)
       {
 	// Do nothing if the list has length 0 or 1.
-	if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
-	    && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
+	if (empty() || ++begin() == end())
+	  return;
+
 	{
-	  using __detail::_Scratch_list;
+	  typedef __list::_Scratch_list<typename _Node_traits::_Node_base>
+	    _Scratch_list;
+
 	  _Scratch_list __carry;
 	  _Scratch_list __tmp[64];
 	  _Scratch_list* __fill = __tmp;
 	  _Scratch_list* __counter;
 
-	_Scratch_list::_Ptr_cmp<iterator, _StrictWeakOrdering> __ptr_comp
-	  = { __comp };
+	  typename _Scratch_list::
+	    template _Ptr_cmp<iterator, _StrictWeakOrdering> __ptr_comp
+	    = { __comp };
 
 	  __try
 	    {
diff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h
index b1ab335ba4c..ddca579033f 100644
--- a/libstdc++-v3/include/bits/stl_list.h
+++ b/libstdc++-v3/include/bits/stl_list.h
@@ -62,6 +62,7 @@
 #if __cplusplus >= 201103L
 #include <initializer_list>
 #include <bits/allocated_ptr.h>
+#include <bits/ptr_traits.h>
 #include <ext/aligned_buffer.h>
 #endif
 #if __glibcxx_ranges_to_container // C++ >= 23
@@ -69,6 +70,13 @@
 # include <bits/ranges_util.h> // ranges::subrange
 #endif
 
+#if __cplusplus < 201103L
+# undef _GLIBCXX_USE_ALLOC_PTR_FOR_LIST
+# define _GLIBCXX_USE_ALLOC_PTR_FOR_LIST 0
+#elif ! defined _GLIBCXX_USE_ALLOC_PTR_FOR_LIST
+# define _GLIBCXX_USE_ALLOC_PTR_FOR_LIST 1
+#endif
+
 namespace std _GLIBCXX_VISIBILITY(default)
 {
 _GLIBCXX_BEGIN_NAMESPACE_VERSION
@@ -84,6 +92,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     /// Common part of a node in the %list.
     struct _List_node_base
     {
+      typedef _List_node_base* _Base_ptr;
+
       _List_node_base* _M_next;
       _List_node_base* _M_prev;
 
@@ -102,6 +112,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       void
       _M_unhook() _GLIBCXX_USE_NOEXCEPT;
+
+      _List_node_base* _M_base() { return this; }
+      const _List_node_base* _M_base() const { return this; }
     };
 
     struct _List_size
@@ -112,7 +125,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #endif
     };
 
-
     /// The %list node header.
     struct _List_node_header : public _List_node_base, _List_size
     {
@@ -157,18 +169,313 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_List_size::operator=(_List_size());
       }
 
-    private:
-      _List_node_base* _M_base() { return this; }
+      using _List_node_base::_M_base;
+#if ! _GLIBCXX_INLINE_VERSION
+      _List_node_base* _M_base() { return this; } // XXX GLIBCXX_ABI Deprecated
+#endif
     };
 
-    // Used by list::sort to hold nodes being sorted.
-    struct _Scratch_list : _List_node_base
+  } // namespace detail
+
+#if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST
+_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
+_GLIBCXX_BEGIN_NAMESPACE_CXX11
+  template<typename _Tp, typename _Allocator> class list;
+_GLIBCXX_END_NAMESPACE_CXX11
+_GLIBCXX_END_NAMESPACE_CONTAINER
+
+namespace __list
+{
+  // The base class for a list node.  Contains the pointers connecting nodes.
+  template<typename _VoidPtr>
+    struct _Node_base
     {
-      _Scratch_list() { _M_next = _M_prev = this; }
+      using _Base_ptr = __ptr_rebind<_VoidPtr, _Node_base>;
+      _Base_ptr _M_next;
+      _Base_ptr _M_prev;
 
-      bool empty() const { return _M_next == this; }
+      static void
+      swap(_Node_base& __x, _Node_base& __y) noexcept;
 
-      void swap(_List_node_base& __l) { _List_node_base::swap(*this, __l); }
+      void
+      _M_transfer(_Base_ptr const __first, _Base_ptr const __last);
+
+      void
+      _M_hook(_Base_ptr const __position) noexcept
+      {
+	auto __self = pointer_traits<_Base_ptr>::pointer_to(*this);
+	this->_M_next = __position;
+	this->_M_prev = __position->_M_prev;
+	__position->_M_prev->_M_next = __self;
+	__position->_M_prev = __self;
+      }
+
+      void
+      _M_unhook() noexcept
+      {
+	auto const __next_node = this->_M_next;
+	auto const __prev_node = this->_M_prev;
+	__prev_node->_M_next = __next_node;
+	__next_node->_M_prev = __prev_node;
+      }
+
+      // This is not const-correct, but it's only used in a const access path
+      // by std::list::empty(), where it doesn't escape, and by
+      // std::list::end() const, where the pointer is used to initialize a
+      // const_iterator and so constness is restored.
+      _Base_ptr
+      _M_base() const noexcept
+      {
+	return pointer_traits<_Base_ptr>::
+		 pointer_to(const_cast<_Node_base&>(*this));
+      }
+    };
+
+  using ::std::__detail::_List_size;
+
+  // The special sentinel node contained by a std::list.
+  // begin()->_M_node->_M_prev and end()->_M_node point to this header.
+  // This is not a complete node, as it doesn't contain a value.
+  template<typename _VoidPtr>
+    struct _Node_header
+    : public _Node_base<_VoidPtr>, _List_size
+    {
+      _Node_header() noexcept
+      { _M_init(); }
+
+      _Node_header(_Node_header&& __x) noexcept
+      : _Node_base<_VoidPtr>(__x), _List_size(__x)
+      {
+	if (__x._M_base()->_M_next == __x._M_base())
+	  this->_M_next = this->_M_prev = this->_M_base();
+	else
+	  {
+	    this->_M_next->_M_prev = this->_M_prev->_M_next = this->_M_base();
+	    __x._M_init();
+	  }
+      }
+
+      void
+      _M_move_nodes(_Node_header&& __x) noexcept
+      {
+	auto const __xnode = __x._M_base();
+	if (__xnode->_M_next == __xnode)
+	  _M_init();
+	else
+	  {
+	    auto 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;
+	    _List_size::operator=(__x);
+	    __x._M_init();
+	  }
+      }
+
+      void
+      _M_init() noexcept
+      {
+	this->_M_next = this->_M_prev = this->_M_base();
+	_List_size::operator=(_List_size());
+      }
+
+      void _M_reverse() noexcept;
+    };
+
+  // The node type used for allocators with fancy pointers.
+  template<typename _ValPtr>
+    struct _Node : public __list::_Node_base<__ptr_rebind<_ValPtr, void>>
+    {
+      using value_type = typename pointer_traits<_ValPtr>::element_type;
+      using _Node_ptr = __ptr_rebind<_ValPtr, _Node>;
+
+      union {
+	value_type _M_data;
+      };
+
+      _Node() { }
+      ~_Node() { }
+      _Node(_Node&&) = delete;
+
+      value_type*       _M_valptr()       { return std::__addressof(_M_data); }
+      value_type const* _M_valptr() const { return std::__addressof(_M_data); }
+
+      _Node_ptr
+      _M_node_ptr()
+      { return pointer_traits<_Node_ptr>::pointer_to(*this); }
+    };
+
+  template<bool _Const, typename _Ptr> class _Iterator;
+
+  template<bool _Const, typename _Ptr>
+    class _Iterator
+    {
+      using _Node     = __list::_Node<_Ptr>;
+      using _Base_ptr
+	= typename __list::_Node_base<__ptr_rebind<_Ptr, void>>::_Base_ptr;
+
+      template<typename _Tp>
+	using __maybe_const = __conditional_t<_Const, const _Tp, _Tp>;
+
+    public:
+      using value_type        = typename pointer_traits<_Ptr>::element_type;
+      using difference_type   = ptrdiff_t;
+      using iterator_category = bidirectional_iterator_tag;
+      using pointer           = __maybe_const<value_type>*;
+      using reference         = __maybe_const<value_type>&;
+
+      constexpr _Iterator() noexcept : _M_node() { }
+
+      _Iterator(const _Iterator&) = default;
+      _Iterator& operator=(const _Iterator&) = default;
+
+#ifdef __glibcxx_concepts
+      constexpr
+      _Iterator(const _Iterator<false, _Ptr>& __i) requires _Const
+#else
+      template<bool _OtherConst,
+	       typename = __enable_if_t<_Const && !_OtherConst>>
+	constexpr
+	_Iterator(const _Iterator<_OtherConst, _Ptr>& __i)
+#endif
+	: _M_node(__i._M_node) { }
+
+      constexpr explicit
+      _Iterator(_Base_ptr __x) noexcept
+      : _M_node(__x) { }
+
+      // Must downcast from _Node_base to _Node to get to value.
+      [[__nodiscard__]]
+      constexpr reference
+      operator*() const noexcept
+      { return static_cast<_Node&>(*_M_node)._M_data; }
+
+      [[__nodiscard__]]
+      constexpr pointer
+      operator->() const noexcept
+      { return std::__addressof(operator*()); }
+
+      _GLIBCXX14_CONSTEXPR _Iterator&
+      operator++() noexcept
+      {
+	_M_node = _M_node->_M_next;
+	return *this;
+      }
+
+      _GLIBCXX14_CONSTEXPR _Iterator
+      operator++(int) noexcept
+      {
+	auto __tmp = *this;
+	_M_node = _M_node->_M_next;
+	return __tmp;
+      }
+
+      _GLIBCXX14_CONSTEXPR _Iterator&
+      operator--() noexcept
+      {
+	_M_node = _M_node->_M_prev;
+	return *this;
+      }
+
+      _GLIBCXX14_CONSTEXPR _Iterator
+      operator--(int) noexcept
+      {
+	auto __tmp = *this;
+	_M_node = _M_node->_M_prev;
+	return __tmp;
+      }
+
+      [[__nodiscard__]]
+      friend constexpr bool
+      operator==(const _Iterator& __x, const _Iterator& __y) noexcept
+      { return __x._M_node == __y._M_node; }
+
+#if __cpp_impl_three_way_comparison < 201907L
+      [[__nodiscard__]]
+      friend constexpr bool
+      operator!=(const _Iterator& __x, const _Iterator& __y) noexcept
+      { return __x._M_node != __y._M_node; }
+#endif
+
+    private:
+      template<typename _Tp, typename _Allocator>
+	friend class _GLIBCXX_STD_C::list;
+
+      friend _Iterator<!_Const, _Ptr>;
+
+      constexpr _Iterator<false, _Ptr>
+      _M_const_cast() const noexcept
+      { return _Iterator<false, _Ptr>(_M_node); }
+
+      _Base_ptr _M_node;
+    };
+} // namespace __list
+#endif // USE_ALLOC_PTR_FOR_LIST
+
+_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
+  template<typename _Tp> struct _List_node;
+  template<typename _Tp> struct _List_iterator;
+  template<typename _Tp> struct _List_const_iterator;
+_GLIBCXX_END_NAMESPACE_CONTAINER
+
+namespace __list
+{
+  // Determine the node and iterator types used by std::list.
+  template<typename _Tp, typename _Ptr>
+    struct _Node_traits;
+
+#if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST <= 9000
+  // Specialization for the simple case where the allocator's pointer type
+  // is the same type as value_type*.
+  // For ABI compatibility we can't change the types used for this case.
+  template<typename _Tp>
+    struct _Node_traits<_Tp, _Tp*>
+    {
+      typedef __detail::_List_node_base			_Node_base;
+      typedef __detail::_List_node_header		_Node_header;
+      typedef _GLIBCXX_STD_C::_List_node<_Tp>		_Node;
+      typedef _GLIBCXX_STD_C::_List_iterator<_Tp>	_Iterator;
+      typedef _GLIBCXX_STD_C::_List_const_iterator<_Tp>	_Const_iterator;
+    };
+#endif
+
+#if ! _GLIBCXX_USE_ALLOC_PTR_FOR_LIST
+  // Always use the T* specialization.
+  template<typename _Tp, typename _Ptr>
+    struct _Node_traits
+    : _Node_traits<_Tp, _Tp*>
+    { };
+#else
+  // Primary template used when the allocator uses fancy pointers.
+  template<typename _Tp, typename _Ptr>
+    struct _Node_traits
+    {
+    private:
+      using _VoidPtr = __ptr_rebind<_Ptr, void>;
+      using _ValPtr = __ptr_rebind<_Ptr, _Tp>;
+
+    public:
+      using _Node_base      = __list::_Node_base<_VoidPtr>;
+      using _Node_header    = __list::_Node_header<_VoidPtr>;
+      using _Node           = __list::_Node<_ValPtr>;
+      using _Iterator       = __list::_Iterator<false, _ValPtr>;
+      using _Const_iterator = __list::_Iterator<true, _ValPtr>;
+    };
+#endif // USE_ALLOC_PTR_FOR_LIST
+
+  // Used by std::list::sort to hold nodes being sorted.
+  template<typename _NodeBaseT>
+    struct _Scratch_list
+    : _NodeBaseT
+    {
+      typedef _NodeBaseT _Base;
+      typedef typename _Base::_Base_ptr _Base_ptr;
+
+      _Scratch_list() { this->_M_next = this->_M_prev = this->_M_base(); }
+
+      bool empty() const { return this->_M_next == this->_M_base(); }
+
+      void swap(_Base& __l) { _Base::swap(*this, __l); }
 
       template<typename _Iter, typename _Cmp>
 	struct _Ptr_cmp
@@ -176,8 +483,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  _Cmp _M_cmp;
 
 	  bool
-	  operator()(__detail::_List_node_base* __lhs,
-		     __detail::_List_node_base* __rhs) /* not const */
+	  operator()(_Base_ptr __lhs, _Base_ptr __rhs) /* not const */
 	  { return _M_cmp(*_Iter(__lhs), *_Iter(__rhs)); }
 	};
 
@@ -185,26 +491,25 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	struct _Ptr_cmp<_Iter, void>
 	{
 	  bool
-	  operator()(__detail::_List_node_base* __lhs,
-		     __detail::_List_node_base* __rhs) const
+	  operator()(_Base_ptr __lhs, _Base_ptr __rhs) const
 	  { return *_Iter(__lhs) < *_Iter(__rhs); }
 	};
 
       // Merge nodes from __x into *this. Both lists must be sorted wrt _Cmp.
       template<typename _Cmp>
 	void
-	merge(_List_node_base& __x, _Cmp __comp)
+	merge(_Base& __x, _Cmp __comp)
 	{
-	  _List_node_base* __first1 = _M_next;
-	  _List_node_base* const __last1 = this;
-	  _List_node_base* __first2 = __x._M_next;
-	  _List_node_base* const __last2 = std::__addressof(__x);
+	  _Base_ptr __first1 = this->_M_next;
+	  _Base_ptr const __last1 = this->_M_base();
+	  _Base_ptr __first2 = __x._M_next;
+	  _Base_ptr const __last2 = __x._M_base();
 
 	  while (__first1 != __last1 && __first2 != __last2)
 	    {
 	      if (__comp(__first2, __first1))
 		{
-		  _List_node_base* __next = __first2->_M_next;
+		  _Base_ptr __next = __first2->_M_next;
 		  __first1->_M_transfer(__first2, __next);
 		  __first2 = __next;
 		}
@@ -216,18 +521,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	}
 
       // Splice the node at __i into *this.
-      void _M_take_one(_List_node_base* __i)
+      void _M_take_one(_Base_ptr __i)
       { this->_M_transfer(__i, __i->_M_next); }
 
       // Splice all nodes from *this after __i.
-      void _M_put_all(_List_node_base* __i)
+      void _M_put_all(_Base_ptr __i)
       {
 	if (!empty())
-	  __i->_M_transfer(_M_next, this);
+	  __i->_M_transfer(this->_M_next, this->_M_base());
       }
     };
-
-  } // namespace detail
+} // namespace __list
 
 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
@@ -235,6 +539,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
   template<typename _Tp>
     struct _List_node : public __detail::_List_node_base
     {
+      typedef _List_node* _Node_ptr;
+
 #if __cplusplus >= 201103L
       __gnu_cxx::__aligned_membuf<_Tp> _M_storage;
       _Tp*       _M_valptr()       { return _M_storage._M_ptr(); }
@@ -244,6 +550,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       _Tp*       _M_valptr()       { return std::__addressof(_M_data); }
       _Tp const* _M_valptr() const { return std::__addressof(_M_data); }
 #endif
+
+      _Node_ptr _M_node_ptr() { return this; }
     };
 
   /**
@@ -432,14 +740,17 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
       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 __list::_Node_traits<_Tp, typename _Tp_alloc_traits::pointer>
+	_Node_traits;
       typedef typename _Tp_alloc_traits::template
-	rebind<_List_node<_Tp> >::other _Node_alloc_type;
+	rebind<typename _Node_traits::_Node>::other _Node_alloc_type;
       typedef __gnu_cxx::__alloc_traits<_Node_alloc_type> _Node_alloc_traits;
 
       struct _List_impl
       : public _Node_alloc_type
       {
-	__detail::_List_node_header _M_node;
+	typename _Node_traits::_Node_header _M_node;
 
 	_List_impl() _GLIBCXX_NOEXCEPT_IF(
 	    is_nothrow_default_constructible<_Node_alloc_type>::value)
@@ -485,9 +796,42 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
       _M_get_node()
       { return _Node_alloc_traits::allocate(_M_impl, 1); }
 
+#if __cplusplus < 201103L || _GLIBCXX_USE_ALLOC_PTR_FOR_LIST
       void
       _M_put_node(typename _Node_alloc_traits::pointer __p) _GLIBCXX_NOEXCEPT
       { _Node_alloc_traits::deallocate(_M_impl, __p, 1); }
+#else
+      void
+      _M_put_node(_List_node<_Tp>* __p)
+      {
+	// When not using the allocator's pointer type internally we must
+	// convert between _Node_ptr (i.e. _List_node*) and the allocator's
+	// pointer type.
+	using __alloc_pointer = typename _Node_alloc_traits::pointer;
+	auto __ap = pointer_traits<__alloc_pointer>::pointer_to(*__p);
+	_Node_alloc_traits::deallocate(_M_impl, __ap, 1);
+      }
+#endif
+
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
+      void
+      _M_destroy_node(typename _Node_alloc_traits::pointer __p)
+      {
+#if __cplusplus >= 201103L
+	// Destroy the element
+	_Node_alloc_traits::destroy(_M_impl, __p->_M_valptr());
+	// Only destroy the node if the pointers require it.
+	using _Node = typename _Node_traits::_Node;
+	using _Base_ptr = typename _Node_traits::_Node_base::_Base_ptr;
+	if constexpr (!is_trivially_destructible<_Base_ptr>::value)
+	  __p->~_Node();
+#else
+	_Tp_alloc_type(_M_impl).destroy(__p->_M_valptr());
+#endif
+	this->_M_put_node(__p);
+      }
+#pragma GCC diagnostic pop
 
   public:
       typedef _Alloc allocator_type;
@@ -547,13 +891,24 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
       // so that explicit instantiation declarations of std::list that were
       // compiled with old versions of GCC can still find these old symbols.
 
+      // Use 'if constexpr' so that the functions don't do anything for
+      // specializations using _Node_traits<T, fancy-pointer>, because any
+      // old code referencing these symbols wasn't using the fancy-pointer
+      // specializations.
+
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
+
 # if __cplusplus >= 201103L
       _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 caller must move individual elements.
+#if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST
+	if constexpr (is_same<typename _Tp_alloc_traits::pointer, _Tp*>::value)
+#endif
+	  if (__x._M_get_Node_allocator() == _M_get_Node_allocator())
+	    _M_move_nodes(std::move(__x));
+	  // else caller must move individual elements.
       }
 # endif
 
@@ -561,13 +916,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
       _S_distance(const __detail::_List_node_base* __first,
 		  const __detail::_List_node_base* __last)
       {
-	size_t __n = 0;
-	while (__first != __last)
+#if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST
+	if constexpr (!is_same<typename _Tp_alloc_traits::pointer, _Tp*>::value)
+	  return 0;
+	else
+#endif
 	  {
-	    __first = __first->_M_next;
-	    ++__n;
+	    size_t __n = 0;
+	    while (__first != __last)
+	      {
+		__first = __first->_M_next;
+		++__n;
+	      }
+	    return __n;
 	  }
-	return __n;
       }
 
 #if _GLIBCXX_USE_CXX11_ABI
@@ -584,10 +946,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
       // count the number of nodes
       size_t _M_node_count() const
       {
-	return _S_distance(_M_impl._M_node._M_next,
-			   std::__addressof(_M_impl._M_node));
+#if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST
+	if constexpr (!is_same<typename _Tp_alloc_traits::pointer, _Tp*>::value)
+	  return 0;
+	else
+#endif
+	  return _S_distance(_M_impl._M_node._M_next,
+			     _M_impl._M_node._M_base());
       }
 #endif
+#pragma GCC diagnostic pop
 #endif // ! INLINE_VERSION
     };
 
@@ -663,6 +1031,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
       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;
+      typedef typename _Base::_Node_traits		_Node_traits;
 
     public:
       typedef _Tp					 value_type;
@@ -670,8 +1039,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
       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 typename _Node_traits::_Iterator		 iterator;
+      typedef typename _Node_traits::_Const_iterator	 const_iterator;
       typedef std::reverse_iterator<const_iterator>	 const_reverse_iterator;
       typedef std::reverse_iterator<iterator>		 reverse_iterator;
       typedef size_t					 size_type;
@@ -681,7 +1050,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
     protected:
       // Note that pointers-to-_Node's can be ctor-converted to
       // iterator types.
-      typedef _List_node<_Tp>				 _Node;
+      typedef typename _Node_alloc_traits::pointer	 _Node_ptr;
 
       using _Base::_M_impl;
       using _Base::_M_put_node;
@@ -695,10 +1064,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
        *  @a __args in it.
        */
 #if __cplusplus < 201103L
-      _Node*
+      _Node_ptr
       _M_create_node(const value_type& __x)
       {
-	_Node* __p = this->_M_get_node();
+	_Node_ptr __p = this->_M_get_node();
 	__try
 	  {
 	    _Tp_alloc_type __alloc(_M_get_Node_allocator());
@@ -713,16 +1082,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
       }
 #else
       template<typename... _Args>
-	_Node*
+	_Node_ptr
 	_M_create_node(_Args&&... __args)
 	{
-	  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(),
+	  auto __guard = std::__allocate_guarded_obj(__alloc);
+	  _Node_alloc_traits::construct(__alloc, __guard->_M_valptr(),
 					std::forward<_Args>(__args)...);
-	  __guard = nullptr;
+	  auto __p = __guard.release();
+#if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST
 	  return __p;
+#else
+	  return std::__to_address(__p);
+#endif
 	}
 #endif
 
@@ -1070,7 +1442,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
       _GLIBCXX_NODISCARD
       iterator
       end() _GLIBCXX_NOEXCEPT
-      { return iterator(&this->_M_impl._M_node); }
+      { return iterator(this->_M_impl._M_node._M_base()); }
 
       /**
        *  Returns a read-only (constant) iterator that points one past
@@ -1080,7 +1452,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
       _GLIBCXX_NODISCARD
       const_iterator
       end() const _GLIBCXX_NOEXCEPT
-      { return const_iterator(&this->_M_impl._M_node); }
+      { return const_iterator(this->_M_impl._M_node._M_base()); }
 
       /**
        *  Returns a read/write reverse iterator that points to the last
@@ -1141,7 +1513,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
       [[__nodiscard__]]
       const_iterator
       cend() const noexcept
-      { return const_iterator(&this->_M_impl._M_node); }
+      { return const_iterator(this->_M_impl._M_node._M_base()); }
 
       /**
        *  Returns a read-only (constant) reverse iterator that points to
@@ -1171,7 +1543,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
        */
       _GLIBCXX_NODISCARD bool
       empty() const _GLIBCXX_NOEXCEPT
-      { return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; }
+      {
+	return this->_M_impl._M_node._M_next == this->_M_impl._M_node._M_base();
+      }
 
       /**  Returns the number of elements in the %list.  */
       _GLIBCXX_NODISCARD
@@ -1682,8 +2056,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
       void
       swap(list& __x) _GLIBCXX_NOEXCEPT
       {
-	__detail::_List_node_base::swap(this->_M_impl._M_node,
-					__x._M_impl._M_node);
+	_Node_traits::_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());
@@ -2105,7 +2479,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
       void
       _M_insert(iterator __position, const value_type& __x)
       {
-	_Node* __tmp = _M_create_node(__x);
+	_Node_ptr __tmp = _M_create_node(__x);
 	__tmp->_M_hook(__position._M_node);
 	this->_M_inc_size(1);
       }
@@ -2114,7 +2488,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
        void
        _M_insert(iterator __position, _Args&&... __args)
        {
-	 _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
+	 _Node_ptr __tmp = _M_create_node(std::forward<_Args>(__args)...);
 	 __tmp->_M_hook(__position._M_node);
 	 this->_M_inc_size(1);
        }
@@ -2124,16 +2498,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
       void
       _M_erase(iterator __position) _GLIBCXX_NOEXCEPT
       {
+	typedef typename _Node_traits::_Node _Node;
 	this->_M_dec_size(1);
 	__position._M_node->_M_unhook();
-	_Node* __n = static_cast<_Node*>(__position._M_node);
-#if __cplusplus >= 201103L
-	_Node_alloc_traits::destroy(_M_get_Node_allocator(), __n->_M_valptr());
-#else
-	_Tp_alloc_type(_M_get_Node_allocator()).destroy(__n->_M_valptr());
-#endif
-
-	_M_put_node(__n);
+	_Node& __n = static_cast<_Node&>(*__position._M_node);
+	this->_M_destroy_node(__n._M_node_ptr());
       }
 
       // To implement the splice (and merge) bits of N1599.
@@ -2397,6 +2766,113 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
 	}
       return __n;
     }
+
+#if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST
+  template<bool _Const, typename _Ptr>
+    inline ptrdiff_t
+    __distance(__list::_Iterator<_Const, _Ptr> __first,
+	       __list::_Iterator<_Const, _Ptr> __last,
+	       input_iterator_tag __tag)
+    {
+      using _Tp = typename __list::_Iterator<_Const, _Ptr>::value_type;
+      using _Sentinel = typename __list::_Node_traits<_Tp, _Ptr>::_Node_header;
+      auto __beyond = __last;
+      ++__beyond;
+      const bool __whole = __first == __beyond;
+      if (__builtin_constant_p (__whole) && __whole)
+	return static_cast<const _Sentinel&>(*__last._M_node)._M_size;
+
+      ptrdiff_t __n = 0;
+      while (__first != __last)
+	{
+	  ++__first;
+	  ++__n;
+	}
+      return __n;
+    }
+#endif
+#endif
+
+#if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST
+namespace __list
+{
+  template<typename _VoidPtr>
+    void
+    _Node_base<_VoidPtr>::swap(_Node_base& __x, _Node_base& __y) noexcept
+    {
+      auto __px = pointer_traits<_Base_ptr>::pointer_to(__x);
+      auto __py = pointer_traits<_Base_ptr>::pointer_to(__y);
+
+      if (__x._M_next != __px)
+	{
+	  if (__y._M_next != __py)
+	    {
+	      using std::swap;
+	      // Both __x and __y are not empty.
+	      swap(__x._M_next,__y._M_next);
+	      swap(__x._M_prev,__y._M_prev);
+	      __x._M_next->_M_prev = __x._M_prev->_M_next = __px;
+	      __y._M_next->_M_prev = __y._M_prev->_M_next = __py;
+	    }
+	  else
+	    {
+	      // __x is not empty, __y is empty.
+	      __y._M_next = __x._M_next;
+	      __y._M_prev = __x._M_prev;
+	      __y._M_next->_M_prev = __y._M_prev->_M_next = __py;
+	      __x._M_next = __x._M_prev = __px;
+	    }
+	}
+      else if (__y._M_next != __py)
+	{
+	  // __x is empty, __y is not empty.
+	  __x._M_next = __y._M_next;
+	  __x._M_prev = __y._M_prev;
+	  __x._M_next->_M_prev = __x._M_prev->_M_next = __px;
+	  __y._M_next = __y._M_prev = __py;
+	}
+    }
+
+  template<typename _VoidPtr>
+    void
+    _Node_base<_VoidPtr>::_M_transfer(_Base_ptr const __first,
+				      _Base_ptr const __last)
+    {
+      __glibcxx_assert(__first != __last);
+
+      auto __self = pointer_traits<_Base_ptr>::pointer_to(*this);
+      if (__self != __last)
+	{
+	  // Remove [first, last) from its old position.
+	  __last->_M_prev->_M_next  = __self;
+	  __first->_M_prev->_M_next = __last;
+	  this->_M_prev->_M_next    = __first;
+
+	  // Splice [first, last) into its new position.
+	  auto const __tmp = this->_M_prev;
+	  this->_M_prev    = __last->_M_prev;
+	  __last->_M_prev  = __first->_M_prev;
+	  __first->_M_prev = __tmp;
+	}
+    }
+
+  template<typename _VoidPtr>
+    void
+    _Node_header<_VoidPtr>::_M_reverse() noexcept
+    {
+      const auto __self = this->_M_base();
+      auto __tmp = __self;
+      do
+	{
+	  using std::swap;
+	  swap(__tmp->_M_next, __tmp->_M_prev);
+
+	  // Old next node is now prev.
+	  __tmp = __tmp->_M_prev;
+	}
+      while (__tmp != __self);
+    }
+} // namespace __list
 #endif
 
 _GLIBCXX_END_NAMESPACE_VERSION
diff --git a/libstdc++-v3/testsuite/23_containers/list/capacity/29134.cc b/libstdc++-v3/testsuite/23_containers/list/capacity/29134.cc
index 956afe19dc0..69540d3703b 100644
--- a/libstdc++-v3/testsuite/23_containers/list/capacity/29134.cc
+++ b/libstdc++-v3/testsuite/23_containers/list/capacity/29134.cc
@@ -35,6 +35,11 @@ void test01()
 
   std::allocator<_List_node<int> > a;
   VERIFY( l.max_size() == __gnu_test::max_size(a) );
+
+#if _GLIBCXX_LIST_USE_ALLOC_PTR
+  std::allocator<std::__list::_Node<int*>> b;
+  VERIFY( __gnu_test::max_size(b) == __gnu_test::max_size(a) );
+#endif
 }
 
 int main()
diff --git a/libstdc++-v3/testsuite/23_containers/list/capacity/node_sizes.cc b/libstdc++-v3/testsuite/23_containers/list/capacity/node_sizes.cc
new file mode 100644
index 00000000000..8394824ba28
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/list/capacity/node_sizes.cc
@@ -0,0 +1,24 @@
+// { dg-do compile { target c++11 } }
+
+#include <list>
+
+#if _GLIBCXX_LIST_USE_ALLOC_PTR
+
+#ifdef _GLIBCXX_DEBUG
+namespace C = std::_GLIBCXX_STD_C;
+#else
+namespace C = std;
+#endif
+
+// We use double here because for ADJUST_FIELD_ALIGN targets (like i386)
+// its alignment differs when used as a data member or as a complete object.
+static_assert(sizeof(C::_List_node<double>)
+	      == sizeof(std::__list::_Node<double*>),
+	      "node types have same size");
+static_assert(alignof(C::_List_node<double>)
+	      == alignof(std::__list::_Node<double*>),
+	      "node types have same alignment");
+static_assert(__alignof(C::_List_node<double>)
+	      == __alignof(std::__list::_Node<double*>),
+	      "node types have same preferred alignment");
+#endif
diff --git a/libstdc++-v3/testsuite/23_containers/list/requirements/completeness.cc b/libstdc++-v3/testsuite/23_containers/list/requirements/completeness.cc
new file mode 100644
index 00000000000..ad359e3b51d
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/list/requirements/completeness.cc
@@ -0,0 +1,19 @@
+// { dg-do compile }
+
+// C++17 [list.overview]
+// An incomplete type T may be used when instantiating list if the allocator
+// satisfies the allocator completeness requirements (20.5.3.5.1).
+// T shall be complete before any member of the resulting specialization
+// of list is referenced.
+
+#include <list>
+
+struct Incomplete;
+
+// This instantiates std::list, but none of its members.
+const int sz = sizeof(std::list<Incomplete>);
+
+// Technically the following references a member of std::list, but because
+// our iterators are SCARY it doesn't instantiate any members of std::list.
+// GCC's own source code expects this to work.
+std::list<Incomplete>::iterator i = std::list<Incomplete>::iterator();
diff --git a/libstdc++-v3/testsuite/23_containers/list/requirements/explicit_instantiation/alloc_ptr.cc b/libstdc++-v3/testsuite/23_containers/list/requirements/explicit_instantiation/alloc_ptr.cc
new file mode 100644
index 00000000000..d3b2cfe6d92
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/list/requirements/explicit_instantiation/alloc_ptr.cc
@@ -0,0 +1,87 @@
+// { dg-do compile { target c++11 } }
+
+#include <list>
+#include <testsuite_allocator.h>
+
+// An allocator that uses __gnu_cxx::_Pointer_adapter as its pointer type.
+template class std::list<int, __gnu_test::CustomPointerAlloc<int>>;
+
+// Unlike __gnu_cxx::_Pointer_adapter, this fancy pointer supports neither
+// implicit nor explicit conversions from raw pointers. The constructor from
+// a raw pointer is explicit and requires a second parameter. The only way for
+// containers to construct one of these pointers is pointer_traits::pointer_to.
+template<typename T>
+struct Pointer : __gnu_test::PointerBase<Pointer<T>, T>
+{
+  using Base = __gnu_test::PointerBase<Pointer<T>, T>;
+
+  Pointer() = default;
+  Pointer(std::nullptr_t) : Base() { }
+  explicit Pointer(T* p, int) : Base(p) { }
+
+  // Allow conversions to const_pointer and to void_pointer
+  template<typename U, typename = typename std::enable_if<
+    (!std::is_const<U>::value && std::is_same<T, const U>::value)
+    || (std::is_void<T>::value && std::is_convertible<U*, T*>::value)
+    >::type>
+    Pointer(const Pointer<U>& p) : Base(p.operator->()) { }
+
+  template<typename U>
+    static typename std::enable_if<std::is_same<U, T>::value, Pointer>::type
+    pointer_to(U& t)
+    { return Pointer(std::addressof(t), 1); }
+};
+
+// A minimal allocator that uses Pointer as its pointer type.
+template<typename T>
+struct Allocator
+{
+  using value_type = T;
+  using pointer = Pointer<T>;
+
+  Allocator() = default;
+  template<typename U>
+    Allocator(const Allocator<U>&) { }
+
+  pointer allocate(std::size_t n)
+  { return pointer(std::allocator<T>().allocate(n), 1); }
+
+  void deallocate(pointer p, std::size_t n)
+  {
+    std::allocator<T>().deallocate(p.operator->(), n);
+  }
+
+  bool operator==(const Allocator&) const { return true; }
+  bool operator!=(const Allocator&) const { return false; }
+};
+
+template class std::list<int, Allocator<int>>;
+
+#include <testsuite_iterators.h>
+
+void
+test_template_members(__gnu_test::input_container<short>& c)
+{
+  // Use member functions that are not included in explicit instantiations.
+  std::list<int, Allocator<int>> l(c.begin(), c.end());
+  l.assign(c.begin(), c.end());
+  l.insert(l.begin(), c.begin(), c.end());
+  l.emplace_front(1);
+  l.emplace_back(1);
+  l.emplace(l.begin(), 1);
+  l.remove_if([](int) { return false; });
+  l.unique([](int, int) { return false; });
+  l.merge(l, [](int, int) { return false; });
+  l.merge(std::move(l), [](int, int) { return false; });
+  l.sort([](int, int) { return false; });
+
+#ifdef __glibcxx_ranges_to_container
+  short arr[2];
+  __gnu_test::test_input_range<short> r(arr);
+  std::list<int, Allocator<int>> l2(std::from_range, r);
+  l2.assign_range(r);
+  l2.prepend_range(r);
+  l2.append_range(r);
+  l2.insert_range(l2.begin(), r);
+#endif
+}
diff --git a/libstdc++-v3/testsuite/23_containers/list/requirements/explicit_instantiation/alloc_ptr_ignored.cc b/libstdc++-v3/testsuite/23_containers/list/requirements/explicit_instantiation/alloc_ptr_ignored.cc
new file mode 100644
index 00000000000..e6a499d2716
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/list/requirements/explicit_instantiation/alloc_ptr_ignored.cc
@@ -0,0 +1,4 @@
+// { dg-options "-D_GLIBCXX_LIST_USE_ALLOC_PTR=0" }
+// { dg-do compile { target c++11 } }
+
+#include "alloc_ptr.cc"
-- 
2.47.0



More information about the Libstdc++ mailing list