public inbox for libstdc++-cvs@sourceware.org
help / color / mirror / Atom feed
* [gcc r13-3361] libstdc++: Implement ranges::stride_view from P1899R3
@ 2022-10-18 14:52 Patrick Palka
0 siblings, 0 replies; only message in thread
From: Patrick Palka @ 2022-10-18 14:52 UTC (permalink / raw)
To: gcc-cvs, libstdc++-cvs
https://gcc.gnu.org/g:c70b44f2c1adf9a9b1c64105d07f177e86139fca
commit r13-3361-gc70b44f2c1adf9a9b1c64105d07f177e86139fca
Author: Patrick Palka <ppalka@redhat.com>
Date: Tue Oct 18 10:51:52 2022 -0400
libstdc++: Implement ranges::stride_view from P1899R3
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.
Diff:
---
libstdc++-v3/include/std/ranges | 351 +++++++++++++++++++++
.../testsuite/std/ranges/adaptors/stride/1.cc | 73 +++++
2 files changed, 424 insertions(+)
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>>();
+}
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2022-10-18 14:52 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-10-18 14:52 [gcc r13-3361] libstdc++: Implement ranges::stride_view from P1899R3 Patrick Palka
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).