Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/2226708/?format=api
{ "id": 2226708, "url": "http://patchwork.ozlabs.org/api/patches/2226708/?format=api", "web_url": "http://patchwork.ozlabs.org/project/gcc/patch/bmm.hhuoj2uk6c.gcc.gcc-TEST.ppalka.57.1.4@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.hhuoj2uk6c.gcc.gcc-TEST.ppalka.57.1.4@forge-stage.sourceware.org>", "list_archive_url": null, "date": "2026-04-22T18:27:28", "name": "[v1,4/8] libstdc++: Directly implement ranges::stable_sort [PR100795]", "commit_ref": null, "pull_url": null, "state": "new", "archived": false, "hash": "90bc113c25281ff4bfb68d775f090acd7b69894f", "submitter": { "id": 93215, "url": "http://patchwork.ozlabs.org/api/people/93215/?format=api", "name": "ppalka via Sourceware Forge", "email": "forge-bot+ppalka@forge-stage.sourceware.org" }, "delegate": null, "mbox": "http://patchwork.ozlabs.org/project/gcc/patch/bmm.hhuoj2uk6c.gcc.gcc-TEST.ppalka.57.1.4@forge-stage.sourceware.org/mbox/", "series": [ { "id": 501079, "url": "http://patchwork.ozlabs.org/api/series/501079/?format=api", "web_url": "http://patchwork.ozlabs.org/project/gcc/list/?series=501079", "date": "2026-04-22T18:27:24", "name": "libstdc++: C++20 iterator awareness fixes for various Ranges algorithms [PR100795]", "version": 1, "mbox": "http://patchwork.ozlabs.org/series/501079/mbox/" } ], "comments": "http://patchwork.ozlabs.org/api/patches/2226708/comments/", "check": "pending", "checks": "http://patchwork.ozlabs.org/api/patches/2226708/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 4g17Rq5s5Yz1yGs\n\tfor <incoming@patchwork.ozlabs.org>; Thu, 23 Apr 2026 04:44:23 +1000 (AEST)", "from vm01.sourceware.org (localhost [127.0.0.1])\n\tby sourceware.org (Postfix) with ESMTP id CD2A2453E3FA\n\tfor <incoming@patchwork.ozlabs.org>; Wed, 22 Apr 2026 18:44:21 +0000 (GMT)", "from forge-stage.sourceware.org (vm08.sourceware.org [38.145.34.39])\n by sourceware.org (Postfix) with ESMTPS id 4B5584B7A1FD\n for <gcc-patches@gcc.gnu.org>; Wed, 22 Apr 2026 18:28:35 +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 205E84349E\n for <gcc-patches@gcc.gnu.org>; Wed, 22 Apr 2026 18:28:35 +0000 (UTC)" ], "DKIM-Filter": [ "OpenDKIM Filter v2.11.0 sourceware.org CD2A2453E3FA", "OpenDKIM Filter v2.11.0 sourceware.org 4B5584B7A1FD" ], "DMARC-Filter": "OpenDMARC Filter v1.4.2 sourceware.org 4B5584B7A1FD", "ARC-Filter": "OpenARC Filter v1.0.0 sourceware.org 4B5584B7A1FD", "ARC-Seal": "i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1776882515; cv=none;\n b=oEgXtjaB7lsf1x+h/xJtBfHdANiXfbyoPJK2/h02pCv4f0ogE8qw8be3kjLIA5iFmaE+4D0l8GOBrqncmYBvM6+WqgjblRPElZbVr63bWcv66jUwUvj+g3D6TrkkI1We0QaMj5rxwHFXHJEzAyUdMP+xufNdD3c3TRPlhL1Fpp0=", "ARC-Message-Signature": "i=1; a=rsa-sha256; d=sourceware.org; s=key;\n t=1776882515; c=relaxed/simple;\n bh=8SKV0VRtagR9j5ipzIqS7gdhNahG/Js57X0RPNC61Is=;\n h=From:Date:Subject:To:Message-ID;\n b=CGtFHvWrXISphAq3vdrzhf3qBAAimRtySvBSu6cizB6oann5TrqN4vRwLvYZazQTKAsZ1J54h75zHw2C3KeY3SD7sGFzbQo5JElX+2ZcLrf2JH3/XUfud5uY9GLLK0o3bjnPrbFuhhYx6Q5GL2xqsh6i+0egzYoqpxvGeqrqhgc=", "ARC-Authentication-Results": "i=1; server2.sourceware.org", "From": "ppalka via Sourceware Forge\n <forge-bot+ppalka@forge-stage.sourceware.org>", "Date": "Wed, 22 Apr 2026 18:27:28 +0000", "Subject": "[PATCH v1 4/8] libstdc++: Directly implement ranges::stable_sort\n [PR100795]", "To": "gcc-patches mailing list <gcc-patches@gcc.gnu.org>", "Message-ID": "\n <bmm.hhuoj2uk6c.gcc.gcc-TEST.ppalka.57.1.4@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/57", "References": "\n <bmm.hhuoj2uk6c.gcc.gcc-TEST.ppalka.57.1.0@forge-stage.sourceware.org>", "In-Reply-To": "\n <bmm.hhuoj2uk6c.gcc.gcc-TEST.ppalka.57.1.0@forge-stage.sourceware.org>", "X-Patch-URL": "\n https://forge.sourceware.org/gcc/gcc-TEST/commit/d9f1bb26d38541337f0f6c3bb7eba211dbca00a8", "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>,\n ppalka@gcc.gnu.org", "Errors-To": "gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org" }, "content": "From: Patrick Palka <ppalka@redhat.com>\n\n\tPR libstdc++/100795\n\nlibstdc++-v3/ChangeLog:\n\n\t* include/bits/ranges_algo.h (__detail::__move_merge): New,\n\tbased on the stl_algo.h implementation.\n\t(__detail::__merge_sort_loop): Likewise.\n\t(__detail::__chunk_insertion_sort): Likewise.\n\t(__detail::__merge_sort_with_buffer): Likewise.\n\t(__detail::__stable_sort_adaptive): Likewise.\n\t(__detail::__stable_sort_adaptive_resize): Likewise.\n\t(__detail::__inplace_stable_sort): Likewise.\n\t(__stable_sort_fn::operator()): Reimplement in terms of the above.\n\t* testsuite/25_algorithms/stable_sort/constrained.cc:\n---\n libstdc++-v3/include/bits/ranges_algo.h | 207 +++++++++++++++++-\n .../25_algorithms/stable_sort/constrained.cc | 30 +++\n 2 files changed, 233 insertions(+), 4 deletions(-)", "diff": "diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h\nindex b0357600adbc..7dfd4e7ed64c 100644\n--- a/libstdc++-v3/include/bits/ranges_algo.h\n+++ b/libstdc++-v3/include/bits/ranges_algo.h\n@@ -2388,6 +2388,170 @@ namespace ranges\n \n inline constexpr __sort_fn sort{};\n \n+ namespace __detail\n+ {\n+ /// This is a helper function for the __merge_sort_loop routines.\n+ template<typename _Iter, typename _Out, typename _Comp>\n+ _Out\n+ __move_merge(_Iter __first1, _Iter __last1,\n+\t\t _Iter __first2, _Iter __last2,\n+\t\t _Out __result, _Comp __comp)\n+ {\n+\twhile (__first1 != __last1 && __first2 != __last2)\n+\t {\n+\t if (__comp(*__first2, *__first1))\n+\t {\n+\t\t*__result = ranges::iter_move(__first2);\n+\t\t++__first2;\n+\t }\n+\t else\n+\t {\n+\t\t*__result = ranges::iter_move(__first1);\n+\t\t++__first1;\n+\t }\n+\t ++__result;\n+\t }\n+\treturn ranges::move(__first2, __last2,\n+\t\t\t ranges::move(__first1, __last1, __result).out).out;\n+ }\n+\n+ template<typename _Iter, typename _Out, typename _Distance, typename _Comp>\n+ void\n+ __merge_sort_loop(_Iter __first, _Iter __last, _Out __result,\n+\t\t\t_Distance __step_size, _Comp __comp)\n+ {\n+\tconst _Distance __two_step = 2 * __step_size;\n+\n+\twhile (__last - __first >= __two_step)\n+\t {\n+\t __result = __detail::__move_merge(__first, __first + __step_size,\n+\t\t\t\t\t __first + __step_size,\n+\t\t\t\t\t __first + __two_step,\n+\t\t\t\t\t __result, __comp);\n+\t __first += __two_step;\n+\t }\n+\t__step_size = ranges::min(_Distance(__last - __first), __step_size);\n+\n+\t__detail::__move_merge(__first, __first + __step_size,\n+\t\t\t __first + __step_size, __last, __result, __comp);\n+ }\n+\n+ template<typename _Iter, typename _Distance, typename _Compare>\n+ constexpr void\n+ __chunk_insertion_sort(_Iter __first, _Iter __last,\n+\t\t\t _Distance __chunk_size, _Compare __comp)\n+ {\n+\twhile (__last - __first >= __chunk_size)\n+\t {\n+\t __detail::__insertion_sort(__first, __first + __chunk_size, __comp);\n+\t __first += __chunk_size;\n+\t }\n+\t__detail::__insertion_sort(__first, __last, __comp);\n+ }\n+\n+ template<typename _Iter, typename _Pointer, typename _Comp>\n+ void\n+ __merge_sort_with_buffer(_Iter __first, _Iter __last,\n+\t\t\t _Pointer __buffer, _Comp __comp)\n+ {\n+\tusing _Distance = iter_difference_t<_Iter>;\n+\n+\tconst _Distance __len = __last - __first;\n+\tconst _Pointer __buffer_last = __buffer + ptrdiff_t(__len);\n+\n+\tconstexpr int __chunk_size = 7;\n+\t_Distance __step_size = __chunk_size;\n+\t__detail::__chunk_insertion_sort(__first, __last, __step_size, __comp);\n+\n+\twhile (__step_size < __len)\n+\t {\n+\t __detail::__merge_sort_loop(__first, __last, __buffer,\n+\t\t\t\t\t__step_size, __comp);\n+\t __step_size *= 2;\n+\t __detail::__merge_sort_loop(__buffer, __buffer_last, __first,\n+\t\t\t\t\tptrdiff_t(__step_size), __comp);\n+\t __step_size *= 2;\n+\t }\n+ }\n+\n+ template<typename _Iter, typename _Pointer, typename _Comp>\n+ void\n+ __merge_adaptive(_Iter __first, _Iter __middle, _Iter __last,\n+\t\t iter_difference_t<_Iter> __len1,\n+\t\t iter_difference_t<_Iter> __len2,\n+\t\t _Pointer __buffer, _Comp __comp); // defined near inplace_merge\n+\n+ template<typename _Iter, typename _Distance, typename _Pointer, typename _Comp>\n+ void\n+ __merge_adaptive_resize(_Iter __first, _Iter __middle, _Iter __last,\n+\t\t\t _Distance __len1, _Distance __len2,\n+\t\t\t _Pointer __buffer, _Distance __buffer_size,\n+\t\t\t _Comp __comp); // defined near inplace_merge\n+\n+ template<typename _Iter, typename _Distance, typename _Comp>\n+ constexpr void\n+ __merge_without_buffer(_Iter __first, _Iter __middle, _Iter __last,\n+\t\t\t _Distance __len1, _Distance __len2,\n+\t\t\t _Comp __comp); // defined near inplace_merge\n+\n+ template<typename _Iter, typename _Pointer, typename _Comp>\n+ void\n+ __stable_sort_adaptive(_Iter __first, _Iter __middle, _Iter __last,\n+\t\t\t _Pointer __buffer, _Comp __comp)\n+ {\n+\t__detail::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);\n+\t__detail::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);\n+\n+\t__detail::__merge_adaptive(__first, __middle, __last,\n+\t\t\t\t __middle - __first, __last - __middle,\n+\t\t\t\t __buffer, __comp);\n+ }\n+\n+ template<typename _Iter, typename _Pointer, typename _Distance, typename _Comp>\n+ void\n+ __stable_sort_adaptive_resize(_Iter __first, _Iter __last,\n+\t\t\t\t _Pointer __buffer, _Distance __buffer_size,\n+\t\t\t\t _Comp __comp)\n+ {\n+\tconst _Distance __len = (__last - __first + 1) / 2;\n+\tconst _Iter __middle = __first + __len;\n+\tif (__len > __buffer_size)\n+\t {\n+\t __detail::__stable_sort_adaptive_resize(__first, __middle, __buffer,\n+\t\t\t\t\t\t __buffer_size, __comp);\n+\t __detail::__stable_sort_adaptive_resize(__middle, __last, __buffer,\n+\t\t\t\t\t\t __buffer_size, __comp);\n+\t __detail::__merge_adaptive_resize(__first, __middle, __last,\n+\t\t\t\t\t _Distance(__middle - __first),\n+\t\t\t\t\t _Distance(__last - __middle),\n+\t\t\t\t\t __buffer, __buffer_size,\n+\t\t\t\t\t __comp);\n+\t }\n+\telse\n+\t __detail::__stable_sort_adaptive(__first, __middle, __last,\n+\t\t\t\t\t __buffer, __comp);\n+ }\n+\n+ template<typename _Iter, typename _Comp>\n+ _GLIBCXX26_CONSTEXPR\n+ void\n+ __inplace_stable_sort(_Iter __first, _Iter __last, _Comp __comp)\n+ {\n+\tif (__last - __first < 15)\n+\t {\n+\t __detail::__insertion_sort(__first, __last, __comp);\n+\t return;\n+\t }\n+\t_Iter __middle = __first + (__last - __first) / 2;\n+\t__detail::__inplace_stable_sort(__first, __middle, __comp);\n+\t__detail::__inplace_stable_sort(__middle, __last, __comp);\n+\t__detail::__merge_without_buffer(__first, __middle, __last,\n+\t\t\t\t\t __middle - __first,\n+\t\t\t\t\t __last - __middle,\n+\t\t\t\t\t __comp);\n+ }\n+ } // namespace __detail\n+\n struct __stable_sort_fn\n {\n template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,\n@@ -2398,10 +2562,45 @@ namespace ranges\n operator()(_Iter __first, _Sent __last,\n \t\t _Comp __comp = {}, _Proj __proj = {}) const\n {\n-\tauto __lasti = ranges::next(__first, __last);\n-\tstd::stable_sort(std::move(__first), __lasti,\n-\t\t\t __detail::__make_comp_proj(__comp, __proj));\n-\treturn __lasti;\n+\tif constexpr (!same_as<_Iter, _Sent>)\n+\t return (*this)(__first, ranges::next(__first, __last),\n+\t\t\t std::move(__comp), std::move(__proj));\n+\telse\n+\t {\n+\t using _DistanceType = iter_difference_t<_Iter>;\n+\n+\t if (__first == __last)\n+\t return __last;\n+\n+#if _GLIBCXX_HOSTED\n+# if __glibcxx_constexpr_algorithms >= 202306L // >= C++26\n+\t if consteval {\n+\t __detail::__inplace_stable_sort(__first, __last, __comp);\n+\t return __last;\n+\t }\n+# endif\n+\n+\t typedef _Temporary_buffer<_Iter, iter_value_t<_Iter>> _TmpBuf;\n+\t // __stable_sort_adaptive sorts the range in two halves,\n+\t // so the buffer only needs to fit half the range at once.\n+\t _TmpBuf __buf(__first, ptrdiff_t((__last - __first + 1) / 2));\n+\n+\t auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);\n+\t if (__buf._M_requested_size() == __buf.size()) [[likely]]\n+\t __detail::__stable_sort_adaptive(__first,\n+\t\t\t\t\t __first + _DistanceType(__buf.size()),\n+\t\t\t\t\t __last, __buf.begin(), __comp_proj);\n+\t else if (__buf.begin()) [[unlikely]]\n+\t __detail::__inplace_stable_sort(__first, __last, __comp_proj);\n+\t else\n+\t __detail::__stable_sort_adaptive_resize(__first, __last, __buf.begin(),\n+\t\t\t\t\t\t _DistanceType(__buf.size()),\n+\t\t\t\t\t\t __comp_proj);\n+#else\n+\t __detail::__inplace_stable_sort(__first, __last, __comp_proj);\n+#endif\n+\t return __last;\n+\t }\n }\n \n template<random_access_range _Range,\ndiff --git a/libstdc++-v3/testsuite/25_algorithms/stable_sort/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/stable_sort/constrained.cc\nindex 0bd438fa5f29..55043442f4be 100644\n--- a/libstdc++-v3/testsuite/25_algorithms/stable_sort/constrained.cc\n+++ b/libstdc++-v3/testsuite/25_algorithms/stable_sort/constrained.cc\n@@ -20,6 +20,7 @@\n \n #include <algorithm>\n #include <random>\n+#include <ranges>\n #include <vector>\n #include <testsuite_hooks.h>\n #include <testsuite_iterators.h>\n@@ -62,8 +63,37 @@ test01()\n }\n }\n \n+void\n+test02()\n+{\n+ // PR libstdc++/100795 - ranges::stable_sort should not use std::stable_sort\n+ // directly\n+#if __SIZEOF_INT128__\n+ auto v = std::views::iota(__int128(0), __int128(20));\n+#else\n+ auto v = std::views::iota(0ll, 20ll);\n+#endif\n+\n+ int storage[20] = {2,5,4,3,1,6,7,9,10,8,11,14,12,13,15,16,18,0,19,17};\n+ auto w = v | std::views::transform([&](auto i) -> int& { return storage[i]; });\n+ using type = decltype(w);\n+ using cat = std::iterator_traits<std::ranges::iterator_t<type>>::iterator_category;\n+ static_assert( std::same_as<cat, std::output_iterator_tag> );\n+ static_assert( std::ranges::random_access_range<type> );\n+\n+ ranges::stable_sort(w);\n+ VERIFY( ranges::equal(w, v) );\n+\n+ ranges::stable_sort(w, std::ranges::greater{});\n+ VERIFY( ranges::equal(w, v | std::views::reverse) );\n+\n+ ranges::stable_sort(w, std::ranges::greater{}, std::negate{});\n+ VERIFY( ranges::equal(w, v) );\n+}\n+\n int\n main()\n {\n test01();\n+ test02();\n }\n", "prefixes": [ "v1", "4/8" ] }