1 // -*- C++ -*-
2 //===-- partial_sort.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 // UNSUPPORTED: c++03, c++11, c++14
11
12 #include "support/pstl_test_config.h"
13
14 #include <cmath>
15 #include <execution>
16 #include <algorithm>
17
18 #include "support/utils.h"
19
20 using namespace TestUtils;
21
22 static std::atomic<int32_t> count_val;
23 static std::atomic<int32_t> count_comp;
24
25 template <typename T>
26 struct Num
27 {
28 T val;
29
NumNum30 Num() { ++count_val; }
NumNum31 Num(T v) : val(v) { ++count_val; }
NumNum32 Num(const Num<T>& v) : val(v.val) { ++count_val; }
NumNum33 Num(Num<T>&& v) : val(v.val) { ++count_val; }
~NumNum34 ~Num() { --count_val; }
35 Num<T>&
operator =Num36 operator=(const Num<T>& v)
37 {
38 val = v.val;
39 return *this;
40 }
operator TNum41 operator T() const { return val; }
42 bool
operator <Num43 operator<(const Num<T>& v) const
44 {
45 ++count_comp;
46 return val < v.val;
47 }
48 };
49
50 struct test_brick_partial_sort
51 {
52 template <typename Policy, typename InputIterator, typename Compare>
53 typename std::enable_if<is_same_iterator_category<InputIterator, std::random_access_iterator_tag>::value,
54 void>::type
operator ()test_brick_partial_sort55 operator()(Policy&& exec, InputIterator first, InputIterator last, InputIterator exp_first, InputIterator exp_last,
56 Compare compare)
57 {
58
59 typedef typename std::iterator_traits<InputIterator>::value_type T;
60
61 // The rand()%(2*n+1) encourages generation of some duplicates.
62 std::srand(42);
63 const std::size_t n = last - first;
64 for (std::size_t k = 0; k < n; ++k)
65 {
66 first[k] = T(rand() % (2 * n + 1));
67 }
68 std::copy(first, last, exp_first);
69
70 for (std::size_t p = 0; p < n; p = p <= 16 ? p + 1 : std::size_t(31.415 * p))
71 {
72 auto m1 = first + p;
73 auto m2 = exp_first + p;
74
75 std::partial_sort(exp_first, m2, exp_last, compare);
76 count_comp = 0;
77 std::partial_sort(exec, first, m1, last, compare);
78 EXPECT_EQ_N(exp_first, first, p, "wrong effect from partial_sort");
79
80 //checking upper bound number of comparisons; O(p*(last-first)log(middle-first)); where p - number of threads;
81 if (m1 - first > 1)
82 {
83 #ifdef _DEBUG
84 # if defined(_PSTL_PAR_BACKEND_TBB)
85 auto p = tbb::this_task_arena::max_concurrency();
86 # else
87 auto p = 1;
88 # endif
89 auto complex = std::ceil(n * std::log(float32_t(m1 - first)));
90 if (count_comp > complex * p)
91 {
92 std::cout << "complexity exceeded" << std::endl;
93 }
94 #endif // _DEBUG
95 }
96 }
97 }
98
99 template <typename Policy, typename InputIterator, typename Compare>
100 typename std::enable_if<!is_same_iterator_category<InputIterator, std::random_access_iterator_tag>::value,
101 void>::type
operator ()test_brick_partial_sort102 operator()(Policy&&, InputIterator, InputIterator, InputIterator, InputIterator, Compare)
103 {
104 }
105 };
106
107 template <typename T, typename Compare>
108 void
test_partial_sort(Compare compare)109 test_partial_sort(Compare compare)
110 {
111
112 const std::size_t n_max = 100000;
113 Sequence<T> in(n_max);
114 Sequence<T> exp(n_max);
115 for (std::size_t n = 0; n < n_max; n = n <= 16 ? n + 1 : size_t(3.1415 * n))
116 {
117 invoke_on_all_policies(test_brick_partial_sort(), in.begin(), in.begin() + n, exp.begin(), exp.begin() + n,
118 compare);
119 }
120 }
121
122 template <typename T>
123 struct test_non_const
124 {
125 template <typename Policy, typename Iterator>
126 void
operator ()test_non_const127 operator()(Policy&& exec, Iterator iter)
128 {
129 partial_sort(exec, iter, iter, iter, non_const(std::less<T>()));
130 }
131 };
132
133 int
main()134 main()
135 {
136 count_val = 0;
137
138 test_partial_sort<Num<float32_t>>([](Num<float32_t> x, Num<float32_t> y) { return x < y; });
139
140 EXPECT_TRUE(count_val == 0, "cleanup error");
141
142 test_partial_sort<int32_t>(
143 [](int32_t x, int32_t y) { return x > y; }); // Reversed so accidental use of < will be detected.
144
145 test_algo_basic_single<int32_t>(run_for_rnd<test_non_const<int32_t>>());
146
147 std::cout << done() << std::endl;
148 return 0;
149 }
150