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 31template <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 73template <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 120template <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 144template <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 159template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> 160_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator1 161search(_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 172template <class _ForwardIterator1, class _ForwardIterator2> 173_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator1 174search(_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 179template <class _ForwardIterator, class _Searcher> 180_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator 181search(_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