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___CXX03___ALGORITHM_SEARCH_H
11 #define _LIBCPP___CXX03___ALGORITHM_SEARCH_H
12
13 #include <__cxx03/__algorithm/comp.h>
14 #include <__cxx03/__algorithm/iterator_operations.h>
15 #include <__cxx03/__config>
16 #include <__cxx03/__functional/identity.h>
17 #include <__cxx03/__iterator/advance.h>
18 #include <__cxx03/__iterator/iterator_traits.h>
19 #include <__cxx03/__type_traits/enable_if.h>
20 #include <__cxx03/__type_traits/invoke.h>
21 #include <__cxx03/__type_traits/is_callable.h>
22 #include <__cxx03/__utility/pair.h>
23
24 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
25 # pragma GCC system_header
26 #endif
27
28 _LIBCPP_BEGIN_NAMESPACE_STD
29
30 template <class _AlgPolicy,
31 class _Iter1,
32 class _Sent1,
33 class _Iter2,
34 class _Sent2,
35 class _Pred,
36 class _Proj1,
37 class _Proj2>
__search_forward_impl(_Iter1 __first1,_Sent1 __last1,_Iter2 __first2,_Sent2 __last2,_Pred & __pred,_Proj1 & __proj1,_Proj2 & __proj2)38 _LIBCPP_HIDE_FROM_ABI pair<_Iter1, _Iter1> __search_forward_impl(
39 _Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) {
40 if (__first2 == __last2)
41 return std::make_pair(__first1, __first1); // Everything matches an empty sequence
42 while (true) {
43 // Find first element in sequence 1 that matchs *__first2, with a mininum of loop checks
44 while (true) {
45 if (__first1 == __last1) { // return __last1 if no element matches *__first2
46 _IterOps<_AlgPolicy>::__advance_to(__first1, __last1);
47 return std::make_pair(__first1, __first1);
48 }
49 if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2)))
50 break;
51 ++__first1;
52 }
53 // *__first1 matches *__first2, now match elements after here
54 _Iter1 __m1 = __first1;
55 _Iter2 __m2 = __first2;
56 while (true) {
57 if (++__m2 == __last2) // If pattern exhausted, __first1 is the answer (works for 1 element pattern)
58 return std::make_pair(__first1, ++__m1);
59 if (++__m1 == __last1) { // Otherwise if source exhaused, pattern not found
60 return std::make_pair(__m1, __m1);
61 }
62
63 // if there is a mismatch, restart with a new __first1
64 if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2))) {
65 ++__first1;
66 break;
67 } // else there is a match, check next elements
68 }
69 }
70 }
71
72 template <class _AlgPolicy,
73 class _Iter1,
74 class _Sent1,
75 class _Iter2,
76 class _Sent2,
77 class _Pred,
78 class _Proj1,
79 class _Proj2,
80 class _DiffT1,
81 class _DiffT2>
__search_random_access_impl(_Iter1 __first1,_Sent1 __last1,_Iter2 __first2,_Sent2 __last2,_Pred & __pred,_Proj1 & __proj1,_Proj2 & __proj2,_DiffT1 __size1,_DiffT2 __size2)82 _LIBCPP_HIDE_FROM_ABI pair<_Iter1, _Iter1> __search_random_access_impl(
83 _Iter1 __first1,
84 _Sent1 __last1,
85 _Iter2 __first2,
86 _Sent2 __last2,
87 _Pred& __pred,
88 _Proj1& __proj1,
89 _Proj2& __proj2,
90 _DiffT1 __size1,
91 _DiffT2 __size2) {
92 const _Iter1 __s = __first1 + __size1 - _DiffT1(__size2 - 1); // Start of pattern match can't go beyond here
93
94 while (true) {
95 while (true) {
96 if (__first1 == __s) {
97 _IterOps<_AlgPolicy>::__advance_to(__first1, __last1);
98 return std::make_pair(__first1, __first1);
99 }
100 if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2)))
101 break;
102 ++__first1;
103 }
104
105 _Iter1 __m1 = __first1;
106 _Iter2 __m2 = __first2;
107 while (true) {
108 if (++__m2 == __last2)
109 return std::make_pair(__first1, __first1 + _DiffT1(__size2));
110 ++__m1; // no need to check range on __m1 because __s guarantees we have enough source
111 if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2))) {
112 ++__first1;
113 break;
114 }
115 }
116 }
117 }
118
119 template <class _Iter1,
120 class _Sent1,
121 class _Iter2,
122 class _Sent2,
123 class _Pred,
124 class _Proj1,
125 class _Proj2,
126 __enable_if_t<__has_random_access_iterator_category<_Iter1>::value &&
127 __has_random_access_iterator_category<_Iter2>::value,
128 int> = 0>
__search_impl(_Iter1 __first1,_Sent1 __last1,_Iter2 __first2,_Sent2 __last2,_Pred & __pred,_Proj1 & __proj1,_Proj2 & __proj2)129 _LIBCPP_HIDE_FROM_ABI pair<_Iter1, _Iter1> __search_impl(
130 _Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) {
131 auto __size2 = __last2 - __first2;
132 if (__size2 == 0)
133 return std::make_pair(__first1, __first1);
134
135 auto __size1 = __last1 - __first1;
136 if (__size1 < __size2) {
137 return std::make_pair(__last1, __last1);
138 }
139
140 return std::__search_random_access_impl<_ClassicAlgPolicy>(
141 __first1, __last1, __first2, __last2, __pred, __proj1, __proj2, __size1, __size2);
142 }
143
144 template <
145 class _Iter1,
146 class _Sent1,
147 class _Iter2,
148 class _Sent2,
149 class _Pred,
150 class _Proj1,
151 class _Proj2,
152 __enable_if_t<__has_forward_iterator_category<_Iter1>::value && __has_forward_iterator_category<_Iter2>::value &&
153 !(__has_random_access_iterator_category<_Iter1>::value &&
154 __has_random_access_iterator_category<_Iter2>::value),
155 int> = 0>
__search_impl(_Iter1 __first1,_Sent1 __last1,_Iter2 __first2,_Sent2 __last2,_Pred & __pred,_Proj1 & __proj1,_Proj2 & __proj2)156 _LIBCPP_HIDE_FROM_ABI pair<_Iter1, _Iter1> __search_impl(
157 _Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) {
158 return std::__search_forward_impl<_ClassicAlgPolicy>(__first1, __last1, __first2, __last2, __pred, __proj1, __proj2);
159 }
160
161 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
162 _LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator1
search(_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_ForwardIterator2 __last2,_BinaryPredicate __pred)163 search(_ForwardIterator1 __first1,
164 _ForwardIterator1 __last1,
165 _ForwardIterator2 __first2,
166 _ForwardIterator2 __last2,
167 _BinaryPredicate __pred) {
168 static_assert(__is_callable<_BinaryPredicate, decltype(*__first1), decltype(*__first2)>::value,
169 "BinaryPredicate has to be callable");
170 auto __proj = __identity();
171 return std::__search_impl(__first1, __last1, __first2, __last2, __pred, __proj, __proj).first;
172 }
173
174 template <class _ForwardIterator1, class _ForwardIterator2>
175 _LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator1
search(_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_ForwardIterator2 __last2)176 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) {
177 return std::search(__first1, __last1, __first2, __last2, __equal_to());
178 }
179
180 _LIBCPP_END_NAMESPACE_STD
181
182 #endif // _LIBCPP___CXX03___ALGORITHM_SEARCH_H
183