1 // -*- C++ -*- 2 //===----------------------------------------------------------------------===// 3 // 4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5 // See https://llvm.org/LICENSE.txt for license information. 6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7 // 8 //===----------------------------------------------------------------------===// 9 10 #ifndef _LIBCPP___PSTL_BACKENDS_SERIAL_H 11 #define _LIBCPP___PSTL_BACKENDS_SERIAL_H 12 13 #include <__algorithm/find_if.h> 14 #include <__algorithm/for_each.h> 15 #include <__algorithm/merge.h> 16 #include <__algorithm/stable_sort.h> 17 #include <__algorithm/transform.h> 18 #include <__config> 19 #include <__numeric/transform_reduce.h> 20 #include <__pstl/backend_fwd.h> 21 #include <__utility/empty.h> 22 #include <__utility/forward.h> 23 #include <__utility/move.h> 24 #include <optional> 25 26 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 27 # pragma GCC system_header 28 #endif 29 30 _LIBCPP_PUSH_MACROS 31 #include <__undef_macros> 32 33 #if _LIBCPP_STD_VER >= 17 34 35 _LIBCPP_BEGIN_NAMESPACE_STD 36 namespace __pstl { 37 38 // 39 // This partial PSTL backend runs everything serially. 40 // 41 // TODO: Right now, the serial backend must be used with another backend 42 // like the "default backend" because it doesn't implement all the 43 // necessary PSTL operations. It would be better to dispatch all 44 // algorithms to their serial counterpart directly, since this can 45 // often be more efficient than the "default backend"'s implementation 46 // if we end up running serially anyways. 47 // 48 49 template <class _ExecutionPolicy> 50 struct __find_if<__serial_backend_tag, _ExecutionPolicy> { 51 template <class _Policy, class _ForwardIterator, class _Pred> 52 _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator> 53 operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept { 54 return std::find_if(std::move(__first), std::move(__last), std::forward<_Pred>(__pred)); 55 } 56 }; 57 58 template <class _ExecutionPolicy> 59 struct __for_each<__serial_backend_tag, _ExecutionPolicy> { 60 template <class _Policy, class _ForwardIterator, class _Function> 61 _LIBCPP_HIDE_FROM_ABI optional<__empty> 62 operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Function&& __func) const noexcept { 63 std::for_each(std::move(__first), std::move(__last), std::forward<_Function>(__func)); 64 return __empty{}; 65 } 66 }; 67 68 template <class _ExecutionPolicy> 69 struct __merge<__serial_backend_tag, _ExecutionPolicy> { 70 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardOutIterator, class _Comp> 71 _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> operator()( 72 _Policy&&, 73 _ForwardIterator1 __first1, 74 _ForwardIterator1 __last1, 75 _ForwardIterator2 __first2, 76 _ForwardIterator2 __last2, 77 _ForwardOutIterator __outit, 78 _Comp&& __comp) const noexcept { 79 return std::merge( 80 std::move(__first1), 81 std::move(__last1), 82 std::move(__first2), 83 std::move(__last2), 84 std::move(__outit), 85 std::forward<_Comp>(__comp)); 86 } 87 }; 88 89 template <class _ExecutionPolicy> 90 struct __stable_sort<__serial_backend_tag, _ExecutionPolicy> { 91 template <class _Policy, class _RandomAccessIterator, class _Comp> 92 _LIBCPP_HIDE_FROM_ABI optional<__empty> 93 operator()(_Policy&&, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp&& __comp) const noexcept { 94 std::stable_sort(std::move(__first), std::move(__last), std::forward<_Comp>(__comp)); 95 return __empty{}; 96 } 97 }; 98 99 template <class _ExecutionPolicy> 100 struct __transform<__serial_backend_tag, _ExecutionPolicy> { 101 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _UnaryOperation> 102 _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> operator()( 103 _Policy&&, _ForwardIterator __first, _ForwardIterator __last, _ForwardOutIterator __outit, _UnaryOperation&& __op) 104 const noexcept { 105 return std::transform( 106 std::move(__first), std::move(__last), std::move(__outit), std::forward<_UnaryOperation>(__op)); 107 } 108 }; 109 110 template <class _ExecutionPolicy> 111 struct __transform_binary<__serial_backend_tag, _ExecutionPolicy> { 112 template <class _Policy, 113 class _ForwardIterator1, 114 class _ForwardIterator2, 115 class _ForwardOutIterator, 116 class _BinaryOperation> 117 _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> 118 operator()(_Policy&&, 119 _ForwardIterator1 __first1, 120 _ForwardIterator1 __last1, 121 _ForwardIterator2 __first2, 122 _ForwardOutIterator __outit, 123 _BinaryOperation&& __op) const noexcept { 124 return std::transform( 125 std::move(__first1), 126 std::move(__last1), 127 std::move(__first2), 128 std::move(__outit), 129 std::forward<_BinaryOperation>(__op)); 130 } 131 }; 132 133 template <class _ExecutionPolicy> 134 struct __transform_reduce<__serial_backend_tag, _ExecutionPolicy> { 135 template <class _Policy, class _ForwardIterator, class _Tp, class _BinaryOperation, class _UnaryOperation> 136 _LIBCPP_HIDE_FROM_ABI optional<_Tp> 137 operator()(_Policy&&, 138 _ForwardIterator __first, 139 _ForwardIterator __last, 140 _Tp __init, 141 _BinaryOperation&& __reduce, 142 _UnaryOperation&& __transform) const noexcept { 143 return std::transform_reduce( 144 std::move(__first), 145 std::move(__last), 146 std::move(__init), 147 std::forward<_BinaryOperation>(__reduce), 148 std::forward<_UnaryOperation>(__transform)); 149 } 150 }; 151 152 template <class _ExecutionPolicy> 153 struct __transform_reduce_binary<__serial_backend_tag, _ExecutionPolicy> { 154 template <class _Policy, 155 class _ForwardIterator1, 156 class _ForwardIterator2, 157 class _Tp, 158 class _BinaryOperation1, 159 class _BinaryOperation2> 160 _LIBCPP_HIDE_FROM_ABI optional<_Tp> operator()( 161 _Policy&&, 162 _ForwardIterator1 __first1, 163 _ForwardIterator1 __last1, 164 _ForwardIterator2 __first2, 165 _Tp __init, 166 _BinaryOperation1&& __reduce, 167 _BinaryOperation2&& __transform) const noexcept { 168 return std::transform_reduce( 169 std::move(__first1), 170 std::move(__last1), 171 std::move(__first2), 172 std::move(__init), 173 std::forward<_BinaryOperation1>(__reduce), 174 std::forward<_BinaryOperation2>(__transform)); 175 } 176 }; 177 178 } // namespace __pstl 179 _LIBCPP_END_NAMESPACE_STD 180 181 #endif // _LIBCPP_STD_VER >= 17 182 183 _LIBCPP_POP_MACROS 184 185 #endif // _LIBCPP___PSTL_BACKENDS_SERIAL_H 186