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