From patchwork Mon Nov 14 04:50:45 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Palka X-Patchwork-Id: 19542 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:6687:0:0:0:0:0 with SMTP id l7csp1964700wru; Sun, 13 Nov 2022 20:53:00 -0800 (PST) X-Google-Smtp-Source: AA0mqf6Cx/4demZEvFhmUjQmgHhKSKpMu3ifb7IkZ29jDzVqma/wojj9rDi4ZvDxauMGFxP6S0TN X-Received: by 2002:aa7:dc03:0:b0:462:6a0c:cfa with SMTP id b3-20020aa7dc03000000b004626a0c0cfamr9901660edu.349.1668401580099; Sun, 13 Nov 2022 20:53:00 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1668401580; cv=none; d=google.com; s=arc-20160816; b=feMaud30yuUojSHjFPgvCD8dc3DMotfRg5fTIC1DlmMEl8zVwy3nIXHhTjqWd3nKW7 MjK7K8GarhnlXr4IqbjDD2dobVaP6ir/ORt8c0jPcS+yJ0HxOeFgQzMnkznw7zIlXGJI FGx89g4CvVvFqtTvRN6gpaZ5kQLuYENQGtJEkf/kxPhNnS+RWs+grnsq8GBpIJPo/Ed5 0rJK8HBjGxJSyoXCDAK8ly8HxZnFunnDoT6MgmyRWDMZUOZuRnlTMCppjVJ7OPrp+qsd xJ4B7GxeUQJdJVWAjEqi6lHVXZOotiV43ROUswEH5C6XaH57gnyFd+vxiNOfJKyBraN5 spVQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:reply-to:from:list-subscribe:list-help:list-post :list-archive:list-unsubscribe:list-id:precedence :content-transfer-encoding:mime-version:message-id:date:subject:cc :to:dmarc-filter:delivered-to:dkim-signature:dkim-filter; bh=2pAnce0g7TJHx3/BjfLiCZGyTlrq+4t8a0UtAFhdkTY=; b=tSj3H3aEUz25HKXKjkjym2PwoqemHAe5r6DBS+XBAnXwnOavBC+oF+rlXJemvn/GMZ FWZn6jC/KLnfWbwFS0XFM0LAvlXUBX5l4LwQZiiJjiCD0R51vdsoGGwYuaJzCE2rPsWc kBt/ubY3a8mm790mTKgJZ+f5ytSrWHOTkt+KZvJI3fLLx3aDD2o4Yvo9HXIsa2CTuDqs bPVMsgSO7CwOZ94KK5IEgN5tdiONwHlTMmBSecWrByfYfw1yyGN5pLuFrLzOA7RtuiIQ iSP2nVDxsWc7yu2LG0gkPiOl81ftbLV1s5J6gSa9hIyifiGK4hsyNVBybWRwIvLWzmeE anuQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=JW4c30yU; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from sourceware.org (server2.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id a3-20020a50e703000000b00462dca18096si7972708edn.520.2022.11.13.20.52.59 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 13 Nov 2022 20:53:00 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=JW4c30yU; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 2A1663835782 for ; Mon, 14 Nov 2022 04:52:09 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 2A1663835782 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1668401529; bh=2pAnce0g7TJHx3/BjfLiCZGyTlrq+4t8a0UtAFhdkTY=; h=To:Cc:Subject:Date:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=JW4c30yUPyv/AjaFB0BpczTvPkxjaHkTfmcHD6Y2KBx38DJdhmjxkzu1MZoTVXcAY 9n1JAoHVbLR9GcNYrc+Sw4leIuCXfR0LHhfZ36lIjWj8apoKxb2hwwMAkFaSYNxR42 fLMIleV0QTKe7HzJVAXc5yitnBsyFSov64xjsyKs= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id 1C55B3851885 for ; Mon, 14 Nov 2022 04:51:22 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 1C55B3851885 Received: from mail-qv1-f72.google.com (mail-qv1-f72.google.com [209.85.219.72]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-270-Cn863VYRNJyF5xuWCWzf2w-1; Sun, 13 Nov 2022 23:51:18 -0500 X-MC-Unique: Cn863VYRNJyF5xuWCWzf2w-1 Received: by mail-qv1-f72.google.com with SMTP id mo15-20020a056214330f00b004b96d712bccso7910790qvb.22 for ; Sun, 13 Nov 2022 20:51:18 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=2pAnce0g7TJHx3/BjfLiCZGyTlrq+4t8a0UtAFhdkTY=; b=e090DlQPRPDKpgyCy/3dycca88K7mC86SNxEomMNI4mUlZFcuVSk3ZR2RTdix+sox+ XI3qxWnA/5FpoYcYqedz6QLm8F92wwiUDIhYixv8fS6lx0IYG/Ttbp+BSKrWhMow+53g 6wbhp5wf685g3JLYtCskuqGT2xkoxPRfdWLslKIGnMV7le2VIeWBoh4ADjilECwl9umv FKDUFG5EX2k2E6T+5armU8OkQmTWF9ssD+3mSaUPg73gTWDAxuPr0ozMt2ykUs4Gcq6g 9EGoGLzJKa+8m4kZpDj9/dfR0QuDG0njPvnfnje1SXkaKzMLdZ/z9B7NYBVSWHRSZbj+ aRrw== X-Gm-Message-State: ANoB5pkE1BF9w2IBc0TX/wBamTaTPuEGjadNixIywHPliMUC2JPa5qdO o2PwXzVUa6lQSqdgooROGsuRCorsakylI1+db5hy0R1r74bGmFyPrI3RZivd/hBlV2e2CWb+MeO UUiaFSZjgStuCx/w7LKQOT2lvIMNOsrl1TpL5D+2e4sVEvoeaQk2X3zBSUptQaGs3WHo= X-Received: by 2002:a37:b086:0:b0:6fa:330c:fb05 with SMTP id z128-20020a37b086000000b006fa330cfb05mr9990463qke.73.1668401477129; Sun, 13 Nov 2022 20:51:17 -0800 (PST) X-Received: by 2002:a37:b086:0:b0:6fa:330c:fb05 with SMTP id z128-20020a37b086000000b006fa330cfb05mr9990452qke.73.1668401476815; Sun, 13 Nov 2022 20:51:16 -0800 (PST) Received: from localhost.localdomain (ool-457670bb.dyn.optonline.net. [69.118.112.187]) by smtp.gmail.com with ESMTPSA id x7-20020ac84a07000000b0035badb499c7sm5180567qtq.21.2022.11.13.20.51.15 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 13 Nov 2022 20:51:16 -0800 (PST) To: gcc-patches@gcc.gnu.org Cc: libstdc++@gcc.gnu.org, Patrick Palka Subject: [PATCH 1/3] libstdc++: Implement ranges::contains/contains_subrange from P2302R4 Date: Sun, 13 Nov 2022 23:50:45 -0500 Message-Id: <20221114045047.362745-1-ppalka@redhat.com> X-Mailer: git-send-email 2.38.1.420.g319605f8f0 MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-13.5 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_NUMSUBJECT, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Patrick Palka via Gcc-patches From: Patrick Palka Reply-To: Patrick Palka Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1749445855640385007?= X-GMAIL-MSGID: =?utf-8?q?1749445855640385007?= Tested on x86_64-pc-linux-gnu, does this look OK for trunk? libstdc++-v3/ChangeLog: * include/bits/ranges_algo.h (__contains_fn, contains): Define. (__contains_subrange_fn, contains_subrange): Define. * testsuite/25_algorithms/contains/1.cc: New test. * testsuite/25_algorithms/contains_subrange/1.cc: New test. --- libstdc++-v3/include/bits/ranges_algo.h | 54 +++++++++++++++++++ .../testsuite/25_algorithms/contains/1.cc | 33 ++++++++++++ .../25_algorithms/contains_subrange/1.cc | 35 ++++++++++++ 3 files changed, 122 insertions(+) create mode 100644 libstdc++-v3/testsuite/25_algorithms/contains/1.cc create mode 100644 libstdc++-v3/testsuite/25_algorithms/contains_subrange/1.cc diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h index de71bd07a2f..da0ca981dc3 100644 --- a/libstdc++-v3/include/bits/ranges_algo.h +++ b/libstdc++-v3/include/bits/ranges_algo.h @@ -3464,6 +3464,60 @@ namespace ranges inline constexpr __prev_permutation_fn prev_permutation{}; +#if __cplusplus > 202002L + struct __contains_fn + { + template _Sent, + typename _Tp, typename _Proj = identity> + requires indirect_binary_predicate, const _Tp*> + constexpr bool + operator()(_Iter __first, _Sent __last, const _Tp& __value, _Proj __proj = {}) const + { return ranges::find(std::move(__first), __last, __value, __proj) != __last; } + + template + requires indirect_binary_predicate, _Proj>, const _Tp*> + constexpr bool + operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const + { return (*this)(ranges::begin(__r), ranges::end(__r), __value, std::move(__proj)); } + }; + + inline constexpr __contains_fn contains{}; + + struct __contains_subrange_fn + { + template _Sent1, + forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2, + typename _Pred = ranges::equal_to, + typename Proj1 = identity, typename Proj2 = identity> + requires indirectly_comparable<_Iter1, _Iter2, _Pred, Proj1, Proj2> + constexpr bool + operator()(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, + _Pred __pred = {}, Proj1 __proj1 = {}, Proj2 __proj2 = {}) const + { + return __first2 == __last2 + || !ranges::search(__first1, __last1, __first2, __last2, + std::move(__pred), std::move(__proj1), std::move(__proj2)).empty(); + } + + template + requires indirectly_comparable, iterator_t<_Range2>, + _Pred, _Proj1, _Proj2> + constexpr bool + operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {}, + _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const + { + return (*this)(ranges::begin(__r1), ranges::end(__r1), + ranges::begin(__r2), ranges::end(__r2), + std::move(__pred), std::move(__proj1), std::move(__proj2)); + } + }; + + inline constexpr __contains_subrange_fn contains_subrange{}; +#endif // C++23 } // namespace ranges #define __cpp_lib_shift 201806L diff --git a/libstdc++-v3/testsuite/25_algorithms/contains/1.cc b/libstdc++-v3/testsuite/25_algorithms/contains/1.cc new file mode 100644 index 00000000000..146ab593b70 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/contains/1.cc @@ -0,0 +1,33 @@ +// { dg-options "-std=gnu++23" } +// { dg-do run { target c++23 } } + +#include +#include +#include + +namespace ranges = std::ranges; + +void +test01() +{ + int x[] = {1,2,3}; + using to_input = __gnu_test::test_input_range; + VERIFY( ranges::contains(to_input(x), 1) ); + VERIFY( ranges::contains(to_input(x), 2) ); + VERIFY( ranges::contains(to_input(x), 3) ); + VERIFY( !ranges::contains(to_input(x), 4) ); + VERIFY( !ranges::contains(x, x+2, 3) ); + auto neg = [](int n) { return -n; }; + VERIFY( ranges::contains(to_input(x), -1, neg) ); + VERIFY( ranges::contains(to_input(x), -2, neg) ); + VERIFY( ranges::contains(to_input(x), -3, neg) ); + VERIFY( !ranges::contains(to_input(x), -4, neg) ); + + VERIFY( !ranges::contains(x, x+2, -3, neg) ); +} + +int +main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/25_algorithms/contains_subrange/1.cc b/libstdc++-v3/testsuite/25_algorithms/contains_subrange/1.cc new file mode 100644 index 00000000000..62b92795f94 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/contains_subrange/1.cc @@ -0,0 +1,35 @@ +// { dg-options "-std=gnu++23" } +// { dg-do run { target c++23 } } + +#include +#include +#include + +namespace ranges = std::ranges; + +void +test01() +{ + int x[] = {1,2,3,4,5}; + int y[] = {2,3,4}; + int z[] = {4,5,6}; + __gnu_test::test_forward_range rx(x); + __gnu_test::test_forward_range ry(y); + __gnu_test::test_forward_range rz(z); + VERIFY( ranges::contains_subrange(rx, ry) ); + VERIFY( !ranges::contains_subrange(rx, rz) ); + VERIFY( ranges::contains_subrange(rx, ry, ranges::less{}) ); + VERIFY( ranges::contains_subrange(rx, rz, ranges::less{}) ); + auto plus3 = [](int n) { return n+3; }; + VERIFY( !ranges::contains_subrange(rx, ry, ranges::equal_to{}, plus3) ); + VERIFY( ranges::contains_subrange(rx, rz, ranges::equal_to{}, plus3) ); + + VERIFY( ranges::contains_subrange(x, x+2, y, y+1) ); + VERIFY( !ranges::contains_subrange(x, x+2, y, y+2) ); +} + +int +main() +{ + test01(); +}