diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -70,6 +70,7 @@ __algorithm/pop_heap.h __algorithm/prev_permutation.h __algorithm/pstl_any_all_none_of.h + __algorithm/pstl_fill.h __algorithm/pstl_for_each.h __algorithm/push_heap.h __algorithm/ranges_adjacent_find.h diff --git a/libcxx/include/__algorithm/pstl_fill.h b/libcxx/include/__algorithm/pstl_fill.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/pstl_fill.h @@ -0,0 +1,71 @@ +//===----------------------------------------------------------------------===// +// +// 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_FILL_H +#define _LIBCPP___ALGORITHM_PSTL_FILL_H + +#include <__algorithm/fill.h> +#include <__config> +#include <__iterator/iterator_traits.h> +#include <__pstl/internal/parallel_impl.h> +#include <__pstl/internal/unseq_backend_simd.h> +#include <__type_traits/is_execution_policy.h> +#include <__utility/terminate_on_exception.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER >= 17 + +_LIBCPP_BEGIN_NAMESPACE_STD + +template >, int> = 0> +_LIBCPP_HIDE_FROM_ABI void +fill(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) { + if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> && + __is_cpp17_random_access_iterator<_ForwardIterator>::value) { + std::__terminate_on_exception([&] { + __pstl::__par_backend::__parallel_for( + __pstl::__internal::__par_backend_tag{}, + __policy, + __first, + __last, + [&__policy, &__value](_ForwardIterator __brick_first, _ForwardIterator __brick_last) { + std::fill(std::__remove_parallel_policy(__policy), __brick_first, __brick_last, __value); + }); + }); + } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> && + __is_cpp17_random_access_iterator<_ForwardIterator>::value) { + __pstl::__unseq_backend::__simd_fill_n(__first, __last - __first, __value); + } else { + std::fill(__first, __last, __value); + } +} + +template >, int> = 0> +_LIBCPP_HIDE_FROM_ABI void +fill_n(_ExecutionPolicy&& __policy, _ForwardIterator __first, _SizeT __n, const _Tp& __value) { + if constexpr (__is_cpp17_random_access_iterator<_ForwardIterator>::value) + std::fill(__policy, __first, __first + __n, __value); + else + std::fill_n(__first, __n, __value); +} + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER >= 17 + +#endif // _LIBCPP___ALGORITHM_PSTL_FILL_H diff --git a/libcxx/include/__pstl/internal/algorithm_impl.h b/libcxx/include/__pstl/internal/algorithm_impl.h --- a/libcxx/include/__pstl/internal/algorithm_impl.h +++ b/libcxx/include/__pstl/internal/algorithm_impl.h @@ -2787,84 +2787,6 @@ } while (__x != __nth); } -//------------------------------------------------------------------------ -// fill, fill_n -//------------------------------------------------------------------------ -template -void __brick_fill(_RandomAccessIterator __first, - _RandomAccessIterator __last, - const _Tp& __value, - /* __is_vector = */ std::true_type) noexcept { - __unseq_backend::__simd_fill_n(__first, __last - __first, __value); -} - -template -void __brick_fill(_ForwardIterator __first, - _ForwardIterator __last, - const _Tp& __value, - /* __is_vector = */ std::false_type) noexcept { - std::fill(__first, __last, __value); -} - -template -void __pattern_fill( - _Tag, _ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) noexcept { - __internal::__brick_fill(__first, __last, __value, typename _Tag::__is_vector{}); -} - -template -_RandomAccessIterator __pattern_fill( - __parallel_tag<_IsVector> __tag, - _ExecutionPolicy&& __exec, - _RandomAccessIterator __first, - _RandomAccessIterator __last, - const _Tp& __value) { - using __backend_tag = typename decltype(__tag)::__backend_tag; - - return __internal::__except_handler([&__exec, __first, __last, &__value]() { - __par_backend::__parallel_for( - __backend_tag{}, - std::forward<_ExecutionPolicy>(__exec), - __first, - __last, - [&__value](_RandomAccessIterator __begin, _RandomAccessIterator __end) { - __internal::__brick_fill(__begin, __end, __value, _IsVector{}); - }); - return __last; - }); -} - -template -_RandomAccessIterator -__brick_fill_n(_RandomAccessIterator __first, - _Size __count, - const _Tp& __value, - /* __is_vector = */ std::true_type) noexcept { - return __unseq_backend::__simd_fill_n(__first, __count, __value); -} - -template -_OutputIterator __brick_fill_n( - _OutputIterator __first, _Size __count, const _Tp& __value, /* __is_vector = */ std::false_type) noexcept { - return std::fill_n(__first, __count, __value); -} - -template -_OutputIterator -__pattern_fill_n(_Tag, _ExecutionPolicy&&, _OutputIterator __first, _Size __count, const _Tp& __value) noexcept { - return __internal::__brick_fill_n(__first, __count, __value, typename _Tag::__is_vector{}); -} - -template -_RandomAccessIterator __pattern_fill_n( - __parallel_tag<_IsVector> __tag, - _ExecutionPolicy&& __exec, - _RandomAccessIterator __first, - _Size __count, - const _Tp& __value) { - return __internal::__pattern_fill(__tag, std::forward<_ExecutionPolicy>(__exec), __first, __first + __count, __value); -} - //------------------------------------------------------------------------ // generate, generate_n //------------------------------------------------------------------------ diff --git a/libcxx/include/__pstl/internal/glue_algorithm_defs.h b/libcxx/include/__pstl/internal/glue_algorithm_defs.h --- a/libcxx/include/__pstl/internal/glue_algorithm_defs.h +++ b/libcxx/include/__pstl/internal/glue_algorithm_defs.h @@ -209,16 +209,6 @@ const _Tp& __old_value, const _Tp& __new_value); -// [alg.fill] - -template -__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void> -fill(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value); - -template -__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator> -fill_n(_ExecutionPolicy&& __exec, _ForwardIterator __first, _Size __count, const _Tp& __value); - // [alg.generate] template __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void> diff --git a/libcxx/include/__pstl/internal/glue_algorithm_impl.h b/libcxx/include/__pstl/internal/glue_algorithm_impl.h --- a/libcxx/include/__pstl/internal/glue_algorithm_impl.h +++ b/libcxx/include/__pstl/internal/glue_algorithm_impl.h @@ -406,28 +406,6 @@ __new_value); } -// [alg.fill] - -template -__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void> -fill(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) { - auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first); - - __pstl::__internal::__pattern_fill(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first, __last, __value); -} - -template -__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator> -fill_n(_ExecutionPolicy&& __exec, _ForwardIterator __first, _Size __count, const _Tp& __value) { - if (__count <= 0) - return __first; - - auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first); - - return __pstl::__internal::__pattern_fill_n( - __dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first, __count, __value); -} - // [alg.generate] template __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void> diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -1910,6 +1910,7 @@ #ifdef _LIBCPP_HAS_PARALLEL_ALGORITHMS # include <__algorithm/pstl_any_all_none_of.h> +# include <__algorithm/pstl_fill.h> # include <__algorithm/pstl_for_each.h> #endif diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/pstl.fill.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/pstl.fill.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/pstl.fill.pass.cpp @@ -0,0 +1,82 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// REQUIRES: with-pstl + +// template +// void fill(ExecutionPolicy&& exec, +// ForwardIterator first, ForwardIterator last, const T& value); + +#include +#include +#include + +#include "test_macros.h" +#include "test_execution_policies.h" +#include "test_iterators.h" + +EXECUTION_POLICY_SFINAE_TEST(fill); + +static_assert(sfinae_test_fill); +static_assert(!sfinae_test_fill); + +template +struct Test { + template + void operator()(Policy&& policy) { + { // simple test + int a[4]; + std::fill(policy, Iter(std::begin(a)), Iter(std::end(a)), 33); + assert(std::all_of(std::begin(a), std::end(a), [](int i) { return i == 33; })); + } + { // check than an empty range works + int a[1] = {2}; + std::fill(policy, Iter(std::begin(a)), Iter(std::begin(a)), 33); + assert(a[0] == 2); + } + { // check than a one-element range works + int a[1]; + std::fill(policy, Iter(std::begin(a)), Iter(std::end(a)), 33); + assert(std::all_of(std::begin(a), std::end(a), [](int i) { return i == 33; })); + } + { // check than a two-element range works + int a[2]; + std::fill(policy, Iter(std::begin(a)), Iter(std::end(a)), 33); + assert(std::all_of(std::begin(a), std::end(a), [](int i) { return i == 33; })); + } + { // check than a large range works + std::vector a(234, 2); + std::fill(policy, Iter(std::data(a)), Iter(std::data(a) + std::size(a)), 33); + assert(std::all_of(std::begin(a), std::end(a), [](int i) { return i == 33; })); + } + } +}; + +struct ThrowOnCopy { + ThrowOnCopy& operator=(const ThrowOnCopy&) { throw int{}; } +}; + +int main(int, char**) { + types::for_each(types::forward_iterator_list{}, TestIteratorWithPolicies{}); + +#ifndef TEST_HAS_NO_EXCEPTIONS + std::set_terminate(terminate_successful); + ThrowOnCopy a[2]; + try { + (void)std::fill(std::execution::par, std::begin(a), std::end(a), ThrowOnCopy{}); + } catch (int) { + assert(false); + } +#endif + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/pstl.fill_n.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/pstl.fill_n.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/pstl.fill_n.pass.cpp @@ -0,0 +1,82 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// REQUIRES: with-pstl + +// template +// void fill(ExecutionPolicy&& exec, +// ForwardIterator first, ForwardIterator last, const T& value); + +#include +#include +#include + +#include "test_macros.h" +#include "test_execution_policies.h" +#include "test_iterators.h" + +EXECUTION_POLICY_SFINAE_TEST(fill_n); + +static_assert(sfinae_test_fill_n); +static_assert(!sfinae_test_fill_n); + +template +struct Test { + template + void operator()(Policy&& policy) { + { // simple test + int a[4]; + std::fill_n(policy, Iter(std::begin(a)), std::size(a), 33); + assert(std::all_of(std::begin(a), std::end(a), [](int i) { return i == 33; })); + } + { // check than an empty range works + int a[1] = {2}; + std::fill_n(policy, Iter(std::begin(a)), 0, 33); + assert(a[0] == 2); + } + { // check than a one-element range works + int a[1]; + std::fill_n(policy, Iter(std::begin(a)), std::size(a), 33); + assert(std::all_of(std::begin(a), std::end(a), [](int i) { return i == 33; })); + } + { // check than a two-element range works + int a[2]; + std::fill_n(policy, Iter(std::begin(a)), std::size(a), 33); + assert(std::all_of(std::begin(a), std::end(a), [](int i) { return i == 33; })); + } + { // check than a large range works + std::vector a(234, 2); + std::fill_n(policy, Iter(std::data(a)), std::size(a), 33); + assert(std::all_of(std::begin(a), std::end(a), [](int i) { return i == 33; })); + } + } +}; + +struct ThrowOnCopy { + ThrowOnCopy& operator=(const ThrowOnCopy&) { throw int{}; } +}; + +int main(int, char**) { + types::for_each(types::forward_iterator_list{}, TestIteratorWithPolicies{}); + +#ifndef TEST_HAS_NO_EXCEPTIONS + std::set_terminate(terminate_successful); + ThrowOnCopy a[2]; + try { + (void)std::fill_n(std::execution::par, std::begin(a), std::size(a), ThrowOnCopy{}); + } catch (int) { + assert(false); + } +#endif + + return 0; +}