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