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, class _Sent1, 33 class _Iter2, class _Sent2, 34 class _Pred, 35 class _Proj1, 36 class _Proj2> 37 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 38 pair<_Iter1, _Iter1> __search_forward_impl(_Iter1 __first1, _Sent1 __last1, 39 _Iter2 __first2, _Sent2 __last2, 40 _Pred& __pred, 41 _Proj1& __proj1, 42 _Proj2& __proj2) { 43 if (__first2 == __last2) 44 return std::make_pair(__first1, __first1); // Everything matches an empty sequence 45 while (true) { 46 // Find first element in sequence 1 that matchs *__first2, with a mininum of loop checks 47 while (true) { 48 if (__first1 == __last1) { // return __last1 if no element matches *__first2 49 _IterOps<_AlgPolicy>::__advance_to(__first1, __last1); 50 return std::make_pair(__first1, __first1); 51 } 52 if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2))) 53 break; 54 ++__first1; 55 } 56 // *__first1 matches *__first2, now match elements after here 57 _Iter1 __m1 = __first1; 58 _Iter2 __m2 = __first2; 59 while (true) { 60 if (++__m2 == __last2) // If pattern exhausted, __first1 is the answer (works for 1 element pattern) 61 return std::make_pair(__first1, ++__m1); 62 if (++__m1 == __last1) { // Otherwise if source exhaused, pattern not found 63 return std::make_pair(__m1, __m1); 64 } 65 66 // if there is a mismatch, restart with a new __first1 67 if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2))) 68 { 69 ++__first1; 70 break; 71 } // else there is a match, check next elements 72 } 73 } 74 } 75 76 template <class _AlgPolicy, 77 class _Iter1, class _Sent1, 78 class _Iter2, class _Sent2, 79 class _Pred, 80 class _Proj1, 81 class _Proj2, 82 class _DiffT1, 83 class _DiffT2> 84 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 85 pair<_Iter1, _Iter1> __search_random_access_impl(_Iter1 __first1, _Sent1 __last1, 86 _Iter2 __first2, _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, class _Sent1, 120 class _Iter2, class _Sent2, 121 class _Pred, 122 class _Proj1, 123 class _Proj2> 124 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 125 pair<_Iter1, _Iter1> __search_impl(_Iter1 __first1, _Sent1 __last1, 126 _Iter2 __first2, _Sent2 __last2, 127 _Pred& __pred, 128 _Proj1& __proj1, 129 _Proj2& __proj2, 130 __enable_if_t<__has_random_access_iterator_category<_Iter1>::value 131 && __has_random_access_iterator_category<_Iter2>::value>* = nullptr) { 132 133 auto __size2 = __last2 - __first2; 134 if (__size2 == 0) 135 return std::make_pair(__first1, __first1); 136 137 auto __size1 = __last1 - __first1; 138 if (__size1 < __size2) { 139 return std::make_pair(__last1, __last1); 140 } 141 142 return std::__search_random_access_impl<_ClassicAlgPolicy>(__first1, __last1, 143 __first2, __last2, 144 __pred, 145 __proj1, 146 __proj2, 147 __size1, 148 __size2); 149 } 150 151 template <class _Iter1, class _Sent1, 152 class _Iter2, class _Sent2, 153 class _Pred, 154 class _Proj1, 155 class _Proj2> 156 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 157 pair<_Iter1, _Iter1> __search_impl(_Iter1 __first1, _Sent1 __last1, 158 _Iter2 __first2, _Sent2 __last2, 159 _Pred& __pred, 160 _Proj1& __proj1, 161 _Proj2& __proj2, 162 __enable_if_t<__has_forward_iterator_category<_Iter1>::value 163 && __has_forward_iterator_category<_Iter2>::value 164 && !(__has_random_access_iterator_category<_Iter1>::value 165 && __has_random_access_iterator_category<_Iter2>::value)>* = nullptr) { 166 return std::__search_forward_impl<_ClassicAlgPolicy>(__first1, __last1, 167 __first2, __last2, 168 __pred, 169 __proj1, 170 __proj2); 171 } 172 173 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> 174 _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 175 _ForwardIterator1 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 176 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 177 _BinaryPredicate __pred) { 178 static_assert(__is_callable<_BinaryPredicate, decltype(*__first1), decltype(*__first2)>::value, 179 "BinaryPredicate has to be callable"); 180 auto __proj = __identity(); 181 return std::__search_impl(__first1, __last1, __first2, __last2, __pred, __proj, __proj).first; 182 } 183 184 template <class _ForwardIterator1, class _ForwardIterator2> 185 _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 186 _ForwardIterator1 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 187 _ForwardIterator2 __first2, _ForwardIterator2 __last2) { 188 return std::search(__first1, __last1, __first2, __last2, __equal_to()); 189 } 190 191 #if _LIBCPP_STD_VER >= 17 192 template <class _ForwardIterator, class _Searcher> 193 _LIBCPP_NODISCARD_EXT _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator 194 search(_ForwardIterator __f, _ForwardIterator __l, const _Searcher& __s) { 195 return __s(__f, __l).first; 196 } 197 198 #endif 199 200 _LIBCPP_END_NAMESPACE_STD 201 202 #endif // _LIBCPP___ALGORITHM_SEARCH_H 203