From: Jonathan Wakely <jwakely@redhat.com>
To: Patrick Palka <ppalka@redhat.com>
Cc: gcc-patches@gcc.gnu.org, libstdc++@gcc.gnu.org
Subject: Re: [PATCH] libstdc++: Implement ranges::stride_view from P1899R3
Date: Tue, 18 Oct 2022 12:59:32 +0100 [thread overview]
Message-ID: <CACb0b4mV1nrDM+sfX9PcXTEcij_YBpZqYcaz9xYdb-vzVw11KQ@mail.gmail.com> (raw)
In-Reply-To: <20221017200926.1230070-1-ppalka@redhat.com>
On Mon, 17 Oct 2022 at 21:09, Patrick Palka via Libstdc++
<libstdc++@gcc.gnu.org> 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<input_range _Vp>
> + requires view<_Vp>
> + class stride_view : public view_interface<stride_view<_Vp>>
> + {
> + _Vp _M_base;
> + range_difference_t<_Vp> _M_stride;
> +
> + template<bool _Const> using _Base = __detail::__maybe_const_t<_Const, _Vp>;
> +
> + template<bool _Const>
> + struct __iter_cat
> + { };
> +
> + template<bool _Const>
> + requires forward_range<_Base<_Const>>
> + struct __iter_cat<_Const>
> + {
> + private:
> + static auto
> + _S_iter_cat()
> + {
> + using _Cat = typename iterator_traits<iterator_t<_Base<_Const>>>::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<bool> 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<false>(this, ranges::begin(_M_base)); }
> +
> + constexpr auto
> + begin() const requires range<const _Vp>
> + { return _Iterator<true>(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<false>(this, ranges::end(_M_base), __missing);
> + }
> + else if constexpr (common_range<_Vp> && !bidirectional_range<_Vp>)
> + return _Iterator<false>(this, ranges::end(_M_base));
> + else
> + return default_sentinel;
> + }
> +
> + constexpr auto
> + end() const requires range<const _Vp>
> + {
> + if constexpr (common_range<const _Vp> && sized_range<const _Vp>
> + && forward_range<const _Vp>)
> + {
> + auto __missing = (_M_stride - ranges::distance(_M_base) % _M_stride) % _M_stride;
> + return _Iterator<true>(this, ranges::end(_M_base), __missing);
> + }
> + else if constexpr (common_range<const _Vp> && !bidirectional_range<const _Vp>)
> + return _Iterator<true>(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<const _Vp>
> + {
> + return __detail::__to_unsigned_like
> + (__detail::__div_ceil(ranges::distance(_M_base), _M_stride));
> + }
> + };
> +
> + template<typename _Range>
> + stride_view(_Range&&, range_difference_t<_Range>) -> stride_view<views::all_t<_Range>>;
> +
> + template<typename _Vp>
> + inline constexpr bool enable_borrowed_range<stride_view<_Vp>>
> + = enable_borrowed_range<_Vp>;
> +
> + template<input_range _Vp>
> + requires view<_Vp>
> + template<bool _Const>
> + 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<iterator_t<_Base>> = default;
> +
> + constexpr
> + _Iterator(_Iterator<!_Const> __other)
> + requires _Const
> + && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
> + && convertible_to<sentinel_t<_Vp>, 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<iterator_t<_Base>>
> + { 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<iterator_t<_Base>>
> + { 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>, 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<sentinel_t<_Base>, 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<sentinel_t<_Base>, 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<iterator_t<_Base>>
> + { ranges::iter_swap(__x._M_current, __y._M_current); }
> + };
> +
> + namespace views
> + {
> + namespace __detail
> + {
> + template<typename _Range, typename _Dp>
> + concept __can_stride_view
> + = requires { stride_view(std::declval<_Range>(), std::declval<_Dp>()); };
> + }
> +
> + struct _Stride : __adaptor::_RangeAdaptor<_Stride>
> + {
> + template<viewable_range _Range, typename _Dp = range_difference_t<_Range>>
> + 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 <ranges>
> +#include <algorithm>
> +#include <testsuite_hooks.h>
> +#include <testsuite_iterators.h>
> +
> +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<class container>
> +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<int>>();
> + test02<__gnu_test::test_forward_range<int>>();
> +}
> --
> 2.38.0.68.ge85701b4af
>
prev parent reply other threads:[~2022-10-18 11:59 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-10-17 20:09 Patrick Palka
2022-10-18 11:59 ` Jonathan Wakely [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CACb0b4mV1nrDM+sfX9PcXTEcij_YBpZqYcaz9xYdb-vzVw11KQ@mail.gmail.com \
--to=jwakely@redhat.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=libstdc++@gcc.gnu.org \
--cc=ppalka@redhat.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).