From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTPS id 9870C385558F for ; Mon, 14 Nov 2022 15:07:05 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 9870C385558F Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1668438425; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=H/9AAtycwLyGejYQWBUmc720bSvbAlFmktBHvI641m8=; b=VXR8XkrgpwPMurZDoyMGpEcMHYnaM6fPnuNM9oEjs49ZUDrhxa2q8xcmpiLx3ne0Ni8GSa 30HCCS9hsJDnhQbvHk6zmnYLj3ZSdkZtyNWqhahFRTlxfZjSqzis5Jjr+/MPMEmkHGPBzi e4zxGNhRfcMQk7wo3MoOqde6Zx7EzxY= Received: from mail-qk1-f198.google.com (mail-qk1-f198.google.com [209.85.222.198]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-269-8x5z6wWwOlmiPmogyt3wcw-1; Mon, 14 Nov 2022 10:07:03 -0500 X-MC-Unique: 8x5z6wWwOlmiPmogyt3wcw-1 Received: by mail-qk1-f198.google.com with SMTP id q14-20020a05620a0d8e00b006ef0350dae1so11166252qkl.12 for ; Mon, 14 Nov 2022 07:07:03 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=mime-version:references:message-id:in-reply-to:subject:cc:to:date :from:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=H/9AAtycwLyGejYQWBUmc720bSvbAlFmktBHvI641m8=; b=5hiD4LgY08nyBaVW8nF8pWcu0h4C5b7dUp+yMhbHxhjZFrxHzBumRlRHeGc6zlgK8h +NXcJaTn2fnntr1hyxACW2CFDYplrjUeWa19VvUvxtiY7pL2U+02igQVUbbpw/E89QIK Laev3oMcnp4WYQPjnVIkYkqEqtbIwzhtd2ATgbkqjvpvISkQ7/xHJV5TjlMGAbuh2Bts 0NhP6IuGFPXWvpNkU2j0NulbzOwJi3sWNvK3NZz5HVGcTggnUCjr04k0qryUoG5/DgXE uptYxixwFlqA+m0B4/QZ39Nyl0xV9JrJ7lC8sT75pFRInBOHZGEui16JX3lNdNF+0X99 boow== X-Gm-Message-State: ANoB5pnFSnqaiAcS8Q55z6oVxpijzxkpUn3YhItPbACy386MIFhom3ID Od4ubL+3qlRWdlRCPtjdA66pE0ImgbnAy3KzPIvGXZkO4hC6yifu10D/6jjo15kSVZCIdBB7czD MdY6y4nK4fKuKZfA= X-Received: by 2002:ae9:ed06:0:b0:6fb:8dc:7eaa with SMTP id c6-20020ae9ed06000000b006fb08dc7eaamr11673078qkg.621.1668438423204; Mon, 14 Nov 2022 07:07:03 -0800 (PST) X-Google-Smtp-Source: AA0mqf7Fi22CcOd38OVSxHARRZBE0Y+Bd69k4CFXSNvhK51usscKbS7HafA1dRGLLS4b3ewET8BMHA== X-Received: by 2002:ae9:ed06:0:b0:6fb:8dc:7eaa with SMTP id c6-20020ae9ed06000000b006fb08dc7eaamr11673059qkg.621.1668438422885; Mon, 14 Nov 2022 07:07:02 -0800 (PST) Received: from [192.168.1.130] (ool-457670bb.dyn.optonline.net. [69.118.112.187]) by smtp.gmail.com with ESMTPSA id bw25-20020a05622a099900b003a580cd979asm5754218qtb.58.2022.11.14.07.07.01 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 14 Nov 2022 07:07:02 -0800 (PST) From: Patrick Palka X-Google-Original-From: Patrick Palka Date: Mon, 14 Nov 2022 10:07:01 -0500 (EST) To: Jonathan Wakely cc: Patrick Palka , gcc-patches@gcc.gnu.org, libstdc++@gcc.gnu.org Subject: Re: [PATCH 1/3] libstdc++: Implement ranges::contains/contains_subrange from P2302R4 In-Reply-To: Message-ID: <3c302b46-3b20-b477-7f45-f76635e4f4be@idea> References: <20221114045047.362745-1-ppalka@redhat.com> MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=US-ASCII X-Spam-Status: No, score=-13.7 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=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: On Mon, 14 Nov 2022, Jonathan Wakely wrote: > On Mon, 14 Nov 2022 at 04:51, Patrick Palka via Libstdc++ > wrote: > > > > 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 > + projected<_Iter, _Proj>, 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; } > > Should this use std::move(__proj)? Oops yes, IIUC std::move'ing projections isn't necessary since they're copyable and equality preserving, but doing so is consistent with the rest of the ranges algos which tend to std::move function objects. -- >8 -- Subject: [PATCH 1/3] libstdc++: Implement ranges::contains/contains_subrange from P2302R4 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 | 37 +++++++++++++ 3 files changed, 124 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..11206bdbcaa 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, std::move(__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..6c3c99c0fd6 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/contains_subrange/1.cc @@ -0,0 +1,37 @@ +// { 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, {}, plus3) ); + VERIFY( ranges::contains_subrange(rx, rz, {}, plus3) ); + VERIFY( ranges::contains_subrange(rx, ry, {}, plus3, plus3) ); + VERIFY( !ranges::contains_subrange(rx, rz, {}, plus3, plus3) ); + + VERIFY( ranges::contains_subrange(x, x+2, y, y+1) ); + VERIFY( !ranges::contains_subrange(x, x+2, y, y+2) ); +} + +int +main() +{ + test01(); +} -- 2.38.1.420.g319605f8f0