libcxx/include/__cxx03/__algorithm/mismatch.h

   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 <__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_header
  32 #endif
  33
  34 _LIBCPP_PUSH_MACROS
  35 #include <__cxx03/__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