1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#ifndef _LIBCPP___PSTL_CPU_ALGOS_SEARCH_N_H
10#define _LIBCPP___PSTL_CPU_ALGOS_SEARCH_N_H
11
12#include <__algorithm/search_n.h>
13#include <__config>
14#include <__functional/operations.h>
15#include <__iterator/concepts.h>
16#include <__iterator/iterator_traits.h>
17#include <__optional/nullopt_t.h>
18#include <__optional/optional.h>
19#include <__pstl/backend_fwd.h>
20#include <__pstl/cpu_algos/cpu_traits.h>
21#include <__pstl/cpu_algos/find_if.h>
22#include <__type_traits/is_execution_policy.h>
23#include <__utility/convert_to_integral.h>
24#include <__utility/move.h>
25#include <__utility/pair.h>
26
27#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
28# pragma GCC system_header
29#endif
30
31_LIBCPP_PUSH_MACROS
32#include <__undef_macros>
33
34#if _LIBCPP_STD_VER >= 17
35
36_LIBCPP_BEGIN_NAMESPACE_STD
37namespace __pstl {
38
39template <class _Backend, class _RawExecutionPolicy>
40struct __cpu_parallel_search_n {
41 template <class _Policy, class _ForwardIterator, class _Size, class _Tp, class _Predicate>
42 _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
43 operator()(_Policy&&,
44 _ForwardIterator __first,
45 _ForwardIterator __last,
46 _Size __count,
47 const _Tp& __value,
48 _Predicate __pred) const noexcept {
49 if constexpr (__is_parallel_execution_policy_v<_RawExecutionPolicy> &&
50 __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
51 typedef typename std::iterator_traits<_ForwardIterator>::difference_type _DifferenceType;
52 _DifferenceType __integral_count = std::__convert_to_integral(__count);
53 if (__integral_count <= 0) {
54 return __first; // If the count is non-positive, the first iterator is returned.
55 }
56 _DifferenceType __size = __last - __first;
57 if (__size < __integral_count) {
58 return __last; // The range is too small to contain the requested number of consecutive elements.
59 }
60 // Calculate the length of the tail where a potential match cannot start by definition.
61 _DifferenceType __crop = __integral_count - 1;
62 // We're only interested in the range where a potential match can start: [first, last - crop)
63 _ForwardIterator __last2 = __last - __crop;
64 // Run a parallel chunked find_if, covering the range where a potential match can start.
65 auto __res = __pstl::__parallel_find<_Backend>(
66 __first,
67 __last2,
68 [__integral_count, __crop, &__value, &__pred](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {
69 // Uncrop the range to allow std::search_n to find a full match, which can go beyond __brick_last.
70 _ForwardIterator __brick_last_uncropped = __brick_last + __crop;
71 // Run a serial std::search_n inside each of the chunks in parallel.
72 _ForwardIterator __ret =
73 std::search_n(__brick_first, __brick_last_uncropped, __integral_count, __value, __pred);
74 // The returned iterator is either a match inside [__brick_first, __brick_last) or a miss encoded as
75 // __brick_last_uncropped. Return the miss as __brick_last to conform to expectations of __parallel_find().
76 return __ret == __brick_last_uncropped ? __brick_last : __ret;
77 },
78 less<>{}, // `less` here means the lowest index among the matches
79 true // `true` here means we want the first match, not the last
80 );
81 if (!__res) {
82 return std::nullopt; // Failed to run the algorithm, propagate the error.
83 }
84 if (*__res == __last2) {
85 return __last; // No match was found in the range.
86 }
87 return *__res; // Return the successful match.
88 } else {
89 // Non-random access iterators cannot be processed in parallel, fall back to the sequential implementation.
90 return std::search_n(std::move(__first), std::move(__last), __count, __value, std::move(__pred));
91 }
92 }
93};
94
95} // namespace __pstl
96_LIBCPP_END_NAMESPACE_STD
97
98#endif // _LIBCPP_STD_VER >= 17
99
100_LIBCPP_POP_MACROS
101
102#endif // _LIBCPP___PSTL_CPU_ALGOS_SEARCH_N_H
103