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