Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/1.2/patches/2226144/?format=api
{ "id": 2226144, "url": "http://patchwork.ozlabs.org/api/1.2/patches/2226144/?format=api", "web_url": "http://patchwork.ozlabs.org/project/gcc/patch/bmm.hhuawf4oe6.gcc.gcc-TEST.ppalka.8.1.1@forge-stage.sourceware.org/", "project": { "id": 17, "url": "http://patchwork.ozlabs.org/api/1.2/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.hhuawf4oe6.gcc.gcc-TEST.ppalka.8.1.1@forge-stage.sourceware.org>", "list_archive_url": null, "date": "2026-04-22T10:13:03", "name": "[v1,1/1] libstdc++: Fix complexity of drop_view::begin const [PR112641]", "commit_ref": null, "pull_url": null, "state": "new", "archived": false, "hash": "cc57bc91f87bb82a345456503aa8e02876fdd9ec", "submitter": { "id": 93215, "url": "http://patchwork.ozlabs.org/api/1.2/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.hhuawf4oe6.gcc.gcc-TEST.ppalka.8.1.1@forge-stage.sourceware.org/mbox/", "series": [ { "id": 500958, "url": "http://patchwork.ozlabs.org/api/1.2/series/500958/?format=api", "web_url": "http://patchwork.ozlabs.org/project/gcc/list/?series=500958", "date": "2026-04-22T10:13:03", "name": "[v1,1/1] libstdc++: Fix complexity of drop_view::begin const [PR112641]", "version": 1, "mbox": "http://patchwork.ozlabs.org/series/500958/mbox/" } ], "comments": "http://patchwork.ozlabs.org/api/patches/2226144/comments/", "check": "pending", "checks": "http://patchwork.ozlabs.org/api/patches/2226144/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 4g0w6t2srrz1yCv\n\tfor <incoming@patchwork.ozlabs.org>; Wed, 22 Apr 2026 20:13:57 +1000 (AEST)", "from vm01.sourceware.org (localhost [127.0.0.1])\n\tby sourceware.org (Postfix) with ESMTP id 370F94B9DB59\n\tfor <incoming@patchwork.ozlabs.org>; Wed, 22 Apr 2026 10:13:55 +0000 (GMT)", "from forge-stage.sourceware.org (vm08.sourceware.org [38.145.34.39])\n by sourceware.org (Postfix) with ESMTPS id E716F4BA23F4\n for <gcc-patches@gcc.gnu.org>; Wed, 22 Apr 2026 10:13:28 +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 B129340546\n for <gcc-patches@gcc.gnu.org>; Wed, 22 Apr 2026 10:13:28 +0000 (UTC)" ], "DKIM-Filter": [ "OpenDKIM Filter v2.11.0 sourceware.org 370F94B9DB59", "OpenDKIM Filter v2.11.0 sourceware.org E716F4BA23F4" ], "DMARC-Filter": "OpenDMARC Filter v1.4.2 sourceware.org E716F4BA23F4", "ARC-Filter": "OpenARC Filter v1.0.0 sourceware.org E716F4BA23F4", "ARC-Seal": "i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1776852809; cv=none;\n b=M+bPuUQtHMM5fnuvR+scL38xBGl5X3Dolwkignwd3toFn/tHML8IrcQanxOeC7S/PvIvw5sz5D8DyKUSmc63z6C4CKFybCCAUVd4wu92gFXYSm2AgZL4rH34w/DfaI4DwGYsaMyQcOE4FjNIm0jYoX9XtucS4pJrO36qzzW4M3w=", "ARC-Message-Signature": "i=1; a=rsa-sha256; d=sourceware.org; s=key;\n t=1776852809; c=relaxed/simple;\n bh=0FzIYbkYXcV90wxSFVFiP9L7bTgLameIbTM0ltzp59E=;\n h=From:Date:Subject:To:Message-ID;\n b=KQKt1PtsxZYAQqDga3fDbg3Znja0Kfaqve3mRfsvj1VUF04h97JWyOt9a4murBHCgWwHaBY8fxc4ykb+tIZk+onLfs0e/yD8fDZ3SI7lECa5N39VwWNOkRHI8WKh8DfApYEGbdxUD3UI9HjvRPTs/gtcQElss8Va7HVFg9kRjdU=", "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 10:13:03 +0000", "Subject": "[PATCH v1 1/1] libstdc++: Fix complexity of drop_view::begin const\n [PR112641]", "To": "gcc-patches mailing list <gcc-patches@gcc.gnu.org>", "Message-ID": "\n <bmm.hhuawf4oe6.gcc.gcc-TEST.ppalka.8.1.1@forge-stage.sourceware.org>", "X-Mailer": "batrachomyomachia", "X-Requested-Reviewer": "redi", "X-Pull-Request-Organization": "gcc", "X-Pull-Request-Repository": "gcc-TEST", "X-Pull-Request": "https://forge.sourceware.org/gcc/gcc-TEST/pulls/8", "References": "\n <bmm.hhuawf4oe6.gcc.gcc-TEST.ppalka.8.1.0@forge-stage.sourceware.org>", "In-Reply-To": "\n <bmm.hhuawf4oe6.gcc.gcc-TEST.ppalka.8.1.0@forge-stage.sourceware.org>", "X-Patch-URL": "\n https://forge.sourceware.org/gcc/gcc-TEST/commit/b184fad509fba4941ceb9ec61427a754e677850a", "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\nViews are required to have a amortized O(1) begin(), but our drop_view's\nconst begin overload is O(n) for non-common ranges. This patch\nreimplements it so that it's O(1) even in that case. See also LWG 4009.\n\n\tPR libstdc++/112641\n\nlibstdc++-v3/ChangeLog:\n\n\t* include/std/ranges (drop_view::begin const): Reimplement\n\tso that it's O(1) instead of O(n) even in the non-common\n\trange case.\n\t* testsuite/std/ranges/adaptors/drop.cc (test10): New test.\n---\n libstdc++-v3/include/std/ranges | 4 ++--\n libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc | 12 ++++++++++++\n 2 files changed, 14 insertions(+), 2 deletions(-)", "diff": "diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges\nindex cebe10683f91..743429dbceae 100644\n--- a/libstdc++-v3/include/std/ranges\n+++ b/libstdc++-v3/include/std/ranges\n@@ -2664,8 +2664,8 @@ namespace views::__adaptor\n begin() const\n \trequires random_access_range<const _Vp> && sized_range<const _Vp>\n {\n-\treturn ranges::next(ranges::begin(_M_base), _M_count,\n-\t\t\t ranges::end(_M_base));\n+\treturn ranges::begin(_M_base) + ranges::min(ranges::distance(_M_base),\n+\t\t\t\t\t\t _M_count);\n }\n \n constexpr auto\ndiff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc\nindex c9987c61e3c1..0bd5bebb785d 100644\n--- a/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc\n+++ b/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc\n@@ -274,6 +274,17 @@ test09()\n static_assert(!requires { views::all | drop; });\n }\n \n+constexpr bool\n+test10()\n+{\n+ // PR libstdc++/112641 - drop_view::begin const may have O(n) complexity\n+ const auto s = ranges::subrange(views::iota(size_t(1)), size_t(-1));\n+ const auto r = ranges::drop_view(s, s.size() - 1);\n+ const auto b = r.begin(); // time out\n+ VERIFY( *b == size_t(-1) );\n+ return true;\n+}\n+\n int\n main()\n {\n@@ -286,4 +297,5 @@ main()\n test07();\n test08();\n test09();\n+ static_assert(test10());\n }\n", "prefixes": [ "v1", "1/1" ] }