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, class _Sent1, class _Iter2, class _Sent2, class _Pred, class _Proj1, class _Proj2> 121 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_Iter1, _Iter1> __search_impl( 122 _Iter1 __first1, 123 _Sent1 __last1, 124 _Iter2 __first2, 125 _Sent2 __last2, 126 _Pred& __pred, 127 _Proj1& __proj1, 128 _Proj2& __proj2, 129 __enable_if_t<__has_random_access_iterator_category<_Iter1>::value && 130 __has_random_access_iterator_category<_Iter2>::value>* = nullptr) { 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 <class _Iter1, class _Sent1, class _Iter2, class _Sent2, class _Pred, class _Proj1, class _Proj2> 145 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_Iter1, _Iter1> __search_impl( 146 _Iter1 __first1, 147 _Sent1 __last1, 148 _Iter2 __first2, 149 _Sent2 __last2, 150 _Pred& __pred, 151 _Proj1& __proj1, 152 _Proj2& __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)>* = nullptr) { 156 return std::__search_forward_impl<_ClassicAlgPolicy>(__first1, __last1, __first2, __last2, __pred, __proj1, __proj2); 157 } 158 159 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> 160 _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator1 161 search(_ForwardIterator1 __first1, 162 _ForwardIterator1 __last1, 163 _ForwardIterator2 __first2, 164 _ForwardIterator2 __last2, 165 _BinaryPredicate __pred) { 166 static_assert(__is_callable<_BinaryPredicate, decltype(*__first1), decltype(*__first2)>::value, 167 "BinaryPredicate has to be callable"); 168 auto __proj = __identity(); 169 return std::__search_impl(__first1, __last1, __first2, __last2, __pred, __proj, __proj).first; 170 } 171 172 template <class _ForwardIterator1, class _ForwardIterator2> 173 _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator1 174 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) { 175 return std::search(__first1, __last1, __first2, __last2, __equal_to()); 176 } 177 178 #if _LIBCPP_STD_VER >= 17 179 template <class _ForwardIterator, class _Searcher> 180 _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator 181 search(_ForwardIterator __f, _ForwardIterator __l, const _Searcher& __s) { 182 return __s(__f, __l).first; 183 } 184 185 #endif 186 187 _LIBCPP_END_NAMESPACE_STD 188 189 #endif // _LIBCPP___ALGORITHM_SEARCH_H 190