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-exception 7 // 8 //===----------------------------------------------------------------------===// 9 10 #ifndef _LIBCPP___ALGORITHM_MISMATCH_H 11 #define _LIBCPP___ALGORITHM_MISMATCH_H 12 13 #include <__algorithm/comp.h> 14 #include <__algorithm/simd_utils.h> 15 #include <__algorithm/unwrap_iter.h> 16 #include <__config> 17 #include <__functional/identity.h> 18 #include <__type_traits/invoke.h> 19 #include <__type_traits/is_constant_evaluated.h> 20 #include <__type_traits/is_equality_comparable.h> 21 #include <__type_traits/operation_traits.h> 22 #include <__utility/move.h> 23 #include <__utility/pair.h> 24 #include <__utility/unreachable.h> 25 26 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 27 # pragma GCC system_header 28 #endif 29 30 _LIBCPP_PUSH_MACROS 31 #include <__undef_macros> 32 33 _LIBCPP_BEGIN_NAMESPACE_STD 34 35 template <class _Iter1, class _Sent1, class _Iter2, class _Pred, class _Proj1, class _Proj2> 36 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_Iter1, _Iter2> 37 __mismatch_loop(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) { 38 while (__first1 != __last1) { 39 if (!std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2))) 40 break; 41 ++__first1; 42 ++__first2; 43 } 44 return std::make_pair(std::move(__first1), std::move(__first2)); 45 } 46 47 template <class _Iter1, class _Sent1, class _Iter2, class _Pred, class _Proj1, class _Proj2> 48 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_Iter1, _Iter2> 49 __mismatch(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) { 50 return std::__mismatch_loop(__first1, __last1, __first2, __pred, __proj1, __proj2); 51 } 52 53 #if _LIBCPP_VECTORIZE_ALGORITHMS 54 55 template <class _Tp, 56 class _Pred, 57 class _Proj1, 58 class _Proj2, 59 __enable_if_t<is_integral<_Tp>::value && __desugars_to<__equal_tag, _Pred, _Tp, _Tp>::value && 60 __is_identity<_Proj1>::value && __is_identity<_Proj2>::value, 61 int> = 0> 62 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_Tp*, _Tp*> 63 __mismatch(_Tp* __first1, _Tp* __last1, _Tp* __first2, _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) { 64 constexpr size_t __unroll_count = 4; 65 constexpr size_t __vec_size = __native_vector_size<_Tp>; 66 using __vec = __simd_vector<_Tp, __vec_size>; 67 if (!__libcpp_is_constant_evaluated()) { 68 while (static_cast<size_t>(__last1 - __first1) >= __unroll_count * __vec_size) [[__unlikely__]] { 69 __vec __lhs[__unroll_count]; 70 __vec __rhs[__unroll_count]; 71 72 for (size_t __i = 0; __i != __unroll_count; ++__i) { 73 __lhs[__i] = std::__load_vector<__vec>(__first1 + __i * __vec_size); 74 __rhs[__i] = std::__load_vector<__vec>(__first2 + __i * __vec_size); 75 } 76 77 for (size_t __i = 0; __i != __unroll_count; ++__i) { 78 if (auto __cmp_res = __lhs[__i] == __rhs[__i]; !std::__all_of(__cmp_res)) { 79 auto __offset = __i * __vec_size + std::__find_first_not_set(__cmp_res); 80 return {__first1 + __offset, __first2 + __offset}; 81 } 82 } 83 84 __first1 += __unroll_count * __vec_size; 85 __first2 += __unroll_count * __vec_size; 86 } 87 } 88 // TODO: Consider vectorizing the tail 89 return std::__mismatch_loop(__first1, __last1, __first2, __pred, __proj1, __proj2); 90 } 91 92 #endif // _LIBCPP_VECTORIZE_ALGORITHMS 93 94 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate> 95 _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_InputIterator1, _InputIterator2> 96 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred) { 97 __identity __proj; 98 auto __res = std::__mismatch( 99 std::__unwrap_iter(__first1), std::__unwrap_iter(__last1), std::__unwrap_iter(__first2), __pred, __proj, __proj); 100 return std::make_pair(std::__rewrap_iter(__first1, __res.first), std::__rewrap_iter(__first2, __res.second)); 101 } 102 103 template <class _InputIterator1, class _InputIterator2> 104 _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_InputIterator1, _InputIterator2> 105 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2) { 106 return std::mismatch(__first1, __last1, __first2, __equal_to()); 107 } 108 109 #if _LIBCPP_STD_VER >= 14 110 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate> 111 _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_InputIterator1, _InputIterator2> 112 mismatch(_InputIterator1 __first1, 113 _InputIterator1 __last1, 114 _InputIterator2 __first2, 115 _InputIterator2 __last2, 116 _BinaryPredicate __pred) { 117 for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void)++__first2) 118 if (!__pred(*__first1, *__first2)) 119 break; 120 return pair<_InputIterator1, _InputIterator2>(__first1, __first2); 121 } 122 123 template <class _InputIterator1, class _InputIterator2> 124 _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_InputIterator1, _InputIterator2> 125 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) { 126 return std::mismatch(__first1, __last1, __first2, __last2, __equal_to()); 127 } 128 #endif 129 130 _LIBCPP_END_NAMESPACE_STD 131 132 _LIBCPP_POP_MACROS 133 134 #endif // _LIBCPP___ALGORITHM_MISMATCH_H 135