diff options
Diffstat (limited to 'pstl')
10 files changed, 507 insertions, 53 deletions
diff --git a/pstl/include/pstl/internal/algorithm_impl.h b/pstl/include/pstl/internal/algorithm_impl.h index 5d09652..01a9405 100644 --- a/pstl/include/pstl/internal/algorithm_impl.h +++ b/pstl/include/pstl/internal/algorithm_impl.h @@ -282,10 +282,10 @@ template <class _ExecutionPolicy, class _RandomAccessIterator1, class _Size, cla class _Function, class _IsVector> _RandomAccessIterator2 __pattern_walk2_n(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first1, _Size __n, _RandomAccessIterator2 __first2, - _Function __f, _IsVector __is_vector, /*parallel=*/std::true_type) + _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()); + is_vector, std::true_type()); } template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Brick> @@ -900,6 +900,36 @@ __brick_move(_RandomAccessIterator __first, _RandomAccessIterator __last, _Outpu [](_RandomAccessIterator __first, _OutputIterator __result) { *__result = std::move(*__first); }); } +struct __brick_move_destroy +{ + template <typename _Iterator, typename _OutputIterator> + _OutputIterator + operator()(_Iterator __first, _Iterator __last, _OutputIterator __result, /*vec*/ std::true_type) const + { + using _IteratorValueType = typename std::iterator_traits<_Iterator>::value_type; + + return __unseq_backend::__simd_assign(__first, __last - __first, __result, + [](_Iterator __first, _OutputIterator __result) { + *__result = std::move(*__first); + (*__first).~_IteratorValueType(); + }); + } + + template <typename _Iterator, typename _OutputIterator> + _OutputIterator + operator()(_Iterator __first, _Iterator __last, _OutputIterator __result, /*vec*/ std::false_type) const + { + using _IteratorValueType = typename std::iterator_traits<_Iterator>::value_type; + + for (; __first != __last; ++__first, ++__result) + { + *__result = std::move(*__first); + (*__first).~_IteratorValueType(); + } + return __result; + } +}; + //------------------------------------------------------------------------ // swap_ranges //------------------------------------------------------------------------ @@ -1221,10 +1251,16 @@ __remove_elements(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardI [&__m](_DifferenceType __total) { __m = __total; }); // 3. Elements from result are moved to [first, last) - __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __result, __result + __m, - [__result, __first, __is_vector](_Tp* __i, _Tp* __j) { - __internal::__brick_move(__i, __j, __first + (__i - __result), __is_vector); - }); + __par_backend::__parallel_for( + std::forward<_ExecutionPolicy>(__exec), __result, __result + __m, + [__result, __first, __is_vector](_Tp* __i, _Tp* __j) { + __invoke_if_else( + std::is_trivial<_Tp>(), + [&]() { __brick_move(__i, __j, __first + (__i - __result), __is_vector); }, + [&]() { + __brick_move_destroy()(__i, __j, __first + (__i - __result), __is_vector); + }); + }); return __first + __m; }); } @@ -1573,8 +1609,8 @@ __pattern_rotate(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIt __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __result, __result + (__n - __m), [__first, __result, __is_vector](_Tp* __b, _Tp* __e) { - __internal::__brick_move(__b, __e, __first + (__b - __result), - __is_vector); + __brick_move_destroy()( + __b, __e, __first + (__b - __result), __is_vector); }); return __first + (__last - __middle); @@ -1599,7 +1635,7 @@ __pattern_rotate(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIt __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __result, __result + __m, [__n, __m, __first, __result, __is_vector](_Tp* __b, _Tp* __e) { - __internal::__brick_move( + __brick_move_destroy()( __b, __e, __first + ((__n - __m) + (__b - __result)), __is_vector); }); @@ -2222,8 +2258,13 @@ __pattern_partial_sort_copy(_ExecutionPolicy&& __exec, _ForwardIterator __first, // 3. Move elements from temporary __buffer to output __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __r, __r + __n2, [__r, __d_first, __is_vector](_T1* __i, _T1* __j) { - __internal::__brick_move(__i, __j, __d_first + (__i - __r), __is_vector); + __brick_move_destroy()( + __i, __j, __d_first + (__i - __r), __is_vector); }); + __par_backend::__parallel_for( + std::forward<_ExecutionPolicy>(__exec), __r + __n2, __r + __n1, + [__is_vector](_T1* __i, _T1* __j) { __brick_destroy(__i, __j, __is_vector); }); + return __d_first + __n2; } }); @@ -2673,10 +2714,10 @@ __pattern_inplace_merge(_ExecutionPolicy&& __exec, _BidirectionalIterator __firs __move_sequences, __move_sequences); return __f3 + (__l1 - __f1) + (__l2 - __f2); }); - __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __r, __r + __n, - [__r, __first, __is_vector](_Tp* __i, _Tp* __j) { - __internal::__brick_move(__i, __j, __first + (__i - __r), __is_vector); - }); + __par_backend::__parallel_for( + std::forward<_ExecutionPolicy>(__exec), __r, __r + __n, [__r, __first, __is_vector](_Tp* __i, _Tp* __j) { + __brick_move_destroy()(__i, __j, __first + (__i - __r), __is_vector); + }); }); } @@ -2781,8 +2822,9 @@ __parallel_set_op(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _Forwar _DifferenceType __m{}; auto __scan = [=](_DifferenceType, _DifferenceType, const _SetRange& __s) { // Scan if (!__s.empty()) - __internal::__brick_move(__buffer + __s.__buf_pos, __buffer + (__s.__buf_pos + __s.__len), - __result + __s.__pos, __is_vector); + __brick_move_destroy()(__buffer + __s.__buf_pos, + __buffer + (__s.__buf_pos + __s.__len), __result + __s.__pos, + __is_vector); }; __par_backend::__parallel_strict_scan( std::forward<_ExecutionPolicy>(__exec), __n1, _SetRange{0, 0, 0}, //-1, 0}, @@ -2968,6 +3010,17 @@ __brick_set_union(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _Forwar return std::set_union(__first1, __last1, __first2, __last2, __result, __comp); } +template <typename _IsVector> +struct __BrickCopyConstruct +{ + template <typename _ForwardIterator, typename _OutputIterator> + _OutputIterator + operator()(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result) + { + return __brick_uninitialized_copy(__first, __last, __result, _IsVector()); + } +}; + template <class _ForwardIterator1, class _ForwardIterator2, class _OutputIterator, class _Compare> _OutputIterator __brick_set_union(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, @@ -3004,12 +3057,14 @@ __pattern_set_union(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _Forw if (__n1 + __n2 <= __set_algo_cut_off) return std::set_union(__first1, __last1, __first2, __last2, __result, __comp); - typedef typename std::iterator_traits<_OutputIterator>::value_type _Tp; - return __internal::__parallel_set_union_op( + typedef typename std::iterator_traits<_OutputIterator>::value_type _T; + 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) { return std::set_union(__first1, __last1, __first2, __last2, __result, __comp); }, + _T* __result, _Compare __comp) { + return __pstl::__utils::__set_union_construct(__first1, __last1, __first2, __last2, __result, __comp, + __BrickCopyConstruct<_IsVector>()); + }, __is_vector); } @@ -3084,7 +3139,8 @@ __pattern_set_intersection(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1 [](_DifferenceType __n, _DifferenceType __m) { return std::min(__n, __m); }, [](_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _Tp* __result, _Compare __comp) { - return std::set_intersection(__first1, __last1, __first2, __last2, __result, __comp); + return __pstl::__utils::__set_intersection_construct(__first1, __last1, __first2, __last2, __result, + __comp); }, __is_vector); } @@ -3098,7 +3154,8 @@ __pattern_set_intersection(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1 [](_DifferenceType __n, _DifferenceType __m) { return std::min(__n, __m); }, [](_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _Tp* __result, _Compare __comp) { - return std::set_intersection(__first2, __last2, __first1, __last1, __result, __comp); + return __pstl::__utils::__set_intersection_construct(__first2, __last2, __first1, __last1, __result, + __comp); }, __is_vector); return __result; @@ -3190,13 +3247,15 @@ __pattern_set_difference(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, std::true_type()); if (__n1 + __n2 > __set_algo_cut_off) - return __internal::__parallel_set_op( - std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __result, __comp, - [](_DifferenceType __n, _DifferenceType) { return __n; }, - [](_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, - _ForwardIterator2 __last2, _Tp* __result, - _Compare __comp) { return std::set_difference(__first1, __last1, __first2, __last2, __result, __comp); }, - __is_vector); + return __parallel_set_op(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __result, + __comp, [](_DifferenceType __n, _DifferenceType __m) { return __n; }, + [](_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, + _ForwardIterator2 __last2, _Tp* __result, _Compare __comp) { + return __pstl::__utils::__set_difference_construct( + __first1, __last1, __first2, __last2, __result, __comp, + __BrickCopyConstruct<_IsVector>()); + }, + __is_vector); // use serial algorithm return std::set_difference(__first1, __last1, __first2, __last2, __result, __comp); @@ -3256,7 +3315,8 @@ __pattern_set_symmetric_difference(_ExecutionPolicy&& __exec, _ForwardIterator1 std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __result, __comp, [](_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _Tp* __result, _Compare __comp) { - return std::set_symmetric_difference(__first1, __last1, __first2, __last2, __result, __comp); + return __pstl::__utils::__set_symmetric_difference_construct(__first1, __last1, __first2, __last2, __result, + __comp, __BrickCopyConstruct<_IsVector>()); }, __is_vector); } diff --git a/pstl/include/pstl/internal/memory_impl.h b/pstl/include/pstl/internal/memory_impl.h index 241f00a..1eb2fe4 100644 --- a/pstl/include/pstl/internal/memory_impl.h +++ b/pstl/include/pstl/internal/memory_impl.h @@ -26,31 +26,82 @@ namespace __internal // uninitialized_move //------------------------------------------------------------------------ -template <class _ForwardIterator, class _OutputIterator> +template <typename _ForwardIterator, typename _OutputIterator> _OutputIterator __brick_uninitialized_move(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, /*vector=*/std::false_type) noexcept { - typedef typename std::iterator_traits<_OutputIterator>::value_type _ValueType2; + using _ValueType = typename std::iterator_traits<_OutputIterator>::value_type; for (; __first != __last; ++__first, ++__result) { - ::new (std::addressof(*__result)) _ValueType2(std::move(*__first)); + ::new (std::addressof(*__result)) _ValueType(std::move(*__first)); } return __result; } -template <class _ForwardIterator, class _OutputIterator> +template <typename _ForwardIterator, typename _OutputIterator> _OutputIterator __brick_uninitialized_move(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, /*vector=*/std::true_type) noexcept { - typedef typename std::iterator_traits<_OutputIterator>::value_type __ValueType2; - typedef typename std::iterator_traits<_ForwardIterator>::reference _ReferenceType1; - typedef typename std::iterator_traits<_OutputIterator>::reference _ReferenceType2; + using __ValueType = typename std::iterator_traits<_OutputIterator>::value_type; + using _ReferenceType1 = typename std::iterator_traits<_ForwardIterator>::reference; + using _ReferenceType2 = typename std::iterator_traits<_OutputIterator>::reference; return __unseq_backend::__simd_walk_2( __first, __last - __first, __result, - [](_ReferenceType1 __x, _ReferenceType2 __y) { ::new (std::addressof(__y)) __ValueType2(std::move(__x)); }); + [](_ReferenceType1 __x, _ReferenceType2 __y) { ::new (std::addressof(__y)) __ValueType(std::move(__x)); }); +} + +template <typename _Iterator> +void +__brick_destroy(_Iterator __first, _Iterator __last, /*vector*/ std::false_type) noexcept +{ + using _ValueType = typename std::iterator_traits<_Iterator>::value_type; + + for (; __first != __last; ++__first) + __first->~_ValueType(); +} + +template <typename _Iterator> +void +__brick_destroy(_Iterator __first, _Iterator __last, /*vector*/ std::true_type) noexcept +{ + using _ValueType = typename std::iterator_traits<_Iterator>::value_type; + using _ReferenceType = typename std::iterator_traits<_Iterator>::reference; + + __unseq_backend::__simd_walk_1(__first, __last - __first, [](_ReferenceType __x) { __x.~_ValueType(); }); +} + +//------------------------------------------------------------------------ +// uninitialized copy +//------------------------------------------------------------------------ + +template <typename _ForwardIterator, typename _OutputIterator> +_OutputIterator +__brick_uninitialized_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, + /*vector=*/std::false_type) noexcept +{ + using _ValueType = typename std::iterator_traits<_OutputIterator>::value_type; + for (; __first != __last; ++__first, ++__result) + { + ::new (std::addressof(*__result)) _ValueType(*__first); + } + return __result; +} + +template <typename _ForwardIterator, typename _OutputIterator> +_OutputIterator +__brick_uninitialized_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, + /*vector=*/std::true_type) noexcept +{ + using __ValueType = typename std::iterator_traits<_OutputIterator>::value_type; + using _ReferenceType1 = typename std::iterator_traits<_ForwardIterator>::reference; + using _ReferenceType2 = typename std::iterator_traits<_OutputIterator>::reference; + + return __unseq_backend::__simd_walk_2( + __first, __last - __first, __result, + [](_ReferenceType1 __x, _ReferenceType2 __y) { ::new (std::addressof(__y)) __ValueType(__x); }); } } // namespace __internal diff --git a/pstl/include/pstl/internal/parallel_backend_utils.h b/pstl/include/pstl/internal/parallel_backend_utils.h index 5728b48..448f924 100644 --- a/pstl/include/pstl/internal/parallel_backend_utils.h +++ b/pstl/include/pstl/internal/parallel_backend_utils.h @@ -138,6 +138,124 @@ struct __serial_move_merge } }; +template <typename _ForwardIterator1, typename _ForwardIterator2, typename _OutputIterator, typename _Compare, + typename _CopyConstructRange> +_OutputIterator +__set_union_construct(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, + _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp, + _CopyConstructRange __cc_range) +{ + using _Tp = typename std::iterator_traits<_OutputIterator>::value_type; + + for (; __first1 != __last1; ++__result) + { + if (__first2 == __last2) + return __cc_range(__first1, __last1, __result); + if (__comp(*__first2, *__first1)) + { + ::new (std::addressof(*__result)) _Tp(*__first2); + ++__first2; + } + else + { + ::new (std::addressof(*__result)) _Tp(*__first1); + if (!__comp(*__first1, *__first2)) + ++__first2; + ++__first1; + } + } + return __cc_range(__first2, __last2, __result); +} + +template <typename _ForwardIterator1, typename _ForwardIterator2, typename _OutputIterator, typename _Compare> +_OutputIterator +__set_intersection_construct(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, + _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp) +{ + using _Tp = typename std::iterator_traits<_OutputIterator>::value_type; + + for (; __first1 != __last1 && __first2 != __last2;) + { + if (__comp(*__first1, *__first2)) + ++__first1; + else + { + if (!__comp(*__first2, *__first1)) + { + ::new (std::addressof(*__result)) _Tp(*__first1); + ++__result; + ++__first1; + } + ++__first2; + } + } + return __result; +} + +template <typename _ForwardIterator1, typename _ForwardIterator2, typename _OutputIterator, typename _Compare, + typename _CopyConstructRange> +_OutputIterator +__set_difference_construct(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, + _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp, + _CopyConstructRange __cc_range) +{ + using _Tp = typename std::iterator_traits<_OutputIterator>::value_type; + + for (; __first1 != __last1;) + { + if (__first2 == __last2) + return __cc_range(__first1, __last1, __result); + + if (__comp(*__first1, *__first2)) + { + ::new (std::addressof(*__result)) _Tp(*__first1); + ++__result; + ++__first1; + } + else + { + if (!__comp(*__first2, *__first1)) + ++__first1; + ++__first2; + } + } + return __result; +} +template <typename _ForwardIterator1, typename _ForwardIterator2, typename _OutputIterator, typename _Compare, + typename _CopyConstructRange> +_OutputIterator +__set_symmetric_difference_construct(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, + _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp, + _CopyConstructRange __cc_range) +{ + using _Tp = typename std::iterator_traits<_OutputIterator>::value_type; + + for (; __first1 != __last1;) + { + if (__first2 == __last2) + return __cc_range(__first1, __last1, __result); + + if (__comp(*__first1, *__first2)) + { + ::new (std::addressof(*__result)) _Tp(*__first1); + ++__result; + ++__first1; + } + else + { + if (__comp(*__first2, *__first1)) + { + ::new (std::addressof(*__result)) _Tp(*__first2); + ++__result; + } + else + ++__first1; + ++__first2; + } + } + return __cc_range(__first2, __last2, __result); +} + } // namespace __utils } // namespace __pstl diff --git a/pstl/test/std/algorithms/alg.merge/inplace_merge.pass.cpp b/pstl/test/std/algorithms/alg.merge/inplace_merge.pass.cpp index 74ecc0c..f2cc404 100644 --- a/pstl/test/std/algorithms/alg.merge/inplace_merge.pass.cpp +++ b/pstl/test/std/algorithms/alg.merge/inplace_merge.pass.cpp @@ -147,6 +147,13 @@ main() test_algo_basic_single<int32_t>(run_for_rnd_bi<test_non_const<int32_t>>()); + test_by_type<MemoryChecker>( + [](std::size_t idx){ return MemoryChecker{std::int32_t(idx * 2)}; }, + [](std::size_t idx){ return MemoryChecker{std::int32_t(idx * 2 + 1)}; }, + [](const MemoryChecker& val1, const MemoryChecker& val2){ return val1.value() == val2.value(); }); + EXPECT_FALSE(MemoryChecker::alive_objects() < 0, "wrong effect from inplace_merge: number of ctors calls < num of dtors calls"); + EXPECT_FALSE(MemoryChecker::alive_objects() > 0, "wrong effect from inplace_merge: number of ctors calls > num of dtors calls"); + std::cout << done() << std::endl; return 0; } diff --git a/pstl/test/std/algorithms/alg.modifying.operations/remove.pass.cpp b/pstl/test/std/algorithms/alg.modifying.operations/remove.pass.cpp index cb8b178..c41a31d 100644 --- a/pstl/test/std/algorithms/alg.modifying.operations/remove.pass.cpp +++ b/pstl/test/std/algorithms/alg.modifying.operations/remove.pass.cpp @@ -149,6 +149,13 @@ main() test_algo_basic_single<int32_t>(run_for_rnd_fw<test_non_const>()); + test<MemoryChecker>(MemoryChecker{0}, MemoryChecker{1}, + [](const MemoryChecker& val){ return val.value() == 1; }, + [](std::size_t idx){ return MemoryChecker{std::int32_t(idx % 3 == 0)}; } + ); + EXPECT_FALSE(MemoryChecker::alive_objects() < 0, "wrong effect from remove,remove_if: number of ctors calls < num of dtors calls"); + EXPECT_FALSE(MemoryChecker::alive_objects() > 0, "wrong effect from remove,remove_if: number of ctors calls > num of dtors calls"); + std::cout << done() << std::endl; return 0; } diff --git a/pstl/test/std/algorithms/alg.modifying.operations/rotate.pass.cpp b/pstl/test/std/algorithms/alg.modifying.operations/rotate.pass.cpp index 5eb242e..03f2b3c 100644 --- a/pstl/test/std/algorithms/alg.modifying.operations/rotate.pass.cpp +++ b/pstl/test/std/algorithms/alg.modifying.operations/rotate.pass.cpp @@ -167,6 +167,9 @@ main() { test<int32_t>(); test<wrapper<float64_t>>(); + test<MemoryChecker>(); + EXPECT_FALSE(MemoryChecker::alive_objects() < 0, "wrong effect from rotate: number of ctors calls < num of dtors calls"); + EXPECT_FALSE(MemoryChecker::alive_objects() > 0, "wrong effect from rotate: number of ctors calls > num of dtors calls"); std::cout << done() << std::endl; return 0; diff --git a/pstl/test/std/algorithms/alg.modifying.operations/unique.pass.cpp b/pstl/test/std/algorithms/alg.modifying.operations/unique.pass.cpp index 79f5518..2f68c00 100644 --- a/pstl/test/std/algorithms/alg.modifying.operations/unique.pass.cpp +++ b/pstl/test/std/algorithms/alg.modifying.operations/unique.pass.cpp @@ -152,6 +152,12 @@ main() test_algo_basic_single<int32_t>(run_for_rnd_fw<test_non_const<int32_t>>()); + test<MemoryChecker>( + [](std::size_t idx){ return MemoryChecker{std::int32_t(idx / 3)}; }, + [](const MemoryChecker& val1, const MemoryChecker& val2){ return val1.value() == val2.value(); }); + EXPECT_FALSE(MemoryChecker::alive_objects() < 0, "wrong effect from unique: number of ctors calls < num of dtors calls"); + EXPECT_FALSE(MemoryChecker::alive_objects() > 0, "wrong effect from unique: number of ctors calls > num of dtors calls"); + std::cout << done() << std::endl; return 0; } diff --git a/pstl/test/std/algorithms/alg.sorting/alg.set.operations/set.pass.cpp b/pstl/test/std/algorithms/alg.sorting/alg.set.operations/set.pass.cpp index 5b86dd5..c85d0e9 100644 --- a/pstl/test/std/algorithms/alg.sorting/alg.set.operations/set.pass.cpp +++ b/pstl/test/std/algorithms/alg.sorting/alg.set.operations/set.pass.cpp @@ -51,7 +51,8 @@ struct Num } }; -struct test_one_policy +template <typename Type> +struct test_set_union { template <typename Policy, typename InputIterator1, typename InputIterator2, typename Compare> typename std::enable_if<!TestUtils::isReverse<InputIterator1>::value, void>::type @@ -66,30 +67,101 @@ struct test_one_policy Sequence<T1> expect(n); Sequence<T1> out(n); - //1. set_union auto expect_res = std::set_union(first1, last1, first2, last2, expect.begin(), comp); auto res = std::set_union(exec, first1, last1, first2, last2, out.begin(), comp); EXPECT_TRUE(expect_res - expect.begin() == res - out.begin(), "wrong result for set_union"); EXPECT_EQ_N(expect.begin(), out.begin(), std::distance(out.begin(), res), "wrong set_union effect"); + } - //2. set_intersection - expect_res = std::set_intersection(first1, last1, first2, last2, expect.begin(), comp); - res = std::set_intersection(exec, first1, last1, first2, last2, out.begin(), comp); + template <typename Policy, typename InputIterator1, typename InputIterator2, typename Compare> + typename std::enable_if<TestUtils::isReverse<InputIterator1>::value, void>::type + operator()(Policy&& exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, + Compare comp) + { + } +}; + +template <typename Type> +struct test_set_intersection +{ + template <typename Policy, typename InputIterator1, typename InputIterator2, typename Compare> + typename std::enable_if<!TestUtils::isReverse<InputIterator1>::value, void>::type + operator()(Policy&& exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, + Compare comp) + { + using T1 = typename std::iterator_traits<InputIterator1>::value_type; + + auto n1 = std::distance(first1, last1); + auto n2 = std::distance(first2, last2); + auto n = n1 + n2; + Sequence<T1> expect(n); + Sequence<T1> out(n); + + auto expect_res = std::set_intersection(first1, last1, first2, last2, expect.begin(), comp); + auto res = std::set_intersection(exec, first1, last1, first2, last2, out.begin(), comp); EXPECT_TRUE(expect_res - expect.begin() == res - out.begin(), "wrong result for set_intersection"); EXPECT_EQ_N(expect.begin(), out.begin(), std::distance(out.begin(), res), "wrong set_intersection effect"); + } + + template <typename Policy, typename InputIterator1, typename InputIterator2, typename Compare> + typename std::enable_if<TestUtils::isReverse<InputIterator1>::value, void>::type + operator()(Policy&& exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, + Compare comp) + { + } +}; - //3. set_difference - expect_res = std::set_difference(first1, last1, first2, last2, expect.begin(), comp); - res = std::set_difference(exec, first1, last1, first2, last2, out.begin(), comp); +template <typename Type> +struct test_set_difference +{ + template <typename Policy, typename InputIterator1, typename InputIterator2, typename Compare> + typename std::enable_if<!TestUtils::isReverse<InputIterator1>::value, void>::type + operator()(Policy&& exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, + Compare comp) + { + using T1 = typename std::iterator_traits<InputIterator1>::value_type; + + auto n1 = std::distance(first1, last1); + auto n2 = std::distance(first2, last2); + auto n = n1 + n2; + Sequence<T1> expect(n); + Sequence<T1> out(n); + + auto expect_res = std::set_difference(first1, last1, first2, last2, expect.begin(), comp); + auto res = std::set_difference(exec, first1, last1, first2, last2, out.begin(), comp); EXPECT_TRUE(expect_res - expect.begin() == res - out.begin(), "wrong result for set_difference"); EXPECT_EQ_N(expect.begin(), out.begin(), std::distance(out.begin(), res), "wrong set_difference effect"); + } + + template <typename Policy, typename InputIterator1, typename InputIterator2, typename Compare> + typename std::enable_if<TestUtils::isReverse<InputIterator1>::value, void>::type + operator()(Policy&& exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, + Compare comp) + { + } +}; - //4. set_symmetric_difference - expect_res = std::set_symmetric_difference(first1, last1, first2, last2, expect.begin(), comp); - res = std::set_symmetric_difference(exec, first1, last1, first2, last2, out.begin(), comp); +template <typename Type> +struct test_set_symmetric_difference +{ + template <typename Policy, typename InputIterator1, typename InputIterator2, typename Compare> + typename std::enable_if<!TestUtils::isReverse<InputIterator1>::value, void>::type + operator()(Policy&& exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, + Compare comp) + { + using T1 = typename std::iterator_traits<InputIterator1>::value_type; + + auto n1 = std::distance(first1, last1); + auto n2 = std::distance(first2, last2); + auto n = n1 + n2; + Sequence<T1> expect(n); + Sequence<T1> out(n); + + auto expect_res = std::set_symmetric_difference(first1, last1, first2, last2, expect.begin(), comp); + auto res = std::set_symmetric_difference(exec, first1, last1, first2, last2, out.begin(), comp); EXPECT_TRUE(expect_res - expect.begin() == res - out.begin(), "wrong result for set_symmetric_difference"); EXPECT_EQ_N(expect.begin(), out.begin(), std::distance(out.begin(), res), @@ -118,31 +190,68 @@ test_set(Compare compare) for (std::size_t m = 0; m < n_max; m = m <= 16 ? m + 1 : size_t(2.71828 * m)) { //prepare the input ranges - Sequence<T1> in1(n, [](std::size_t k) { return rand() % (2 * k + 1); }); + Sequence<T1> in1(n, [n](std::size_t k) { return rand() % (2 * k + 1); }); Sequence<T2> in2(m, [m](std::size_t k) { return (m % 2) * rand() + rand() % (k + 1); }); std::sort(in1.begin(), in1.end(), compare); std::sort(in2.begin(), in2.end(), compare); - invoke_on_all_policies(test_one_policy(), in1.begin(), in1.end(), in2.cbegin(), in2.cend(), compare); + invoke_on_all_policies(test_set_union<T1>(), in1.begin(), in1.end(), in2.cbegin(), in2.cend(), + compare); + + invoke_on_all_policies(test_set_intersection<T1>(), in1.begin(), in1.end(), in2.cbegin(), in2.cend(), + compare); + + invoke_on_all_policies(test_set_difference<T1>(), in1.begin(), in1.end(), in2.cbegin(), in2.cend(), + compare); + + invoke_on_all_policies(test_set_symmetric_difference<T1>(), in1.begin(), in1.end(), in2.cbegin(), + in2.cend(), compare); } } } template <typename T> -struct test_non_const +struct test_non_const_set_difference { template <typename Policy, typename InputIterator, typename OutputInterator> void operator()(Policy&& exec, InputIterator input_iter, OutputInterator out_iter) { set_difference(exec, input_iter, input_iter, input_iter, input_iter, out_iter, non_const(std::less<T>())); + } +}; +template <typename T> +struct test_non_const_set_intersection +{ + template <typename Policy, typename InputIterator, typename OutputInterator> + void + operator()(Policy&& exec, InputIterator input_iter, OutputInterator out_iter) + { set_intersection(exec, input_iter, input_iter, input_iter, input_iter, out_iter, non_const(std::less<T>())); + } +}; +template <typename T> +struct test_non_const_set_symmetric_difference +{ + template <typename Policy, typename InputIterator, typename OutputInterator> + void + operator()(Policy&& exec, InputIterator input_iter, OutputInterator out_iter) + { set_symmetric_difference(exec, input_iter, input_iter, input_iter, input_iter, out_iter, non_const(std::less<T>())); + } +}; +template <typename T> +struct test_non_const_set_union +{ + template <typename Policy, typename InputIterator, typename OutputInterator> + void + operator()(Policy&& exec, InputIterator input_iter, OutputInterator out_iter) + { set_union(exec, input_iter, input_iter, input_iter, input_iter, out_iter, non_const(std::less<T>())); } }; @@ -154,7 +263,19 @@ main() test_set<float64_t, float64_t>(std::less<>()); test_set<Num<int64_t>, Num<int32_t>>([](const Num<int64_t>& x, const Num<int32_t>& y) { return x < y; }); - test_algo_basic_double<int32_t>(run_for_rnd_fw<test_non_const<int32_t>>()); + test_set<MemoryChecker, MemoryChecker>([](const MemoryChecker& val1, const MemoryChecker& val2) -> bool { + return val1.value() < val2.value(); + }); + EXPECT_FALSE(MemoryChecker::alive_objects() < 0, "wrong effect from set algorithms: number of ctors calls < num of dtors calls"); + EXPECT_FALSE(MemoryChecker::alive_objects() > 0, "wrong effect from set algorithms: number of ctors calls > num of dtors calls"); + + test_algo_basic_double<int32_t>(run_for_rnd_fw<test_non_const_set_difference<int32_t>>()); + + test_algo_basic_double<int32_t>(run_for_rnd_fw<test_non_const_set_intersection<int32_t>>()); + + test_algo_basic_double<int32_t>(run_for_rnd_fw<test_non_const_set_symmetric_difference<int32_t>>()); + + test_algo_basic_double<int32_t>(run_for_rnd_fw<test_non_const_set_union<int32_t>>()); std::cout << done() << std::endl; diff --git a/pstl/test/std/algorithms/alg.sorting/partial_sort_copy.pass.cpp b/pstl/test/std/algorithms/alg.sorting/partial_sort_copy.pass.cpp index 3fe1d5a..ad0f0d6 100644 --- a/pstl/test/std/algorithms/alg.sorting/partial_sort_copy.pass.cpp +++ b/pstl/test/std/algorithms/alg.sorting/partial_sort_copy.pass.cpp @@ -186,6 +186,11 @@ main() test_algo_basic_double<int32_t>(run_for_rnd<test_non_const<int32_t>>()); + test_partial_sort_copy<MemoryChecker>( + [](const MemoryChecker& val1, const MemoryChecker& val2){ return val1.value() < val2.value(); }); + EXPECT_FALSE(MemoryChecker::alive_objects() < 0, "wrong effect from partial_sort_copy: number of ctors calls < num of dtors calls"); + EXPECT_FALSE(MemoryChecker::alive_objects() > 0, "wrong effect from partial_sort_copy: number of ctors calls > num of dtors calls"); + std::cout << done() << std::endl; return 0; } diff --git a/pstl/test/support/utils.h b/pstl/test/support/utils.h index 541dc8c..090f937 100644 --- a/pstl/test/support/utils.h +++ b/pstl/test/support/utils.h @@ -231,6 +231,82 @@ fill_data(Iterator first, Iterator last, F f) } } +struct MemoryChecker { + // static counters and state tags + static std::atomic<std::int64_t> alive_object_counter; // initialized outside + static constexpr std::int64_t alive_state = 0xAAAAAAAAAAAAAAAA; + static constexpr std::int32_t dead_state = 0; // only used as a set value to cancel alive_state + + std::int32_t _value; // object value used for algorithms + std::int64_t _state; // state tag used for checks + + // ctors, dtors, assign ops + explicit MemoryChecker(std::int32_t value = 0) : _value(value) { + // check for EXPECT_TRUE(state() != alive_state, ...) has not been done since we cannot guarantee that + // raw memory for object being constructed does not have a bit sequence being equal to alive_state + + // set constructed state and increment counter for living object + inc_alive_objects(); + _state = alive_state; + } + MemoryChecker(MemoryChecker&& other) : _value(other.value()) { + // check for EXPECT_TRUE(state() != alive_state, ...) has not been done since + // compiler can optimize out the move ctor call that results in false positive failure + EXPECT_TRUE(other.state() == alive_state, "wrong effect from MemoryChecker(MemoryChecker&&): attemp to construct an object from non-existing object"); + // set constructed state and increment counter for living object + inc_alive_objects(); + _state = alive_state; + } + MemoryChecker(const MemoryChecker& other) : _value(other.value()) { + // check for EXPECT_TRUE(state() != alive_state, ...) has not been done since + // compiler can optimize out the copy ctor call that results in false positive failure + EXPECT_TRUE(other.state() == alive_state, "wrong effect from MemoryChecker(const MemoryChecker&): attemp to construct an object from non-existing object"); + // set constructed state and increment counter for living object + inc_alive_objects(); + _state = alive_state; + } + MemoryChecker& operator=(MemoryChecker&& other) { + // check if we do not assign over uninitialized memory + EXPECT_TRUE(state() == alive_state, "wrong effect from MemoryChecker::operator=(MemoryChecker&& other): attemp to assign to non-existing object"); + EXPECT_TRUE(other.state() == alive_state, "wrong effect from MemoryChecker::operator=(MemoryChecker&& other): attemp to assign from non-existing object"); + // just assign new value, counter is the same, state is the same + _value = other.value(); + + return *this; + } + MemoryChecker& operator=(const MemoryChecker& other) { + // check if we do not assign over uninitialized memory + EXPECT_TRUE(state() == alive_state, "wrong effect from MemoryChecker::operator=(const MemoryChecker& other): attemp to assign to non-existing object"); + EXPECT_TRUE(other.state() == alive_state, "wrong effect from MemoryChecker::operator=(const MemoryChecker& other): attemp to assign from non-existing object"); + // just assign new value, counter is the same, state is the same + _value = other.value(); + + return *this; + } + ~MemoryChecker() { + // check if we do not double destruct the object + EXPECT_TRUE(state() == alive_state, "wrong effect from ~MemoryChecker(): attemp to destroy non-existing object"); + // set destructed state and decrement counter for living object + static_cast<volatile std::int64_t&>(_state) = dead_state; + dec_alive_objects(); + } + + // getters + std::int32_t value() const { return _value; } + std::int64_t state() const { return _state; } + static std::int32_t alive_objects() { return alive_object_counter.load(); } +private: + // setters + void inc_alive_objects() { alive_object_counter.fetch_add(1); } + void dec_alive_objects() { alive_object_counter.fetch_sub(1); } +}; + +std::atomic<std::int64_t> MemoryChecker::alive_object_counter{0}; + +std::ostream& operator<<(std::ostream& os, const MemoryChecker& val) { return (os << val.value()); } +bool operator==(const MemoryChecker& v1, const MemoryChecker& v2) { return v1.value() == v2.value(); } +bool operator<(const MemoryChecker& v1, const MemoryChecker& v2) { return v1.value() < v2.value(); } + // Sequence<T> is a container of a sequence of T with lots of kinds of iterators. // Prefixes on begin/end mean: // c = "const" |