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_N_H 11 #define _LIBCPP___ALGORITHM_SEARCH_N_H 12 13 #include <__config> 14 #include <__algorithm/comp.h> 15 #include <__iterator/iterator_traits.h> 16 #include <type_traits> 17 18 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 19 #pragma GCC system_header 20 #endif 21 22 _LIBCPP_PUSH_MACROS 23 #include <__undef_macros> 24 25 _LIBCPP_BEGIN_NAMESPACE_STD 26 27 template <class _BinaryPredicate, class _ForwardIterator, class _Size, class _Tp> 28 _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator __search_n(_ForwardIterator __first, _ForwardIterator __last, 29 _Size __count, const _Tp& __value_, _BinaryPredicate __pred, 30 forward_iterator_tag) { 31 if (__count <= 0) 32 return __first; 33 while (true) { 34 // Find first element in sequence that matchs __value_, with a mininum of loop checks 35 while (true) { 36 if (__first == __last) // return __last if no element matches __value_ 37 return __last; 38 if (__pred(*__first, __value_)) 39 break; 40 ++__first; 41 } 42 // *__first matches __value_, now match elements after here 43 _ForwardIterator __m = __first; 44 _Size __c(0); 45 while (true) { 46 if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern) 47 return __first; 48 if (++__m == __last) // Otherwise if source exhaused, pattern not found 49 return __last; 50 if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first 51 { 52 __first = __m; 53 ++__first; 54 break; 55 } // else there is a match, check next elements 56 } 57 } 58 } 59 60 template <class _BinaryPredicate, class _RandomAccessIterator, class _Size, class _Tp> 61 _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator __search_n(_RandomAccessIterator __first, 62 _RandomAccessIterator __last, _Size __count, 63 const _Tp& __value_, _BinaryPredicate __pred, 64 random_access_iterator_tag) { 65 if (__count <= 0) 66 return __first; 67 _Size __len = static_cast<_Size>(__last - __first); 68 if (__len < __count) 69 return __last; 70 const _RandomAccessIterator __s = __last - (__count - 1); // Start of pattern match can't go beyond here 71 while (true) { 72 // Find first element in sequence that matchs __value_, with a mininum of loop checks 73 while (true) { 74 if (__first >= __s) // return __last if no element matches __value_ 75 return __last; 76 if (__pred(*__first, __value_)) 77 break; 78 ++__first; 79 } 80 // *__first matches __value_, now match elements after here 81 _RandomAccessIterator __m = __first; 82 _Size __c(0); 83 while (true) { 84 if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern) 85 return __first; 86 ++__m; // no need to check range on __m because __s guarantees we have enough source 87 if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first 88 { 89 __first = __m; 90 ++__first; 91 break; 92 } // else there is a match, check next elements 93 } 94 } 95 } 96 97 template <class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate> 98 _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator search_n( 99 _ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_, _BinaryPredicate __pred) { 100 return _VSTD::__search_n<typename add_lvalue_reference<_BinaryPredicate>::type>( 101 __first, __last, _VSTD::__convert_to_integral(__count), __value_, __pred, 102 typename iterator_traits<_ForwardIterator>::iterator_category()); 103 } 104 105 template <class _ForwardIterator, class _Size, class _Tp> 106 _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator 107 search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_) { 108 typedef typename iterator_traits<_ForwardIterator>::value_type __v; 109 return _VSTD::search_n(__first, __last, _VSTD::__convert_to_integral(__count), __value_, __equal_to<__v, _Tp>()); 110 } 111 112 _LIBCPP_END_NAMESPACE_STD 113 114 _LIBCPP_POP_MACROS 115 116 #endif // _LIBCPP___ALGORITHM_SEARCH_N_H 117