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