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_H
10#define _LIBCPP___PSTL_CPU_ALGOS_SEARCH_H
11
12#include <__algorithm/search.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
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
35_LIBCPP_BEGIN_NAMESPACE_STD
36namespace __pstl {
37
38template <class _Backend, class _RawExecutionPolicy>
39struct __cpu_parallel_search {
40 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
41 _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator1>
42 operator()(_Policy&&,
43 _ForwardIterator1 __first1,
44 _ForwardIterator1 __last1,
45 _ForwardIterator2 __first2,
46 _ForwardIterator2 __last2,
47 _BinaryPredicate __pred) const noexcept {
48 if constexpr (__is_parallel_execution_policy_v<_RawExecutionPolicy> &&
49 __has_random_access_iterator_category_or_concept<_ForwardIterator1>::value &&
50 __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value) {
51 typedef typename std::iterator_traits<_ForwardIterator1>::difference_type _DifferenceType;
52 _DifferenceType __size2 = __last2 - __first2; // The length of the needle to search for.
53 if (__size2 == 0) {
54 return __first1; // If the needle length is zero, the first iterator is returned.
55 }
56 _DifferenceType __size1 = __last1 - __first1;
57 if (__size1 < __size2) {
58 return __last1; // 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 = __size2 - 1;
62 // We're only interested in the range where a potential match can start: [first, last - crop)
63 _ForwardIterator1 __last1_cropped = __last1 - __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 __first1,
67 __last1_cropped,
68 [__first2, __last2, __crop, &__pred](_ForwardIterator1 __brick_first, _ForwardIterator1 __brick_last) {
69 // Uncrop the range to allow std::search to find a full match, which can go beyond __brick_last.
70 _ForwardIterator1 __brick_last_uncropped = __brick_last + __crop;
71 // Run a serial std::search inside each of the chunks in parallel.
72 _ForwardIterator1 __ret = std::search(__brick_first, __brick_last_uncropped, __first2, __last2, __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 __parallel_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 == __last1_cropped) {
84 return __last1; // 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(
90 std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), 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_H
103