Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/2226284/?format=api
{ "id": 2226284, "url": "http://patchwork.ozlabs.org/api/patches/2226284/?format=api", "web_url": "http://patchwork.ozlabs.org/project/gcc/patch/bmm.hhubjjpeho.gcc.gcc-TEST.redi.25.1.3@forge-stage.sourceware.org/", "project": { "id": 17, "url": "http://patchwork.ozlabs.org/api/projects/17/?format=api", "name": "GNU Compiler Collection", "link_name": "gcc", "list_id": "gcc-patches.gcc.gnu.org", "list_email": "gcc-patches@gcc.gnu.org", "web_url": null, "scm_url": null, "webscm_url": null, "list_archive_url": "", "list_archive_url_format": "", "commit_url_format": "" }, "msgid": "<bmm.hhubjjpeho.gcc.gcc-TEST.redi.25.1.3@forge-stage.sourceware.org>", "list_archive_url": null, "date": "2026-04-22T10:36:20", "name": "[v1,3/4] libstdc++: Add fancy pointer support to std::list [PR57272]", "commit_ref": null, "pull_url": null, "state": "new", "archived": false, "hash": "6483d3677617b9687c661573d43a52ee68abe880", "submitter": { "id": 93210, "url": "http://patchwork.ozlabs.org/api/people/93210/?format=api", "name": "Jonathan Wakely via Sourceware Forge", "email": "forge-bot+redi@forge-stage.sourceware.org" }, "delegate": null, "mbox": "http://patchwork.ozlabs.org/project/gcc/patch/bmm.hhubjjpeho.gcc.gcc-TEST.redi.25.1.3@forge-stage.sourceware.org/mbox/", "series": [ { "id": 500985, "url": "http://patchwork.ozlabs.org/api/series/500985/?format=api", "web_url": "http://patchwork.ozlabs.org/project/gcc/list/?series=500985", "date": "2026-04-22T10:36:19", "name": "libstdc++: Add fancy pointer support to std::list and std::forward_list [PR57272]", "version": 1, "mbox": "http://patchwork.ozlabs.org/series/500985/mbox/" } ], "comments": "http://patchwork.ozlabs.org/api/patches/2226284/comments/", "check": "pending", "checks": "http://patchwork.ozlabs.org/api/patches/2226284/checks/", "tags": {}, "related": [], "headers": { "Return-Path": "<gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org>", "X-Original-To": [ "incoming@patchwork.ozlabs.org", "gcc-patches@gcc.gnu.org" ], "Delivered-To": [ "patchwork-incoming@legolas.ozlabs.org", "gcc-patches@gcc.gnu.org" ], "Authentication-Results": [ "legolas.ozlabs.org;\n spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org\n (client-ip=2620:52:6:3111::32; helo=vm01.sourceware.org;\n envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org;\n receiver=patchwork.ozlabs.org)", "sourceware.org; dmarc=none (p=none dis=none)\n header.from=forge-stage.sourceware.org", "sourceware.org;\n spf=pass smtp.mailfrom=forge-stage.sourceware.org", "server2.sourceware.org;\n arc=none smtp.remote-ip=38.145.34.39" ], "Received": [ "from vm01.sourceware.org (vm01.sourceware.org\n [IPv6:2620:52:6:3111::32])\n\t(using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)\n\t key-exchange x25519 server-signature ECDSA (secp384r1) server-digest SHA384)\n\t(No client certificate requested)\n\tby legolas.ozlabs.org (Postfix) with ESMTPS id 4g0xLC31c9z1yD5\n\tfor <incoming@patchwork.ozlabs.org>; Wed, 22 Apr 2026 21:08:51 +1000 (AEST)", "from vm01.sourceware.org (localhost [127.0.0.1])\n\tby sourceware.org (Postfix) with ESMTP id 4786F42D2860\n\tfor <incoming@patchwork.ozlabs.org>; Wed, 22 Apr 2026 11:08:49 +0000 (GMT)", "from forge-stage.sourceware.org (vm08.sourceware.org [38.145.34.39])\n by sourceware.org (Postfix) with ESMTPS id 2DC4542FA7A6\n for <gcc-patches@gcc.gnu.org>; Wed, 22 Apr 2026 10:37:13 +0000 (GMT)", "from forge-stage.sourceware.org (localhost [IPv6:::1])\n (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)\n key-exchange x25519 server-signature ECDSA (prime256v1) server-digest SHA256)\n (No client certificate requested)\n by forge-stage.sourceware.org (Postfix) with ESMTPS id 09ADA42B58\n for <gcc-patches@gcc.gnu.org>; Wed, 22 Apr 2026 10:37:13 +0000 (UTC)" ], "DKIM-Filter": [ "OpenDKIM Filter v2.11.0 sourceware.org 4786F42D2860", "OpenDKIM Filter v2.11.0 sourceware.org 2DC4542FA7A6" ], "DMARC-Filter": "OpenDMARC Filter v1.4.2 sourceware.org 2DC4542FA7A6", "ARC-Filter": "OpenARC Filter v1.0.0 sourceware.org 2DC4542FA7A6", "ARC-Seal": "i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1776854233; cv=none;\n b=G405aR8V9fQDU2xrUoFwMJQ2vhPC6ej6I8SknNGPcSNH3haBjIzszpMSA7JRT+DAYS/mKHhIlRR3HTMsXSvUb+2IjRIQjaUpc5vQKigjRDvQUbxXCzojgbLtIHOaih6PDSUPlCJdM1tco3zpEyJLf1Nq7J9n2kQPvsCgTLih8Gk=", "ARC-Message-Signature": "i=1; a=rsa-sha256; d=sourceware.org; s=key;\n t=1776854233; c=relaxed/simple;\n bh=VwtzMxj6TMVDjCgi3G6KpxA0ZNW2iR2PWy8751teitg=;\n h=From:Date:Subject:To:Message-ID;\n b=wG67QA7ifrAjSnDWBWZ/WtjOvOsAEsvcpgs1btTxHoZnzZq6ZLdtYR/Ax/9mCxLysdWbNOx1YU7g4U1R2aQbbPWGrIdNwweUxIyewgax7mEWhULSSGrbjtANnnVbCJ/Wwgjg4NiaxsERP2xiiOeMaPXbFquKefWBVjo+QPc90xg=", "ARC-Authentication-Results": "i=1; server2.sourceware.org", "From": "Jonathan Wakely via Sourceware Forge\n <forge-bot+redi@forge-stage.sourceware.org>", "Date": "Wed, 22 Apr 2026 10:36:20 +0000", "Subject": "[PATCH v1 3/4] libstdc++: Add fancy pointer support to std::list\n [PR57272]", "To": "gcc-patches mailing list <gcc-patches@gcc.gnu.org>", "Message-ID": "\n <bmm.hhubjjpeho.gcc.gcc-TEST.redi.25.1.3@forge-stage.sourceware.org>", "X-Mailer": "batrachomyomachia", "X-Pull-Request-Organization": "gcc", "X-Pull-Request-Repository": "gcc-TEST", "X-Pull-Request": "https://forge.sourceware.org/gcc/gcc-TEST/pulls/25", "References": "\n <bmm.hhubjjpeho.gcc.gcc-TEST.redi.25.1.0@forge-stage.sourceware.org>", "In-Reply-To": "\n <bmm.hhubjjpeho.gcc.gcc-TEST.redi.25.1.0@forge-stage.sourceware.org>", "X-Patch-URL": "\n https://forge.sourceware.org/redi/gcc/commit/3af34d890e7a10408fa1944406c8633939143ae6", "X-BeenThere": "gcc-patches@gcc.gnu.org", "X-Mailman-Version": "2.1.30", "Precedence": "list", "List-Id": "Gcc-patches mailing list <gcc-patches.gcc.gnu.org>", "List-Unsubscribe": "<https://gcc.gnu.org/mailman/options/gcc-patches>,\n <mailto:gcc-patches-request@gcc.gnu.org?subject=unsubscribe>", "List-Archive": "<https://gcc.gnu.org/pipermail/gcc-patches/>", "List-Post": "<mailto:gcc-patches@gcc.gnu.org>", "List-Help": "<mailto:gcc-patches-request@gcc.gnu.org?subject=help>", "List-Subscribe": "<https://gcc.gnu.org/mailman/listinfo/gcc-patches>,\n <mailto:gcc-patches-request@gcc.gnu.org?subject=subscribe>", "Reply-To": "gcc-patches mailing list <gcc-patches@gcc.gnu.org>, redi@gcc.gnu.org", "Errors-To": "gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org" }, "content": "From: Jonathan Wakely <jwakely@redhat.com>\n\nCurrently std::list uses raw pointers to connect its nodes, which is\nnon-conforming. We should use the allocator's pointer type everywhere\nthat a \"pointer\" is needed.\n\nBecause the existing types like _List_node<T> are part of the ABI now,\nwe can't change them. To support nodes that are connected by fancy\npointers we need a parallel hierarchy of node types. This change\nintroduces new class templates parameterized on the allocator's\nvoid_pointer type, __list::_Node_base and __list::_Node_header, and new\nclass templates parameterized on the allocator's pointer type,\n__list::Node, __list::_Iterator. The iterator class template is used for\nboth iterator and const_iterator. Whether std::list<T, A> should use the\nold _List_node<T> or new _list::_Node<A::pointer> type family internally\nis controlled by a new __list::_Node_traits traits template.\n\nBecause std::pointer_traits and std::__to_address are not defined for\nC++98, there is no way to support fancy pointers in C++98. For C++98 the\n_Node_traits traits always choose the old _List_node family.\n\nIn case anybody is currently using std::list with an allocator that has\na fancy pointer, this change would be an ABI break, because their\nstd::list instantiations would start to (correctly) use the fancy\npointer type. If the fancy pointer just contains a single pointer and so\nhas the same size, layout, and object represenation as a raw pointer,\nthe code might still work (despite being an ODR violation). But if their\nfancy pointer has a different representation, they would need to\nrecompile all their code using that allocator with std::list. Because\nstd::list will never use fancy pointers in C++98 mode, recompiling\neverything to use fancy pointers isn't even possible if mixing C++98 and\nC++11 code that uses std::list. To alleviate this problem, compiling\nwith -D_GLIBCXX_USE_ALLOC_PTR_FOR_LIST=0 will force std::list to have\nthe old, non-conforming behaviour and use raw pointers internally. For\ntesting purposes, compiling with -D_GLIBCXX_USE_ALLOC_PTR_FOR_LIST=9001\nwill force std::list to always use the new node types. This macro is\ncurrently undocumented, which needs to be fixed.\n\nThe original _List_node<T> type is trivially constructible and trivially\ndestructible, but the new __list::_Node<Ptr> type might not be,\ndepending on the fancy pointer data members in _Node_base. This means\nthat std::list needs to explicitly construct and destroy the node\nobject, not just the value that it contains. This commit adds a new\n__allocated_obj helper which wraps an __allocated_ptr and additionally\nconstructs and destroys an object in the allocated storage.\n\nPretty printers for std::list need to be updated to handle the new node\ntypes.\n\nlibstdc++-v3/ChangeLog:\n\n\tPR libstdc++/57272\n\tPR libstdc++/110952\n\t* include/bits/allocated_ptr.h (__allocated_ptr::get): Add\n\tconst.\n\t(__allocated_ptr::operator bool, __allocated_ptr::release): New\n\tmember functions.\n\t(__allocate_guarded): Add inline.\n\t(__allocated_obj): New class template.\n\t(__allocate_guarded_obj): New function template.\n\t* include/bits/list.tcc (_List_base::_M_clear()): Replace uses\n\tof raw pointers. Use _M_destroy_node.\n\t(list::emplace, list::insert): Likewise.\n\t(list::sort): Adjust check for 0 or 1 wsize. Use template\n\targument list for _Scratch_list.\n\t* include/bits/stl_list.h (_GLIBCXX_USE_ALLOC_PTR_FOR_LIST):\n\tDefine.\n\t(_List_node_base::_Base_ptr): New typedef.\n\t(_List_node_base::_M_base): New member functions.\n\t(_List_node_header::_M_base): Make public and add\n\tusing-declaration for base class overload.\n\t(__list::_Node_traits, __list::_Node_base)\n\t(__list::_Node_header, __list::_Node, __list::_Iterator): New\n\tclass templates.\n\t(_Scratch_list): Turn class into class template. Use _Base_ptr\n\ttypedef instead of _List_node_base*.\n\t(_List_node::_Node_ptr): New typedef.\n\t(_List_node::_M_node_ptr): New member function.\n\t(_List_base, _List_impl): Use _Node_traits to get node types.\n\t(_List_base::_M_put_node): Convert to fancy pointer if needed.\n\t(_List_base::_M_destroy_node): New member function.\n\t(_List_base(_List_base&&, _Node_alloc_type&&)): Use if constexpr\n\tto make function a no-op for fancy pointers.\n\t(_List_base::_S_distance, _List_base::_M_distance)\n\t(_List_base::_M_node_count): Likewise.\n\t(list): Use _Node_traits to get iterator, node and pointer\n\ttypes.\n\t(list::_M_create_node): Use _Node_ptr typedef instead of _Node*.\n\tUse __allocate_guarded_obj instead of _M_get_node.\n\t(list::end, list::cend, list::empty): Use node header's\n\t_M_base() function instead of taking its address.\n\t(list::swap): Use _Node_traits to get node base type.\n\t(list::_M_create_node, list::_M_insert): Use _Node_ptr instead\n\tof _Node*.\n\t(list::_M_erase): Likewise. Use _M_destroy_node.\n\t(__distance): Overload for __list::_Iterator.\n\t(_Node_base::swap, _Node_base::_M_transfer): Define non-inline\n\tmember functions of class templates.\n\t(_Node_header::_M_reverse): Likewise.\n\t* testsuite/23_containers/list/capacity/29134.cc: Check max_size\n\tfor allocator of new node type.\n\t* testsuite/23_containers/list/capacity/node_sizes.cc: New test.\n\t* testsuite/23_containers/list/requirements/explicit_instantiation/alloc_ptr.cc:\n\tNew test.\n\t* testsuite/23_containers/list/requirements/explicit_instantiation/alloc_ptr_ignored.cc:\n\tNew test.\n---\n libstdc++-v3/include/bits/allocated_ptr.h | 44 +-\n libstdc++-v3/include/bits/list.tcc | 52 +-\n libstdc++-v3/include/bits/stl_list.h | 596 ++++++++++++++++--\n .../23_containers/list/capacity/29134.cc | 5 +\n .../23_containers/list/capacity/node_sizes.cc | 24 +\n .../list/requirements/completeness.cc | 19 +\n .../explicit_instantiation/alloc_ptr.cc | 87 +++\n .../alloc_ptr_ignored.cc | 4 +\n 8 files changed, 743 insertions(+), 88 deletions(-)\n create mode 100644 libstdc++-v3/testsuite/23_containers/list/capacity/node_sizes.cc\n create mode 100644 libstdc++-v3/testsuite/23_containers/list/requirements/completeness.cc\n create mode 100644 libstdc++-v3/testsuite/23_containers/list/requirements/explicit_instantiation/alloc_ptr.cc\n create mode 100644 libstdc++-v3/testsuite/23_containers/list/requirements/explicit_instantiation/alloc_ptr_ignored.cc", "diff": "diff --git a/libstdc++-v3/include/bits/allocated_ptr.h b/libstdc++-v3/include/bits/allocated_ptr.h\nindex 26a07a1d34f2..3d0f62bfa9fa 100644\n--- a/libstdc++-v3/include/bits/allocated_ptr.h\n+++ b/libstdc++-v3/include/bits/allocated_ptr.h\n@@ -82,22 +82,60 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \treturn *this;\n }\n \n+ explicit operator bool() const noexcept { return (bool)_M_ptr; }\n+\n /// Get the address that the owned pointer refers to.\n- value_type* get() { return std::__to_address(_M_ptr); }\n+ value_type* get() const { return std::__to_address(_M_ptr); }\n+\n+ pointer release() { return std::__exchange(_M_ptr, nullptr); }\n \n private:\n _Alloc* _M_alloc;\n pointer _M_ptr;\n };\n \n- /// Allocate space for a single object using __a\n+ /// Allocate space for a single object using __a.\n template<typename _Alloc>\n- __allocated_ptr<_Alloc>\n+ inline __allocated_ptr<_Alloc>\n __allocate_guarded(_Alloc& __a)\n {\n return { __a, std::allocator_traits<_Alloc>::allocate(__a, 1) };\n }\n \n+ /// RAII type for constructing/destroying an object with an allocated pointer\n+ template<typename _Alloc>\n+ struct __allocated_obj : __allocated_ptr<_Alloc>\n+ {\n+ using value_type = typename __allocated_ptr<_Alloc>::value_type;\n+\n+ __allocated_obj(__allocated_obj<_Alloc>&&) = default;\n+\n+ // Default-initialize a value_type at *__ptr\n+ __allocated_obj(__allocated_ptr<_Alloc>&& __ptr)\n+ : __allocated_ptr<_Alloc>(std::move(__ptr))\n+ { ::new ((void*)this->get()) value_type; }\n+\n+ // Call the destructor if an object is owned.\n+ ~__allocated_obj()\n+ {\n+\tif (static_cast<bool>(*this))\n+\t this->get()->~value_type();\n+ }\n+\n+ using __allocated_ptr<_Alloc>::operator=;\n+\n+ value_type& operator*() const { return *this->get(); }\n+ value_type* operator->() const { return this->get(); }\n+ };\n+\n+ /// Construct an object in storage allocated using __a.\n+ template<typename _Alloc>\n+ inline __allocated_obj<_Alloc>\n+ __allocate_guarded_obj(_Alloc& __a)\n+ {\n+ return { std::__allocate_guarded(__a) };\n+ }\n+\n /// @endcond\n _GLIBCXX_END_NAMESPACE_VERSION\n } // namespace std\ndiff --git a/libstdc++-v3/include/bits/list.tcc b/libstdc++-v3/include/bits/list.tcc\nindex 65835c1379f4..2102e15eec23 100644\n--- a/libstdc++-v3/include/bits/list.tcc\n+++ b/libstdc++-v3/include/bits/list.tcc\n@@ -66,19 +66,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER\n _List_base<_Tp, _Alloc>::\n _M_clear() _GLIBCXX_NOEXCEPT\n {\n- typedef _List_node<_Tp> _Node;\n- __detail::_List_node_base* __cur = _M_impl._M_node._M_next;\n- while (__cur != &_M_impl._M_node)\n+ typedef typename _Node_traits::_Node _Node;\n+ typedef typename _Node_traits::_Node_base _Node_base;\n+ typename _Node_base::_Base_ptr __cur = _M_impl._M_node._M_next;\n+ while (__cur != _M_impl._M_node._M_base())\n \t{\n-\t _Node* __tmp = static_cast<_Node*>(__cur);\n-\t __cur = __tmp->_M_next;\n-\t _Tp* __val = __tmp->_M_valptr();\n-#if __cplusplus >= 201103L\n-\t _Node_alloc_traits::destroy(_M_get_Node_allocator(), __val);\n-#else\n-\t _Tp_alloc_type(_M_get_Node_allocator()).destroy(__val);\n-#endif\n-\t _M_put_node(__tmp);\n+\t _Node& __tmp = static_cast<_Node&>(*__cur);\n+\t __cur = __tmp._M_next;\n+\t this->_M_destroy_node(__tmp._M_node_ptr());\n \t}\n }\n \n@@ -89,10 +84,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER\n list<_Tp, _Alloc>::\n emplace(const_iterator __position, _Args&&... __args)\n {\n-\t_Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);\n+\t_Node_ptr __tmp = _M_create_node(std::forward<_Args>(__args)...);\n \t__tmp->_M_hook(__position._M_const_cast()._M_node);\n \tthis->_M_inc_size(1);\n-\treturn iterator(__tmp);\n+\treturn iterator(__tmp->_M_base());\n }\n #endif\n \n@@ -105,10 +100,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER\n insert(iterator __position, const value_type& __x)\n #endif\n {\n- _Node* __tmp = _M_create_node(__x);\n+ _Node_ptr __tmp = _M_create_node(__x);\n __tmp->_M_hook(__position._M_const_cast()._M_node);\n this->_M_inc_size(1);\n- return iterator(__tmp);\n+ return iterator(__tmp->_M_base());\n }\n \n #if __cplusplus >= 201103L\n@@ -482,10 +477,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER\n sort()\n {\n // Do nothing if the list has length 0 or 1.\n- if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node\n-\t && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)\n+ if (empty() || ++begin() == end())\n+\treturn;\n+\n {\n-\tusing __detail::_Scratch_list;\n+\ttypedef __list::_Scratch_list<typename _Node_traits::_Node_base>\n+\t _Scratch_list;\n+\n \t// The algorithm used here is largely unchanged from the SGI STL\n \t// and is described in The C++ Standard Template Library by Plauger,\n \t// Stepanov, Lee, Musser.\n@@ -499,7 +497,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER\n \t_Scratch_list* __fill = __tmp;\n \t_Scratch_list* __counter;\n \n-\t_Scratch_list::_Ptr_cmp<iterator, void> __ptr_comp;\n+\ttypename _Scratch_list::template _Ptr_cmp<iterator, void> __ptr_comp;\n \n \t__try\n \t {\n@@ -614,17 +612,21 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER\n sort(_StrictWeakOrdering __comp)\n {\n \t// Do nothing if the list has length 0 or 1.\n-\tif (this->_M_impl._M_node._M_next != &this->_M_impl._M_node\n-\t && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)\n+\tif (empty() || ++begin() == end())\n+\t return;\n+\n \t{\n-\t using __detail::_Scratch_list;\n+\t typedef __list::_Scratch_list<typename _Node_traits::_Node_base>\n+\t _Scratch_list;\n+\n \t _Scratch_list __carry;\n \t _Scratch_list __tmp[64];\n \t _Scratch_list* __fill = __tmp;\n \t _Scratch_list* __counter;\n \n-\t_Scratch_list::_Ptr_cmp<iterator, _StrictWeakOrdering> __ptr_comp\n-\t = { __comp };\n+\t typename _Scratch_list::\n+\t template _Ptr_cmp<iterator, _StrictWeakOrdering> __ptr_comp\n+\t = { __comp };\n \n \t __try\n \t {\ndiff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h\nindex b1ab335ba4c9..ddca579033f8 100644\n--- a/libstdc++-v3/include/bits/stl_list.h\n+++ b/libstdc++-v3/include/bits/stl_list.h\n@@ -62,6 +62,7 @@\n #if __cplusplus >= 201103L\n #include <initializer_list>\n #include <bits/allocated_ptr.h>\n+#include <bits/ptr_traits.h>\n #include <ext/aligned_buffer.h>\n #endif\n #if __glibcxx_ranges_to_container // C++ >= 23\n@@ -69,6 +70,13 @@\n # include <bits/ranges_util.h> // ranges::subrange\n #endif\n \n+#if __cplusplus < 201103L\n+# undef _GLIBCXX_USE_ALLOC_PTR_FOR_LIST\n+# define _GLIBCXX_USE_ALLOC_PTR_FOR_LIST 0\n+#elif ! defined _GLIBCXX_USE_ALLOC_PTR_FOR_LIST\n+# define _GLIBCXX_USE_ALLOC_PTR_FOR_LIST 1\n+#endif\n+\n namespace std _GLIBCXX_VISIBILITY(default)\n {\n _GLIBCXX_BEGIN_NAMESPACE_VERSION\n@@ -84,6 +92,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n /// Common part of a node in the %list.\n struct _List_node_base\n {\n+ typedef _List_node_base* _Base_ptr;\n+\n _List_node_base* _M_next;\n _List_node_base* _M_prev;\n \n@@ -102,6 +112,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \n void\n _M_unhook() _GLIBCXX_USE_NOEXCEPT;\n+\n+ _List_node_base* _M_base() { return this; }\n+ const _List_node_base* _M_base() const { return this; }\n };\n \n struct _List_size\n@@ -112,7 +125,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n #endif\n };\n \n-\n /// The %list node header.\n struct _List_node_header : public _List_node_base, _List_size\n {\n@@ -157,18 +169,313 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t_List_size::operator=(_List_size());\n }\n \n+ using _List_node_base::_M_base;\n+#if ! _GLIBCXX_INLINE_VERSION\n+ _List_node_base* _M_base() { return this; } // XXX GLIBCXX_ABI Deprecated\n+#endif\n+ };\n+\n+ } // namespace detail\n+\n+#if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST\n+_GLIBCXX_BEGIN_NAMESPACE_CONTAINER\n+_GLIBCXX_BEGIN_NAMESPACE_CXX11\n+ template<typename _Tp, typename _Allocator> class list;\n+_GLIBCXX_END_NAMESPACE_CXX11\n+_GLIBCXX_END_NAMESPACE_CONTAINER\n+\n+namespace __list\n+{\n+ // The base class for a list node. Contains the pointers connecting nodes.\n+ template<typename _VoidPtr>\n+ struct _Node_base\n+ {\n+ using _Base_ptr = __ptr_rebind<_VoidPtr, _Node_base>;\n+ _Base_ptr _M_next;\n+ _Base_ptr _M_prev;\n+\n+ static void\n+ swap(_Node_base& __x, _Node_base& __y) noexcept;\n+\n+ void\n+ _M_transfer(_Base_ptr const __first, _Base_ptr const __last);\n+\n+ void\n+ _M_hook(_Base_ptr const __position) noexcept\n+ {\n+\tauto __self = pointer_traits<_Base_ptr>::pointer_to(*this);\n+\tthis->_M_next = __position;\n+\tthis->_M_prev = __position->_M_prev;\n+\t__position->_M_prev->_M_next = __self;\n+\t__position->_M_prev = __self;\n+ }\n+\n+ void\n+ _M_unhook() noexcept\n+ {\n+\tauto const __next_node = this->_M_next;\n+\tauto const __prev_node = this->_M_prev;\n+\t__prev_node->_M_next = __next_node;\n+\t__next_node->_M_prev = __prev_node;\n+ }\n+\n+ // This is not const-correct, but it's only used in a const access path\n+ // by std::list::empty(), where it doesn't escape, and by\n+ // std::list::end() const, where the pointer is used to initialize a\n+ // const_iterator and so constness is restored.\n+ _Base_ptr\n+ _M_base() const noexcept\n+ {\n+\treturn pointer_traits<_Base_ptr>::\n+\t\t pointer_to(const_cast<_Node_base&>(*this));\n+ }\n+ };\n+\n+ using ::std::__detail::_List_size;\n+\n+ // The special sentinel node contained by a std::list.\n+ // begin()->_M_node->_M_prev and end()->_M_node point to this header.\n+ // This is not a complete node, as it doesn't contain a value.\n+ template<typename _VoidPtr>\n+ struct _Node_header\n+ : public _Node_base<_VoidPtr>, _List_size\n+ {\n+ _Node_header() noexcept\n+ { _M_init(); }\n+\n+ _Node_header(_Node_header&& __x) noexcept\n+ : _Node_base<_VoidPtr>(__x), _List_size(__x)\n+ {\n+\tif (__x._M_base()->_M_next == __x._M_base())\n+\t this->_M_next = this->_M_prev = this->_M_base();\n+\telse\n+\t {\n+\t this->_M_next->_M_prev = this->_M_prev->_M_next = this->_M_base();\n+\t __x._M_init();\n+\t }\n+ }\n+\n+ void\n+ _M_move_nodes(_Node_header&& __x) noexcept\n+ {\n+\tauto const __xnode = __x._M_base();\n+\tif (__xnode->_M_next == __xnode)\n+\t _M_init();\n+\telse\n+\t {\n+\t auto const __node = this->_M_base();\n+\t __node->_M_next = __xnode->_M_next;\n+\t __node->_M_prev = __xnode->_M_prev;\n+\t __node->_M_next->_M_prev = __node->_M_prev->_M_next = __node;\n+\t _List_size::operator=(__x);\n+\t __x._M_init();\n+\t }\n+ }\n+\n+ void\n+ _M_init() noexcept\n+ {\n+\tthis->_M_next = this->_M_prev = this->_M_base();\n+\t_List_size::operator=(_List_size());\n+ }\n+\n+ void _M_reverse() noexcept;\n+ };\n+\n+ // The node type used for allocators with fancy pointers.\n+ template<typename _ValPtr>\n+ struct _Node : public __list::_Node_base<__ptr_rebind<_ValPtr, void>>\n+ {\n+ using value_type = typename pointer_traits<_ValPtr>::element_type;\n+ using _Node_ptr = __ptr_rebind<_ValPtr, _Node>;\n+\n+ union {\n+\tvalue_type _M_data;\n+ };\n+\n+ _Node() { }\n+ ~_Node() { }\n+ _Node(_Node&&) = delete;\n+\n+ value_type* _M_valptr() { return std::__addressof(_M_data); }\n+ value_type const* _M_valptr() const { return std::__addressof(_M_data); }\n+\n+ _Node_ptr\n+ _M_node_ptr()\n+ { return pointer_traits<_Node_ptr>::pointer_to(*this); }\n+ };\n+\n+ template<bool _Const, typename _Ptr> class _Iterator;\n+\n+ template<bool _Const, typename _Ptr>\n+ class _Iterator\n+ {\n+ using _Node = __list::_Node<_Ptr>;\n+ using _Base_ptr\n+\t= typename __list::_Node_base<__ptr_rebind<_Ptr, void>>::_Base_ptr;\n+\n+ template<typename _Tp>\n+\tusing __maybe_const = __conditional_t<_Const, const _Tp, _Tp>;\n+\n+ public:\n+ using value_type = typename pointer_traits<_Ptr>::element_type;\n+ using difference_type = ptrdiff_t;\n+ using iterator_category = bidirectional_iterator_tag;\n+ using pointer = __maybe_const<value_type>*;\n+ using reference = __maybe_const<value_type>&;\n+\n+ constexpr _Iterator() noexcept : _M_node() { }\n+\n+ _Iterator(const _Iterator&) = default;\n+ _Iterator& operator=(const _Iterator&) = default;\n+\n+#ifdef __glibcxx_concepts\n+ constexpr\n+ _Iterator(const _Iterator<false, _Ptr>& __i) requires _Const\n+#else\n+ template<bool _OtherConst,\n+\t typename = __enable_if_t<_Const && !_OtherConst>>\n+\tconstexpr\n+\t_Iterator(const _Iterator<_OtherConst, _Ptr>& __i)\n+#endif\n+\t: _M_node(__i._M_node) { }\n+\n+ constexpr explicit\n+ _Iterator(_Base_ptr __x) noexcept\n+ : _M_node(__x) { }\n+\n+ // Must downcast from _Node_base to _Node to get to value.\n+ [[__nodiscard__]]\n+ constexpr reference\n+ operator*() const noexcept\n+ { return static_cast<_Node&>(*_M_node)._M_data; }\n+\n+ [[__nodiscard__]]\n+ constexpr pointer\n+ operator->() const noexcept\n+ { return std::__addressof(operator*()); }\n+\n+ _GLIBCXX14_CONSTEXPR _Iterator&\n+ operator++() noexcept\n+ {\n+\t_M_node = _M_node->_M_next;\n+\treturn *this;\n+ }\n+\n+ _GLIBCXX14_CONSTEXPR _Iterator\n+ operator++(int) noexcept\n+ {\n+\tauto __tmp = *this;\n+\t_M_node = _M_node->_M_next;\n+\treturn __tmp;\n+ }\n+\n+ _GLIBCXX14_CONSTEXPR _Iterator&\n+ operator--() noexcept\n+ {\n+\t_M_node = _M_node->_M_prev;\n+\treturn *this;\n+ }\n+\n+ _GLIBCXX14_CONSTEXPR _Iterator\n+ operator--(int) noexcept\n+ {\n+\tauto __tmp = *this;\n+\t_M_node = _M_node->_M_prev;\n+\treturn __tmp;\n+ }\n+\n+ [[__nodiscard__]]\n+ friend constexpr bool\n+ operator==(const _Iterator& __x, const _Iterator& __y) noexcept\n+ { return __x._M_node == __y._M_node; }\n+\n+#if __cpp_impl_three_way_comparison < 201907L\n+ [[__nodiscard__]]\n+ friend constexpr bool\n+ operator!=(const _Iterator& __x, const _Iterator& __y) noexcept\n+ { return __x._M_node != __y._M_node; }\n+#endif\n+\n private:\n- _List_node_base* _M_base() { return this; }\n+ template<typename _Tp, typename _Allocator>\n+\tfriend class _GLIBCXX_STD_C::list;\n+\n+ friend _Iterator<!_Const, _Ptr>;\n+\n+ constexpr _Iterator<false, _Ptr>\n+ _M_const_cast() const noexcept\n+ { return _Iterator<false, _Ptr>(_M_node); }\n+\n+ _Base_ptr _M_node;\n };\n+} // namespace __list\n+#endif // USE_ALLOC_PTR_FOR_LIST\n \n- // Used by list::sort to hold nodes being sorted.\n- struct _Scratch_list : _List_node_base\n+_GLIBCXX_BEGIN_NAMESPACE_CONTAINER\n+ template<typename _Tp> struct _List_node;\n+ template<typename _Tp> struct _List_iterator;\n+ template<typename _Tp> struct _List_const_iterator;\n+_GLIBCXX_END_NAMESPACE_CONTAINER\n+\n+namespace __list\n+{\n+ // Determine the node and iterator types used by std::list.\n+ template<typename _Tp, typename _Ptr>\n+ struct _Node_traits;\n+\n+#if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST <= 9000\n+ // Specialization for the simple case where the allocator's pointer type\n+ // is the same type as value_type*.\n+ // For ABI compatibility we can't change the types used for this case.\n+ template<typename _Tp>\n+ struct _Node_traits<_Tp, _Tp*>\n {\n- _Scratch_list() { _M_next = _M_prev = this; }\n+ typedef __detail::_List_node_base\t\t\t_Node_base;\n+ typedef __detail::_List_node_header\t\t_Node_header;\n+ typedef _GLIBCXX_STD_C::_List_node<_Tp>\t\t_Node;\n+ typedef _GLIBCXX_STD_C::_List_iterator<_Tp>\t_Iterator;\n+ typedef _GLIBCXX_STD_C::_List_const_iterator<_Tp>\t_Const_iterator;\n+ };\n+#endif\n \n- bool empty() const { return _M_next == this; }\n+#if ! _GLIBCXX_USE_ALLOC_PTR_FOR_LIST\n+ // Always use the T* specialization.\n+ template<typename _Tp, typename _Ptr>\n+ struct _Node_traits\n+ : _Node_traits<_Tp, _Tp*>\n+ { };\n+#else\n+ // Primary template used when the allocator uses fancy pointers.\n+ template<typename _Tp, typename _Ptr>\n+ struct _Node_traits\n+ {\n+ private:\n+ using _VoidPtr = __ptr_rebind<_Ptr, void>;\n+ using _ValPtr = __ptr_rebind<_Ptr, _Tp>;\n \n- void swap(_List_node_base& __l) { _List_node_base::swap(*this, __l); }\n+ public:\n+ using _Node_base = __list::_Node_base<_VoidPtr>;\n+ using _Node_header = __list::_Node_header<_VoidPtr>;\n+ using _Node = __list::_Node<_ValPtr>;\n+ using _Iterator = __list::_Iterator<false, _ValPtr>;\n+ using _Const_iterator = __list::_Iterator<true, _ValPtr>;\n+ };\n+#endif // USE_ALLOC_PTR_FOR_LIST\n+\n+ // Used by std::list::sort to hold nodes being sorted.\n+ template<typename _NodeBaseT>\n+ struct _Scratch_list\n+ : _NodeBaseT\n+ {\n+ typedef _NodeBaseT _Base;\n+ typedef typename _Base::_Base_ptr _Base_ptr;\n+\n+ _Scratch_list() { this->_M_next = this->_M_prev = this->_M_base(); }\n+\n+ bool empty() const { return this->_M_next == this->_M_base(); }\n+\n+ void swap(_Base& __l) { _Base::swap(*this, __l); }\n \n template<typename _Iter, typename _Cmp>\n \tstruct _Ptr_cmp\n@@ -176,8 +483,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t _Cmp _M_cmp;\n \n \t bool\n-\t operator()(__detail::_List_node_base* __lhs,\n-\t\t __detail::_List_node_base* __rhs) /* not const */\n+\t operator()(_Base_ptr __lhs, _Base_ptr __rhs) /* not const */\n \t { return _M_cmp(*_Iter(__lhs), *_Iter(__rhs)); }\n \t};\n \n@@ -185,26 +491,25 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \tstruct _Ptr_cmp<_Iter, void>\n \t{\n \t bool\n-\t operator()(__detail::_List_node_base* __lhs,\n-\t\t __detail::_List_node_base* __rhs) const\n+\t operator()(_Base_ptr __lhs, _Base_ptr __rhs) const\n \t { return *_Iter(__lhs) < *_Iter(__rhs); }\n \t};\n \n // Merge nodes from __x into *this. Both lists must be sorted wrt _Cmp.\n template<typename _Cmp>\n \tvoid\n-\tmerge(_List_node_base& __x, _Cmp __comp)\n+\tmerge(_Base& __x, _Cmp __comp)\n \t{\n-\t _List_node_base* __first1 = _M_next;\n-\t _List_node_base* const __last1 = this;\n-\t _List_node_base* __first2 = __x._M_next;\n-\t _List_node_base* const __last2 = std::__addressof(__x);\n+\t _Base_ptr __first1 = this->_M_next;\n+\t _Base_ptr const __last1 = this->_M_base();\n+\t _Base_ptr __first2 = __x._M_next;\n+\t _Base_ptr const __last2 = __x._M_base();\n \n \t while (__first1 != __last1 && __first2 != __last2)\n \t {\n \t if (__comp(__first2, __first1))\n \t\t{\n-\t\t _List_node_base* __next = __first2->_M_next;\n+\t\t _Base_ptr __next = __first2->_M_next;\n \t\t __first1->_M_transfer(__first2, __next);\n \t\t __first2 = __next;\n \t\t}\n@@ -216,18 +521,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t}\n \n // Splice the node at __i into *this.\n- void _M_take_one(_List_node_base* __i)\n+ void _M_take_one(_Base_ptr __i)\n { this->_M_transfer(__i, __i->_M_next); }\n \n // Splice all nodes from *this after __i.\n- void _M_put_all(_List_node_base* __i)\n+ void _M_put_all(_Base_ptr __i)\n {\n \tif (!empty())\n-\t __i->_M_transfer(_M_next, this);\n+\t __i->_M_transfer(this->_M_next, this->_M_base());\n }\n };\n-\n- } // namespace detail\n+} // namespace __list\n \n _GLIBCXX_BEGIN_NAMESPACE_CONTAINER\n \n@@ -235,6 +539,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER\n template<typename _Tp>\n struct _List_node : public __detail::_List_node_base\n {\n+ typedef _List_node* _Node_ptr;\n+\n #if __cplusplus >= 201103L\n __gnu_cxx::__aligned_membuf<_Tp> _M_storage;\n _Tp* _M_valptr() { return _M_storage._M_ptr(); }\n@@ -244,6 +550,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER\n _Tp* _M_valptr() { return std::__addressof(_M_data); }\n _Tp const* _M_valptr() const { return std::__addressof(_M_data); }\n #endif\n+\n+ _Node_ptr _M_node_ptr() { return this; }\n };\n \n /**\n@@ -432,14 +740,17 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11\n typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template\n \trebind<_Tp>::other\t\t\t\t_Tp_alloc_type;\n typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type>\t_Tp_alloc_traits;\n+\n+ typedef __list::_Node_traits<_Tp, typename _Tp_alloc_traits::pointer>\n+\t_Node_traits;\n typedef typename _Tp_alloc_traits::template\n-\trebind<_List_node<_Tp> >::other _Node_alloc_type;\n+\trebind<typename _Node_traits::_Node>::other _Node_alloc_type;\n typedef __gnu_cxx::__alloc_traits<_Node_alloc_type> _Node_alloc_traits;\n \n struct _List_impl\n : public _Node_alloc_type\n {\n-\t__detail::_List_node_header _M_node;\n+\ttypename _Node_traits::_Node_header _M_node;\n \n \t_List_impl() _GLIBCXX_NOEXCEPT_IF(\n \t is_nothrow_default_constructible<_Node_alloc_type>::value)\n@@ -485,9 +796,42 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11\n _M_get_node()\n { return _Node_alloc_traits::allocate(_M_impl, 1); }\n \n+#if __cplusplus < 201103L || _GLIBCXX_USE_ALLOC_PTR_FOR_LIST\n void\n _M_put_node(typename _Node_alloc_traits::pointer __p) _GLIBCXX_NOEXCEPT\n { _Node_alloc_traits::deallocate(_M_impl, __p, 1); }\n+#else\n+ void\n+ _M_put_node(_List_node<_Tp>* __p)\n+ {\n+\t// When not using the allocator's pointer type internally we must\n+\t// convert between _Node_ptr (i.e. _List_node*) and the allocator's\n+\t// pointer type.\n+\tusing __alloc_pointer = typename _Node_alloc_traits::pointer;\n+\tauto __ap = pointer_traits<__alloc_pointer>::pointer_to(*__p);\n+\t_Node_alloc_traits::deallocate(_M_impl, __ap, 1);\n+ }\n+#endif\n+\n+#pragma GCC diagnostic push\n+#pragma GCC diagnostic ignored \"-Wc++17-extensions\" // if constexpr\n+ void\n+ _M_destroy_node(typename _Node_alloc_traits::pointer __p)\n+ {\n+#if __cplusplus >= 201103L\n+\t// Destroy the element\n+\t_Node_alloc_traits::destroy(_M_impl, __p->_M_valptr());\n+\t// Only destroy the node if the pointers require it.\n+\tusing _Node = typename _Node_traits::_Node;\n+\tusing _Base_ptr = typename _Node_traits::_Node_base::_Base_ptr;\n+\tif constexpr (!is_trivially_destructible<_Base_ptr>::value)\n+\t __p->~_Node();\n+#else\n+\t_Tp_alloc_type(_M_impl).destroy(__p->_M_valptr());\n+#endif\n+\tthis->_M_put_node(__p);\n+ }\n+#pragma GCC diagnostic pop\n \n public:\n typedef _Alloc allocator_type;\n@@ -547,13 +891,24 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11\n // so that explicit instantiation declarations of std::list that were\n // compiled with old versions of GCC can still find these old symbols.\n \n+ // Use 'if constexpr' so that the functions don't do anything for\n+ // specializations using _Node_traits<T, fancy-pointer>, because any\n+ // old code referencing these symbols wasn't using the fancy-pointer\n+ // specializations.\n+\n+#pragma GCC diagnostic push\n+#pragma GCC diagnostic ignored \"-Wc++17-extensions\" // if constexpr\n+\n # if __cplusplus >= 201103L\n _List_base(_List_base&& __x, _Node_alloc_type&& __a)\n : _M_impl(std::move(__a))\n {\n-\tif (__x._M_get_Node_allocator() == _M_get_Node_allocator())\n-\t _M_move_nodes(std::move(__x));\n-\t// else caller must move individual elements.\n+#if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST\n+\tif constexpr (is_same<typename _Tp_alloc_traits::pointer, _Tp*>::value)\n+#endif\n+\t if (__x._M_get_Node_allocator() == _M_get_Node_allocator())\n+\t _M_move_nodes(std::move(__x));\n+\t // else caller must move individual elements.\n }\n # endif\n \n@@ -561,13 +916,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11\n _S_distance(const __detail::_List_node_base* __first,\n \t\t const __detail::_List_node_base* __last)\n {\n-\tsize_t __n = 0;\n-\twhile (__first != __last)\n+#if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST\n+\tif constexpr (!is_same<typename _Tp_alloc_traits::pointer, _Tp*>::value)\n+\t return 0;\n+\telse\n+#endif\n \t {\n-\t __first = __first->_M_next;\n-\t ++__n;\n+\t size_t __n = 0;\n+\t while (__first != __last)\n+\t {\n+\t\t__first = __first->_M_next;\n+\t\t++__n;\n+\t }\n+\t return __n;\n \t }\n-\treturn __n;\n }\n \n #if _GLIBCXX_USE_CXX11_ABI\n@@ -584,10 +946,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11\n // count the number of nodes\n size_t _M_node_count() const\n {\n-\treturn _S_distance(_M_impl._M_node._M_next,\n-\t\t\t std::__addressof(_M_impl._M_node));\n+#if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST\n+\tif constexpr (!is_same<typename _Tp_alloc_traits::pointer, _Tp*>::value)\n+\t return 0;\n+\telse\n+#endif\n+\t return _S_distance(_M_impl._M_node._M_next,\n+\t\t\t _M_impl._M_node._M_base());\n }\n #endif\n+#pragma GCC diagnostic pop\n #endif // ! INLINE_VERSION\n };\n \n@@ -663,6 +1031,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11\n typedef typename _Base::_Tp_alloc_traits\t\t_Tp_alloc_traits;\n typedef typename _Base::_Node_alloc_type\t\t_Node_alloc_type;\n typedef typename _Base::_Node_alloc_traits\t_Node_alloc_traits;\n+ typedef typename _Base::_Node_traits\t\t_Node_traits;\n \n public:\n typedef _Tp\t\t\t\t\t value_type;\n@@ -670,8 +1039,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11\n typedef typename _Tp_alloc_traits::const_pointer\t const_pointer;\n typedef typename _Tp_alloc_traits::reference\t reference;\n typedef typename _Tp_alloc_traits::const_reference const_reference;\n- typedef _List_iterator<_Tp>\t\t\t iterator;\n- typedef _List_const_iterator<_Tp>\t\t\t const_iterator;\n+ typedef typename _Node_traits::_Iterator\t\t iterator;\n+ typedef typename _Node_traits::_Const_iterator\t const_iterator;\n typedef std::reverse_iterator<const_iterator>\t const_reverse_iterator;\n typedef std::reverse_iterator<iterator>\t\t reverse_iterator;\n typedef size_t\t\t\t\t\t size_type;\n@@ -681,7 +1050,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11\n protected:\n // Note that pointers-to-_Node's can be ctor-converted to\n // iterator types.\n- typedef _List_node<_Tp>\t\t\t\t _Node;\n+ typedef typename _Node_alloc_traits::pointer\t _Node_ptr;\n \n using _Base::_M_impl;\n using _Base::_M_put_node;\n@@ -695,10 +1064,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11\n * @a __args in it.\n */\n #if __cplusplus < 201103L\n- _Node*\n+ _Node_ptr\n _M_create_node(const value_type& __x)\n {\n-\t_Node* __p = this->_M_get_node();\n+\t_Node_ptr __p = this->_M_get_node();\n \t__try\n \t {\n \t _Tp_alloc_type __alloc(_M_get_Node_allocator());\n@@ -713,16 +1082,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11\n }\n #else\n template<typename... _Args>\n-\t_Node*\n+\t_Node_ptr\n \t_M_create_node(_Args&&... __args)\n \t{\n-\t auto __p = this->_M_get_node();\n \t auto& __alloc = _M_get_Node_allocator();\n-\t __allocated_ptr<_Node_alloc_type> __guard{__alloc, __p};\n-\t _Node_alloc_traits::construct(__alloc, __p->_M_valptr(),\n+\t auto __guard = std::__allocate_guarded_obj(__alloc);\n+\t _Node_alloc_traits::construct(__alloc, __guard->_M_valptr(),\n \t\t\t\t\tstd::forward<_Args>(__args)...);\n-\t __guard = nullptr;\n+\t auto __p = __guard.release();\n+#if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST\n \t return __p;\n+#else\n+\t return std::__to_address(__p);\n+#endif\n \t}\n #endif\n \n@@ -1070,7 +1442,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11\n _GLIBCXX_NODISCARD\n iterator\n end() _GLIBCXX_NOEXCEPT\n- { return iterator(&this->_M_impl._M_node); }\n+ { return iterator(this->_M_impl._M_node._M_base()); }\n \n /**\n * Returns a read-only (constant) iterator that points one past\n@@ -1080,7 +1452,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11\n _GLIBCXX_NODISCARD\n const_iterator\n end() const _GLIBCXX_NOEXCEPT\n- { return const_iterator(&this->_M_impl._M_node); }\n+ { return const_iterator(this->_M_impl._M_node._M_base()); }\n \n /**\n * Returns a read/write reverse iterator that points to the last\n@@ -1141,7 +1513,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11\n [[__nodiscard__]]\n const_iterator\n cend() const noexcept\n- { return const_iterator(&this->_M_impl._M_node); }\n+ { return const_iterator(this->_M_impl._M_node._M_base()); }\n \n /**\n * Returns a read-only (constant) reverse iterator that points to\n@@ -1171,7 +1543,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11\n */\n _GLIBCXX_NODISCARD bool\n empty() const _GLIBCXX_NOEXCEPT\n- { return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; }\n+ {\n+\treturn this->_M_impl._M_node._M_next == this->_M_impl._M_node._M_base();\n+ }\n \n /** Returns the number of elements in the %list. */\n _GLIBCXX_NODISCARD\n@@ -1682,8 +2056,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11\n void\n swap(list& __x) _GLIBCXX_NOEXCEPT\n {\n-\t__detail::_List_node_base::swap(this->_M_impl._M_node,\n-\t\t\t\t\t__x._M_impl._M_node);\n+\t_Node_traits::_Node_base::swap(this->_M_impl._M_node,\n+\t\t\t\t __x._M_impl._M_node);\n \n \tsize_t __xsize = __x._M_get_size();\n \t__x._M_set_size(this->_M_get_size());\n@@ -2105,7 +2479,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11\n void\n _M_insert(iterator __position, const value_type& __x)\n {\n-\t_Node* __tmp = _M_create_node(__x);\n+\t_Node_ptr __tmp = _M_create_node(__x);\n \t__tmp->_M_hook(__position._M_node);\n \tthis->_M_inc_size(1);\n }\n@@ -2114,7 +2488,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11\n void\n _M_insert(iterator __position, _Args&&... __args)\n {\n-\t _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);\n+\t _Node_ptr __tmp = _M_create_node(std::forward<_Args>(__args)...);\n \t __tmp->_M_hook(__position._M_node);\n \t this->_M_inc_size(1);\n }\n@@ -2124,16 +2498,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11\n void\n _M_erase(iterator __position) _GLIBCXX_NOEXCEPT\n {\n+\ttypedef typename _Node_traits::_Node _Node;\n \tthis->_M_dec_size(1);\n \t__position._M_node->_M_unhook();\n-\t_Node* __n = static_cast<_Node*>(__position._M_node);\n-#if __cplusplus >= 201103L\n-\t_Node_alloc_traits::destroy(_M_get_Node_allocator(), __n->_M_valptr());\n-#else\n-\t_Tp_alloc_type(_M_get_Node_allocator()).destroy(__n->_M_valptr());\n-#endif\n-\n-\t_M_put_node(__n);\n+\t_Node& __n = static_cast<_Node&>(*__position._M_node);\n+\tthis->_M_destroy_node(__n._M_node_ptr());\n }\n \n // To implement the splice (and merge) bits of N1599.\n@@ -2397,6 +2766,113 @@ _GLIBCXX_END_NAMESPACE_CONTAINER\n \t}\n return __n;\n }\n+\n+#if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST\n+ template<bool _Const, typename _Ptr>\n+ inline ptrdiff_t\n+ __distance(__list::_Iterator<_Const, _Ptr> __first,\n+\t __list::_Iterator<_Const, _Ptr> __last,\n+\t input_iterator_tag __tag)\n+ {\n+ using _Tp = typename __list::_Iterator<_Const, _Ptr>::value_type;\n+ using _Sentinel = typename __list::_Node_traits<_Tp, _Ptr>::_Node_header;\n+ auto __beyond = __last;\n+ ++__beyond;\n+ const bool __whole = __first == __beyond;\n+ if (__builtin_constant_p (__whole) && __whole)\n+\treturn static_cast<const _Sentinel&>(*__last._M_node)._M_size;\n+\n+ ptrdiff_t __n = 0;\n+ while (__first != __last)\n+\t{\n+\t ++__first;\n+\t ++__n;\n+\t}\n+ return __n;\n+ }\n+#endif\n+#endif\n+\n+#if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST\n+namespace __list\n+{\n+ template<typename _VoidPtr>\n+ void\n+ _Node_base<_VoidPtr>::swap(_Node_base& __x, _Node_base& __y) noexcept\n+ {\n+ auto __px = pointer_traits<_Base_ptr>::pointer_to(__x);\n+ auto __py = pointer_traits<_Base_ptr>::pointer_to(__y);\n+\n+ if (__x._M_next != __px)\n+\t{\n+\t if (__y._M_next != __py)\n+\t {\n+\t using std::swap;\n+\t // Both __x and __y are not empty.\n+\t swap(__x._M_next,__y._M_next);\n+\t swap(__x._M_prev,__y._M_prev);\n+\t __x._M_next->_M_prev = __x._M_prev->_M_next = __px;\n+\t __y._M_next->_M_prev = __y._M_prev->_M_next = __py;\n+\t }\n+\t else\n+\t {\n+\t // __x is not empty, __y is empty.\n+\t __y._M_next = __x._M_next;\n+\t __y._M_prev = __x._M_prev;\n+\t __y._M_next->_M_prev = __y._M_prev->_M_next = __py;\n+\t __x._M_next = __x._M_prev = __px;\n+\t }\n+\t}\n+ else if (__y._M_next != __py)\n+\t{\n+\t // __x is empty, __y is not empty.\n+\t __x._M_next = __y._M_next;\n+\t __x._M_prev = __y._M_prev;\n+\t __x._M_next->_M_prev = __x._M_prev->_M_next = __px;\n+\t __y._M_next = __y._M_prev = __py;\n+\t}\n+ }\n+\n+ template<typename _VoidPtr>\n+ void\n+ _Node_base<_VoidPtr>::_M_transfer(_Base_ptr const __first,\n+\t\t\t\t _Base_ptr const __last)\n+ {\n+ __glibcxx_assert(__first != __last);\n+\n+ auto __self = pointer_traits<_Base_ptr>::pointer_to(*this);\n+ if (__self != __last)\n+\t{\n+\t // Remove [first, last) from its old position.\n+\t __last->_M_prev->_M_next = __self;\n+\t __first->_M_prev->_M_next = __last;\n+\t this->_M_prev->_M_next = __first;\n+\n+\t // Splice [first, last) into its new position.\n+\t auto const __tmp = this->_M_prev;\n+\t this->_M_prev = __last->_M_prev;\n+\t __last->_M_prev = __first->_M_prev;\n+\t __first->_M_prev = __tmp;\n+\t}\n+ }\n+\n+ template<typename _VoidPtr>\n+ void\n+ _Node_header<_VoidPtr>::_M_reverse() noexcept\n+ {\n+ const auto __self = this->_M_base();\n+ auto __tmp = __self;\n+ do\n+\t{\n+\t using std::swap;\n+\t swap(__tmp->_M_next, __tmp->_M_prev);\n+\n+\t // Old next node is now prev.\n+\t __tmp = __tmp->_M_prev;\n+\t}\n+ while (__tmp != __self);\n+ }\n+} // namespace __list\n #endif\n \n _GLIBCXX_END_NAMESPACE_VERSION\ndiff --git a/libstdc++-v3/testsuite/23_containers/list/capacity/29134.cc b/libstdc++-v3/testsuite/23_containers/list/capacity/29134.cc\nindex 956afe19dc05..69540d3703b6 100644\n--- a/libstdc++-v3/testsuite/23_containers/list/capacity/29134.cc\n+++ b/libstdc++-v3/testsuite/23_containers/list/capacity/29134.cc\n@@ -35,6 +35,11 @@ void test01()\n \n std::allocator<_List_node<int> > a;\n VERIFY( l.max_size() == __gnu_test::max_size(a) );\n+\n+#if _GLIBCXX_LIST_USE_ALLOC_PTR\n+ std::allocator<std::__list::_Node<int*>> b;\n+ VERIFY( __gnu_test::max_size(b) == __gnu_test::max_size(a) );\n+#endif\n }\n \n int main()\ndiff --git a/libstdc++-v3/testsuite/23_containers/list/capacity/node_sizes.cc b/libstdc++-v3/testsuite/23_containers/list/capacity/node_sizes.cc\nnew file mode 100644\nindex 000000000000..8394824ba286\n--- /dev/null\n+++ b/libstdc++-v3/testsuite/23_containers/list/capacity/node_sizes.cc\n@@ -0,0 +1,24 @@\n+// { dg-do compile { target c++11 } }\n+\n+#include <list>\n+\n+#if _GLIBCXX_LIST_USE_ALLOC_PTR\n+\n+#ifdef _GLIBCXX_DEBUG\n+namespace C = std::_GLIBCXX_STD_C;\n+#else\n+namespace C = std;\n+#endif\n+\n+// We use double here because for ADJUST_FIELD_ALIGN targets (like i386)\n+// its alignment differs when used as a data member or as a complete object.\n+static_assert(sizeof(C::_List_node<double>)\n+\t == sizeof(std::__list::_Node<double*>),\n+\t \"node types have same size\");\n+static_assert(alignof(C::_List_node<double>)\n+\t == alignof(std::__list::_Node<double*>),\n+\t \"node types have same alignment\");\n+static_assert(__alignof(C::_List_node<double>)\n+\t == __alignof(std::__list::_Node<double*>),\n+\t \"node types have same preferred alignment\");\n+#endif\ndiff --git a/libstdc++-v3/testsuite/23_containers/list/requirements/completeness.cc b/libstdc++-v3/testsuite/23_containers/list/requirements/completeness.cc\nnew file mode 100644\nindex 000000000000..ad359e3b51d0\n--- /dev/null\n+++ b/libstdc++-v3/testsuite/23_containers/list/requirements/completeness.cc\n@@ -0,0 +1,19 @@\n+// { dg-do compile }\n+\n+// C++17 [list.overview]\n+// An incomplete type T may be used when instantiating list if the allocator\n+// satisfies the allocator completeness requirements (20.5.3.5.1).\n+// T shall be complete before any member of the resulting specialization\n+// of list is referenced.\n+\n+#include <list>\n+\n+struct Incomplete;\n+\n+// This instantiates std::list, but none of its members.\n+const int sz = sizeof(std::list<Incomplete>);\n+\n+// Technically the following references a member of std::list, but because\n+// our iterators are SCARY it doesn't instantiate any members of std::list.\n+// GCC's own source code expects this to work.\n+std::list<Incomplete>::iterator i = std::list<Incomplete>::iterator();\ndiff --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\nnew file mode 100644\nindex 000000000000..d3b2cfe6d923\n--- /dev/null\n+++ b/libstdc++-v3/testsuite/23_containers/list/requirements/explicit_instantiation/alloc_ptr.cc\n@@ -0,0 +1,87 @@\n+// { dg-do compile { target c++11 } }\n+\n+#include <list>\n+#include <testsuite_allocator.h>\n+\n+// An allocator that uses __gnu_cxx::_Pointer_adapter as its pointer type.\n+template class std::list<int, __gnu_test::CustomPointerAlloc<int>>;\n+\n+// Unlike __gnu_cxx::_Pointer_adapter, this fancy pointer supports neither\n+// implicit nor explicit conversions from raw pointers. The constructor from\n+// a raw pointer is explicit and requires a second parameter. The only way for\n+// containers to construct one of these pointers is pointer_traits::pointer_to.\n+template<typename T>\n+struct Pointer : __gnu_test::PointerBase<Pointer<T>, T>\n+{\n+ using Base = __gnu_test::PointerBase<Pointer<T>, T>;\n+\n+ Pointer() = default;\n+ Pointer(std::nullptr_t) : Base() { }\n+ explicit Pointer(T* p, int) : Base(p) { }\n+\n+ // Allow conversions to const_pointer and to void_pointer\n+ template<typename U, typename = typename std::enable_if<\n+ (!std::is_const<U>::value && std::is_same<T, const U>::value)\n+ || (std::is_void<T>::value && std::is_convertible<U*, T*>::value)\n+ >::type>\n+ Pointer(const Pointer<U>& p) : Base(p.operator->()) { }\n+\n+ template<typename U>\n+ static typename std::enable_if<std::is_same<U, T>::value, Pointer>::type\n+ pointer_to(U& t)\n+ { return Pointer(std::addressof(t), 1); }\n+};\n+\n+// A minimal allocator that uses Pointer as its pointer type.\n+template<typename T>\n+struct Allocator\n+{\n+ using value_type = T;\n+ using pointer = Pointer<T>;\n+\n+ Allocator() = default;\n+ template<typename U>\n+ Allocator(const Allocator<U>&) { }\n+\n+ pointer allocate(std::size_t n)\n+ { return pointer(std::allocator<T>().allocate(n), 1); }\n+\n+ void deallocate(pointer p, std::size_t n)\n+ {\n+ std::allocator<T>().deallocate(p.operator->(), n);\n+ }\n+\n+ bool operator==(const Allocator&) const { return true; }\n+ bool operator!=(const Allocator&) const { return false; }\n+};\n+\n+template class std::list<int, Allocator<int>>;\n+\n+#include <testsuite_iterators.h>\n+\n+void\n+test_template_members(__gnu_test::input_container<short>& c)\n+{\n+ // Use member functions that are not included in explicit instantiations.\n+ std::list<int, Allocator<int>> l(c.begin(), c.end());\n+ l.assign(c.begin(), c.end());\n+ l.insert(l.begin(), c.begin(), c.end());\n+ l.emplace_front(1);\n+ l.emplace_back(1);\n+ l.emplace(l.begin(), 1);\n+ l.remove_if([](int) { return false; });\n+ l.unique([](int, int) { return false; });\n+ l.merge(l, [](int, int) { return false; });\n+ l.merge(std::move(l), [](int, int) { return false; });\n+ l.sort([](int, int) { return false; });\n+\n+#ifdef __glibcxx_ranges_to_container\n+ short arr[2];\n+ __gnu_test::test_input_range<short> r(arr);\n+ std::list<int, Allocator<int>> l2(std::from_range, r);\n+ l2.assign_range(r);\n+ l2.prepend_range(r);\n+ l2.append_range(r);\n+ l2.insert_range(l2.begin(), r);\n+#endif\n+}\ndiff --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\nnew file mode 100644\nindex 000000000000..e6a499d27160\n--- /dev/null\n+++ b/libstdc++-v3/testsuite/23_containers/list/requirements/explicit_instantiation/alloc_ptr_ignored.cc\n@@ -0,0 +1,4 @@\n+// { dg-options \"-D_GLIBCXX_LIST_USE_ALLOC_PTR=0\" }\n+// { dg-do compile { target c++11 } }\n+\n+#include \"alloc_ptr.cc\"\n", "prefixes": [ "v1", "3/4" ] }