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