247 lines · cpp
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-exception6//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++1714// mismatch(Iter1 first1, Iter1 last1, Iter2 first2);15//16// template<InputIterator Iter1, InputIterator Iter2Pred>17// constexpr pair<Iter1, Iter2> // constexpr after c++1718// mismatch(Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2); // C++1419//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++1724// 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++1728// mismatch(Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2, Pred pred); // C++1429 30// ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-steps): -fconstexpr-steps=5000000031// ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-ops-limit): -fconstexpr-ops-limit=10000000032 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 >= 1459 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#endif70}71 72// Compares modulo 4 to make sure we only forward to the vectorized version if we are trivially equality comparable73struct 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 >= 2085struct 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 >= 2093 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 ranges101 std::array<int, 0> lhs = {};102 std::array<int, 0> rhs = {};103 check<Iter>(lhs, rhs, 0);104 }105 106 { // same range without mismatch107 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 mismatch113 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 smaller119 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 smaller125 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 comparator131 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 >= 14136 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#endif139 }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 match155 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 match161 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 >= 20167 { // trivially equality comparable class type to test forwarding to the vectorized version - all elements match168 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 match174 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 >= 20179 180 return true;181}182 183int main(int, char**) {184 test();185#if TEST_STD_VER >= 20186 static_assert(test());187#endif188 189 { // check with a lot of elements to test the vectorization optimization190 {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 loop218 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