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_MIN_ELEMENT_H
10#define _LIBCPP___PSTL_CPU_ALGOS_MIN_ELEMENT_H
11
12#include <__algorithm/min_element.h>
13#include <__config>
14#include <__functional/identity.h>
15#include <__functional/operations.h>
16#include <__iterator/concepts.h>
17#include <__iterator/iterator_traits.h>
18#include <__optional/optional.h>
19#include <__pstl/backend_fwd.h>
20#include <__pstl/cpu_algos/cpu_traits.h>
21#include <__type_traits/is_execution_policy.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
34namespace __pstl {
35
36template <class _Backend, class _RawExecutionPolicy>
37struct __cpu_parallel_min_element {
38 template <class _Policy, class _ForwardIterator, class _Compare>
39 _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
40 operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Compare __comp) const noexcept {
41 if constexpr (__is_parallel_execution_policy_v<_RawExecutionPolicy> &&
42 __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
43 if (__first == __last) {
44 return __last; // nothing to do
45 }
46
47 _ForwardIterator __init = __first;
48 ++__first;
49 if (__first == __last) {
50 return __init; // the only element is the minimum
51 }
52
53 // A reduction that returns an iterator pointing to the lowest element, left bias in case of a tie
54 auto __iter_reduce = [&__comp](_ForwardIterator __lhs, _ForwardIterator __rhs) {
55 return __comp(*__rhs, *__lhs) ? __rhs : __lhs;
56 };
57
58 // Perform a parallel reduction of iterators [first+1, last) with 'first' as init.
59 return __cpu_traits<_Backend>::__transform_reduce(
60 std::move(__first),
61 std::move(__last),
62 __identity{}, // No transformations
63 std::move(__init), // Use the first iterator as the init element
64 __iter_reduce, // Reduction of 2 elements
65 [&__iter_reduce, &__comp](auto __brick_first, auto __brick_last, auto __brick_init) {
66 // Reduction of an iterage range + init element: use the serial version to find the minimum among
67 // the iterators and then reduce with the init element.
68 // Atm __transform_reduce can give empty bricks in edge cases, handle them explicitly until the contract is
69 // tightened.
70 return __brick_first == __brick_last
71 ? __brick_init
72 : __iter_reduce(__brick_init, std::min_element(__brick_first, __brick_last, __comp));
73 });
74 } else {
75 // Non-random access iterators cannot be processed in parallel, fall back to the sequential implementation.
76 return std::min_element(std::move(__first), std::move(__last), std::move(__comp));
77 }
78 }
79};
80
81} // namespace __pstl
82_LIBCPP_END_NAMESPACE_STD
83
84#endif // _LIBCPP_STD_VER >= 17
85
86_LIBCPP_POP_MACROS
87
88#endif // _LIBCPP___PSTL_CPU_ALGOS_MIN_ELEMENT_H
89