1// -*- C++ -*-
2//===-- 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 <execution>
15#include <algorithm>
16
17#include "support/utils.h"
18
19using namespace TestUtils;
20#define _CRT_SECURE_NO_WARNINGS
21
22#include <atomic>
23
24static bool Stable;
25
26//! Number of extant keys
27static std::atomic<int32_t> KeyCount;
28
29//! One more than highest index in array to be sorted.
30static uint32_t LastIndex;
31
32//! Keeping Equal() static and a friend of ParanoidKey class (C++, paragraphs 3.5/7.1.1)
33class ParanoidKey;
34static bool
35Equal(const ParanoidKey& x, const ParanoidKey& y);
36
37//! A key to be sorted, with lots of checking.
38class ParanoidKey
39{
40 //! Value used by comparator
41 int32_t value;
42 //! Original position or special value (Empty or Dead)
43 int32_t index;
44 //! Special value used to mark object without a comparable value, e.g. after being moved from.
45 static const int32_t Empty = -1;
46 //! Special value used to mark destroyed objects.
47 static const int32_t Dead = -2;
48 // True if key object has comparable value
49 bool
50 isLive() const
51 {
52 return (uint32_t)(index) < LastIndex;
53 }
54 // True if key object has been constructed.
55 bool
56 isConstructed() const
57 {
58 return isLive() || index == Empty;
59 }
60
61 public:
62 ParanoidKey()
63 {
64 ++KeyCount;
65 index = Empty;
66 value = Empty;
67 }
68 ParanoidKey(const ParanoidKey& k) : value(k.value), index(k.index)
69 {
70 EXPECT_TRUE(k.isLive(), "source for copy-constructor is dead");
71 ++KeyCount;
72 }
73 ~ParanoidKey()
74 {
75 EXPECT_TRUE(isConstructed(), "double destruction");
76 index = Dead;
77 --KeyCount;
78 }
79 ParanoidKey&
80 operator=(const ParanoidKey& k)
81 {
82 EXPECT_TRUE(k.isLive(), "source for copy-assignment is dead");
83 EXPECT_TRUE(isConstructed(), "destination for copy-assignment is dead");
84 value = k.value;
85 index = k.index;
86 return *this;
87 }
88 ParanoidKey(int32_t index, int32_t value, OddTag) : value(value), index(index) {}
89 ParanoidKey(ParanoidKey&& k) : value(k.value), index(k.index)
90 {
91 EXPECT_TRUE(k.isConstructed(), "source for move-construction is dead");
92// std::stable_sort() fails in move semantics on paranoid test before VS2015
93#if !defined(_MSC_VER) || _MSC_VER >= 1900
94 k.index = Empty;
95#endif
96 ++KeyCount;
97 }
98 ParanoidKey&
99 operator=(ParanoidKey&& k)
100 {
101 EXPECT_TRUE(k.isConstructed(), "source for move-assignment is dead");
102 EXPECT_TRUE(isConstructed(), "destination for move-assignment is dead");
103 value = k.value;
104 index = k.index;
105// std::stable_sort() fails in move semantics on paranoid test before VS2015
106#if !defined(_MSC_VER) || _MSC_VER >= 1900
107 k.index = Empty;
108#endif
109 return *this;
110 }
111 friend class KeyCompare;
112 friend bool
113 Equal(const ParanoidKey& x, const ParanoidKey& y);
114};
115
116class KeyCompare
117{
118 enum statusType
119 {
120 //! Special value used to mark defined object.
121 Live = 0xabcd,
122 //! Special value used to mark destroyed objects.
123 Dead = -1
124 } status;
125
126 public:
127 KeyCompare(OddTag) : status(Live) {}
128 ~KeyCompare() { status = Dead; }
129 bool
130 operator()(const ParanoidKey& j, const ParanoidKey& k) const
131 {
132 EXPECT_TRUE(status == Live, "key comparison object not defined");
133 EXPECT_TRUE(j.isLive(), "first key to operator() is not live");
134 EXPECT_TRUE(k.isLive(), "second key to operator() is not live");
135 return j.value < k.value;
136 }
137};
138
139// Equal is equality comparison used for checking result of sort against expected result.
140static bool
141Equal(const ParanoidKey& x, const ParanoidKey& y)
142{
143 return (x.value == y.value && !Stable) || (x.index == y.index);
144}
145
146static bool
147Equal(float32_t x, float32_t y)
148{
149 return x == y;
150}
151
152static bool
153Equal(int32_t x, int32_t y)
154{
155 return x == y;
156}
157
158struct test_sort_with_compare
159{
160 template <typename Policy, typename InputIterator, typename OutputIterator, typename OutputIterator2, typename Size,
161 typename Compare>
162 typename std::enable_if<is_same_iterator_category<InputIterator, std::random_access_iterator_tag>::value,
163 void>::type
164 operator()(Policy&& exec, OutputIterator tmp_first, OutputIterator tmp_last, OutputIterator2 expected_first,
165 OutputIterator2 expected_last, InputIterator first, InputIterator, Size n, Compare compare)
166 {
167 using namespace std;
168 copy_n(first, n, expected_first);
169 copy_n(first, n, tmp_first);
170 if (Stable)
171 std::stable_sort(expected_first + 1, expected_last - 1, compare);
172 else
173 std::sort(expected_first + 1, expected_last - 1, compare);
174 int32_t count0 = KeyCount;
175 if (Stable)
176 stable_sort(exec, tmp_first + 1, tmp_last - 1, compare);
177 else
178 sort(exec, tmp_first + 1, tmp_last - 1, compare);
179
180 for (size_t i = 0; i < n; ++i, ++expected_first, ++tmp_first)
181 {
182 // Check that expected[i] is equal to tmp[i]
183 EXPECT_TRUE(Equal(*expected_first, *tmp_first), "bad sort");
184 }
185 int32_t count1 = KeyCount;
186 EXPECT_EQ(count0, count1, "key cleanup error");
187 }
188 template <typename Policy, typename InputIterator, typename OutputIterator, typename OutputIterator2, typename Size,
189 typename Compare>
190 typename std::enable_if<!is_same_iterator_category<InputIterator, std::random_access_iterator_tag>::value,
191 void>::type
192 operator()(Policy&&, OutputIterator, OutputIterator, OutputIterator2, OutputIterator2, InputIterator, InputIterator,
193 Size, Compare)
194 {
195 }
196};
197
198template <typename T, typename Compare, typename Convert>
199void
200test_sort(Compare compare, Convert convert)
201{
202 for (size_t n = 0; n < 100000; n = n <= 16 ? n + 1 : size_t(3.1415 * n))
203 {
204 LastIndex = n + 2;
205 // The rand()%(2*n+1) encourages generation of some duplicates.
206 // Sequence is padded with an extra element at front and back, to detect overwrite bugs.
207 Sequence<T> in(n + 2, [=](size_t k) { return convert(k, rand() % (2 * n + 1)); });
208 Sequence<T> expected(in);
209 Sequence<T> tmp(in);
210 invoke_on_all_policies(test_sort_with_compare(), tmp.begin(), tmp.end(), expected.begin(), expected.end(),
211 in.begin(), in.end(), in.size(), compare);
212 }
213}
214
215template <typename T>
216struct test_non_const
217{
218 template <typename Policy, typename Iterator>
219 void
220 operator()(Policy&& exec, Iterator iter)
221 {
222 sort(exec, iter, iter, non_const(std::less<T>()));
223 stable_sort(exec, iter, iter, non_const(std::less<T>()));
224 }
225};
226
227int
228main()
229{
230 std::srand(seed: 42);
231 for (int32_t kind = 0; kind < 2; ++kind)
232 {
233 Stable = kind != 0;
234 test_sort<ParanoidKey>(compare: KeyCompare(OddTag()),
235 convert: [](size_t k, size_t val) { return ParanoidKey(k, val, OddTag()); });
236 test_sort<float32_t>(compare: [](float32_t x, float32_t y) { return x < y; },
237 convert: [](size_t, size_t val) { return float32_t(val); });
238 test_sort<int32_t>(
239 compare: [](int32_t x, int32_t y) { return x > y; }, // Reversed so accidental use of < will be detected.
240 convert: [](size_t, size_t val) { return int32_t(val); });
241 }
242
243 test_algo_basic_single<int32_t>(f: run_for_rnd<test_non_const<int32_t>>());
244
245 std::cout << done() << std::endl;
246 return 0;
247}
248

source code of pstl/test/std/algorithms/alg.sorting/sort.pass.cpp