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
45template <class Iter, class Container1, class Container2>
46TEST_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
73struct 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
85struct 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
94struct ModTwoComp {
95 TEST_CONSTEXPR_CXX20 bool operator()(int lhs, int rhs) { return lhs % 2 == rhs % 2; }
96};
97
98template <class Iter>
99TEST_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
144struct Test {
145 template <class Iter>
146 TEST_CONSTEXPR_CXX20 void operator()() {
147 test<Iter>();
148 }
149};
150
151TEST_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
183int 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

source code of libcxx/test/std/algorithms/alg.nonmodifying/mismatch/mismatch.pass.cpp