1*0fca6ea1SDimitry Andric //===----------------------------------------------------------------------===// 2*0fca6ea1SDimitry Andric // 3*0fca6ea1SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4*0fca6ea1SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 5*0fca6ea1SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6*0fca6ea1SDimitry Andric // 7*0fca6ea1SDimitry Andric //===----------------------------------------------------------------------===// 8*0fca6ea1SDimitry Andric 9*0fca6ea1SDimitry Andric #ifndef _LIBCPP___PSTL_CPU_ALGOS_MERGE_H 10*0fca6ea1SDimitry Andric #define _LIBCPP___PSTL_CPU_ALGOS_MERGE_H 11*0fca6ea1SDimitry Andric 12*0fca6ea1SDimitry Andric #include <__algorithm/merge.h> 13*0fca6ea1SDimitry Andric #include <__assert> 14*0fca6ea1SDimitry Andric #include <__config> 15*0fca6ea1SDimitry Andric #include <__iterator/concepts.h> 16*0fca6ea1SDimitry Andric #include <__pstl/backend_fwd.h> 17*0fca6ea1SDimitry Andric #include <__pstl/cpu_algos/cpu_traits.h> 18*0fca6ea1SDimitry Andric #include <__type_traits/is_execution_policy.h> 19*0fca6ea1SDimitry Andric #include <__utility/move.h> 20*0fca6ea1SDimitry Andric #include <optional> 21*0fca6ea1SDimitry Andric 22*0fca6ea1SDimitry Andric #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 23*0fca6ea1SDimitry Andric # pragma GCC system_header 24*0fca6ea1SDimitry Andric #endif 25*0fca6ea1SDimitry Andric 26*0fca6ea1SDimitry Andric _LIBCPP_PUSH_MACROS 27*0fca6ea1SDimitry Andric #include <__undef_macros> 28*0fca6ea1SDimitry Andric 29*0fca6ea1SDimitry Andric _LIBCPP_BEGIN_NAMESPACE_STD 30*0fca6ea1SDimitry Andric namespace __pstl { 31*0fca6ea1SDimitry Andric 32*0fca6ea1SDimitry Andric template <class _Backend, class _RawExecutionPolicy> 33*0fca6ea1SDimitry Andric struct __cpu_parallel_merge { 34*0fca6ea1SDimitry Andric template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardOutIterator, class _Comp> operator__cpu_parallel_merge35*0fca6ea1SDimitry Andric _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> operator()( 36*0fca6ea1SDimitry Andric _Policy&& __policy, 37*0fca6ea1SDimitry Andric _ForwardIterator1 __first1, 38*0fca6ea1SDimitry Andric _ForwardIterator1 __last1, 39*0fca6ea1SDimitry Andric _ForwardIterator2 __first2, 40*0fca6ea1SDimitry Andric _ForwardIterator2 __last2, 41*0fca6ea1SDimitry Andric _ForwardOutIterator __result, 42*0fca6ea1SDimitry Andric _Comp __comp) const noexcept { 43*0fca6ea1SDimitry Andric if constexpr (__is_parallel_execution_policy_v<_RawExecutionPolicy> && 44*0fca6ea1SDimitry Andric __has_random_access_iterator_category_or_concept<_ForwardIterator1>::value && 45*0fca6ea1SDimitry Andric __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value && 46*0fca6ea1SDimitry Andric __has_random_access_iterator_category_or_concept<_ForwardOutIterator>::value) { 47*0fca6ea1SDimitry Andric auto __res = __cpu_traits<_Backend>::__merge( 48*0fca6ea1SDimitry Andric __first1, 49*0fca6ea1SDimitry Andric __last1, 50*0fca6ea1SDimitry Andric __first2, 51*0fca6ea1SDimitry Andric __last2, 52*0fca6ea1SDimitry Andric __result, 53*0fca6ea1SDimitry Andric __comp, 54*0fca6ea1SDimitry Andric [&__policy](_ForwardIterator1 __g_first1, 55*0fca6ea1SDimitry Andric _ForwardIterator1 __g_last1, 56*0fca6ea1SDimitry Andric _ForwardIterator2 __g_first2, 57*0fca6ea1SDimitry Andric _ForwardIterator2 __g_last2, 58*0fca6ea1SDimitry Andric _ForwardOutIterator __g_result, 59*0fca6ea1SDimitry Andric _Comp __g_comp) { 60*0fca6ea1SDimitry Andric using _MergeUnseq = __pstl::__merge<_Backend, __remove_parallel_policy_t<_RawExecutionPolicy>>; 61*0fca6ea1SDimitry Andric [[maybe_unused]] auto __g_res = _MergeUnseq()( 62*0fca6ea1SDimitry Andric std::__remove_parallel_policy(__policy), 63*0fca6ea1SDimitry Andric std::move(__g_first1), 64*0fca6ea1SDimitry Andric std::move(__g_last1), 65*0fca6ea1SDimitry Andric std::move(__g_first2), 66*0fca6ea1SDimitry Andric std::move(__g_last2), 67*0fca6ea1SDimitry Andric std::move(__g_result), 68*0fca6ea1SDimitry Andric std::move(__g_comp)); 69*0fca6ea1SDimitry Andric _LIBCPP_ASSERT_INTERNAL(__g_res, "unsed/sed should never try to allocate!"); 70*0fca6ea1SDimitry Andric }); 71*0fca6ea1SDimitry Andric if (!__res) 72*0fca6ea1SDimitry Andric return nullopt; 73*0fca6ea1SDimitry Andric return __result + (__last1 - __first1) + (__last2 - __first2); 74*0fca6ea1SDimitry Andric } else { 75*0fca6ea1SDimitry Andric return std::merge(__first1, __last1, __first2, __last2, __result, __comp); 76*0fca6ea1SDimitry Andric } 77*0fca6ea1SDimitry Andric } 78*0fca6ea1SDimitry Andric }; 79*0fca6ea1SDimitry Andric 80*0fca6ea1SDimitry Andric } // namespace __pstl 81*0fca6ea1SDimitry Andric _LIBCPP_END_NAMESPACE_STD 82*0fca6ea1SDimitry Andric 83*0fca6ea1SDimitry Andric _LIBCPP_POP_MACROS 84*0fca6ea1SDimitry Andric 85*0fca6ea1SDimitry Andric #endif // _LIBCPP___PSTL_CPU_ALGOS_MERGE_H 86