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