xref: /freebsd-src/contrib/llvm-project/libcxx/include/__algorithm/find_end.h (revision 0fca6ea1d4eea4c934cfff25ac9ee8ad6fe95583)
1fe6060f1SDimitry Andric // -*- C++ -*-
2fe6060f1SDimitry Andric //===----------------------------------------------------------------------===//
3fe6060f1SDimitry Andric //
4fe6060f1SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5fe6060f1SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
6fe6060f1SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7fe6060f1SDimitry Andric //
8fe6060f1SDimitry Andric //===----------------------------------------------------------------------===//
9fe6060f1SDimitry Andric 
10fe6060f1SDimitry Andric #ifndef _LIBCPP___ALGORITHM_FIND_END_OF_H
11fe6060f1SDimitry Andric #define _LIBCPP___ALGORITHM_FIND_END_OF_H
12fe6060f1SDimitry Andric 
13fe6060f1SDimitry Andric #include <__algorithm/comp.h>
14753f127fSDimitry Andric #include <__algorithm/iterator_operations.h>
15753f127fSDimitry Andric #include <__algorithm/search.h>
1604eeddc0SDimitry Andric #include <__config>
17753f127fSDimitry Andric #include <__functional/identity.h>
1806c3fb27SDimitry Andric #include <__functional/invoke.h>
19753f127fSDimitry Andric #include <__iterator/advance.h>
20fe6060f1SDimitry Andric #include <__iterator/iterator_traits.h>
21753f127fSDimitry Andric #include <__iterator/next.h>
22753f127fSDimitry Andric #include <__iterator/reverse_iterator.h>
23753f127fSDimitry Andric #include <__utility/pair.h>
24fe6060f1SDimitry Andric 
25fe6060f1SDimitry Andric #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
26fe6060f1SDimitry Andric #  pragma GCC system_header
27fe6060f1SDimitry Andric #endif
28fe6060f1SDimitry Andric 
29fe6060f1SDimitry Andric _LIBCPP_BEGIN_NAMESPACE_STD
30fe6060f1SDimitry Andric 
31cb14a3feSDimitry Andric template < class _AlgPolicy,
32753f127fSDimitry Andric            class _Iter1,
33753f127fSDimitry Andric            class _Sent1,
34753f127fSDimitry Andric            class _Iter2,
35753f127fSDimitry Andric            class _Sent2,
36753f127fSDimitry Andric            class _Pred,
37753f127fSDimitry Andric            class _Proj1,
38753f127fSDimitry Andric            class _Proj2>
39bdd1243dSDimitry Andric _LIBCPP_HIDE_FROM_ABI inline _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_Iter1, _Iter1> __find_end_impl(
40753f127fSDimitry Andric     _Iter1 __first1,
41753f127fSDimitry Andric     _Sent1 __last1,
42753f127fSDimitry Andric     _Iter2 __first2,
43753f127fSDimitry Andric     _Sent2 __last2,
44753f127fSDimitry Andric     _Pred& __pred,
45753f127fSDimitry Andric     _Proj1& __proj1,
46753f127fSDimitry Andric     _Proj2& __proj2,
47753f127fSDimitry Andric     forward_iterator_tag,
48fe6060f1SDimitry Andric     forward_iterator_tag) {
49fe6060f1SDimitry Andric   // modeled after search algorithm
50753f127fSDimitry Andric   _Iter1 __match_first = _IterOps<_AlgPolicy>::next(__first1, __last1); // __last1 is the "default" answer
51753f127fSDimitry Andric   _Iter1 __match_last  = __match_first;
52fe6060f1SDimitry Andric   if (__first2 == __last2)
53753f127fSDimitry Andric     return pair<_Iter1, _Iter1>(__match_last, __match_last);
54fe6060f1SDimitry Andric   while (true) {
55fe6060f1SDimitry Andric     while (true) {
56753f127fSDimitry Andric       if (__first1 == __last1) // if source exhausted return last correct answer (or __last1 if never found)
57753f127fSDimitry Andric         return pair<_Iter1, _Iter1>(__match_first, __match_last);
58753f127fSDimitry Andric       if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2)))
59fe6060f1SDimitry Andric         break;
60fe6060f1SDimitry Andric       ++__first1;
61fe6060f1SDimitry Andric     }
62fe6060f1SDimitry Andric     // *__first1 matches *__first2, now match elements after here
63753f127fSDimitry Andric     _Iter1 __m1 = __first1;
64753f127fSDimitry Andric     _Iter2 __m2 = __first2;
65fe6060f1SDimitry Andric     while (true) {
66fe6060f1SDimitry Andric       if (++__m2 == __last2) { // Pattern exhaused, record answer and search for another one
67753f127fSDimitry Andric         __match_first = __first1;
68753f127fSDimitry Andric         __match_last  = ++__m1;
69fe6060f1SDimitry Andric         ++__first1;
70fe6060f1SDimitry Andric         break;
71fe6060f1SDimitry Andric       }
72fe6060f1SDimitry Andric       if (++__m1 == __last1) // Source exhausted, return last answer
73753f127fSDimitry Andric         return pair<_Iter1, _Iter1>(__match_first, __match_last);
74753f127fSDimitry Andric       // mismatch, restart with a new __first
75cb14a3feSDimitry Andric       if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2))) {
76fe6060f1SDimitry Andric         ++__first1;
77fe6060f1SDimitry Andric         break;
78fe6060f1SDimitry Andric       } // else there is a match, check next elements
79fe6060f1SDimitry Andric     }
80fe6060f1SDimitry Andric   }
81fe6060f1SDimitry Andric }
82fe6060f1SDimitry Andric 
83cb14a3feSDimitry Andric template < class _IterOps,
84753f127fSDimitry Andric            class _Pred,
85753f127fSDimitry Andric            class _Iter1,
86753f127fSDimitry Andric            class _Sent1,
87753f127fSDimitry Andric            class _Iter2,
88753f127fSDimitry Andric            class _Sent2,
89753f127fSDimitry Andric            class _Proj1,
90753f127fSDimitry Andric            class _Proj2>
91bdd1243dSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _Iter1 __find_end(
92753f127fSDimitry Andric     _Iter1 __first1,
93753f127fSDimitry Andric     _Sent1 __sent1,
94753f127fSDimitry Andric     _Iter2 __first2,
95753f127fSDimitry Andric     _Sent2 __sent2,
96753f127fSDimitry Andric     _Pred& __pred,
97753f127fSDimitry Andric     _Proj1& __proj1,
98753f127fSDimitry Andric     _Proj2& __proj2,
99753f127fSDimitry Andric     bidirectional_iterator_tag,
100753f127fSDimitry Andric     bidirectional_iterator_tag) {
101753f127fSDimitry Andric   auto __last1 = _IterOps::next(__first1, __sent1);
102753f127fSDimitry Andric   auto __last2 = _IterOps::next(__first2, __sent2);
103fe6060f1SDimitry Andric   // modeled after search algorithm (in reverse)
104fe6060f1SDimitry Andric   if (__first2 == __last2)
105fe6060f1SDimitry Andric     return __last1; // Everything matches an empty sequence
106753f127fSDimitry Andric   _Iter1 __l1 = __last1;
107753f127fSDimitry Andric   _Iter2 __l2 = __last2;
108fe6060f1SDimitry Andric   --__l2;
109fe6060f1SDimitry Andric   while (true) {
110fe6060f1SDimitry Andric     // Find last element in sequence 1 that matchs *(__last2-1), with a mininum of loop checks
111fe6060f1SDimitry Andric     while (true) {
112fe6060f1SDimitry Andric       if (__first1 == __l1) // return __last1 if no element matches *__first2
113fe6060f1SDimitry Andric         return __last1;
114753f127fSDimitry Andric       if (std::__invoke(__pred, std::__invoke(__proj1, *--__l1), std::__invoke(__proj2, *__l2)))
115fe6060f1SDimitry Andric         break;
116fe6060f1SDimitry Andric     }
117fe6060f1SDimitry Andric     // *__l1 matches *__l2, now match elements before here
118753f127fSDimitry Andric     _Iter1 __m1 = __l1;
119753f127fSDimitry Andric     _Iter2 __m2 = __l2;
120fe6060f1SDimitry Andric     while (true) {
121fe6060f1SDimitry Andric       if (__m2 == __first2) // If pattern exhausted, __m1 is the answer (works for 1 element pattern)
122fe6060f1SDimitry Andric         return __m1;
123fe6060f1SDimitry Andric       if (__m1 == __first1) // Otherwise if source exhaused, pattern not found
124fe6060f1SDimitry Andric         return __last1;
125753f127fSDimitry Andric 
126753f127fSDimitry Andric       // if there is a mismatch, restart with a new __l1
127cb14a3feSDimitry Andric       if (!std::__invoke(__pred, std::__invoke(__proj1, *--__m1), std::__invoke(__proj2, *--__m2))) {
128fe6060f1SDimitry Andric         break;
129fe6060f1SDimitry Andric       } // else there is a match, check next elements
130fe6060f1SDimitry Andric     }
131fe6060f1SDimitry Andric   }
132fe6060f1SDimitry Andric }
133fe6060f1SDimitry Andric 
134cb14a3feSDimitry Andric template < class _AlgPolicy,
135753f127fSDimitry Andric            class _Pred,
136753f127fSDimitry Andric            class _Iter1,
137753f127fSDimitry Andric            class _Sent1,
138753f127fSDimitry Andric            class _Iter2,
139753f127fSDimitry Andric            class _Sent2,
140753f127fSDimitry Andric            class _Proj1,
141753f127fSDimitry Andric            class _Proj2>
142bdd1243dSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iter1 __find_end(
143753f127fSDimitry Andric     _Iter1 __first1,
144753f127fSDimitry Andric     _Sent1 __sent1,
145753f127fSDimitry Andric     _Iter2 __first2,
146753f127fSDimitry Andric     _Sent2 __sent2,
147753f127fSDimitry Andric     _Pred& __pred,
148753f127fSDimitry Andric     _Proj1& __proj1,
149753f127fSDimitry Andric     _Proj2& __proj2,
150753f127fSDimitry Andric     random_access_iterator_tag,
151753f127fSDimitry Andric     random_access_iterator_tag) {
152753f127fSDimitry Andric   typedef typename iterator_traits<_Iter1>::difference_type _D1;
153753f127fSDimitry Andric   auto __last1 = _IterOps<_AlgPolicy>::next(__first1, __sent1);
154753f127fSDimitry Andric   auto __last2 = _IterOps<_AlgPolicy>::next(__first2, __sent2);
155fe6060f1SDimitry Andric   // Take advantage of knowing source and pattern lengths.  Stop short when source is smaller than pattern
156753f127fSDimitry Andric   auto __len2 = __last2 - __first2;
157fe6060f1SDimitry Andric   if (__len2 == 0)
158fe6060f1SDimitry Andric     return __last1;
159753f127fSDimitry Andric   auto __len1 = __last1 - __first1;
160fe6060f1SDimitry Andric   if (__len1 < __len2)
161fe6060f1SDimitry Andric     return __last1;
162753f127fSDimitry Andric   const _Iter1 __s = __first1 + _D1(__len2 - 1); // End of pattern match can't go before here
163753f127fSDimitry Andric   _Iter1 __l1      = __last1;
164753f127fSDimitry Andric   _Iter2 __l2      = __last2;
165fe6060f1SDimitry Andric   --__l2;
166fe6060f1SDimitry Andric   while (true) {
167fe6060f1SDimitry Andric     while (true) {
168fe6060f1SDimitry Andric       if (__s == __l1)
169fe6060f1SDimitry Andric         return __last1;
170753f127fSDimitry Andric       if (std::__invoke(__pred, std::__invoke(__proj1, *--__l1), std::__invoke(__proj2, *__l2)))
171fe6060f1SDimitry Andric         break;
172fe6060f1SDimitry Andric     }
173753f127fSDimitry Andric     _Iter1 __m1 = __l1;
174753f127fSDimitry Andric     _Iter2 __m2 = __l2;
175fe6060f1SDimitry Andric     while (true) {
176fe6060f1SDimitry Andric       if (__m2 == __first2)
177fe6060f1SDimitry Andric         return __m1;
178fe6060f1SDimitry Andric       // no need to check range on __m1 because __s guarantees we have enough source
179753f127fSDimitry Andric       if (!std::__invoke(__pred, std::__invoke(__proj1, *--__m1), std::__invoke(*--__m2))) {
180fe6060f1SDimitry Andric         break;
181fe6060f1SDimitry Andric       }
182fe6060f1SDimitry Andric     }
183fe6060f1SDimitry Andric   }
184fe6060f1SDimitry Andric }
185fe6060f1SDimitry Andric 
186fe6060f1SDimitry Andric template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
187cb14a3feSDimitry Andric _LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _ForwardIterator1 __find_end_classic(
188cb14a3feSDimitry Andric     _ForwardIterator1 __first1,
189cb14a3feSDimitry Andric     _ForwardIterator1 __last1,
190cb14a3feSDimitry Andric     _ForwardIterator2 __first2,
191cb14a3feSDimitry Andric     _ForwardIterator2 __last2,
192753f127fSDimitry Andric     _BinaryPredicate& __pred) {
193753f127fSDimitry Andric   auto __proj = __identity();
194753f127fSDimitry Andric   return std::__find_end_impl<_ClassicAlgPolicy>(
195753f127fSDimitry Andric              __first1,
196753f127fSDimitry Andric              __last1,
197753f127fSDimitry Andric              __first2,
198753f127fSDimitry Andric              __last2,
199753f127fSDimitry Andric              __pred,
200753f127fSDimitry Andric              __proj,
201753f127fSDimitry Andric              __proj,
202753f127fSDimitry Andric              typename iterator_traits<_ForwardIterator1>::iterator_category(),
203753f127fSDimitry Andric              typename iterator_traits<_ForwardIterator2>::iterator_category())
204753f127fSDimitry Andric       .first;
205753f127fSDimitry Andric }
206753f127fSDimitry Andric 
207753f127fSDimitry Andric template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
208*0fca6ea1SDimitry Andric _LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator1 find_end(
209cb14a3feSDimitry Andric     _ForwardIterator1 __first1,
210cb14a3feSDimitry Andric     _ForwardIterator1 __last1,
211cb14a3feSDimitry Andric     _ForwardIterator2 __first2,
212cb14a3feSDimitry Andric     _ForwardIterator2 __last2,
213fe6060f1SDimitry Andric     _BinaryPredicate __pred) {
214753f127fSDimitry Andric   return std::__find_end_classic(__first1, __last1, __first2, __last2, __pred);
215fe6060f1SDimitry Andric }
216fe6060f1SDimitry Andric 
217fe6060f1SDimitry Andric template <class _ForwardIterator1, class _ForwardIterator2>
218*0fca6ea1SDimitry Andric _LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator1
219cb14a3feSDimitry Andric find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) {
220bdd1243dSDimitry Andric   return std::find_end(__first1, __last1, __first2, __last2, __equal_to());
221fe6060f1SDimitry Andric }
222fe6060f1SDimitry Andric 
223fe6060f1SDimitry Andric _LIBCPP_END_NAMESPACE_STD
224fe6060f1SDimitry Andric 
225fe6060f1SDimitry Andric #endif // _LIBCPP___ALGORITHM_FIND_END_OF_H
226