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 | // template<InputIterator Iter1, InputIterator Iter2> |
12 | // requires HasEqualTo<Iter1::value_type, Iter2::value_type> |
13 | // constexpr pair<Iter1, Iter2> // constexpr after c++17 |
14 | // mismatch(Iter1 first1, Iter1 last1, Iter2 first2); |
15 | // |
16 | // template<InputIterator Iter1, InputIterator Iter2Pred> |
17 | // constexpr pair<Iter1, Iter2> // constexpr after c++17 |
18 | // mismatch(Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2); // C++14 |
19 | // |
20 | // template<InputIterator Iter1, InputIterator Iter2, |
21 | // Predicate<auto, Iter1::value_type, Iter2::value_type> Pred> |
22 | // requires CopyConstructible<Pred> |
23 | // constexpr pair<Iter1, Iter2> // constexpr after c++17 |
24 | // mismatch(Iter1 first1, Iter1 last1, Iter2 first2, Pred pred); |
25 | // |
26 | // template<InputIterator Iter1, InputIterator Iter2, Predicate Pred> |
27 | // constexpr pair<Iter1, Iter2> // constexpr after c++17 |
28 | // mismatch(Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2, Pred pred); // C++14 |
29 | |
30 | // ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-steps): -fconstexpr-steps=50000000 |
31 | // ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-ops-limit): -fconstexpr-ops-limit=100000000 |
32 | |
33 | #include <algorithm> |
34 | #include <array> |
35 | #include <cassert> |
36 | #include <cstddef> |
37 | #include <functional> |
38 | #include <utility> |
39 | #include <vector> |
40 | |
41 | #include "test_macros.h" |
42 | #include "test_iterators.h" |
43 | #include "type_algorithms.h" |
44 | |
45 | template <class Iter, class Container1, class Container2> |
46 | TEST_CONSTEXPR_CXX20 void check(Container1 lhs, Container2 rhs, size_t offset) { |
47 | if (lhs.size() == rhs.size()) { |
48 | assert(std::mismatch(Iter(lhs.data()), Iter(lhs.data() + lhs.size()), Iter(rhs.data())) == |
49 | std::make_pair(Iter(lhs.data() + offset), Iter(rhs.data() + offset))); |
50 | |
51 | assert(std::mismatch(Iter(lhs.data()), |
52 | Iter(lhs.data() + lhs.size()), |
53 | Iter(rhs.data()), |
54 | std::equal_to<typename Container1::value_type>()) == |
55 | std::make_pair(Iter(lhs.data() + offset), Iter(rhs.data() + offset))); |
56 | } |
57 | |
58 | #if TEST_STD_VER >= 14 |
59 | assert( |
60 | std::mismatch(Iter(lhs.data()), Iter(lhs.data() + lhs.size()), Iter(rhs.data()), Iter(rhs.data() + rhs.size())) == |
61 | std::make_pair(Iter(lhs.data() + offset), Iter(rhs.data() + offset))); |
62 | |
63 | assert(std::mismatch(Iter(lhs.data()), |
64 | Iter(lhs.data() + lhs.size()), |
65 | Iter(rhs.data()), |
66 | Iter(rhs.data() + rhs.size()), |
67 | std::equal_to<typename Container1::value_type>()) == |
68 | std::make_pair(Iter(lhs.data() + offset), Iter(rhs.data() + offset))); |
69 | #endif |
70 | } |
71 | |
72 | // Compares modulo 4 to make sure we only forward to the vectorized version if we are trivially equality comparable |
73 | struct NonTrivialMod4Comp { |
74 | int i_; |
75 | |
76 | TEST_CONSTEXPR_CXX20 NonTrivialMod4Comp(int i) : i_(i) {} |
77 | TEST_CONSTEXPR_CXX20 NonTrivialMod4Comp(NonTrivialMod4Comp&& other) : i_(other.i_) { other.i_ = 0; } |
78 | |
79 | TEST_CONSTEXPR_CXX20 friend bool operator==(const NonTrivialMod4Comp& lhs, const NonTrivialMod4Comp& rhs) { |
80 | return lhs.i_ % 4 == rhs.i_ % 4; |
81 | } |
82 | }; |
83 | |
84 | #if TEST_STD_VER >= 20 |
85 | struct TriviallyEqualityComparable { |
86 | int i_; |
87 | |
88 | TEST_CONSTEXPR_CXX20 TriviallyEqualityComparable(int i) : i_(i) {} |
89 | |
90 | TEST_CONSTEXPR_CXX20 friend bool operator==(TriviallyEqualityComparable, TriviallyEqualityComparable) = default; |
91 | }; |
92 | #endif // TEST_STD_VER >= 20 |
93 | |
94 | struct ModTwoComp { |
95 | TEST_CONSTEXPR_CXX20 bool operator()(int lhs, int rhs) { return lhs % 2 == rhs % 2; } |
96 | }; |
97 | |
98 | template <class Iter> |
99 | TEST_CONSTEXPR_CXX20 bool test() { |
100 | { // empty ranges |
101 | std::array<int, 0> lhs = {}; |
102 | std::array<int, 0> rhs = {}; |
103 | check<Iter>(lhs, rhs, 0); |
104 | } |
105 | |
106 | { // same range without mismatch |
107 | std::array<int, 8> lhs = {0, 1, 2, 3, 0, 1, 2, 3}; |
108 | std::array<int, 8> rhs = {0, 1, 2, 3, 0, 1, 2, 3}; |
109 | check<Iter>(lhs, rhs, 8); |
110 | } |
111 | |
112 | { // same range with mismatch |
113 | std::array<int, 8> lhs = {0, 1, 2, 2, 0, 1, 2, 3}; |
114 | std::array<int, 8> rhs = {0, 1, 2, 3, 0, 1, 2, 3}; |
115 | check<Iter>(lhs, rhs, 3); |
116 | } |
117 | |
118 | { // second range is smaller |
119 | std::array<int, 8> lhs = {0, 1, 2, 2, 0, 1, 2, 3}; |
120 | std::array<int, 2> rhs = {0, 1}; |
121 | check<Iter>(lhs, rhs, 2); |
122 | } |
123 | |
124 | { // first range is smaller |
125 | std::array<int, 2> lhs = {0, 1}; |
126 | std::array<int, 8> rhs = {0, 1, 2, 2, 0, 1, 2, 3}; |
127 | check<Iter>(lhs, rhs, 2); |
128 | } |
129 | |
130 | { // use a custom comparator |
131 | std::array<int, 4> lhs = {0, 2, 3, 4}; |
132 | std::array<int, 4> rhs = {0, 0, 4, 4}; |
133 | assert(std::mismatch(lhs.data(), lhs.data() + lhs.size(), rhs.data(), ModTwoComp()) == |
134 | std::make_pair(lhs.data() + 2, rhs.data() + 2)); |
135 | #if TEST_STD_VER >= 14 |
136 | assert(std::mismatch(lhs.data(), lhs.data() + lhs.size(), rhs.data(), rhs.data() + rhs.size(), ModTwoComp()) == |
137 | std::make_pair(lhs.data() + 2, rhs.data() + 2)); |
138 | #endif |
139 | } |
140 | |
141 | return true; |
142 | } |
143 | |
144 | struct Test { |
145 | template <class Iter> |
146 | TEST_CONSTEXPR_CXX20 void operator()() { |
147 | test<Iter>(); |
148 | } |
149 | }; |
150 | |
151 | TEST_CONSTEXPR_CXX20 bool test() { |
152 | types::for_each(types::cpp17_input_iterator_list<int*>(), Test()); |
153 | |
154 | { // use a non-integer type to also test the general case - all elements match |
155 | std::array<NonTrivialMod4Comp, 8> lhs = {1, 2, 3, 4, 5, 6, 7, 8}; |
156 | std::array<NonTrivialMod4Comp, 8> rhs = {1, 2, 3, 4, 1, 6, 7, 8}; |
157 | check<NonTrivialMod4Comp*>(std::move(lhs), std::move(rhs), 8); |
158 | } |
159 | |
160 | { // use a non-integer type to also test the general case - not all elements match |
161 | std::array<NonTrivialMod4Comp, 8> lhs = {1, 2, 3, 4, 7, 6, 7, 8}; |
162 | std::array<NonTrivialMod4Comp, 8> rhs = {1, 2, 3, 4, 5, 6, 7, 8}; |
163 | check<NonTrivialMod4Comp*>(std::move(lhs), std::move(rhs), 4); |
164 | } |
165 | |
166 | #if TEST_STD_VER >= 20 |
167 | { // trivially equality comparable class type to test forwarding to the vectorized version - all elements match |
168 | std::array<TriviallyEqualityComparable, 8> lhs = {1, 2, 3, 4, 5, 6, 7, 8}; |
169 | std::array<TriviallyEqualityComparable, 8> rhs = {1, 2, 3, 4, 5, 6, 7, 8}; |
170 | check<TriviallyEqualityComparable*>(std::move(lhs), std::move(rhs), 8); |
171 | } |
172 | |
173 | { // trivially equality comparable class type to test forwarding to the vectorized version - not all elements match |
174 | std::array<TriviallyEqualityComparable, 8> lhs = {1, 2, 3, 4, 7, 6, 7, 8}; |
175 | std::array<TriviallyEqualityComparable, 8> rhs = {1, 2, 3, 4, 5, 6, 7, 8}; |
176 | check<TriviallyEqualityComparable*>(std::move(lhs), std::move(rhs), 4); |
177 | } |
178 | #endif // TEST_STD_VER >= 20 |
179 | |
180 | return true; |
181 | } |
182 | |
183 | int main(int, char**) { |
184 | test(); |
185 | #if TEST_STD_VER >= 20 |
186 | static_assert(test()); |
187 | #endif |
188 | |
189 | { // check with a lot of elements to test the vectorization optimization |
190 | { |
191 | std::vector<char> lhs(256); |
192 | std::vector<char> rhs(256); |
193 | for (size_t i = 0; i != lhs.size(); ++i) { |
194 | lhs[i] = 1; |
195 | check<char*>(lhs, rhs, i); |
196 | lhs[i] = 0; |
197 | rhs[i] = 1; |
198 | check<char*>(lhs, rhs, i); |
199 | rhs[i] = 0; |
200 | } |
201 | } |
202 | |
203 | { |
204 | std::vector<int> lhs(256); |
205 | std::vector<int> rhs(256); |
206 | for (size_t i = 0; i != lhs.size(); ++i) { |
207 | lhs[i] = 1; |
208 | check<int*>(lhs, rhs, i); |
209 | lhs[i] = 0; |
210 | rhs[i] = 1; |
211 | check<int*>(lhs, rhs, i); |
212 | rhs[i] = 0; |
213 | } |
214 | } |
215 | } |
216 | |
217 | { // check the tail of the vectorized loop |
218 | for (size_t vec_size = 1; vec_size != 256; ++vec_size) { |
219 | { |
220 | std::vector<char> lhs(vec_size); |
221 | std::vector<char> rhs(vec_size); |
222 | |
223 | check<char*>(lhs, rhs, lhs.size()); |
224 | lhs.back() = 1; |
225 | check<char*>(lhs, rhs, lhs.size() - 1); |
226 | lhs.back() = 0; |
227 | rhs.back() = 1; |
228 | check<char*>(lhs, rhs, lhs.size() - 1); |
229 | rhs.back() = 0; |
230 | } |
231 | { |
232 | std::vector<int> lhs(vec_size); |
233 | std::vector<int> rhs(vec_size); |
234 | |
235 | check<int*>(lhs, rhs, lhs.size()); |
236 | lhs.back() = 1; |
237 | check<int*>(lhs, rhs, lhs.size() - 1); |
238 | lhs.back() = 0; |
239 | rhs.back() = 1; |
240 | check<int*>(lhs, rhs, lhs.size() - 1); |
241 | rhs.back() = 0; |
242 | } |
243 | } |
244 | } |
245 | return 0; |
246 | } |
247 | |