xref: /freebsd/contrib/llvm-project/libcxx/include/__algorithm/search_n.h (revision 924226fba12cc9a228c73b956e1b7fa24c60b055)
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