Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/2226721/?format=api
{ "id": 2226721, "url": "http://patchwork.ozlabs.org/api/patches/2226721/?format=api", "web_url": "http://patchwork.ozlabs.org/project/gcc/patch/bmm.hhuoj2uk6c.gcc.gcc-TEST.ppalka.57.1.5@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.5@forge-stage.sourceware.org>", "list_archive_url": null, "date": "2026-04-22T18:27:29", "name": "[v1,5/8] libstdc++: Directly implement ranges::stable_partition [PR100795]", "commit_ref": null, "pull_url": null, "state": "new", "archived": false, "hash": "4f10f3c60f611e0d018970460c6376c6e22ccc39", "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.5@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/2226721/comments/", "check": "pending", "checks": "http://patchwork.ozlabs.org/api/patches/2226721/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=38.145.34.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 [38.145.34.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 4g17cX14Zgz1y2d\n\tfor <incoming@patchwork.ozlabs.org>; Thu, 23 Apr 2026 04:51:56 +1000 (AEST)", "from vm01.sourceware.org (localhost [127.0.0.1])\n\tby sourceware.org (Postfix) with ESMTP id 5901844AFFD7\n\tfor <incoming@patchwork.ozlabs.org>; Wed, 22 Apr 2026 18:51:49 +0000 (GMT)", "from forge-stage.sourceware.org (vm08.sourceware.org [38.145.34.39])\n by sourceware.org (Postfix) with ESMTPS id B7E6A48FEC26\n for <gcc-patches@gcc.gnu.org>; Wed, 22 Apr 2026 18:28:36 +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 2DFE04349F\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 5901844AFFD7", "OpenDKIM Filter v2.11.0 sourceware.org B7E6A48FEC26" ], "DMARC-Filter": "OpenDMARC Filter v1.4.2 sourceware.org B7E6A48FEC26", "ARC-Filter": "OpenARC Filter v1.0.0 sourceware.org B7E6A48FEC26", "ARC-Seal": "i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1776882516; cv=none;\n b=j/PpstCELFpAssqGkl0IcCmRQDoohG4I7NDb4wpsuJnJutOEctCWMmZGgczVthjcSI+DL1YaZ928dSKP978LxcyvgruF5aKMtRyQB4C9ZkjzwNp8FLvqvK6+RayAUDaiR7oqq8L1qprwCDcjXv3+c/dUEhL+NMRchmmUsPsLNk8=", "ARC-Message-Signature": "i=1; a=rsa-sha256; d=sourceware.org; s=key;\n t=1776882516; c=relaxed/simple;\n bh=HxZahkmu8STgXkKVYzwGBNPZV9ayr2ARBZ3JTiPhS1M=;\n h=From:Date:Subject:To:Message-ID;\n b=Ks14+/FdeK2OQb0OfEBSQegOLkSPxYhuSWJCXDt3M0cgrr0GqokTr1eqXHYhDDtInktBu2jSHpqTGKjx7q/ON/b5YbPfrfRuEC3RVrGPazkhdK57Mdz4Hp8h9ex7OWX2/e5MetkWNmt1HF4X+F5+B3fysWCO8wYFUCKY8krXa2k=", "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:29 +0000", "Subject": "[PATCH v1 5/8] libstdc++: Directly implement ranges::stable_partition\n [PR100795]", "To": "gcc-patches mailing list <gcc-patches@gcc.gnu.org>", "Message-ID": "\n <bmm.hhuoj2uk6c.gcc.gcc-TEST.ppalka.57.1.5@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/198c145f2ea6ad5b9ee2991477e213f9c50181a7", "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::__find_if_not_n): New,\n\tbased on the stl_algo.h implementation.\n\t(__detail::__stable_partition_adaptive): Likewise.\n\t(__stable_partition_fn::operator()): Reimplement in terms of\n\tthe above.\n\t* testsuite/25_algorithms/stable_partition/constrained.cc\n\t(test03): New test.\n---\n libstdc++-v3/include/bits/ranges_algo.h | 106 +++++++++++++++++-\n .../stable_partition/constrained.cc | 26 +++++\n 2 files changed, 127 insertions(+), 5 deletions(-)", "diff": "diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h\nindex 7dfd4e7ed64c..a9924cd9c49e 100644\n--- a/libstdc++-v3/include/bits/ranges_algo.h\n+++ b/libstdc++-v3/include/bits/ranges_algo.h\n@@ -3133,6 +3133,81 @@ namespace ranges\n inline constexpr __partition_fn partition{};\n \n #if _GLIBCXX_HOSTED\n+ namespace __detail\n+ {\n+ /// Like find_if_not(), but uses and updates a count of the\n+ /// remaining range length instead of comparing against an end\n+ /// iterator.\n+ template<typename _Iter, typename _Pred, typename _Distance>\n+ constexpr _Iter\n+ __find_if_not_n(_Iter __first, _Distance& __len, _Pred __pred)\n+ {\n+\tfor (; __len; --__len, (void) ++__first)\n+\t if (!__pred(*__first))\n+\t break;\n+\treturn __first;\n+ }\n+\n+ template<typename _Iter, typename _Sent, typename _Pointer,\n+\t typename _Pred, typename _Distance>\n+ _GLIBCXX26_CONSTEXPR\n+ subrange<_Iter>\n+ __stable_partition_adaptive(_Iter __first, _Sent __last,\n+\t\t\t\t _Pred __pred, _Distance __len,\n+\t\t\t\t _Pointer __buffer,\n+\t\t\t\t _Distance __buffer_size)\n+ {\n+\tif (__len == 1)\n+\t return {__first, ranges::next(__first, 1)};\n+\n+\tif (__len <= __buffer_size)\n+\t {\n+\t _Iter __result1 = __first;\n+\t _Pointer __result2 = __buffer;\n+\n+\t // The precondition guarantees that !__pred(__first), so\n+\t // move that element to the buffer before starting the loop.\n+\t // This ensures that we only call __pred once per element.\n+\t *__result2 = ranges::iter_move(__first);\n+\t ++__result2;\n+\t ++__first;\n+\t for (; __first != __last; ++__first)\n+\t if (__pred(*__first))\n+\t\t{\n+\t\t *__result1 = ranges::iter_move(__first);\n+\t\t ++__result1;\n+\t\t}\n+\t else\n+\t\t{\n+\t\t *__result2 = ranges::iter_move(__first);\n+\t\t ++__result2;\n+\t\t}\n+\n+\t ranges::move(__buffer, __result2, __result1);\n+\t return {__result1, __first};\n+\t }\n+\n+\t_Iter __middle = __first;\n+\tranges::advance(__middle, __len / 2);\n+\t_Iter __left_split\n+\t = __detail::__stable_partition_adaptive(__first, __middle, __pred,\n+\t\t\t\t\t\t __len / 2, __buffer,\n+\t\t\t\t\t\t __buffer_size).begin();\n+\n+\t// Advance past true-predicate values to satisfy this\n+\t// function's preconditions.\n+\t_Distance __right_len = __len - __len / 2;\n+\t_Iter __right_split = __detail::__find_if_not_n(__middle, __right_len, __pred);\n+\n+\tif (__right_len)\n+\t __right_split\n+\t = __detail::__stable_partition_adaptive(__right_split, __last, __pred,\n+\t\t\t\t\t\t __right_len, __buffer, __buffer_size).begin();\n+\n+\treturn ranges::rotate(__left_split, __middle, __right_split);\n+ }\n+ } // namespace __detail\n+\n struct __stable_partition_fn\n {\n template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,\n@@ -3144,11 +3219,32 @@ namespace ranges\n operator()(_Iter __first, _Sent __last,\n \t\t _Pred __pred, _Proj __proj = {}) const\n {\n-\tauto __lasti = ranges::next(__first, __last);\n-\tauto __middle\n-\t = std::stable_partition(std::move(__first), __lasti,\n-\t\t\t\t __detail::__make_pred_proj(__pred, __proj));\n-\treturn {std::move(__middle), std::move(__lasti)};\n+\tauto __pred_proj = __detail::__make_pred_proj(__pred, __proj);\n+\t__first = ranges::find_if_not(__first, __last, __pred_proj);\n+\n+\tif (__first == __last)\n+\t return {__first, __first};\n+\n+\tusing _DistanceType = iter_difference_t<_Iter>;\n+\tconst _DistanceType __len = ranges::distance(__first, __last);\n+\n+#if __glibcxx_constexpr_algorithms >= 202306L // >= C++26\n+\tif consteval {\n+\t // Simulate a _Temporary_buffer of length 1:\n+\t iter_value_t<_Iter> __buf = ranges::iter_move(__first);\n+\t *__first = std::move(__buf);\n+\t return __detail::__stable_partition_adaptive(__first, __last,\n+\t\t\t\t\t\t __pred_proj,\n+\t\t\t\t\t\t __len, &__buf,\n+\t\t\t\t\t\t _DistanceType(1));\n+\t}\n+#endif\n+\n+\t_Temporary_buffer<_Iter, iter_value_t<_Iter>> __buf(__first, ptrdiff_t(__len));\n+\treturn __detail::__stable_partition_adaptive(__first, __last,\n+\t\t\t\t\t\t __pred_proj,\n+\t\t\t\t\t\t __len, __buf.begin(),\n+\t\t\t\t\t\t _DistanceType(__buf.size()));\n }\n \n template<bidirectional_range _Range, typename _Proj = identity,\ndiff --git a/libstdc++-v3/testsuite/25_algorithms/stable_partition/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/stable_partition/constrained.cc\nindex fc11c6439f9c..4dc267873ae2 100644\n--- a/libstdc++-v3/testsuite/25_algorithms/stable_partition/constrained.cc\n+++ b/libstdc++-v3/testsuite/25_algorithms/stable_partition/constrained.cc\n@@ -21,6 +21,7 @@\n // { dg-require-effective-target hosted }\n \n #include <algorithm>\n+#include <ranges>\n #include <testsuite_hooks.h>\n #include <testsuite_iterators.h>\n \n@@ -70,9 +71,34 @@ test02()\n }\n }\n \n+void\n+test03()\n+{\n+ // PR libstdc++/100795 - ranges::stable_partition should not use\n+ // std::stable_partition 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+ auto pred = [] (int a) { return a%2==0; };\n+ ranges::stable_partition(w, pred);\n+ VERIFY( ranges::all_of(w.begin(), w.begin() + 10, pred) );\n+ VERIFY( ranges::none_of(w.begin() + 10, w.end(), pred) );\n+}\n+\n int\n main()\n {\n test01();\n test02();\n+ test03();\n }\n", "prefixes": [ "v1", "5/8" ] }