1 // -*- C++ -*- 2 //===-- partition.pass.cpp ------------------------------------------------===// 3 // 4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5 // See https://llvm.org/LICENSE.txt for license information. 6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7 // 8 //===----------------------------------------------------------------------===// 9 10 // Tests for stable_partition and partition 11 #include "support/pstl_test_config.h" 12 13 #ifdef PSTL_STANDALONE_TESTS 14 #include "pstl/execution" 15 #include "pstl/algorithm" 16 #else 17 #include <execution> 18 #include <algorithm> 19 #endif // PSTL_STANDALONE_TESTS 20 21 #include "support/utils.h" 22 23 #include <iterator> 24 #include <type_traits> 25 26 using namespace TestUtils; 27 28 template <typename T> 29 struct DataType 30 { 31 explicit DataType(int32_t k) : my_val(k) {} 32 DataType(DataType&& input) { my_val = std::move(input.my_val); } 33 DataType& 34 operator=(DataType&& input) 35 { 36 my_val = std::move(input.my_val); 37 return *this; 38 } 39 T 40 get_val() const 41 { 42 return my_val; 43 } 44 45 friend std::ostream& 46 operator<<(std::ostream& stream, const DataType<T>& input) 47 { 48 return stream << input.my_val; 49 } 50 51 private: 52 T my_val; 53 }; 54 55 template <typename Iterator> 56 typename std::enable_if<std::is_trivial<typename std::iterator_traits<Iterator>::value_type>::value, bool>::type 57 is_equal(Iterator first, Iterator last, Iterator d_first) 58 { 59 return std::equal(first, last, d_first); 60 } 61 62 template <typename Iterator> 63 typename std::enable_if<!std::is_trivial<typename std::iterator_traits<Iterator>::value_type>::value, bool>::type 64 is_equal(Iterator first, Iterator last, Iterator d_first) 65 { 66 return true; 67 } 68 69 struct test_one_policy 70 { 71 #if __PSTL_ICC_17_VC141_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN || \ 72 __PSTL_ICC_16_VC14_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN //dummy specializations to skip testing in case of broken configuration 73 template <typename BiDirIt, typename Size, typename UnaryOp, typename Generator> 74 void 75 operator()(pstl::execution::unsequenced_policy, BiDirIt first, BiDirIt last, BiDirIt exp_first, BiDirIt exp_last, 76 Size n, UnaryOp unary_op, Generator generator) 77 { 78 } 79 80 template <typename BiDirIt, typename Size, typename UnaryOp, typename Generator> 81 void 82 operator()(pstl::execution::parallel_unsequenced_policy, BiDirIt first, BiDirIt last, BiDirIt exp_first, 83 BiDirIt exp_last, Size n, UnaryOp unary_op, Generator generator) 84 { 85 } 86 #elif __PSTL_ICC_16_VC14_TEST_PAR_TBB_RT_RELEASE_64_BROKEN //dummy specializations to skip testing in case of broken configuration 87 template <typename BiDirIt, typename Size, typename UnaryOp, typename Generator> 88 void 89 operator()(pstl::execution::parallel_policy, BiDirIt first, BiDirIt last, BiDirIt exp_first, BiDirIt exp_last, 90 Size n, UnaryOp unary_op, Generator generator) 91 { 92 } 93 94 template <typename BiDirIt, typename Size, typename UnaryOp, typename Generator> 95 void 96 operator()(pstl::execution::parallel_unsequenced_policy, BiDirIt first, BiDirIt last, BiDirIt exp_first, 97 BiDirIt exp_last, Size n, UnaryOp unary_op, Generator generator) 98 { 99 } 100 #endif 101 102 template <typename Policy, typename BiDirIt, typename Size, typename UnaryOp, typename Generator> 103 typename std::enable_if<!is_same_iterator_category<BiDirIt, std::forward_iterator_tag>::value, void>::type 104 operator()(Policy&& exec, BiDirIt first, BiDirIt last, BiDirIt exp_first, BiDirIt exp_last, Size n, 105 UnaryOp unary_op, Generator generator) 106 { 107 // partition 108 { 109 fill_data(first, last, generator); 110 BiDirIt actual_ret = std::partition(exec, first, last, unary_op); 111 EXPECT_TRUE(std::all_of(first, actual_ret, unary_op) && !std::any_of(actual_ret, last, unary_op), 112 "wrong effect from partition"); 113 } 114 // stable_partition 115 { 116 fill_data(exp_first, exp_last, generator); 117 BiDirIt exp_ret = std::stable_partition(exp_first, exp_last, unary_op); 118 fill_data(first, last, generator); 119 BiDirIt actual_ret = std::stable_partition(exec, first, last, unary_op); 120 121 EXPECT_TRUE(std::distance(first, actual_ret) == std::distance(exp_first, exp_ret), 122 "wrong result from stable_partition"); 123 EXPECT_TRUE((is_equal<BiDirIt>(exp_first, exp_last, first)), "wrong effect from stable_partition"); 124 } 125 } 126 template <typename Policy, typename BiDirIt, typename Size, typename UnaryOp, typename Generator> 127 typename std::enable_if<is_same_iterator_category<BiDirIt, std::forward_iterator_tag>::value, void>::type 128 operator()(Policy&& exec, BiDirIt first, BiDirIt last, BiDirIt exp_first, BiDirIt exp_last, Size n, 129 UnaryOp unary_op, Generator generator) 130 { 131 } 132 }; 133 134 template <typename T, typename Generator, typename UnaryPred> 135 void 136 test_by_type(Generator generator, UnaryPred pred) 137 { 138 139 using namespace std; 140 size_t max_size = 100000; 141 Sequence<T> in(max_size, [](size_t v) { return T(v); }); 142 Sequence<T> exp(max_size, [](size_t v) { return T(v); }); 143 144 for (size_t n = 0; n <= max_size; n = n <= 16 ? n + 1 : size_t(3.1415 * n)) 145 { 146 invoke_on_all_policies(test_one_policy(), in.begin(), in.begin() + n, exp.begin(), exp.begin() + n, n, pred, 147 generator); 148 } 149 } 150 151 struct test_non_const 152 { 153 template <typename Policy, typename Iterator> 154 void 155 operator()(Policy&& exec, Iterator iter) 156 { 157 auto is_even = [&](float64_t v) { 158 uint32_t i = (uint32_t)v; 159 return i % 2 == 0; 160 }; 161 invoke_if(exec, [&]() { 162 partition(exec, iter, iter, non_const(is_even)); 163 stable_partition(exec, iter, iter, non_const(is_even)); 164 }); 165 } 166 }; 167 168 int32_t 169 main() 170 { 171 #if !__PSTL_ICC_16_17_TEST_REDUCTION_RELEASE_BROKEN 172 test_by_type<int32_t>([](int32_t i) { return i; }, [](int32_t) { return true; }); 173 #endif 174 test_by_type<float64_t>([](int32_t i) { return -i; }, [](const float64_t x) { return x < 0; }); 175 test_by_type<int64_t>([](int32_t i) { return i + 1; }, [](int64_t x) { return x % 3 == 0; }); 176 test_by_type<DataType<float32_t>>([](int32_t i) { return DataType<float32_t>(2 * i + 1); }, 177 [](const DataType<float32_t>& x) { return x.get_val() < 0; }); 178 179 test_algo_basic_single<int32_t>(run_for_rnd_bi<test_non_const>()); 180 181 std::cout << done() << std::endl; 182 return 0; 183 } 184