diff options
author | Nikolas Klauser <nikolasklauser@berlin.de> | 2022-11-21 12:41:15 +0100 |
---|---|---|
committer | Nikolas Klauser <nikolasklauser@berlin.de> | 2023-01-20 07:55:58 +0100 |
commit | 21f4232dd963c449231f03a90836071202fd134a (patch) | |
tree | 79d47ea1309337a4edc8f651aa37f57d72912e39 /libcxx | |
parent | dddcf3014aa094d3ecd0430511a5c10045fefbd6 (diff) | |
download | llvm-21f4232dd963c449231f03a90836071202fd134a.zip llvm-21f4232dd963c449231f03a90836071202fd134a.tar.gz llvm-21f4232dd963c449231f03a90836071202fd134a.tar.bz2 |
[libc++] Enable segmented iterator optimizations for join_view::iterator
Reviewed By: ldionne, #libc
Spies: libcxx-commits
Differential Revision: https://reviews.llvm.org/D138413
Diffstat (limited to 'libcxx')
-rw-r--r-- | libcxx/benchmarks/CMakeLists.txt | 1 | ||||
-rw-r--r-- | libcxx/benchmarks/join_view.bench.cpp | 77 | ||||
-rw-r--r-- | libcxx/docs/ReleaseNotes.rst | 3 | ||||
-rw-r--r-- | libcxx/include/CMakeLists.txt | 1 | ||||
-rw-r--r-- | libcxx/include/__iterator/iterator_with_data.h | 100 | ||||
-rw-r--r-- | libcxx/include/__ranges/join_view.h | 128 | ||||
-rw-r--r-- | libcxx/include/module.modulemap.in | 1 | ||||
-rw-r--r-- | libcxx/test/libcxx/iterators/iterator_with_data.pass.cpp | 39 | ||||
-rw-r--r-- | libcxx/test/libcxx/private_headers.verify.cpp | 1 | ||||
-rw-r--r-- | libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy.segmented.pass.cpp | 57 | ||||
-rw-r--r-- | libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_backward.pass.cpp | 64 |
11 files changed, 443 insertions, 29 deletions
diff --git a/libcxx/benchmarks/CMakeLists.txt b/libcxx/benchmarks/CMakeLists.txt index fbc5144..7eb76ac 100644 --- a/libcxx/benchmarks/CMakeLists.txt +++ b/libcxx/benchmarks/CMakeLists.txt @@ -185,6 +185,7 @@ set(BENCHMARK_TESTS formatter_float.bench.cpp formatter_int.bench.cpp function.bench.cpp + join_view.bench.cpp map.bench.cpp monotonic_buffer.bench.cpp ordered_set.bench.cpp diff --git a/libcxx/benchmarks/join_view.bench.cpp b/libcxx/benchmarks/join_view.bench.cpp new file mode 100644 index 0000000..c789a39 --- /dev/null +++ b/libcxx/benchmarks/join_view.bench.cpp @@ -0,0 +1,77 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include <algorithm> +#include <deque> +#include <ranges> + +#include "benchmark/benchmark.h" + +namespace { +void run_sizes(auto benchmark) { + benchmark->Arg(0) + ->Arg(1) + ->Arg(2) + ->Arg(64) + ->Arg(512) + ->Arg(1024) + ->Arg(4000) + ->Arg(4096) + ->Arg(5500) + ->Arg(64000) + ->Arg(65536) + ->Arg(70000); +} + +void BM_join_view_in_vectors(benchmark::State& state) { + auto size = state.range(0); + std::vector<std::vector<int>> input(size, std::vector<int>(32)); + std::ranges::fill(input | std::views::join, 10); + std::vector<int> output; + output.resize(size * 32); + + for (auto _ : state) { + benchmark::DoNotOptimize(input); + benchmark::DoNotOptimize(output); + std::ranges::copy(input | std::views::join, output.begin()); + } +} +BENCHMARK(BM_join_view_in_vectors)->Apply(run_sizes); + +void BM_join_view_out_vectors(benchmark::State& state) { + auto size = state.range(0); + std::vector<std::vector<int>> output(size, std::vector<int>(32)); + std::vector<int> input; + input.resize(size * 32); + std::ranges::fill(input, 10); + + for (auto _ : state) { + benchmark::DoNotOptimize(output); + benchmark::DoNotOptimize(input); + std::ranges::copy(input, (output | std::views::join).begin()); + } +} +BENCHMARK(BM_join_view_out_vectors)->Apply(run_sizes); + +void BM_join_view_deques(benchmark::State& state) { + auto size = state.range(0); + std::deque<std::deque<int>> deque(size, std::deque<int>(32)); + std::ranges::fill(deque | std::views::join, 10); + std::vector<int> output; + output.resize(size * 32); + + for (auto _ : state) { + benchmark::DoNotOptimize(deque); + benchmark::DoNotOptimize(output); + std::ranges::copy(deque | std::views::join, output.begin()); + } +} +BENCHMARK(BM_join_view_deques)->Apply(run_sizes); +} // namespace + +BENCHMARK_MAIN(); diff --git a/libcxx/docs/ReleaseNotes.rst b/libcxx/docs/ReleaseNotes.rst index 0d5e95e..c0e5542 100644 --- a/libcxx/docs/ReleaseNotes.rst +++ b/libcxx/docs/ReleaseNotes.rst @@ -79,6 +79,9 @@ Improvements and New Features - `D122780 <https://reviews.llvm.org/D122780>`_ Improved the performance of std::sort - The ``ranges`` versions of ``copy``, ``move``, ``copy_backward`` and ``move_backward`` are now also optimized for ``std::deque<>::iterator``, which can lead to up to 20x performance improvements on certain algorithms. +- The ``std`` and ``ranges`` versions of ``copy``, ``move``, ``copy_backward`` and ``move_backward`` are now also + optimized for ``join_view::iterator``, which can lead to up to 20x performance improvements on certain combinations of + iterators and algorithms. Deprecations and Removals ------------------------- diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt index 74d1f96..44e129a 100644 --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -392,6 +392,7 @@ set(files __iterator/iter_swap.h __iterator/iterator.h __iterator/iterator_traits.h + __iterator/iterator_with_data.h __iterator/mergeable.h __iterator/move_iterator.h __iterator/move_sentinel.h diff --git a/libcxx/include/__iterator/iterator_with_data.h b/libcxx/include/__iterator/iterator_with_data.h new file mode 100644 index 0000000..06c2fa6 --- /dev/null +++ b/libcxx/include/__iterator/iterator_with_data.h @@ -0,0 +1,100 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ITERATOR_ITERATOR_WITH_DATA_H +#define _LIBCPP___ITERATOR_ITERATOR_WITH_DATA_H + +#include <__compare/compare_three_way_result.h> +#include <__compare/three_way_comparable.h> +#include <__config> +#include <__iterator/concepts.h> +#include <__iterator/incrementable_traits.h> +#include <__iterator/iter_move.h> +#include <__iterator/iter_swap.h> +#include <__iterator/iterator_traits.h> +#include <__iterator/readable_traits.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER >= 20 + +_LIBCPP_BEGIN_NAMESPACE_STD + +template <forward_iterator _Iterator, class _Data> +class __iterator_with_data { + _Iterator __iter_{}; + _Data __data_{}; + +public: + using value_type = iter_value_t<_Iterator>; + using difference_type = iter_difference_t<_Iterator>; + + _LIBCPP_HIDE_FROM_ABI __iterator_with_data() = default; + + constexpr _LIBCPP_HIDE_FROM_ABI __iterator_with_data(_Iterator __iter, _Data __data) + : __iter_(std::move(__iter)), __data_(std::move(__data)) {} + + constexpr _LIBCPP_HIDE_FROM_ABI _Iterator __get_iter() const { return __iter_; } + + constexpr _LIBCPP_HIDE_FROM_ABI _Data __get_data() && { return std::move(__data_); } + + friend constexpr _LIBCPP_HIDE_FROM_ABI bool + operator==(const __iterator_with_data& __lhs, const __iterator_with_data& __rhs) { + return __lhs.__iter_ == __rhs.__iter_; + } + + constexpr _LIBCPP_HIDE_FROM_ABI __iterator_with_data& operator++() { + ++__iter_; + return *this; + } + + constexpr _LIBCPP_HIDE_FROM_ABI __iterator_with_data operator++(int) { + auto __tmp = *this; + __iter_++; + return __tmp; + } + + constexpr _LIBCPP_HIDE_FROM_ABI __iterator_with_data& operator--() + requires bidirectional_iterator<_Iterator> + { + --__iter_; + return *this; + } + + constexpr _LIBCPP_HIDE_FROM_ABI __iterator_with_data operator--(int) + requires bidirectional_iterator<_Iterator> + { + auto __tmp = *this; + --__iter_; + return __tmp; + } + + constexpr _LIBCPP_HIDE_FROM_ABI iter_reference_t<_Iterator> operator*() const { return *__iter_; } + + _LIBCPP_HIDE_FROM_ABI friend constexpr iter_rvalue_reference_t<_Iterator> + iter_move(const __iterator_with_data& __iter) noexcept(noexcept(ranges::iter_move(__iter.__iter_))) { + return ranges::iter_move(__iter.__iter_); + } + + _LIBCPP_HIDE_FROM_ABI friend constexpr void + iter_swap(const __iterator_with_data& __lhs, + const __iterator_with_data& __rhs) noexcept(noexcept(ranges::iter_swap(__lhs.__iter_, __rhs.__iter_))) + requires indirectly_swappable<_Iterator> + { + return ranges::iter_swap(__lhs.__data_, __rhs.__iter_); + } +}; + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER >= 20 + +#endif // _LIBCPP___ITERATOR_ITERATOR_WITH_DATA_H diff --git a/libcxx/include/__ranges/join_view.h b/libcxx/include/__ranges/join_view.h index 293926c..869540f 100644 --- a/libcxx/include/__ranges/join_view.h +++ b/libcxx/include/__ranges/join_view.h @@ -20,9 +20,12 @@ #include <__iterator/iter_move.h> #include <__iterator/iter_swap.h> #include <__iterator/iterator_traits.h> +#include <__iterator/iterator_with_data.h> +#include <__iterator/segmented_iterator.h> #include <__ranges/access.h> #include <__ranges/all.h> #include <__ranges/concepts.h> +#include <__ranges/empty.h> #include <__ranges/non_propagating_cache.h> #include <__ranges/range_adaptor.h> #include <__ranges/view_interface.h> @@ -63,6 +66,14 @@ namespace ranges { >; }; + template <input_range _View, bool _Const> + requires view<_View> && input_range<range_reference_t<_View>> + struct __join_view_iterator; + + template <input_range _View, bool _Const> + requires view<_View> && input_range<range_reference_t<_View>> + struct __join_view_sentinel; + template<input_range _View> requires view<_View> && input_range<range_reference_t<_View>> class join_view @@ -70,8 +81,22 @@ namespace ranges { private: using _InnerRange = range_reference_t<_View>; - template<bool> struct __iterator; - template<bool> struct __sentinel; + template<bool _Const> + using __iterator = __join_view_iterator<_View, _Const>; + + template<bool _Const> + using __sentinel = __join_view_sentinel<_View, _Const>; + + template <input_range _View2, bool _Const2> + requires view<_View2> && input_range<range_reference_t<_View2>> + friend struct __join_view_iterator; + + template <input_range _View2, bool _Const2> + requires view<_View2> && input_range<range_reference_t<_View2>> + friend struct __join_view_sentinel; + + template <class> + friend struct std::__segmented_iterator_traits; static constexpr bool _UseCache = !is_reference_v<_InnerRange>; using _Cache = _If<_UseCache, __non_propagating_cache<remove_cvref_t<_InnerRange>>, __empty_cache>; @@ -139,49 +164,57 @@ namespace ranges { } }; - template<input_range _View> + template<input_range _View, bool _Const> requires view<_View> && input_range<range_reference_t<_View>> - template<bool _Const> struct join_view<_View>::__sentinel { - template<bool> friend struct __sentinel; + struct __join_view_sentinel { + template<input_range _View2, bool> + requires view<_View2> && input_range<range_reference_t<_View2>> + friend struct __join_view_sentinel; private: - using _Parent = __maybe_const<_Const, join_view>; + using _Parent = __maybe_const<_Const, join_view<_View>>; using _Base = __maybe_const<_Const, _View>; sentinel_t<_Base> __end_ = sentinel_t<_Base>(); public: _LIBCPP_HIDE_FROM_ABI - __sentinel() = default; + __join_view_sentinel() = default; _LIBCPP_HIDE_FROM_ABI - constexpr explicit __sentinel(_Parent& __parent) + constexpr explicit __join_view_sentinel(_Parent& __parent) : __end_(ranges::end(__parent.__base_)) {} _LIBCPP_HIDE_FROM_ABI - constexpr __sentinel(__sentinel<!_Const> __s) + constexpr __join_view_sentinel(__join_view_sentinel<_View, !_Const> __s) requires _Const && convertible_to<sentinel_t<_View>, sentinel_t<_Base>> : __end_(std::move(__s.__end_)) {} template<bool _OtherConst> requires sentinel_for<sentinel_t<_Base>, iterator_t<__maybe_const<_OtherConst, _View>>> _LIBCPP_HIDE_FROM_ABI - friend constexpr bool operator==(const __iterator<_OtherConst>& __x, const __sentinel& __y) { + friend constexpr bool operator==(const __join_view_iterator<_View, _OtherConst>& __x, const __join_view_sentinel& __y) { return __x.__outer_ == __y.__end_; } }; - template<input_range _View> + template<input_range _View, bool _Const> requires view<_View> && input_range<range_reference_t<_View>> - template<bool _Const> struct join_view<_View>::__iterator + struct __join_view_iterator : public __join_view_iterator_category<__maybe_const<_Const, _View>> { - template<bool> friend struct __iterator; + template<input_range _View2, bool> + requires view<_View2> && input_range<range_reference_t<_View2>> + friend struct __join_view_iterator; + + template <class> + friend struct std::__segmented_iterator_traits; private: - using _Parent = __maybe_const<_Const, join_view>; + using _Parent = __maybe_const<_Const, join_view<_View>>; using _Base = __maybe_const<_Const, _View>; using _Outer = iterator_t<_Base>; using _Inner = iterator_t<range_reference_t<_Base>>; + using _InnerRange = range_reference_t<_View>; static constexpr bool __ref_is_glvalue = is_reference_v<range_reference_t<_Base>>; @@ -210,6 +243,9 @@ namespace ranges { __inner_.reset(); } + _LIBCPP_HIDE_FROM_ABI constexpr __join_view_iterator(_Parent* __parent, _Outer __outer, _Inner __inner) + : __outer_(std::move(__outer)), __inner_(std::move(__inner)), __parent_(__parent) {} + public: using iterator_concept = _If< __ref_is_glvalue && bidirectional_range<_Base> && bidirectional_range<range_reference_t<_Base>> && @@ -228,17 +264,17 @@ namespace ranges { range_difference_t<_Base>, range_difference_t<range_reference_t<_Base>>>; _LIBCPP_HIDE_FROM_ABI - __iterator() requires default_initializable<_Outer> = default; + __join_view_iterator() requires default_initializable<_Outer> = default; _LIBCPP_HIDE_FROM_ABI - constexpr __iterator(_Parent& __parent, _Outer __outer) + constexpr __join_view_iterator(_Parent& __parent, _Outer __outer) : __outer_(std::move(__outer)) , __parent_(std::addressof(__parent)) { __satisfy(); } _LIBCPP_HIDE_FROM_ABI - constexpr __iterator(__iterator<!_Const> __i) + constexpr __join_view_iterator(__join_view_iterator<_View, !_Const> __i) requires _Const && convertible_to<iterator_t<_View>, _Outer> && convertible_to<iterator_t<_InnerRange>, _Inner> @@ -259,7 +295,7 @@ namespace ranges { } _LIBCPP_HIDE_FROM_ABI - constexpr __iterator& operator++() { + constexpr __join_view_iterator& operator++() { auto&& __inner = [&]() -> auto&& { if constexpr (__ref_is_glvalue) return *__outer_; @@ -279,7 +315,7 @@ namespace ranges { } _LIBCPP_HIDE_FROM_ABI - constexpr __iterator operator++(int) + constexpr __join_view_iterator operator++(int) requires __ref_is_glvalue && forward_range<_Base> && forward_range<range_reference_t<_Base>> @@ -290,7 +326,7 @@ namespace ranges { } _LIBCPP_HIDE_FROM_ABI - constexpr __iterator& operator--() + constexpr __join_view_iterator& operator--() requires __ref_is_glvalue && bidirectional_range<_Base> && bidirectional_range<range_reference_t<_Base>> && @@ -309,7 +345,7 @@ namespace ranges { } _LIBCPP_HIDE_FROM_ABI - constexpr __iterator operator--(int) + constexpr __join_view_iterator operator--(int) requires __ref_is_glvalue && bidirectional_range<_Base> && bidirectional_range<range_reference_t<_Base>> && @@ -321,7 +357,7 @@ namespace ranges { } _LIBCPP_HIDE_FROM_ABI - friend constexpr bool operator==(const __iterator& __x, const __iterator& __y) + friend constexpr bool operator==(const __join_view_iterator& __x, const __join_view_iterator& __y) requires __ref_is_glvalue && equality_comparable<iterator_t<_Base>> && equality_comparable<iterator_t<range_reference_t<_Base>>> @@ -330,14 +366,14 @@ namespace ranges { } _LIBCPP_HIDE_FROM_ABI - friend constexpr decltype(auto) iter_move(const __iterator& __i) + friend constexpr decltype(auto) iter_move(const __join_view_iterator& __i) noexcept(noexcept(ranges::iter_move(*__i.__inner_))) { return ranges::iter_move(*__i.__inner_); } _LIBCPP_HIDE_FROM_ABI - friend constexpr void iter_swap(const __iterator& __x, const __iterator& __y) + friend constexpr void iter_swap(const __join_view_iterator& __x, const __join_view_iterator& __y) noexcept(noexcept(ranges::iter_swap(*__x.__inner_, *__y.__inner_))) requires indirectly_swappable<_Inner> { @@ -365,6 +401,50 @@ inline namespace __cpo { } // namespace views } // namespace ranges +template <class _View, bool _Const> + requires(ranges::common_range<typename ranges::__join_view_iterator<_View, _Const>::_Parent> && + __is_cpp17_random_access_iterator<typename ranges::__join_view_iterator<_View, _Const>::_Outer>::value && + __is_cpp17_random_access_iterator<typename ranges::__join_view_iterator<_View, _Const>::_Inner>::value) +struct __segmented_iterator_traits<ranges::__join_view_iterator<_View, _Const>> { + using _JoinViewIterator = ranges::__join_view_iterator<_View, _Const>; + + using __segment_iterator = + _LIBCPP_NODEBUG __iterator_with_data<typename _JoinViewIterator::_Outer, typename _JoinViewIterator::_Parent*>; + using __local_iterator = typename _JoinViewIterator::_Inner; + + // TODO: Would it make sense to enable the optimization for other iterator types? + + static constexpr _LIBCPP_HIDE_FROM_ABI __segment_iterator __segment(_JoinViewIterator __iter) { + if (ranges::empty(__iter.__parent_->__base_)) + return {}; + if (!__iter.__inner_.has_value()) + return __segment_iterator(--__iter.__outer_, __iter.__parent_); + return __segment_iterator(__iter.__outer_, __iter.__parent_); + } + + static constexpr _LIBCPP_HIDE_FROM_ABI __local_iterator __local(_JoinViewIterator __iter) { + if (ranges::empty(__iter.__parent_->__base_)) + return {}; + if (!__iter.__inner_.has_value()) + return ranges::end(*--__iter.__outer_); + return *__iter.__inner_; + } + + static constexpr _LIBCPP_HIDE_FROM_ABI __local_iterator __begin(__segment_iterator __iter) { + return ranges::begin(*__iter.__get_iter()); + } + + static constexpr _LIBCPP_HIDE_FROM_ABI __local_iterator __end(__segment_iterator __iter) { + return ranges::end(*__iter.__get_iter()); + } + + static constexpr _LIBCPP_HIDE_FROM_ABI _JoinViewIterator + __compose(__segment_iterator __seg_iter, __local_iterator __local_iter) { + return _JoinViewIterator( + std::move(__seg_iter).__get_data(), std::move(__seg_iter).__get_iter(), std::move(__local_iter)); + } +}; + #endif // _LIBCPP_STD_VER > 17 _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in index ffc8e27..ab9a213 100644 --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -996,6 +996,7 @@ module std [system] { module iter_swap { private header "__iterator/iter_swap.h" } module iterator { private header "__iterator/iterator.h" } module iterator_traits { private header "__iterator/iterator_traits.h" } + module iterator_with_data { private header "__iterator/iterator_with_data.h" } module mergeable { private header "__iterator/mergeable.h" export functional.__functional.ranges_operations diff --git a/libcxx/test/libcxx/iterators/iterator_with_data.pass.cpp b/libcxx/test/libcxx/iterators/iterator_with_data.pass.cpp new file mode 100644 index 0000000..a4c2b08 --- /dev/null +++ b/libcxx/test/libcxx/iterators/iterator_with_data.pass.cpp @@ -0,0 +1,39 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 + +#include "test_macros.h" + +TEST_DIAGNOSTIC_PUSH +TEST_CLANG_DIAGNOSTIC_IGNORED("-Wprivate-header") +#include <__iterator/iterator_with_data.h> +TEST_DIAGNOSTIC_POP + +#include "test_iterators.h" + +static_assert(std::forward_iterator<std::__iterator_with_data<forward_iterator<int*>, int>>); +static_assert(std::bidirectional_iterator<std::__iterator_with_data<bidirectional_iterator<int*>, int>>); +static_assert(std::bidirectional_iterator<std::__iterator_with_data<random_access_iterator<int*>, int>>); +static_assert(std::bidirectional_iterator<std::__iterator_with_data<contiguous_iterator<int*>, int>>); + +constexpr bool test() { + { + std::__iterator_with_data<forward_iterator<int*>, int> iter(forward_iterator<int*>(nullptr), 3); + assert(iter == iter); + assert(iter.__get_iter() == forward_iterator<int*>(nullptr)); + assert(std::move(iter).__get_data() == 3); + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); +} diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp index 86d93b6..d677053 100644 --- a/libcxx/test/libcxx/private_headers.verify.cpp +++ b/libcxx/test/libcxx/private_headers.verify.cpp @@ -423,6 +423,7 @@ END-SCRIPT #include <__iterator/iter_swap.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/iter_swap.h'}} #include <__iterator/iterator.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/iterator.h'}} #include <__iterator/iterator_traits.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/iterator_traits.h'}} +#include <__iterator/iterator_with_data.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/iterator_with_data.h'}} #include <__iterator/mergeable.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/mergeable.h'}} #include <__iterator/move_iterator.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/move_iterator.h'}} #include <__iterator/move_sentinel.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/move_sentinel.h'}} diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy.segmented.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy.segmented.pass.cpp index e8f8301..5b8d8b8 100644 --- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy.segmented.pass.cpp +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy.segmented.pass.cpp @@ -9,11 +9,16 @@ // UNSUPPORTED: c++03, c++11, c++14, c++17 #include <algorithm> +#include <array> #include <cassert> #include <concepts> #include <deque> +#include <ranges> #include <vector> +#include "test_iterators.h" +#include "type_algorithms.h" + template <class InContainer, class OutContainer> constexpr void test_containers() { using InIter = typename InContainer::iterator; @@ -39,6 +44,52 @@ constexpr void test_containers() { } } +template <class Iter, class Sent> +constexpr void test_join_view() { + auto to_subranges = std::views::transform([](auto& vec) { + return std::ranges::subrange(Iter(vec.data()), Sent(Iter(vec.data() + vec.size()))); + }); + + { // segmented -> contiguous + std::vector<std::vector<int>> vectors = {}; + auto range = vectors | to_subranges; + std::vector<std::ranges::subrange<Iter, Sent>> subrange_vector(range.begin(), range.end()); + std::array<int, 0> arr; + + std::ranges::copy(subrange_vector | std::views::join, arr.begin()); + assert(std::ranges::equal(arr, std::array<int, 0>{})); + } + { // segmented -> contiguous + std::vector<std::vector<int>> vectors = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10}, {}}; + auto range = vectors | to_subranges; + std::vector<std::ranges::subrange<Iter, Sent>> subrange_vector(range.begin(), range.end()); + std::array<int, 10> arr; + + std::ranges::copy(subrange_vector | std::views::join, arr.begin()); + assert(std::ranges::equal(arr, std::array{1, 2, 3, 4, 5, 6, 7, 8, 9, 10})); + } + { // contiguous -> segmented + std::vector<std::vector<int>> vectors = {{0, 0, 0, 0}, {0, 0}, {0, 0, 0, 0}, {}}; + auto range = vectors | to_subranges; + std::vector<std::ranges::subrange<Iter, Sent>> subrange_vector(range.begin(), range.end()); + std::array arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; + + std::ranges::copy(arr, (subrange_vector | std::views::join).begin()); + assert(std::ranges::equal(subrange_vector | std::views::join, std::array{1, 2, 3, 4, 5, 6, 7, 8, 9, 10})); + } + { // segmented -> segmented + std::vector<std::vector<int>> vectors = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10}, {}}; + auto range1 = vectors | to_subranges; + std::vector<std::ranges::subrange<Iter, Sent>> subrange_vector(range1.begin(), range1.end()); + std::vector<std::vector<int>> to_vectors = {{0, 0, 0, 0}, {0, 0, 0, 0}, {}, {0, 0}}; + auto range2 = to_vectors | to_subranges; + std::vector<std::ranges::subrange<Iter, Sent>> to_subrange_vector(range2.begin(), range2.end()); + + std::ranges::copy(subrange_vector | std::views::join, (to_subrange_vector | std::views::join).begin()); + assert(std::ranges::equal(to_subrange_vector | std::views::join, std::array{1, 2, 3, 4, 5, 6, 7, 8, 9, 10})); + } +} + int main(int, char**) { if (!std::is_constant_evaluated()) { test_containers<std::deque<int>, std::deque<int>>(); @@ -47,5 +98,11 @@ int main(int, char**) { test_containers<std::vector<int>, std::vector<int>>(); } + meta::for_each(meta::forward_iterator_list<int*>{}, []<class Iter> { + test_join_view<Iter, Iter>(); + test_join_view<Iter, sentinel_wrapper<Iter>>(); + test_join_view<Iter, sized_sentinel<Iter>>(); + }); + return 0; } diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_backward.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_backward.pass.cpp index 3762948..036dfe5 100644 --- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_backward.pass.cpp +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_backward.pass.cpp @@ -123,17 +123,69 @@ constexpr void test_containers() { } } +template <class Iter, class Sent> +constexpr void test_join_view() { + auto to_subranges = std::views::transform([](auto& vec) { + return std::ranges::subrange(Iter(vec.begin()), Sent(Iter(vec.end()))); + }); + + { // segmented -> contiguous + std::vector<std::vector<int>> vectors = {}; + auto range = vectors | to_subranges; + std::vector<std::ranges::subrange<Iter, Sent>> subrange_vector(range.begin(), range.end()); + std::array<int, 0> arr; + + std::ranges::copy_backward(subrange_vector | std::views::join, arr.end()); + assert(std::ranges::equal(arr, std::array<int, 0>{})); + } + { // segmented -> contiguous + std::vector<std::vector<int>> vectors = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10}, {}}; + auto range = vectors | to_subranges; + std::vector<std::ranges::subrange<Iter, Sent>> subrange_vector(range.begin(), range.end()); + std::array<int, 10> arr; + + std::ranges::copy_backward(subrange_vector | std::views::join, arr.end()); + assert(std::ranges::equal(arr, std::array{1, 2, 3, 4, 5, 6, 7, 8, 9, 10})); + } + { // contiguous -> segmented + std::vector<std::vector<int>> vectors = {{0, 0, 0, 0}, {0, 0}, {0, 0, 0, 0}, {}}; + auto range = vectors | to_subranges; + std::vector<std::ranges::subrange<Iter, Sent>> subrange_vector(range.begin(), range.end()); + std::array arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; + + std::ranges::copy_backward(arr, (subrange_vector | std::views::join).end()); + assert(std::ranges::equal(subrange_vector | std::views::join, std::array{1, 2, 3, 4, 5, 6, 7, 8, 9, 10})); + } + { // segmented -> segmented + std::vector<std::vector<int>> vectors = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10}, {}}; + auto range1 = vectors | to_subranges; + std::vector<std::ranges::subrange<Iter, Sent>> subrange_vector(range1.begin(), range1.end()); + std::vector<std::vector<int>> to_vectors = {{0, 0, 0, 0}, {0, 0, 0, 0}, {}, {0, 0}}; + auto range2 = to_vectors | to_subranges; + std::vector<std::ranges::subrange<Iter, Sent>> to_subrange_vector(range2.begin(), range2.end()); + + std::ranges::copy_backward(subrange_vector | std::views::join, (to_subrange_vector | std::views::join).end()); + assert(std::ranges::equal(to_subrange_vector | std::views::join, std::array{1, 2, 3, 4, 5, 6, 7, 8, 9, 10})); + } +} + +template <class> +constexpr bool is_proxy_iterator = false; + +template <class Iter> +constexpr bool is_proxy_iterator<ProxyIterator<Iter>> = true; + template <template <class> class InIter, template <class> class OutIter> constexpr void test_sentinels() { test_iterators<InIter<int*>, OutIter<int*>, InIter<int*>>(); test_iterators<InIter<int*>, OutIter<int*>, sentinel_wrapper<InIter<int*>>>(); test_iterators<InIter<int*>, OutIter<int*>, sized_sentinel<InIter<int*>>>(); - if (!std::is_constant_evaluated()) { - if constexpr (!std::is_same_v<InIter<int*>, contiguous_iterator<int*>> && - !std::is_same_v<OutIter<int*>, contiguous_iterator<int*>> && - !std::is_same_v<InIter<int*>, ContiguousProxyIterator<int*>> && - !std::is_same_v<OutIter<int*>, ContiguousProxyIterator<int*>>) { + if constexpr (!std::is_same_v<InIter<int*>, contiguous_iterator<int*>> && + !std::is_same_v<OutIter<int*>, contiguous_iterator<int*>> && + !std::is_same_v<InIter<int*>, ContiguousProxyIterator<int*>> && + !std::is_same_v<OutIter<int*>, ContiguousProxyIterator<int*>>) { + if (!std::is_constant_evaluated()) { test_containers<std::deque<int>, std::deque<int>, InIter<std::deque<int>::iterator>, @@ -151,6 +203,8 @@ constexpr void test_sentinels() { InIter<std::vector<int>::iterator>, OutIter<std::vector<int>::iterator>>(); } + if constexpr (!is_proxy_iterator<InIter<int*>>) + test_join_view<InIter<std::vector<int>::iterator>, InIter<std::vector<int>::iterator>>(); } } |