Pushed
On Sat, 16 Nov 2024 at 23:34, Jonathan Wakely <jwak...@redhat.com> wrote:
>
> 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
>
