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 _LIBCPP_BEGIN_NAMESPACE_STD 34 namespace __pstl { 35 36 // 37 // This partial PSTL backend runs everything serially. 38 // 39 // TODO: Right now, the serial backend must be used with another backend 40 // like the "default backend" because it doesn't implement all the 41 // necessary PSTL operations. It would be better to dispatch all 42 // algorithms to their serial counterpart directly, since this can 43 // often be more efficient than the "default backend"'s implementation 44 // if we end up running serially anyways. 45 // 46 47 template <class _ExecutionPolicy> 48 struct __find_if<__serial_backend_tag, _ExecutionPolicy> { 49 template <class _Policy, class _ForwardIterator, class _Pred> 50 _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator> 51 operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept { 52 return std::find_if(std::move(__first), std::move(__last), std::forward<_Pred>(__pred)); 53 } 54 }; 55 56 template <class _ExecutionPolicy> 57 struct __for_each<__serial_backend_tag, _ExecutionPolicy> { 58 template <class _Policy, class _ForwardIterator, class _Function> 59 _LIBCPP_HIDE_FROM_ABI optional<__empty> 60 operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Function&& __func) const noexcept { 61 std::for_each(std::move(__first), std::move(__last), std::forward<_Function>(__func)); 62 return __empty{}; 63 } 64 }; 65 66 template <class _ExecutionPolicy> 67 struct __merge<__serial_backend_tag, _ExecutionPolicy> { 68 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardOutIterator, class _Comp> 69 _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> operator()( 70 _Policy&&, 71 _ForwardIterator1 __first1, 72 _ForwardIterator1 __last1, 73 _ForwardIterator2 __first2, 74 _ForwardIterator2 __last2, 75 _ForwardOutIterator __outit, 76 _Comp&& __comp) const noexcept { 77 return std::merge( 78 std::move(__first1), 79 std::move(__last1), 80 std::move(__first2), 81 std::move(__last2), 82 std::move(__outit), 83 std::forward<_Comp>(__comp)); 84 } 85 }; 86 87 template <class _ExecutionPolicy> 88 struct __stable_sort<__serial_backend_tag, _ExecutionPolicy> { 89 template <class _Policy, class _RandomAccessIterator, class _Comp> 90 _LIBCPP_HIDE_FROM_ABI optional<__empty> 91 operator()(_Policy&&, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp&& __comp) const noexcept { 92 std::stable_sort(std::move(__first), std::move(__last), std::forward<_Comp>(__comp)); 93 return __empty{}; 94 } 95 }; 96 97 template <class _ExecutionPolicy> 98 struct __transform<__serial_backend_tag, _ExecutionPolicy> { 99 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _UnaryOperation> 100 _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> operator()( 101 _Policy&&, _ForwardIterator __first, _ForwardIterator __last, _ForwardOutIterator __outit, _UnaryOperation&& __op) 102 const noexcept { 103 return std::transform( 104 std::move(__first), std::move(__last), std::move(__outit), std::forward<_UnaryOperation>(__op)); 105 } 106 }; 107 108 template <class _ExecutionPolicy> 109 struct __transform_binary<__serial_backend_tag, _ExecutionPolicy> { 110 template <class _Policy, 111 class _ForwardIterator1, 112 class _ForwardIterator2, 113 class _ForwardOutIterator, 114 class _BinaryOperation> 115 _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> 116 operator()(_Policy&&, 117 _ForwardIterator1 __first1, 118 _ForwardIterator1 __last1, 119 _ForwardIterator2 __first2, 120 _ForwardOutIterator __outit, 121 _BinaryOperation&& __op) const noexcept { 122 return std::transform( 123 std::move(__first1), 124 std::move(__last1), 125 std::move(__first2), 126 std::move(__outit), 127 std::forward<_BinaryOperation>(__op)); 128 } 129 }; 130 131 template <class _ExecutionPolicy> 132 struct __transform_reduce<__serial_backend_tag, _ExecutionPolicy> { 133 template <class _Policy, class _ForwardIterator, class _Tp, class _BinaryOperation, class _UnaryOperation> 134 _LIBCPP_HIDE_FROM_ABI optional<_Tp> 135 operator()(_Policy&&, 136 _ForwardIterator __first, 137 _ForwardIterator __last, 138 _Tp __init, 139 _BinaryOperation&& __reduce, 140 _UnaryOperation&& __transform) const noexcept { 141 return std::transform_reduce( 142 std::move(__first), 143 std::move(__last), 144 std::move(__init), 145 std::forward<_BinaryOperation>(__reduce), 146 std::forward<_UnaryOperation>(__transform)); 147 } 148 }; 149 150 template <class _ExecutionPolicy> 151 struct __transform_reduce_binary<__serial_backend_tag, _ExecutionPolicy> { 152 template <class _Policy, 153 class _ForwardIterator1, 154 class _ForwardIterator2, 155 class _Tp, 156 class _BinaryOperation1, 157 class _BinaryOperation2> 158 _LIBCPP_HIDE_FROM_ABI optional<_Tp> operator()( 159 _Policy&&, 160 _ForwardIterator1 __first1, 161 _ForwardIterator1 __last1, 162 _ForwardIterator2 __first2, 163 _Tp __init, 164 _BinaryOperation1&& __reduce, 165 _BinaryOperation2&& __transform) const noexcept { 166 return std::transform_reduce( 167 std::move(__first1), 168 std::move(__last1), 169 std::move(__first2), 170 std::move(__init), 171 std::forward<_BinaryOperation1>(__reduce), 172 std::forward<_BinaryOperation2>(__transform)); 173 } 174 }; 175 176 } // namespace __pstl 177 _LIBCPP_END_NAMESPACE_STD 178 179 _LIBCPP_POP_MACROS 180 181 #endif // _LIBCPP___PSTL_BACKENDS_SERIAL_H 182