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_FIND_END_H
10#define _LIBCPP___PSTL_BACKENDS_STATPART_FIND_END_H
11
12#include <__algorithm/find_end.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/move.h>
23
24#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
25# pragma GCC system_header
26#endif
27
28_LIBCPP_PUSH_MACROS
29#include <__undef_macros>
30
31#if _LIBCPP_STD_VER >= 17
32
33_LIBCPP_BEGIN_NAMESPACE_STD
34_LIBCPP_BEGIN_EXPLICIT_ABI_ANNOTATIONS
35namespace __pstl {
36
37template <class _ExecutionPolicy>
38struct __find_end<__statpart_backend_tag, _ExecutionPolicy> {
39 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
40 _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator1>
41 operator()(_Policy&&,
42 _ForwardIterator1 __first1,
43 _ForwardIterator1 __last1,
44 _ForwardIterator2 __first2,
45 _ForwardIterator2 __last2,
46 _BinaryPredicate __pred) const noexcept {
47 if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
48 __has_random_access_iterator_category_or_concept<_ForwardIterator1>::value &&
49 __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value) {
50 typedef typename std::iterator_traits<_ForwardIterator1>::difference_type _DifferenceType;
51 _DifferenceType __size2 = __last2 - __first2; // The length of the needle to search for.
52 if (__size2 == 0) {
53 return __last1; // If the needle length is zero, the last iterator is returned.
54 }
55 _DifferenceType __size1 = __last1 - __first1;
56 if (__size1 < __size2) {
57 return __last1; // 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 = __size2 - 1;
61 // We're only interested in the range where a potential match can start: [first, last - crop)
62 _ForwardIterator1 __last1_cropped = __last1 - __crop;
63 // Run a parallel chunked find_if, covering the range where a potential match can start.
64 auto __res = __statpart::__find(
65 __first1,
66 __last1_cropped,
67 [__first2, __last2, __crop, &__pred](_ForwardIterator1 __brick_first, _ForwardIterator1 __brick_last) {
68 // Uncrop the range to allow std::find_end to find a full match, which can go beyond __brick_last.
69 _ForwardIterator1 __brick_last_uncropped = __brick_last + __crop;
70 // Run a serial std::find_end inside each of the chunks in parallel.
71 _ForwardIterator1 __ret = std::find_end(__brick_first, __brick_last_uncropped, __first2, __last2, __pred);
72 // The returned iterator is either a match inside [__brick_first, __brick_last) or a miss encoded as
73 // __brick_last_uncropped. Return the miss as __brick_last to conform to expectations of __parallel_find().
74 return __ret == __brick_last_uncropped ? __brick_last : __ret;
75 },
76 greater<>{}, // `greater` here means the highest index among the matches
77 false // `false` here means we want the last match, not the first
78 );
79 if (!__res) {
80 return std::nullopt; // Failed to run the algorithm, propagate the error.
81 }
82 if (*__res == __last1_cropped) {
83 return __last1; // No match was found in the range.
84 }
85 return *__res; // Return the successful match.
86 } else {
87 // Non-random access iterators cannot be processed in parallel, fall back to the sequential implementation.
88 return std::find_end(
89 std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), 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_FIND_END_H
103