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