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