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 | // <algorithm> |
10 | |
11 | // Test std::sort stability randomization |
12 | |
13 | // UNSUPPORTED: c++03 |
14 | // ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY |
15 | |
16 | #include <algorithm> |
17 | #include <array> |
18 | #include <cassert> |
19 | #include <functional> |
20 | #include <iterator> |
21 | #include <vector> |
22 | |
23 | #include "test_macros.h" |
24 | |
25 | struct EqualType { |
26 | int value = 0; |
27 | constexpr bool operator<(const EqualType&) const { return false; } |
28 | }; |
29 | |
30 | std::vector<EqualType> deterministic() { |
31 | static constexpr int kSize = 100; |
32 | std::vector<EqualType> v; |
33 | v.resize(new_size: kSize); |
34 | for (int i = 0; i < kSize; ++i) { |
35 | v[i].value = kSize / 2 - i * (i % 2 ? -1 : 1); |
36 | } |
37 | std::less<EqualType> comp; |
38 | std::__sort_dispatch<std::_ClassicAlgPolicy>(v.begin(), v.end(), comp); |
39 | return v; |
40 | } |
41 | |
42 | void test_randomization() { |
43 | static constexpr int kSize = 100; |
44 | std::vector<EqualType> v; |
45 | v.resize(new_size: kSize); |
46 | for (int i = 0; i < kSize; ++i) { |
47 | v[i].value = kSize / 2 - i * (i % 2 ? -1 : 1); |
48 | } |
49 | auto deterministic_v = deterministic(); |
50 | std::sort(first: v.begin(), last: v.end()); |
51 | bool all_equal = true; |
52 | for (int i = 0; i < kSize; ++i) { |
53 | if (v[i].value != deterministic_v[i].value) { |
54 | all_equal = false; |
55 | } |
56 | } |
57 | assert(!all_equal); |
58 | } |
59 | |
60 | void test_same() { |
61 | static constexpr int kSize = 100; |
62 | std::vector<EqualType> v; |
63 | v.resize(new_size: kSize); |
64 | for (int i = 0; i < kSize; ++i) { |
65 | v[i].value = kSize / 2 - i * (i % 2 ? -1 : 1); |
66 | } |
67 | auto snapshot_v = v; |
68 | auto snapshot_custom_v = v; |
69 | std::sort(first: v.begin(), last: v.end()); |
70 | std::sort(first: snapshot_v.begin(), last: snapshot_v.end()); |
71 | std::sort(first: snapshot_custom_v.begin(), last: snapshot_custom_v.end(), |
72 | comp: [](const EqualType&, const EqualType&) { return false; }); |
73 | bool all_equal = true; |
74 | for (int i = 0; i < kSize; ++i) { |
75 | if (v[i].value != snapshot_v[i].value || v[i].value != snapshot_custom_v[i].value) { |
76 | all_equal = false; |
77 | } |
78 | } |
79 | assert(all_equal); |
80 | } |
81 | |
82 | #if TEST_STD_VER > 17 |
83 | constexpr bool test_constexpr() { |
84 | std::array<EqualType, 10> v; |
85 | for (int i = 9; i >= 0; --i) { |
86 | v[9 - i].value = i; |
87 | } |
88 | std::sort(v.begin(), v.end()); |
89 | return std::is_sorted(v.begin(), v.end()); |
90 | } |
91 | #endif |
92 | |
93 | int main(int, char**) { |
94 | test_randomization(); |
95 | test_same(); |
96 | #if TEST_STD_VER > 17 |
97 | static_assert(test_constexpr(), "" ); |
98 | #endif |
99 | return 0; |
100 | } |
101 | |