diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -77,6 +77,7 @@ __algorithm/pstl_backends/cpu_backends/fill.h __algorithm/pstl_backends/cpu_backends/find_if.h __algorithm/pstl_backends/cpu_backends/for_each.h + __algorithm/pstl_backends/cpu_backends/merge.h __algorithm/pstl_backends/cpu_backends/serial.h __algorithm/pstl_backends/cpu_backends/thread.h __algorithm/pstl_backends/cpu_backends/transform.h @@ -85,6 +86,7 @@ __algorithm/pstl_find.h __algorithm/pstl_for_each.h __algorithm/pstl_frontend_dispatch.h + __algorithm/pstl_merge.h __algorithm/pstl_transform.h __algorithm/push_heap.h __algorithm/ranges_adjacent_find.h diff --git a/libcxx/include/__algorithm/pstl_backend.h b/libcxx/include/__algorithm/pstl_backend.h --- a/libcxx/include/__algorithm/pstl_backend.h +++ b/libcxx/include/__algorithm/pstl_backend.h @@ -72,6 +72,15 @@ template void __pstl_fill_n(_Backend, _Iterator __first, _SizeT __n, const _Tp& __value); + template + _OutIterator __pstl_merge(_Backend, + _Iterator1 __first1, + _Iterator1 __last1, + _Iterator2 __first2, + _Iterator2 __last2, + _OutIterator __result, + _Comp __comp); + // TODO: Complete this list */ diff --git a/libcxx/include/__algorithm/pstl_backends/cpu_backend.h b/libcxx/include/__algorithm/pstl_backends/cpu_backend.h --- a/libcxx/include/__algorithm/pstl_backends/cpu_backend.h +++ b/libcxx/include/__algorithm/pstl_backends/cpu_backend.h @@ -20,6 +20,20 @@ // Cancel the execution of other jobs - they aren't needed anymore void __cancel_execution(); + template + void __parallel_merge( + _RandomAccessIterator1 __first1, + _RandomAccessIterator1 __last1, + _RandomAccessIterator2 __first2, + _RandomAccessIterator2 __last2, + _RandomAccessIterator3 __outit, + _Compare __comp, + _LeafMerge __leaf_merge); + TODO: Document the parallel backend */ @@ -27,6 +41,7 @@ #include <__algorithm/pstl_backends/cpu_backends/fill.h> #include <__algorithm/pstl_backends/cpu_backends/find_if.h> #include <__algorithm/pstl_backends/cpu_backends/for_each.h> +#include <__algorithm/pstl_backends/cpu_backends/merge.h> #include <__algorithm/pstl_backends/cpu_backends/transform.h> #endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKEND_H diff --git a/libcxx/include/__algorithm/pstl_backends/cpu_backends/merge.h b/libcxx/include/__algorithm/pstl_backends/cpu_backends/merge.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/pstl_backends/cpu_backends/merge.h @@ -0,0 +1,79 @@ +//===----------------------------------------------------------------------===// +// +// 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_BACKENDS_CPU_BACKENDS_MERGE_H +#define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_MERGE_H + +#include <__algorithm/merge.h> +#include <__algorithm/pstl_backends/cpu_backends/backend.h> +#include <__config> +#include <__iterator/iterator_traits.h> +#include <__type_traits/is_execution_policy.h> +#include <__utility/move.h> +#include <__utility/terminate_on_exception.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 +_LIBCPP_HIDE_FROM_ABI _ForwardOutIterator __pstl_merge( + __cpu_backend_tag, + _ForwardIterator1 __first1, + _ForwardIterator1 __last1, + _ForwardIterator2 __first2, + _ForwardIterator2 __last2, + _ForwardOutIterator __result, + _Comp __comp) { + if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> && + __has_random_access_iterator_category<_ForwardIterator1>::value && + __has_random_access_iterator_category<_ForwardIterator2>::value && + __has_random_access_iterator_category<_ForwardOutIterator>::value) { + return std::__terminate_on_exception([&] { + __par_backend::__parallel_merge( + __first1, + __last1, + __first2, + __last2, + __result, + __comp, + [](_ForwardIterator1 __g_first1, + _ForwardIterator1 __g_last1, + _ForwardIterator2 __g_first2, + _ForwardIterator2 __g_last2, + _ForwardOutIterator __g_result, + _Comp __g_comp) { + return std::__pstl_merge<__remove_parallel_policy_t<_ExecutionPolicy>>( + __cpu_backend_tag{}, + std::move(__g_first1), + std::move(__g_last1), + std::move(__g_first2), + std::move(__g_last2), + std::move(__g_result), + std::move(__g_comp)); + }); + return __result + (__last1 - __first1) + (__last2 - __first2); + }); + } else { + return std::merge(__first1, __last1, __first2, __last2, __result, __comp); + } +} + +_LIBCPP_END_NAMESPACE_STD + +#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17 + +#endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_MERGE_H diff --git a/libcxx/include/__algorithm/pstl_backends/cpu_backends/serial.h b/libcxx/include/__algorithm/pstl_backends/cpu_backends/serial.h --- a/libcxx/include/__algorithm/pstl_backends/cpu_backends/serial.h +++ b/libcxx/include/__algorithm/pstl_backends/cpu_backends/serial.h @@ -30,6 +30,22 @@ _LIBCPP_HIDE_FROM_ABI inline void __cancel_execution() {} +template +_LIBCPP_HIDE_FROM_ABI void __parallel_merge( + _RandomAccessIterator1 __first1, + _RandomAccessIterator1 __last1, + _RandomAccessIterator2 __first2, + _RandomAccessIterator2 __last2, + _RandomAccessIterator3 __outit, + _Compare __comp, + _LeafMerge __leaf_merge) { + __leaf_merge(__first1, __last1, __first2, __last2, __outit, __comp); +} + // TODO: Complete this list } // namespace __serial_cpu_backend diff --git a/libcxx/include/__algorithm/pstl_backends/cpu_backends/thread.h b/libcxx/include/__algorithm/pstl_backends/cpu_backends/thread.h --- a/libcxx/include/__algorithm/pstl_backends/cpu_backends/thread.h +++ b/libcxx/include/__algorithm/pstl_backends/cpu_backends/thread.h @@ -33,6 +33,22 @@ _LIBCPP_HIDE_FROM_ABI inline void __cancel_execution() {} +template +_LIBCPP_HIDE_FROM_ABI void __parallel_merge( + _RandomAccessIterator1 __first1, + _RandomAccessIterator1 __last1, + _RandomAccessIterator2 __first2, + _RandomAccessIterator2 __last2, + _RandomAccessIterator3 __outit, + _Compare __comp, + _LeafMerge __leaf_merge) { + __leaf_merge(__first1, __last1, __first2, __last2, __outit, __comp); +} + } // namespace __thread_cpu_backend } // namespace __par_backend diff --git a/libcxx/include/__algorithm/pstl_merge.h b/libcxx/include/__algorithm/pstl_merge.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/pstl_merge.h @@ -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 +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_PSTL_MERGE_H +#define _LIBCPP___ALGORITHM_PSTL_MERGE_H + +#include <__algorithm/pstl_backend.h> +#include <__config> +#include <__functional/operations.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 , + class _RawPolicy = __remove_cvref_t<_ExecutionPolicy>, + enable_if_t, int> = 0> +_LIBCPP_HIDE_FROM_ABI _ForwardOutIterator +merge(_ExecutionPolicy&&, + _ForwardIterator1 __first1, + _ForwardIterator1 __last1, + _ForwardIterator2 __first2, + _ForwardIterator2 __last2, + _ForwardOutIterator __result, + _Comp __comp = {}) { + using _Backend = typename __select_backend<_RawPolicy>::type; + return std::__pstl_merge<_RawPolicy>( + _Backend{}, + std::move(__first1), + std::move(__last1), + std::move(__first2), + std::move(__last2), + std::move(__result), + std::move(__comp)); +} + +_LIBCPP_END_NAMESPACE_STD + +#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17 + +#endif // _LIBCPP___ALGORITHM_PSTL_MERGE_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 @@ -2869,89 +2869,6 @@ }); } -//------------------------------------------------------------------------ -// merge -//------------------------------------------------------------------------ - -template -_OutputIterator __brick_merge( - _ForwardIterator1 __first1, - _ForwardIterator1 __last1, - _ForwardIterator2 __first2, - _ForwardIterator2 __last2, - _OutputIterator __d_first, - _Compare __comp, - /* __is_vector = */ std::false_type) noexcept { - return std::merge(__first1, __last1, __first2, __last2, __d_first, __comp); -} - -template -_RandomAccessIterator3 __brick_merge( - _RandomAccessIterator1 __first1, - _RandomAccessIterator1 __last1, - _RandomAccessIterator2 __first2, - _RandomAccessIterator2 __last2, - _RandomAccessIterator3 __d_first, - _Compare __comp, - /* __is_vector = */ std::true_type) noexcept { - // TODO: vectorize - return std::merge(__first1, __last1, __first2, __last2, __d_first, __comp); -} - -template -_OutputIterator __pattern_merge( - _Tag, - _ExecutionPolicy&&, - _ForwardIterator1 __first1, - _ForwardIterator1 __last1, - _ForwardIterator2 __first2, - _ForwardIterator2 __last2, - _OutputIterator __d_first, - _Compare __comp) noexcept { - return __internal::__brick_merge( - __first1, __last1, __first2, __last2, __d_first, __comp, typename _Tag::__is_vector{}); -} - -template -_RandomAccessIterator3 __pattern_merge( - __parallel_tag<_IsVector> __tag, - _ExecutionPolicy&& __exec, - _RandomAccessIterator1 __first1, - _RandomAccessIterator1 __last1, - _RandomAccessIterator2 __first2, - _RandomAccessIterator2 __last2, - _RandomAccessIterator3 __d_first, - _Compare __comp) { - using __backend_tag = typename decltype(__tag)::__backend_tag; - - __par_backend::__parallel_merge( - __backend_tag{}, - std::forward<_ExecutionPolicy>(__exec), - __first1, - __last1, - __first2, - __last2, - __d_first, - __comp, - [](_RandomAccessIterator1 __f1, - _RandomAccessIterator1 __l1, - _RandomAccessIterator2 __f2, - _RandomAccessIterator2 __l2, - _RandomAccessIterator3 __f3, - _Compare __comp) { return __internal::__brick_merge(__f1, __l1, __f2, __l2, __f3, __comp, _IsVector{}); }); - return __d_first + (__last1 - __first1) + (__last2 - __first2); -} - //------------------------------------------------------------------------ // inplace_merge //------------------------------------------------------------------------ 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 @@ -763,37 +763,6 @@ } // [alg.merge] -template -__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator> -merge(_ExecutionPolicy&& __exec, - _ForwardIterator1 __first1, - _ForwardIterator1 __last1, - _ForwardIterator2 __first2, - _ForwardIterator2 __last2, - _ForwardIterator __d_first, - _Compare __comp) { - auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first1, __first2, __d_first); - - return __pstl::__internal::__pattern_merge( - __dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __d_first, __comp); -} - -template -__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator> -merge(_ExecutionPolicy&& __exec, - _ForwardIterator1 __first1, - _ForwardIterator1 __last1, - _ForwardIterator2 __first2, - _ForwardIterator2 __last2, - _ForwardIterator __d_first) { - return std::merge( - std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __d_first, std::less<>()); -} - template __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void> inplace_merge(_ExecutionPolicy&& __exec, diff --git a/libcxx/include/__pstl/internal/parallel_backend_serial.h b/libcxx/include/__pstl/internal/parallel_backend_serial.h --- a/libcxx/include/__pstl/internal/parallel_backend_serial.h +++ b/libcxx/include/__pstl/internal/parallel_backend_serial.h @@ -98,16 +98,6 @@ __leaf_sort(__first, __last, __comp); } -template -_LIBCPP_HIDE_FROM_ABI void -__parallel_merge(__pstl::__internal::__serial_backend_tag, _ExecutionPolicy&&, _RandomAccessIterator1 __first1, - _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, - _RandomAccessIterator3 __outit, _Compare __comp, _LeafMerge __leaf_merge) -{ - __leaf_merge(__first1, __last1, __first2, __last2, __outit, __comp); -} - template _LIBCPP_HIDE_FROM_ABI void __parallel_invoke(__pstl::__internal::__serial_backend_tag, _ExecutionPolicy&&, _F1&& __f1, _F2&& __f2) diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -1805,6 +1805,7 @@ #include <__algorithm/pstl_fill.h> #include <__algorithm/pstl_find.h> #include <__algorithm/pstl_for_each.h> +#include <__algorithm/pstl_merge.h> #include <__algorithm/pstl_transform.h> #include <__algorithm/push_heap.h> #include <__algorithm/ranges_adjacent_find.h> diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -338,6 +338,9 @@ module pstl_backends_cpu_backends_for_each { private header "__algorithm/pstl_backends/cpu_backends/for_each.h" } + module pstl_backends_cpu_backends_merge { + private header "__algorithm/pstl_backends/cpu_backends/merge.h" + } module pstl_backends_cpu_backends_serial { private header "__algorithm/pstl_backends/cpu_backends/serial.h" } diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp --- a/libcxx/test/libcxx/private_headers.verify.cpp +++ b/libcxx/test/libcxx/private_headers.verify.cpp @@ -120,6 +120,7 @@ #include <__algorithm/pstl_backends/cpu_backends/fill.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/fill.h'}} #include <__algorithm/pstl_backends/cpu_backends/find_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/find_if.h'}} #include <__algorithm/pstl_backends/cpu_backends/for_each.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/for_each.h'}} +#include <__algorithm/pstl_backends/cpu_backends/merge.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/merge.h'}} #include <__algorithm/pstl_backends/cpu_backends/serial.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/serial.h'}} #include <__algorithm/pstl_backends/cpu_backends/thread.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/thread.h'}} #include <__algorithm/pstl_backends/cpu_backends/transform.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/transform.h'}} diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.merge/pstl.merge.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.merge/pstl.merge.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.sorting/alg.merge/pstl.merge.pass.cpp @@ -0,0 +1,132 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// merge(ExecutionPolicy&& exec, +// ForwardIterator1 first1, ForwardIterator1 last1, +// ForwardIterator2 first2, ForwardIterator2 last2, +// ForwardIterator result); +// +// template +// ForwardIterator +// merge(ExecutionPolicy&& exec, +// ForwardIterator1 first1, ForwardIterator1 last1, +// ForwardIterator2 first2, ForwardIterator2 last2, +// ForwardIterator result, Compare comp); + +#include +#include +#include +#include +#include +#include + +#include "type_algorithms.h" +#include "test_execution_policies.h" +#include "test_iterators.h" + +template +struct Test { + template + void operator()(Policy&& policy) { + { // simple test + int a[] = {1, 3, 5, 7, 9}; + int b[] = {2, 4, 6, 8, 10}; + std::array out; + std::merge( + policy, Iter1(std::begin(a)), Iter1(std::end(a)), Iter2(std::begin(b)), Iter2(std::end(b)), std::begin(out)); + assert((out == std::array{1, 2, 3, 4, 5, 6, 7, 8, 9, 10})); + } + + { // check that it works with the first range being empty + std::array a; + int b[] = {2, 4, 6, 8, 10}; + std::array out; + std::merge( + policy, Iter1(std::begin(a)), Iter1(std::end(a)), Iter2(std::begin(b)), Iter2(std::end(b)), std::begin(out)); + assert((out == std::array{2, 4, 6, 8, 10})); + } + + { // check that it works with the second range being empty + int a[] = {2, 4, 6, 8, 10}; + std::array b; + std::array out; + std::merge( + policy, Iter1(std::begin(a)), Iter1(std::end(a)), Iter2(std::begin(b)), Iter2(std::end(b)), std::begin(out)); + assert((out == std::array{2, 4, 6, 8, 10})); + } + + { // check that it works when the ranges don't have the same length + int a[] = {2, 4, 6, 8, 10}; + int b[] = {3, 4}; + std::array out; + std::merge( + policy, Iter1(std::begin(a)), Iter1(std::end(a)), Iter2(std::begin(b)), Iter2(std::end(b)), std::begin(out)); + assert((out == std::array{2, 3, 4, 4, 6, 8, 10})); + } + + { // check that large ranges work + std::vector a(100); + std::vector b(100); + { + int i = 0; + for (auto& e : a) { + e = i; + i += 2; + } + } + + { + int i = 1; + for (auto& e : b) { + e = i; + i += 2; + } + } + + std::vector out(std::size(a) + std::size(b)); + std::merge( + Iter1(a.data()), Iter1(a.data() + a.size()), Iter2(b.data()), Iter2(b.data() + b.size()), std::begin(out)); + std::vector expected(200); + std::iota(expected.begin(), expected.end(), 0); + assert(std::equal(out.begin(), out.end(), expected.begin())); + } + + { // check that the predicate is used + int a[] = {10, 9, 8, 7}; + int b[] = {8, 4, 3}; + std::array out; + std::merge( + policy, + Iter1(std::begin(a)), + Iter1(std::end(a)), + Iter2(std::begin(b)), + Iter2(std::end(b)), + std::begin(out), + std::greater{}); + assert((out == std::array{10, 9, 8, 8, 7, 4, 3})); + } + } +}; + +int main(int, char**) { + types::for_each(types::forward_iterator_list{}, types::apply_type_identity{[](auto v) { + using Iter = typename decltype(v)::type; + types::for_each( + types::forward_iterator_list{}, + TestIteratorWithPolicies::template apply>{}); + }}); + + return 0; +}