From cd916108b4c6fea5908deed6066d5d4720cf7659 Mon Sep 17 00:00:00 2001 From: Nikolas Klauser Date: Fri, 9 Jun 2023 13:45:34 -0700 Subject: [PATCH] [libc++][PSTL] Implement std::generate{,_n} Reviewed By: #libc, ldionne Spies: ldionne, libcxx-commits Differential Revision: https://reviews.llvm.org/D152581 --- libcxx/docs/Status/PSTLPaper.csv | 4 +- libcxx/include/CMakeLists.txt | 1 + libcxx/include/__algorithm/pstl_backend.h | 6 ++ libcxx/include/__algorithm/pstl_generate.h | 80 ++++++++++++++++++++++ libcxx/include/algorithm | 10 +++ ...ainst_customization_points_not_working.pass.cpp | 20 ++++++ .../alg.generate/pstl.generate.pass.cpp | 57 +++++++++++++++ .../alg.generate/pstl.generate_n.pass.cpp | 56 +++++++++++++++ 8 files changed, 232 insertions(+), 2 deletions(-) create mode 100644 libcxx/include/__algorithm/pstl_generate.h create mode 100644 libcxx/test/std/algorithms/alg.modifying.operations/alg.generate/pstl.generate.pass.cpp create mode 100644 libcxx/test/std/algorithms/alg.modifying.operations/alg.generate/pstl.generate_n.pass.cpp diff --git a/libcxx/docs/Status/PSTLPaper.csv b/libcxx/docs/Status/PSTLPaper.csv index 949a6f3..e70c44c 100644 --- a/libcxx/docs/Status/PSTLPaper.csv +++ b/libcxx/docs/Status/PSTLPaper.csv @@ -20,8 +20,8 @@ Section,Description,Assignee,Complete | `[alg.find] `_,std::find_if_not,Nikolas Klauser,|Complete| | `[alg.foreach] `_,std::for_each,Nikolas Klauser,|Complete| | `[alg.foreach] `_,std::for_each_n,Nikolas Klauser,|Complete| -| `[alg.generate] `_,std::generate,Nikolas Klauser,|In Progress| -| `[alg.generate] `_,std::generate_n,Nikolas Klauser,|In Progress| +| `[alg.generate] `_,std::generate,Nikolas Klauser,|Complete| +| `[alg.generate] `_,std::generate_n,Nikolas Klauser,|Complete| | `[alg.set.operations] `_,std::includes,Nikolas Klauser,|Not Started| | `[alg.inclusive.scan] `_,std::inclusive_scan,Nikolas Klauser,|Not Started| | `[alg.merge] `_,std::inplace_merge,Nikolas Klauser,|Not Started| diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt index 62e9449..7088a3e 100644 --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -90,6 +90,7 @@ set(files __algorithm/pstl_find.h __algorithm/pstl_for_each.h __algorithm/pstl_frontend_dispatch.h + __algorithm/pstl_generate.h __algorithm/pstl_merge.h __algorithm/pstl_replace.h __algorithm/pstl_stable_sort.h diff --git a/libcxx/include/__algorithm/pstl_backend.h b/libcxx/include/__algorithm/pstl_backend.h index 7b2edb6..55003a8 100644 --- a/libcxx/include/__algorithm/pstl_backend.h +++ b/libcxx/include/__algorithm/pstl_backend.h @@ -98,6 +98,12 @@ implemented, all the algorithms will eventually forward to the basis algorithms template void __pstl_fill_n(_Backend, _Iterator __first, _SizeT __n, const _Tp& __value); + template + void __pstl_generate(_Backend, _Iterator __first, _Iterator __last, _Generator __gen); + + template + void __pstl_generator_n(_Backend, _Iterator __first, _Size __n, _Generator __gen); + template _OutIterator __pstl_merge(_Backend, _Iterator1 __first1, diff --git a/libcxx/include/__algorithm/pstl_generate.h b/libcxx/include/__algorithm/pstl_generate.h new file mode 100644 index 0000000..4ad4105 --- /dev/null +++ b/libcxx/include/__algorithm/pstl_generate.h @@ -0,0 +1,80 @@ +//===----------------------------------------------------------------------===// +// +// 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___ALGORITHM_PSTL_GENERATE_H +#define _LIBCPP___ALGORITHM_PSTL_GENERATE_H + +#include <__algorithm/pstl_backend.h> +#include <__algorithm/pstl_for_each.h> +#include <__algorithm/pstl_frontend_dispatch.h> +#include <__config> +#include <__iterator/cpp17_iterator_concepts.h> +#include <__type_traits/is_execution_policy.h> +#include <__type_traits/remove_cvref.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17 + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +void __pstl_generate(); + +template , + enable_if_t, int> = 0> +_LIBCPP_HIDE_FROM_ABI void +generate(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Generator __gen) { + _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator); + std::__pstl_frontend_dispatch( + _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_generate), + [&__policy](_ForwardIterator __g_first, _ForwardIterator __g_last, _Generator __g_gen) { + std::for_each( + __policy, std::move(__g_first), std::move(__g_last), [&](__iter_reference<_ForwardIterator> __element) { + __element = __g_gen(); + }); + }, + std::move(__first), + std::move(__last), + std::move(__gen)); +} + +template +void __pstl_generate_n(); + +template , + enable_if_t, int> = 0> +_LIBCPP_HIDE_FROM_ABI void +generate_n(_ExecutionPolicy&& __policy, _ForwardIterator __first, _Size __n, _Generator __gen) { + _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator); + std::__pstl_frontend_dispatch( + _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_generate_n), + [&__policy](_ForwardIterator __g_first, _Size __g_n, _Generator __g_gen) { + std::for_each_n(__policy, std::move(__g_first), __g_n, [&](__iter_reference<_ForwardIterator> __element) { + __element = __g_gen(); + }); + }, + std::move(__first), + __n, + std::move(__gen)); +} + +_LIBCPP_END_NAMESPACE_STD + +#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17 + +#endif // _LIBCPP___ALGORITHM_PSTL_GENERATE_H diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm index 2ceedc9..fefa98a 100644 --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -401,6 +401,11 @@ namespace ranges { requires invocable && indirectly_writable> constexpr O generate(O first, S last, F gen); // since C++20 + template + void generate(ExecutionPolicy&& exec, + ForwardIterator first, ForwardIterator last, + Generator gen); // since C++17 + template requires invocable && output_range> constexpr borrowed_iterator_t generate(R&& r, F gen); // since C++20 @@ -409,6 +414,10 @@ namespace ranges { requires invocable && indirectly_writable> constexpr O generate_n(O first, iter_difference_t n, F gen); // since C++20 + template + ForwardIterator generate_n(ExecutionPolicy&& exec, + ForwardIterator first, Size n, Generator gen); // since C++17 + template S1, input_iterator I2, sentinel_for S2, class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> requires indirectly_comparable @@ -1806,6 +1815,7 @@ template #include <__algorithm/pstl_fill.h> #include <__algorithm/pstl_find.h> #include <__algorithm/pstl_for_each.h> +#include <__algorithm/pstl_generate.h> #include <__algorithm/pstl_merge.h> #include <__algorithm/pstl_replace.h> #include <__algorithm/pstl_stable_sort.h> diff --git a/libcxx/test/libcxx/algorithms/pstl.robust_against_customization_points_not_working.pass.cpp b/libcxx/test/libcxx/algorithms/pstl.robust_against_customization_points_not_working.pass.cpp index 4291521..914159d 100644 --- a/libcxx/test/libcxx/algorithms/pstl.robust_against_customization_points_not_working.pass.cpp +++ b/libcxx/test/libcxx/algorithms/pstl.robust_against_customization_points_not_working.pass.cpp @@ -62,6 +62,22 @@ __pstl_count_if(TestBackend, ForwardIterator, ForwardIterator, Pred) { return 0; } +bool pstl_generate_called = false; + +template +void __pstl_generate(TestBackend, ForwardIterator, ForwardIterator, Gen) { + assert(!pstl_generate_called); + pstl_generate_called = true; +} + +bool pstl_generate_n_called = false; + +template +void __pstl_generate_n(TestBackend, Size, ForwardIterator, Gen) { + assert(!pstl_generate_n_called); + pstl_generate_n_called = true; +} + bool pstl_none_of_called = false; template @@ -267,6 +283,10 @@ int main(int, char**) { assert(std::pstl_for_each_called); (void)std::for_each_n(TestPolicy{}, std::begin(a), std::size(a), pred); assert(std::pstl_for_each_n_called); + (void)std::generate(TestPolicy{}, std::begin(a), std::end(a), pred); + assert(std::pstl_generate_called); + (void)std::generate_n(TestPolicy{}, std::begin(a), std::size(a), pred); + assert(std::pstl_generate_n_called); (void)std::replace(TestPolicy{}, std::begin(a), std::end(a), 0, 0); assert(std::pstl_replace_called); (void)std::replace_if(TestPolicy{}, std::begin(a), std::end(a), pred, 0); diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.generate/pstl.generate.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.generate/pstl.generate.pass.cpp new file mode 100644 index 0000000..064b710 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.generate/pstl.generate.pass.cpp @@ -0,0 +1,57 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// UNSUPPORTED: libcpp-has-no-incomplete-pstl + +// template +// void generate(ExecutionPolicy&& exec, +// ForwardIterator first, ForwardIterator last, +// Generator gen); + +#include +#include +#include + +#include "test_iterators.h" +#include "test_execution_policies.h" +#include "type_algorithms.h" + +template +struct Test { + template + void operator()(ExecutionPolicy&& policy) { + { // simple test + int a[10]; + std::generate(policy, Iter(std::begin(a)), Iter(std::end(a)), []() { return 1; }); + assert(std::all_of(std::begin(a), std::end(a), [](int i) { return i == 1; })); + } + { // empty range works + int a[10] {3}; + std::generate(policy, Iter(std::begin(a)), Iter(std::begin(a)), []() { return 1; }); + assert(a[0] == 3); + } + { // single-element range works + int a[] {3}; + std::generate(policy, Iter(std::begin(a)), Iter(std::end(a)), []() { return 5; }); + assert(a[0] == 5); + } + { // large range works + std::vector vec(150, 4); + std::generate(policy, Iter(std::data(vec)), Iter(std::data(vec) + std::size(vec)), []() { return 5; }); + assert(std::all_of(std::begin(vec), std::end(vec), [](int i) { return i == 5; })); + } + } +}; + +int main(int, char**) { + types::for_each(types::forward_iterator_list{}, TestIteratorWithPolicies{}); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.generate/pstl.generate_n.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.generate/pstl.generate_n.pass.cpp new file mode 100644 index 0000000..9506044 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.generate/pstl.generate_n.pass.cpp @@ -0,0 +1,56 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// UNSUPPORTED: libcpp-has-no-incomplete-pstl + +// template +// ForwardIterator generate_n(ExecutionPolicy&& exec, +// ForwardIterator first, Size n, Generator gen); + +#include +#include +#include + +#include "test_iterators.h" +#include "test_execution_policies.h" +#include "type_algorithms.h" + +template +struct Test { + template + void operator()(ExecutionPolicy&& policy) { + { // simple test + int a[10]; + std::generate_n(policy, Iter(std::begin(a)), std::size(a), []() { return 1; }); + assert(std::all_of(std::begin(a), std::end(a), [](int i) { return i == 1; })); + } + { // empty range works + int a[10] {3}; + std::generate_n(policy, Iter(std::begin(a)), 0, []() { return 1; }); + assert(a[0] == 3); + } + { // single-element range works + int a[] {3}; + std::generate_n(policy, Iter(std::begin(a)), std::size(a), []() { return 5; }); + assert(a[0] == 5); + } + { // large range works + std::vector vec(150, 4); + std::generate_n(policy, Iter(std::data(vec)), std::size(vec), []() { return 5; }); + assert(std::all_of(std::begin(vec), std::end(vec), [](int i) { return i == 5; })); + } + } +}; + +int main(int, char**) { + types::for_each(types::forward_iterator_list{}, TestIteratorWithPolicies{}); + + return 0; +} -- 2.7.4