1 // -*- C++ -*-
2 // { dg-options "-std=gnu++17 -ltbb" }
3 // { dg-do run { target c++17 } }
4 // { dg-require-effective-target tbb-backend }
5
6 //===-- partial_sort.pass.cpp ---------------------------------------------===//
7 //
8 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
9 // See https://llvm.org/LICENSE.txt for license information.
10 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "pstl/pstl_test_config.h"
15
16
17 #include <cmath>
18
19 #ifdef PSTL_STANDALONE_TESTS
20 #include "pstl/execution"
21 #include "pstl/algorithm"
22 #else
23 #include <execution>
24 #include <algorithm>
25 #endif // PSTL_STANDALONE_TESTS
26
27 #include "pstl/test_utils.h"
28
29 using namespace TestUtils;
30
31 static std::atomic<int32_t> count_val;
32 static std::atomic<int32_t> count_comp;
33
34 template <typename T>
35 struct Num
36 {
37 T val;
38
NumNum39 Num() { ++count_val; }
NumNum40 Num(T v) : val(v) { ++count_val; }
NumNum41 Num(const Num<T>& v) : val(v.val) { ++count_val; }
NumNum42 Num(Num<T>&& v) : val(v.val) { ++count_val; }
~NumNum43 ~Num() { --count_val; }
44 Num<T>&
operator =Num45 operator=(const Num<T>& v)
46 {
47 val = v.val;
48 return *this;
49 }
operator TNum50 operator T() const { return val; }
51 bool
operator <Num52 operator<(const Num<T>& v) const
53 {
54 ++count_comp;
55 return val < v.val;
56 }
57 };
58
59 struct test_brick_partial_sort
60 {
61 template <typename Policy, typename InputIterator, typename Compare>
62 typename std::enable_if<is_same_iterator_category<InputIterator, std::random_access_iterator_tag>::value,
63 void>::type
operator ()test_brick_partial_sort64 operator()(Policy&& exec, InputIterator first, InputIterator last, InputIterator exp_first, InputIterator exp_last,
65 Compare compare)
66 {
67
68 typedef typename std::iterator_traits<InputIterator>::value_type T;
69
70 // The rand()%(2*n+1) encourages generation of some duplicates.
71 std::srand(42);
72 const std::size_t n = last - first;
73 for (std::size_t k = 0; k < n; ++k)
74 {
75 first[k] = T(rand() % (2 * n + 1));
76 }
77 std::copy(first, last, exp_first);
78
79 for (std::size_t p = 0; p < n; p = p <= 16 ? p + 1 : std::size_t(31.415 * p))
80 {
81 auto m1 = first + p;
82 auto m2 = exp_first + p;
83
84 std::partial_sort(exp_first, m2, exp_last, compare);
85 count_comp = 0;
86 std::partial_sort(exec, first, m1, last, compare);
87 EXPECT_EQ_N(exp_first, first, p, "wrong effect from partial_sort");
88
89 //checking upper bound number of comparisons; O(p*(last-first)log(middle-first)); where p - number of threads;
90 if (m1 - first > 1)
91 {
92 auto complex = std::ceil(n * std::log(float32_t(m1 - first)));
93 #if __PSTL_USE_PAR_POLICIES
94 auto p = tbb::this_task_arena::max_concurrency();
95 #else
96 auto p = 1;
97 #endif
98
99 #ifdef _DEBUG
100 if (count_comp > complex * p)
101 {
102 std::cout << "complexity exceeded" << std::endl;
103 }
104 #endif
105 }
106 }
107 }
108
109 template <typename Policy, typename InputIterator, typename Compare>
110 typename std::enable_if<!is_same_iterator_category<InputIterator, std::random_access_iterator_tag>::value,
111 void>::type
operator ()test_brick_partial_sort112 operator()(Policy&& exec, InputIterator first, InputIterator last, InputIterator exp_first, InputIterator exp_last,
113 Compare compare)
114 {
115 }
116 };
117
118 template <typename T, typename Compare>
119 void
test_partial_sort(Compare compare)120 test_partial_sort(Compare compare)
121 {
122
123 const std::size_t n_max = 100000;
124 Sequence<T> in(n_max);
125 Sequence<T> exp(n_max);
126 for (std::size_t n = 0; n < n_max; n = n <= 16 ? n + 1 : size_t(3.1415 * n))
127 {
128 invoke_on_all_policies(test_brick_partial_sort(), in.begin(), in.begin() + n, exp.begin(), exp.begin() + n,
129 compare);
130 }
131 }
132
133 template <typename T>
134 struct test_non_const
135 {
136 template <typename Policy, typename Iterator>
137 void
operator ()test_non_const138 operator()(Policy&& exec, Iterator iter)
139 {
140 partial_sort(exec, iter, iter, iter, non_const(std::less<T>()));
141 }
142 };
143
144 int32_t
main()145 main()
146 {
147 count_val = 0;
148
149 test_partial_sort<Num<float32_t>>([](Num<float32_t> x, Num<float32_t> y) { return x < y; });
150
151 EXPECT_TRUE(count_val == 0, "cleanup error");
152
153 test_partial_sort<int32_t>(
154 [](int32_t x, int32_t y) { return x > y; }); // Reversed so accidental use of < will be detected.
155
156 test_algo_basic_single<int32_t>(run_for_rnd<test_non_const<int32_t>>());
157
158 std::cout << done() << std::endl;
159 return 0;
160 }
161