219 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___ALGORITHM_MISMATCH_H11#define _LIBCPP___ALGORITHM_MISMATCH_H12 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 <__cstddef/size_t.h>19#include <__functional/identity.h>20#include <__iterator/aliasing_iterator.h>21#include <__iterator/iterator_traits.h>22#include <__type_traits/desugars_to.h>23#include <__type_traits/enable_if.h>24#include <__type_traits/invoke.h>25#include <__type_traits/is_constant_evaluated.h>26#include <__type_traits/is_equality_comparable.h>27#include <__type_traits/is_integral.h>28#include <__utility/move.h>29#include <__utility/pair.h>30 31#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)32# pragma GCC system_header33#endif34 35_LIBCPP_PUSH_MACROS36#include <__undef_macros>37 38_LIBCPP_BEGIN_NAMESPACE_STD39 40template <class _Iter1, class _Sent1, class _Iter2, class _Pred, class _Proj1, class _Proj2>41[[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_Iter1, _Iter2>42__mismatch_loop(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) {43 while (__first1 != __last1) {44 if (!std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2)))45 break;46 ++__first1;47 ++__first2;48 }49 return std::make_pair(std::move(__first1), std::move(__first2));50}51 52template <class _Iter1, class _Sent1, class _Iter2, class _Pred, class _Proj1, class _Proj2>53[[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_Iter1, _Iter2>54__mismatch(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) {55 return std::__mismatch_loop(__first1, __last1, __first2, __pred, __proj1, __proj2);56}57 58#if _LIBCPP_VECTORIZE_ALGORITHMS59 60template <class _Iter>61[[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_Iter, _Iter>62__mismatch_vectorized(_Iter __first1, _Iter __last1, _Iter __first2) {63 using __value_type = __iterator_value_type<_Iter>;64 constexpr size_t __unroll_count = 4;65 constexpr size_t __vec_size = __native_vector_size<__value_type>;66 using __vec = __simd_vector<__value_type, __vec_size>;67 68 if (!__libcpp_is_constant_evaluated()) {69 auto __orig_first1 = __first1;70 auto __last2 = __first2 + (__last1 - __first1);71 while (static_cast<size_t>(__last1 - __first1) >= __unroll_count * __vec_size) [[__unlikely__]] {72 __vec __lhs[__unroll_count];73 __vec __rhs[__unroll_count];74 75 for (size_t __i = 0; __i != __unroll_count; ++__i) {76 __lhs[__i] = std::__load_vector<__vec>(__first1 + __i * __vec_size);77 __rhs[__i] = std::__load_vector<__vec>(__first2 + __i * __vec_size);78 }79 80 for (size_t __i = 0; __i != __unroll_count; ++__i) {81 if (auto __cmp_res = __lhs[__i] == __rhs[__i]; !std::__all_of(__cmp_res)) {82 auto __offset = __i * __vec_size + std::__find_first_not_set(__cmp_res);83 return {__first1 + __offset, __first2 + __offset};84 }85 }86 87 __first1 += __unroll_count * __vec_size;88 __first2 += __unroll_count * __vec_size;89 }90 91 // check the remaining 0-3 vectors92 while (static_cast<size_t>(__last1 - __first1) >= __vec_size) {93 if (auto __cmp_res = std::__load_vector<__vec>(__first1) == std::__load_vector<__vec>(__first2);94 !std::__all_of(__cmp_res)) {95 auto __offset = std::__find_first_not_set(__cmp_res);96 return {__first1 + __offset, __first2 + __offset};97 }98 __first1 += __vec_size;99 __first2 += __vec_size;100 }101 102 if (__last1 - __first1 == 0)103 return {__first1, __first2};104 105 // Check if we can load elements in front of the current pointer. If that's the case load a vector at106 // (last - vector_size) to check the remaining elements107 if (static_cast<size_t>(__first1 - __orig_first1) >= __vec_size) {108 __first1 = __last1 - __vec_size;109 __first2 = __last2 - __vec_size;110 auto __offset =111 std::__find_first_not_set(std::__load_vector<__vec>(__first1) == std::__load_vector<__vec>(__first2));112 return {__first1 + __offset, __first2 + __offset};113 } // else loop over the elements individually114 }115 116 __equal_to __pred;117 __identity __proj;118 return std::__mismatch_loop(__first1, __last1, __first2, __pred, __proj, __proj);119}120 121template <class _Tp,122 class _Pred,123 class _Proj1,124 class _Proj2,125 __enable_if_t<is_integral<_Tp>::value && __desugars_to_v<__equal_tag, _Pred, _Tp, _Tp> &&126 __is_identity<_Proj1>::value && __is_identity<_Proj2>::value,127 int> = 0>128[[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_Tp*, _Tp*>129__mismatch(_Tp* __first1, _Tp* __last1, _Tp* __first2, _Pred&, _Proj1&, _Proj2&) {130 return std::__mismatch_vectorized(__first1, __last1, __first2);131}132 133template <class _Tp,134 class _Pred,135 class _Proj1,136 class _Proj2,137 __enable_if_t<!is_integral<_Tp>::value && __desugars_to_v<__equal_tag, _Pred, _Tp, _Tp> &&138 __is_identity<_Proj1>::value && __is_identity<_Proj2>::value &&139 __can_map_to_integer_v<_Tp> && __libcpp_is_trivially_equality_comparable<_Tp, _Tp>::value,140 int> = 0>141[[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_Tp*, _Tp*>142__mismatch(_Tp* __first1, _Tp* __last1, _Tp* __first2, _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) {143 if (__libcpp_is_constant_evaluated()) {144 return std::__mismatch_loop(__first1, __last1, __first2, __pred, __proj1, __proj2);145 } else {146 using _Iter = __aliasing_iterator<_Tp*, __get_as_integer_type_t<_Tp>>;147 auto __ret = std::__mismatch_vectorized(_Iter(__first1), _Iter(__last1), _Iter(__first2));148 return {__ret.first.__base(), __ret.second.__base()};149 }150}151#endif // _LIBCPP_VECTORIZE_ALGORITHMS152 153template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>154[[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_InputIterator1, _InputIterator2>155mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred) {156 __identity __proj;157 auto __res = std::__mismatch(158 std::__unwrap_iter(__first1), std::__unwrap_iter(__last1), std::__unwrap_iter(__first2), __pred, __proj, __proj);159 return std::make_pair(std::__rewrap_iter(__first1, __res.first), std::__rewrap_iter(__first2, __res.second));160}161 162template <class _InputIterator1, class _InputIterator2>163[[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_InputIterator1, _InputIterator2>164mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2) {165 return std::mismatch(__first1, __last1, __first2, __equal_to());166}167 168#if _LIBCPP_STD_VER >= 14169template <class _Iter1, class _Sent1, class _Iter2, class _Sent2, class _Pred, class _Proj1, class _Proj2>170[[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_Iter1, _Iter2> __mismatch(171 _Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) {172 while (__first1 != __last1 && __first2 != __last2) {173 if (!std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2)))174 break;175 ++__first1;176 ++__first2;177 }178 return {std::move(__first1), std::move(__first2)};179}180 181template <class _Tp, class _Pred, class _Proj1, class _Proj2>182[[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_Tp*, _Tp*>183__mismatch(_Tp* __first1, _Tp* __last1, _Tp* __first2, _Tp* __last2, _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) {184 auto __len = std::min(__last1 - __first1, __last2 - __first2);185 return std::__mismatch(__first1, __first1 + __len, __first2, __pred, __proj1, __proj2);186}187 188template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>189[[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_InputIterator1, _InputIterator2>190mismatch(_InputIterator1 __first1,191 _InputIterator1 __last1,192 _InputIterator2 __first2,193 _InputIterator2 __last2,194 _BinaryPredicate __pred) {195 __identity __proj;196 auto __res = std::__mismatch(197 std::__unwrap_iter(__first1),198 std::__unwrap_iter(__last1),199 std::__unwrap_iter(__first2),200 std::__unwrap_iter(__last2),201 __pred,202 __proj,203 __proj);204 return {std::__rewrap_iter(__first1, __res.first), std::__rewrap_iter(__first2, __res.second)};205}206 207template <class _InputIterator1, class _InputIterator2>208[[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_InputIterator1, _InputIterator2>209mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) {210 return std::mismatch(__first1, __last1, __first2, __last2, __equal_to());211}212#endif213 214_LIBCPP_END_NAMESPACE_STD215 216_LIBCPP_POP_MACROS217 218#endif // _LIBCPP___ALGORITHM_MISMATCH_H219