From e957b86ca26f9a4e49acf625ed397e7dd05b0d66 Mon Sep 17 00:00:00 2001 From: Thomas Rodgers Date: Wed, 21 Oct 2020 06:11:28 -0700 Subject: [PATCH] libstdc++: Rebase include/pstl to current upstream From llvm-project/pstl @ 0b2e0e80d96 libstdc++-v3/ChangeLog: * include/pstl/algorithm_impl.h: Update file. * include/pstl/execution_impl.h: Likewise. * include/pstl/glue_algorithm_impl.h: Likewise. * include/pstl/glue_memory_impl.h: Likewise. * include/pstl/glue_numeric_impl.h: Likewise. * include/pstl/memory_impl.h: Likewise. * include/pstl/numeric_impl.h: Likewise. * include/pstl/parallel_backend.h: Likewise. * include/pstl/parallel_backend_serial.h: Likewise. * include/pstl/parallel_backend_tbb.h: Likewise. * include/pstl/parallel_backend_utils.h: Likewise. * include/pstl/pstl_config.h: Likewise. * include/pstl/unseq_backend_simd.h: Likewise. --- libstdc++-v3/include/pstl/algorithm_impl.h | 181 +++-- libstdc++-v3/include/pstl/execution_impl.h | 4 +- libstdc++-v3/include/pstl/glue_algorithm_impl.h | 543 ++++++------- libstdc++-v3/include/pstl/glue_memory_impl.h | 264 +++--- libstdc++-v3/include/pstl/glue_numeric_impl.h | 68 +- libstdc++-v3/include/pstl/memory_impl.h | 67 +- libstdc++-v3/include/pstl/numeric_impl.h | 8 +- libstdc++-v3/include/pstl/parallel_backend.h | 8 + .../include/pstl/parallel_backend_serial.h | 8 +- libstdc++-v3/include/pstl/parallel_backend_tbb.h | 903 +++++++++++++++++---- libstdc++-v3/include/pstl/parallel_backend_utils.h | 248 +++--- libstdc++-v3/include/pstl/pstl_config.h | 24 +- libstdc++-v3/include/pstl/unseq_backend_simd.h | 39 +- 13 files changed, 1586 insertions(+), 779 deletions(-) diff --git a/libstdc++-v3/include/pstl/algorithm_impl.h b/libstdc++-v3/include/pstl/algorithm_impl.h index 0a78b33..8e127b5 100644 --- a/libstdc++-v3/include/pstl/algorithm_impl.h +++ b/libstdc++-v3/include/pstl/algorithm_impl.h @@ -402,9 +402,7 @@ __brick_equal(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _ if (__last1 - __first1 != __last2 - __first2) return false; - return __unseq_backend::__simd_first(__first1, __last1 - __first1, __first2, - __internal::__not_pred<_BinaryPredicate>(__p)) - .first == __last1; + return __unseq_backend::__simd_first(__first1, __last1 - __first1, __first2, std::not_fn(__p)).first == __last1; } template (__p)) - .first == __last1; + return __unseq_backend::__simd_first(__first1, __last1 - __first1, __first2, std::not_fn(__p)).first == __last1; } template (__global_last - __first) < __count || __count < 1) { return __last; // According to the standard last shall be returned when count < 1 } - auto __n = __global_last - __first; auto __unary_pred = __equal_value_by_pred<_Tp, _BinaryPredicate>(__value, __pred); - while (__first != __last && (__global_last - __first >= __count)) + while (__first != __last && (static_cast<_Size>(__global_last - __first) >= __count)) { __first = __internal::__brick_find_if(__first, __last, __unary_pred, __is_vector); // check that all of elements in [first+1, first+count) equal to value - if (__first != __last && (__global_last - __first >= __count) && - !__internal::__brick_any_of(__first + 1, __first + __count, - __not_pred(__unary_pred), __is_vector)) + if (__first != __last && (static_cast<_Size>(__global_last - __first) >= __count) && + !__internal::__brick_any_of(__first + 1, __first + __count, std::not_fn(__unary_pred), __is_vector)) { return __first; } @@ -821,7 +816,7 @@ __pattern_search_n(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _Ra _Size __count, const _Tp& __value, _BinaryPredicate __pred, _IsVector __is_vector, /*is_parallel=*/std::true_type) noexcept { - if (__last - __first == __count) + if (static_cast<_Size>(__last - __first) == __count) { const bool __result = !__internal::__pattern_any_of( std::forward<_ExecutionPolicy>(__exec), __first, __last, @@ -903,6 +898,36 @@ __brick_move(_RandomAccessIterator __first, _RandomAccessIterator __last, _Outpu [](_RandomAccessIterator __first, _OutputIterator __result) { *__result = std::move(*__first); }); } +struct __brick_move_destroy +{ + template + _OutputIterator + operator()(_Iterator __first, _Iterator __last, _OutputIterator __result, /*vec*/ std::true_type) const + { + using _IteratorValueType = typename std::iterator_traits<_Iterator>::value_type; + + return __unseq_backend::__simd_assign(__first, __last - __first, __result, + [](_Iterator __first, _OutputIterator __result) { + *__result = std::move(*__first); + (*__first).~_IteratorValueType(); + }); + } + + template + _OutputIterator + operator()(_Iterator __first, _Iterator __last, _OutputIterator __result, /*vec*/ std::false_type) const + { + using _IteratorValueType = typename std::iterator_traits<_Iterator>::value_type; + + for (; __first != __last; ++__first, ++__result) + { + *__result = std::move(*__first); + (*__first).~_IteratorValueType(); + } + return __result; + } +}; + //------------------------------------------------------------------------ // swap_ranges //------------------------------------------------------------------------ @@ -1224,10 +1249,16 @@ __remove_elements(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardI [&__m](_DifferenceType __total) { __m = __total; }); // 3. Elements from result are moved to [first, last) - __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __result, __result + __m, - [__result, __first, __is_vector](_Tp* __i, _Tp* __j) { - __internal::__brick_move(__i, __j, __first + (__i - __result), __is_vector); - }); + __par_backend::__parallel_for( + std::forward<_ExecutionPolicy>(__exec), __result, __result + __m, + [__result, __first, __is_vector](_Tp* __i, _Tp* __j) { + __invoke_if_else( + std::is_trivial<_Tp>(), + [&]() { __brick_move(__i, __j, __first + (__i - __result), __is_vector); }, + [&]() { + __brick_move_destroy()(__i, __j, __first + (__i - __result), __is_vector); + }); + }); return __first + __m; }); } @@ -1576,8 +1607,8 @@ __pattern_rotate(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIt __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __result, __result + (__n - __m), [__first, __result, __is_vector](_Tp* __b, _Tp* __e) { - __internal::__brick_move(__b, __e, __first + (__b - __result), - __is_vector); + __brick_move_destroy()( + __b, __e, __first + (__b - __result), __is_vector); }); return __first + (__last - __middle); @@ -1602,7 +1633,7 @@ __pattern_rotate(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIt __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __result, __result + __m, [__n, __m, __first, __result, __is_vector](_Tp* __b, _Tp* __e) { - __internal::__brick_move( + __brick_move_destroy()( __b, __e, __first + ((__n - __m) + (__b - __result)), __is_vector); }); @@ -1764,7 +1795,7 @@ __pattern_is_partitioned(_ExecutionPolicy&& __exec, _ForwardIterator __first, _F { // find first element that don't satisfy pred _ForwardIterator __x = - __internal::__brick_find_if(__i + 1, __j, __not_pred<_UnaryPredicate>(__pred), __is_vector); + __internal::__brick_find_if(__i + 1, __j, std::not_fn(__pred), __is_vector); if (__x != __j) { // find first element after "x" that satisfy pred @@ -2087,8 +2118,7 @@ __pattern_sort(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _Random __internal::__except_handler([&]() { __par_backend::__parallel_stable_sort(std::forward<_ExecutionPolicy>(__exec), __first, __last, __comp, [](_RandomAccessIterator __first, _RandomAccessIterator __last, - _Compare __comp) { std::sort(__first, __last, __comp); }, - __last - __first); + _Compare __comp) { std::sort(__first, __last, __comp); }); }); } @@ -2135,6 +2165,9 @@ __pattern_partial_sort(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, _IsVector, /*is_parallel=*/std::true_type) { const auto __n = __middle - __first; + if (__n == 0) + return; + __internal::__except_handler([&]() { __par_backend::__parallel_stable_sort( std::forward<_ExecutionPolicy>(__exec), __first, __last, __comp, @@ -2223,8 +2256,13 @@ __pattern_partial_sort_copy(_ExecutionPolicy&& __exec, _ForwardIterator __first, // 3. Move elements from temporary __buffer to output __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __r, __r + __n2, [__r, __d_first, __is_vector](_T1* __i, _T1* __j) { - __internal::__brick_move(__i, __j, __d_first + (__i - __r), __is_vector); + __brick_move_destroy()( + __i, __j, __d_first + (__i - __r), __is_vector); }); + __par_backend::__parallel_for( + std::forward<_ExecutionPolicy>(__exec), __r + __n2, __r + __n1, + [__is_vector](_T1* __i, _T1* __j) { __brick_destroy(__i, __j, __is_vector); }); + return __d_first + __n2; } }); @@ -2244,7 +2282,7 @@ __brick_adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _Binary template _ForwardIterator __brick_adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred, - /* IsVector = */ std::false_type, bool __or_semantic) noexcept + /* IsVector = */ std::false_type, bool) noexcept { return std::adjacent_find(__first, __last, __pred); } @@ -2670,16 +2708,14 @@ __pattern_inplace_merge(_ExecutionPolicy&& __exec, _BidirectionalIterator __firs [__n, __move_values, __move_sequences](_BidirectionalIterator __f1, _BidirectionalIterator __l1, _BidirectionalIterator __f2, _BidirectionalIterator __l2, _Tp* __f3, _Compare __comp) { - auto __func = __par_backend::__serial_move_merge( - __n, __move_values, __move_sequences); - __func(__f1, __l1, __f2, __l2, __f3, __comp); + (__utils::__serial_move_merge(__n))(__f1, __l1, __f2, __l2, __f3, __comp, __move_values, __move_values, + __move_sequences, __move_sequences); return __f3 + (__l1 - __f1) + (__l2 - __f2); }); - - __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __r, __r + __n, - [__r, __first, __is_vector](_Tp* __i, _Tp* __j) { - __internal::__brick_move(__i, __j, __first + (__i - __r), __is_vector); - }); + __par_backend::__parallel_for( + std::forward<_ExecutionPolicy>(__exec), __r, __r + __n, [__r, __first, __is_vector](_Tp* __i, _Tp* __j) { + __brick_move_destroy()(__i, __j, __first + (__i - __r), __is_vector); + }); }); } @@ -2689,7 +2725,7 @@ __pattern_inplace_merge(_ExecutionPolicy&& __exec, _BidirectionalIterator __firs template bool -__pattern_includes(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, +__pattern_includes(_ExecutionPolicy&&, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _Compare __comp, _IsVector, /*is_parallel=*/std::false_type) noexcept { @@ -2699,7 +2735,7 @@ __pattern_includes(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _Forwa template bool __pattern_includes(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, _Compare __comp, _IsVector __is_vector, + _ForwardIterator2 __first2, _ForwardIterator2 __last2, _Compare __comp, _IsVector, /*is_parallel=*/std::true_type) { if (__first2 >= __last2) @@ -2761,7 +2797,7 @@ __parallel_set_op(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _Forwar _SizeFunction __size_func, _SetOP __set_op, _IsVector __is_vector) { typedef typename std::iterator_traits<_ForwardIterator1>::difference_type _DifferenceType; - typedef typename std::iterator_traits<_OutputIterator>::value_type _T; + typedef typename std::iterator_traits<_OutputIterator>::value_type _Tp; struct _SetRange { @@ -2776,7 +2812,7 @@ __parallel_set_op(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _Forwar const _DifferenceType __n1 = __last1 - __first1; const _DifferenceType __n2 = __last2 - __first2; - __par_backend::__buffer<_T> __buf(__size_func(__n1, __n2)); + __par_backend::__buffer<_Tp> __buf(__size_func(__n1, __n2)); return __internal::__except_handler([&__exec, __n1, __first1, __last1, __first2, __last2, __result, __is_vector, __comp, __size_func, __set_op, &__buf]() { @@ -2784,8 +2820,9 @@ __parallel_set_op(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _Forwar _DifferenceType __m{}; auto __scan = [=](_DifferenceType, _DifferenceType, const _SetRange& __s) { // Scan if (!__s.empty()) - __internal::__brick_move(__buffer + __s.__buf_pos, __buffer + (__s.__buf_pos + __s.__len), - __result + __s.__pos, __is_vector); + __brick_move_destroy()(__buffer + __s.__buf_pos, + __buffer + (__s.__buf_pos + __s.__len), __result + __s.__pos, + __is_vector); }; __par_backend::__parallel_strict_scan( std::forward<_ExecutionPolicy>(__exec), __n1, _SetRange{0, 0, 0}, //-1, 0}, @@ -2971,6 +3008,17 @@ __brick_set_union(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _Forwar return std::set_union(__first1, __last1, __first2, __last2, __result, __comp); } +template +struct __BrickCopyConstruct +{ + template + _OutputIterator + operator()(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result) + { + return __brick_uninitialized_copy(__first, __last, __result, _IsVector()); + } +}; + template _OutputIterator __brick_set_union(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, @@ -3007,12 +3055,14 @@ __pattern_set_union(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _Forw if (__n1 + __n2 <= __set_algo_cut_off) return std::set_union(__first1, __last1, __first2, __last2, __result, __comp); - typedef typename std::iterator_traits<_OutputIterator>::value_type _T; - return __internal::__parallel_set_union_op( + typedef typename std::iterator_traits<_OutputIterator>::value_type _Tp; + return __parallel_set_union_op( std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __result, __comp, [](_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, - _T* __result, - _Compare __comp) { return std::set_union(__first1, __last1, __first2, __last2, __result, __comp); }, + _Tp* __result, _Compare __comp) { + return __pstl::__utils::__set_union_construct(__first1, __last1, __first2, __last2, __result, __comp, + __BrickCopyConstruct<_IsVector>()); + }, __is_vector); } @@ -3056,7 +3106,7 @@ __pattern_set_intersection(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp, _IsVector __is_vector, /*is_parallel=*/std::true_type) { - typedef typename std::iterator_traits<_OutputIterator>::value_type _T; + typedef typename std::iterator_traits<_OutputIterator>::value_type _Tp; typedef typename std::iterator_traits<_ForwardIterator1>::difference_type _DifferenceType; const auto __n1 = __last1 - __first1; @@ -3086,8 +3136,9 @@ __pattern_set_intersection(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1 std::forward<_ExecutionPolicy>(__exec), __left_bound_seq_1, __last1, __first2, __last2, __result, __comp, [](_DifferenceType __n, _DifferenceType __m) { return std::min(__n, __m); }, [](_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, - _ForwardIterator2 __last2, _T* __result, _Compare __comp) { - return std::set_intersection(__first1, __last1, __first2, __last2, __result, __comp); + _ForwardIterator2 __last2, _Tp* __result, _Compare __comp) { + return __pstl::__utils::__set_intersection_construct(__first1, __last1, __first2, __last2, __result, + __comp); }, __is_vector); } @@ -3100,8 +3151,9 @@ __pattern_set_intersection(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1 std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __left_bound_seq_2, __last2, __result, __comp, [](_DifferenceType __n, _DifferenceType __m) { return std::min(__n, __m); }, [](_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, - _ForwardIterator2 __last2, _T* __result, _Compare __comp) { - return std::set_intersection(__first2, __last2, __first1, __last1, __result, __comp); + _ForwardIterator2 __last2, _Tp* __result, _Compare __comp) { + return __pstl::__utils::__set_intersection_construct(__first2, __last2, __first1, __last1, __result, + __comp); }, __is_vector); return __result; @@ -3151,7 +3203,7 @@ __pattern_set_difference(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp, _IsVector __is_vector, /*is_parallel=*/std::true_type) { - typedef typename std::iterator_traits<_OutputIterator>::value_type _T; + typedef typename std::iterator_traits<_OutputIterator>::value_type _Tp; typedef typename std::iterator_traits<_ForwardIterator1>::difference_type _DifferenceType; const auto __n1 = __last1 - __first1; @@ -3193,13 +3245,15 @@ __pattern_set_difference(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, std::true_type()); if (__n1 + __n2 > __set_algo_cut_off) - return __internal::__parallel_set_op( - std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __result, __comp, - [](_DifferenceType __n, _DifferenceType __m) { return __n; }, - [](_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, - _ForwardIterator2 __last2, _T* __result, - _Compare __comp) { return std::set_difference(__first1, __last1, __first2, __last2, __result, __comp); }, - __is_vector); + return __parallel_set_op(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __result, + __comp, [](_DifferenceType __n, _DifferenceType) { return __n; }, + [](_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, + _ForwardIterator2 __last2, _Tp* __result, _Compare __comp) { + return __pstl::__utils::__set_difference_construct( + __first1, __last1, __first2, __last2, __result, __comp, + __BrickCopyConstruct<_IsVector>()); + }, + __is_vector); // use serial algorithm return std::set_difference(__first1, __last1, __first2, __last2, __result, __comp); @@ -3254,12 +3308,13 @@ __pattern_set_symmetric_difference(_ExecutionPolicy&& __exec, _ForwardIterator1 if (__n1 + __n2 <= __set_algo_cut_off) return std::set_symmetric_difference(__first1, __last1, __first2, __last2, __result, __comp); - typedef typename std::iterator_traits<_OutputIterator>::value_type _T; + typedef typename std::iterator_traits<_OutputIterator>::value_type _Tp; return __internal::__parallel_set_union_op( std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __result, __comp, [](_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, - _T* __result, _Compare __comp) { - return std::set_symmetric_difference(__first1, __last1, __first2, __last2, __result, __comp); + _Tp* __result, _Compare __comp) { + return __pstl::__utils::__set_symmetric_difference_construct(__first1, __last1, __first2, __last2, __result, + __comp, __BrickCopyConstruct<_IsVector>()); }, __is_vector); } @@ -3443,14 +3498,14 @@ __pattern_minmax_element(_ExecutionPolicy&& __exec, _ForwardIterator __first, _F std::forward<_ExecutionPolicy>(__exec), __first + 1, __last, std::make_pair(__first, __first), [=](_ForwardIterator __begin, _ForwardIterator __end, _Result __init) -> _Result { const _Result __subresult = __internal::__brick_minmax_element(__begin, __end, __comp, __is_vector); - return std::make_pair(__internal::__cmp_iterators_by_values(__subresult.first, __init.first, __comp), - __internal::__cmp_iterators_by_values(__init.second, __subresult.second, - __not_pred<_Compare>(__comp))); + return std::make_pair( + __internal::__cmp_iterators_by_values(__subresult.first, __init.first, __comp), + __internal::__cmp_iterators_by_values(__init.second, __subresult.second, std::not_fn(__comp))); }, [=](_Result __p1, _Result __p2) -> _Result { return std::make_pair( __internal::__cmp_iterators_by_values(__p1.first, __p2.first, __comp), - __internal::__cmp_iterators_by_values(__p2.second, __p1.second, __not_pred<_Compare>(__comp))); + __internal::__cmp_iterators_by_values(__p2.second, __p1.second, std::not_fn(__comp))); }); }); } @@ -3487,7 +3542,7 @@ __brick_mismatch(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _Forward _ForwardIterator2 __last2, _Predicate __pred, /* __is_vector = */ std::true_type) noexcept { auto __n = std::min(__last1 - __first1, __last2 - __first2); - return __unseq_backend::__simd_first(__first1, __n, __first2, __not_pred<_Predicate>(__pred)); + return __unseq_backend::__simd_first(__first1, __n, __first2, std::not_fn(__pred)); } template diff --git a/libstdc++-v3/include/pstl/execution_impl.h b/libstdc++-v3/include/pstl/execution_impl.h index d53fd6f..53ff11f 100644 --- a/libstdc++-v3/include/pstl/execution_impl.h +++ b/libstdc++-v3/include/pstl/execution_impl.h @@ -28,7 +28,7 @@ template std::false_type __lazy_and(_Tp, std::false_type) { return std::false_type{}; -}; +} template inline _Tp @@ -41,7 +41,7 @@ template std::true_type __lazy_or(_Tp, std::true_type) { return std::true_type{}; -}; +} template inline _Tp diff --git a/libstdc++-v3/include/pstl/glue_algorithm_impl.h b/libstdc++-v3/include/pstl/glue_algorithm_impl.h index 379de40..d2e3052 100644 --- a/libstdc++-v3/include/pstl/glue_algorithm_impl.h +++ b/libstdc++-v3/include/pstl/glue_algorithm_impl.h @@ -26,11 +26,10 @@ template __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool> any_of(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) { - using namespace __pstl; - return __internal::__pattern_any_of( + return __pstl::__internal::__pattern_any_of( std::forward<_ExecutionPolicy>(__exec), __first, __last, __pred, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); } // [alg.all_of] @@ -39,8 +38,7 @@ template __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool> all_of(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Pred __pred) { - return !std::any_of(std::forward<_ExecutionPolicy>(__exec), __first, __last, - __pstl::__internal::__not_pred<_Pred>(__pred)); + return !std::any_of(std::forward<_ExecutionPolicy>(__exec), __first, __last, std::not_fn(__pred)); } // [alg.none_of] @@ -58,21 +56,20 @@ template __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void> for_each(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Function __f) { - using namespace __pstl; - __internal::__pattern_walk1(std::forward<_ExecutionPolicy>(__exec), __first, __last, __f, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); + __pstl::__internal::__pattern_walk1( + std::forward<_ExecutionPolicy>(__exec), __first, __last, __f, + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); } template __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator> for_each_n(_ExecutionPolicy&& __exec, _ForwardIterator __first, _Size __n, _Function __f) { - using namespace __pstl; - return __internal::__pattern_walk1_n( + return __pstl::__internal::__pattern_walk1_n( std::forward<_ExecutionPolicy>(__exec), __first, __n, __f, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); } // [alg.find] @@ -81,19 +78,17 @@ template __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator> find_if(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) { - using namespace __pstl; - return __internal::__pattern_find_if( + return __pstl::__internal::__pattern_find_if( std::forward<_ExecutionPolicy>(__exec), __first, __last, __pred, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); } template __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator> find_if_not(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) { - return std::find_if(std::forward<_ExecutionPolicy>(__exec), __first, __last, - __pstl::__internal::__not_pred<_Predicate>(__pred)); + return std::find_if(std::forward<_ExecutionPolicy>(__exec), __first, __last, std::not_fn(__pred)); } template @@ -110,11 +105,12 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardItera find_end(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __s_first, _ForwardIterator2 __s_last, _BinaryPredicate __pred) { - using namespace __pstl; - return __internal::__pattern_find_end( + return __pstl::__internal::__pattern_find_end( std::forward<_ExecutionPolicy>(__exec), __first, __last, __s_first, __s_last, __pred, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec)); } template @@ -123,7 +119,7 @@ find_end(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 _ForwardIterator2 __s_last) { return std::find_end(std::forward<_ExecutionPolicy>(__exec), __first, __last, __s_first, __s_last, - __pstl::__internal::__pstl_equal()); + std::equal_to<>()); } // [alg.find_first_of] @@ -132,11 +128,12 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardItera find_first_of(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __s_first, _ForwardIterator2 __s_last, _BinaryPredicate __pred) { - using namespace __pstl; - return __internal::__pattern_find_first_of( + return __pstl::__internal::__pattern_find_first_of( std::forward<_ExecutionPolicy>(__exec), __first, __last, __s_first, __s_last, __pred, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec)); } template @@ -145,7 +142,7 @@ find_first_of(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIter _ForwardIterator2 __s_first, _ForwardIterator2 __s_last) { return std::find_first_of(std::forward<_ExecutionPolicy>(__exec), __first, __last, __s_first, __s_last, - __pstl::__internal::__pstl_equal()); + std::equal_to<>()); } // [alg.adjacent_find] @@ -154,22 +151,22 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardItera adjacent_find(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last) { typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType; - using namespace __pstl; - return __internal::__pattern_adjacent_find( + return __pstl::__internal::__pattern_adjacent_find( std::forward<_ExecutionPolicy>(__exec), __first, __last, std::equal_to<_ValueType>(), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), /*first_semantic*/ false); + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), + /*first_semantic*/ false); } template __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator> adjacent_find(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred) { - using namespace __pstl; - return __internal::__pattern_adjacent_find( + return __pstl::__internal::__pattern_adjacent_find( std::forward<_ExecutionPolicy>(__exec), __first, __last, __pred, - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), /*first_semantic*/ false); + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), + /*first_semantic*/ false); } // [alg.count] @@ -183,12 +180,11 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, count(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) { typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType; - using namespace __pstl; - return __internal::__pattern_count( + return __pstl::__internal::__pattern_count( std::forward<_ExecutionPolicy>(__exec), __first, __last, [&__value](const _ValueType& __x) { return __value == __x; }, - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); } template @@ -196,11 +192,10 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, typename iterator_traits<_ForwardIterator>::difference_type> count_if(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) { - using namespace __pstl; - return __internal::__pattern_count( + return __pstl::__internal::__pattern_count( std::forward<_ExecutionPolicy>(__exec), __first, __last, __pred, - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); } // [alg.search] @@ -210,11 +205,12 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardItera search(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __s_first, _ForwardIterator2 __s_last, _BinaryPredicate __pred) { - using namespace __pstl; - return __internal::__pattern_search( + return __pstl::__internal::__pattern_search( std::forward<_ExecutionPolicy>(__exec), __first, __last, __s_first, __s_last, __pred, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec)); } template @@ -222,8 +218,7 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardItera search(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __s_first, _ForwardIterator2 __s_last) { - return std::search(std::forward<_ExecutionPolicy>(__exec), __first, __last, __s_first, __s_last, - __pstl::__internal::__pstl_equal()); + return std::search(std::forward<_ExecutionPolicy>(__exec), __first, __last, __s_first, __s_last, std::equal_to<>()); } template @@ -231,11 +226,10 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardItera search_n(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value, _BinaryPredicate __pred) { - using namespace __pstl; - return __internal::__pattern_search_n( + return __pstl::__internal::__pattern_search_n( std::forward<_ExecutionPolicy>(__exec), __first, __last, __count, __value, __pred, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); } template @@ -253,32 +247,34 @@ template copy(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __result) { - using namespace __pstl; const auto __is_vector = - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec); - return __internal::__pattern_walk2_brick( + return __pstl::__internal::__pattern_walk2_brick( std::forward<_ExecutionPolicy>(__exec), __first, __last, __result, [__is_vector](_ForwardIterator1 __begin, _ForwardIterator1 __end, _ForwardIterator2 __res) { - return __internal::__brick_copy(__begin, __end, __res, __is_vector); + return __pstl::__internal::__brick_copy(__begin, __end, __res, __is_vector); }, - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec)); + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec)); } template __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2> copy_n(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _Size __n, _ForwardIterator2 __result) { - using namespace __pstl; const auto __is_vector = - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec); - return __internal::__pattern_walk2_brick_n( + return __pstl::__internal::__pattern_walk2_brick_n( std::forward<_ExecutionPolicy>(__exec), __first, __n, __result, [__is_vector](_ForwardIterator1 __begin, _Size __sz, _ForwardIterator2 __res) { - return __internal::__brick_copy_n(__begin, __sz, __res, __is_vector); + return __pstl::__internal::__brick_copy_n(__begin, __sz, __res, __is_vector); }, - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec)); + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec)); } template @@ -286,11 +282,12 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardItera copy_if(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __result, _Predicate __pred) { - using namespace __pstl; - return __internal::__pattern_copy_if( + return __pstl::__internal::__pattern_copy_if( std::forward<_ExecutionPolicy>(__exec), __first, __last, __result, __pred, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec)); } // [alg.swap] @@ -300,17 +297,18 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardItera swap_ranges(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2) { - using namespace __pstl; typedef typename iterator_traits<_ForwardIterator1>::reference _ReferenceType1; typedef typename iterator_traits<_ForwardIterator2>::reference _ReferenceType2; - return __internal::__pattern_walk2( + return __pstl::__internal::__pattern_walk2( std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, [](_ReferenceType1 __x, _ReferenceType2 __y) { using std::swap; swap(__x, __y); }, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec)); } // [alg.transform] @@ -322,12 +320,13 @@ transform(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator { typedef typename iterator_traits<_ForwardIterator1>::reference _InputType; typedef typename iterator_traits<_ForwardIterator2>::reference _OutputType; - using namespace __pstl; - return __internal::__pattern_walk2( + return __pstl::__internal::__pattern_walk2( std::forward<_ExecutionPolicy>(__exec), __first, __last, __result, [__op](_InputType __x, _OutputType __y) mutable { __y = __op(__x); }, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec)); } template ::reference _Input1Type; typedef typename iterator_traits<_ForwardIterator2>::reference _Input2Type; typedef typename iterator_traits<_ForwardIterator>::reference _OutputType; - using namespace __pstl; - return __internal::__pattern_walk3( + return __pstl::__internal::__pattern_walk3( std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __result, [__op](_Input1Type x, _Input2Type y, _OutputType z) mutable { z = __op(x, y); }, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2, - _ForwardIterator>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2, - _ForwardIterator>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2, + _ForwardIterator>(__exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2, + _ForwardIterator>(__exec)); } // [alg.replace] @@ -356,17 +354,17 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void> replace_if(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _UnaryPredicate __pred, const _Tp& __new_value) { - using namespace __pstl; typedef typename iterator_traits<_ForwardIterator>::reference _ElementType; - __internal::__pattern_walk1(std::forward<_ExecutionPolicy>(__exec), __first, __last, - [&__pred, &__new_value](_ElementType __elem) { - if (__pred(__elem)) - { - __elem = __new_value; - } - }, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); + __pstl::__internal::__pattern_walk1( + std::forward<_ExecutionPolicy>(__exec), __first, __last, + [&__pred, &__new_value](_ElementType __elem) { + if (__pred(__elem)) + { + __elem = __new_value; + } + }, + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); } template @@ -385,12 +383,13 @@ replace_copy_if(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIt { typedef typename iterator_traits<_ForwardIterator1>::reference _InputType; typedef typename iterator_traits<_ForwardIterator2>::reference _OutputType; - using namespace __pstl; - return __internal::__pattern_walk2( + return __pstl::__internal::__pattern_walk2( std::forward<_ExecutionPolicy>(__exec), __first, __last, __result, [__pred, &__new_value](_InputType __x, _OutputType __y) mutable { __y = __pred(__x) ? __new_value : __x; }, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec)); } template @@ -408,10 +407,10 @@ template __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void> fill(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) { - using namespace __pstl; - __internal::__pattern_fill(std::forward<_ExecutionPolicy>(__exec), __first, __last, __value, - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); + __pstl::__internal::__pattern_fill( + std::forward<_ExecutionPolicy>(__exec), __first, __last, __value, + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); } template @@ -421,11 +420,10 @@ fill_n(_ExecutionPolicy&& __exec, _ForwardIterator __first, _Size __count, const if (__count <= 0) return __first; - using namespace __pstl; - return __internal::__pattern_fill_n( + return __pstl::__internal::__pattern_fill_n( std::forward<_ExecutionPolicy>(__exec), __first, __count, __value, - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); } // [alg.generate] @@ -433,11 +431,10 @@ template __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void> generate(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Generator __g) { - using namespace __pstl; - __internal::__pattern_generate( + __pstl::__internal::__pattern_generate( std::forward<_ExecutionPolicy>(__exec), __first, __last, __g, - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); } template @@ -447,11 +444,10 @@ generate_n(_ExecutionPolicy&& __exec, _ForwardIterator __first, _Size __count, _ if (__count <= 0) return __first; - using namespace __pstl; - return __internal::__pattern_generate_n( + return __pstl::__internal::__pattern_generate_n( std::forward<_ExecutionPolicy>(__exec), __first, __count, __g, - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); } // [alg.remove] @@ -461,8 +457,7 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardItera remove_copy_if(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __result, _Predicate __pred) { - return std::copy_if(std::forward<_ExecutionPolicy>(__exec), __first, __last, __result, - __pstl::__internal::__not_pred<_Predicate>(__pred)); + return std::copy_if(std::forward<_ExecutionPolicy>(__exec), __first, __last, __result, std::not_fn(__pred)); } template @@ -478,11 +473,10 @@ template __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator> remove_if(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _UnaryPredicate __pred) { - using namespace __pstl; - return __internal::__pattern_remove_if( + return __pstl::__internal::__pattern_remove_if( std::forward<_ExecutionPolicy>(__exec), __first, __last, __pred, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); } template @@ -499,18 +493,17 @@ template unique(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred) { - using namespace __pstl; - return __internal::__pattern_unique( + return __pstl::__internal::__pattern_unique( std::forward<_ExecutionPolicy>(__exec), __first, __last, __pred, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); } template __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator> unique(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last) { - return std::unique(std::forward<_ExecutionPolicy>(__exec), __first, __last, __pstl::__internal::__pstl_equal()); + return std::unique(std::forward<_ExecutionPolicy>(__exec), __first, __last, std::equal_to<>()); } template @@ -518,18 +511,19 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardItera unique_copy(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __result, _BinaryPredicate __pred) { - using namespace __pstl; - return __internal::__pattern_unique_copy( + return __pstl::__internal::__pattern_unique_copy( std::forward<_ExecutionPolicy>(__exec), __first, __last, __result, __pred, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec)); } template __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2> unique_copy(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __result) { - return std::unique_copy(__exec, __first, __last, __result, __pstl::__internal::__pstl_equal()); + return std::unique_copy(__exec, __first, __last, __result, std::equal_to<>()); } // [alg.reverse] @@ -538,11 +532,10 @@ template __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void> reverse(_ExecutionPolicy&& __exec, _BidirectionalIterator __first, _BidirectionalIterator __last) { - using namespace __pstl; - __internal::__pattern_reverse( + __pstl::__internal::__pattern_reverse( std::forward<_ExecutionPolicy>(__exec), __first, __last, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _BidirectionalIterator>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _BidirectionalIterator>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _BidirectionalIterator>(__exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _BidirectionalIterator>(__exec)); } template @@ -550,11 +543,12 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardItera reverse_copy(_ExecutionPolicy&& __exec, _BidirectionalIterator __first, _BidirectionalIterator __last, _ForwardIterator __d_first) { - using namespace __pstl; - return __internal::__pattern_reverse_copy( + return __pstl::__internal::__pattern_reverse_copy( std::forward<_ExecutionPolicy>(__exec), __first, __last, __d_first, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _BidirectionalIterator, _ForwardIterator>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _BidirectionalIterator, _ForwardIterator>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _BidirectionalIterator, _ForwardIterator>( + __exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _BidirectionalIterator, _ForwardIterator>( + __exec)); } // [alg.rotate] @@ -563,11 +557,10 @@ template __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator> rotate(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last) { - using namespace __pstl; - return __internal::__pattern_rotate( + return __pstl::__internal::__pattern_rotate( std::forward<_ExecutionPolicy>(__exec), __first, __middle, __last, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); } template @@ -575,11 +568,12 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardItera rotate_copy(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __middle, _ForwardIterator1 __last, _ForwardIterator2 __result) { - using namespace __pstl; - return __internal::__pattern_rotate_copy( + return __pstl::__internal::__pattern_rotate_copy( std::forward<_ExecutionPolicy>(__exec), __first, __middle, __last, __result, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec)); } // [alg.partitions] @@ -588,22 +582,20 @@ template __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool> is_partitioned(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _UnaryPredicate __pred) { - using namespace __pstl; - return __internal::__pattern_is_partitioned( + return __pstl::__internal::__pattern_is_partitioned( std::forward<_ExecutionPolicy>(__exec), __first, __last, __pred, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); } template __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator> partition(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _UnaryPredicate __pred) { - using namespace __pstl; - return __internal::__pattern_partition( + return __pstl::__internal::__pattern_partition( std::forward<_ExecutionPolicy>(__exec), __first, __last, __pred, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); } template @@ -611,11 +603,10 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Bidirectiona stable_partition(_ExecutionPolicy&& __exec, _BidirectionalIterator __first, _BidirectionalIterator __last, _UnaryPredicate __pred) { - using namespace __pstl; - return __internal::__pattern_stable_partition( + return __pstl::__internal::__pattern_stable_partition( std::forward<_ExecutionPolicy>(__exec), __first, __last, __pred, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _BidirectionalIterator>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _BidirectionalIterator>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _BidirectionalIterator>(__exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _BidirectionalIterator>(__exec)); } template (__exec), __first, __last, __out_true, __out_false, __pred, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator, _ForwardIterator1, - _ForwardIterator2>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator, _ForwardIterator1, - _ForwardIterator2>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator, _ForwardIterator1, + _ForwardIterator2>(__exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator, _ForwardIterator1, + _ForwardIterator2>(__exec)); } // [alg.sort] @@ -640,11 +630,10 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void> sort(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { typedef typename iterator_traits<_RandomAccessIterator>::value_type _InputType; - using namespace __pstl; - return __internal::__pattern_sort( + return __pstl::__internal::__pattern_sort( std::forward<_ExecutionPolicy>(__exec), __first, __last, __comp, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _RandomAccessIterator>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _RandomAccessIterator>(__exec), + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _RandomAccessIterator>(__exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _RandomAccessIterator>(__exec), typename std::is_move_constructible<_InputType>::type()); } @@ -662,11 +651,10 @@ template __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void> stable_sort(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { - using namespace __pstl; - return __internal::__pattern_stable_sort( + return __pstl::__internal::__pattern_stable_sort( std::forward<_ExecutionPolicy>(__exec), __first, __last, __comp, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _RandomAccessIterator>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _RandomAccessIterator>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _RandomAccessIterator>(__exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _RandomAccessIterator>(__exec)); } template @@ -674,7 +662,7 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void> stable_sort(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last) { typedef typename std::iterator_traits<_RandomAccessIterator>::value_type _InputType; - std::stable_sort(std::forward<_ExecutionPolicy>(__exec), __first, __last, std::less<_InputType>()); + std::stable_sort(__exec, __first, __last, std::less<_InputType>()); } // [mismatch] @@ -684,11 +672,12 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, std::pair<_Fo mismatch(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred) { - using namespace __pstl; - return __internal::__pattern_mismatch( + return __pstl::__internal::__pattern_mismatch( std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __pred, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec)); } template @@ -696,8 +685,8 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, std::pair<_Fo mismatch(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _BinaryPredicate __pred) { - return std::mismatch(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, - std::next(__first2, std::distance(__first1, __last1)), __pred); + return std::mismatch(__exec, __first1, __last1, __first2, std::next(__first2, std::distance(__first1, __last1)), + __pred); } template @@ -706,7 +695,7 @@ mismatch(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator _ForwardIterator2 __last2) { return std::mismatch(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, - __pstl::__internal::__pstl_equal()); + std::equal_to<>()); } template @@ -725,19 +714,17 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool> equal(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _BinaryPredicate __p) { - using namespace __pstl; - return __internal::__pattern_equal( + return __pstl::__internal::__pattern_equal( std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __p, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1>(__exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1>(__exec)); } template __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool> equal(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2) { - return std::equal(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, - __pstl::__internal::__pstl_equal()); + return std::equal(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, std::equal_to<>()); } template @@ -745,11 +732,10 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool> equal(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __p) { - using namespace __pstl; - return __internal::__pattern_equal( + return __pstl::__internal::__pattern_equal( std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __p, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1>(__exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1>(__exec)); } template @@ -757,8 +743,7 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool> equal(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) { - return std::equal(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, - __pstl::__internal::__pstl_equal()); + return equal(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, std::equal_to<>()); } // [alg.move] @@ -766,16 +751,17 @@ template move(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __d_first) { - using namespace __pstl; const auto __is_vector = - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec); - return __internal::__pattern_walk2_brick( + return __pstl::__internal::__pattern_walk2_brick( std::forward<_ExecutionPolicy>(__exec), __first, __last, __d_first, [__is_vector](_ForwardIterator1 __begin, _ForwardIterator1 __end, _ForwardIterator2 __res) { - return __internal::__brick_move(__begin, __end, __res, __is_vector); + return __pstl::__internal::__brick_move(__begin, __end, __res, __is_vector); }, - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec)); + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec)); } // [partial.sort] @@ -785,11 +771,10 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void> partial_sort(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp) { - using namespace __pstl; - __internal::__pattern_partial_sort( + __pstl::__internal::__pattern_partial_sort( std::forward<_ExecutionPolicy>(__exec), __first, __middle, __last, __comp, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _RandomAccessIterator>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _RandomAccessIterator>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _RandomAccessIterator>(__exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _RandomAccessIterator>(__exec)); } template @@ -798,7 +783,7 @@ partial_sort(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAc _RandomAccessIterator __last) { typedef typename iterator_traits<_RandomAccessIterator>::value_type _InputType; - std::partial_sort(std::forward<_ExecutionPolicy>(__exec), __first, __middle, __last, std::less<_InputType>()); + std::partial_sort(__exec, __first, __middle, __last, std::less<_InputType>()); } // [partial.sort.copy] @@ -808,11 +793,12 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _RandomAccess partial_sort_copy(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _RandomAccessIterator __d_first, _RandomAccessIterator __d_last, _Compare __comp) { - using namespace __pstl; - return __internal::__pattern_partial_sort_copy( + return __pstl::__internal::__pattern_partial_sort_copy( std::forward<_ExecutionPolicy>(__exec), __first, __last, __d_first, __d_last, __comp, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator, _RandomAccessIterator>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator, _RandomAccessIterator>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator, _RandomAccessIterator>( + __exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator, _RandomAccessIterator>( + __exec)); } template @@ -821,7 +807,7 @@ partial_sort_copy(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardI _RandomAccessIterator __d_first, _RandomAccessIterator __d_last) { return std::partial_sort_copy(std::forward<_ExecutionPolicy>(__exec), __first, __last, __d_first, __d_last, - __pstl::__internal::__pstl_less()); + std::less<>()); } // [is.sorted] @@ -829,11 +815,11 @@ template __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator> is_sorted_until(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Compare __comp) { - using namespace __pstl; - const _ForwardIterator __res = __internal::__pattern_adjacent_find( + const _ForwardIterator __res = __pstl::__internal::__pattern_adjacent_find( std::forward<_ExecutionPolicy>(__exec), __first, __last, __pstl::__internal::__reorder_pred<_Compare>(__comp), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), /*first_semantic*/ false); + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), + /*first_semantic*/ false); return __res == __last ? __last : std::next(__res); } @@ -849,11 +835,11 @@ template __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool> is_sorted(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Compare __comp) { - using namespace __pstl; - return __internal::__pattern_adjacent_find( - std::forward<_ExecutionPolicy>(__exec), __first, __last, __internal::__reorder_pred<_Compare>(__comp), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), + return __pstl::__internal::__pattern_adjacent_find( + std::forward<_ExecutionPolicy>(__exec), __first, __last, + __pstl::__internal::__reorder_pred<_Compare>(__comp), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), /*or_semantic*/ true) == __last; } @@ -872,13 +858,12 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardItera merge(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _ForwardIterator __d_first, _Compare __comp) { - using namespace __pstl; - return __internal::__pattern_merge( + return __pstl::__internal::__pattern_merge( std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __d_first, __comp, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2, - _ForwardIterator>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2, - _ForwardIterator>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2, + _ForwardIterator>(__exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2, + _ForwardIterator>(__exec)); } template @@ -887,7 +872,7 @@ merge(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 _ _ForwardIterator2 __last2, _ForwardIterator __d_first) { return std::merge(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __d_first, - __pstl::__internal::__pstl_less()); + std::less<>()); } template @@ -895,11 +880,10 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void> inplace_merge(_ExecutionPolicy&& __exec, _BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Compare __comp) { - using namespace __pstl; - __internal::__pattern_inplace_merge( + __pstl::__internal::__pattern_inplace_merge( std::forward<_ExecutionPolicy>(__exec), __first, __middle, __last, __comp, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _BidirectionalIterator>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _BidirectionalIterator>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _BidirectionalIterator>(__exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _BidirectionalIterator>(__exec)); } template @@ -908,7 +892,7 @@ inplace_merge(_ExecutionPolicy&& __exec, _BidirectionalIterator __first, _Bidire _BidirectionalIterator __last) { typedef typename std::iterator_traits<_BidirectionalIterator>::value_type _InputType; - std::inplace_merge(std::forward<_ExecutionPolicy>(__exec), __first, __middle, __last, std::less<_InputType>()); + std::inplace_merge(__exec, __first, __middle, __last, std::less<_InputType>()); } // [includes] @@ -918,11 +902,12 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool> includes(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _Compare __comp) { - using namespace __pstl; - return __internal::__pattern_includes( + return __pstl::__internal::__pattern_includes( std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __comp, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec)); } template @@ -930,8 +915,7 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool> includes(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) { - return std::includes(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, - __pstl::__internal::__pstl_less()); + return std::includes(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, std::less<>()); } // [set.union] @@ -942,13 +926,12 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardItera set_union(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _ForwardIterator __result, _Compare __comp) { - using namespace __pstl; - return __internal::__pattern_set_union( + return __pstl::__internal::__pattern_set_union( std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __result, __comp, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2, - _ForwardIterator>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2, - _ForwardIterator>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2, + _ForwardIterator>(__exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2, + _ForwardIterator>(__exec)); } template @@ -957,7 +940,7 @@ set_union(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterato _ForwardIterator2 __last2, _ForwardIterator __result) { return std::set_union(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __result, - __pstl::__internal::__pstl_less()); + std::less<>()); } // [set.intersection] @@ -968,13 +951,12 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardItera set_intersection(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _ForwardIterator __result, _Compare __comp) { - using namespace __pstl; - return __internal::__pattern_set_intersection( + return __pstl::__internal::__pattern_set_intersection( std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __result, __comp, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2, - _ForwardIterator>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2, - _ForwardIterator>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2, + _ForwardIterator>(__exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2, + _ForwardIterator>(__exec)); } template @@ -983,7 +965,7 @@ set_intersection(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _Forward _ForwardIterator2 __first2, _ForwardIterator2 __last2, _ForwardIterator __result) { return std::set_intersection(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __result, - __pstl::__internal::__pstl_less()); + std::less<>()); } // [set.difference] @@ -994,13 +976,12 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardItera set_difference(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _ForwardIterator __result, _Compare __comp) { - using namespace __pstl; - return __internal::__pattern_set_difference( + return __pstl::__internal::__pattern_set_difference( std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __result, __comp, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2, - _ForwardIterator>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2, - _ForwardIterator>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2, + _ForwardIterator>(__exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2, + _ForwardIterator>(__exec)); } template @@ -1009,7 +990,7 @@ set_difference(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIt _ForwardIterator2 __first2, _ForwardIterator2 __last2, _ForwardIterator __result) { return std::set_difference(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __result, - __pstl::__internal::__pstl_less()); + std::less<>()); } // [set.symmetric.difference] @@ -1021,13 +1002,12 @@ set_symmetric_difference(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _ForwardIterator __result, _Compare __comp) { - using namespace __pstl; - return __internal::__pattern_set_symmetric_difference( + return __pstl::__internal::__pattern_set_symmetric_difference( std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __result, __comp, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2, - _ForwardIterator>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2, - _ForwardIterator>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2, + _ForwardIterator>(__exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2, + _ForwardIterator>(__exec)); } template @@ -1036,7 +1016,7 @@ set_symmetric_difference(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _ForwardIterator __result) { return std::set_symmetric_difference(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, - __result, __pstl::__internal::__pstl_less()); + __result, std::less<>()); } // [is.heap] @@ -1044,11 +1024,10 @@ template __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _RandomAccessIterator> is_heap_until(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { - using namespace __pstl; - return __internal::__pattern_is_heap_until( + return __pstl::__internal::__pattern_is_heap_until( std::forward<_ExecutionPolicy>(__exec), __first, __last, __comp, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _RandomAccessIterator>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _RandomAccessIterator>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _RandomAccessIterator>(__exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _RandomAccessIterator>(__exec)); } template @@ -1080,11 +1059,10 @@ template __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator> min_element(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Compare __comp) { - using namespace __pstl; - return __internal::__pattern_min_element( + return __pstl::__internal::__pattern_min_element( std::forward<_ExecutionPolicy>(__exec), __first, __last, __comp, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); } template @@ -1116,11 +1094,10 @@ template __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, std::pair<_ForwardIterator, _ForwardIterator>> minmax_element(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Compare __comp) { - using namespace __pstl; - return __internal::__pattern_minmax_element( + return __pstl::__internal::__pattern_minmax_element( std::forward<_ExecutionPolicy>(__exec), __first, __last, __comp, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); } template @@ -1138,11 +1115,10 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void> nth_element(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp) { - using namespace __pstl; - __internal::__pattern_nth_element( + __pstl::__internal::__pattern_nth_element( std::forward<_ExecutionPolicy>(__exec), __first, __nth, __last, __comp, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _RandomAccessIterator>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _RandomAccessIterator>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _RandomAccessIterator>(__exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _RandomAccessIterator>(__exec)); } template @@ -1161,11 +1137,12 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool> lexicographical_compare(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _Compare __comp) { - using namespace __pstl; - return __internal::__pattern_lexicographical_compare( + return __pstl::__internal::__pattern_lexicographical_compare( std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __comp, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec)); } template @@ -1174,7 +1151,7 @@ lexicographical_compare(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ _ForwardIterator2 __first2, _ForwardIterator2 __last2) { return std::lexicographical_compare(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, - __pstl::__internal::__pstl_less()); + std::less<>()); } } // namespace std diff --git a/libstdc++-v3/include/pstl/glue_memory_impl.h b/libstdc++-v3/include/pstl/glue_memory_impl.h index 52ae75f..ea462e9 100644 --- a/libstdc++-v3/include/pstl/glue_memory_impl.h +++ b/libstdc++-v3/include/pstl/glue_memory_impl.h @@ -26,29 +26,29 @@ uninitialized_copy(_ExecutionPolicy&& __exec, _InputIterator __first, _InputIter typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType2; typedef typename iterator_traits<_InputIterator>::reference _ReferenceType1; typedef typename iterator_traits<_ForwardIterator>::reference _ReferenceType2; - using namespace __pstl; const auto __is_parallel = - __internal::__is_parallelization_preferred<_ExecutionPolicy, _InputIterator, _ForwardIterator>(__exec); + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _InputIterator, _ForwardIterator>(__exec); const auto __is_vector = - __internal::__is_vectorization_preferred<_ExecutionPolicy, _InputIterator, _ForwardIterator>(__exec); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _InputIterator, _ForwardIterator>(__exec); - return __internal::__invoke_if_else( + return __pstl::__internal::__invoke_if_else( std::integral_constant < bool, std::is_trivial<_ValueType1>::value&& std::is_trivial<_ValueType2>::value > (), [&]() { - return __internal::__pattern_walk2_brick( + return __pstl::__internal::__pattern_walk2_brick( std::forward<_ExecutionPolicy>(__exec), __first, __last, __result, [__is_vector](_InputIterator __begin, _InputIterator __end, _ForwardIterator __res) { - return __internal::__brick_copy(__begin, __end, __res, __is_vector); + return __pstl::__internal::__brick_copy(__begin, __end, __res, __is_vector); }, __is_parallel); }, [&]() { - return __internal::__pattern_walk2(std::forward<_ExecutionPolicy>(__exec), __first, __last, __result, - [](_ReferenceType1 __val1, _ReferenceType2 __val2) { - ::new (std::addressof(__val2)) _ValueType2(__val1); - }, - __is_vector, __is_parallel); + return __pstl::__internal::__pattern_walk2(std::forward<_ExecutionPolicy>(__exec), __first, __last, + __result, + [](_ReferenceType1 __val1, _ReferenceType2 __val2) { + ::new (std::addressof(__val2)) _ValueType2(__val1); + }, + __is_vector, __is_parallel); }); } @@ -60,29 +60,28 @@ uninitialized_copy_n(_ExecutionPolicy&& __exec, _InputIterator __first, _Size __ typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType2; typedef typename iterator_traits<_InputIterator>::reference _ReferenceType1; typedef typename iterator_traits<_ForwardIterator>::reference _ReferenceType2; - using namespace __pstl; const auto __is_parallel = - __internal::__is_parallelization_preferred<_ExecutionPolicy, _InputIterator, _ForwardIterator>(__exec); + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _InputIterator, _ForwardIterator>(__exec); const auto __is_vector = - __internal::__is_vectorization_preferred<_ExecutionPolicy, _InputIterator, _ForwardIterator>(__exec); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _InputIterator, _ForwardIterator>(__exec); - return __internal::__invoke_if_else( + return __pstl::__internal::__invoke_if_else( std::integral_constant < bool, std::is_trivial<_ValueType1>::value&& std::is_trivial<_ValueType2>::value > (), [&]() { - return __internal::__pattern_walk2_brick_n( + return __pstl::__internal::__pattern_walk2_brick_n( std::forward<_ExecutionPolicy>(__exec), __first, __n, __result, [__is_vector](_InputIterator __begin, _Size __sz, _ForwardIterator __res) { - return __internal::__brick_copy_n(__begin, __sz, __res, __is_vector); + return __pstl::__internal::__brick_copy_n(__begin, __sz, __res, __is_vector); }, __is_parallel); }, [&]() { - return __internal::__pattern_walk2_n(std::forward<_ExecutionPolicy>(__exec), __first, __n, __result, - [](_ReferenceType1 __val1, _ReferenceType2 __val2) { - ::new (std::addressof(__val2)) _ValueType2(__val1); - }, - __is_vector, __is_parallel); + return __pstl::__internal::__pattern_walk2_n(std::forward<_ExecutionPolicy>(__exec), __first, __n, __result, + [](_ReferenceType1 __val1, _ReferenceType2 __val2) { + ::new (std::addressof(__val2)) _ValueType2(__val1); + }, + __is_vector, __is_parallel); }); } @@ -96,29 +95,29 @@ uninitialized_move(_ExecutionPolicy&& __exec, _InputIterator __first, _InputIter typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType2; typedef typename iterator_traits<_InputIterator>::reference _ReferenceType1; typedef typename iterator_traits<_ForwardIterator>::reference _ReferenceType2; - using namespace __pstl; const auto __is_parallel = - __internal::__is_parallelization_preferred<_ExecutionPolicy, _InputIterator, _ForwardIterator>(__exec); + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _InputIterator, _ForwardIterator>(__exec); const auto __is_vector = - __internal::__is_vectorization_preferred<_ExecutionPolicy, _InputIterator, _ForwardIterator>(__exec); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _InputIterator, _ForwardIterator>(__exec); - return __internal::__invoke_if_else( + return __pstl::__internal::__invoke_if_else( std::integral_constant < bool, std::is_trivial<_ValueType1>::value&& std::is_trivial<_ValueType2>::value > (), [&]() { - return __internal::__pattern_walk2_brick( + return __pstl::__internal::__pattern_walk2_brick( std::forward<_ExecutionPolicy>(__exec), __first, __last, __result, [__is_vector](_InputIterator __begin, _InputIterator __end, _ForwardIterator __res) { - return __internal::__brick_copy(__begin, __end, __res, __is_vector); + return __pstl::__internal::__brick_copy(__begin, __end, __res, __is_vector); }, __is_parallel); }, [&]() { - return __internal::__pattern_walk2(std::forward<_ExecutionPolicy>(__exec), __first, __last, __result, - [](_ReferenceType1 __val1, _ReferenceType2 __val2) { - ::new (std::addressof(__val2)) _ValueType2(std::move(__val1)); - }, - __is_vector, __is_parallel); + return __pstl::__internal::__pattern_walk2( + std::forward<_ExecutionPolicy>(__exec), __first, __last, __result, + [](_ReferenceType1 __val1, _ReferenceType2 __val2) { + ::new (std::addressof(__val2)) _ValueType2(std::move(__val1)); + }, + __is_vector, __is_parallel); }); } @@ -130,29 +129,29 @@ uninitialized_move_n(_ExecutionPolicy&& __exec, _InputIterator __first, _Size __ typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType2; typedef typename iterator_traits<_InputIterator>::reference _ReferenceType1; typedef typename iterator_traits<_ForwardIterator>::reference _ReferenceType2; - using namespace __pstl; const auto __is_parallel = - __internal::__is_parallelization_preferred<_ExecutionPolicy, _InputIterator, _ForwardIterator>(__exec); + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _InputIterator, _ForwardIterator>(__exec); const auto __is_vector = - __internal::__is_vectorization_preferred<_ExecutionPolicy, _InputIterator, _ForwardIterator>(__exec); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _InputIterator, _ForwardIterator>(__exec); - return __internal::__invoke_if_else( + return __pstl::__internal::__invoke_if_else( std::integral_constant < bool, std::is_trivial<_ValueType1>::value&& std::is_trivial<_ValueType2>::value > (), [&]() { - return __internal::__pattern_walk2_brick_n( + return __pstl::__internal::__pattern_walk2_brick_n( std::forward<_ExecutionPolicy>(__exec), __first, __n, __result, [__is_vector](_InputIterator __begin, _Size __sz, _ForwardIterator __res) { - return __internal::__brick_copy_n(__begin, __sz, __res, __is_vector); + return __pstl::__internal::__brick_copy_n(__begin, __sz, __res, __is_vector); }, __is_parallel); }, [&]() { - return __internal::__pattern_walk2_n(std::forward<_ExecutionPolicy>(__exec), __first, __n, __result, - [](_ReferenceType1 __val1, _ReferenceType2 __val2) { - ::new (std::addressof(__val2)) _ValueType2(std::move(__val1)); - }, - __is_vector, __is_parallel); + return __pstl::__internal::__pattern_walk2_n(std::forward<_ExecutionPolicy>(__exec), __first, __n, __result, + [](_ReferenceType1 __val1, _ReferenceType2 __val2) { + ::new (std::addressof(__val2)) + _ValueType2(std::move(__val1)); + }, + __is_vector, __is_parallel); }); } @@ -164,28 +163,28 @@ uninitialized_fill(_ExecutionPolicy&& __exec, _ForwardIterator __first, _Forward { typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType; typedef typename iterator_traits<_ForwardIterator>::reference _ReferenceType; - using namespace __pstl; - - const auto __is_parallel = __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); - const auto __is_vector = __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); - - __internal::__invoke_if_else(std::is_arithmetic<_ValueType>(), - [&]() { - __internal::__pattern_walk_brick( - std::forward<_ExecutionPolicy>(__exec), __first, __last, - [&__value, &__is_vector](_ForwardIterator __begin, _ForwardIterator __end) { - __internal::__brick_fill(__begin, __end, _ValueType(__value), __is_vector); - }, - __is_parallel); - }, - [&]() { - __internal::__pattern_walk1(std::forward<_ExecutionPolicy>(__exec), __first, - __last, - [&__value](_ReferenceType __val) { - ::new (std::addressof(__val)) _ValueType(__value); - }, - __is_vector, __is_parallel); - }); + + const auto __is_parallel = + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); + const auto __is_vector = + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); + + __pstl::__internal::__invoke_if_else( + std::is_arithmetic<_ValueType>(), + [&]() { + __pstl::__internal::__pattern_walk_brick( + std::forward<_ExecutionPolicy>(__exec), __first, __last, + [&__value, &__is_vector](_ForwardIterator __begin, _ForwardIterator __end) { + __pstl::__internal::__brick_fill(__begin, __end, _ValueType(__value), __is_vector); + }, + __is_parallel); + }, + [&]() { + __pstl::__internal::__pattern_walk1( + std::forward<_ExecutionPolicy>(__exec), __first, __last, + [&__value](_ReferenceType __val) { ::new (std::addressof(__val)) _ValueType(__value); }, __is_vector, + __is_parallel); + }); } template @@ -194,23 +193,24 @@ uninitialized_fill_n(_ExecutionPolicy&& __exec, _ForwardIterator __first, _Size { typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType; typedef typename iterator_traits<_ForwardIterator>::reference _ReferenceType; - using namespace __pstl; - const auto __is_parallel = __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); - const auto __is_vector = __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); + const auto __is_parallel = + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); + const auto __is_vector = + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); - return __internal::__invoke_if_else( + return __pstl::__internal::__invoke_if_else( std::is_arithmetic<_ValueType>(), [&]() { - return __internal::__pattern_walk_brick_n( + return __pstl::__internal::__pattern_walk_brick_n( std::forward<_ExecutionPolicy>(__exec), __first, __n, [&__value, &__is_vector](_ForwardIterator __begin, _Size __count) { - return __internal::__brick_fill_n(__begin, __count, _ValueType(__value), __is_vector); + return __pstl::__internal::__brick_fill_n(__begin, __count, _ValueType(__value), __is_vector); }, __is_parallel); }, [&]() { - return __internal::__pattern_walk1_n( + return __pstl::__internal::__pattern_walk1_n( std::forward<_ExecutionPolicy>(__exec), __first, __n, [&__value](_ReferenceType __val) { ::new (std::addressof(__val)) _ValueType(__value); }, __is_vector, __is_parallel); @@ -225,14 +225,16 @@ destroy(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __ { typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType; typedef typename iterator_traits<_ForwardIterator>::reference _ReferenceType; - using namespace __pstl; - const auto __is_parallel = __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); - const auto __is_vector = __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); + const auto __is_parallel = + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); + const auto __is_vector = + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); - __internal::__invoke_if_not(std::is_trivially_destructible<_ValueType>(), [&]() { - __internal::__pattern_walk1(std::forward<_ExecutionPolicy>(__exec), __first, __last, - [](_ReferenceType __val) { __val.~_ValueType(); }, __is_vector, __is_parallel); + __pstl::__internal::__invoke_if_not(std::is_trivially_destructible<_ValueType>(), [&]() { + __pstl::__internal::__pattern_walk1(std::forward<_ExecutionPolicy>(__exec), __first, __last, + [](_ReferenceType __val) { __val.~_ValueType(); }, __is_vector, + __is_parallel); }); } @@ -242,17 +244,18 @@ destroy_n(_ExecutionPolicy&& __exec, _ForwardIterator __first, _Size __n) { typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType; typedef typename iterator_traits<_ForwardIterator>::reference _ReferenceType; - using namespace __pstl; - const auto __is_parallel = __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); - const auto __is_vector = __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); + const auto __is_parallel = + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); + const auto __is_vector = + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); - return __internal::__invoke_if_else( + return __pstl::__internal::__invoke_if_else( std::is_trivially_destructible<_ValueType>(), [&]() { return std::next(__first, __n); }, [&]() { - return __internal::__pattern_walk1_n(std::forward<_ExecutionPolicy>(__exec), __first, __n, - [](_ReferenceType __val) { __val.~_ValueType(); }, __is_vector, - __is_parallel); + return __pstl::__internal::__pattern_walk1_n(std::forward<_ExecutionPolicy>(__exec), __first, __n, + [](_ReferenceType __val) { __val.~_ValueType(); }, __is_vector, + __is_parallel); }); } @@ -264,15 +267,16 @@ uninitialized_default_construct(_ExecutionPolicy&& __exec, _ForwardIterator __fi { typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType; typedef typename iterator_traits<_ForwardIterator>::reference _ReferenceType; - using namespace __pstl; - const auto __is_parallel = __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); - const auto __is_vector = __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); + const auto __is_parallel = + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); + const auto __is_vector = + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); - __internal::__invoke_if_not(std::is_trivial<_ValueType>(), [&]() { - __internal::__pattern_walk1(std::forward<_ExecutionPolicy>(__exec), __first, __last, - [](_ReferenceType __val) { ::new (std::addressof(__val)) _ValueType; }, __is_vector, - __is_parallel); + __pstl::__internal::__invoke_if_not(std::is_trivial<_ValueType>(), [&]() { + __pstl::__internal::__pattern_walk1(std::forward<_ExecutionPolicy>(__exec), __first, __last, + [](_ReferenceType __val) { ::new (std::addressof(__val)) _ValueType; }, + __is_vector, __is_parallel); }); } @@ -282,18 +286,19 @@ uninitialized_default_construct_n(_ExecutionPolicy&& __exec, _ForwardIterator __ { typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType; typedef typename iterator_traits<_ForwardIterator>::reference _ReferenceType; - using namespace __pstl; - - const auto __is_parallel = __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); - const auto __is_vector = __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); - - return __internal::__invoke_if_else(std::is_trivial<_ValueType>(), [&]() { return std::next(__first, __n); }, - [&]() { - return __internal::__pattern_walk1_n( - std::forward<_ExecutionPolicy>(__exec), __first, __n, - [](_ReferenceType __val) { ::new (std::addressof(__val)) _ValueType; }, - __is_vector, __is_parallel); - }); + + const auto __is_parallel = + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); + const auto __is_vector = + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); + + return __pstl::__internal::__invoke_if_else( + std::is_trivial<_ValueType>(), [&]() { return std::next(__first, __n); }, + [&]() { + return __pstl::__internal::__pattern_walk1_n( + std::forward<_ExecutionPolicy>(__exec), __first, __n, + [](_ReferenceType __val) { ::new (std::addressof(__val)) _ValueType; }, __is_vector, __is_parallel); + }); } // [uninitialized.construct.value] @@ -304,24 +309,26 @@ uninitialized_value_construct(_ExecutionPolicy&& __exec, _ForwardIterator __firs { typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType; typedef typename iterator_traits<_ForwardIterator>::reference _ReferenceType; - using namespace __pstl; - const auto __is_parallel = __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); - const auto __is_vector = __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); + const auto __is_parallel = + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); + const auto __is_vector = + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); - __internal::__invoke_if_else( + __pstl::__internal::__invoke_if_else( std::is_trivial<_ValueType>(), [&]() { - __internal::__pattern_walk_brick(std::forward<_ExecutionPolicy>(__exec), __first, __last, - [__is_vector](_ForwardIterator __begin, _ForwardIterator __end) { - __internal::__brick_fill(__begin, __end, _ValueType(), __is_vector); - }, - __is_parallel); + __pstl::__internal::__pattern_walk_brick(std::forward<_ExecutionPolicy>(__exec), __first, __last, + [__is_vector](_ForwardIterator __begin, _ForwardIterator __end) { + __pstl::__internal::__brick_fill(__begin, __end, _ValueType(), + __is_vector); + }, + __is_parallel); }, [&]() { - __internal::__pattern_walk1(std::forward<_ExecutionPolicy>(__exec), __first, __last, - [](_ReferenceType __val) { ::new (std::addressof(__val)) _ValueType(); }, - __is_vector, __is_parallel); + __pstl::__internal::__pattern_walk1( + std::forward<_ExecutionPolicy>(__exec), __first, __last, + [](_ReferenceType __val) { ::new (std::addressof(__val)) _ValueType(); }, __is_vector, __is_parallel); }); } @@ -331,23 +338,24 @@ uninitialized_value_construct_n(_ExecutionPolicy&& __exec, _ForwardIterator __fi { typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType; typedef typename iterator_traits<_ForwardIterator>::reference _ReferenceType; - using namespace __pstl; - const auto __is_parallel = __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); - const auto __is_vector = __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); + const auto __is_parallel = + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); + const auto __is_vector = + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec); - return __internal::__invoke_if_else( + return __pstl::__internal::__invoke_if_else( std::is_trivial<_ValueType>(), [&]() { - return __internal::__pattern_walk_brick_n(std::forward<_ExecutionPolicy>(__exec), __first, __n, - [__is_vector](_ForwardIterator __begin, _Size __count) { - return __internal::__brick_fill_n(__begin, __count, - _ValueType(), __is_vector); - }, - __is_parallel); + return __pstl::__internal::__pattern_walk_brick_n(std::forward<_ExecutionPolicy>(__exec), __first, __n, + [__is_vector](_ForwardIterator __begin, _Size __count) { + return __pstl::__internal::__brick_fill_n( + __begin, __count, _ValueType(), __is_vector); + }, + __is_parallel); }, [&]() { - return __internal::__pattern_walk1_n( + return __pstl::__internal::__pattern_walk1_n( std::forward<_ExecutionPolicy>(__exec), __first, __n, [](_ReferenceType __val) { ::new (std::addressof(__val)) _ValueType(); }, __is_vector, __is_parallel); }); diff --git a/libstdc++-v3/include/pstl/glue_numeric_impl.h b/libstdc++-v3/include/pstl/glue_numeric_impl.h index d5acbac..9db64b5 100644 --- a/libstdc++-v3/include/pstl/glue_numeric_impl.h +++ b/libstdc++-v3/include/pstl/glue_numeric_impl.h @@ -55,12 +55,13 @@ transform_reduce(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _Forward _ForwardIterator2 __first2, _Tp __init) { typedef typename iterator_traits<_ForwardIterator1>::value_type _InputType; - using namespace __pstl; - return __internal::__pattern_transform_reduce( + return __pstl::__internal::__pattern_transform_reduce( std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __init, std::plus<_InputType>(), std::multiplies<_InputType>(), - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec)); } template transform_reduce(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _Tp __init, _BinaryOperation1 __binary_op1, _BinaryOperation2 __binary_op2) { - using namespace __pstl; - return __internal::__pattern_transform_reduce( + return __pstl::__internal::__pattern_transform_reduce( std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __init, __binary_op1, __binary_op2, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec)); } template @@ -81,11 +83,10 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Tp> transform_reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Tp __init, _BinaryOperation __binary_op, _UnaryOperation __unary_op) { - using namespace __pstl; - return __internal::__pattern_transform_reduce( + return __pstl::__internal::__pattern_transform_reduce( std::forward<_ExecutionPolicy>(__exec), __first, __last, __init, __binary_op, __unary_op, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec)); } // [exclusive.scan] @@ -95,8 +96,12 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardItera exclusive_scan(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __result, _Tp __init) { - return transform_exclusive_scan(std::forward<_ExecutionPolicy>(__exec), __first, __last, __result, __init, - std::plus<_Tp>(), __pstl::__internal::__no_op()); + using namespace __pstl; + return __internal::__pattern_transform_scan( + std::forward<_ExecutionPolicy>(__exec), __first, __last, __result, __pstl::__internal::__no_op(), __init, + std::plus<_Tp>(), /*inclusive=*/std::false_type(), + __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec), + __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec)); } template @@ -104,8 +109,12 @@ __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardItera exclusive_scan(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __result, _Tp __init, _BinaryOperation __binary_op) { - return transform_exclusive_scan(std::forward<_ExecutionPolicy>(__exec), __first, __last, __result, __init, - __binary_op, __pstl::__internal::__no_op()); + using namespace __pstl; + return __internal::__pattern_transform_scan( + std::forward<_ExecutionPolicy>(__exec), __first, __last, __result, __pstl::__internal::__no_op(), __init, + __binary_op, /*inclusive=*/std::false_type(), + __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec), + __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec)); } // [inclusive.scan] @@ -147,12 +156,13 @@ transform_exclusive_scan(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ _ForwardIterator2 __result, _Tp __init, _BinaryOperation __binary_op, _UnaryOperation __unary_op) { - using namespace __pstl; - return __internal::__pattern_transform_scan( + return __pstl::__internal::__pattern_transform_scan( std::forward<_ExecutionPolicy>(__exec), __first, __last, __result, __unary_op, __init, __binary_op, /*inclusive=*/std::false_type(), - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec)); } // [transform.inclusive.scan] @@ -164,12 +174,13 @@ transform_inclusive_scan(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ _ForwardIterator2 __result, _BinaryOperation __binary_op, _UnaryOperation __unary_op, _Tp __init) { - using namespace __pstl; - return __internal::__pattern_transform_scan( + return __pstl::__internal::__pattern_transform_scan( std::forward<_ExecutionPolicy>(__exec), __first, __last, __result, __unary_op, __init, __binary_op, /*inclusive=*/std::true_type(), - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec)); } template (__exec), __first, __last, __d_first, __op, - __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec), - __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec)); + __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec), + __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>( + __exec)); } template diff --git a/libstdc++-v3/include/pstl/memory_impl.h b/libstdc++-v3/include/pstl/memory_impl.h index d96f021..be5a103 100644 --- a/libstdc++-v3/include/pstl/memory_impl.h +++ b/libstdc++-v3/include/pstl/memory_impl.h @@ -23,31 +23,82 @@ namespace __internal // uninitialized_move //------------------------------------------------------------------------ -template +template _OutputIterator __brick_uninitialized_move(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, /*vector=*/std::false_type) noexcept { - typedef typename std::iterator_traits<_OutputIterator>::value_type _ValueType2; + using _ValueType = typename std::iterator_traits<_OutputIterator>::value_type; for (; __first != __last; ++__first, ++__result) { - ::new (std::addressof(*__result)) _ValueType2(std::move(*__first)); + ::new (std::addressof(*__result)) _ValueType(std::move(*__first)); } return __result; } -template +template _OutputIterator __brick_uninitialized_move(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, /*vector=*/std::true_type) noexcept { - typedef typename std::iterator_traits<_OutputIterator>::value_type __ValueType2; - typedef typename std::iterator_traits<_ForwardIterator>::reference _ReferenceType1; - typedef typename std::iterator_traits<_OutputIterator>::reference _ReferenceType2; + using __ValueType = typename std::iterator_traits<_OutputIterator>::value_type; + using _ReferenceType1 = typename std::iterator_traits<_ForwardIterator>::reference; + using _ReferenceType2 = typename std::iterator_traits<_OutputIterator>::reference; return __unseq_backend::__simd_walk_2( __first, __last - __first, __result, - [](_ReferenceType1 __x, _ReferenceType2 __y) { ::new (std::addressof(__y)) __ValueType2(std::move(__x)); }); + [](_ReferenceType1 __x, _ReferenceType2 __y) { ::new (std::addressof(__y)) __ValueType(std::move(__x)); }); +} + +template +void +__brick_destroy(_Iterator __first, _Iterator __last, /*vector*/ std::false_type) noexcept +{ + using _ValueType = typename std::iterator_traits<_Iterator>::value_type; + + for (; __first != __last; ++__first) + __first->~_ValueType(); +} + +template +void +__brick_destroy(_Iterator __first, _Iterator __last, /*vector*/ std::true_type) noexcept +{ + using _ValueType = typename std::iterator_traits<_Iterator>::value_type; + using _ReferenceType = typename std::iterator_traits<_Iterator>::reference; + + __unseq_backend::__simd_walk_1(__first, __last - __first, [](_ReferenceType __x) { __x.~_ValueType(); }); +} + +//------------------------------------------------------------------------ +// uninitialized copy +//------------------------------------------------------------------------ + +template +_OutputIterator +__brick_uninitialized_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, + /*vector=*/std::false_type) noexcept +{ + using _ValueType = typename std::iterator_traits<_OutputIterator>::value_type; + for (; __first != __last; ++__first, ++__result) + { + ::new (std::addressof(*__result)) _ValueType(*__first); + } + return __result; +} + +template +_OutputIterator +__brick_uninitialized_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, + /*vector=*/std::true_type) noexcept +{ + using __ValueType = typename std::iterator_traits<_OutputIterator>::value_type; + using _ReferenceType1 = typename std::iterator_traits<_ForwardIterator>::reference; + using _ReferenceType2 = typename std::iterator_traits<_OutputIterator>::reference; + + return __unseq_backend::__simd_walk_2( + __first, __last - __first, __result, + [](_ReferenceType1 __x, _ReferenceType2 __y) { ::new (std::addressof(__y)) __ValueType(__x); }); } } // namespace __internal diff --git a/libstdc++-v3/include/pstl/numeric_impl.h b/libstdc++-v3/include/pstl/numeric_impl.h index c5760b0..75d9641 100644 --- a/libstdc++-v3/include/pstl/numeric_impl.h +++ b/libstdc++-v3/include/pstl/numeric_impl.h @@ -93,11 +93,7 @@ _Tp __brick_transform_reduce(_ForwardIterator __first, _ForwardIterator __last, _Tp __init, _BinaryOperation __binary_op, _UnaryOperation __unary_op, /*is_vector=*/std::false_type) noexcept { - for (; __first != __last; ++__first) - { - __init = __binary_op(__init, __unary_op(*__first)); - } - return __init; + return std::transform_reduce(__first, __last, __init, __binary_op, __unary_op); } template @@ -284,7 +280,7 @@ __pattern_transform_scan(_ExecutionPolicy&& __exec, _RandomAccessIterator __firs }) - 1); }, - [](_Tp __res) {}); + [](_Tp) {}); return __result + (__last - __first); }); } diff --git a/libstdc++-v3/include/pstl/parallel_backend.h b/libstdc++-v3/include/pstl/parallel_backend.h index 85d2d4b..4caa4a8 100644 --- a/libstdc++-v3/include/pstl/parallel_backend.h +++ b/libstdc++-v3/include/pstl/parallel_backend.h @@ -12,8 +12,16 @@ #if defined(_PSTL_PAR_BACKEND_SERIAL) # include "parallel_backend_serial.h" +namespace __pstl +{ +namespace __par_backend = __serial_backend; +} #elif defined(_PSTL_PAR_BACKEND_TBB) # include "parallel_backend_tbb.h" +namespace __pstl +{ +namespace __par_backend = __tbb_backend; +} #else _PSTL_PRAGMA_MESSAGE("Parallel backend was not specified"); #endif diff --git a/libstdc++-v3/include/pstl/parallel_backend_serial.h b/libstdc++-v3/include/pstl/parallel_backend_serial.h index e4b3a70..32abe77 100644 --- a/libstdc++-v3/include/pstl/parallel_backend_serial.h +++ b/libstdc++-v3/include/pstl/parallel_backend_serial.h @@ -18,7 +18,7 @@ namespace __pstl { -namespace __serial +namespace __serial_backend { template @@ -110,10 +110,10 @@ template void __parallel_merge(_ExecutionPolicy&&, _RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, - _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _RandomAccessIterator3 __out, + _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _RandomAccessIterator3 __outit, _Compare __comp, _LeafMerge __leaf_merge) { - __leaf_merge(__first1, __last1, __first2, __last2, __out, __comp); + __leaf_merge(__first1, __last1, __first2, __last2, __outit, __comp); } template @@ -124,7 +124,7 @@ __parallel_invoke(_ExecutionPolicy&&, _F1&& __f1, _F2&& __f2) std::forward<_F2>(__f2)(); } -} // namespace __serial +} // namespace __serial_backend } // namespace __pstl namespace __pstl diff --git a/libstdc++-v3/include/pstl/parallel_backend_tbb.h b/libstdc++-v3/include/pstl/parallel_backend_tbb.h index 9c05ade..4476486 100644 --- a/libstdc++-v3/include/pstl/parallel_backend_tbb.h +++ b/libstdc++-v3/include/pstl/parallel_backend_tbb.h @@ -23,6 +23,7 @@ #include #include #include +#include #if TBB_INTERFACE_VERSION < 10000 # error Intel(R) Threading Building Blocks 2018 is required; older versions are not supported. @@ -30,7 +31,7 @@ namespace __pstl { -namespace __par_backend +namespace __tbb_backend { //! Raw memory buffer with automatic freeing and no exceptions. @@ -67,7 +68,11 @@ class __buffer inline void __cancel_execution() { +#if TBB_INTERFACE_VERSION <= 12000 tbb::task::self().group()->cancel_group_execution(); +#else + tbb::task::current_context()->cancel_group_execution(); +#endif } //------------------------------------------------------------------------ @@ -189,7 +194,7 @@ _Tp __parallel_transform_reduce(_ExecutionPolicy&&, _Index __first, _Index __last, _Up __u, _Tp __init, _Cp __combine, _Rp __brick_reduce) { - __par_backend::__par_trans_red_body<_Index, _Up, _Tp, _Cp, _Rp> __body(__u, __init, __combine, __brick_reduce); + __tbb_backend::__par_trans_red_body<_Index, _Up, _Tp, _Cp, _Rp> __body(__u, __init, __combine, __brick_reduce); // The grain size of 3 is used in order to provide mininum 2 elements for each body tbb::this_task_arena::isolate( [__first, __last, &__body]() { tbb::parallel_reduce(tbb::blocked_range<_Index>(__first, __last, 3), __body); }); @@ -303,9 +308,9 @@ __upsweep(_Index __i, _Index __m, _Index __tilesize, _Tp* __r, _Index __lastsize { _Index __k = __split(__m); tbb::parallel_invoke( - [=] { __par_backend::__upsweep(__i, __k, __tilesize, __r, __tilesize, __reduce, __combine); }, + [=] { __tbb_backend::__upsweep(__i, __k, __tilesize, __r, __tilesize, __reduce, __combine); }, [=] { - __par_backend::__upsweep(__i + __k, __m - __k, __tilesize, __r + __k, __lastsize, __reduce, __combine); + __tbb_backend::__upsweep(__i + __k, __m - __k, __tilesize, __r + __k, __lastsize, __reduce, __combine); }); if (__m == 2 * __k) __r[__m - 1] = __combine(__r[__k - 1], __r[__m - 1]); @@ -323,11 +328,11 @@ __downsweep(_Index __i, _Index __m, _Index __tilesize, _Tp* __r, _Index __lastsi { const _Index __k = __split(__m); tbb::parallel_invoke( - [=] { __par_backend::__downsweep(__i, __k, __tilesize, __r, __tilesize, __initial, __combine, __scan); }, + [=] { __tbb_backend::__downsweep(__i, __k, __tilesize, __r, __tilesize, __initial, __combine, __scan); }, // Assumes that __combine never throws. //TODO: Consider adding a requirement for user functors to be constant. [=, &__combine] { - __par_backend::__downsweep(__i + __k, __m - __k, __tilesize, __r + __k, __lastsize, + __tbb_backend::__downsweep(__i + __k, __m - __k, __tilesize, __r + __k, __lastsize, __combine(__initial, __r[__k - 1]), __combine, __scan); }); } @@ -361,7 +366,7 @@ __parallel_strict_scan(_ExecutionPolicy&&, _Index __n, _Tp __initial, _Rp __redu _Index __m = (__n - 1) / __tilesize; __buffer<_Tp> __buf(__m + 1); _Tp* __r = __buf.get(); - __par_backend::__upsweep(_Index(0), _Index(__m + 1), __tilesize, __r, __n - __m * __tilesize, __reduce, + __tbb_backend::__upsweep(_Index(0), _Index(__m + 1), __tilesize, __r, __n - __m * __tilesize, __reduce, __combine); // When __apex is a no-op and __combine has no side effects, a good optimizer @@ -373,7 +378,7 @@ __parallel_strict_scan(_ExecutionPolicy&&, _Index __n, _Tp __initial, _Rp __redu while ((__k &= __k - 1)) __t = __combine(__r[__k - 1], __t); __apex(__combine(__initial, __t)); - __par_backend::__downsweep(_Index(0), _Index(__m + 1), __tilesize, __r, __n - __m * __tilesize, __initial, + __tbb_backend::__downsweep(_Index(0), _Index(__m + 1), __tilesize, __r, __n - __m * __tilesize, __initial, __combine, __scan); return; } @@ -407,79 +412,680 @@ __parallel_transform_scan(_ExecutionPolicy&&, _Index __n, _Up __u, _Tp __init, _ // // These are used by parallel implementations but do not depend on them. //------------------------------------------------------------------------ +#define _PSTL_MERGE_CUT_OFF 2000 -template -class __merge_task : public tbb::task +template +class __func_task; +template +class __root_task; + +#if TBB_INTERFACE_VERSION <= 12000 +class __task : public tbb::task { - /*override*/ tbb::task* - execute(); - _RandomAccessIterator1 _M_xs, _M_xe; - _RandomAccessIterator2 _M_ys, _M_ye; - _RandomAccessIterator3 _M_zs; - _Compare _M_comp; - _Cleanup _M_cleanup; - _LeafMerge _M_leaf_merge; + public: + template + __task* + make_continuation(_Fn&& __f) + { + return new (allocate_continuation()) __func_task::type>(std::forward<_Fn>(__f)); + } + + template + __task* + make_child_of(__task* parent, _Fn&& __f) + { + return new (parent->allocate_child()) __func_task::type>(std::forward<_Fn>(__f)); + } + + template + __task* + make_additional_child_of(tbb::task* parent, _Fn&& __f) + { + return new (tbb::task::allocate_additional_child_of(*parent)) + __func_task::type>(std::forward<_Fn>(__f)); + } + + inline void + recycle_as_continuation() + { + tbb::task::recycle_as_continuation(); + } + + inline void + recycle_as_child_of(__task* parent) + { + tbb::task::recycle_as_child_of(*parent); + } + + inline void + spawn(__task* __t) + { + tbb::task::spawn(*__t); + } + + template + static inline void + spawn_root_and_wait(__root_task<_Fn>& __root) + { + tbb::task::spawn_root_and_wait(*__root._M_task); + } +}; + +template +class __func_task : public __task +{ + _Func _M_func; + + tbb::task* + execute() + { + return _M_func(this); + }; public: - __merge_task(_RandomAccessIterator1 __xs, _RandomAccessIterator1 __xe, _RandomAccessIterator2 __ys, - _RandomAccessIterator2 __ye, _RandomAccessIterator3 __zs, _Compare __comp, _Cleanup __cleanup, - _LeafMerge __leaf_merge) - : _M_xs(__xs), _M_xe(__xe), _M_ys(__ys), _M_ye(__ye), _M_zs(__zs), _M_comp(__comp), _M_cleanup(__cleanup), - _M_leaf_merge(__leaf_merge) + template + __func_task(_Fn&& __f) : _M_func{std::forward<_Fn>(__f)} { } + + _Func& + body() + { + return _M_func; + } }; -#define _PSTL_MERGE_CUT_OFF 2000 +template +class __root_task +{ + tbb::task* _M_task; -template -tbb::task* -__merge_task<_RandomAccessIterator1, _RandomAccessIterator2, _RandomAccessIterator3, __M_Compare, _Cleanup, - _LeafMerge>::execute() + public: + template + __root_task(Args&&... args) + : _M_task{new (tbb::task::allocate_root()) __func_task<_Func>{_Func(std::forward(args)...)}} + { + } + + friend class __task; + friend class __func_task<_Func>; +}; + +#else // TBB_INTERFACE_VERSION <= 12000 +class __task : public tbb::detail::d1::task +{ + protected: + tbb::detail::d1::small_object_allocator _M_allocator{}; + tbb::detail::d1::execution_data* _M_execute_data{}; + __task* _M_parent{}; + std::atomic _M_refcount{}; + bool _M_recycle{}; + + template + __task* + allocate_func_task(_Fn&& __f) + { + _PSTL_ASSERT(_M_execute_data != nullptr); + tbb::detail::d1::small_object_allocator __alloc{}; + auto __t = + __alloc.new_object<__func_task::type>>(*_M_execute_data, std::forward<_Fn>(__f)); + __t->_M_allocator = __alloc; + return __t; + } + + public: + __task* + parent() + { + return _M_parent; + } + + void + set_ref_count(int __n) + { + _M_refcount.store(__n, std::memory_order_release); + } + + template + __task* + make_continuation(_Fn&& __f) + { + auto __t = allocate_func_task(std::forward<_Fn&&>(__f)); + __t->_M_parent = _M_parent; + _M_parent = nullptr; + return __t; + } + + template + __task* + make_child_of(__task* __parent, _Fn&& __f) + { + auto __t = allocate_func_task(std::forward<_Fn&&>(__f)); + __t->_M_parent = __parent; + return __t; + } + + template + __task* + make_additional_child_of(__task* __parent, _Fn&& __f) + { + auto __t = make_child_of(__parent, std::forward<_Fn>(__f)); + _PSTL_ASSERT(__parent->_M_refcount.load(std::memory_order_relaxed) > 0); + ++__parent->_M_refcount; + return __t; + } + + inline void + recycle_as_continuation() + { + _M_recycle = true; + } + + inline void + recycle_as_child_of(__task* parent) + { + _M_recycle = true; + _M_parent = parent; + } + + inline void + spawn(__task* __t) + { + _PSTL_ASSERT(_M_execute_data != nullptr); + tbb::detail::d1::spawn(*__t, *_M_execute_data->context); + } + + template + static inline void + spawn_root_and_wait(__root_task<_Fn>& __root) + { + tbb::detail::d1::execute_and_wait(*__root._M_func_task, __root._M_context, __root._M_wait_object, + __root._M_context); + } + + template + friend class __func_task; +}; + +template +class __func_task : public __task +{ + _Func _M_func; + + __task* + execute(tbb::detail::d1::execution_data& __ed) override + { + _M_execute_data = &__ed; + _M_recycle = false; + __task* __next = _M_func(this); + return finalize(__next); + }; + + __task* + cancel(tbb::detail::d1::execution_data& __ed) override + { + return finalize(nullptr); + } + + __task* + finalize(__task* __next) + { + bool __recycle = _M_recycle; + _M_recycle = false; + + if (__recycle) + { + return __next; + } + + auto __parent = _M_parent; + auto __alloc = _M_allocator; + auto __ed = _M_execute_data; + + this->~__func_task(); + + _PSTL_ASSERT(__parent != nullptr); + _PSTL_ASSERT(__parent->_M_refcount.load(std::memory_order_relaxed) > 0); + if (--__parent->_M_refcount == 0) + { + _PSTL_ASSERT(__next == nullptr); + __alloc.deallocate(this, *__ed); + return __parent; + } + + return __next; + } + + friend class __root_task<_Func>; + + public: + template + __func_task(_Fn&& __f) : _M_func(std::forward<_Fn>(__f)) + { + } + + _Func& + body() + { + return _M_func; + } +}; + +template +class __root_task : public __task +{ + __task* + execute(tbb::detail::d1::execution_data& __ed) override + { + _M_wait_object.release(); + return nullptr; + }; + + __task* + cancel(tbb::detail::d1::execution_data& __ed) override + { + _M_wait_object.release(); + return nullptr; + } + + __func_task<_Func>* _M_func_task{}; + tbb::detail::d1::wait_context _M_wait_object{0}; + tbb::task_group_context _M_context{}; + + public: + template + __root_task(Args&&... args) : _M_wait_object{1} + { + tbb::detail::d1::small_object_allocator __alloc{}; + _M_func_task = __alloc.new_object<__func_task<_Func>>(_Func(std::forward(args)...)); + _M_func_task->_M_allocator = __alloc; + _M_func_task->_M_parent = this; + _M_refcount.store(1, std::memory_order_relaxed); + } + + friend class __task; +}; +#endif // TBB_INTERFACE_VERSION <= 12000 + +template +class __merge_func { typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _DifferenceType1; typedef typename std::iterator_traits<_RandomAccessIterator2>::difference_type _DifferenceType2; typedef typename std::common_type<_DifferenceType1, _DifferenceType2>::type _SizeType; - const _SizeType __n = (_M_xe - _M_xs) + (_M_ye - _M_ys); - const _SizeType __merge_cut_off = _PSTL_MERGE_CUT_OFF; - if (__n <= __merge_cut_off) + typedef typename std::iterator_traits<_RandomAccessIterator1>::value_type _ValueType; + + _RandomAccessIterator1 _M_x_beg; + _RandomAccessIterator2 _M_z_beg; + + _SizeType _M_xs, _M_xe; + _SizeType _M_ys, _M_ye; + _SizeType _M_zs; + _Compare _M_comp; + _LeafMerge _M_leaf_merge; + _SizeType _M_nsort; //number of elements to be sorted for partial_sort alforithm + + static const _SizeType __merge_cut_off = _PSTL_MERGE_CUT_OFF; + + bool _root; //means a task is merging root task + bool _x_orig; //"true" means X(or left ) subrange is in the original container; false - in the buffer + bool _y_orig; //"true" means Y(or right) subrange is in the original container; false - in the buffer + bool _split; //"true" means a merge task is a split task for parallel merging, the execution logic differs + + bool + is_partial() const { - _M_leaf_merge(_M_xs, _M_xe, _M_ys, _M_ye, _M_zs, _M_comp); + return _M_nsort > 0; + } + + struct __move_value + { + template + void + operator()(Iterator1 __x, Iterator2 __z) + { + *__z = std::move(*__x); + } + }; - //we clean the buffer one time on last step of the sort - _M_cleanup(_M_xs, _M_xe); - _M_cleanup(_M_ys, _M_ye); + struct __move_value_construct + { + template + void + operator()(Iterator1 __x, Iterator2 __z) + { + ::new (std::addressof(*__z)) _ValueType(std::move(*__x)); + } + }; + + struct __move_range + { + template + Iterator2 + operator()(Iterator1 __first1, Iterator1 __last1, Iterator2 __first2) + { + if (__last1 - __first1 < __merge_cut_off) + return std::move(__first1, __last1, __first2); + + auto __n = __last1 - __first1; + tbb::parallel_for(tbb::blocked_range<_SizeType>(0, __n, __merge_cut_off), + [__first1, __first2](const tbb::blocked_range<_SizeType>& __range) { + std::move(__first1 + __range.begin(), __first1 + __range.end(), + __first2 + __range.begin()); + }); + return __first2 + __n; + } + }; + + struct __move_range_construct + { + template + Iterator2 + operator()(Iterator1 __first1, Iterator1 __last1, Iterator2 __first2) + { + if (__last1 - __first1 < __merge_cut_off) + { + for (; __first1 != __last1; ++__first1, ++__first2) + __move_value_construct()(__first1, __first2); + return __first2; + } + + auto __n = __last1 - __first1; + tbb::parallel_for(tbb::blocked_range<_SizeType>(0, __n, __merge_cut_off), + [__first1, __first2](const tbb::blocked_range<_SizeType>& __range) { + for (auto i = __range.begin(); i != __range.end(); ++i) + __move_value_construct()(__first1 + i, __first2 + i); + }); + return __first2 + __n; + } + }; + + struct __cleanup_range + { + template + void + operator()(Iterator __first, Iterator __last) + { + if (__last - __first < __merge_cut_off) + _Cleanup()(__first, __last); + else + { + auto __n = __last - __first; + tbb::parallel_for(tbb::blocked_range<_SizeType>(0, __n, __merge_cut_off), + [__first](const tbb::blocked_range<_SizeType>& __range) { + _Cleanup()(__first + __range.begin(), __first + __range.end()); + }); + } + } + }; + + public: + __merge_func(_SizeType __xs, _SizeType __xe, _SizeType __ys, _SizeType __ye, _SizeType __zs, _Compare __comp, + _Cleanup, _LeafMerge __leaf_merge, _SizeType __nsort, _RandomAccessIterator1 __x_beg, + _RandomAccessIterator2 __z_beg, bool __x_orig, bool __y_orig, bool __root) + : _M_xs(__xs), _M_xe(__xe), _M_ys(__ys), _M_ye(__ye), _M_zs(__zs), _M_x_beg(__x_beg), _M_z_beg(__z_beg), + _M_comp(__comp), _M_leaf_merge(__leaf_merge), _M_nsort(__nsort), _root(__root), + _x_orig(__x_orig), _y_orig(__y_orig), _split(false) + { + } + + bool + is_left(_SizeType __idx) const + { + return _M_xs == __idx; + } + + template + void + set_odd(IndexType __idx, bool __on_off) + { + if (is_left(__idx)) + _x_orig = __on_off; + else + _y_orig = __on_off; + } + + __task* + operator()(__task* __self); + + private: + __merge_func* + parent_merge(__task* __self) const + { + return _root ? nullptr : &static_cast<__func_task<__merge_func>*>(__self->parent())->body(); + } + bool + x_less_y() + { + const auto __nx = (_M_xe - _M_xs); + const auto __ny = (_M_ye - _M_ys); + _PSTL_ASSERT(__nx > 0 && __ny > 0); + + _PSTL_ASSERT(_x_orig == _y_orig); + _PSTL_ASSERT(!is_partial()); + + if (_x_orig) + { + _PSTL_ASSERT(std::is_sorted(_M_x_beg + _M_xs, _M_x_beg + _M_xe, _M_comp)); + _PSTL_ASSERT(std::is_sorted(_M_x_beg + _M_ys, _M_x_beg + _M_ye, _M_comp)); + return !_M_comp(*(_M_x_beg + _M_ys), *(_M_x_beg + _M_xe - 1)); + } + + _PSTL_ASSERT(std::is_sorted(_M_z_beg + _M_xs, _M_z_beg + _M_xe, _M_comp)); + _PSTL_ASSERT(std::is_sorted(_M_z_beg + _M_ys, _M_z_beg + _M_ye, _M_comp)); + return !_M_comp(*(_M_z_beg + _M_zs + __nx), *(_M_z_beg + _M_zs + __nx - 1)); + } + void + move_x_range() + { + const auto __nx = (_M_xe - _M_xs); + const auto __ny = (_M_ye - _M_ys); + _PSTL_ASSERT(__nx > 0 && __ny > 0); + + if (_x_orig) + __move_range_construct()(_M_x_beg + _M_xs, _M_x_beg + _M_xe, _M_z_beg + _M_zs); + else + { + __move_range()(_M_z_beg + _M_zs, _M_z_beg + _M_zs + __nx, _M_x_beg + _M_xs); + __cleanup_range()(_M_z_beg + _M_zs, _M_z_beg + _M_zs + __nx); + } + + _x_orig = !_x_orig; + } + void + move_y_range() + { + const auto __nx = (_M_xe - _M_xs); + const auto __ny = (_M_ye - _M_ys); + + if (_y_orig) + __move_range_construct()(_M_x_beg + _M_ys, _M_x_beg + _M_ye, _M_z_beg + _M_zs + __nx); + else + { + __move_range()(_M_z_beg + _M_zs + __nx, _M_z_beg + _M_zs + __nx + __ny, _M_x_beg + _M_ys); + __cleanup_range()(_M_z_beg + _M_zs + __nx, _M_z_beg + _M_zs + __nx + __ny); + } + + _y_orig = !_y_orig; + } + __task* + merge_ranges(__task* __self) + { + _PSTL_ASSERT(_x_orig == _y_orig); //two merged subrange must be lie into the same buffer + + const auto __nx = (_M_xe - _M_xs); + const auto __ny = (_M_ye - _M_ys); + const auto __n = __nx + __ny; + + // need to merge {x} and {y} + if (__n > __merge_cut_off) + return split_merging(__self); + + //merge to buffer + if (_x_orig) + { + _M_leaf_merge(_M_x_beg + _M_xs, _M_x_beg + _M_xe, _M_x_beg + _M_ys, _M_x_beg + _M_ye, _M_z_beg + _M_zs, + _M_comp, __move_value_construct(), __move_value_construct(), __move_range_construct(), + __move_range_construct()); + _PSTL_ASSERT(parent_merge(__self)); //not root merging task + } + //merge to "origin" + else + { + _PSTL_ASSERT(_x_orig == _y_orig); + + _PSTL_ASSERT(is_partial() || std::is_sorted(_M_z_beg + _M_xs, _M_z_beg + _M_xe, _M_comp)); + _PSTL_ASSERT(is_partial() || std::is_sorted(_M_z_beg + _M_ys, _M_z_beg + _M_ye, _M_comp)); + + const auto __nx = (_M_xe - _M_xs); + const auto __ny = (_M_ye - _M_ys); + + _M_leaf_merge(_M_z_beg + _M_xs, _M_z_beg + _M_xe, _M_z_beg + _M_ys, _M_z_beg + _M_ye, _M_x_beg + _M_zs, + _M_comp, __move_value(), __move_value(), __move_range(), __move_range()); + + __cleanup_range()(_M_z_beg + _M_xs, _M_z_beg + _M_xe); + __cleanup_range()(_M_z_beg + _M_ys, _M_z_beg + _M_ye); + } return nullptr; } - else + + __task* + process_ranges(__task* __self) { - _RandomAccessIterator1 __xm; - _RandomAccessIterator2 __ym; - if (_M_xe - _M_xs < _M_ye - _M_ys) + _PSTL_ASSERT(_x_orig == _y_orig); + _PSTL_ASSERT(!_split); + + auto p = parent_merge(__self); + + if (!p) + { //root merging task + + //optimization, just for sort algorithm, //{x} <= {y} + if (!is_partial() && x_less_y()) //we have a solution + { + if (!_x_orig) + { //we have to move the solution to the origin + move_x_range(); //parallel moving + move_y_range(); //parallel moving + } + return nullptr; + } + //else: if we have data in the origin, + //we have to move data to the buffer for final merging into the origin. + if (_x_orig) + { + move_x_range(); //parallel moving + move_y_range(); //parallel moving + } + // need to merge {x} and {y}. + return merge_ranges(__self); + } + //else: not root merging task (parent_merge() == NULL) + //optimization, just for sort algorithm, //{x} <= {y} + if (!is_partial() && x_less_y()) { - __ym = _M_ys + (_M_ye - _M_ys) / 2; - __xm = std::upper_bound(_M_xs, _M_xe, *__ym, _M_comp); + const auto id_range = _M_zs; + p->set_odd(id_range, _x_orig); + return nullptr; + } + //else: we have to revert "_x(y)_orig" flag of the parent merging task + const auto id_range = _M_zs; + p->set_odd(id_range, !_x_orig); + + return merge_ranges(__self); + } + + //splitting as merge task into 2 of the same level + __task* + split_merging(__task* __self) + { + _PSTL_ASSERT(_x_orig == _y_orig); + const auto __nx = (_M_xe - _M_xs); + const auto __ny = (_M_ye - _M_ys); + + _SizeType __xm{}; + _SizeType __ym{}; + if (__nx < __ny) + { + __ym = _M_ys + __ny / 2; + + if (_x_orig) + __xm = std::upper_bound(_M_x_beg + _M_xs, _M_x_beg + _M_xe, *(_M_x_beg + __ym), _M_comp) - _M_x_beg; + else + __xm = std::upper_bound(_M_z_beg + _M_xs, _M_z_beg + _M_xe, *(_M_z_beg + __ym), _M_comp) - _M_z_beg; } else { - __xm = _M_xs + (_M_xe - _M_xs) / 2; - __ym = std::lower_bound(_M_ys, _M_ye, *__xm, _M_comp); + __xm = _M_xs + __nx / 2; + + if (_y_orig) + __ym = std::lower_bound(_M_x_beg + _M_ys, _M_x_beg + _M_ye, *(_M_x_beg + __xm), _M_comp) - _M_x_beg; + else + __ym = std::lower_bound(_M_z_beg + _M_ys, _M_z_beg + _M_ye, *(_M_z_beg + __xm), _M_comp) - _M_z_beg; } - const _RandomAccessIterator3 __zm = _M_zs + ((__xm - _M_xs) + (__ym - _M_ys)); - tbb::task* __right = new (tbb::task::allocate_additional_child_of(*parent())) - __merge_task(__xm, _M_xe, __ym, _M_ye, __zm, _M_comp, _M_cleanup, _M_leaf_merge); - tbb::task::spawn(*__right); - tbb::task::recycle_as_continuation(); + + auto __zm = _M_zs + ((__xm - _M_xs) + (__ym - _M_ys)); + __merge_func __right_func(__xm, _M_xe, __ym, _M_ye, __zm, _M_comp, _Cleanup(), _M_leaf_merge, _M_nsort, + _M_x_beg, _M_z_beg, _x_orig, _y_orig, _root); + __right_func._split = true; + auto __merge_task = __self->make_additional_child_of(__self->parent(), std::move(__right_func)); + __self->spawn(__merge_task); + __self->recycle_as_continuation(); + _M_xe = __xm; _M_ye = __ym; + _split = true; + + return __self; } - return this; +}; + +template +__task* +__merge_func<_RandomAccessIterator1, _RandomAccessIterator2, __M_Compare, _Cleanup, _LeafMerge>:: +operator()(__task* __self) +{ + //a. split merge task into 2 of the same level; the special logic, + //without processing(process_ranges) adjacent sub-ranges x and y + if (_split) + return merge_ranges(__self); + + //b. General merging of adjacent sub-ranges x and y (with optimization in case of {x} <= {y} ) + + //1. x and y are in the even buffer + //2. x and y are in the odd buffer + if (_x_orig == _y_orig) + return process_ranges(__self); + + //3. x is in even buffer, y is in the odd buffer + //4. x is in odd buffer, y is in the even buffer + if (!parent_merge(__self)) + { //root merge task + if (_x_orig) + move_x_range(); + else + move_y_range(); + } + else + { + const _SizeType __nx = (_M_xe - _M_xs); + const _SizeType __ny = (_M_ye - _M_ys); + _PSTL_ASSERT(__nx > 0); + _PSTL_ASSERT(__nx > 0); + + if (__nx < __ny) + move_x_range(); + else + move_y_range(); + } + + return process_ranges(__self); } template -class __stable_sort_task : public tbb::task +class __stable_sort_func { public: typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _DifferenceType1; @@ -487,98 +1093,63 @@ class __stable_sort_task : public tbb::task typedef typename std::common_type<_DifferenceType1, _DifferenceType2>::type _SizeType; private: - /*override*/ tbb::task* - execute(); - _RandomAccessIterator1 _M_xs, _M_xe; - _RandomAccessIterator2 _M_zs; + _RandomAccessIterator1 _M_xs, _M_xe, _M_x_beg; + _RandomAccessIterator2 _M_zs, _M_z_beg; _Compare _M_comp; _LeafSort _M_leaf_sort; - int32_t _M_inplace; - _SizeType _M_nsort; + bool _M_root; + _SizeType _M_nsort; //zero or number of elements to be sorted for partial_sort alforithm public: - __stable_sort_task(_RandomAccessIterator1 __xs, _RandomAccessIterator1 __xe, _RandomAccessIterator2 __zs, - int32_t __inplace, _Compare __comp, _LeafSort __leaf_sort, _SizeType __n) - : _M_xs(__xs), _M_xe(__xe), _M_zs(__zs), _M_comp(__comp), _M_leaf_sort(__leaf_sort), _M_inplace(__inplace), - _M_nsort(__n) + __stable_sort_func(_RandomAccessIterator1 __xs, _RandomAccessIterator1 __xe, _RandomAccessIterator2 __zs, + bool __root, _Compare __comp, _LeafSort __leaf_sort, _SizeType __nsort, + _RandomAccessIterator1 __x_beg, _RandomAccessIterator2 __z_beg) + : _M_xs(__xs), _M_xe(__xe), _M_x_beg(__x_beg), _M_zs(__zs), _M_z_beg(__z_beg), _M_comp(__comp), + _M_leaf_sort(__leaf_sort), _M_root(__root), _M_nsort(__nsort) { } -}; -//! Binary operator that does nothing -struct __binary_no_op -{ - template - void operator()(_Tp, _Tp) - { - } + __task* + operator()(__task* __self); }; #define _PSTL_STABLE_SORT_CUT_OFF 500 template -tbb::task* -__stable_sort_task<_RandomAccessIterator1, _RandomAccessIterator2, _Compare, _LeafSort>::execute() +__task* +__stable_sort_func<_RandomAccessIterator1, _RandomAccessIterator2, _Compare, _LeafSort>::operator()(__task* __self) { + typedef __merge_func<_RandomAccessIterator1, _RandomAccessIterator2, _Compare, __utils::__serial_destroy, + __utils::__serial_move_merge> + _MergeTaskType; + const _SizeType __n = _M_xe - _M_xs; const _SizeType __nmerge = _M_nsort > 0 ? _M_nsort : __n; const _SizeType __sort_cut_off = _PSTL_STABLE_SORT_CUT_OFF; if (__n <= __sort_cut_off) { _M_leaf_sort(_M_xs, _M_xe, _M_comp); - if (_M_inplace != 2) - __par_backend::__init_buf(_M_xs, _M_xe, _M_zs, _M_inplace == 0); - return NULL; - } - else - { - const _RandomAccessIterator1 __xm = _M_xs + __n / 2; - const _RandomAccessIterator2 __zm = _M_zs + (__xm - _M_xs); - const _RandomAccessIterator2 __ze = _M_zs + __n; - task* __m; - auto __move_values = [](_RandomAccessIterator2 __x, _RandomAccessIterator1 __z) { *__z = std::move(*__x); }; - auto __move_sequences = [](_RandomAccessIterator2 __first1, _RandomAccessIterator2 __last1, - _RandomAccessIterator1 __first2) { return std::move(__first1, __last1, __first2); }; - if (_M_inplace == 2) - __m = new (tbb::task::allocate_continuation()) - __merge_task<_RandomAccessIterator2, _RandomAccessIterator2, _RandomAccessIterator1, _Compare, - __serial_destroy, - __par_backend::__serial_move_merge>( - _M_zs, __zm, __zm, __ze, _M_xs, _M_comp, __serial_destroy(), - __par_backend::__serial_move_merge( - __nmerge, __move_values, __move_sequences)); - else if (_M_inplace) - __m = new (tbb::task::allocate_continuation()) - __merge_task<_RandomAccessIterator2, _RandomAccessIterator2, _RandomAccessIterator1, _Compare, - __par_backend::__binary_no_op, - __par_backend::__serial_move_merge>( - _M_zs, __zm, __zm, __ze, _M_xs, _M_comp, __par_backend::__binary_no_op(), - __par_backend::__serial_move_merge( - __nmerge, __move_values, __move_sequences)); - else - { - auto __move_values = [](_RandomAccessIterator1 __x, _RandomAccessIterator2 __z) { *__z = std::move(*__x); }; - auto __move_sequences = [](_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, - _RandomAccessIterator2 __first2) { - return std::move(__first1, __last1, __first2); - }; - __m = new (tbb::task::allocate_continuation()) - __merge_task<_RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2, _Compare, - __par_backend::__binary_no_op, - __par_backend::__serial_move_merge>( - _M_xs, __xm, __xm, _M_xe, _M_zs, _M_comp, __par_backend::__binary_no_op(), - __par_backend::__serial_move_merge( - __nmerge, __move_values, __move_sequences)); - } - __m->set_ref_count(2); - task* __right = new (__m->allocate_child()) - __stable_sort_task(__xm, _M_xe, __zm, !_M_inplace, _M_comp, _M_leaf_sort, __nmerge); - tbb::task::spawn(*__right); - tbb::task::recycle_as_child_of(*__m); - _M_xe = __xm; - _M_inplace = !_M_inplace; + _PSTL_ASSERT(!_M_root); + return nullptr; } - return this; + + const _RandomAccessIterator1 __xm = _M_xs + __n / 2; + const _RandomAccessIterator2 __zm = _M_zs + (__xm - _M_xs); + const _RandomAccessIterator2 __ze = _M_zs + __n; + _MergeTaskType __m(_MergeTaskType(_M_xs - _M_x_beg, __xm - _M_x_beg, __xm - _M_x_beg, _M_xe - _M_x_beg, + _M_zs - _M_z_beg, _M_comp, __utils::__serial_destroy(), + __utils::__serial_move_merge(__nmerge), _M_nsort, _M_x_beg, _M_z_beg, + /*x_orig*/ true, /*y_orig*/ true, /*root*/ _M_root)); + auto __parent = __self->make_continuation(std::move(__m)); + __parent->set_ref_count(2); + auto __right = __self->make_child_of( + __parent, __stable_sort_func(__xm, _M_xe, __zm, false, _M_comp, _M_leaf_sort, _M_nsort, _M_x_beg, _M_z_beg)); + __self->spawn(__right); + __self->recycle_as_child_of(__parent); + _M_root = false; + _M_xe = __xm; + + return __self; } template @@ -591,18 +1162,16 @@ __parallel_stable_sort(_ExecutionPolicy&&, _RandomAccessIterator __xs, _RandomAc typedef typename std::iterator_traits<_RandomAccessIterator>::value_type _ValueType; typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _DifferenceType; const _DifferenceType __n = __xe - __xs; - if (__nsort == 0) - __nsort = __n; + if (__nsort == __n) + __nsort = 0; // 'partial_sort' becames 'sort' const _DifferenceType __sort_cut_off = _PSTL_STABLE_SORT_CUT_OFF; if (__n > __sort_cut_off) { - _PSTL_ASSERT(__nsort > 0 && __nsort <= __n); __buffer<_ValueType> __buf(__n); - using tbb::task; - task::spawn_root_and_wait(*new (task::allocate_root()) - __stable_sort_task<_RandomAccessIterator, _ValueType*, _Compare, _LeafSort>( - __xs, __xe, (_ValueType*)__buf.get(), 2, __comp, __leaf_sort, __nsort)); + __root_task<__stable_sort_func<_RandomAccessIterator, _ValueType*, _Compare, _LeafSort>> __root{ + __xs, __xe, __buf.get(), true, __comp, __leaf_sort, __nsort, __xs, __buf.get()}; + __task::spawn_root_and_wait(__root); return; } //serial sort @@ -613,6 +1182,68 @@ __parallel_stable_sort(_ExecutionPolicy&&, _RandomAccessIterator __xs, _RandomAc //------------------------------------------------------------------------ // parallel_merge //------------------------------------------------------------------------ +template +class __merge_func_static +{ + _RandomAccessIterator1 _M_xs, _M_xe; + _RandomAccessIterator2 _M_ys, _M_ye; + _RandomAccessIterator3 _M_zs; + _Compare _M_comp; + _LeafMerge _M_leaf_merge; + + public: + __merge_func_static(_RandomAccessIterator1 __xs, _RandomAccessIterator1 __xe, _RandomAccessIterator2 __ys, + _RandomAccessIterator2 __ye, _RandomAccessIterator3 __zs, _Compare __comp, + _LeafMerge __leaf_merge) + : _M_xs(__xs), _M_xe(__xe), _M_ys(__ys), _M_ye(__ye), _M_zs(__zs), _M_comp(__comp), _M_leaf_merge(__leaf_merge) + { + } + + __task* + operator()(__task* __self); +}; + +//TODO: consider usage of parallel_for with a custom blocked_range +template +__task* +__merge_func_static<_RandomAccessIterator1, _RandomAccessIterator2, _RandomAccessIterator3, __M_Compare, _LeafMerge>:: +operator()(__task* __self) +{ + typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _DifferenceType1; + typedef typename std::iterator_traits<_RandomAccessIterator2>::difference_type _DifferenceType2; + typedef typename std::common_type<_DifferenceType1, _DifferenceType2>::type _SizeType; + const _SizeType __n = (_M_xe - _M_xs) + (_M_ye - _M_ys); + const _SizeType __merge_cut_off = _PSTL_MERGE_CUT_OFF; + if (__n <= __merge_cut_off) + { + _M_leaf_merge(_M_xs, _M_xe, _M_ys, _M_ye, _M_zs, _M_comp); + return nullptr; + } + + _RandomAccessIterator1 __xm; + _RandomAccessIterator2 __ym; + if (_M_xe - _M_xs < _M_ye - _M_ys) + { + __ym = _M_ys + (_M_ye - _M_ys) / 2; + __xm = std::upper_bound(_M_xs, _M_xe, *__ym, _M_comp); + } + else + { + __xm = _M_xs + (_M_xe - _M_xs) / 2; + __ym = std::lower_bound(_M_ys, _M_ye, *__xm, _M_comp); + } + const _RandomAccessIterator3 __zm = _M_zs + ((__xm - _M_xs) + (__ym - _M_ys)); + auto __right = __self->make_additional_child_of( + __self->parent(), __merge_func_static(__xm, _M_xe, __ym, _M_ye, __zm, _M_comp, _M_leaf_merge)); + __self->spawn(__right); + __self->recycle_as_continuation(); + _M_xe = __xm; + _M_ye = __ym; + + return __self; +} template @@ -634,11 +1265,11 @@ __parallel_merge(_ExecutionPolicy&&, _RandomAccessIterator1 __xs, _RandomAccessI else { tbb::this_task_arena::isolate([=]() { - typedef __merge_task<_RandomAccessIterator1, _RandomAccessIterator2, _RandomAccessIterator3, _Compare, - __par_backend::__binary_no_op, _LeafMerge> + typedef __merge_func_static<_RandomAccessIterator1, _RandomAccessIterator2, _RandomAccessIterator3, + _Compare, _LeafMerge> _TaskType; - tbb::task::spawn_root_and_wait(*new (tbb::task::allocate_root()) _TaskType( - __xs, __xe, __ys, __ye, __zs, __comp, __par_backend::__binary_no_op(), __leaf_merge)); + __root_task<_TaskType> __root{__xs, __xe, __ys, __ye, __zs, __comp, __leaf_merge}; + __task::spawn_root_and_wait(__root); }); } } @@ -654,7 +1285,7 @@ __parallel_invoke(_ExecutionPolicy&&, _F1&& __f1, _F2&& __f2) tbb::this_task_arena::isolate([&]() { tbb::parallel_invoke(std::forward<_F1>(__f1), std::forward<_F2>(__f2)); }); } -} // namespace __par_backend +} // namespace __tbb_backend } // namespace __pstl #endif /* _PSTL_PARALLEL_BACKEND_TBB_H */ diff --git a/libstdc++-v3/include/pstl/parallel_backend_utils.h b/libstdc++-v3/include/pstl/parallel_backend_utils.h index 4c3b3a5..39eafad 100644 --- a/libstdc++-v3/include/pstl/parallel_backend_utils.h +++ b/libstdc++-v3/include/pstl/parallel_backend_utils.h @@ -16,7 +16,8 @@ namespace __pstl { -namespace __par_backend + +namespace __utils { //! Destroy sequence [xs,xe) @@ -36,24 +37,28 @@ struct __serial_destroy }; //! Merge sequences [__xs,__xe) and [__ys,__ye) to output sequence [__zs,(__xe-__xs)+(__ye-__ys)), using std::move -template struct __serial_move_merge { const std::size_t _M_nmerge; - _MoveValues _M_move_values; - _MoveSequences _M_move_sequences; - explicit __serial_move_merge(std::size_t __nmerge, _MoveValues __move_values, _MoveSequences __move_sequences) - : _M_nmerge(__nmerge), _M_move_values(__move_values), _M_move_sequences(__move_sequences) - { - } - template + explicit __serial_move_merge(std::size_t __nmerge) : _M_nmerge(__nmerge) {} + template void operator()(_RandomAccessIterator1 __xs, _RandomAccessIterator1 __xe, _RandomAccessIterator2 __ys, - _RandomAccessIterator2 __ye, _RandomAccessIterator3 __zs, _Compare __comp) + _RandomAccessIterator2 __ye, _RandomAccessIterator3 __zs, _Compare __comp, _MoveValueX __move_value_x, + _MoveValueY __move_value_y, _MoveSequenceX __move_sequence_x, _MoveSequenceY __move_sequence_y) { + constexpr bool __same_move_val = std::is_same<_MoveValueX, _MoveValueY>::value; + constexpr bool __same_move_seq = std::is_same<_MoveSequenceX, _MoveSequenceY>::value; + auto __n = _M_nmerge; _PSTL_ASSERT(__n > 0); + + auto __nx = __xe - __xs; + //auto __ny = __ye - __ys; + _RandomAccessIterator3 __zs_beg = __zs; + if (__xs != __xe) { if (__ys != __ye) @@ -62,7 +67,11 @@ struct __serial_move_merge { if (__comp(*__ys, *__xs)) { - _M_move_values(__ys, __zs); + const auto __i = __zs - __zs_beg; + if (__i < __nx) + __move_value_x(__ys, __zs); + else + __move_value_y(__ys, __zs); ++__zs, --__n; if (++__ys == __ye) { @@ -70,126 +79,179 @@ struct __serial_move_merge } else if (__n == 0) { - __zs = _M_move_sequences(__ys, __ye, __zs); + const auto __j = __zs - __zs_beg; + if (__same_move_seq || __j < __nx) + __zs = __move_sequence_x(__ys, __ye, __zs); + else + __zs = __move_sequence_y(__ys, __ye, __zs); break; } - else - { - } } else { - _M_move_values(__xs, __zs); + const auto __i = __zs - __zs_beg; + if (__same_move_val || __i < __nx) + __move_value_x(__xs, __zs); + else + __move_value_y(__xs, __zs); ++__zs, --__n; if (++__xs == __xe) { - _M_move_sequences(__ys, __ye, __zs); + const auto __j = __zs - __zs_beg; + if (__same_move_seq || __j < __nx) + __move_sequence_x(__ys, __ye, __zs); + else + __move_sequence_y(__ys, __ye, __zs); return; } else if (__n == 0) { - __zs = _M_move_sequences(__xs, __xe, __zs); - _M_move_sequences(__ys, __ye, __zs); + const auto __j = __zs - __zs_beg; + if (__same_move_seq || __j < __nx) + { + __zs = __move_sequence_x(__xs, __xe, __zs); + __move_sequence_x(__ys, __ye, __zs); + } + else + { + __zs = __move_sequence_y(__xs, __xe, __zs); + __move_sequence_y(__ys, __ye, __zs); + } return; } - else - { - } } } } __ys = __xs; __ye = __xe; } - _M_move_sequences(__ys, __ye, __zs); + const auto __i = __zs - __zs_beg; + if (__same_move_seq || __i < __nx) + __move_sequence_x(__ys, __ye, __zs); + else + __move_sequence_y(__ys, __ye, __zs); } }; -template -void -__init_buf(_RandomAccessIterator1 __xs, _RandomAccessIterator1 __xe, _OutputIterator __zs, bool __bMove) +template +_OutputIterator +__set_union_construct(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, + _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp, + _CopyConstructRange __cc_range) { - const _OutputIterator __ze = __zs + (__xe - __xs); - typedef typename std::iterator_traits<_OutputIterator>::value_type _ValueType; - if (__bMove) - { - // Initialize the temporary buffer and move keys to it. - for (; __zs != __ze; ++__xs, ++__zs) - new (&*__zs) _ValueType(std::move(*__xs)); - } - else + using _Tp = typename std::iterator_traits<_OutputIterator>::value_type; + + for (; __first1 != __last1; ++__result) { - // Initialize the temporary buffer - for (; __zs != __ze; ++__zs) - new (&*__zs) _ValueType; + if (__first2 == __last2) + return __cc_range(__first1, __last1, __result); + if (__comp(*__first2, *__first1)) + { + ::new (std::addressof(*__result)) _Tp(*__first2); + ++__first2; + } + else + { + ::new (std::addressof(*__result)) _Tp(*__first1); + if (!__comp(*__first1, *__first2)) + ++__first2; + ++__first1; + } } + return __cc_range(__first2, __last2, __result); } -// TODO is this actually used anywhere? -template -class __stack +template +_OutputIterator +__set_intersection_construct(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, + _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp) { - typedef typename std::iterator_traits::value_type _ValueType; - typedef typename std::iterator_traits<_ValueType*>::difference_type _DifferenceType; + using _Tp = typename std::iterator_traits<_OutputIterator>::value_type; - _Buf _M_buf; - _ValueType* _M_ptr; - _DifferenceType _M_maxsize; - - __stack(const __stack&) = delete; - void - operator=(const __stack&) = delete; - - public: - __stack(_DifferenceType __max_size) : _M_buf(__max_size), _M_maxsize(__max_size) { _M_ptr = _M_buf.get(); } - - ~__stack() + for (; __first1 != __last1 && __first2 != __last2;) { - _PSTL_ASSERT(size() <= _M_maxsize); - while (!empty()) - pop(); + if (__comp(*__first1, *__first2)) + ++__first1; + else + { + if (!__comp(*__first2, *__first1)) + { + ::new (std::addressof(*__result)) _Tp(*__first1); + ++__result; + ++__first1; + } + ++__first2; + } } + return __result; +} - const _Buf& - buffer() const - { - return _M_buf; - } - size_t - size() const - { - _PSTL_ASSERT(_M_ptr - _M_buf.get() <= _M_maxsize); - _PSTL_ASSERT(_M_ptr - _M_buf.get() >= 0); - return _M_ptr - _M_buf.get(); - } - bool - empty() const - { - _PSTL_ASSERT(_M_ptr >= _M_buf.get()); - return _M_ptr == _M_buf.get(); - } - void - push(const _ValueType& __v) - { - _PSTL_ASSERT(size() < _M_maxsize); - new (_M_ptr) _ValueType(__v); - ++_M_ptr; - } - const _ValueType& - top() const +template +_OutputIterator +__set_difference_construct(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, + _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp, + _CopyConstructRange __cc_range) +{ + using _Tp = typename std::iterator_traits<_OutputIterator>::value_type; + + for (; __first1 != __last1;) { - return *(_M_ptr - 1); + if (__first2 == __last2) + return __cc_range(__first1, __last1, __result); + + if (__comp(*__first1, *__first2)) + { + ::new (std::addressof(*__result)) _Tp(*__first1); + ++__result; + ++__first1; + } + else + { + if (!__comp(*__first2, *__first1)) + ++__first1; + ++__first2; + } } - void - pop() + return __result; +} +template +_OutputIterator +__set_symmetric_difference_construct(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, + _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp, + _CopyConstructRange __cc_range) +{ + using _Tp = typename std::iterator_traits<_OutputIterator>::value_type; + + for (; __first1 != __last1;) { - _PSTL_ASSERT(_M_ptr > _M_buf.get()); - --_M_ptr; - (*_M_ptr).~_ValueType(); + if (__first2 == __last2) + return __cc_range(__first1, __last1, __result); + + if (__comp(*__first1, *__first2)) + { + ::new (std::addressof(*__result)) _Tp(*__first1); + ++__result; + ++__first1; + } + else + { + if (__comp(*__first2, *__first1)) + { + ::new (std::addressof(*__result)) _Tp(*__first2); + ++__result; + } + else + ++__first1; + ++__first2; + } } -}; + return __cc_range(__first2, __last2, __result); +} -} // namespace __par_backend +} // namespace __utils } // namespace __pstl #endif /* _PSTL_PARALLEL_BACKEND_UTILS_H */ diff --git a/libstdc++-v3/include/pstl/pstl_config.h b/libstdc++-v3/include/pstl/pstl_config.h index a96e06b..d1bf08e 100644 --- a/libstdc++-v3/include/pstl/pstl_config.h +++ b/libstdc++-v3/include/pstl/pstl_config.h @@ -11,13 +11,13 @@ #define _PSTL_CONFIG_H // The version is XYYZ, where X is major, YY is minor, and Z is patch (i.e. X.YY.Z) -#define _PSTL_VERSION 9000 +#define _PSTL_VERSION 12000 #define _PSTL_VERSION_MAJOR (_PSTL_VERSION / 1000) #define _PSTL_VERSION_MINOR ((_PSTL_VERSION % 1000) / 10) #define _PSTL_VERSION_PATCH (_PSTL_VERSION % 10) #if !defined(_PSTL_PAR_BACKEND_SERIAL) && !defined(_PSTL_PAR_BACKEND_TBB) -# error "The parallel backend is neither serial nor TBB" +# error "A parallel backend must be specified" #endif // Check the user-defined macro for warnings @@ -40,6 +40,15 @@ #define _PSTL_STRING(x) _PSTL_STRING_AUX(x) #define _PSTL_STRING_CONCAT(x, y) x #y +#ifdef _PSTL_HIDE_FROM_ABI_PER_TU +# define _PSTL_HIDE_FROM_ABI_PUSH \ + _Pragma("clang attribute push(__attribute__((internal_linkage)), apply_to=any(function,record))") +# define _PSTL_HIDE_FROM_ABI_POP _Pragma("clang attribute pop") +#else +# define _PSTL_HIDE_FROM_ABI_PUSH /* nothing */ +# define _PSTL_HIDE_FROM_ABI_POP /* nothing */ +#endif + // note that when ICC or Clang is in use, _PSTL_GCC_VERSION might not fully match // the actual GCC version on the system. #define _PSTL_GCC_VERSION (__GNUC__ * 10000 + __GNUC_MINOR__ * 100 + __GNUC_PATCHLEVEL__) @@ -50,7 +59,8 @@ #endif // Enable SIMD for compilers that support OpenMP 4.0 -#if (_OPENMP >= 201307) || (__INTEL_COMPILER >= 1600) || (!defined(__INTEL_COMPILER) && _PSTL_GCC_VERSION >= 40900) +#if (_OPENMP >= 201307) || (__INTEL_COMPILER >= 1600) || (!defined(__INTEL_COMPILER) && _PSTL_GCC_VERSION >= 40900) || \ + defined(__clang__) # define _PSTL_PRAGMA_SIMD _PSTL_PRAGMA(omp simd) # define _PSTL_PRAGMA_DECLARE_SIMD _PSTL_PRAGMA(omp declare simd) # define _PSTL_PRAGMA_SIMD_REDUCTION(PRM) _PSTL_PRAGMA(omp simd reduction(PRM)) @@ -70,7 +80,7 @@ # define _PSTL_PRAGMA_FORCEINLINE #endif -#if (__INTEL_COMPILER >= 1900) || (_PSTL_GCC_VERSION >= 100000) +#if (__INTEL_COMPILER >= 1900) # define _PSTL_PRAGMA_SIMD_SCAN(PRM) _PSTL_PRAGMA(omp simd reduction(inscan, PRM)) # define _PSTL_PRAGMA_SIMD_INCLUSIVE_SCAN(PRM) _PSTL_PRAGMA(omp scan inclusive(PRM)) # define _PSTL_PRAGMA_SIMD_EXCLUSIVE_SCAN(PRM) _PSTL_PRAGMA(omp scan exclusive(PRM)) @@ -100,11 +110,7 @@ # define _PSTL_UDR_PRESENT 0 #endif -#if ((__INTEL_COMPILER >= 1900 && __INTEL_COMPILER_BUILD_DATE >= 20180626) || _PSTL_GCC_VERSION >= 100000) -# define _PSTL_UDS_PRESENT 1 -#else -# define _PSTL_UDS_PRESENT 0 -#endif +#define _PSTL_UDS_PRESENT (__INTEL_COMPILER >= 1900 && __INTEL_COMPILER_BUILD_DATE >= 20180626) #if _PSTL_EARLYEXIT_PRESENT # define _PSTL_PRAGMA_SIMD_EARLYEXIT _PSTL_PRAGMA(omp simd early_exit) diff --git a/libstdc++-v3/include/pstl/unseq_backend_simd.h b/libstdc++-v3/include/pstl/unseq_backend_simd.h index 6f11b95..a05de39 100644 --- a/libstdc++-v3/include/pstl/unseq_backend_simd.h +++ b/libstdc++-v3/include/pstl/unseq_backend_simd.h @@ -181,7 +181,7 @@ __simd_first(_Index1 __first1, _DifferenceType __n, _Index2 __first2, _Pred __pr _DifferenceType __i; _PSTL_PRAGMA_VECTOR_UNALIGNED // Do not generate peel loop part _PSTL_PRAGMA_SIMD_REDUCTION(| - : __found) for (__i = 0; __i < __block_size; ++__i) + : __found) for (__i = 0; __i < __block_size; ++__i) { const _DifferenceType __t = __pred(__first1[__i], __first2[__i]); __lane[__i] = __t; @@ -189,14 +189,14 @@ __simd_first(_Index1 __first1, _DifferenceType __n, _Index2 __first2, _Pred __pr } if (__found) { - _DifferenceType __i; + _DifferenceType __i2; // This will vectorize - for (__i = 0; __i < __block_size; ++__i) + for (__i2 = 0; __i2 < __block_size; ++__i2) { - if (__lane[__i]) + if (__lane[__i2]) break; } - return std::make_pair(__first1 + __i, __first2 + __i); + return std::make_pair(__first1 + __i2, __first2 + __i2); } __first1 += __block_size; __first2 += __block_size; @@ -403,7 +403,7 @@ __simd_adjacent_find(_Index __first, _Index __last, _BinaryPredicate __pred, boo _DifferenceType __found = 0; _PSTL_PRAGMA_VECTOR_UNALIGNED // Do not generate peel loop part _PSTL_PRAGMA_SIMD_REDUCTION(| - : __found) for (__i = 0; __i < __block_size - 1; ++__i) + : __found) for (__i = 0; __i < __block_size - 1; ++__i) { //TODO: to improve SIMD vectorization const _DifferenceType __t = __pred(*(__first + __i), *(__first + __i + 1)); @@ -486,15 +486,15 @@ __simd_transform_reduce(_Size __n, _Tp __init, _BinaryOperation __binary_op, _Un __lane[__j] = __binary_op(__lane[__j], __f(last_iteration + __j)); } // combiner - for (_Size __i = 0; __i < __block_size; ++__i) + for (_Size __j = 0; __j < __block_size; ++__j) { - __init = __binary_op(__init, __lane[__i]); + __init = __binary_op(__init, __lane[__j]); } // destroyer _PSTL_PRAGMA_SIMD - for (_Size __i = 0; __i < __block_size; ++__i) + for (_Size __j = 0; __j < __block_size; ++__j) { - __lane[__i].~_Tp(); + __lane[__j].~_Tp(); } } else @@ -796,8 +796,9 @@ __simd_find_first_of(_ForwardIterator1 __first, _ForwardIterator1 __last, _Forwa { for (; __first != __last; ++__first) { - if (__unseq_backend::__simd_or(__s_first, __n2, - __internal::__equal_value_by_pred(*__first, __pred))) + if (__unseq_backend::__simd_or( + __s_first, __n2, + __internal::__equal_value_by_pred(*__first, __pred))) { return __first; } @@ -807,10 +808,10 @@ __simd_find_first_of(_ForwardIterator1 __first, _ForwardIterator1 __last, _Forwa { for (; __s_first != __s_last; ++__s_first) { - const auto __result = __unseq_backend::__simd_first(__first, _DifferencType(0), __n1, - [__s_first, &__pred](_ForwardIterator1 __it, _DifferencType __i) { - return __pred(__it[__i], *__s_first); - }); + const auto __result = __unseq_backend::__simd_first( + __first, _DifferencType(0), __n1, [__s_first, &__pred](_ForwardIterator1 __it, _DifferencType __i) { + return __pred(__it[__i], *__s_first); + }); if (__result != __last) { return __result; @@ -825,9 +826,9 @@ _RandomAccessIterator __simd_remove_if(_RandomAccessIterator __first, _DifferenceType __n, _UnaryPredicate __pred) noexcept { // find first element we need to remove - auto __current = - __unseq_backend::__simd_first(__first, _DifferenceType(0), __n, - [&__pred](_RandomAccessIterator __it, _DifferenceType __i) { return __pred(__it[__i]); }); + auto __current = __unseq_backend::__simd_first( + __first, _DifferenceType(0), __n, + [&__pred](_RandomAccessIterator __it, _DifferenceType __i) { return __pred(__it[__i]); }); __n -= __current - __first; // if we have in sequence only one element that pred(__current[1]) != false we can exit the function -- 2.7.4