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 void __pstl_for_each(_Backend, _ExecutionPolicy&&, _Iterator __first, _Iterator __last, _Func __f); 31 32 template <class _ExecutionPolicy, class _Iterator, class _Predicate> 33 _Iterator __pstl_find_if(_Backend, _Iterator __first, _Iterator __last, _Predicate __pred); 34 35 template <class _ExecutionPolicy, class _RandomAccessIterator, class _Comp> 36 void __pstl_stable_sort(_Backend, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp); 37 38 template <class _ExecutionPolicy, class _InIterator, class _OutIterator, class _UnaryOperation> 39 _OutIterator __pstl_transform(_InIterator __first, _InIterator __last, _OutIterator __result, _UnaryOperation __op); 40 41 template <class _ExecutionPolicy, class _InIterator1, class _InIterator2, class _OutIterator, class _BinaryOperation> 42 _OutIterator __pstl_transform(_InIterator1 __first1, 43 _InIterator1 __last1, 44 _InIterator2 __first2, 45 _OutIterator __result, 46 _BinaryOperation __op); 47 48 template <class _ExecutionPolicy, 49 class _Iterator1, 50 class _Iterator2, 51 class _Tp, 52 class _BinaryOperation1, 53 class _BinaryOperation2> 54 _Tp __pstl_transform_reduce(_Backend, 55 _Iterator1 __first1, 56 _Iterator1 __last1, 57 _Iterator2 __first2, 58 _Iterator2 __last2, 59 _Tp __init, 60 _BinaryOperation1 __reduce, 61 _BinaryOperation2 __transform); 62 63 template <class _ExecutionPolicy, class _Iterator, class _Tp, class _BinaryOperation, class _UnaryOperation> 64 _Tp __pstl_transform_reduce(_Backend, 65 _Iterator __first, 66 _Iterator __last, 67 _Tp __init, 68 _BinaryOperation __reduce, 69 _UnaryOperation __transform); 70 71 // TODO: Complete this list 72 73 The following functions are optional but can be provided. If provided, they are used by the corresponding 74 algorithms, otherwise they are implemented in terms of other algorithms. If none of the optional algorithms are 75 implemented, all the algorithms will eventually forward to the basis algorithms listed above: 76 77 template <class _ExecutionPolicy, class _Iterator, class _Size, class _Func> 78 void __pstl_for_each_n(_Backend, _Iterator __first, _Size __n, _Func __f); 79 80 template <class _ExecutionPolicy, class _Iterator, class _Predicate> 81 bool __pstl_any_of(_Backend, _Iterator __first, _iterator __last, _Predicate __pred); 82 83 template <class _ExecutionPolicy, class _Iterator, class _Predicate> 84 bool __pstl_all_of(_Backend, _Iterator __first, _iterator __last, _Predicate __pred); 85 86 template <class _ExecutionPolicy, class _Iterator, class _Predicate> 87 bool __pstl_none_of(_Backend, _Iterator __first, _iterator __last, _Predicate __pred); 88 89 template <class _ExecutionPolicy, class _Iterator, class _Tp> 90 _Iterator __pstl_find(_Backend, _Iterator __first, _Iterator __last, const _Tp& __value); 91 92 template <class _ExecutionPolicy, class _Iterator, class _Predicate> 93 _Iterator __pstl_find_if_not(_Backend, _Iterator __first, _Iterator __last, _Predicate __pred); 94 95 template <class _ExecutionPolicy, class _Iterator, class _Tp> 96 void __pstl_fill(_Backend, _Iterator __first, _Iterator __last, const _Tp& __value); 97 98 template <class _ExecutionPolicy, class _Iterator, class _SizeT, class _Tp> 99 void __pstl_fill_n(_Backend, _Iterator __first, _SizeT __n, const _Tp& __value); 100 101 template <class _ExecutionPolicy, class _Iterator, class _Generator> 102 void __pstl_generate(_Backend, _Iterator __first, _Iterator __last, _Generator __gen); 103 104 template <class _ExecutionPolicy, class _Iterator, class _Predicate> 105 void __pstl_is_partitioned(_Backend, _Iterator __first, _Iterator __last, _Predicate __pred); 106 107 template <class _ExecutionPolicy, class _Iterator, class _Size, class _Generator> 108 void __pstl_generator_n(_Backend, _Iterator __first, _Size __n, _Generator __gen); 109 110 template <class _ExecutionPolicy, class _terator1, class _Iterator2, class _OutIterator, class _Comp> 111 _OutIterator __pstl_merge(_Backend, 112 _Iterator1 __first1, 113 _Iterator1 __last1, 114 _Iterator2 __first2, 115 _Iterator2 __last2, 116 _OutIterator __result, 117 _Comp __comp); 118 119 template <class _ExecutionPolicy, class _Iterator, class _Tp, class _BinaryOperation> 120 _Tp __pstl_reduce(_Backend, _Iterator __first, _Iterator __last, _Tp __init, _BinaryOperation __op); 121 122 temlate <class _ExecutionPolicy, class _Iterator> 123 __iter_value_type<_Iterator> __pstl_reduce(_Backend, _Iterator __first, _Iterator __last); 124 125 template <class _ExecuitonPolicy, class _Iterator, class _Tp> 126 __iter_diff_t<_Iterator> __pstl_count(_Backend, _Iterator __first, _Iterator __last, const _Tp& __value); 127 128 template <class _ExecutionPolicy, class _Iterator, class _Predicate> 129 __iter_diff_t<_Iterator> __pstl_count_if(_Backend, _Iterator __first, _Iterator __last, _Predicate __pred); 130 131 template <class _ExecutionPolicy, class _Iterator, class _Tp> 132 void __pstl_replace(_Backend, _Iterator __first, _Iterator __last, const _Tp& __old_value, const _Tp& __new_value); 133 134 template <class _ExecutionPolicy, class _Iterator, class _Pred, class _Tp> 135 void __pstl_replace_if(_Backend, _Iterator __first, _Iterator __last, _Pred __pred, const _Tp& __new_value); 136 137 template <class _ExecutionPolicy, class _Iterator, class _OutIterator, class _Tp> 138 void __pstl_replace_copy(_Backend, 139 _Iterator __first, 140 _Iterator __last, 141 _OutIterator __result, 142 const _Tp& __old_value, 143 const _Tp& __new_value); 144 145 template <class _ExecutionPolicy, class _Iterator, class _OutIterator, class _Pred, class _Tp> 146 void __pstl_replace_copy_if(_Backend, 147 _Iterator __first, 148 _Iterator __last, 149 _OutIterator __result, 150 _Pred __pred, 151 const _Tp& __new_value); 152 153 template <class _ExecutionPolicy, class _Iterator, class _Comp> 154 void __pstl_sort(_Backend, _Iterator __first, _Iterator __last, _Comp __comp); 155 156 // TODO: Complete this list 157 158 */ 159 160 template <class _ExecutionPolicy> 161 struct __select_backend; 162 163 template <> 164 struct __select_backend<std::execution::sequenced_policy> { 165 using type = __cpu_backend_tag; 166 }; 167 168 # if _LIBCPP_STD_VER >= 20 169 template <> 170 struct __select_backend<std::execution::unsequenced_policy> { 171 using type = __cpu_backend_tag; 172 }; 173 # endif 174 175 # if defined(_LIBCPP_PSTL_CPU_BACKEND_SERIAL) || defined(_LIBCPP_PSTL_CPU_BACKEND_THREAD) || \ 176 defined(_LIBCPP_PSTL_CPU_BACKEND_LIBDISPATCH) 177 template <> 178 struct __select_backend<std::execution::parallel_policy> { 179 using type = __cpu_backend_tag; 180 }; 181 182 template <> 183 struct __select_backend<std::execution::parallel_unsequenced_policy> { 184 using type = __cpu_backend_tag; 185 }; 186 187 # else 188 189 // ...New vendors can add parallel backends here... 190 191 # error "Invalid choice of a PSTL parallel backend" 192 # endif 193 194 _LIBCPP_END_NAMESPACE_STD 195 196 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17 197 198 #endif // _LIBCPP___ALGORITHM_PSTL_BACKEND_H 199