libcxx/include/__algorithm/search.h

   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/enable_if.h>
  21 #include <__type_traits/invoke.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 [[__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                 "The comparator 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 [[__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