From patchwork Wed Sep 14 14:19:00 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Palka X-Patchwork-Id: 1209 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:5044:0:0:0:0:0 with SMTP id h4csp2839503wrt; Wed, 14 Sep 2022 07:20:07 -0700 (PDT) X-Google-Smtp-Source: AA6agR4L/tGrUTemPH5xMLvjXfQybRKstUy5r/jumIpDyS5e49xEYM0hPAkP/7ftaMyWaADiuWpR X-Received: by 2002:a17:906:8455:b0:773:c45b:d970 with SMTP id e21-20020a170906845500b00773c45bd970mr22663741ejy.46.1663165207239; Wed, 14 Sep 2022 07:20:07 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1663165207; cv=none; d=google.com; s=arc-20160816; b=V2EKvJlTTfDozdWZl8jdjTM/AdbTdMlQMpBZEGULoZranKLyNGVU1ziNvLlWBqyjxR UEL0Hpqu8mgZsBvl1WThoijWUHJYzMTKD/YIVYTjkz7Otm4kxYKitDGrdEeL7pko45HB 3Ufmg5jbzgxxsC1hBkS96El/ohL1LzY7A3e98Z4Zx0XxvM4G6T36vIRTK3DlMkqyXbly Z5XVzqx3pgeKtiw+Svq9d8ySDY6Jutc44LDXImU1lTEGSG4lyojDWjNefdvwNFybb4uO e9rUrBDE7lx2H8PXf28sfs7qWb8hkqQ27Aq4b1tr5ps7NfV+zgFVcJmcYVhXdFZyoYib pBGQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:cc: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:to :dmarc-filter:delivered-to:dkim-signature:dkim-filter; bh=faphKzWehiSXrs3ZOfMdLO0HjDlxlONe5yS9N+2BAAg=; b=GD/KpbVAhPzboIn6jit4AMGxCDaW32adMDGLhmzj+W6I9hmruyiec3pOfFygbLIv5s S7KZSAqtbcY4nJ5Uc6HAxwuRyVPJ9t5R0J7hR9117IomCJdtMNwnzbZNyi5QqPfpee71 ABG80AUcRAeQTupUlLPk8ud5f9WaGPYwU43XvqpsxngzjaffuYUr0T+CM+AI3D21VQXG VGZCWKX2QaVEk8r1FcRM9SIWhZzRWlLXAAntHPXEMbPf6kSocAHc7nBIWMTV+Fan6qJ6 Q3poxf4l9rTfLA51qR7wu/apaZe6viTgRwdOQbNs5+W94/3AkHmAkH1lietH93CHW3eF aIPg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b="aKl2z/MF"; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c 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. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id x22-20020a170906711600b00780429cae96si457895ejj.412.2022.09.14.07.20.06 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 14 Sep 2022 07:20:07 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) client-ip=2620:52:3:1:0:246e:9693:128c; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b="aKl2z/MF"; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c 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 4399E3851147 for ; Wed, 14 Sep 2022 14:19:51 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 4399E3851147 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1663165191; bh=faphKzWehiSXrs3ZOfMdLO0HjDlxlONe5yS9N+2BAAg=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=aKl2z/MFpaF3kUaIip2/z8ycc0zX2NphwY7YBdqu9i9jWP33axIscZLnoOkiFVm19 Wl0eFvarRuWzeSfCMFLnxiRWXIErDtpkT2DOVIVosANRSJH4Ta7tvs7T/+WgsXpLO3 93PAA4jNNvb3vHuPJczGVOR0fMnNr2Oe3isZ8Xa0= 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 25AFF3858427 for ; Wed, 14 Sep 2022 14:19:07 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 25AFF3858427 Received: from mail-qk1-f199.google.com (mail-qk1-f199.google.com [209.85.222.199]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-618-i7dxuD5XOya6jxQn7l0i8w-1; Wed, 14 Sep 2022 10:19:03 -0400 X-MC-Unique: i7dxuD5XOya6jxQn7l0i8w-1 Received: by mail-qk1-f199.google.com with SMTP id m19-20020a05620a24d300b006bb85a44e96so13241617qkn.23 for ; Wed, 14 Sep 2022 07:19:03 -0700 (PDT) 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; bh=faphKzWehiSXrs3ZOfMdLO0HjDlxlONe5yS9N+2BAAg=; b=XrucCWH1zkUNQLqUTyN4UBh9uSfugMgnX1OKF2OiTpOv77CvN+wNcCwIL5GDBY5ZAn vzIvZ0cOJuVzzYIWOuWfpAcfB0Oy1Vp+I5TKLLwFCYAthvBnbUUiImhGeIfqH5GrOSz/ 0zXiutzMBlRAaKkDwCMyw8D5wBFOQRRHBE6/UFZZ3R1s8uArT63olZDgm5leIsJrJxG+ yAqRMvSkzHMb7PeMG4i5iBz6tMRH1qqQZcgecyHluQ62GWNHW0YJauT5F8P4m+qhNFNh i0jCYXL1dZqJBoCYfuz8QkcGRh8YOa5LtKkuxP1yfFQj6ZRENcfJCHH3tPOBcz574Fky QJ8Q== X-Gm-Message-State: ACgBeo3hGnmhRSkNUvqRPcvI3BtDSdxjIAy8pgDxVFs+wCBF7lOtL5Jw T2fuy9TiKy253g/nAavgX+br3cLOf3KvfoClbcovNVmtemHUpiCdo+xt2r/rcYWXQzW9ugk+Btr pqyFsapWBgLNeyYpldperBOcPATc0t4emoPJFNMnKYDT1DPggtca4+w0WnRTI+o4qpSU= X-Received: by 2002:a37:9ac2:0:b0:6cd:e304:7189 with SMTP id c185-20020a379ac2000000b006cde3047189mr17328501qke.536.1663165143169; Wed, 14 Sep 2022 07:19:03 -0700 (PDT) X-Received: by 2002:a37:9ac2:0:b0:6cd:e304:7189 with SMTP id c185-20020a379ac2000000b006cde3047189mr17328465qke.536.1663165142765; Wed, 14 Sep 2022 07:19:02 -0700 (PDT) Received: from localhost.localdomain (ool-457670bb.dyn.optonline.net. [69.118.112.187]) by smtp.gmail.com with ESMTPSA id bn29-20020a05620a2add00b006bb2cd2f6d1sm1792396qkb.127.2022.09.14.07.19.02 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 14 Sep 2022 07:19:02 -0700 (PDT) To: gcc-patches@gcc.gnu.org Subject: [PATCH] libstdc++: Implement ranges::chunk_by_view from P2443R1 Date: Wed, 14 Sep 2022 10:19:00 -0400 Message-Id: <20220914141900.3489407-1-ppalka@redhat.com> X-Mailer: git-send-email 2.37.3.611.ge188ec3a73 MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-14.1 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_LOW, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE 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 Cc: libstdc++@gcc.gnu.org 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?1743955120313604841?= X-GMAIL-MSGID: =?utf-8?q?1743955120313604841?= Tested on x86_64-pc-linux-gnu, does this look OK for trunk? libstdc++-v3/ChangeLog: * include/bits/ranges_algo.h (__adjacent_find_fn, adjacent_find): Move to ... * include/bits/ranges_util.h: ... here. * include/std/ranges (chunk_by_view): Define. (chunk_by_view::_Iterator): Define. (__detail::__can_chunk_by_view): Define. (_ChunkBy, chunk_by): Define. * testsuite/std/ranges/adaptors/chunk_by/1.cc: New test. --- libstdc++-v3/include/bits/ranges_algo.h | 38 +--- libstdc++-v3/include/bits/ranges_util.h | 38 ++++ libstdc++-v3/include/std/ranges | 193 ++++++++++++++++++ .../std/ranges/adaptors/chunk_by/1.cc | 58 ++++++ 4 files changed, 290 insertions(+), 37 deletions(-) create mode 100644 libstdc++-v3/testsuite/std/ranges/adaptors/chunk_by/1.cc diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h index 2a116361a67..228e10b62bf 100644 --- a/libstdc++-v3/include/bits/ranges_algo.h +++ b/libstdc++-v3/include/bits/ranges_algo.h @@ -506,43 +506,7 @@ namespace ranges inline constexpr __find_end_fn find_end{}; - struct __adjacent_find_fn - { - template _Sent, - typename _Proj = identity, - indirect_binary_predicate, - projected<_Iter, _Proj>> _Pred - = ranges::equal_to> - constexpr _Iter - operator()(_Iter __first, _Sent __last, - _Pred __pred = {}, _Proj __proj = {}) const - { - if (__first == __last) - return __first; - auto __next = __first; - for (; ++__next != __last; __first = __next) - { - if (std::__invoke(__pred, - std::__invoke(__proj, *__first), - std::__invoke(__proj, *__next))) - return __first; - } - return __next; - } - - template, _Proj>, - projected, _Proj>> _Pred = ranges::equal_to> - constexpr borrowed_iterator_t<_Range> - operator()(_Range&& __r, _Pred __pred = {}, _Proj __proj = {}) const - { - return (*this)(ranges::begin(__r), ranges::end(__r), - std::move(__pred), std::move(__proj)); - } - }; - - inline constexpr __adjacent_find_fn adjacent_find{}; + // adjacent_find is defined in . struct __is_permutation_fn { diff --git a/libstdc++-v3/include/bits/ranges_util.h b/libstdc++-v3/include/bits/ranges_util.h index bb56deee01b..85ddea68407 100644 --- a/libstdc++-v3/include/bits/ranges_util.h +++ b/libstdc++-v3/include/bits/ranges_util.h @@ -704,6 +704,44 @@ namespace ranges inline constexpr __min_fn min{}; + struct __adjacent_find_fn + { + template _Sent, + typename _Proj = identity, + indirect_binary_predicate, + projected<_Iter, _Proj>> _Pred + = ranges::equal_to> + constexpr _Iter + operator()(_Iter __first, _Sent __last, + _Pred __pred = {}, _Proj __proj = {}) const + { + if (__first == __last) + return __first; + auto __next = __first; + for (; ++__next != __last; __first = __next) + { + if (std::__invoke(__pred, + std::__invoke(__proj, *__first), + std::__invoke(__proj, *__next))) + return __first; + } + return __next; + } + + template, _Proj>, + projected, _Proj>> _Pred = ranges::equal_to> + constexpr borrowed_iterator_t<_Range> + operator()(_Range&& __r, _Pred __pred = {}, _Proj __proj = {}) const + { + return (*this)(ranges::begin(__r), ranges::end(__r), + std::move(__pred), std::move(__proj)); + } + }; + + inline constexpr __adjacent_find_fn adjacent_find{}; + } // namespace ranges using ranges::get; diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges index 44a4df8b5d5..53093a3762f 100644 --- a/libstdc++-v3/include/std/ranges +++ b/libstdc++-v3/include/std/ranges @@ -6676,6 +6676,199 @@ namespace views::__adaptor inline constexpr _Slide slide; } + + template, iterator_t<_Vp>> _Pred> + requires view<_Vp> && is_object_v<_Pred> + class chunk_by_view : public view_interface> + { + _Vp _M_base = _Vp(); + __detail::__box<_Pred> _M_pred = _Pred(); + __detail::_CachedPosition<_Vp> _M_cached_begin; + + constexpr iterator_t<_Vp> + _M_find_next(iterator_t<_Vp> __current) + { + __glibcxx_assert(_M_pred.has_value()); + auto __pred = [this](_Tp&& __x, _Tp&& __y) { + return !bool((*_M_pred)(std::forward<_Tp>(__x), std::forward<_Tp>(__y))); + }; + auto __it = ranges::adjacent_find(__current, ranges::end(_M_base), __pred); + return ranges::next(__it, 1, ranges::end(_M_base)); + } + + constexpr iterator_t<_Vp> + _M_find_prev(iterator_t<_Vp> __current) requires bidirectional_range<_Vp> + { + __glibcxx_assert(_M_pred.has_value()); + auto __pred = [this](_Tp&& __x, _Tp&& __y) { + return !bool((*_M_pred)(std::forward<_Tp>(__y), std::forward<_Tp>(__x))); + }; + auto __rbegin = std::make_reverse_iterator(__current); + auto __rend = std::make_reverse_iterator(ranges::begin(_M_base)); + __glibcxx_assert(__rbegin != __rend); + auto __it = ranges::adjacent_find(__rbegin, __rend, __pred).base(); + return ranges::prev(__it, 1, ranges::begin(_M_base)); + } + + class _Iterator; + + public: + chunk_by_view() requires (default_initializable<_Vp> + && default_initializable<_Pred>) + = default; + + constexpr explicit + chunk_by_view(_Vp __base, _Pred __pred) + : _M_base(std::move(__base)), _M_pred(std::move(__pred)) + { } + + constexpr _Vp + base() const & requires copy_constructible<_Vp> + { return _M_base; } + + constexpr _Vp + base() && + { return std::move(_M_base); } + + constexpr const _Pred& + pred() const + { return *_M_pred; } + + constexpr _Iterator + begin() + { + __glibcxx_assert(_M_pred.has_value()); + iterator_t<_Vp> __it; + if (_M_cached_begin._M_has_value()) + __it = _M_cached_begin._M_get(_M_base); + else + { + __it = _M_find_next(ranges::begin(_M_base)); + _M_cached_begin._M_set(_M_base, __it); + } + return _Iterator(*this, ranges::begin(_M_base), __it); + } + + constexpr auto + end() + { + if constexpr (common_range<_Vp>) + return _Iterator(*this, ranges::end(_M_base), ranges::end(_M_base)); + else + return default_sentinel; + } + }; + + template + chunk_by_view(_Range&&, _Pred) -> chunk_by_view, _Pred>; + + template, iterator_t<_Vp>> _Pred> + requires view<_Vp> && is_object_v<_Pred> + class chunk_by_view<_Vp, _Pred>::_Iterator + { + chunk_by_view* _M_parent = nullptr; + iterator_t<_Vp> _M_current = iterator_t<_Vp>(); + iterator_t<_Vp> _M_next = iterator_t<_Vp>(); + + constexpr + _Iterator(chunk_by_view& __parent, iterator_t<_Vp> __current, iterator_t<_Vp> __next) + : _M_parent(std::__addressof(__parent)), _M_current(__current), _M_next(__next) + { } + + static auto + _S_iter_concept() + { + if constexpr (bidirectional_range<_Vp>) + return bidirectional_iterator_tag{}; + else + return forward_iterator_tag{}; + } + + friend chunk_by_view; + + public: + using value_type = subrange>; + using difference_type = range_difference_t<_Vp>; + using iterator_category = input_iterator_tag; + using iterator_concept = decltype(_S_iter_concept()); + + _Iterator() = default; + + constexpr value_type + operator*() const + { + __glibcxx_assert(_M_current != _M_next); + return ranges::subrange(_M_current, _M_next); + } + + constexpr _Iterator& + operator++() + { + __glibcxx_assert(_M_current != _M_next); + _M_current = _M_next; + _M_next = _M_parent->_M_find_next(_M_current); + return *this; + } + + constexpr _Iterator + operator++(int) + { + auto __tmp = *this; + ++*this; + return __tmp; + } + + constexpr _Iterator& + operator--() requires bidirectional_range<_Vp> + { + _M_next = _M_current; + _M_current = _M_parent->_M_find_prev(_M_next); + return *this; + } + + constexpr _Iterator + operator--(int) requires bidirectional_range<_Vp> + { + auto __tmp = *this; + --*this; + return __tmp; + } + + friend constexpr bool + operator==(const _Iterator& __x, const _Iterator& __y) + { return __x._M_current == __y._M_current; } + + friend constexpr bool + operator==(const _Iterator& __x, default_sentinel_t) + { return __x._M_current == __x._M_next; } + }; + + namespace views + { + namespace __detail + { + template + concept __can_chunk_by_view + = requires { chunk_by_view(std::declval<_Range>(), std::declval<_Pred>()); }; + } + + struct _ChunkBy : __adaptor::_RangeAdaptor<_ChunkBy> + { + template + requires __detail::__can_chunk_by_view<_Range, _Pred> + constexpr auto + operator() [[nodiscard]] (_Range&& __r, _Pred&& __pred) const + { return chunk_by_view(std::forward<_Range>(__r), std::forward<_Pred>(__pred)); } + + using __adaptor::_RangeAdaptor<_ChunkBy>::operator(); + static constexpr int _S_arity = 2; + static constexpr bool _S_has_simple_extra_args = true; + }; + + inline constexpr _ChunkBy chunk_by; + } #endif // C++23 } // namespace ranges diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/chunk_by/1.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/chunk_by/1.cc new file mode 100644 index 00000000000..d57b127fbc8 --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/chunk_by/1.cc @@ -0,0 +1,58 @@ +// { dg-options "-std=gnu++23" } +// { dg-do run { target c++23 } } + +#include +#include +#include +#include +#include + +namespace ranges = std::ranges; +namespace views = std::views; + +constexpr bool +test01() +{ + int x[] = {1, 2, 2, 3, 0, 4, 5, 2}; + auto v = x | views::chunk_by(ranges::less_equal{}); + static_assert(ranges::bidirectional_range + && ranges::common_range); + VERIFY( ranges::equal(v, (std::initializer_list[]){{1, 2, 2, 3}, {0, 4, 5}, {2}}, + ranges::equal) ); + VERIFY( ranges::equal(v | views::reverse, + (std::initializer_list[]){{2}, {0, 4, 5}, {1, 2, 2, 3}}, + ranges::equal) ); + VERIFY( ranges::equal(v | views::join, x) ); + auto i = v.begin(); + auto j = i; + j++; + VERIFY( i == i && i != v.end() ); + VERIFY( j == j && j != v.end() ); + VERIFY( j != i ); + j--; + VERIFY( j == i ); + + return true; +} + +void +test02() +{ + int x[] = {1, 2, 3}; + __gnu_test::test_forward_range rx(x); + auto v = rx | views::chunk_by(ranges::equal_to{}); + static_assert(!ranges::bidirectional_range + && !ranges::common_range); + VERIFY( ranges::equal(v, x | views::transform(views::single), ranges::equal) ); + auto i = v.begin(); + VERIFY( i != v.end() ); + ranges::advance(i, 3); + VERIFY( i == v.end() ); +} + +int +main() +{ + static_assert(test01()); + test02(); +}