1 //===----------------------------------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #ifndef _LIBCPP___ALGORITHM_PSTL_BACKEND_H 10 #define _LIBCPP___ALGORITHM_PSTL_BACKEND_H 11 12 #include <__algorithm/pstl_backends/cpu_backend.h> 13 #include <__config> 14 #include <execution> 15 16 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 17 # pragma GCC system_header 18 #endif 19 20 #if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17 21 22 _LIBCPP_BEGIN_NAMESPACE_STD 23 24 /* 25 TODO: Documentation of how backends work 26 27 A PSTL parallel backend is a tag type to which the following functions are associated, at minimum: 28 29 template <class _ExecutionPolicy, class _Iterator, class _Func> 30 optional<__empty> __pstl_for_each(_Backend, _ExecutionPolicy&&, _Iterator __first, _Iterator __last, _Func __f); 31 32 template <class _ExecutionPolicy, class _Iterator, class _Predicate> 33 optional<_Iterator> __pstl_find_if(_Backend, _Iterator __first, _Iterator __last, _Predicate __pred); 34 35 template <class _ExecutionPolicy, class _RandomAccessIterator, class _Comp> 36 optional<__empty> 37 __pstl_stable_sort(_Backend, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp); 38 39 template <class _ExecutionPolicy, 40 class _ForwardIterator1, 41 class _ForwardIterator2, 42 class _ForwardOutIterator, 43 class _Comp> 44 optional<_ForwardOutIterator> __pstl_merge(_Backend, 45 _ForwardIterator1 __first1, 46 _ForwardIterator1 __last1, 47 _ForwardIterator2 __first2, 48 _ForwardIterator2 __last2, 49 _ForwardOutIterator __result, 50 _Comp __comp); 51 52 template <class _ExecutionPolicy, class _InIterator, class _OutIterator, class _UnaryOperation> 53 optional<_OutIterator> 54 __pstl_transform(_Backend, _InIterator __first, _InIterator __last, _OutIterator __result, _UnaryOperation __op); 55 56 template <class _ExecutionPolicy, class _InIterator1, class _InIterator2, class _OutIterator, class _BinaryOperation> 57 optional<_OutIterator> __pstl_transform(_InIterator1 __first1, 58 _InIterator2 __first2, 59 _InIterator1 __last1, 60 _OutIterator __result, 61 _BinaryOperation __op); 62 63 template <class _ExecutionPolicy, 64 class _Iterator1, 65 class _Iterator2, 66 class _Tp, 67 class _BinaryOperation1, 68 class _BinaryOperation2> 69 optional<_Tp> __pstl_transform_reduce(_Backend, 70 _Iterator1 __first1, 71 _Iterator1 __last1, 72 _Iterator2 __first2, 73 _Iterator2 __last2, 74 _Tp __init, 75 _BinaryOperation1 __reduce, 76 _BinaryOperation2 __transform); 77 78 template <class _ExecutionPolicy, class _Iterator, class _Tp, class _BinaryOperation, class _UnaryOperation> 79 optional<_Tp> __pstl_transform_reduce(_Backend, 80 _Iterator __first, 81 _Iterator __last, 82 _Tp __init, 83 _BinaryOperation __reduce, 84 _UnaryOperation __transform); 85 86 // TODO: Complete this list 87 88 The following functions are optional but can be provided. If provided, they are used by the corresponding 89 algorithms, otherwise they are implemented in terms of other algorithms. If none of the optional algorithms are 90 implemented, all the algorithms will eventually forward to the basis algorithms listed above: 91 92 template <class _ExecutionPolicy, class _Iterator, class _Size, class _Func> 93 optional<__empty> __pstl_for_each_n(_Backend, _Iterator __first, _Size __n, _Func __f); 94 95 template <class _ExecutionPolicy, class _Iterator, class _Predicate> 96 optional<bool> __pstl_any_of(_Backend, _Iterator __first, _iterator __last, _Predicate __pred); 97 98 template <class _ExecutionPolicy, class _Iterator, class _Predicate> 99 optional<bool> __pstl_all_of(_Backend, _Iterator __first, _iterator __last, _Predicate __pred); 100 101 template <class _ExecutionPolicy, class _Iterator, class _Predicate> 102 optional<bool> __pstl_none_of(_Backend, _Iterator __first, _iterator __last, _Predicate __pred); 103 104 template <class _ExecutionPolicy, class _Iterator, class _Tp> 105 optional<_Iterator> __pstl_find(_Backend, _Iterator __first, _Iterator __last, const _Tp& __value); 106 107 template <class _ExecutionPolicy, class _Iterator, class _Predicate> 108 optional<_Iterator> __pstl_find_if_not(_Backend, _Iterator __first, _Iterator __last, _Predicate __pred); 109 110 template <class _ExecutionPolicy, class _Iterator, class _Tp> 111 optional<__empty> __pstl_fill(_Backend, _Iterator __first, _Iterator __last, const _Tp& __value); 112 113 template <class _ExecutionPolicy, class _Iterator, class _SizeT, class _Tp> 114 optional<__empty> __pstl_fill_n(_Backend, _Iterator __first, _SizeT __n, const _Tp& __value); 115 116 template <class _ExecutionPolicy, class _Iterator, class _Generator> 117 optional<__empty> __pstl_generate(_Backend, _Iterator __first, _Iterator __last, _Generator __gen); 118 119 template <class _ExecutionPolicy, class _Iterator, class _Predicate> 120 optional<__empty> __pstl_is_partitioned(_Backend, _Iterator __first, _Iterator __last, _Predicate __pred); 121 122 template <class _ExecutionPolicy, class _Iterator, class _Size, class _Generator> 123 optional<__empty> __pstl_generator_n(_Backend, _Iterator __first, _Size __n, _Generator __gen); 124 125 template <class _ExecutionPolicy, class _terator1, class _Iterator2, class _OutIterator, class _Comp> 126 optional<_OutIterator> __pstl_merge(_Backend, 127 _Iterator1 __first1, 128 _Iterator1 __last1, 129 _Iterator2 __first2, 130 _Iterator2 __last2, 131 _OutIterator __result, 132 _Comp __comp); 133 134 template <class _ExecutionPolicy, class _Iterator, class _OutIterator> 135 optional<_OutIterator> __pstl_move(_Backend, _Iterator __first, _Iterator __last, _OutIterator __result); 136 137 template <class _ExecutionPolicy, class _Iterator, class _Tp, class _BinaryOperation> 138 optional<_Tp> __pstl_reduce(_Backend, _Iterator __first, _Iterator __last, _Tp __init, _BinaryOperation __op); 139 140 temlate <class _ExecutionPolicy, class _Iterator> 141 optional<__iter_value_type<_Iterator>> __pstl_reduce(_Backend, _Iterator __first, _Iterator __last); 142 143 template <class _ExecutionPolicy, class _Iterator, class _Tp> 144 optional<__iter_diff_t<_Iterator>> __pstl_count(_Backend, _Iterator __first, _Iterator __last, const _Tp& __value); 145 146 template <class _ExecutionPolicy, class _Iterator, class _Predicate> 147 optional<__iter_diff_t<_Iterator>> __pstl_count_if(_Backend, _Iterator __first, _Iterator __last, _Predicate __pred); 148 149 template <class _ExecutionPolicy, class _Iterator, class _Tp> 150 optional<__empty> 151 __pstl_replace(_Backend, _Iterator __first, _Iterator __last, const _Tp& __old_value, const _Tp& __new_value); 152 153 template <class _ExecutionPolicy, class _Iterator, class _Pred, class _Tp> 154 optional<__empty> 155 __pstl_replace_if(_Backend, _Iterator __first, _Iterator __last, _Pred __pred, const _Tp& __new_value); 156 157 template <class _ExecutionPolicy, class _Iterator, class _OutIterator, class _Tp> 158 optional<__empty> __pstl_replace_copy(_Backend, 159 _Iterator __first, 160 _Iterator __last, 161 _OutIterator __result, 162 const _Tp& __old_value, 163 const _Tp& __new_value); 164 165 template <class _ExecutionPolicy, class _Iterator, class _OutIterator, class _Pred, class _Tp> 166 optional<__empty> __pstl_replace_copy_if(_Backend, 167 _Iterator __first, 168 _Iterator __last, 169 _OutIterator __result, 170 _Pred __pred, 171 const _Tp& __new_value); 172 173 template <class _ExecutionPolicy, class _Iterator, class _OutIterator> 174 optional<_Iterator> __pstl_rotate_copy( 175 _Backend, _Iterator __first, _Iterator __middle, _Iterator __last, _OutIterator __result); 176 177 template <class _ExecutionPolicy, class _Iterator, class _Comp> 178 optional<__empty> __pstl_sort(_Backend, _Iterator __first, _Iterator __last, _Comp __comp); 179 180 template <class _ExecutionPolicy, class _Iterator1, class _Iterator2, class _Comp> 181 optional<bool> __pstl_equal(_Backend, _Iterator1 first1, _Iterator1 last1, _Iterator2 first2, _Comp __comp); 182 183 // TODO: Complete this list 184 185 Exception handling 186 ================== 187 188 PSTL backends are expected to report errors (i.e. failure to allocate) by returning a disengaged `optional` from their 189 implementation. Exceptions shouldn't be used to report an internal failure-to-allocate, since all exceptions are turned 190 into a program termination at the front-end level. When a backend returns a disengaged `optional` to the frontend, the 191 frontend will turn that into a call to `std::__throw_bad_alloc();` to report the internal failure to the user. 192 */ 193 194 template <class _ExecutionPolicy> 195 struct __select_backend; 196 197 template <> 198 struct __select_backend<std::execution::sequenced_policy> { 199 using type = __cpu_backend_tag; 200 }; 201 202 # if _LIBCPP_STD_VER >= 20 203 template <> 204 struct __select_backend<std::execution::unsequenced_policy> { 205 using type = __cpu_backend_tag; 206 }; 207 # endif 208 209 # if defined(_LIBCPP_PSTL_CPU_BACKEND_SERIAL) || defined(_LIBCPP_PSTL_CPU_BACKEND_THREAD) || \ 210 defined(_LIBCPP_PSTL_CPU_BACKEND_LIBDISPATCH) 211 template <> 212 struct __select_backend<std::execution::parallel_policy> { 213 using type = __cpu_backend_tag; 214 }; 215 216 template <> 217 struct __select_backend<std::execution::parallel_unsequenced_policy> { 218 using type = __cpu_backend_tag; 219 }; 220 221 # else 222 223 // ...New vendors can add parallel backends here... 224 225 # error "Invalid choice of a PSTL parallel backend" 226 # endif 227 228 _LIBCPP_END_NAMESPACE_STD 229 230 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17 231 232 #endif // _LIBCPP___ALGORITHM_PSTL_BACKEND_H 233