172 lines · c
1// -*- C++ -*-2//===----------------------------------------------------------------------===//3//4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.5// See https://llvm.org/LICENSE.txt for license information.6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___CXX03___ALGORITHM_MISMATCH_H11#define _LIBCPP___CXX03___ALGORITHM_MISMATCH_H12 13#include <__cxx03/__algorithm/comp.h>14#include <__cxx03/__algorithm/min.h>15#include <__cxx03/__algorithm/simd_utils.h>16#include <__cxx03/__algorithm/unwrap_iter.h>17#include <__cxx03/__config>18#include <__cxx03/__functional/identity.h>19#include <__cxx03/__iterator/aliasing_iterator.h>20#include <__cxx03/__type_traits/desugars_to.h>21#include <__cxx03/__type_traits/invoke.h>22#include <__cxx03/__type_traits/is_constant_evaluated.h>23#include <__cxx03/__type_traits/is_equality_comparable.h>24#include <__cxx03/__type_traits/is_integral.h>25#include <__cxx03/__utility/move.h>26#include <__cxx03/__utility/pair.h>27#include <__cxx03/__utility/unreachable.h>28#include <__cxx03/cstddef>29 30#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)31# pragma GCC system_header32#endif33 34_LIBCPP_PUSH_MACROS35#include <__cxx03/__undef_macros>36 37_LIBCPP_BEGIN_NAMESPACE_STD38 39template <class _Iter1, class _Sent1, class _Iter2, class _Pred, class _Proj1, class _Proj2>40_LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI pair<_Iter1, _Iter2>41__mismatch_loop(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) {42 while (__first1 != __last1) {43 if (!std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2)))44 break;45 ++__first1;46 ++__first2;47 }48 return std::make_pair(std::move(__first1), std::move(__first2));49}50 51template <class _Iter1, class _Sent1, class _Iter2, class _Pred, class _Proj1, class _Proj2>52_LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI pair<_Iter1, _Iter2>53__mismatch(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) {54 return std::__mismatch_loop(__first1, __last1, __first2, __pred, __proj1, __proj2);55}56 57#if _LIBCPP_VECTORIZE_ALGORITHMS58 59template <class _Iter>60_LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI pair<_Iter, _Iter>61__mismatch_vectorized(_Iter __first1, _Iter __last1, _Iter __first2) {62 using __value_type = __iter_value_type<_Iter>;63 constexpr size_t __unroll_count = 4;64 constexpr size_t __vec_size = __native_vector_size<__value_type>;65 using __vec = __simd_vector<__value_type, __vec_size>;66 67 if (!__libcpp_is_constant_evaluated()) {68 auto __orig_first1 = __first1;69 auto __last2 = __first2 + (__last1 - __first1);70 while (static_cast<size_t>(__last1 - __first1) >= __unroll_count * __vec_size) [[__unlikely__]] {71 __vec __lhs[__unroll_count];72 __vec __rhs[__unroll_count];73 74 for (size_t __i = 0; __i != __unroll_count; ++__i) {75 __lhs[__i] = std::__load_vector<__vec>(__first1 + __i * __vec_size);76 __rhs[__i] = std::__load_vector<__vec>(__first2 + __i * __vec_size);77 }78 79 for (size_t __i = 0; __i != __unroll_count; ++__i) {80 if (auto __cmp_res = __lhs[__i] == __rhs[__i]; !std::__all_of(__cmp_res)) {81 auto __offset = __i * __vec_size + std::__find_first_not_set(__cmp_res);82 return {__first1 + __offset, __first2 + __offset};83 }84 }85 86 __first1 += __unroll_count * __vec_size;87 __first2 += __unroll_count * __vec_size;88 }89 90 // check the remaining 0-3 vectors91 while (static_cast<size_t>(__last1 - __first1) >= __vec_size) {92 if (auto __cmp_res = std::__load_vector<__vec>(__first1) == std::__load_vector<__vec>(__first2);93 !std::__all_of(__cmp_res)) {94 auto __offset = std::__find_first_not_set(__cmp_res);95 return {__first1 + __offset, __first2 + __offset};96 }97 __first1 += __vec_size;98 __first2 += __vec_size;99 }100 101 if (__last1 - __first1 == 0)102 return {__first1, __first2};103 104 // Check if we can load elements in front of the current pointer. If that's the case load a vector at105 // (last - vector_size) to check the remaining elements106 if (static_cast<size_t>(__first1 - __orig_first1) >= __vec_size) {107 __first1 = __last1 - __vec_size;108 __first2 = __last2 - __vec_size;109 auto __offset =110 std::__find_first_not_set(std::__load_vector<__vec>(__first1) == std::__load_vector<__vec>(__first2));111 return {__first1 + __offset, __first2 + __offset};112 } // else loop over the elements individually113 }114 115 __equal_to __pred;116 __identity __proj;117 return std::__mismatch_loop(__first1, __last1, __first2, __pred, __proj, __proj);118}119 120template <class _Tp,121 class _Pred,122 class _Proj1,123 class _Proj2,124 __enable_if_t<is_integral<_Tp>::value && __desugars_to_v<__equal_tag, _Pred, _Tp, _Tp> &&125 __is_identity<_Proj1>::value && __is_identity<_Proj2>::value,126 int> = 0>127_LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI pair<_Tp*, _Tp*>128__mismatch(_Tp* __first1, _Tp* __last1, _Tp* __first2, _Pred&, _Proj1&, _Proj2&) {129 return std::__mismatch_vectorized(__first1, __last1, __first2);130}131 132template <class _Tp,133 class _Pred,134 class _Proj1,135 class _Proj2,136 __enable_if_t<!is_integral<_Tp>::value && __desugars_to_v<__equal_tag, _Pred, _Tp, _Tp> &&137 __is_identity<_Proj1>::value && __is_identity<_Proj2>::value &&138 __can_map_to_integer_v<_Tp> && __libcpp_is_trivially_equality_comparable<_Tp, _Tp>::value,139 int> = 0>140_LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI pair<_Tp*, _Tp*>141__mismatch(_Tp* __first1, _Tp* __last1, _Tp* __first2, _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) {142 if (__libcpp_is_constant_evaluated()) {143 return std::__mismatch_loop(__first1, __last1, __first2, __pred, __proj1, __proj2);144 } else {145 using _Iter = __aliasing_iterator<_Tp*, __get_as_integer_type_t<_Tp>>;146 auto __ret = std::__mismatch_vectorized(_Iter(__first1), _Iter(__last1), _Iter(__first2));147 return {__ret.first.__base(), __ret.second.__base()};148 }149}150#endif // _LIBCPP_VECTORIZE_ALGORITHMS151 152template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>153_LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI pair<_InputIterator1, _InputIterator2>154mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred) {155 __identity __proj;156 auto __res = std::__mismatch(157 std::__unwrap_iter(__first1), std::__unwrap_iter(__last1), std::__unwrap_iter(__first2), __pred, __proj, __proj);158 return std::make_pair(std::__rewrap_iter(__first1, __res.first), std::__rewrap_iter(__first2, __res.second));159}160 161template <class _InputIterator1, class _InputIterator2>162_LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI pair<_InputIterator1, _InputIterator2>163mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2) {164 return std::mismatch(__first1, __last1, __first2, __equal_to());165}166 167_LIBCPP_END_NAMESPACE_STD168 169_LIBCPP_POP_MACROS170 171#endif // _LIBCPP___CXX03___ALGORITHM_MISMATCH_H172