1 //===----------------------------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 // This test appears to hang with picolibc & qemu.
10 // UNSUPPORTED: LIBCXX-PICOLIBC-FIXME
11
12 // <algorithm>
13
14 // template<RandomAccessIterator Iter>
15 // requires ShuffleIterator<Iter>
16 // && LessThanComparable<Iter::value_type>
17 // void
18 // sort(Iter first, Iter last);
19
20 #include <algorithm>
21 #include <iterator>
22 #include <numeric>
23 #include <random>
24 #include <cassert>
25 #include <vector>
26 #include <deque>
27 #include <utility>
28
29 #include "test_macros.h"
30
31 std::mt19937 randomness;
32
33 template <class Container, class RI>
34 void
test_sort_helper(RI f,RI l)35 test_sort_helper(RI f, RI l)
36 {
37 if (f != l)
38 {
39 Container save(l - f);
40 do
41 {
42 std::copy(f, l, save.begin());
43 std::sort(save.begin(), save.end());
44 assert(std::is_sorted(save.begin(), save.end()));
45 assert(std::is_permutation(save.begin(), save.end(), f));
46 } while (std::next_permutation(f, l));
47 }
48 }
49
50 template <class T>
set_value(T & dest,int value)51 void set_value(T& dest, int value)
52 {
53 dest = value;
54 }
55
set_value(std::pair<int,int> & dest,int value)56 inline void set_value(std::pair<int, int>& dest, int value)
57 {
58 dest.first = value;
59 dest.second = value;
60 }
61
62 template <class Container, class RI>
63 void
test_sort_driver_driver(RI f,RI l,int start,RI real_last)64 test_sort_driver_driver(RI f, RI l, int start, RI real_last)
65 {
66 for (RI i = l; i > f + start;)
67 {
68 set_value(*--i, start);
69 if (f == i)
70 {
71 test_sort_helper<Container>(f, real_last);
72 }
73 if (start > 0)
74 test_sort_driver_driver<Container>(f, i, start-1, real_last);
75 }
76 }
77
78 template <class Container, class RI>
79 void
test_sort_driver(RI f,RI l,int start)80 test_sort_driver(RI f, RI l, int start)
81 {
82 test_sort_driver_driver<Container>(f, l, start, l);
83 }
84
85 template <class Container, int sa>
86 void
test_sort_()87 test_sort_()
88 {
89 Container ia(sa);
90 for (int i = 0; i < sa; ++i)
91 {
92 test_sort_driver<Container>(ia.begin(), ia.end(), i);
93 }
94 }
95
96 template <class T>
increment_or_reset(T value,int max_value)97 T increment_or_reset(T value, int max_value)
98 {
99 return value == max_value - 1 ? 0 : value + 1;
100 }
101
increment_or_reset(std::pair<int,int> value,int max_value)102 inline std::pair<int, int> increment_or_reset(std::pair<int, int> value,
103 int max_value)
104 {
105 int new_value = value.first + 1;
106 if (new_value == max_value)
107 {
108 new_value = 0;
109 }
110 return std::make_pair(new_value, new_value);
111 }
112
113 template <class Container>
114 void
test_larger_sorts(int N,int M)115 test_larger_sorts(int N, int M)
116 {
117 using Iter = typename Container::iterator;
118 using ValueType = typename Container::value_type;
119 assert(N != 0);
120 assert(M != 0);
121 // create container of length N filled with M different objects
122 Container array(N);
123 ValueType x = ValueType();
124 for (int i = 0; i < N; ++i)
125 {
126 array[i] = x;
127 x = increment_or_reset(x, M);
128 }
129 Container original = array;
130 Iter iter = array.begin();
131 Iter original_iter = original.begin();
132
133 // test saw tooth pattern
134 std::sort(iter, iter+N);
135 assert(std::is_sorted(iter, iter+N));
136 assert(std::is_permutation(iter, iter+N, original_iter));
137 // test random pattern
138 std::shuffle(iter, iter+N, randomness);
139 std::sort(iter, iter+N);
140 assert(std::is_sorted(iter, iter+N));
141 assert(std::is_permutation(iter, iter+N, original_iter));
142 // test sorted pattern
143 std::sort(iter, iter+N);
144 assert(std::is_sorted(iter, iter+N));
145 assert(std::is_permutation(iter, iter+N, original_iter));
146 // test reverse sorted pattern
147 std::reverse(iter, iter+N);
148 std::sort(iter, iter+N);
149 assert(std::is_sorted(iter, iter+N));
150 assert(std::is_permutation(iter, iter+N, original_iter));
151 // test swap ranges 2 pattern
152 std::swap_ranges(iter, iter+N/2, iter+N/2);
153 std::sort(iter, iter+N);
154 assert(std::is_sorted(iter, iter+N));
155 assert(std::is_permutation(iter, iter+N, original_iter));
156 // test reverse swap ranges 2 pattern
157 std::reverse(iter, iter+N);
158 std::swap_ranges(iter, iter+N/2, iter+N/2);
159 std::sort(iter, iter+N);
160 assert(std::is_sorted(iter, iter+N));
161 assert(std::is_permutation(iter, iter+N, original_iter));
162 }
163
164 template <class Container>
165 void
test_larger_sorts(int N)166 test_larger_sorts(int N)
167 {
168 test_larger_sorts<Container>(N, 1);
169 test_larger_sorts<Container>(N, 2);
170 test_larger_sorts<Container>(N, 3);
171 test_larger_sorts<Container>(N, N/2-1);
172 test_larger_sorts<Container>(N, N/2);
173 test_larger_sorts<Container>(N, N/2+1);
174 test_larger_sorts<Container>(N, N-2);
175 test_larger_sorts<Container>(N, N-1);
176 test_larger_sorts<Container>(N, N);
177 }
178
179 void
test_pointer_sort()180 test_pointer_sort()
181 {
182 static const int array_size = 10;
183 const int v[array_size] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
184 const int *pv[array_size];
185 for (int i = 0; i < array_size; i++) {
186 pv[i] = &v[array_size - 1 - i];
187 }
188 std::sort(pv, pv + array_size);
189 assert(*pv[0] == v[0]);
190 assert(*pv[1] == v[1]);
191 assert(*pv[array_size - 1] == v[array_size - 1]);
192 }
193
194 // test_adversarial_quicksort generates a vector with values arranged in such a
195 // way that they would invoke O(N^2) behavior on any quick sort implementation
196 // that satisfies certain conditions. Details are available in the following
197 // paper:
198 // "A Killer Adversary for Quicksort", M. D. McIlroy, Software-Practice &
199 // Experience Volume 29 Issue 4 April 10, 1999 pp 341-344.
200 // https://dl.acm.org/doi/10.5555/311868.311871.
201 struct AdversaryComparator {
AdversaryComparatorAdversaryComparator202 AdversaryComparator(int N, std::vector<int>& input) : gas(N - 1), V(input) {
203 V.resize(N);
204 // Populate all positions in the generated input to gas to indicate that
205 // none of the values have been fixed yet.
206 for (int i = 0; i < N; ++i)
207 V[i] = gas;
208 }
209
operator ()AdversaryComparator210 bool operator()(int x, int y) {
211 if (V[x] == gas && V[y] == gas) {
212 // We are comparing two inputs whose value is still to be decided.
213 if (x == candidate) {
214 V[x] = nsolid++;
215 } else {
216 V[y] = nsolid++;
217 }
218 }
219 if (V[x] == gas) {
220 candidate = x;
221 } else if (V[y] == gas) {
222 candidate = y;
223 }
224 return V[x] < V[y];
225 }
226
227 private:
228 // If an element is equal to gas, it indicates that the value of the element
229 // is still to be decided and may change over the course of time.
230 const int gas;
231 // This is a reference so that we can manipulate the input vector later.
232 std::vector<int>& V;
233 // Candidate for the pivot position.
234 int candidate = 0;
235 int nsolid = 0;
236 };
237
test_adversarial_quicksort(int N)238 void test_adversarial_quicksort(int N) {
239 assert(N > 0);
240 std::vector<int> ascVals(N);
241 // Fill up with ascending values from 0 to N-1. These will act as indices
242 // into V.
243 std::iota(ascVals.begin(), ascVals.end(), 0);
244 std::vector<int> V;
245 AdversaryComparator comp(N, V);
246 std::sort(ascVals.begin(), ascVals.end(), comp);
247 std::sort(V.begin(), V.end());
248 assert(std::is_sorted(V.begin(), V.end()));
249 }
250
251 template <class Container>
run_sort_tests()252 void run_sort_tests()
253 {
254 // test null range
255 using ValueType = typename Container::value_type;
256 ValueType d = ValueType();
257 std::sort(&d, &d);
258
259 // exhaustively test all possibilities up to length 8
260 test_sort_<Container, 1>();
261 test_sort_<Container, 2>();
262 test_sort_<Container, 3>();
263 test_sort_<Container, 4>();
264 test_sort_<Container, 5>();
265 test_sort_<Container, 6>();
266 test_sort_<Container, 7>();
267 test_sort_<Container, 8>();
268
269 test_larger_sorts<Container>(256);
270 test_larger_sorts<Container>(257);
271 test_larger_sorts<Container>(499);
272 test_larger_sorts<Container>(500);
273 test_larger_sorts<Container>(997);
274 test_larger_sorts<Container>(1000);
275 test_larger_sorts<Container>(1009);
276 }
277
main(int,char **)278 int main(int, char**)
279 {
280 // test various combinations of contiguous/non-contiguous containers with
281 // arithmetic/non-arithmetic types
282 run_sort_tests<std::vector<int> >();
283 run_sort_tests<std::deque<int> >();
284 run_sort_tests<std::vector<std::pair<int, int> > >();
285
286 test_pointer_sort();
287 test_adversarial_quicksort(1 << 20);
288
289 return 0;
290 }
291