From 5856f202057cd375cd9599fe44cfa7e78239c625 Mon Sep 17 00:00:00 2001 From: Mikhail Dvorskiy Date: Sat, 13 Feb 2021 20:28:50 +0300 Subject: [pstl] Iterator types renaming: ForwardIterator -> RandomAccessIterator; for parallel patterns/bricks https://reviews.llvm.org/D96266 --- pstl/include/pstl/internal/algorithm_fwd.h | 403 ++++++------- pstl/include/pstl/internal/algorithm_impl.h | 873 ++++++++++++++-------------- pstl/include/pstl/internal/memory_impl.h | 20 +- pstl/include/pstl/internal/numeric_fwd.h | 30 +- pstl/include/pstl/internal/numeric_impl.h | 70 +-- 5 files changed, 719 insertions(+), 677 deletions(-) (limited to 'pstl') diff --git a/pstl/include/pstl/internal/algorithm_fwd.h b/pstl/include/pstl/internal/algorithm_fwd.h index d3986de..8d0a3de 100644 --- a/pstl/include/pstl/internal/algorithm_fwd.h +++ b/pstl/include/pstl/internal/algorithm_fwd.h @@ -32,9 +32,9 @@ bool __brick_any_of(const _ForwardIterator, const _ForwardIterator, _Pred, /*__is_vector=*/std::false_type) noexcept; -template +template bool -__brick_any_of(const _ForwardIterator, const _ForwardIterator, _Pred, +__brick_any_of(const _RandomAccessIterator, const _RandomAccessIterator, _Pred, /*__is_vector=*/std::true_type) noexcept; template @@ -42,9 +42,9 @@ bool __pattern_any_of(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Pred, _IsVector, /*parallel=*/std::false_type) noexcept; -template +template bool -__pattern_any_of(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Pred, _IsVector, +__pattern_any_of(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _Pred, _IsVector, /*parallel=*/std::true_type); //------------------------------------------------------------------------ @@ -66,9 +66,9 @@ void __pattern_walk1(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Function, _IsVector, /*parallel=*/std::false_type) noexcept; -template +template void -__pattern_walk1(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Function, _IsVector, +__pattern_walk1(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _Function, _IsVector, /*parallel=*/std::true_type); template @@ -76,9 +76,9 @@ void __pattern_walk_brick(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Brick, /*parallel=*/std::false_type) noexcept; -template +template void -__pattern_walk_brick(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Brick, +__pattern_walk_brick(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _Brick, /*parallel=*/std::true_type); //------------------------------------------------------------------------ @@ -123,26 +123,28 @@ template _ForwardIterator2 __brick_walk2(_ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _Function, /*vector=*/std::false_type) noexcept; -template -_ForwardIterator2 __brick_walk2(_ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _Function, - /*vector=*/std::true_type) noexcept; +template +_RandomAccessIterator2 __brick_walk2(_RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2, _Function, + /*vector=*/std::true_type) noexcept; template _ForwardIterator2 __brick_walk2_n(_ForwardIterator1, _Size, _ForwardIterator2, _Function, /*vector=*/std::false_type) noexcept; -template -_ForwardIterator2 __brick_walk2_n(_ForwardIterator1, _Size, _ForwardIterator2, _Function, - /*vector=*/std::true_type) noexcept; +template +_RandomAccessIterator2 __brick_walk2_n(_RandomAccessIterator1, _Size, _RandomAccessIterator2, _Function, + /*vector=*/std::true_type) noexcept; template _ForwardIterator2 __pattern_walk2(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _Function, _IsVector, /*parallel=*/std::false_type) noexcept; -template -_ForwardIterator2 -__pattern_walk2(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _Function, _IsVector, +template +_RandomAccessIterator2 +__pattern_walk2(_ExecutionPolicy&&, _RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2, _Function, + _IsVector, /*parallel=*/std::true_type); template -_ForwardIterator -__pattern_find_if(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Predicate, _IsVector, +template +_RandomAccessIterator +__pattern_find_if(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _Predicate, _IsVector, /*is_parallel=*/std::true_type); //------------------------------------------------------------------------ @@ -281,10 +283,10 @@ _ForwardIterator1 __brick_find_end(_ForwardIterator1, _ForwardIterator1, _Forwar _BinaryPredicate, /*__is_vector=*/std::false_type) noexcept; -template -_ForwardIterator1 __brick_find_end(_ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2, - _BinaryPredicate, - /*__is_vector=*/std::true_type) noexcept; +template +_RandomAccessIterator1 __brick_find_end(_RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2, + _RandomAccessIterator2, _BinaryPredicate, + /*__is_vector=*/std::true_type) noexcept; template @@ -293,11 +295,11 @@ __pattern_find_end(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _Fo _BinaryPredicate, _IsVector, /*is_parallel=*/std::false_type) noexcept; -template -_ForwardIterator1 -__pattern_find_end(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2, - _BinaryPredicate, _IsVector, +_RandomAccessIterator1 +__pattern_find_end(_ExecutionPolicy&&, _RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2, + _RandomAccessIterator2, _BinaryPredicate, _IsVector, /*is_parallel=*/std::true_type) noexcept; //------------------------------------------------------------------------ @@ -309,10 +311,10 @@ _ForwardIterator1 __brick_find_first_of(_ForwardIterator1, _ForwardIterator1, _F _BinaryPredicate, /*__is_vector=*/std::false_type) noexcept; -template -_ForwardIterator1 __brick_find_first_of(_ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2, - _BinaryPredicate, - /*__is_vector=*/std::true_type) noexcept; +template +_RandomAccessIterator1 __brick_find_first_of(_RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2, + _RandomAccessIterator2, _BinaryPredicate, + /*__is_vector=*/std::true_type) noexcept; template @@ -320,11 +322,11 @@ _ForwardIterator1 __pattern_find_first_of(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2, _BinaryPredicate, _IsVector, /*is_parallel=*/std::false_type) noexcept; -template -_ForwardIterator1 -__pattern_find_first_of(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2, - _BinaryPredicate, _IsVector, /*is_parallel=*/std::true_type) noexcept; +_RandomAccessIterator1 +__pattern_find_first_of(_ExecutionPolicy&&, _RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2, + _RandomAccessIterator2, _BinaryPredicate, _IsVector, /*is_parallel=*/std::true_type) noexcept; //------------------------------------------------------------------------ // search @@ -335,10 +337,10 @@ _ForwardIterator1 __brick_search(_ForwardIterator1, _ForwardIterator1, _ForwardI _BinaryPredicate, /*vector=*/std::false_type) noexcept; -template -_ForwardIterator1 __brick_search(_ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2, - _BinaryPredicate, - /*vector=*/std::true_type) noexcept; +template +_RandomAccessIterator1 __brick_search(_RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2, + _RandomAccessIterator2, _BinaryPredicate, + /*vector=*/std::true_type) noexcept; template @@ -347,11 +349,11 @@ __pattern_search(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _Forw _BinaryPredicate, _IsVector, /*is_parallel=*/std::false_type) noexcept; -template -_ForwardIterator1 -__pattern_search(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2, - _BinaryPredicate, _IsVector, +_RandomAccessIterator1 +__pattern_search(_ExecutionPolicy&&, _RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2, + _RandomAccessIterator2, _BinaryPredicate, _IsVector, /*is_parallel=*/std::true_type) noexcept; //------------------------------------------------------------------------ @@ -363,9 +365,9 @@ _ForwardIterator __brick_search_n(_ForwardIterator, _ForwardIterator, _Size, const _Tp&, _BinaryPredicate, /*vector=*/std::false_type) noexcept; -template -_ForwardIterator -__brick_search_n(_ForwardIterator, _ForwardIterator, _Size, const _Tp&, _BinaryPredicate, +template +_RandomAccessIterator +__brick_search_n(_RandomAccessIterator, _RandomAccessIterator, _Size, const _Tp&, _BinaryPredicate, /*vector=*/std::true_type) noexcept; template _OutputIterator __brick_copy_n(_ForwardIterator, _Size, _OutputIterator, /*vector=*/std::false_type) noexcept; -template -_OutputIterator __brick_copy_n(_ForwardIterator, _Size, _OutputIterator, +template +_OutputIterator __brick_copy_n(_RandomAccessIterator, _Size, _OutputIterator, /*vector=*/std::true_type) noexcept; //------------------------------------------------------------------------ @@ -426,9 +428,9 @@ _OutputIterator __brick_swap_ranges(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, /*vector=*/std::false_type) noexcept; -template +template _OutputIterator -__brick_swap_ranges(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, +__brick_swap_ranges(_RandomAccessIterator __first, _RandomAccessIterator __last, _OutputIterator __result, /*vector=*/std::true_type) noexcept; //------------------------------------------------------------------------ @@ -439,8 +441,8 @@ template _OutputIterator __brick_copy_if(_ForwardIterator, _ForwardIterator, _OutputIterator, _UnaryPredicate, /*vector=*/std::false_type) noexcept; -template -_OutputIterator __brick_copy_if(_ForwardIterator, _ForwardIterator, _OutputIterator, _UnaryPredicate, +template +_OutputIterator __brick_copy_if(_RandomAccessIterator, _RandomAccessIterator, _OutputIterator, _UnaryPredicate, /*vector=*/std::true_type) noexcept; template @@ -457,9 +459,9 @@ void __brick_copy_by_mask(_ForwardIterator, _ForwardIterator, _OutputIterator, bool*, /*vector=*/std::false_type) noexcept; -template +template void -__brick_copy_by_mask(_ForwardIterator, _ForwardIterator, _OutputIterator, bool* __restrict, +__brick_copy_by_mask(_RandomAccessIterator, _RandomAccessIterator, _OutputIterator, bool* __restrict, /*vector=*/std::true_type) noexcept; template @@ -487,9 +489,9 @@ __pattern_copy_if(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterat // count //------------------------------------------------------------------------ -template -typename std::iterator_traits<_ForwardIterator>::difference_type - __brick_count(_ForwardIterator, _ForwardIterator, _Predicate, +template +typename std::iterator_traits<_RandomAccessIterator>::difference_type + __brick_count(_RandomAccessIterator, _RandomAccessIterator, _Predicate, /* is_vector = */ std::true_type) noexcept; template @@ -502,9 +504,9 @@ typename std::iterator_traits<_ForwardIterator>::difference_type __pattern_count(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Predicate, /* is_parallel */ std::false_type, _IsVector) noexcept; -template -typename std::iterator_traits<_ForwardIterator>::difference_type -__pattern_count(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Predicate, +template +typename std::iterator_traits<_RandomAccessIterator>::difference_type +__pattern_count(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _Predicate, /* is_parallel */ std::true_type, _IsVector); //------------------------------------------------------------------------ @@ -515,18 +517,18 @@ template _ForwardIterator __brick_unique(_ForwardIterator, _ForwardIterator, _BinaryPredicate, /*is_vector=*/std::false_type) noexcept; -template -_ForwardIterator __brick_unique(_ForwardIterator, _ForwardIterator, _BinaryPredicate, - /*is_vector=*/std::true_type) noexcept; +template +_RandomAccessIterator __brick_unique(_RandomAccessIterator, _RandomAccessIterator, _BinaryPredicate, + /*is_vector=*/std::true_type) noexcept; template _ForwardIterator __pattern_unique(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _BinaryPredicate, _IsVector, /*is_parallel=*/std::false_type) noexcept; -template -_ForwardIterator -__pattern_unique(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _BinaryPredicate, _IsVector, +template +_RandomAccessIterator +__pattern_unique(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _BinaryPredicate, _IsVector, /*is_parallel=*/std::true_type) noexcept; //------------------------------------------------------------------------ @@ -571,16 +573,16 @@ template void __brick_reverse(_BidirectionalIterator, _BidirectionalIterator, /*__is_vector=*/std::false_type) noexcept; -template -void __brick_reverse(_BidirectionalIterator, _BidirectionalIterator, +template +void __brick_reverse(_RandomAccessIterator, _RandomAccessIterator, /*__is_vector=*/std::true_type) noexcept; template void __brick_reverse(_BidirectionalIterator, _BidirectionalIterator, _BidirectionalIterator, /*is_vector=*/std::false_type) noexcept; -template -void __brick_reverse(_BidirectionalIterator, _BidirectionalIterator, _BidirectionalIterator, +template +void __brick_reverse(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, /*is_vector=*/std::true_type) noexcept; template @@ -588,9 +590,9 @@ void __pattern_reverse(_ExecutionPolicy&&, _BidirectionalIterator, _BidirectionalIterator, _IsVector, /*is_parallel=*/std::false_type) noexcept; -template +template void -__pattern_reverse(_ExecutionPolicy&&, _BidirectionalIterator, _BidirectionalIterator, _IsVector, +__pattern_reverse(_RandomAccessIterator&&, _RandomAccessIterator, _RandomAccessIterator, _IsVector, /*is_parallel=*/std::true_type); //------------------------------------------------------------------------ @@ -601,8 +603,8 @@ template _OutputIterator __brick_reverse_copy(_BidirectionalIterator, _BidirectionalIterator, _OutputIterator, /*is_vector=*/std::false_type) noexcept; -template -_OutputIterator __brick_reverse_copy(_BidirectionalIterator, _BidirectionalIterator, _OutputIterator, +template +_OutputIterator __brick_reverse_copy(_RandomAccessIterator, _RandomAccessIterator, _OutputIterator, /*is_vector=*/std::true_type) noexcept; template @@ -610,9 +612,9 @@ _OutputIterator __pattern_reverse_copy(_ExecutionPolicy&&, _BidirectionalIterator, _BidirectionalIterator, _OutputIterator, _IsVector, /*is_parallel=*/std::false_type) noexcept; -template +template _OutputIterator -__pattern_reverse_copy(_ExecutionPolicy&&, _BidirectionalIterator, _BidirectionalIterator, _OutputIterator, _IsVector, +__pattern_reverse_copy(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _OutputIterator, _IsVector, /*is_parallel=*/std::true_type); //------------------------------------------------------------------------ @@ -623,18 +625,18 @@ template _ForwardIterator __brick_rotate(_ForwardIterator, _ForwardIterator, _ForwardIterator, /*is_vector=*/std::false_type) noexcept; -template -_ForwardIterator __brick_rotate(_ForwardIterator, _ForwardIterator, _ForwardIterator, - /*is_vector=*/std::true_type) noexcept; +template +_RandomAccessIterator __brick_rotate(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, + /*is_vector=*/std::true_type) noexcept; template _ForwardIterator __pattern_rotate(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _ForwardIterator, _IsVector, /*is_parallel=*/std::false_type) noexcept; -template -_ForwardIterator -__pattern_rotate(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _ForwardIterator, _IsVector, +template +_RandomAccessIterator +__pattern_rotate(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _IsVector, /*is_parallel=*/std::true_type); //------------------------------------------------------------------------ @@ -645,8 +647,9 @@ template _OutputIterator __brick_rotate_copy(_ForwardIterator, _ForwardIterator, _ForwardIterator, _OutputIterator, /*__is_vector=*/std::false_type) noexcept; -template -_OutputIterator __brick_rotate_copy(_ForwardIterator, _ForwardIterator, _ForwardIterator, _OutputIterator, +template +_OutputIterator __brick_rotate_copy(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, + _OutputIterator, /*__is_vector=*/std::true_type) noexcept; template @@ -655,10 +658,10 @@ __pattern_rotate_copy(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _F _IsVector, /*is_parallel=*/std::false_type) noexcept; -template +template _OutputIterator -__pattern_rotate_copy(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _ForwardIterator, _OutputIterator, - _IsVector, +__pattern_rotate_copy(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, + _OutputIterator, _IsVector, /*is_parallel=*/std::true_type); //------------------------------------------------------------------------ @@ -669,8 +672,8 @@ template bool __brick_is_partitioned(_ForwardIterator, _ForwardIterator, _UnaryPredicate, /*is_vector=*/std::false_type) noexcept; -template -bool __brick_is_partitioned(_ForwardIterator, _ForwardIterator, _UnaryPredicate, +template +bool __brick_is_partitioned(_RandomAccessIterator, _RandomAccessIterator, _UnaryPredicate, /*is_vector=*/std::true_type) noexcept; template @@ -678,9 +681,9 @@ bool __pattern_is_partitioned(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _UnaryPredicate, _IsVector, /*is_parallel=*/std::false_type) noexcept; -template +template bool -__pattern_is_partitioned(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _UnaryPredicate, _IsVector, +__pattern_is_partitioned(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _UnaryPredicate, _IsVector, /*is_parallel=*/std::true_type); //------------------------------------------------------------------------ @@ -691,18 +694,18 @@ template _ForwardIterator __brick_partition(_ForwardIterator, _ForwardIterator, _UnaryPredicate, /*is_vector=*/std::false_type) noexcept; -template -_ForwardIterator __brick_partition(_ForwardIterator, _ForwardIterator, _UnaryPredicate, - /*is_vector=*/std::true_type) noexcept; +template +_RandomAccessIterator __brick_partition(_RandomAccessIterator, _RandomAccessIterator, _UnaryPredicate, + /*is_vector=*/std::true_type) noexcept; template _ForwardIterator __pattern_partition(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _UnaryPredicate, _IsVector, /*is_parallel=*/std::false_type) noexcept; -template -_ForwardIterator -__pattern_partition(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _UnaryPredicate, _IsVector, +template +_RandomAccessIterator +__pattern_partition(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _UnaryPredicate, _IsVector, /*is_parallel=*/std::true_type); //------------------------------------------------------------------------ @@ -713,9 +716,9 @@ template _BidirectionalIterator __brick_stable_partition(_BidirectionalIterator, _BidirectionalIterator, _UnaryPredicate, /*__is_vector=*/std::false_type) noexcept; -template -_BidirectionalIterator __brick_stable_partition(_BidirectionalIterator, _BidirectionalIterator, _UnaryPredicate, - /*__is_vector=*/std::true_type) noexcept; +template +_RandomAccessIterator __brick_stable_partition(_RandomAccessIterator, _RandomAccessIterator, _UnaryPredicate, + /*__is_vector=*/std::true_type) noexcept; template _BidirectionalIterator @@ -723,10 +726,9 @@ __pattern_stable_partition(_ExecutionPolicy&&, _BidirectionalIterator, _Bidirect _IsVector, /*is_parallelization=*/std::false_type) noexcept; -template -_BidirectionalIterator -__pattern_stable_partition(_ExecutionPolicy&&, _BidirectionalIterator, _BidirectionalIterator, _UnaryPredicate, - _IsVector, +template +_RandomAccessIterator +__pattern_stable_partition(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _UnaryPredicate, _IsVector, /*is_parallelization=*/std::true_type) noexcept; //------------------------------------------------------------------------ @@ -738,10 +740,11 @@ std::pair<_OutputIterator1, _OutputIterator2> __brick_partition_copy(_ForwardIterator, _ForwardIterator, _OutputIterator1, _OutputIterator2, _UnaryPredicate, /*is_vector=*/std::false_type) noexcept; -template -std::pair<_OutputIterator1, _OutputIterator2> - __brick_partition_copy(_ForwardIterator, _ForwardIterator, _OutputIterator1, _OutputIterator2, _UnaryPredicate, - /*is_vector=*/std::true_type) noexcept; +template +std::pair<_OutputIterator1, _OutputIterator2> __brick_partition_copy(_RandomAccessIterator, _RandomAccessIterator, + _OutputIterator1, _OutputIterator2, + _UnaryPredicate, + /*is_vector=*/std::true_type) noexcept; template @@ -809,25 +812,27 @@ __pattern_partial_sort(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessI // partial_sort_copy //------------------------------------------------------------------------ -template -_RandomAccessIterator -__pattern_partial_sort_copy(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _RandomAccessIterator, - _RandomAccessIterator, _Compare, _IsVector, +template +_RandomAccessIterator2 +__pattern_partial_sort_copy(_ExecutionPolicy&&, _RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2, + _RandomAccessIterator2, _Compare, _IsVector, /*is_parallel=*/std::false_type) noexcept; -template -_RandomAccessIterator -__pattern_partial_sort_copy(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _RandomAccessIterator, - _RandomAccessIterator, _Compare, _IsVector, +template +_RandomAccessIterator2 +__pattern_partial_sort_copy(_ExecutionPolicy&&, _RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2, + _RandomAccessIterator2, _Compare, _IsVector, /*is_parallel=*/std::true_type); //------------------------------------------------------------------------ // adjacent_find //------------------------------------------------------------------------ -template -_ForwardIterator -__brick_adjacent_find(_ForwardIterator, _ForwardIterator, _BinaryPredicate, +template +_RandomAccessIterator +__brick_adjacent_find(_RandomAccessIterator, _RandomAccessIterator, _BinaryPredicate, /* IsVector = */ std::true_type, bool) noexcept; template @@ -863,9 +868,9 @@ __pattern_nth_element(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIt //------------------------------------------------------------------------ // fill, fill_n //------------------------------------------------------------------------ -template +template void -__brick_fill(_ForwardIterator, _ForwardIterator, const _Tp&, +__brick_fill(_RandomAccessIterator, _RandomAccessIterator, const _Tp&, /* __is_vector = */ std::true_type) noexcept; template @@ -878,14 +883,14 @@ void __pattern_fill(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, const _Tp&, /*is_parallel=*/std::false_type, _IsVector) noexcept; -template -_ForwardIterator -__pattern_fill(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, const _Tp&, +template +_RandomAccessIterator +__pattern_fill(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, const _Tp&, /*is_parallel=*/std::true_type, _IsVector); -template -_OutputIterator -__brick_fill_n(_OutputIterator, _Size, const _Tp&, +template +_RandomAccessIterator +__brick_fill_n(_RandomAccessIterator, _Size, const _Tp&, /* __is_vector = */ std::true_type) noexcept; template @@ -898,9 +903,9 @@ _OutputIterator __pattern_fill_n(_ExecutionPolicy&&, _OutputIterator, _Size, const _Tp&, /*is_parallel=*/std::false_type, _IsVector) noexcept; -template -_OutputIterator -__pattern_fill_n(_ExecutionPolicy&&, _OutputIterator, _Size, const _Tp&, +template +_RandomAccessIterator +__pattern_fill_n(_ExecutionPolicy&&, _RandomAccessIterator, _Size, const _Tp&, /*is_parallel=*/std::true_type, _IsVector); //------------------------------------------------------------------------ @@ -920,14 +925,14 @@ void __pattern_generate(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Generator, /*is_parallel=*/std::false_type, _IsVector) noexcept; -template -_ForwardIterator -__pattern_generate(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Generator, +template +_RandomAccessIterator +__pattern_generate(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _Generator, /*is_parallel=*/std::true_type, _IsVector); -template -OutputIterator __brick_generate_n(OutputIterator, Size, _Generator, - /* is_vector = */ std::true_type) noexcept; +template +_RandomAccessIterator __brick_generate_n(_RandomAccessIterator, Size, _Generator, + /* is_vector = */ std::true_type) noexcept; template OutputIterator __brick_generate_n(OutputIterator, Size, _Generator, @@ -938,9 +943,9 @@ OutputIterator __pattern_generate_n(_ExecutionPolicy&&, OutputIterator, Size, _Generator, /*is_parallel=*/std::false_type, _IsVector) noexcept; -template -OutputIterator -__pattern_generate_n(_ExecutionPolicy&&, OutputIterator, Size, _Generator, +template +_RandomAccessIterator +__pattern_generate_n(_ExecutionPolicy&&, _RandomAccessIterator, Size, _Generator, /*is_parallel=*/std::true_type, _IsVector); //------------------------------------------------------------------------ @@ -959,9 +964,9 @@ _ForwardIterator __pattern_remove_if(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _UnaryPredicate, _IsVector, /*is_parallel*/ std::false_type) noexcept; -template -_ForwardIterator -__pattern_remove_if(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _UnaryPredicate, _IsVector, +template +_RandomAccessIterator +__pattern_remove_if(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _UnaryPredicate, _IsVector, /*is_parallel*/ std::true_type) noexcept; //------------------------------------------------------------------------ @@ -973,9 +978,9 @@ _OutputIterator __brick_merge(_ForwardIterator1, _ForwardIterator1, _ForwardIter _OutputIterator, _Compare, /* __is_vector = */ std::false_type) noexcept; -template -_OutputIterator __brick_merge(_ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2, - _OutputIterator, _Compare, +template +_OutputIterator __brick_merge(_RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2, + _RandomAccessIterator2, _OutputIterator, _Compare, /* __is_vector = */ std::true_type) noexcept; template void __brick_inplace_merge(_BidirectionalIterator, _BidirectionalIterator, _BidirectionalIterator, _Compare, /* __is_vector = */ std::false_type) noexcept; -template -void __brick_inplace_merge(_BidirectionalIterator, _BidirectionalIterator, _BidirectionalIterator, _Compare, +template +void __brick_inplace_merge(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare, /* __is_vector = */ std::true_type) noexcept; template @@ -1009,9 +1014,9 @@ __pattern_inplace_merge(_ExecutionPolicy&&, _BidirectionalIterator, _Bidirection _Compare, _IsVector, /* is_parallel = */ std::false_type) noexcept; -template +template void -__pattern_inplace_merge(_ExecutionPolicy&&, _BidirectionalIterator, _BidirectionalIterator, _BidirectionalIterator, +__pattern_inplace_merge(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare, _IsVector, /*is_parallel=*/std::true_type); @@ -1025,10 +1030,11 @@ __pattern_includes(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _Fo _Compare, _IsVector, /*is_parallel=*/std::false_type) noexcept; -template +template bool -__pattern_includes(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2, - _Compare, _IsVector, +__pattern_includes(_ExecutionPolicy&&, _RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2, + _RandomAccessIterator2, _Compare, _IsVector, /*is_parallel=*/std::true_type); //------------------------------------------------------------------------ @@ -1040,9 +1046,9 @@ _OutputIterator __brick_set_union(_ForwardIterator1, _ForwardIterator1, _Forward _OutputIterator, _Compare, /*__is_vector=*/std::false_type) noexcept; -template -_OutputIterator __brick_set_union(_ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2, - _OutputIterator, _Compare, +template +_OutputIterator __brick_set_union(_RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2, + _RandomAccessIterator2, _OutputIterator, _Compare, /*__is_vector=*/std::true_type) noexcept; template _OutputIterator -__pattern_set_union(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2, - _OutputIterator, _Compare, _IsVector, /*is_parallel=*/std::true_type); +__pattern_set_union(_ExecutionPolicy&&, _RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2, + _RandomAccessIterator2, _OutputIterator, _Compare, _IsVector, /*is_parallel=*/std::true_type); //------------------------------------------------------------------------ // set_intersection @@ -1066,9 +1072,9 @@ _OutputIterator __brick_set_intersection(_ForwardIterator1, _ForwardIterator1, _ _OutputIterator, _Compare, /*__is_vector=*/std::false_type) noexcept; -template -_OutputIterator __brick_set_intersection(_ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2, - _OutputIterator, _Compare, +template +_OutputIterator __brick_set_intersection(_RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2, + _RandomAccessIterator2, _OutputIterator, _Compare, /*__is_vector=*/std::true_type) noexcept; template _OutputIterator -__pattern_set_intersection(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, - _ForwardIterator2, _OutputIterator, _Compare, _IsVector, /*is_parallel=*/std::true_type); +__pattern_set_intersection(_ExecutionPolicy&&, _RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2, + _RandomAccessIterator2, _OutputIterator, _Compare, _IsVector, + /*is_parallel=*/std::true_type); //------------------------------------------------------------------------ // set_difference @@ -1093,9 +1100,9 @@ _OutputIterator __brick_set_difference(_ForwardIterator1, _ForwardIterator1, _Fo _OutputIterator, _Compare, /*__is_vector=*/std::false_type) noexcept; -template -_OutputIterator __brick_set_difference(_ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2, - _OutputIterator, _Compare, +template +_OutputIterator __brick_set_difference(_RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2, + _RandomAccessIterator2, _OutputIterator, _Compare, /*__is_vector=*/std::true_type) noexcept; template _OutputIterator -__pattern_set_difference(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2, - _OutputIterator, _Compare, _IsVector, /*is_parallel=*/std::true_type); +__pattern_set_difference(_ExecutionPolicy&&, _RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2, + _RandomAccessIterator2, _OutputIterator, _Compare, _IsVector, /*is_parallel=*/std::true_type); //------------------------------------------------------------------------ // set_symmetric_difference @@ -1119,9 +1126,9 @@ _OutputIterator __brick_set_symmetric_difference(_ForwardIterator1, _ForwardIter _ForwardIterator2, _OutputIterator, _Compare, /*__is_vector=*/std::false_type) noexcept; -template -_OutputIterator __brick_set_symmetric_difference(_ForwardIterator1, _ForwardIterator1, _ForwardIterator2, - _ForwardIterator2, _OutputIterator, _Compare, +template +_OutputIterator __brick_set_symmetric_difference(_RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2, + _RandomAccessIterator2, _OutputIterator, _Compare, /*__is_vector=*/std::true_type) noexcept; template _OutputIterator -__pattern_set_symmetric_difference(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, - _ForwardIterator2, _OutputIterator, _Compare, _IsVector, +__pattern_set_symmetric_difference(_ExecutionPolicy&&, _RandomAccessIterator1, _RandomAccessIterator1, + _RandomAccessIterator2, _RandomAccessIterator2, _OutputIterator, _Compare, _IsVector, /*is_parallel=*/std::true_type); //------------------------------------------------------------------------ @@ -1168,9 +1175,9 @@ template _ForwardIterator __brick_min_element(_ForwardIterator, _ForwardIterator, _Compare, /* __is_vector = */ std::false_type) noexcept; -template -_ForwardIterator __brick_min_element(_ForwardIterator, _ForwardIterator, _Compare, - /* __is_vector = */ std::true_type) noexcept; +template +_RandomAccessIterator __brick_min_element(_RandomAccessIterator, _RandomAccessIterator, _Compare, + /* __is_vector = */ std::true_type) noexcept; template _ForwardIterator @@ -1190,18 +1197,19 @@ template std::pair<_ForwardIterator, _ForwardIterator> __brick_minmax_element(_ForwardIterator, _ForwardIterator, _Compare, /* __is_vector = */ std::false_type) noexcept; -template -std::pair<_ForwardIterator, _ForwardIterator> __brick_minmax_element(_ForwardIterator, _ForwardIterator, _Compare, - /* __is_vector = */ std::true_type) noexcept; +template +std::pair<_RandomAccessIterator, _RandomAccessIterator> + __brick_minmax_element(_RandomAccessIterator, _RandomAccessIterator, _Compare, + /* __is_vector = */ std::true_type) noexcept; template std::pair<_ForwardIterator, _ForwardIterator> __pattern_minmax_element(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Compare, _IsVector, /* is_parallel = */ std::false_type) noexcept; -template -std::pair<_ForwardIterator, _ForwardIterator> -__pattern_minmax_element(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Compare, _IsVector, +template +std::pair<_RandomAccessIterator, _RandomAccessIterator> +__pattern_minmax_element(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _Compare, _IsVector, /* is_parallel = */ std::true_type); //------------------------------------------------------------------------ @@ -1213,10 +1221,11 @@ std::pair<_ForwardIterator1, _ForwardIterator2> __brick_mismatch(_ForwardIterato _ForwardIterator2, _ForwardIterator2, _Predicate, /* __is_vector = */ std::false_type) noexcept; -template -std::pair<_ForwardIterator1, _ForwardIterator2> __brick_mismatch(_ForwardIterator1, _ForwardIterator1, - _ForwardIterator2, _ForwardIterator2, _Predicate, - /* __is_vector = */ std::true_type) noexcept; +template +std::pair<_RandomAccessIterator1, _RandomAccessIterator2> + __brick_mismatch(_RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2, _RandomAccessIterator2, + _Predicate, + /* __is_vector = */ std::true_type) noexcept; template std::pair<_ForwardIterator1, _ForwardIterator2> @@ -1239,9 +1248,9 @@ bool __brick_lexicographical_compare(_ForwardIterator1, _ForwardIterator1, _Forw _Compare, /* __is_vector = */ std::false_type) noexcept; -template -bool __brick_lexicographical_compare(_ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2, - _Compare, +template +bool __brick_lexicographical_compare(_RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2, + _RandomAccessIterator2, _Compare, /* __is_vector = */ std::true_type) noexcept; template @@ -1249,10 +1258,12 @@ bool __pattern_lexicographical_compare(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2, _Compare, _IsVector, /* is_parallel = */ std::false_type) noexcept; -template +template bool -__pattern_lexicographical_compare(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, - _ForwardIterator2, _Compare, _IsVector, /* is_parallel = */ std::true_type) noexcept; +__pattern_lexicographical_compare(_ExecutionPolicy&&, _RandomAccessIterator1, _RandomAccessIterator1, + _RandomAccessIterator2, _RandomAccessIterator2, _Compare, _IsVector, + /* is_parallel = */ std::true_type) noexcept; } // namespace __internal } // namespace __pstl diff --git a/pstl/include/pstl/internal/algorithm_impl.h b/pstl/include/pstl/internal/algorithm_impl.h index 46f4224..d5d9a31 100644 --- a/pstl/include/pstl/internal/algorithm_impl.h +++ b/pstl/include/pstl/internal/algorithm_impl.h @@ -43,9 +43,9 @@ __brick_any_of(const _ForwardIterator __first, const _ForwardIterator __last, _P return std::any_of(__first, __last, __pred); }; -template +template bool -__brick_any_of(const _ForwardIterator __first, const _ForwardIterator __last, _Pred __pred, +__brick_any_of(const _RandomAccessIterator __first, const _RandomAccessIterator __last, _Pred __pred, /*__is_vector=*/std::true_type) noexcept { return __unseq_backend::__simd_or(__first, __last - __first, __pred); @@ -59,14 +59,14 @@ __pattern_any_of(_ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterator return __internal::__brick_any_of(__first, __last, __pred, __is_vector); } -template +template bool -__pattern_any_of(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Pred __pred, +__pattern_any_of(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last, _Pred __pred, _IsVector __is_vector, /*parallel=*/std::true_type) { return __internal::__except_handler([&]() { return __internal::__parallel_or(std::forward<_ExecutionPolicy>(__exec), __first, __last, - [__pred, __is_vector](_ForwardIterator __i, _ForwardIterator __j) { + [__pred, __is_vector](_RandomAccessIterator __i, _RandomAccessIterator __j) { return __internal::__brick_any_of(__i, __j, __pred, __is_vector); }); }); @@ -113,15 +113,15 @@ __pattern_walk1(_ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterator _ __internal::__brick_walk1(__first, __last, __f, __is_vector); } -template +template void -__pattern_walk1(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Function __f, +__pattern_walk1(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last, _Function __f, _IsVector __is_vector, /*parallel=*/std::true_type) { __internal::__except_handler([&]() { __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __first, __last, - [__f, __is_vector](_ForwardIterator __i, _ForwardIterator __j) { + [__f, __is_vector](_RandomAccessIterator __i, _RandomAccessIterator __j) { __internal::__brick_walk1(__i, __j, __f, __is_vector); }); }); @@ -135,14 +135,16 @@ __pattern_walk_brick(_ExecutionPolicy&&, _ForwardIterator __first, _ForwardItera __brick(__first, __last); } -template +template void -__pattern_walk_brick(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Brick __brick, +__pattern_walk_brick(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last, + _Brick __brick, /*parallel=*/std::true_type) { __internal::__except_handler([&]() { - __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __first, __last, - [__brick](_ForwardIterator __i, _ForwardIterator __j) { __brick(__i, __j); }); + __par_backend::__parallel_for( + std::forward<_ExecutionPolicy>(__exec), __first, __last, + [__brick](_RandomAccessIterator __i, _RandomAccessIterator __j) { __brick(__i, __j); }); }); } @@ -220,9 +222,10 @@ __brick_walk2(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIte return __first2; } -template -_ForwardIterator2 -__brick_walk2(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _Function __f, +template +_RandomAccessIterator2 +__brick_walk2(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, + _Function __f, /*vector=*/std::true_type) noexcept { return __unseq_backend::__simd_walk_2(__first1, __last1 - __first1, __first2, __f); @@ -238,9 +241,9 @@ __brick_walk2_n(_ForwardIterator1 __first1, _Size __n, _ForwardIterator2 __first return __first2; } -template -_ForwardIterator2 -__brick_walk2_n(_ForwardIterator1 __first1, _Size __n, _ForwardIterator2 __first2, _Function __f, +template +_RandomAccessIterator2 +__brick_walk2_n(_RandomAccessIterator1 __first1, _Size __n, _RandomAccessIterator2 __first2, _Function __f, /*vector=*/std::true_type) noexcept { return __unseq_backend::__simd_walk_2(__first1, __n, __first2, __f); @@ -254,15 +257,16 @@ __pattern_walk2(_ExecutionPolicy&&, _ForwardIterator1 __first1, _ForwardIterator return __internal::__brick_walk2(__first1, __last1, __first2, __f, __is_vector); } -template -_ForwardIterator2 -__pattern_walk2(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _Function __f, _IsVector __is_vector, /*parallel=*/std::true_type) +template +_RandomAccessIterator2 +__pattern_walk2(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, + _RandomAccessIterator2 __first2, _Function __f, _IsVector __is_vector, /*parallel=*/std::true_type) { return __internal::__except_handler([&]() { __par_backend::__parallel_for( std::forward<_ExecutionPolicy>(__exec), __first1, __last1, - [__f, __first1, __first2, __is_vector](_ForwardIterator1 __i, _ForwardIterator1 __j) { + [__f, __first1, __first2, __is_vector](_RandomAccessIterator1 __i, _RandomAccessIterator1 __j) { __internal::__brick_walk2(__i, __j, __first2 + (__i - __first1), __f, __is_vector); }); return __first2 + (__last1 - __first1); @@ -281,8 +285,8 @@ __pattern_walk2_n(_ExecutionPolicy&&, _ForwardIterator1 __first1, _Size __n, _Fo template _RandomAccessIterator2 -__pattern_walk2_n(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first1, _Size __n, _RandomAccessIterator2 __first2, - _Function __f, _IsVector is_vector, /*parallel=*/std::true_type) +__pattern_walk2_n(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first1, _Size __n, + _RandomAccessIterator2 __first2, _Function __f, _IsVector is_vector, /*parallel=*/std::true_type) { return __internal::__pattern_walk2(std::forward<_ExecutionPolicy>(__exec), __first1, __first1 + __n, __first2, __f, is_vector, std::true_type()); @@ -513,19 +517,19 @@ __pattern_find_if(_ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterator return __internal::__brick_find_if(__first, __last, __pred, __is_vector); } -template -_ForwardIterator -__pattern_find_if(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, - _IsVector __is_vector, +template +_RandomAccessIterator +__pattern_find_if(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last, + _Predicate __pred, _IsVector __is_vector, /*is_parallel=*/std::true_type) { return __internal::__except_handler([&]() { return __internal::__parallel_find( std::forward<_ExecutionPolicy>(__exec), __first, __last, - [__pred, __is_vector](_ForwardIterator __i, _ForwardIterator __j) { + [__pred, __is_vector](_RandomAccessIterator __i, _RandomAccessIterator __j) { return __internal::__brick_find_if(__i, __j, __pred, __is_vector); }, - std::less::difference_type>(), + std::less::difference_type>(), /*is_first=*/true); }); } @@ -634,10 +638,10 @@ __brick_find_end(_ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIt return std::find_end(__first, __last, __s_first, __s_last, __pred); } -template -_ForwardIterator1 -__brick_find_end(_ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __s_first, - _ForwardIterator2 __s_last, _BinaryPredicate __pred, /*__is_vector=*/std::true_type) noexcept +template +_RandomAccessIterator1 +__brick_find_end(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __s_first, + _RandomAccessIterator2 __s_last, _BinaryPredicate __pred, /*__is_vector=*/std::true_type) noexcept { return __find_subrange(__first, __last, __last, __s_first, __s_last, __pred, false, std::true_type()); } @@ -652,11 +656,11 @@ __pattern_find_end(_ExecutionPolicy&&, _ForwardIterator1 __first, _ForwardIterat return __internal::__brick_find_end(__first, __last, __s_first, __s_last, __pred, __is_vector); } -template -_ForwardIterator1 -__pattern_find_end(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, - _ForwardIterator2 __s_first, _ForwardIterator2 __s_last, _BinaryPredicate __pred, +_RandomAccessIterator1 +__pattern_find_end(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first, _RandomAccessIterator1 __last, + _RandomAccessIterator2 __s_first, _RandomAccessIterator2 __s_last, _BinaryPredicate __pred, _IsVector __is_vector, /*is_parallel=*/std::true_type) noexcept { if (__last - __first == __s_last - __s_first) @@ -670,11 +674,13 @@ __pattern_find_end(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _Forwar return __internal::__except_handler([&]() { return __internal::__parallel_find( std::forward<_ExecutionPolicy>(__exec), __first, __last, - [__last, __s_first, __s_last, __pred, __is_vector](_ForwardIterator1 __i, _ForwardIterator1 __j) { + [__last, __s_first, __s_last, __pred, __is_vector](_RandomAccessIterator1 __i, + _RandomAccessIterator1 __j) { return __internal::__find_subrange(__i, __j, __last, __s_first, __s_last, __pred, false, __is_vector); }, - std::greater::difference_type>(), /*is_first=*/false); + std::greater::difference_type>(), + /*is_first=*/false); }); } } @@ -690,10 +696,10 @@ __brick_find_first_of(_ForwardIterator1 __first, _ForwardIterator1 __last, _Forw return std::find_first_of(__first, __last, __s_first, __s_last, __pred); } -template -_ForwardIterator1 -__brick_find_first_of(_ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __s_first, - _ForwardIterator2 __s_last, _BinaryPredicate __pred, /*__is_vector=*/std::true_type) noexcept +template +_RandomAccessIterator1 +__brick_find_first_of(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __s_first, + _RandomAccessIterator2 __s_last, _BinaryPredicate __pred, /*__is_vector=*/std::true_type) noexcept { return __unseq_backend::__simd_find_first_of(__first, __last, __s_first, __s_last, __pred); } @@ -708,38 +714,38 @@ __pattern_find_first_of(_ExecutionPolicy&&, _ForwardIterator1 __first, _ForwardI return __internal::__brick_find_first_of(__first, __last, __s_first, __s_last, __pred, __is_vector); } -template -_ForwardIterator1 -__pattern_find_first_of(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, - _ForwardIterator2 __s_first, _ForwardIterator2 __s_last, _BinaryPredicate __pred, +_RandomAccessIterator1 +__pattern_find_first_of(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first, _RandomAccessIterator1 __last, + _RandomAccessIterator2 __s_first, _RandomAccessIterator2 __s_last, _BinaryPredicate __pred, _IsVector __is_vector, /*is_parallel=*/std::true_type) noexcept { return __internal::__except_handler([&]() { return __internal::__parallel_find( std::forward<_ExecutionPolicy>(__exec), __first, __last, - [__s_first, __s_last, __pred, __is_vector](_ForwardIterator1 __i, _ForwardIterator1 __j) { + [__s_first, __s_last, __pred, __is_vector](_RandomAccessIterator1 __i, _RandomAccessIterator1 __j) { return __internal::__brick_find_first_of(__i, __j, __s_first, __s_last, __pred, __is_vector); }, - std::less::difference_type>(), /*is_first=*/true); + std::less::difference_type>(), /*is_first=*/true); }); } //------------------------------------------------------------------------ // search //------------------------------------------------------------------------ -template -_ForwardIterator1 -__brick_search(_ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __s_first, - _ForwardIterator2 __s_last, _BinaryPredicate __pred, /*vector=*/std::false_type) noexcept +template +_RandomAccessIterator1 +__brick_search(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __s_first, + _RandomAccessIterator2 __s_last, _BinaryPredicate __pred, /*vector=*/std::false_type) noexcept { return std::search(__first, __last, __s_first, __s_last, __pred); } -template -_ForwardIterator1 -__brick_search(_ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __s_first, - _ForwardIterator2 __s_last, _BinaryPredicate __pred, /*vector=*/std::true_type) noexcept +template +_RandomAccessIterator1 +__brick_search(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __s_first, + _RandomAccessIterator2 __s_last, _BinaryPredicate __pred, /*vector=*/std::true_type) noexcept { return __internal::__find_subrange(__first, __last, __last, __s_first, __s_last, __pred, true, std::true_type()); } @@ -754,11 +760,11 @@ __pattern_search(_ExecutionPolicy&&, _ForwardIterator1 __first, _ForwardIterator return __internal::__brick_search(__first, __last, __s_first, __s_last, __pred, __is_vector); } -template -_ForwardIterator1 -__pattern_search(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, - _ForwardIterator2 __s_first, _ForwardIterator2 __s_last, _BinaryPredicate __pred, +_RandomAccessIterator1 +__pattern_search(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first, _RandomAccessIterator1 __last, + _RandomAccessIterator2 __s_first, _RandomAccessIterator2 __s_last, _BinaryPredicate __pred, _IsVector __is_vector, /*is_parallel=*/std::true_type) noexcept { @@ -773,11 +779,12 @@ __pattern_search(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardI return __internal::__except_handler([&]() { return __internal::__parallel_find( std::forward<_ExecutionPolicy>(__exec), __first, __last, - [__last, __s_first, __s_last, __pred, __is_vector](_ForwardIterator1 __i, _ForwardIterator1 __j) { + [__last, __s_first, __s_last, __pred, __is_vector](_RandomAccessIterator1 __i, + _RandomAccessIterator1 __j) { return __internal::__find_subrange(__i, __j, __last, __s_first, __s_last, __pred, true, __is_vector); }, - std::less::difference_type>(), /*is_first=*/true); + std::less::difference_type>(), /*is_first=*/true); }); } } @@ -793,9 +800,9 @@ __brick_search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __coun return std::search_n(__first, __last, __count, __value, __pred); } -template -_ForwardIterator -__brick_search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value, +template +_RandomAccessIterator +__brick_search_n(_RandomAccessIterator __first, _RandomAccessIterator __last, _Size __count, const _Tp& __value, _BinaryPredicate __pred, /*vector=*/std::true_type) noexcept { return __internal::__find_subrange(__first, __last, __last, __count, __value, __pred, std::true_type()); @@ -850,12 +857,14 @@ __brick_copy_n(_ForwardIterator __first, _Size __n, _OutputIterator __result, /* return std::copy_n(__first, __n, __result); } -template -_OutputIterator -__brick_copy_n(_ForwardIterator __first, _Size __n, _OutputIterator __result, /*vector=*/std::true_type) noexcept +template +_RandomAccessIterator2 +__brick_copy_n(_RandomAccessIterator1 __first, _Size __n, _RandomAccessIterator2 __result, + /*vector=*/std::true_type) noexcept { return __unseq_backend::__simd_assign( - __first, __n, __result, [](_ForwardIterator __first, _OutputIterator __result) { *__result = *__first; }); + __first, __n, __result, + [](_RandomAccessIterator1 __first, _RandomAccessIterator2 __result) { *__result = *__first; }); } //------------------------------------------------------------------------ @@ -869,14 +878,14 @@ __brick_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator return std::copy(__first, __last, __result); } -template -_OutputIterator -__brick_copy(_RandomAccessIterator __first, _RandomAccessIterator __last, _OutputIterator __result, +template +_RandomAccessIterator2 +__brick_copy(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __result, /*vector=*/std::true_type) noexcept { return __unseq_backend::__simd_assign( __first, __last - __first, __result, - [](_RandomAccessIterator __first, _OutputIterator __result) { *__result = *__first; }); + [](_RandomAccessIterator1 __first, _RandomAccessIterator2 __result) { *__result = *__first; }); } //------------------------------------------------------------------------ @@ -890,36 +899,38 @@ __brick_move(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator return std::move(__first, __last, __result); } -template -_OutputIterator -__brick_move(_RandomAccessIterator __first, _RandomAccessIterator __last, _OutputIterator __result, +template +_RandomAccessIterator2 +__brick_move(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __result, /*vector=*/std::true_type) noexcept { return __unseq_backend::__simd_assign( __first, __last - __first, __result, - [](_RandomAccessIterator __first, _OutputIterator __result) { *__result = std::move(*__first); }); + [](_RandomAccessIterator1 __first, _RandomAccessIterator2 __result) { *__result = std::move(*__first); }); } struct __brick_move_destroy { - template - _OutputIterator - operator()(_Iterator __first, _Iterator __last, _OutputIterator __result, /*vec*/ std::true_type) const + template + _RandomAccessIterator2 + operator()(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __result, + /*vec*/ std::true_type) const { - using _IteratorValueType = typename std::iterator_traits<_Iterator>::value_type; + using _IteratorValueType = typename std::iterator_traits<_RandomAccessIterator1>::value_type; return __unseq_backend::__simd_assign(__first, __last - __first, __result, - [](_Iterator __first, _OutputIterator __result) { + [](_RandomAccessIterator1 __first, _RandomAccessIterator2 __result) { *__result = std::move(*__first); (*__first).~_IteratorValueType(); }); } - template - _OutputIterator - operator()(_Iterator __first, _Iterator __last, _OutputIterator __result, /*vec*/ std::false_type) const + template + _RandomAccessIterator2 + operator()(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __result, + /*vec*/ std::false_type) const { - using _IteratorValueType = typename std::iterator_traits<_Iterator>::value_type; + using _IteratorValueType = typename std::iterator_traits<_RandomAccessIterator1>::value_type; for (; __first != __last; ++__first, ++__result) { @@ -941,14 +952,14 @@ __brick_swap_ranges(_ForwardIterator __first, _ForwardIterator __last, _OutputIt return std::swap_ranges(__first, __last, __result); } -template -_OutputIterator -__brick_swap_ranges(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, +template +_RandomAccessIterator2 +__brick_swap_ranges(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __result, /*vector=*/std::true_type) noexcept { using std::iter_swap; return __unseq_backend::__simd_assign(__first, __last - __first, __result, - iter_swap<_ForwardIterator, _OutputIterator>); + iter_swap<_RandomAccessIterator1, _RandomAccessIterator2>); } //------------------------------------------------------------------------ @@ -962,9 +973,10 @@ __brick_copy_if(_ForwardIterator __first, _ForwardIterator __last, _OutputIterat return std::copy_if(__first, __last, __result, __pred); } -template -_OutputIterator -__brick_copy_if(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _UnaryPredicate __pred, +template +_RandomAccessIterator2 +__brick_copy_if(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __result, + _UnaryPredicate __pred, /*vector=*/std::true_type) noexcept { #if (_PSTL_MONOTONIC_PRESENT) @@ -1021,9 +1033,9 @@ __brick_copy_by_mask(_ForwardIterator __first, _ForwardIterator __last, _OutputI } } -template +template void -__brick_copy_by_mask(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, +__brick_copy_by_mask(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __result, bool* __restrict __mask, _Assigner __assigner, /*vector=*/std::true_type) noexcept { #if (_PSTL_MONOTONIC_PRESENT) @@ -1053,10 +1065,11 @@ __brick_partition_by_mask(_ForwardIterator __first, _ForwardIterator __last, _Ou } } -template +template void -__brick_partition_by_mask(_RandomAccessIterator __first, _RandomAccessIterator __last, _OutputIterator1 __out_true, - _OutputIterator2 __out_false, bool* __mask, /*vector=*/std::true_type) noexcept +__brick_partition_by_mask(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, + _RandomAccessIterator2 __out_true, _RandomAccessIterator3 __out_false, bool* __mask, + /*vector=*/std::true_type) noexcept { #if (_PSTL_MONOTONIC_PRESENT) __unseq_backend::__simd_partition_by_mask(__first, __last - __first, __out_true, __out_false, __mask); @@ -1073,13 +1086,14 @@ __pattern_copy_if(_ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterator return __internal::__brick_copy_if(__first, __last, __result, __pred, __is_vector); } -template -_OutputIterator -__pattern_copy_if(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last, - _OutputIterator __result, _UnaryPredicate __pred, _IsVector __is_vector, /*parallel=*/std::true_type) +_RandomAccessIterator2 +__pattern_copy_if(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first, _RandomAccessIterator1 __last, + _RandomAccessIterator2 __result, _UnaryPredicate __pred, _IsVector __is_vector, + /*parallel=*/std::true_type) { - typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _DifferenceType; + typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _DifferenceType; const _DifferenceType __n = __last - __first; if (_DifferenceType(1) < __n) { @@ -1098,7 +1112,7 @@ __pattern_copy_if(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _Ran [=](_DifferenceType __i, _DifferenceType __len, _DifferenceType __initial) { // Scan __internal::__brick_copy_by_mask( __first + __i, __first + (__i + __len), __result + __initial, __mask + __i, - [](_RandomAccessIterator __x, _OutputIterator __z) { *__z = *__x; }, __is_vector); + [](_RandomAccessIterator1 __x, _RandomAccessIterator2 __z) { *__z = *__x; }, __is_vector); }, [&__m](_DifferenceType __total) { __m = __total; }); return __result + __m; @@ -1111,9 +1125,9 @@ __pattern_copy_if(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _Ran //------------------------------------------------------------------------ // count //------------------------------------------------------------------------ -template -typename std::iterator_traits<_ForwardIterator>::difference_type -__brick_count(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, +template +typename std::iterator_traits<_RandomAccessIterator>::difference_type +__brick_count(_RandomAccessIterator __first, _RandomAccessIterator __last, _Predicate __pred, /* is_vector = */ std::true_type) noexcept { return __unseq_backend::__simd_count(__first, __last - __first, __pred); @@ -1135,18 +1149,18 @@ __pattern_count(_ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterator _ return __internal::__brick_count(__first, __last, __pred, __is_vector); } -template -typename std::iterator_traits<_ForwardIterator>::difference_type -__pattern_count(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, +template +typename std::iterator_traits<_RandomAccessIterator>::difference_type +__pattern_count(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last, + _Predicate __pred, /* is_parallel */ std::true_type, _IsVector __is_vector) { - typedef typename std::iterator_traits<_ForwardIterator>::difference_type _SizeType; + typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _SizeType; return __internal::__except_handler([&]() { return __par_backend::__parallel_reduce( std::forward<_ExecutionPolicy>(__exec), __first, __last, _SizeType(0), - [__pred, __is_vector](_ForwardIterator __begin, _ForwardIterator __end, _SizeType __value) -> _SizeType { - return __value + __internal::__brick_count(__begin, __end, __pred, __is_vector); - }, + [__pred, __is_vector](_RandomAccessIterator __begin, _RandomAccessIterator __end, _SizeType __value) + -> _SizeType { return __value + __internal::__brick_count(__begin, __end, __pred, __is_vector); }, std::plus<_SizeType>()); }); } @@ -1155,17 +1169,17 @@ __pattern_count(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIte // unique //------------------------------------------------------------------------ -template -_ForwardIterator -__brick_unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred, +template +_RandomAccessIterator +__brick_unique(_RandomAccessIterator __first, _RandomAccessIterator __last, _BinaryPredicate __pred, /*is_vector=*/std::false_type) noexcept { return std::unique(__first, __last, __pred); } -template -_ForwardIterator -__brick_unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred, +template +_RandomAccessIterator +__brick_unique(_RandomAccessIterator __first, _RandomAccessIterator __last, _BinaryPredicate __pred, /*is_vector=*/std::true_type) noexcept { _PSTL_PRAGMA_MESSAGE("Vectorized algorithm unimplemented, redirected to serial"); @@ -1254,23 +1268,20 @@ __remove_elements(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardI __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); - }); + __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; }); } -template -_ForwardIterator -__pattern_unique(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred, - _IsVector __is_vector, /*is_parallel=*/std::true_type) noexcept +template +_RandomAccessIterator +__pattern_unique(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last, + _BinaryPredicate __pred, _IsVector __is_vector, /*is_parallel=*/std::true_type) noexcept { - typedef typename std::iterator_traits<_ForwardIterator>::reference _ReferenceType; + typedef typename std::iterator_traits<_RandomAccessIterator>::reference _ReferenceType; if (__first == __last) { @@ -1283,7 +1294,7 @@ __pattern_unique(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIt } return __internal::__remove_elements( std::forward<_ExecutionPolicy>(__exec), ++__first, __last, - [&__pred, __is_vector](bool* __b, bool* __e, _ForwardIterator __it) { + [&__pred, __is_vector](bool* __b, bool* __e, _RandomAccessIterator __it) { __internal::__brick_walk3( __b, __e, __it - 1, __it, [&__pred](bool& __x, _ReferenceType __y, _ReferenceType __z) { __x = !__pred(__y, __z); }, __is_vector); @@ -1303,9 +1314,9 @@ __brick_unique_copy(_ForwardIterator __first, _ForwardIterator __last, OutputIte return std::unique_copy(__first, __last, __result, __pred); } -template -OutputIterator -__brick_unique_copy(_RandomAccessIterator __first, _RandomAccessIterator __last, OutputIterator __result, +template +_RandomAccessIterator2 +__brick_unique_copy(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __result, _BinaryPredicate __pred, /*vector=*/std::true_type) noexcept { #if (_PSTL_MONOTONIC_PRESENT) @@ -1346,14 +1357,14 @@ __brick_calc_mask_2(_RandomAccessIterator __first, _RandomAccessIterator __last, return __unseq_backend::__simd_calc_mask_2(__first, __last - __first, __mask, __pred); } -template -_OutputIterator -__pattern_unique_copy(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last, - _OutputIterator __result, _BinaryPredicate __pred, _IsVector __is_vector, +_RandomAccessIterator2 +__pattern_unique_copy(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first, _RandomAccessIterator1 __last, + _RandomAccessIterator2 __result, _BinaryPredicate __pred, _IsVector __is_vector, /*parallel=*/std::true_type) { - typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _DifferenceType; + typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _DifferenceType; const _DifferenceType __n = __last - __first; if (_DifferenceType(2) < __n) { @@ -1385,7 +1396,7 @@ __pattern_unique_copy(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, // Phase 2 is same as for __pattern_copy_if __internal::__brick_copy_by_mask( __first + __i, __first + (__i + __len), __result + __initial, __mask + __i, - [](_RandomAccessIterator __x, _OutputIterator __z) { *__z = *__x; }, __is_vector); + [](_RandomAccessIterator1 __x, _RandomAccessIterator2 __z) { *__z = *__x; }, __is_vector); }, [&__m](_DifferenceType __total) { __m = __total; }); return __result + __m; @@ -1406,14 +1417,14 @@ __brick_reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, / std::reverse(__first, __last); } -template +template void -__brick_reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, /*__is_vector=*/std::true_type) noexcept +__brick_reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, /*__is_vector=*/std::true_type) noexcept { - typedef typename std::iterator_traits<_BidirectionalIterator>::reference _ReferenceType; + typedef typename std::iterator_traits<_RandomAccessIterator>::reference _ReferenceType; const auto __n = (__last - __first) / 2; - __unseq_backend::__simd_walk_2(__first, __n, std::reverse_iterator<_BidirectionalIterator>(__last), + __unseq_backend::__simd_walk_2(__first, __n, std::reverse_iterator<_RandomAccessIterator>(__last), [](_ReferenceType __x, _ReferenceType __y) { using std::swap; swap(__x, __y); @@ -1434,14 +1445,14 @@ __brick_reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, _ } // this brick is called in parallel version, so we can use iterator arithmetic -template +template void -__brick_reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, _BidirectionalIterator __d_last, +__brick_reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __d_last, /*is_vector=*/std::true_type) noexcept { - typedef typename std::iterator_traits<_BidirectionalIterator>::reference _ReferenceType; + typedef typename std::iterator_traits<_RandomAccessIterator>::reference _ReferenceType; - __unseq_backend::__simd_walk_2(__first, __last - __first, std::reverse_iterator<_BidirectionalIterator>(__d_last), + __unseq_backend::__simd_walk_2(__first, __last - __first, std::reverse_iterator<_RandomAccessIterator>(__d_last), [](_ReferenceType __x, _ReferenceType __y) { using std::swap; swap(__x, __y); @@ -1457,14 +1468,14 @@ __pattern_reverse(_ExecutionPolicy&&, _BidirectionalIterator __first, _Bidirecti __internal::__brick_reverse(__first, __last, _is_vector); } -template +template void -__pattern_reverse(_ExecutionPolicy&& __exec, _BidirectionalIterator __first, _BidirectionalIterator __last, +__pattern_reverse(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last, _IsVector __is_vector, /*is_parallel=*/std::true_type) { __par_backend::__parallel_for( std::forward<_ExecutionPolicy>(__exec), __first, __first + (__last - __first) / 2, - [__is_vector, __first, __last](_BidirectionalIterator __inner_first, _BidirectionalIterator __inner_last) { + [__is_vector, __first, __last](_RandomAccessIterator __inner_first, _RandomAccessIterator __inner_last) { __internal::__brick_reverse(__inner_first, __inner_last, __last - (__inner_first - __first), __is_vector); }); } @@ -1481,15 +1492,15 @@ __brick_reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __la return std::reverse_copy(__first, __last, __d_first); } -template -_OutputIterator -__brick_reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __d_first, +template +_RandomAccessIterator2 +__brick_reverse_copy(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __d_first, /*is_vector=*/std::true_type) noexcept { - typedef typename std::iterator_traits<_BidirectionalIterator>::reference _ReferenceType1; - typedef typename std::iterator_traits<_OutputIterator>::reference _ReferenceType2; + typedef typename std::iterator_traits<_RandomAccessIterator1>::reference _ReferenceType1; + typedef typename std::iterator_traits<_RandomAccessIterator2>::reference _ReferenceType2; - return __unseq_backend::__simd_walk_2(std::reverse_iterator<_BidirectionalIterator>(__last), __last - __first, + return __unseq_backend::__simd_walk_2(std::reverse_iterator<_RandomAccessIterator1>(__last), __last - __first, __d_first, [](_ReferenceType1 __x, _ReferenceType2 __y) { __y = __x; }); } @@ -1501,15 +1512,15 @@ __pattern_reverse_copy(_ExecutionPolicy&&, _BidirectionalIterator __first, _Bidi return __internal::__brick_reverse_copy(__first, __last, __d_first, __is_vector); } -template -_OutputIterator -__pattern_reverse_copy(_ExecutionPolicy&& __exec, _BidirectionalIterator __first, _BidirectionalIterator __last, - _OutputIterator __d_first, _IsVector __is_vector, /*is_parallel=*/std::true_type) +template +_RandomAccessIterator2 +__pattern_reverse_copy(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first, _RandomAccessIterator1 __last, + _RandomAccessIterator2 __d_first, _IsVector __is_vector, /*is_parallel=*/std::true_type) { auto __len = __last - __first; __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __first, __last, - [__is_vector, __first, __len, __d_first](_BidirectionalIterator __inner_first, - _BidirectionalIterator __inner_last) { + [__is_vector, __first, __len, __d_first](_RandomAccessIterator1 __inner_first, + _RandomAccessIterator1 __inner_last) { __internal::__brick_reverse_copy(__inner_first, __inner_last, __d_first + (__len - (__inner_last - __first)), __is_vector); @@ -1533,14 +1544,14 @@ __brick_rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIter #endif } -template -_ForwardIterator -__brick_rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, +template +_RandomAccessIterator +__brick_rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, /*is_vector=*/std::true_type) noexcept { auto __n = __last - __first; auto __m = __middle - __first; - const _ForwardIterator __ret = __first + (__last - __middle); + const _RandomAccessIterator __ret = __first + (__last - __middle); bool __is_left = (__m <= __n / 2); if (!__is_left) @@ -1555,7 +1566,7 @@ __brick_rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIter for (; __last - __first >= __m_2; __first += __m) { __unseq_backend::__simd_assign(__first, __m, __first + __m, - iter_swap<_ForwardIterator, _ForwardIterator>); + iter_swap<_RandomAccessIterator, _RandomAccessIterator>); } } else @@ -1563,7 +1574,7 @@ __brick_rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIter for (; __last - __first >= __m_2; __last -= __m) { __unseq_backend::__simd_assign(__last - __m, __m, __last - __m_2, - iter_swap<_ForwardIterator, _ForwardIterator>); + iter_swap<_RandomAccessIterator, _RandomAccessIterator>); } } __is_left = !__is_left; @@ -1582,12 +1593,12 @@ __pattern_rotate(_ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterator return __internal::__brick_rotate(__first, __middle, __last, __is_vector); } -template -_ForwardIterator -__pattern_rotate(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __middle, - _ForwardIterator __last, _IsVector __is_vector, /*is_parallel=*/std::true_type) +template +_RandomAccessIterator +__pattern_rotate(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __middle, + _RandomAccessIterator __last, _IsVector __is_vector, /*is_parallel=*/std::true_type) { - typedef typename std::iterator_traits<_ForwardIterator>::value_type _Tp; + typedef typename std::iterator_traits<_RandomAccessIterator>::value_type _Tp; auto __n = __last - __first; auto __m = __middle - __first; if (__m <= __n / 2) @@ -1597,20 +1608,19 @@ __pattern_rotate(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIt _Tp* __result = __buf.get(); __par_backend::__parallel_for( std::forward<_ExecutionPolicy>(__exec), __middle, __last, - [__middle, __result, __is_vector](_ForwardIterator __b, _ForwardIterator __e) { + [__middle, __result, __is_vector](_RandomAccessIterator __b, _RandomAccessIterator __e) { __internal::__brick_uninitialized_move(__b, __e, __result + (__b - __middle), __is_vector); }); - __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __first, __middle, - [__last, __middle, __is_vector](_ForwardIterator __b, _ForwardIterator __e) { - __internal::__brick_move(__b, __e, __b + (__last - __middle), - __is_vector); - }); + __par_backend::__parallel_for( + std::forward<_ExecutionPolicy>(__exec), __first, __middle, + [__last, __middle, __is_vector](_RandomAccessIterator __b, _RandomAccessIterator __e) { + __internal::__brick_move(__b, __e, __b + (__last - __middle), __is_vector); + }); __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __result, __result + (__n - __m), [__first, __result, __is_vector](_Tp* __b, _Tp* __e) { - __brick_move_destroy()( - __b, __e, __first + (__b - __result), __is_vector); + __brick_move_destroy()(__b, __e, __first + (__b - __result), __is_vector); }); return __first + (__last - __middle); @@ -1621,17 +1631,17 @@ __pattern_rotate(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIt __par_backend::__buffer<_Tp> __buf(__m); return __internal::__except_handler([&__exec, __n, __m, __first, __middle, __last, __is_vector, &__buf]() { _Tp* __result = __buf.get(); - __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __first, __middle, - [__first, __result, __is_vector](_ForwardIterator __b, _ForwardIterator __e) { - __internal::__brick_uninitialized_move( - __b, __e, __result + (__b - __first), __is_vector); - }); + __par_backend::__parallel_for( + std::forward<_ExecutionPolicy>(__exec), __first, __middle, + [__first, __result, __is_vector](_RandomAccessIterator __b, _RandomAccessIterator __e) { + __internal::__brick_uninitialized_move(__b, __e, __result + (__b - __first), __is_vector); + }); - __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __middle, __last, - [__first, __middle, __is_vector](_ForwardIterator __b, _ForwardIterator __e) { - __internal::__brick_move(__b, __e, __first + (__b - __middle), - __is_vector); - }); + __par_backend::__parallel_for( + std::forward<_ExecutionPolicy>(__exec), __middle, __last, + [__first, __middle, __is_vector](_RandomAccessIterator __b, _RandomAccessIterator __e) { + __internal::__brick_move(__b, __e, __first + (__b - __middle), __is_vector); + }); __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __result, __result + __m, [__n, __m, __first, __result, __is_vector](_Tp* __b, _Tp* __e) { @@ -1656,12 +1666,12 @@ __brick_rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _Forwar return std::rotate_copy(__first, __middle, __last, __result); } -template -_OutputIterator -__brick_rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, - _OutputIterator __result, /*__is_vector=*/std::true_type) noexcept +template +_RandomAccessIterator2 +__brick_rotate_copy(_RandomAccessIterator1 __first, _RandomAccessIterator1 __middle, _RandomAccessIterator1 __last, + _RandomAccessIterator2 __result, /*__is_vector=*/std::true_type) noexcept { - _OutputIterator __res = __internal::__brick_copy(__middle, __last, __result, std::true_type()); + _RandomAccessIterator2 __res = __internal::__brick_copy(__middle, __last, __result, std::true_type()); return __internal::__brick_copy(__first, __middle, __res, std::true_type()); } @@ -1673,22 +1683,22 @@ __pattern_rotate_copy(_ExecutionPolicy&&, _ForwardIterator __first, _ForwardIter return __internal::__brick_rotate_copy(__first, __middle, __last, __result, __is_vector); } -template -_OutputIterator -__pattern_rotate_copy(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __middle, - _ForwardIterator __last, _OutputIterator __result, _IsVector __is_vector, +template +_RandomAccessIterator2 +__pattern_rotate_copy(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first, _RandomAccessIterator1 __middle, + _RandomAccessIterator1 __last, _RandomAccessIterator2 __result, _IsVector __is_vector, /*is_parallel=*/std::true_type) { __par_backend::__parallel_for( std::forward<_ExecutionPolicy>(__exec), __first, __last, - [__first, __last, __middle, __result, __is_vector](_ForwardIterator __b, _ForwardIterator __e) { + [__first, __last, __middle, __result, __is_vector](_RandomAccessIterator1 __b, _RandomAccessIterator1 __e) { if (__b > __middle) { __internal::__brick_copy(__b, __e, __result + (__b - __middle), __is_vector); } else { - _OutputIterator __new_result = __result + ((__last - __middle) + (__b - __first)); + _RandomAccessIterator2 __new_result = __result + ((__last - __middle) + (__b - __first)); if (__e < __middle) { __internal::__brick_copy(__b, __e, __new_result, __is_vector); @@ -1715,21 +1725,21 @@ __brick_is_partitioned(_ForwardIterator __first, _ForwardIterator __last, _Unary return std::is_partitioned(__first, __last, __pred); } -template +template bool -__brick_is_partitioned(_ForwardIterator __first, _ForwardIterator __last, _UnaryPredicate __pred, +__brick_is_partitioned(_RandomAccessIterator __first, _RandomAccessIterator __last, _UnaryPredicate __pred, /*is_vector=*/std::true_type) noexcept { - typedef typename std::iterator_traits<_ForwardIterator>::difference_type _SizeType; + typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _SizeType; if (__first == __last) { return true; } else { - _ForwardIterator __result = __unseq_backend::__simd_first( + _RandomAccessIterator __result = __unseq_backend::__simd_first( __first, _SizeType(0), __last - __first, - [&__pred](_ForwardIterator __it, _SizeType __i) { return !__pred(__it[__i]); }); + [&__pred](_RandomAccessIterator __it, _SizeType __i) { return !__pred(__it[__i]); }); if (__result == __last) { return true; @@ -1750,9 +1760,9 @@ __pattern_is_partitioned(_ExecutionPolicy&&, _ForwardIterator __first, _ForwardI return __internal::__brick_is_partitioned(__first, __last, __pred, __is_vector); } -template +template bool -__pattern_is_partitioned(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, +__pattern_is_partitioned(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last, _UnaryPredicate __pred, _IsVector __is_vector, /*is_parallel=*/std::true_type) { if (__first == __last) @@ -1785,7 +1795,7 @@ __pattern_is_partitioned(_ExecutionPolicy&& __exec, _ForwardIterator __first, _F __init = __par_backend::__parallel_reduce( std::forward<_ExecutionPolicy>(__exec), __first, __last, __init, - [&__pred, &__table, __is_vector](_ForwardIterator __i, _ForwardIterator __j, + [&__pred, &__table, __is_vector](_RandomAccessIterator __i, _RandomAccessIterator __j, _ReduceType __value) -> _ReduceType { if (__value == __broken) { @@ -1796,12 +1806,12 @@ __pattern_is_partitioned(_ExecutionPolicy&& __exec, _ForwardIterator __first, _F if (__pred(*__i)) { // find first element that don't satisfy pred - _ForwardIterator __x = + _RandomAccessIterator __x = __internal::__brick_find_if(__i + 1, __j, std::not_fn(__pred), __is_vector); if (__x != __j) { // find first element after "x" that satisfy pred - _ForwardIterator __y = __internal::__brick_find_if(__x + 1, __j, __pred, __is_vector); + _RandomAccessIterator __y = __internal::__brick_find_if(__x + 1, __j, __pred, __is_vector); // if it was found then range isn't partitioned by pred if (__y != __j) { @@ -1859,9 +1869,9 @@ __brick_partition(_ForwardIterator __first, _ForwardIterator __last, _UnaryPredi return std::partition(__first, __last, __pred); } -template -_ForwardIterator -__brick_partition(_ForwardIterator __first, _ForwardIterator __last, _UnaryPredicate __pred, +template +_RandomAccessIterator +__brick_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, _UnaryPredicate __pred, /*is_vector=*/std::true_type) noexcept { _PSTL_PRAGMA_MESSAGE("Vectorized algorithm unimplemented, redirected to serial"); @@ -1876,9 +1886,9 @@ __pattern_partition(_ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterat return __internal::__brick_partition(__first, __last, __pred, __is_vector); } -template -_ForwardIterator -__pattern_partition(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, +template +_RandomAccessIterator +__pattern_partition(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last, _UnaryPredicate __pred, _IsVector __is_vector, /*is_parallel=*/std::true_type) { @@ -1886,9 +1896,9 @@ __pattern_partition(_ExecutionPolicy&& __exec, _ForwardIterator __first, _Forwar // elements after pivot don't satisfy pred (false part) struct _PartitionRange { - _ForwardIterator __begin; - _ForwardIterator __pivot; - _ForwardIterator __end; + _RandomAccessIterator __begin; + _RandomAccessIterator __pivot; + _RandomAccessIterator __end; }; return __internal::__except_handler([&]() { @@ -1911,7 +1921,7 @@ __pattern_partition(_ExecutionPolicy&& __exec, _ForwardIterator __first, _Forwar { __par_backend::__parallel_for( std::forward<_ExecutionPolicy>(__exec), __val1.__pivot, __val1.__pivot + __size1, - [__val1, __val2, __size1, __is_vector](_ForwardIterator __i, _ForwardIterator __j) { + [__val1, __val2, __size1, __is_vector](_RandomAccessIterator __i, _RandomAccessIterator __j) { __internal::__brick_swap_ranges(__i, __j, (__val2.__pivot - __size1) + (__i - __val1.__pivot), __is_vector); }); @@ -1922,7 +1932,7 @@ __pattern_partition(_ExecutionPolicy&& __exec, _ForwardIterator __first, _Forwar { __par_backend::__parallel_for( std::forward<_ExecutionPolicy>(__exec), __val1.__pivot, __val1.__pivot + __size2, - [__val1, __val2, __is_vector](_ForwardIterator __i, _ForwardIterator __j) { + [__val1, __val2, __is_vector](_RandomAccessIterator __i, _RandomAccessIterator __j) { __internal::__brick_swap_ranges(__i, __j, __val2.__begin + (__i - __val1.__pivot), __is_vector); }); return {__new_begin, __val1.__pivot + __size2, __val2.__end}; @@ -1931,10 +1941,10 @@ __pattern_partition(_ExecutionPolicy&& __exec, _ForwardIterator __first, _Forwar _PartitionRange __result = __par_backend::__parallel_reduce( std::forward<_ExecutionPolicy>(__exec), __first, __last, __init, - [__pred, __is_vector, __reductor](_ForwardIterator __i, _ForwardIterator __j, + [__pred, __is_vector, __reductor](_RandomAccessIterator __i, _RandomAccessIterator __j, _PartitionRange __value) -> _PartitionRange { //1. serial partition - _ForwardIterator __pivot = __internal::__brick_partition(__i, __j, __pred, __is_vector); + _RandomAccessIterator __pivot = __internal::__brick_partition(__i, __j, __pred, __is_vector); // 2. merging of two ranges (left and right respectively) return __reductor(__value, {__i, __pivot, __j}); @@ -1956,9 +1966,9 @@ __brick_stable_partition(_BidirectionalIterator __first, _BidirectionalIterator return std::stable_partition(__first, __last, __pred); } -template -_BidirectionalIterator -__brick_stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _UnaryPredicate __pred, +template +_RandomAccessIterator +__brick_stable_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, _UnaryPredicate __pred, /*__is_vector=*/std::true_type) noexcept { _PSTL_PRAGMA_MESSAGE("Vectorized algorithm unimplemented, redirected to serial"); @@ -1974,9 +1984,9 @@ __pattern_stable_partition(_ExecutionPolicy&&, _BidirectionalIterator __first, _ return __internal::__brick_stable_partition(__first, __last, __pred, __is_vector); } -template -_BidirectionalIterator -__pattern_stable_partition(_ExecutionPolicy&& __exec, _BidirectionalIterator __first, _BidirectionalIterator __last, +template +_RandomAccessIterator +__pattern_stable_partition(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last, _UnaryPredicate __pred, _IsVector __is_vector, /*is_parallelization=*/std::true_type) noexcept { @@ -1984,9 +1994,9 @@ __pattern_stable_partition(_ExecutionPolicy&& __exec, _BidirectionalIterator __f // elements after pivot don't satisfy pred (false part) struct _PartitionRange { - _BidirectionalIterator __begin; - _BidirectionalIterator __pivot; - _BidirectionalIterator __end; + _RandomAccessIterator __begin; + _RandomAccessIterator __pivot; + _RandomAccessIterator __end; }; return __internal::__except_handler([&]() { @@ -2013,10 +2023,10 @@ __pattern_stable_partition(_ExecutionPolicy&& __exec, _BidirectionalIterator __f _PartitionRange __result = __par_backend::__parallel_reduce( std::forward<_ExecutionPolicy>(__exec), __first, __last, __init, - [&__pred, __is_vector, __reductor](_BidirectionalIterator __i, _BidirectionalIterator __j, + [&__pred, __is_vector, __reductor](_RandomAccessIterator __i, _RandomAccessIterator __j, _PartitionRange __value) -> _PartitionRange { //1. serial stable_partition - _BidirectionalIterator __pivot = __internal::__brick_stable_partition(__i, __j, __pred, __is_vector); + _RandomAccessIterator __pivot = __internal::__brick_stable_partition(__i, __j, __pred, __is_vector); // 2. merging of two ranges (left and right respectively) return __reductor(__value, {__i, __pivot, __j}); @@ -2038,10 +2048,12 @@ __brick_partition_copy(_ForwardIterator __first, _ForwardIterator __last, _Outpu return std::partition_copy(__first, __last, __out_true, __out_false, __pred); } -template -std::pair<_OutputIterator1, _OutputIterator2> -__brick_partition_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator1 __out_true, - _OutputIterator2 __out_false, _UnaryPredicate __pred, /*is_vector=*/std::true_type) noexcept +template +std::pair<_RandomAccessIterator2, _RandomAccessIterator3> +__brick_partition_copy(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __out_true, + _RandomAccessIterator3 __out_false, _UnaryPredicate __pred, + /*is_vector=*/std::true_type) noexcept { #if (_PSTL_MONOTONIC_PRESENT) return __unseq_backend::__simd_partition_copy(__first, __last - __first, __out_true, __out_false, __pred); @@ -2060,14 +2072,14 @@ __pattern_partition_copy(_ExecutionPolicy&&, _ForwardIterator __first, _ForwardI return __internal::__brick_partition_copy(__first, __last, __out_true, __out_false, __pred, __is_vector); } -template -std::pair<_OutputIterator1, _OutputIterator2> -__pattern_partition_copy(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last, - _OutputIterator1 __out_true, _OutputIterator2 __out_false, _UnaryPredicate __pred, +template +std::pair<_RandomAccessIterator2, _RandomAccessIterator3> +__pattern_partition_copy(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first, _RandomAccessIterator1 __last, + _RandomAccessIterator2 __out_true, _RandomAccessIterator3 __out_false, _UnaryPredicate __pred, _IsVector __is_vector, /*is_parallelization=*/std::true_type) { - typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _DifferenceType; + typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _DifferenceType; typedef std::pair<_DifferenceType, _DifferenceType> _ReturnType; const _DifferenceType __n = __last - __first; if (_DifferenceType(1) < __n) @@ -2196,10 +2208,11 @@ __pattern_partial_sort_copy(_ExecutionPolicy&&, _ForwardIterator __first, _Forwa return std::partial_sort_copy(__first, __last, __d_first, __d_last, __comp); } -template -_RandomAccessIterator -__pattern_partial_sort_copy(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, - _RandomAccessIterator __d_first, _RandomAccessIterator __d_last, _Compare __comp, +template +_RandomAccessIterator2 +__pattern_partial_sort_copy(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first, _RandomAccessIterator1 __last, + _RandomAccessIterator2 __d_first, _RandomAccessIterator2 __d_last, _Compare __comp, _IsVector __is_vector, /*is_parallel=*/std::true_type) { if (__last == __first || __d_last == __d_first) @@ -2213,10 +2226,10 @@ __pattern_partial_sort_copy(_ExecutionPolicy&& __exec, _ForwardIterator __first, { __par_backend::__parallel_stable_sort( std::forward<_ExecutionPolicy>(__exec), __d_first, __d_first + __n1, __comp, - [__first, __d_first, __is_vector](_RandomAccessIterator __i, _RandomAccessIterator __j, + [__first, __d_first, __is_vector](_RandomAccessIterator2 __i, _RandomAccessIterator2 __j, _Compare __comp) { - _ForwardIterator __i1 = __first + (__i - __d_first); - _ForwardIterator __j1 = __first + (__j - __d_first); + _RandomAccessIterator1 __i1 = __first + (__i - __d_first); + _RandomAccessIterator1 __j1 = __first + (__j - __d_first); // 1. Copy elements from input to output #if !_PSTL_ICC_18_OMP_SIMD_BROKEN @@ -2232,14 +2245,14 @@ __pattern_partial_sort_copy(_ExecutionPolicy&& __exec, _ForwardIterator __first, } else { - typedef typename std::iterator_traits<_ForwardIterator>::value_type _T1; - typedef typename std::iterator_traits<_RandomAccessIterator>::value_type _T2; + typedef typename std::iterator_traits<_RandomAccessIterator1>::value_type _T1; + typedef typename std::iterator_traits<_RandomAccessIterator2>::value_type _T2; __par_backend::__buffer<_T1> __buf(__n1); _T1* __r = __buf.get(); __par_backend::__parallel_stable_sort(std::forward<_ExecutionPolicy>(__exec), __r, __r + __n1, __comp, [__n2, __first, __r](_T1* __i, _T1* __j, _Compare __comp) { - _ForwardIterator __it = __first + (__i - __r); + _RandomAccessIterator1 __it = __first + (__i - __r); // 1. Copy elements from input to raw memory for (_T1* __k = __i; __k != __j; ++__k, ++__it) @@ -2258,8 +2271,7 @@ __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) { - __brick_move_destroy()( - __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, @@ -2273,9 +2285,9 @@ __pattern_partial_sort_copy(_ExecutionPolicy&& __exec, _ForwardIterator __first, //------------------------------------------------------------------------ // adjacent_find //------------------------------------------------------------------------ -template -_ForwardIterator -__brick_adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred, +template +_RandomAccessIterator +__brick_adjacent_find(_RandomAccessIterator __first, _RandomAccessIterator __last, _BinaryPredicate __pred, /* IsVector = */ std::true_type, bool __or_semantic) noexcept { return __unseq_backend::__simd_adjacent_find(__first, __last, __pred, __or_semantic); @@ -2406,9 +2418,9 @@ __pattern_nth_element(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, //------------------------------------------------------------------------ // fill, fill_n //------------------------------------------------------------------------ -template +template void -__brick_fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, +__brick_fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value, /* __is_vector = */ std::true_type) noexcept { __unseq_backend::__simd_fill_n(__first, __last - __first, __value); @@ -2430,23 +2442,26 @@ __pattern_fill(_ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterator __ __internal::__brick_fill(__first, __last, __value, __is_vector); } -template -_ForwardIterator -__pattern_fill(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, +template +_RandomAccessIterator +__pattern_fill(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last, + const _Tp& __value, /*is_parallel=*/std::true_type, _IsVector __is_vector) { return __internal::__except_handler([&__exec, __first, __last, &__value, __is_vector]() { - __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __first, __last, - [&__value, __is_vector](_ForwardIterator __begin, _ForwardIterator __end) { - __internal::__brick_fill(__begin, __end, __value, __is_vector); - }); + __par_backend::__parallel_for( + std::forward<_ExecutionPolicy>(__exec), __first, __last, + [&__value, __is_vector](_RandomAccessIterator __begin, _RandomAccessIterator __end) { + __internal::__brick_fill(__begin, __end, __value, __is_vector); + }); return __last; }); } -template -_OutputIterator -__brick_fill_n(_OutputIterator __first, _Size __count, const _Tp& __value, /* __is_vector = */ std::true_type) noexcept +template +_RandomAccessIterator +__brick_fill_n(_RandomAccessIterator __first, _Size __count, const _Tp& __value, + /* __is_vector = */ std::true_type) noexcept { return __unseq_backend::__simd_fill_n(__first, __count, __value); } @@ -2466,9 +2481,9 @@ __pattern_fill_n(_ExecutionPolicy&&, _OutputIterator __first, _Size __count, con return __internal::__brick_fill_n(__first, __count, __value, __is_vector); } -template -_OutputIterator -__pattern_fill_n(_ExecutionPolicy&& __exec, _OutputIterator __first, _Size __count, const _Tp& __value, +template +_RandomAccessIterator +__pattern_fill_n(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _Size __count, const _Tp& __value, /*is_parallel=*/std::true_type, _IsVector __is_vector) { return __internal::__pattern_fill(std::forward<_ExecutionPolicy>(__exec), __first, __first + __count, __value, @@ -2502,23 +2517,25 @@ __pattern_generate(_ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterato __internal::__brick_generate(__first, __last, __g, __is_vector); } -template -_ForwardIterator -__pattern_generate(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Generator __g, +template +_RandomAccessIterator +__pattern_generate(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last, + _Generator __g, /*is_parallel=*/std::true_type, _IsVector __is_vector) { return __internal::__except_handler([&]() { __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __first, __last, - [__g, __is_vector](_ForwardIterator __begin, _ForwardIterator __end) { + [__g, __is_vector](_RandomAccessIterator __begin, _RandomAccessIterator __end) { __internal::__brick_generate(__begin, __end, __g, __is_vector); }); return __last; }); } -template -OutputIterator -__brick_generate_n(OutputIterator __first, Size __count, _Generator __g, /* is_vector = */ std::true_type) noexcept +template +_RandomAccessIterator +__brick_generate_n(_RandomAccessIterator __first, Size __count, _Generator __g, + /* is_vector = */ std::true_type) noexcept { return __unseq_backend::__simd_generate_n(__first, __count, __g); } @@ -2538,12 +2555,12 @@ __pattern_generate_n(_ExecutionPolicy&&, _OutputIterator __first, _Size __count, return __internal::__brick_generate_n(__first, __count, __g, __is_vector); } -template -_OutputIterator -__pattern_generate_n(_ExecutionPolicy&& __exec, _OutputIterator __first, _Size __count, _Generator __g, +template +_RandomAccessIterator +__pattern_generate_n(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _Size __count, _Generator __g, /*is_parallel=*/std::true_type, _IsVector __is_vector) { - static_assert(__is_random_access_iterator<_OutputIterator>::value, + static_assert(__is_random_access_iterator<_RandomAccessIterator>::value, "Pattern-brick error. Should be a random access iterator."); return __internal::__pattern_generate(std::forward<_ExecutionPolicy>(__exec), __first, __first + __count, __g, std::true_type(), __is_vector); @@ -2581,12 +2598,12 @@ __pattern_remove_if(_ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterat return __internal::__brick_remove_if(__first, __last, __pred, __is_vector); } -template -_ForwardIterator -__pattern_remove_if(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, +template +_RandomAccessIterator +__pattern_remove_if(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last, _UnaryPredicate __pred, _IsVector __is_vector, /*is_parallel*/ std::true_type) noexcept { - typedef typename std::iterator_traits<_ForwardIterator>::reference _ReferenceType; + typedef typename std::iterator_traits<_RandomAccessIterator>::reference _ReferenceType; if (__first == __last || __first + 1 == __last) { @@ -2596,7 +2613,7 @@ __pattern_remove_if(_ExecutionPolicy&& __exec, _ForwardIterator __first, _Forwar return __internal::__remove_elements( std::forward<_ExecutionPolicy>(__exec), __first, __last, - [&__pred, __is_vector](bool* __b, bool* __e, _ForwardIterator __it) { + [&__pred, __is_vector](bool* __b, bool* __e, _RandomAccessIterator __it) { __internal::__brick_walk2(__b, __e, __it, [&__pred](bool& __x, _ReferenceType __y) { __x = !__pred(__y); }, __is_vector); }, @@ -2616,10 +2633,10 @@ __brick_merge(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIte return std::merge(__first1, __last1, __first2, __last2, __d_first, __comp); } -template -_OutputIterator -__brick_merge(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, - _ForwardIterator2 __last2, _OutputIterator __d_first, _Compare __comp, +template +_RandomAccessIterator3 +__brick_merge(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, + _RandomAccessIterator2 __last2, _RandomAccessIterator3 __d_first, _Compare __comp, /* __is_vector = */ std::true_type) noexcept { _PSTL_PRAGMA_MESSAGE("Vectorized algorithm unimplemented, redirected to serial"); @@ -2636,17 +2653,17 @@ __pattern_merge(_ExecutionPolicy&&, _ForwardIterator1 __first1, _ForwardIterator return __internal::__brick_merge(__first1, __last1, __first2, __last2, __d_first, __comp, __is_vector); } -template -_OutputIterator +template +_RandomAccessIterator3 __pattern_merge(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, - _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _OutputIterator __d_first, + _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _RandomAccessIterator3 __d_first, _Compare __comp, _IsVector __is_vector, /* is_parallel = */ std::true_type) { __par_backend::__parallel_merge( std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __d_first, __comp, [__is_vector](_RandomAccessIterator1 __f1, _RandomAccessIterator1 __l1, _RandomAccessIterator2 __f2, - _RandomAccessIterator2 __l2, _OutputIterator __f3, _Compare __comp) { + _RandomAccessIterator2 __l2, _RandomAccessIterator3 __f3, _Compare __comp) { return __internal::__brick_merge(__f1, __l1, __f2, __l2, __f3, __comp, __is_vector); }); return __d_first + (__last1 - __first1) + (__last2 - __first2); @@ -2663,9 +2680,9 @@ __brick_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __m std::inplace_merge(__first, __middle, __last, __comp); } -template +template void -__brick_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, +__brick_inplace_merge(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp, /* __is_vector = */ std::true_type) noexcept { _PSTL_PRAGMA_MESSAGE("Vectorized algorithm unimplemented, redirected to serial") @@ -2681,43 +2698,43 @@ __pattern_inplace_merge(_ExecutionPolicy&&, _BidirectionalIterator __first, _Bid __internal::__brick_inplace_merge(__first, __middle, __last, __comp, __is_vector); } -template +template void -__pattern_inplace_merge(_ExecutionPolicy&& __exec, _BidirectionalIterator __first, _BidirectionalIterator __middle, - _BidirectionalIterator __last, _Compare __comp, _IsVector __is_vector, +__pattern_inplace_merge(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __middle, + _RandomAccessIterator __last, _Compare __comp, _IsVector __is_vector, /*is_parallel=*/std::true_type) { if (__first == __last || __first == __middle || __middle == __last) { return; } - typedef typename std::iterator_traits<_BidirectionalIterator>::value_type _Tp; + typedef typename std::iterator_traits<_RandomAccessIterator>::value_type _Tp; auto __n = __last - __first; __par_backend::__buffer<_Tp> __buf(__n); _Tp* __r = __buf.get(); __internal::__except_handler([&]() { - auto __move_values = [](_BidirectionalIterator __x, _Tp* __z) { + auto __move_values = [](_RandomAccessIterator __x, _Tp* __z) { __internal::__invoke_if_else(std::is_trivial<_Tp>(), [&]() { *__z = std::move(*__x); }, [&]() { ::new (std::addressof(*__z)) _Tp(std::move(*__x)); }); }; - auto __move_sequences = [](_BidirectionalIterator __first1, _BidirectionalIterator __last1, _Tp* __first2) { + auto __move_sequences = [](_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Tp* __first2) { return __internal::__brick_uninitialized_move(__first1, __last1, __first2, _IsVector()); }; __par_backend::__parallel_merge( std::forward<_ExecutionPolicy>(__exec), __first, __middle, __middle, __last, __r, __comp, - [__n, __move_values, __move_sequences](_BidirectionalIterator __f1, _BidirectionalIterator __l1, - _BidirectionalIterator __f2, _BidirectionalIterator __l2, _Tp* __f3, + [__n, __move_values, __move_sequences](_RandomAccessIterator __f1, _RandomAccessIterator __l1, + _RandomAccessIterator __f2, _RandomAccessIterator __l2, _Tp* __f3, _Compare __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) { - __brick_move_destroy()(__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); + }); }); } @@ -2734,10 +2751,11 @@ __pattern_includes(_ExecutionPolicy&&, _ForwardIterator1 __first1, _ForwardItera return std::includes(__first1, __last1, __first2, __last2, __comp); } -template +template bool -__pattern_includes(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, _Compare __comp, _IsVector, +__pattern_includes(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, + _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _Compare __comp, _IsVector, /*is_parallel=*/std::true_type) { if (__first2 >= __last2) @@ -2756,12 +2774,12 @@ __pattern_includes(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _Forwa return __internal::__except_handler([&]() { return !__internal::__parallel_or( std::forward<_ExecutionPolicy>(__exec), __first2, __last2, - [__first1, __last1, __first2, __last2, &__comp](_ForwardIterator2 __i, _ForwardIterator2 __j) { + [__first1, __last1, __first2, __last2, &__comp](_RandomAccessIterator2 __i, _RandomAccessIterator2 __j) { _PSTL_ASSERT(__j > __i); //_PSTL_ASSERT(__j - __i > 1); //1. moving boundaries to "consume" subsequence of equal elements - auto __is_equal = [&__comp](_ForwardIterator2 __a, _ForwardIterator2 __b) -> bool { + auto __is_equal = [&__comp](_RandomAccessIterator2 __a, _RandomAccessIterator2 __b) -> bool { return !__comp(*__a, *__b) && !__comp(*__b, *__a); }; @@ -2822,9 +2840,8 @@ __parallel_set_op(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _Forwar _DifferenceType __m{}; auto __scan = [=](_DifferenceType, _DifferenceType, const _SetRange& __s) { // Scan if (!__s.empty()) - __brick_move_destroy()(__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}, @@ -3021,10 +3038,10 @@ struct __BrickCopyConstruct } }; -template +template _OutputIterator -__brick_set_union(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, - _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp, +__brick_set_union(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, + _RandomAccessIterator2 __last2, _OutputIterator __result, _Compare __comp, /*__is_vector=*/std::true_type) noexcept { _PSTL_PRAGMA_MESSAGE("Vectorized algorithm unimplemented, redirected to serial"); @@ -3042,12 +3059,12 @@ __pattern_set_union(_ExecutionPolicy&&, _ForwardIterator1 __first1, _ForwardIter return __internal::__brick_set_union(__first1, __last1, __first2, __last2, __result, __comp, __is_vector); } -template _OutputIterator -__pattern_set_union(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp, - _IsVector __is_vector, /*__is_parallel=*/std::true_type) +__pattern_set_union(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, + _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _OutputIterator __result, + _Compare __comp, _IsVector __is_vector, /*__is_parallel=*/std::true_type) { const auto __n1 = __last1 - __first1; @@ -3060,8 +3077,8 @@ __pattern_set_union(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _Forw 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, - _Tp* __result, _Compare __comp) { + [](_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, + _RandomAccessIterator2 __last2, _Tp* __result, _Compare __comp) { return __pstl::__utils::__set_union_construct(__first1, __last1, __first2, __last2, __result, __comp, __BrickCopyConstruct<_IsVector>()); }, @@ -3081,10 +3098,11 @@ __brick_set_intersection(_ForwardIterator1 __first1, _ForwardIterator1 __last1, return std::set_intersection(__first1, __last1, __first2, __last2, __result, __comp); } -template -_OutputIterator -__brick_set_intersection(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, - _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp, +template +_RandomAccessIterator3 +__brick_set_intersection(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, + _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, + _RandomAccessIterator3 __result, _Compare __comp, /*__is_vector=*/std::true_type) noexcept { _PSTL_PRAGMA_MESSAGE("Vectorized algorithm unimplemented, redirected to serial"); @@ -3101,15 +3119,16 @@ __pattern_set_intersection(_ExecutionPolicy&&, _ForwardIterator1 __first1, _Forw return __internal::__brick_set_intersection(__first1, __last1, __first2, __last2, __result, __comp, __is_vector); } -template -_OutputIterator -__pattern_set_intersection(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, _OutputIterator __result, - _Compare __comp, _IsVector __is_vector, /*is_parallel=*/std::true_type) +template +_RandomAccessIterator3 +__pattern_set_intersection(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, + _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, + _RandomAccessIterator3 __result, _Compare __comp, _IsVector __is_vector, + /*is_parallel=*/std::true_type) { - typedef typename std::iterator_traits<_OutputIterator>::value_type _Tp; - typedef typename std::iterator_traits<_ForwardIterator1>::difference_type _DifferenceType; + typedef typename std::iterator_traits<_RandomAccessIterator3>::value_type _Tp; + typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _DifferenceType; const auto __n1 = __last1 - __first1; const auto __n2 = __last2 - __first2; @@ -3119,13 +3138,13 @@ __pattern_set_intersection(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1 return __result; // testing whether the sequences are intersected - _ForwardIterator1 __left_bound_seq_1 = std::lower_bound(__first1, __last1, *__first2, __comp); + _RandomAccessIterator1 __left_bound_seq_1 = std::lower_bound(__first1, __last1, *__first2, __comp); //{1} < {2}: seq 2 is wholly greater than seq 1, so, the intersection is empty if (__left_bound_seq_1 == __last1) return __result; // testing whether the sequences are intersected - _ForwardIterator2 __left_bound_seq_2 = std::lower_bound(__first2, __last2, *__first1, __comp); + _RandomAccessIterator2 __left_bound_seq_2 = std::lower_bound(__first2, __last2, *__first1, __comp); //{2} < {1}: seq 1 is wholly greater than seq 2, so, the intersection is empty if (__left_bound_seq_2 == __last2) return __result; @@ -3137,8 +3156,8 @@ __pattern_set_intersection(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1 return __internal::__parallel_set_op( 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, _Tp* __result, _Compare __comp) { + [](_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, + _RandomAccessIterator2 __last2, _Tp* __result, _Compare __comp) { return __pstl::__utils::__set_intersection_construct(__first1, __last1, __first2, __last2, __result, __comp); }, @@ -3152,8 +3171,8 @@ __pattern_set_intersection(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1 __result = __internal::__parallel_set_op( 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, _Tp* __result, _Compare __comp) { + [](_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, + _RandomAccessIterator2 __last2, _Tp* __result, _Compare __comp) { return __pstl::__utils::__set_intersection_construct(__first2, __last2, __first1, __last1, __result, __comp); }, @@ -3178,10 +3197,10 @@ __brick_set_difference(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _F return std::set_difference(__first1, __last1, __first2, __last2, __result, __comp); } -template -_OutputIterator -__brick_set_difference(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, - _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp, +template +_RandomAccessIterator3 +__brick_set_difference(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, + _RandomAccessIterator2 __last2, _RandomAccessIterator3 __result, _Compare __comp, /*__is_vector=*/std::true_type) noexcept { _PSTL_PRAGMA_MESSAGE("Vectorized algorithm unimplemented, redirected to serial"); @@ -3198,15 +3217,16 @@ __pattern_set_difference(_ExecutionPolicy&&, _ForwardIterator1 __first1, _Forwar return __internal::__brick_set_difference(__first1, __last1, __first2, __last2, __result, __comp, __is_vector); } -template -_OutputIterator -__pattern_set_difference(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, _OutputIterator __result, - _Compare __comp, _IsVector __is_vector, /*is_parallel=*/std::true_type) +template +_RandomAccessIterator3 +__pattern_set_difference(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, + _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, + _RandomAccessIterator3 __result, _Compare __comp, _IsVector __is_vector, + /*is_parallel=*/std::true_type) { - typedef typename std::iterator_traits<_OutputIterator>::value_type _Tp; - typedef typename std::iterator_traits<_ForwardIterator1>::difference_type _DifferenceType; + typedef typename std::iterator_traits<_RandomAccessIterator3>::value_type _Tp; + typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _DifferenceType; const auto __n1 = __last1 - __first1; const auto __n2 = __last2 - __first2; @@ -3219,43 +3239,43 @@ __pattern_set_difference(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, if (__n2 == 0) return __internal::__pattern_walk2_brick( std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __result, - [__is_vector](_ForwardIterator1 __begin, _ForwardIterator1 __end, _OutputIterator __res) { + [__is_vector](_RandomAccessIterator1 __begin, _RandomAccessIterator1 __end, _RandomAccessIterator3 __res) { return __internal::__brick_copy(__begin, __end, __res, __is_vector); }, std::true_type()); // testing whether the sequences are intersected - _ForwardIterator1 __left_bound_seq_1 = std::lower_bound(__first1, __last1, *__first2, __comp); + _RandomAccessIterator1 __left_bound_seq_1 = std::lower_bound(__first1, __last1, *__first2, __comp); //{1} < {2}: seq 2 is wholly greater than seq 1, so, parallel copying just first sequence if (__left_bound_seq_1 == __last1) return __internal::__pattern_walk2_brick( std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __result, - [__is_vector](_ForwardIterator1 __begin, _ForwardIterator1 __end, _OutputIterator __res) { + [__is_vector](_RandomAccessIterator1 __begin, _RandomAccessIterator1 __end, _RandomAccessIterator3 __res) { return __internal::__brick_copy(__begin, __end, __res, __is_vector); }, std::true_type()); // testing whether the sequences are intersected - _ForwardIterator2 __left_bound_seq_2 = std::lower_bound(__first2, __last2, *__first1, __comp); + _RandomAccessIterator2 __left_bound_seq_2 = std::lower_bound(__first2, __last2, *__first1, __comp); //{2} < {1}: seq 1 is wholly greater than seq 2, so, parallel copying just first sequence if (__left_bound_seq_2 == __last2) return __internal::__pattern_walk2_brick( std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __result, - [__is_vector](_ForwardIterator1 __begin, _ForwardIterator1 __end, _OutputIterator __res) { + [__is_vector](_RandomAccessIterator1 __begin, _RandomAccessIterator1 __end, _RandomAccessIterator3 __res) { return __internal::__brick_copy(__begin, __end, __res, __is_vector); }, std::true_type()); if (__n1 + __n2 > __set_algo_cut_off) - 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); + return __parallel_set_op( + std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __result, __comp, + [](_DifferenceType __n, _DifferenceType) { return __n; }, + [](_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, + _RandomAccessIterator2 __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); @@ -3274,10 +3294,11 @@ __brick_set_symmetric_difference(_ForwardIterator1 __first1, _ForwardIterator1 _ return std::set_symmetric_difference(__first1, __last1, __first2, __last2, __result, __comp); } -template -_OutputIterator -__brick_set_symmetric_difference(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, - _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp, +template +_RandomAccessIterator3 +__brick_set_symmetric_difference(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, + _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, + _RandomAccessIterator3 __result, _Compare __comp, /*__is_vector=*/std::true_type) noexcept { _PSTL_PRAGMA_MESSAGE("Vectorized algorithm unimplemented, redirected to serial"); @@ -3295,12 +3316,13 @@ __pattern_set_symmetric_difference(_ExecutionPolicy&&, _ForwardIterator1 __first __is_vector); } -template -_OutputIterator -__pattern_set_symmetric_difference(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, _OutputIterator __result, - _Compare __comp, _IsVector __is_vector, /*is_parallel=*/std::true_type) +template +_RandomAccessIterator3 +__pattern_set_symmetric_difference(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first1, + _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, + _RandomAccessIterator2 __last2, _RandomAccessIterator3 __result, _Compare __comp, + _IsVector __is_vector, /*is_parallel=*/std::true_type) { const auto __n1 = __last1 - __first1; @@ -3310,11 +3332,11 @@ __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 _Tp; + typedef typename std::iterator_traits<_RandomAccessIterator3>::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, - _Tp* __result, _Compare __comp) { + [](_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, + _RandomAccessIterator2 __last2, _Tp* __result, _Compare __comp) { return __pstl::__utils::__set_symmetric_difference_construct(__first1, __last1, __first2, __last2, __result, __comp, __BrickCopyConstruct<_IsVector>()); }, @@ -3410,9 +3432,9 @@ __brick_min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare return std::min_element(__first, __last, __comp); } -template -_ForwardIterator -__brick_min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp, +template +_RandomAccessIterator +__brick_min_element(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, /* __is_vector = */ std::true_type) noexcept { #if _PSTL_UDR_PRESENT @@ -3465,9 +3487,9 @@ __brick_minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compa return std::minmax_element(__first, __last, __comp); } -template -std::pair<_ForwardIterator, _ForwardIterator> -__brick_minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp, +template +std::pair<_RandomAccessIterator, _RandomAccessIterator> +__brick_minmax_element(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, /* __is_vector = */ std::true_type) noexcept { #if _PSTL_UDR_PRESENT @@ -3485,20 +3507,20 @@ __pattern_minmax_element(_ExecutionPolicy&&, _ForwardIterator __first, _ForwardI return __internal::__brick_minmax_element(__first, __last, __comp, __is_vector); } -template -std::pair<_ForwardIterator, _ForwardIterator> -__pattern_minmax_element(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Compare __comp, - _IsVector __is_vector, /* is_parallel = */ std::true_type) +template +std::pair<_RandomAccessIterator, _RandomAccessIterator> +__pattern_minmax_element(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last, + _Compare __comp, _IsVector __is_vector, /* is_parallel = */ std::true_type) { if (__first == __last) return std::make_pair(__first, __first); return __internal::__except_handler([&]() { - typedef std::pair<_ForwardIterator, _ForwardIterator> _Result; + typedef std::pair<_RandomAccessIterator, _RandomAccessIterator> _Result; return __par_backend::__parallel_reduce( std::forward<_ExecutionPolicy>(__exec), __first + 1, __last, std::make_pair(__first, __first), - [=](_ForwardIterator __begin, _ForwardIterator __end, _Result __init) -> _Result { + [=](_RandomAccessIterator __begin, _RandomAccessIterator __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), @@ -3538,10 +3560,10 @@ __brick_mismatch(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _Forward return __mismatch_serial(__first1, __last1, __first2, __last2, __pred); } -template -std::pair<_ForwardIterator1, _ForwardIterator2> -__brick_mismatch(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, - _ForwardIterator2 __last2, _Predicate __pred, /* __is_vector = */ std::true_type) noexcept +template +std::pair<_RandomAccessIterator1, _RandomAccessIterator2> +__brick_mismatch(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, + _RandomAccessIterator2 __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, std::not_fn(__pred)); @@ -3590,10 +3612,11 @@ __brick_lexicographical_compare(_ForwardIterator1 __first1, _ForwardIterator1 __ return std::lexicographical_compare(__first1, __last1, __first2, __last2, __comp); } -template +template bool -__brick_lexicographical_compare(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, - _ForwardIterator2 __last2, _Compare __comp, /* __is_vector = */ std::true_type) noexcept +__brick_lexicographical_compare(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, + _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _Compare __comp, + /* __is_vector = */ std::true_type) noexcept { if (__first2 == __last2) { // if second sequence is empty @@ -3605,12 +3628,12 @@ __brick_lexicographical_compare(_ForwardIterator1 __first1, _ForwardIterator1 __ } else { - typedef typename std::iterator_traits<_ForwardIterator1>::reference ref_type1; - typedef typename std::iterator_traits<_ForwardIterator2>::reference ref_type2; + typedef typename std::iterator_traits<_RandomAccessIterator1>::reference ref_type1; + typedef typename std::iterator_traits<_RandomAccessIterator2>::reference ref_type2; --__last1; --__last2; auto __n = std::min(__last1 - __first1, __last2 - __first2); - std::pair<_ForwardIterator1, _ForwardIterator2> __result = __unseq_backend::__simd_first( + std::pair<_RandomAccessIterator1, _RandomAccessIterator2> __result = __unseq_backend::__simd_first( __first1, __n, __first2, [__comp](const ref_type1 __x, const ref_type2 __y) mutable { return __comp(__x, __y) || __comp(__y, __x); }); @@ -3635,11 +3658,13 @@ __pattern_lexicographical_compare(_ExecutionPolicy&&, _ForwardIterator1 __first1 return __internal::__brick_lexicographical_compare(__first1, __last1, __first2, __last2, __comp, __is_vector); } -template +template bool -__pattern_lexicographical_compare(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, _Compare __comp, - _IsVector __is_vector, /* is_parallel = */ std::true_type) noexcept +__pattern_lexicographical_compare(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first1, + _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, + _RandomAccessIterator2 __last2, _Compare __comp, _IsVector __is_vector, + /* is_parallel = */ std::true_type) noexcept { if (__first2 == __last2) { // if second sequence is empty @@ -3651,14 +3676,14 @@ __pattern_lexicographical_compare(_ExecutionPolicy&& __exec, _ForwardIterator1 _ } else { - typedef typename std::iterator_traits<_ForwardIterator1>::reference _RefType1; - typedef typename std::iterator_traits<_ForwardIterator2>::reference _RefType2; + typedef typename std::iterator_traits<_RandomAccessIterator1>::reference _RefType1; + typedef typename std::iterator_traits<_RandomAccessIterator2>::reference _RefType2; --__last1; --__last2; auto __n = std::min(__last1 - __first1, __last2 - __first2); auto __result = __internal::__parallel_find( std::forward<_ExecutionPolicy>(__exec), __first1, __first1 + __n, - [__first1, __first2, &__comp, __is_vector](_ForwardIterator1 __i, _ForwardIterator1 __j) { + [__first1, __first2, &__comp, __is_vector](_RandomAccessIterator1 __i, _RandomAccessIterator1 __j) { return __internal::__brick_mismatch(__i, __j, __first2 + (__i - __first1), __first2 + (__j - __first1), [&__comp](const _RefType1 __x, const _RefType2 __y) { return !__comp(__x, __y) && !__comp(__y, __x); @@ -3666,7 +3691,7 @@ __pattern_lexicographical_compare(_ExecutionPolicy&& __exec, _ForwardIterator1 _ __is_vector) .first; }, - std::less::difference_type>(), /*is_first=*/true); + std::less::difference_type>(), /*is_first=*/true); if (__result == __last1 && __first2 + (__result - __first1) != __last2) { // if first sequence shorter than second diff --git a/pstl/include/pstl/internal/memory_impl.h b/pstl/include/pstl/internal/memory_impl.h index 1eb2fe4..942a30e 100644 --- a/pstl/include/pstl/internal/memory_impl.h +++ b/pstl/include/pstl/internal/memory_impl.h @@ -39,13 +39,13 @@ __brick_uninitialized_move(_ForwardIterator __first, _ForwardIterator __last, _O return __result; } -template +template _OutputIterator -__brick_uninitialized_move(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, +__brick_uninitialized_move(_RandomAccessIterator __first, _RandomAccessIterator __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 _ReferenceType1 = typename std::iterator_traits<_RandomAccessIterator>::reference; using _ReferenceType2 = typename std::iterator_traits<_OutputIterator>::reference; return __unseq_backend::__simd_walk_2( @@ -63,12 +63,12 @@ __brick_destroy(_Iterator __first, _Iterator __last, /*vector*/ std::false_type) __first->~_ValueType(); } -template +template void -__brick_destroy(_Iterator __first, _Iterator __last, /*vector*/ std::true_type) noexcept +__brick_destroy(_RandomAccessIterator __first, _RandomAccessIterator __last, /*vector*/ std::true_type) noexcept { - using _ValueType = typename std::iterator_traits<_Iterator>::value_type; - using _ReferenceType = typename std::iterator_traits<_Iterator>::reference; + using _ValueType = typename std::iterator_traits<_RandomAccessIterator>::value_type; + using _ReferenceType = typename std::iterator_traits<_RandomAccessIterator>::reference; __unseq_backend::__simd_walk_1(__first, __last - __first, [](_ReferenceType __x) { __x.~_ValueType(); }); } @@ -90,13 +90,13 @@ __brick_uninitialized_copy(_ForwardIterator __first, _ForwardIterator __last, _O return __result; } -template +template _OutputIterator -__brick_uninitialized_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, +__brick_uninitialized_copy(_RandomAccessIterator __first, _RandomAccessIterator __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 _ReferenceType1 = typename std::iterator_traits<_RandomAccessIterator>::reference; using _ReferenceType2 = typename std::iterator_traits<_OutputIterator>::reference; return __unseq_backend::__simd_walk_2( diff --git a/pstl/include/pstl/internal/numeric_fwd.h b/pstl/include/pstl/internal/numeric_fwd.h index 07d7f07..bcb3e2d 100644 --- a/pstl/include/pstl/internal/numeric_fwd.h +++ b/pstl/include/pstl/internal/numeric_fwd.h @@ -26,9 +26,10 @@ namespace __internal // transform_reduce (version with two binary functions, according to draft N4659) //------------------------------------------------------------------------ -template -_Tp __brick_transform_reduce(_ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _Tp, _BinaryOperation1, - _BinaryOperation2, +template +_Tp __brick_transform_reduce(_RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2, _Tp, + _BinaryOperation1, _BinaryOperation2, /*__is_vector=*/std::true_type) noexcept; template @@ -54,8 +55,8 @@ __pattern_transform_reduce(_ExecutionPolicy&&, _RandomAccessIterator1, _RandomAc // transform_reduce (version with unary and binary functions) //------------------------------------------------------------------------ -template -_Tp __brick_transform_reduce(_ForwardIterator, _ForwardIterator, _Tp, _BinaryOperation, _UnaryOperation, +template +_Tp __brick_transform_reduce(_RandomAccessIterator, _RandomAccessIterator, _Tp, _BinaryOperation, _UnaryOperation, /*is_vector=*/std::true_type) noexcept; template @@ -69,10 +70,10 @@ __pattern_transform_reduce(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterato _UnaryOperation, _IsVector, /*is_parallel=*/std::false_type) noexcept; -template _Tp -__pattern_transform_reduce(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Tp, _BinaryOperation, +__pattern_transform_reduce(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _Tp, _BinaryOperation, _UnaryOperation, _IsVector, /*is_parallel=*/std::true_type); @@ -87,8 +88,8 @@ std::pair<_OutputIterator, _Tp> __brick_transform_scan(_ForwardIterator, _Forwar _UnaryOperation, _Tp, _BinaryOperation, /*Inclusive*/ std::false_type) noexcept; -template -std::pair<_OutputIterator, _Tp> __brick_transform_scan(_ForwardIterator, _ForwardIterator, _OutputIterator, +template +std::pair<_OutputIterator, _Tp> __brick_transform_scan(_RandomAccessIterator, _RandomAccessIterator, _OutputIterator, _UnaryOperation, _Tp, _BinaryOperation, /*Inclusive*/ std::true_type) noexcept; @@ -119,8 +120,9 @@ template _OutputIterator __brick_adjacent_difference(_ForwardIterator, _ForwardIterator, _OutputIterator, _BinaryOperation, /*is_vector*/ std::false_type) noexcept; -template -_OutputIterator __brick_adjacent_difference(_ForwardIterator, _ForwardIterator, _OutputIterator, _BinaryOperation, +template +_OutputIterator __brick_adjacent_difference(_RandomAccessIterator, _RandomAccessIterator, _OutputIterator, + _BinaryOperation, /*is_vector*/ std::true_type) noexcept; template _OutputIterator -__pattern_adjacent_difference(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _OutputIterator, _BinaryOperation, - _IsVector, /*is_parallel*/ std::true_type); +__pattern_adjacent_difference(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _OutputIterator, + _BinaryOperation, _IsVector, /*is_parallel*/ std::true_type); } // namespace __internal } // namespace __pstl diff --git a/pstl/include/pstl/internal/numeric_impl.h b/pstl/include/pstl/internal/numeric_impl.h index 3e653bb..e90d865 100644 --- a/pstl/include/pstl/internal/numeric_impl.h +++ b/pstl/include/pstl/internal/numeric_impl.h @@ -40,13 +40,15 @@ __brick_transform_reduce(_ForwardIterator1 __first1, _ForwardIterator1 __last1, return std::inner_product(__first1, __last1, __first2, __init, __binary_op1, __binary_op2); } -template +template _Tp -__brick_transform_reduce(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _Tp __init, - _BinaryOperation1 __binary_op1, _BinaryOperation2 __binary_op2, +__brick_transform_reduce(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, + _RandomAccessIterator2 __first2, _Tp __init, _BinaryOperation1 __binary_op1, + _BinaryOperation2 __binary_op2, /*is_vector=*/std::true_type) noexcept { - typedef typename std::iterator_traits<_ForwardIterator1>::difference_type _DifferenceType; + typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _DifferenceType; return __unseq_backend::__simd_transform_reduce( __last1 - __first1, __init, __binary_op1, [=, &__binary_op2](_DifferenceType __i) { return __binary_op2(__first1[__i], __first2[__i]); }); @@ -98,12 +100,13 @@ __brick_transform_reduce(_ForwardIterator __first, _ForwardIterator __last, _Tp return std::transform_reduce(__first, __last, __init, __binary_op, __unary_op); } -template +template _Tp -__brick_transform_reduce(_ForwardIterator __first, _ForwardIterator __last, _Tp __init, _BinaryOperation __binary_op, - _UnaryOperation __unary_op, /*is_vector=*/std::true_type) noexcept +__brick_transform_reduce(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp __init, + _BinaryOperation __binary_op, _UnaryOperation __unary_op, + /*is_vector=*/std::true_type) noexcept { - typedef typename std::iterator_traits<_ForwardIterator>::difference_type _DifferenceType; + typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _DifferenceType; return __unseq_backend::__simd_transform_reduce( __last - __first, __init, __binary_op, [=, &__unary_op](_DifferenceType __i) { return __unary_op(__first[__i]); }); @@ -119,18 +122,18 @@ __pattern_transform_reduce(_ExecutionPolicy&&, _ForwardIterator __first, _Forwar return __internal::__brick_transform_reduce(__first, __last, __init, __binary_op, __unary_op, __is_vector); } -template _Tp -__pattern_transform_reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Tp __init, - _BinaryOperation __binary_op, _UnaryOperation __unary_op, _IsVector __is_vector, +__pattern_transform_reduce(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last, + _Tp __init, _BinaryOperation __binary_op, _UnaryOperation __unary_op, _IsVector __is_vector, /*is_parallel=*/std::true_type) { return __internal::__except_handler([&]() { return __par_backend::__parallel_transform_reduce( std::forward<_ExecutionPolicy>(__exec), __first, __last, - [__unary_op](_ForwardIterator __i) mutable { return __unary_op(*__i); }, __init, __binary_op, - [__unary_op, __binary_op, __is_vector](_ForwardIterator __i, _ForwardIterator __j, _Tp __init) { + [__unary_op](_RandomAccessIterator __i) mutable { return __unary_op(*__i); }, __init, __binary_op, + [__unary_op, __binary_op, __is_vector](_RandomAccessIterator __i, _RandomAccessIterator __j, _Tp __init) { return __internal::__brick_transform_reduce(__i, __j, __init, __binary_op, __unary_op, __is_vector); }); }); @@ -159,9 +162,9 @@ __brick_transform_scan(_ForwardIterator __first, _ForwardIterator __last, _Outpu } // Inclusive form -template +template std::pair<_OutputIterator, _Tp> -__brick_transform_scan(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, +__brick_transform_scan(_RandomAccessIterator __first, _RandomAccessIterator __last, _OutputIterator __result, _UnaryOperation __unary_op, _Tp __init, _BinaryOperation __binary_op, /*Inclusive*/ std::true_type, /*is_vector=*/std::false_type) noexcept { @@ -181,10 +184,10 @@ using is_arithmetic_udop = std::integral_constant: // [restriction] - T shall be DefaultConstructible. // [violation] - default ctor of T shall set the identity value for binary_op. -template typename std::enable_if::value, std::pair<_OutputIterator, _Tp>>::type -__brick_transform_scan(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, +__brick_transform_scan(_RandomAccessIterator __first, _RandomAccessIterator __last, _OutputIterator __result, _UnaryOperation __unary_op, _Tp __init, _BinaryOperation __binary_op, _Inclusive, /*is_vector=*/std::true_type) noexcept { @@ -198,10 +201,10 @@ __brick_transform_scan(_ForwardIterator __first, _ForwardIterator __last, _Outpu #endif } -template typename std::enable_if::value, std::pair<_OutputIterator, _Tp>>::type -__brick_transform_scan(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, +__brick_transform_scan(_RandomAccessIterator __first, _RandomAccessIterator __last, _OutputIterator __result, _UnaryOperation __unary_op, _Tp __init, _BinaryOperation __binary_op, _Inclusive, /*is_vector=*/std::true_type) noexcept { @@ -299,15 +302,16 @@ __brick_adjacent_difference(_ForwardIterator __first, _ForwardIterator __last, _ return std::adjacent_difference(__first, __last, __d_first, __op); } -template -_ForwardIterator2 -__brick_adjacent_difference(_ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __d_first, - BinaryOperation __op, /*is_vector=*/std::true_type) noexcept +template +_RandomAccessIterator2 +__brick_adjacent_difference(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, + _RandomAccessIterator2 __d_first, BinaryOperation __op, + /*is_vector=*/std::true_type) noexcept { _PSTL_ASSERT(__first != __last); - typedef typename std::iterator_traits<_ForwardIterator1>::reference _ReferenceType1; - typedef typename std::iterator_traits<_ForwardIterator2>::reference _ReferenceType2; + typedef typename std::iterator_traits<_RandomAccessIterator1>::reference _ReferenceType1; + typedef typename std::iterator_traits<_RandomAccessIterator2>::reference _ReferenceType2; auto __n = __last - __first; *__d_first = *__first; @@ -326,22 +330,22 @@ __pattern_adjacent_difference(_ExecutionPolicy&&, _ForwardIterator __first, _For return __internal::__brick_adjacent_difference(__first, __last, __d_first, __op, __is_vector); } -template -_ForwardIterator2 -__pattern_adjacent_difference(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, - _ForwardIterator2 __d_first, _BinaryOperation __op, _IsVector __is_vector, +_RandomAccessIterator2 +__pattern_adjacent_difference(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first, _RandomAccessIterator1 __last, + _RandomAccessIterator2 __d_first, _BinaryOperation __op, _IsVector __is_vector, /*is_parallel=*/std::true_type) { _PSTL_ASSERT(__first != __last); - typedef typename std::iterator_traits<_ForwardIterator1>::reference _ReferenceType1; - typedef typename std::iterator_traits<_ForwardIterator2>::reference _ReferenceType2; + typedef typename std::iterator_traits<_RandomAccessIterator1>::reference _ReferenceType1; + typedef typename std::iterator_traits<_RandomAccessIterator2>::reference _ReferenceType2; *__d_first = *__first; __par_backend::__parallel_for( std::forward<_ExecutionPolicy>(__exec), __first, __last - 1, - [&__op, __is_vector, __d_first, __first](_ForwardIterator1 __b, _ForwardIterator1 __e) { - _ForwardIterator2 __d_b = __d_first + (__b - __first); + [&__op, __is_vector, __d_first, __first](_RandomAccessIterator1 __b, _RandomAccessIterator1 __e) { + _RandomAccessIterator2 __d_b = __d_first + (__b - __first); __internal::__brick_walk3( __b, __e, __b + 1, __d_b + 1, [&__op](_ReferenceType1 __x, _ReferenceType1 __y, _ReferenceType2 __z) { __z = __op(__y, __x); }, -- cgit v1.1