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.133.124]) by sourceware.org (Postfix) with ESMTPS id 2FA3438582AD for ; Tue, 18 Oct 2022 11:59:47 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 2FA3438582AD 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=1666094386; 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=dioZ0vftg+ooteVJbIjXdnIob1BvW6oYfhh5/CslfZI=; b=UNkGy/+0NEwJ8et2qZ5TN8hgmPlBFLPIVGiVr1XKu1CPjh2yUC9J/iGFOOnhn3o27jniFa uEo34wu+pAhTKSQWbgIU/TVoM7me4oN5DKEJlxNHksu/1BIC2Xs1iw458HVEzFZARElIMJ bXZcdyOfQdukNgddW8+ZHRxAAJIpY+A= Received: from mail-qk1-f197.google.com (mail-qk1-f197.google.com [209.85.222.197]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-100-XC4Yn2fVOyaC6g55CN_87A-1; Tue, 18 Oct 2022 07:59:43 -0400 X-MC-Unique: XC4Yn2fVOyaC6g55CN_87A-1 Received: by mail-qk1-f197.google.com with SMTP id o13-20020a05620a2a0d00b006cf9085682dso11978975qkp.7 for ; Tue, 18 Oct 2022 04:59:43 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=dioZ0vftg+ooteVJbIjXdnIob1BvW6oYfhh5/CslfZI=; b=GGmHAsSN73fayEcwQR2/n8aoYvVV+evuK69ZZi5u+dt3+KYYrcmd8OrsciiVxfW8Q+ QOBclUw1TYfDNRMLL2o0xR7DQa6YkfgkIu1cqLFbKhCYd1F/R8ds74Cauqv96bKHVjvk tt1AWWcKQ+z/+/X93VPqQVjPOsBTH+fVrWVy9JDDCN/f9En42Om1vlq2PaVgkCfeqHac f2pXTTHYDUI4IrbbXZRjXwewVEfalOFH/1E9Jai2Uo2/kMB/vuuSigKLy6PLCrtD15Wi zZwtZOz4vn7JSxcxGFW/h0cdVt7Ld4mshV6iDYM4DvT6g+BxZ5fTzX8Y3EZwLLPDyW7K tKnw== X-Gm-Message-State: ACrzQf355A9/Ek1hqQtGxn9FLO8+K0AFNbs5vu6CFYZUhppd3+NG4aPA PIAa/9UB7ieRUOopoOZWFOokChdd8x9l6gi9Kb8ynlHbZePcjqGNWqakosxocSudoz6mtxTrtym K7rIAnqNNKTSh+ORj3ZPIP3ImCiWgTts= X-Received: by 2002:a37:4454:0:b0:6e7:9bd0:bf53 with SMTP id r81-20020a374454000000b006e79bd0bf53mr1499553qka.616.1666094383480; Tue, 18 Oct 2022 04:59:43 -0700 (PDT) X-Google-Smtp-Source: AMsMyM4wKom2bmmG09+vykqQiSarwS+M+nd4sQTNXbxKCvTPMTHf0MbXQksybolRCj92YLN+G16RkMyW8XqPS5t+DnY= X-Received: by 2002:a37:4454:0:b0:6e7:9bd0:bf53 with SMTP id r81-20020a374454000000b006e79bd0bf53mr1499539qka.616.1666094383180; Tue, 18 Oct 2022 04:59:43 -0700 (PDT) MIME-Version: 1.0 References: <20221017200926.1230070-1-ppalka@redhat.com> In-Reply-To: <20221017200926.1230070-1-ppalka@redhat.com> From: Jonathan Wakely Date: Tue, 18 Oct 2022 12:59:32 +0100 Message-ID: Subject: Re: [PATCH] libstdc++: Implement ranges::stride_view from P1899R3 To: Patrick Palka Cc: gcc-patches@gcc.gnu.org, libstdc++@gcc.gnu.org X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-12.4 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 List-Id: On Mon, 17 Oct 2022 at 21:09, Patrick Palka via Libstdc++ wrote: > > Tested on x86_64-pc-linux-gnu, does this look OK for trunk? OK, thanks. > > libstdc++-v3/ChangeLog: > > * include/std/ranges (stride_view): Define. > (stride_view::_Iterator): Define. > (views::__detail::__can_stride_view): Define. > (views::_Stride, views::stride): Define. > * testsuite/std/ranges/adaptors/stride/1.cc: New test. > --- > libstdc++-v3/include/std/ranges | 351 ++++++++++++++++++ > .../testsuite/std/ranges/adaptors/stride/1.cc | 73 ++++ > 2 files changed, 424 insertions(+) > create mode 100644 libstdc++-v3/testsuite/std/ranges/adaptors/stride/1.cc > > diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges > index 5857d426a66..d113cf19dc7 100644 > --- a/libstdc++-v3/include/std/ranges > +++ b/libstdc++-v3/include/std/ranges > @@ -7566,6 +7566,357 @@ namespace views::__adaptor > > inline constexpr _Repeat repeat; > } > + > + template > + requires view<_Vp> > + class stride_view : public view_interface> > + { > + _Vp _M_base; > + range_difference_t<_Vp> _M_stride; > + > + template using _Base = __detail::__maybe_const_t<_Const, _Vp>; > + > + template > + struct __iter_cat > + { }; > + > + template > + requires forward_range<_Base<_Const>> > + struct __iter_cat<_Const> > + { > + private: > + static auto > + _S_iter_cat() > + { > + using _Cat = typename iterator_traits>>::iterator_category; > + if constexpr (derived_from<_Cat, random_access_iterator_tag>) > + return random_access_iterator_tag{}; > + else > + return _Cat{}; > + } > + public: > + using iterator_category = decltype(_S_iter_cat()); > + }; > + > + template class _Iterator; > + > + public: > + constexpr explicit > + stride_view(_Vp __base, range_difference_t<_Vp> __stride) > + : _M_base(std::move(__base)), _M_stride(__stride) > + { __glibcxx_assert(__stride > 0); } > + > + constexpr _Vp > + base() const& requires copy_constructible<_Vp> > + { return _M_base; } > + > + constexpr _Vp > + base() && > + { return std::move(_M_base); } > + > + constexpr range_difference_t<_Vp> > + stride() const noexcept > + { return _M_stride; } > + > + constexpr auto > + begin() requires (!__detail::__simple_view<_Vp>) > + { return _Iterator(this, ranges::begin(_M_base)); } > + > + constexpr auto > + begin() const requires range > + { return _Iterator(this, ranges::begin(_M_base)); } > + > + constexpr auto > + end() requires (!__detail::__simple_view<_Vp>) > + { > + if constexpr (common_range<_Vp> && sized_range<_Vp> && forward_range<_Vp>) > + { > + auto __missing = (_M_stride - ranges::distance(_M_base) % _M_stride) % _M_stride; > + return _Iterator(this, ranges::end(_M_base), __missing); > + } > + else if constexpr (common_range<_Vp> && !bidirectional_range<_Vp>) > + return _Iterator(this, ranges::end(_M_base)); > + else > + return default_sentinel; > + } > + > + constexpr auto > + end() const requires range > + { > + if constexpr (common_range && sized_range > + && forward_range) > + { > + auto __missing = (_M_stride - ranges::distance(_M_base) % _M_stride) % _M_stride; > + return _Iterator(this, ranges::end(_M_base), __missing); > + } > + else if constexpr (common_range && !bidirectional_range) > + return _Iterator(this, ranges::end(_M_base)); > + else > + return default_sentinel; > + } > + > + constexpr auto > + size() requires sized_range<_Vp> > + { > + return __detail::__to_unsigned_like > + (__detail::__div_ceil(ranges::distance(_M_base), _M_stride)); > + } > + > + constexpr auto > + size() const requires sized_range > + { > + return __detail::__to_unsigned_like > + (__detail::__div_ceil(ranges::distance(_M_base), _M_stride)); > + } > + }; > + > + template > + stride_view(_Range&&, range_difference_t<_Range>) -> stride_view>; > + > + template > + inline constexpr bool enable_borrowed_range> > + = enable_borrowed_range<_Vp>; > + > + template > + requires view<_Vp> > + template > + class stride_view<_Vp>::_Iterator : public __iter_cat<_Const> > + { > + using _Parent = __detail::__maybe_const_t<_Const, stride_view>; > + using _Base = stride_view::_Base<_Const>; > + > + iterator_t<_Base> _M_current = iterator_t<_Base>(); > + sentinel_t<_Base> _M_end = sentinel_t<_Base>(); > + range_difference_t<_Base> _M_stride = 0; > + range_difference_t<_Base> _M_missing = 0; > + > + constexpr > + _Iterator(_Parent* __parent, iterator_t<_Base> __current, > + range_difference_t<_Base> __missing = 0) > + : _M_current(std::move(__current)), _M_end(ranges::end(__parent->_M_base)), > + _M_stride(__parent->_M_stride), _M_missing(__missing) > + { } > + > + static auto > + _S_iter_concept() > + { > + if constexpr (random_access_range<_Base>) > + return random_access_iterator_tag{}; > + else if constexpr (bidirectional_range<_Base>) > + return bidirectional_iterator_tag{}; > + else if constexpr (forward_range<_Base>) > + return forward_iterator_tag{}; > + else > + return input_iterator_tag{}; > + } > + > + friend stride_view; > + > + public: > + using difference_type = range_difference_t<_Base>; > + using value_type = range_value_t<_Base>; > + using iterator_concept = decltype(_S_iter_concept()); > + // iterator_category defined in stride_view::__iter_cat > + > + _Iterator() requires default_initializable> = default; > + > + constexpr > + _Iterator(_Iterator __other) > + requires _Const > + && convertible_to, iterator_t<_Base>> > + && convertible_to, sentinel_t<_Base>> > + : _M_current(std::move(__other._M_current)), _M_end(std::move(__other._M_end)), > + _M_stride(__other._M_stride), _M_missing(__other._M_missing) > + { } > + > + constexpr iterator_t<_Base> > + base() && > + { return std::move(_M_current); } > + > + constexpr const iterator_t<_Base>& > + base() const & noexcept > + { return _M_current; } > + > + constexpr decltype(auto) > + operator*() const > + { return *_M_current; } > + > + constexpr _Iterator& > + operator++() > + { > + __glibcxx_assert(_M_current != _M_end); > + _M_missing = ranges::advance(_M_current, _M_stride, _M_end); > + return *this; > + } > + > + constexpr void > + operator++(int) > + { ++*this; } > + > + constexpr _Iterator > + operator++(int) requires forward_range<_Base> > + { > + auto __tmp = *this; > + ++*this; > + return __tmp; > + } > + > + constexpr _Iterator& > + operator--() requires bidirectional_range<_Base> > + { > + ranges::advance(_M_current, _M_missing - _M_stride); > + _M_missing = 0; > + return *this; > + } > + > + constexpr _Iterator > + operator--(int) requires bidirectional_range<_Base> > + { > + auto __tmp = *this; > + --*this; > + return __tmp; > + } > + > + constexpr _Iterator& > + operator+=(difference_type __n) requires random_access_range<_Base> > + { > + if (__n > 0) > + { > + __glibcxx_assert(ranges::distance(_M_current, _M_end) > _M_stride * (__n - 1)); > + _M_missing = ranges::advance(_M_current, _M_stride * __n, _M_end); > + } > + else if (__n < 0) > + { > + ranges::advance(_M_current, _M_stride * __n + _M_missing); > + _M_missing = 0; > + } > + return *this; > + } > + > + constexpr _Iterator& > + operator-=(difference_type __n) requires random_access_range<_Base> > + { return *this += -__n; } > + > + constexpr decltype(auto) operator[](difference_type __n) const > + requires random_access_range<_Base> > + { return *(*this + __n); } > + > + friend constexpr bool > + operator==(const _Iterator& __x, default_sentinel_t) > + { return __x._M_current == __x._M_end; } > + > + friend constexpr bool > + operator==(const _Iterator& __x, const _Iterator& __y) > + requires equality_comparable> > + { return __x._M_current == __y._M_current; } > + > + friend constexpr bool > + operator<(const _Iterator& __x, const _Iterator& __y) > + requires random_access_range<_Base> > + { return __x._M_current < __y._M_current; } > + > + friend constexpr bool > + operator>(const _Iterator& __x, const _Iterator& __y) > + requires random_access_range<_Base> > + { return __y._M_current < __x._M_current; } > + > + friend constexpr bool > + operator<=(const _Iterator& __x, const _Iterator& __y) > + requires random_access_range<_Base> > + { return !(__y._M_current < __x._M_current); } > + > + friend constexpr bool > + operator>=(const _Iterator& __x, const _Iterator& __y) > + requires random_access_range<_Base> > + { return !(__x._M_current < __y._M_current); } > + > + friend constexpr auto > + operator<=>(const _Iterator& __x, const _Iterator& __y) > + requires random_access_range<_Base> && three_way_comparable> > + { return __x._M_current <=> __y._M_current; } > + > + friend constexpr _Iterator > + operator+(const _Iterator& __i, difference_type __n) > + requires random_access_range<_Base> > + { > + auto __r = __i; > + __r += __n; > + return __r; > + } > + > + friend constexpr _Iterator > + operator+(difference_type __n, const _Iterator& __i) > + requires random_access_range<_Base> > + { return __i + __n; } > + > + friend constexpr _Iterator > + operator-(const _Iterator& __i, difference_type __n) > + requires random_access_range<_Base> > + { > + auto __r = __i; > + __r -= __n; > + return __r; > + } > + > + friend constexpr difference_type > + operator-(const _Iterator& __x, const _Iterator& __y) > + requires sized_sentinel_for, iterator_t<_Base>> > + { > + auto __n = __x._M_current - __y._M_current; > + if constexpr (forward_range<_Base>) > + return (__n + __x._M_missing - __y._M_missing) / __x._M_stride; > + else if (__n < 0) > + return -__detail::__div_ceil(-__n, __x._M_stride); > + else > + return __detail::__div_ceil(__n, __x._M_stride); > + } > + > + friend constexpr difference_type > + operator-(default_sentinel_t __y, const _Iterator& __x) > + requires sized_sentinel_for, iterator_t<_Base>> > + { return __detail::__div_ceil(__x._M_end, __x._M_current, __x._M_stride); } > + > + friend constexpr difference_type > + operator-(const _Iterator& __x, default_sentinel_t __y) > + requires sized_sentinel_for, iterator_t<_Base>> > + { return -(__y - __x); } > + > + friend constexpr range_rvalue_reference_t<_Base> > + iter_move(const _Iterator& __i) > + noexcept(noexcept(ranges::iter_move(__i._M_current))) > + { return ranges::iter_move(__i._M_current); } > + > + friend constexpr void > + iter_swap(const _Iterator& __x, const _Iterator& __y) > + noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current))) > + requires indirectly_swappable> > + { ranges::iter_swap(__x._M_current, __y._M_current); } > + }; > + > + namespace views > + { > + namespace __detail > + { > + template > + concept __can_stride_view > + = requires { stride_view(std::declval<_Range>(), std::declval<_Dp>()); }; > + } > + > + struct _Stride : __adaptor::_RangeAdaptor<_Stride> > + { > + template> > + requires __detail::__can_stride_view<_Range, _Dp> > + constexpr auto > + operator() [[nodiscard]] (_Range&& __r, type_identity_t<_Dp> __n) const > + { return stride_view(std::forward<_Range>(__r), __n); } > + > + using __adaptor::_RangeAdaptor<_Stride>::operator(); > + static constexpr int _S_arity = 2; > + static constexpr bool _S_has_simple_extra_args = true; > + }; > + > + inline constexpr _Stride stride; > + } > #endif // C++23 > } // namespace ranges > > diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/stride/1.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/stride/1.cc > new file mode 100644 > index 00000000000..745d1a61c1b > --- /dev/null > +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/stride/1.cc > @@ -0,0 +1,73 @@ > +// { dg-options "-std=gnu++23" } > +// { dg-do run { target c++23 } } > + > +#include > +#include > +#include > +#include > + > +namespace ranges = std::ranges; > +namespace views = std::views; > + > +constexpr bool > +test01() > +{ > + int x[] = {1, 2, 3, 4, 5, 6, 7}; > + > + auto v2 = x | views::stride(2); > + const auto i0 = v2.begin(), i1 = v2.begin() + 1; > + VERIFY( i0 + 1 - 1 == i0 ); > + VERIFY( i0 != i1 ); > + VERIFY( i0 < i1 ); > + VERIFY( i0 <= i0 ); > + VERIFY( i0 >= i0 ); > + VERIFY( v2.end() > i1 ); > + VERIFY( i1 - i0 == 1 ); > + VERIFY( i0 - i1 == -1 ); > + VERIFY( v2.end() - i1 == 3 ); > + VERIFY( i1 - v2.end() == -3 ); > + auto i2 = v2.begin(); > + i2 += 2; > + i2 -= -2; > + VERIFY( i2 == v2.end() ); > + VERIFY( ranges::size(v2) == 4 ); > + VERIFY( ranges::equal(v2, (int[]){1, 3, 5, 7}) ); > + VERIFY( ranges::equal(v2 | views::reverse, (int[]){7, 5, 3, 1}) ); > + VERIFY( v2.stride() == 2 ); > + > + auto v1 = x | views::stride(1); > + VERIFY( ranges::size(v1) == ranges::size(x) ); > + VERIFY( ranges::equal(v1, x) ); > + VERIFY( ranges::equal(v1 | views::reverse, x | views::reverse) ); > + VERIFY( v1.stride() == 1 ); > + > + auto v5 = x | views::stride(5); > + VERIFY( ranges::equal(v5, (int[]){1, 6}) ); > + VERIFY( ranges::equal(v5 | views::reverse, (int[]){6, 1}) ); > + VERIFY( v5.stride() == 5 ); > + > + auto v10 = x | views::stride(10); > + VERIFY( ranges::equal(v10, (int[]){1}) ); > + VERIFY( ranges::equal(v10 | views::reverse, (int[]){1}) ); > + VERIFY( v10.stride() == 10 ); > + > + return true; > +} > + > +template > +void > +test02() > +{ > + int x[] = {1, 2, 3, 4, 5, 6, 7, 8}; > + container rx(x); > + auto v = rx | views::stride(3); > + VERIFY( ranges::equal(v, (int[]){1, 4, 7}) ); > +} > + > +int > +main() > +{ > + static_assert(test01()); > + test02<__gnu_test::test_input_range>(); > + test02<__gnu_test::test_forward_range>(); > +} > -- > 2.38.0.68.ge85701b4af >