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 struct NonTrivial { 70 int i_; 71 72 TEST_CONSTEXPR_CXX20 NonTrivial(int i) : i_(i) {} 73 TEST_CONSTEXPR_CXX20 NonTrivial(NonTrivial&& other) : i_(other.i_) { other.i_ = 0; } 74 75 TEST_CONSTEXPR_CXX20 friend bool operator==(const NonTrivial& lhs, const NonTrivial& rhs) { return lhs.i_ == rhs.i_; } 76 }; 77 78 struct ModTwoComp { 79 TEST_CONSTEXPR_CXX20 bool operator()(int lhs, int rhs) { return lhs % 2 == rhs % 2; } 80 }; 81 82 template <class Iter> 83 TEST_CONSTEXPR_CXX20 bool test() { 84 { // empty ranges 85 std::array<int, 0> lhs = {}; 86 std::array<int, 0> rhs = {}; 87 check<Iter>(lhs, rhs, 0); 88 } 89 90 { // same range without mismatch 91 std::array<int, 8> lhs = {0, 1, 2, 3, 0, 1, 2, 3}; 92 std::array<int, 8> rhs = {0, 1, 2, 3, 0, 1, 2, 3}; 93 check<Iter>(lhs, rhs, 8); 94 } 95 96 { // same range with mismatch 97 std::array<int, 8> lhs = {0, 1, 2, 2, 0, 1, 2, 3}; 98 std::array<int, 8> rhs = {0, 1, 2, 3, 0, 1, 2, 3}; 99 check<Iter>(lhs, rhs, 3); 100 } 101 102 { // second range is smaller 103 std::array<int, 8> lhs = {0, 1, 2, 2, 0, 1, 2, 3}; 104 std::array<int, 2> rhs = {0, 1}; 105 check<Iter>(lhs, rhs, 2); 106 } 107 108 { // first range is smaller 109 std::array<int, 2> lhs = {0, 1}; 110 std::array<int, 8> rhs = {0, 1, 2, 2, 0, 1, 2, 3}; 111 check<Iter>(lhs, rhs, 2); 112 } 113 114 { // use a custom comparator 115 std::array<int, 4> lhs = {0, 2, 3, 4}; 116 std::array<int, 4> rhs = {0, 0, 4, 4}; 117 assert(std::mismatch(lhs.data(), lhs.data() + lhs.size(), rhs.data(), ModTwoComp()) == 118 std::make_pair(lhs.data() + 2, rhs.data() + 2)); 119 #if TEST_STD_VER >= 14 120 assert(std::mismatch(lhs.data(), lhs.data() + lhs.size(), rhs.data(), rhs.data() + rhs.size(), ModTwoComp()) == 121 std::make_pair(lhs.data() + 2, rhs.data() + 2)); 122 #endif 123 } 124 125 return true; 126 } 127 128 struct Test { 129 template <class Iter> 130 TEST_CONSTEXPR_CXX20 void operator()() { 131 test<Iter>(); 132 } 133 }; 134 135 TEST_CONSTEXPR_CXX20 bool test() { 136 types::for_each(types::cpp17_input_iterator_list<int*>(), Test()); 137 138 { // use a non-integer type to also test the general case - all elements match 139 std::array<NonTrivial, 8> lhs = {1, 2, 3, 4, 5, 6, 7, 8}; 140 std::array<NonTrivial, 8> rhs = {1, 2, 3, 4, 5, 6, 7, 8}; 141 check<NonTrivial*>(std::move(lhs), std::move(rhs), 8); 142 } 143 144 { // use a non-integer type to also test the general case - not all elements match 145 std::array<NonTrivial, 8> lhs = {1, 2, 3, 4, 7, 6, 7, 8}; 146 std::array<NonTrivial, 8> rhs = {1, 2, 3, 4, 5, 6, 7, 8}; 147 check<NonTrivial*>(std::move(lhs), std::move(rhs), 4); 148 } 149 150 return true; 151 } 152 153 int main(int, char**) { 154 test(); 155 #if TEST_STD_VER >= 20 156 static_assert(test()); 157 #endif 158 159 { // check with a lot of elements to test the vectorization optimization 160 { 161 std::vector<char> lhs(256); 162 std::vector<char> rhs(256); 163 for (size_t i = 0; i != lhs.size(); ++i) { 164 lhs[i] = 1; 165 check<char*>(lhs, rhs, i); 166 lhs[i] = 0; 167 rhs[i] = 1; 168 check<char*>(lhs, rhs, i); 169 rhs[i] = 0; 170 } 171 } 172 173 { 174 std::vector<int> lhs(256); 175 std::vector<int> rhs(256); 176 for (size_t i = 0; i != lhs.size(); ++i) { 177 lhs[i] = 1; 178 check<int*>(lhs, rhs, i); 179 lhs[i] = 0; 180 rhs[i] = 1; 181 check<int*>(lhs, rhs, i); 182 rhs[i] = 0; 183 } 184 } 185 } 186 187 { // check the tail of the vectorized loop 188 for (size_t vec_size = 1; vec_size != 256; ++vec_size) { 189 { 190 std::vector<char> lhs(256); 191 std::vector<char> rhs(256); 192 193 check<char*>(lhs, rhs, lhs.size()); 194 lhs.back() = 1; 195 check<char*>(lhs, rhs, lhs.size() - 1); 196 lhs.back() = 0; 197 rhs.back() = 1; 198 check<char*>(lhs, rhs, lhs.size() - 1); 199 rhs.back() = 0; 200 } 201 { 202 std::vector<int> lhs(256); 203 std::vector<int> rhs(256); 204 205 check<int*>(lhs, rhs, lhs.size()); 206 lhs.back() = 1; 207 check<int*>(lhs, rhs, lhs.size() - 1); 208 lhs.back() = 0; 209 rhs.back() = 1; 210 check<int*>(lhs, rhs, lhs.size() - 1); 211 rhs.back() = 0; 212 } 213 } 214 } 215 return 0; 216 } 217