__cxx03/__algorithm/mismatch.h

0001 // -*- C++ -*-
0002 //===----------------------------------------------------------------------===//
0003 //
0004 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0005 // See https://llvm.org/LICENSE.txt for license information.
0006 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0007 //
0008 //===----------------------------------------------------------------------===//
0009
0010 #ifndef _LIBCPP___CXX03___ALGORITHM_MISMATCH_H
0011 #define _LIBCPP___CXX03___ALGORITHM_MISMATCH_H
0012
0013 #include <__cxx03/__algorithm/comp.h>
0014 #include <__cxx03/__algorithm/min.h>
0015 #include <__cxx03/__algorithm/simd_utils.h>
0016 #include <__cxx03/__algorithm/unwrap_iter.h>
0017 #include <__cxx03/__config>
0018 #include <__cxx03/__functional/identity.h>
0019 #include <__cxx03/__iterator/aliasing_iterator.h>
0020 #include <__cxx03/__type_traits/desugars_to.h>
0021 #include <__cxx03/__type_traits/invoke.h>
0022 #include <__cxx03/__type_traits/is_constant_evaluated.h>
0023 #include <__cxx03/__type_traits/is_equality_comparable.h>
0024 #include <__cxx03/__type_traits/is_integral.h>
0025 #include <__cxx03/__utility/move.h>
0026 #include <__cxx03/__utility/pair.h>
0027 #include <__cxx03/__utility/unreachable.h>
0028 #include <__cxx03/cstddef>
0029
0030 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0031 #  pragma GCC system_header
0032 #endif
0033
0034 _LIBCPP_PUSH_MACROS
0035 #include <__cxx03/__undef_macros>
0036
0037 _LIBCPP_BEGIN_NAMESPACE_STD
0038
0039 template <class _Iter1, class _Sent1, class _Iter2, class _Pred, class _Proj1, class _Proj2>
0040 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_Iter1, _Iter2>
0041 __mismatch_loop(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) {
0042   while (__first1 != __last1) {
0043     if (!std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2)))
0044       break;
0045     ++__first1;
0046     ++__first2;
0047   }
0048   return std::make_pair(std::move(__first1), std::move(__first2));
0049 }
0050
0051 template <class _Iter1, class _Sent1, class _Iter2, class _Pred, class _Proj1, class _Proj2>
0052 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_Iter1, _Iter2>
0053 __mismatch(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) {
0054   return std::__mismatch_loop(__first1, __last1, __first2, __pred, __proj1, __proj2);
0055 }
0056
0057 #if _LIBCPP_VECTORIZE_ALGORITHMS
0058
0059 template <class _Iter>
0060 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_Iter, _Iter>
0061 __mismatch_vectorized(_Iter __first1, _Iter __last1, _Iter __first2) {
0062   using __value_type              = __iter_value_type<_Iter>;
0063   constexpr size_t __unroll_count = 4;
0064   constexpr size_t __vec_size     = __native_vector_size<__value_type>;
0065   using __vec                     = __simd_vector<__value_type, __vec_size>;
0066
0067   if (!__libcpp_is_constant_evaluated()) {
0068     auto __orig_first1 = __first1;
0069     auto __last2       = __first2 + (__last1 - __first1);
0070     while (static_cast<size_t>(__last1 - __first1) >= __unroll_count * __vec_size) [[__unlikely__]] {
0071       __vec __lhs[__unroll_count];
0072       __vec __rhs[__unroll_count];
0073
0074       for (size_t __i = 0; __i != __unroll_count; ++__i) {
0075         __lhs[__i] = std::__load_vector<__vec>(__first1 + __i * __vec_size);
0076         __rhs[__i] = std::__load_vector<__vec>(__first2 + __i * __vec_size);
0077       }
0078
0079       for (size_t __i = 0; __i != __unroll_count; ++__i) {
0080         if (auto __cmp_res = __lhs[__i] == __rhs[__i]; !std::__all_of(__cmp_res)) {
0081           auto __offset = __i * __vec_size + std::__find_first_not_set(__cmp_res);
0082           return {__first1 + __offset, __first2 + __offset};
0083         }
0084       }
0085
0086       __first1 += __unroll_count * __vec_size;
0087       __first2 += __unroll_count * __vec_size;
0088     }
0089
0090     // check the remaining 0-3 vectors
0091     while (static_cast<size_t>(__last1 - __first1) >= __vec_size) {
0092       if (auto __cmp_res = std::__load_vector<__vec>(__first1) == std::__load_vector<__vec>(__first2);
0093           !std::__all_of(__cmp_res)) {
0094         auto __offset = std::__find_first_not_set(__cmp_res);
0095         return {__first1 + __offset, __first2 + __offset};
0096       }
0097       __first1 += __vec_size;
0098       __first2 += __vec_size;
0099     }
0100
0101     if (__last1 - __first1 == 0)
0102       return {__first1, __first2};
0103
0104     // Check if we can load elements in front of the current pointer. If that's the case load a vector at
0105     // (last - vector_size) to check the remaining elements
0106     if (static_cast<size_t>(__first1 - __orig_first1) >= __vec_size) {
0107       __first1 = __last1 - __vec_size;
0108       __first2 = __last2 - __vec_size;
0109       auto __offset =
0110           std::__find_first_not_set(std::__load_vector<__vec>(__first1) == std::__load_vector<__vec>(__first2));
0111       return {__first1 + __offset, __first2 + __offset};
0112     } // else loop over the elements individually
0113   }
0114
0115   __equal_to __pred;
0116   __identity __proj;
0117   return std::__mismatch_loop(__first1, __last1, __first2, __pred, __proj, __proj);
0118 }
0119
0120 template <class _Tp,
0121           class _Pred,
0122           class _Proj1,
0123           class _Proj2,
0124           __enable_if_t<is_integral<_Tp>::value && __desugars_to_v<__equal_tag, _Pred, _Tp, _Tp> &&
0125                             __is_identity<_Proj1>::value && __is_identity<_Proj2>::value,
0126                         int> = 0>
0127 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_Tp*, _Tp*>
0128 __mismatch(_Tp* __first1, _Tp* __last1, _Tp* __first2, _Pred&, _Proj1&, _Proj2&) {
0129   return std::__mismatch_vectorized(__first1, __last1, __first2);
0130 }
0131
0132 template <class _Tp,
0133           class _Pred,
0134           class _Proj1,
0135           class _Proj2,
0136           __enable_if_t<!is_integral<_Tp>::value && __desugars_to_v<__equal_tag, _Pred, _Tp, _Tp> &&
0137                             __is_identity<_Proj1>::value && __is_identity<_Proj2>::value &&
0138                             __can_map_to_integer_v<_Tp> && __libcpp_is_trivially_equality_comparable<_Tp, _Tp>::value,
0139                         int> = 0>
0140 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_Tp*, _Tp*>
0141 __mismatch(_Tp* __first1, _Tp* __last1, _Tp* __first2, _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) {
0142   if (__libcpp_is_constant_evaluated()) {
0143     return std::__mismatch_loop(__first1, __last1, __first2, __pred, __proj1, __proj2);
0144   } else {
0145     using _Iter = __aliasing_iterator<_Tp*, __get_as_integer_type_t<_Tp>>;
0146     auto __ret  = std::__mismatch_vectorized(_Iter(__first1), _Iter(__last1), _Iter(__first2));
0147     return {__ret.first.__base(), __ret.second.__base()};
0148   }
0149 }
0150 #endif // _LIBCPP_VECTORIZE_ALGORITHMS
0151
0152 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
0153 _LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_InputIterator1, _InputIterator2>
0154 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred) {
0155   __identity __proj;
0156   auto __res = std::__mismatch(
0157       std::__unwrap_iter(__first1), std::__unwrap_iter(__last1), std::__unwrap_iter(__first2), __pred, __proj, __proj);
0158   return std::make_pair(std::__rewrap_iter(__first1, __res.first), std::__rewrap_iter(__first2, __res.second));
0159 }
0160
0161 template <class _InputIterator1, class _InputIterator2>
0162 _LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_InputIterator1, _InputIterator2>
0163 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2) {
0164   return std::mismatch(__first1, __last1, __first2, __equal_to());
0165 }
0166
0167 #if _LIBCPP_STD_VER >= 14
0168 template <class _Iter1, class _Sent1, class _Iter2, class _Sent2, class _Pred, class _Proj1, class _Proj2>
0169 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_Iter1, _Iter2> __mismatch(
0170     _Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) {
0171   while (__first1 != __last1 && __first2 != __last2) {
0172     if (!std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2)))
0173       break;
0174     ++__first1;
0175     ++__first2;
0176   }
0177   return {std::move(__first1), std::move(__first2)};
0178 }
0179
0180 template <class _Tp, class _Pred, class _Proj1, class _Proj2>
0181 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_Tp*, _Tp*>
0182 __mismatch(_Tp* __first1, _Tp* __last1, _Tp* __first2, _Tp* __last2, _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) {
0183   auto __len = std::min(__last1 - __first1, __last2 - __first2);
0184   return std::__mismatch(__first1, __first1 + __len, __first2, __pred, __proj1, __proj2);
0185 }
0186
0187 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
0188 _LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_InputIterator1, _InputIterator2>
0189 mismatch(_InputIterator1 __first1,
0190          _InputIterator1 __last1,
0191          _InputIterator2 __first2,
0192          _InputIterator2 __last2,
0193          _BinaryPredicate __pred) {
0194   __identity __proj;
0195   auto __res = std::__mismatch(
0196       std::__unwrap_iter(__first1),
0197       std::__unwrap_iter(__last1),
0198       std::__unwrap_iter(__first2),
0199       std::__unwrap_iter(__last2),
0200       __pred,
0201       __proj,
0202       __proj);
0203   return {std::__rewrap_iter(__first1, __res.first), std::__rewrap_iter(__first2, __res.second)};
0204 }
0205
0206 template <class _InputIterator1, class _InputIterator2>
0207 _LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_InputIterator1, _InputIterator2>
0208 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) {
0209   return std::mismatch(__first1, __last1, __first2, __last2, __equal_to());
0210 }
0211 #endif
0212
0213 _LIBCPP_END_NAMESPACE_STD
0214
0215 _LIBCPP_POP_MACROS
0216
0217 #endif // _LIBCPP___CXX03___ALGORITHM_MISMATCH_H