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