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/min.h> 15 #include <__algorithm/simd_utils.h> 16 #include <__algorithm/unwrap_iter.h> 17 #include <__config> 18 #include <__functional/identity.h> 19 #include <__iterator/aliasing_iterator.h> 20 #include <__type_traits/desugars_to.h> 21 #include <__type_traits/invoke.h> 22 #include <__type_traits/is_constant_evaluated.h> 23 #include <__type_traits/is_equality_comparable.h> 24 #include <__type_traits/is_integral.h> 25 #include <__utility/move.h> 26 #include <__utility/pair.h> 27 #include <__utility/unreachable.h> 28 #include <cstddef> 29 30 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 31 # pragma GCC system_header 32 #endif 33 34 _LIBCPP_PUSH_MACROS 35 #include <__undef_macros> 36 37 _LIBCPP_BEGIN_NAMESPACE_STD 38 39 template <class _Iter1, class _Sent1, class _Iter2, class _Pred, class _Proj1, class _Proj2> 40 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 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 51 template <class _Iter1, class _Sent1, class _Iter2, class _Pred, class _Proj1, class _Proj2> 52 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 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_ALGORITHMS 58 59 template <class _Iter> 60 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 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 vectors 91 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 at 105 // (last - vector_size) to check the remaining elements 106 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 individually 113 } 114 115 __equal_to __pred; 116 __identity __proj; 117 return std::__mismatch_loop(__first1, __last1, __first2, __pred, __proj, __proj); 118 } 119 120 template <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 _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_Tp*, _Tp*> 128 __mismatch(_Tp* __first1, _Tp* __last1, _Tp* __first2, _Pred&, _Proj1&, _Proj2&) { 129 return std::__mismatch_vectorized(__first1, __last1, __first2); 130 } 131 132 template <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 _LIBCPP_CONSTEXPR_SINCE_CXX20 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_ALGORITHMS 151 152 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate> 153 _LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_InputIterator1, _InputIterator2> 154 mismatch(_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 161 template <class _InputIterator1, class _InputIterator2> 162 _LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_InputIterator1, _InputIterator2> 163 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2) { 164 return std::mismatch(__first1, __last1, __first2, __equal_to()); 165 } 166 167 #if _LIBCPP_STD_VER >= 14 168 template <class _Iter1, class _Sent1, class _Iter2, class _Sent2, class _Pred, class _Proj1, class _Proj2> 169 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_Iter1, _Iter2> __mismatch( 170 _Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) { 171 while (__first1 != __last1 && __first2 != __last2) { 172 if (!std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2))) 173 break; 174 ++__first1; 175 ++__first2; 176 } 177 return {std::move(__first1), std::move(__first2)}; 178 } 179 180 template <class _Tp, class _Pred, class _Proj1, class _Proj2> 181 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_Tp*, _Tp*> 182 __mismatch(_Tp* __first1, _Tp* __last1, _Tp* __first2, _Tp* __last2, _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) { 183 auto __len = std::min(__last1 - __first1, __last2 - __first2); 184 return std::__mismatch(__first1, __first1 + __len, __first2, __pred, __proj1, __proj2); 185 } 186 187 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate> 188 _LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_InputIterator1, _InputIterator2> 189 mismatch(_InputIterator1 __first1, 190 _InputIterator1 __last1, 191 _InputIterator2 __first2, 192 _InputIterator2 __last2, 193 _BinaryPredicate __pred) { 194 __identity __proj; 195 auto __res = std::__mismatch( 196 std::__unwrap_iter(__first1), 197 std::__unwrap_iter(__last1), 198 std::__unwrap_iter(__first2), 199 std::__unwrap_iter(__last2), 200 __pred, 201 __proj, 202 __proj); 203 return {std::__rewrap_iter(__first1, __res.first), std::__rewrap_iter(__first2, __res.second)}; 204 } 205 206 template <class _InputIterator1, class _InputIterator2> 207 _LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_InputIterator1, _InputIterator2> 208 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) { 209 return std::mismatch(__first1, __last1, __first2, __last2, __equal_to()); 210 } 211 #endif 212 213 _LIBCPP_END_NAMESPACE_STD 214 215 _LIBCPP_POP_MACROS 216 217 #endif // _LIBCPP___ALGORITHM_MISMATCH_H 218