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>  // __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   if (__count <= 0)
63     return __first;
64   _Size __len = static_cast<_Size>(__last - __first);
65   if (__len < __count)
66     return __last;
67   const _RandomAccessIterator __s = __last - (__count - 1); // Start of pattern match can't go beyond here
68   while (true) {
69     // Find first element in sequence that matchs __value_, with a mininum of loop checks
70     while (true) {
71       if (__first >= __s) // return __last if no element matches __value_
72         return __last;
73       if (__pred(*__first, __value_))
74         break;
75       ++__first;
76     }
77     // *__first matches __value_, now match elements after here
78     _RandomAccessIterator __m = __first;
79     _Size __c(0);
80     while (true) {
81       if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern)
82         return __first;
83       ++__m;                       // no need to check range on __m because __s guarantees we have enough source
84       if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first
85       {
86         __first = __m;
87         ++__first;
88         break;
89       } // else there is a match, check next elements
90     }
91   }
92 }
93 
94 template <class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate>
95 _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator search_n(
96     _ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_, _BinaryPredicate __pred) {
97   return _VSTD::__search_n<_BinaryPredicate&>(
98       __first, __last, _VSTD::__convert_to_integral(__count), __value_, __pred,
99       typename iterator_traits<_ForwardIterator>::iterator_category());
100 }
101 
102 template <class _ForwardIterator, class _Size, class _Tp>
103 _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
104 search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_) {
105   typedef typename iterator_traits<_ForwardIterator>::value_type __v;
106   return _VSTD::search_n(__first, __last, _VSTD::__convert_to_integral(__count), __value_, __equal_to<__v, _Tp>());
107 }
108 
109 _LIBCPP_END_NAMESPACE_STD
110 
111 #endif // _LIBCPP___ALGORITHM_SEARCH_N_H
112