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_MINMAX_ELEMENT_H
10#define _LIBCPP___PSTL_CPU_ALGOS_MINMAX_ELEMENT_H
11
12#include <__algorithm/minmax_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#include <__utility/pair.h>
24
25#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
26# pragma GCC system_header
27#endif
28
29_LIBCPP_PUSH_MACROS
30#include <__undef_macros>
31
32#if _LIBCPP_STD_VER >= 17
33
34_LIBCPP_BEGIN_NAMESPACE_STD
35namespace __pstl {
36
37template <class _Backend, class _RawExecutionPolicy>
38struct __cpu_parallel_minmax_element {
39 template <class _Policy, class _ForwardIterator, class _Compare>
40 _LIBCPP_HIDE_FROM_ABI optional<pair<_ForwardIterator, _ForwardIterator>>
41 operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Compare __comp) const noexcept {
42 if constexpr (__is_parallel_execution_policy_v<_RawExecutionPolicy> &&
43 __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
44 using _IterPair = pair<_ForwardIterator, _ForwardIterator>;
45
46 if (__first == __last) {
47 return _IterPair{__last, __last}; // Nothing to do
48 }
49
50 _IterPair __init = {__first, __first};
51 ++__first;
52 if (__first == __last) {
53 return __init; // The only element is both the minimum and the maximum
54 }
55
56 // A reduction that returns a pair of iterators pointing to the minimum and maximum elements.
57 // In a case of a tie the minimum iterators are biased left and the maximum iterators are biased right.
58 auto __iter_reduce = [&__comp](_IterPair __lhs, _IterPair __rhs) {
59 return _IterPair{__comp(*__rhs.first, *__lhs.first) ? __rhs.first : __lhs.first,
60 __comp(*__rhs.second, *__lhs.second) ? __lhs.second : __rhs.second};
61 };
62
63 // Perform a parallel reduction of iterators [first+1, last) with {first, first} as init.
64 return __cpu_traits<_Backend>::__transform_reduce(
65 std::move(__first),
66 std::move(__last),
67 [](auto __it) { return _IterPair{__it, __it}; }, // Transform an iterator into an iterator pair
68 std::move(__init), // Use the pair of first iterators as the init element
69 __iter_reduce, // Reduction of 2 minmax pairs
70 [&__iter_reduce, &__comp](auto __brick_first, auto __brick_last, auto __brick_init) {
71 // Reduction of an iterator range + init element: use the serial version to find the minmax among
72 // the iterators and then reduce it with the init element.
73 // Atm __transform_reduce can give empty bricks in edge cases, handle them explicitly until the contract is
74 // tightened.
75 return __brick_first == __brick_last
76 ? __brick_init
77 : __iter_reduce(__brick_init, std::minmax_element(__brick_first, __brick_last, __comp));
78 });
79 } else {
80 // Non-random access iterators cannot be processed in parallel, fall back to the sequential implementation.
81 return std::minmax_element(std::move(__first), std::move(__last), std::move(__comp));
82 }
83 }
84};
85
86} // namespace __pstl
87_LIBCPP_END_NAMESPACE_STD
88
89#endif // _LIBCPP_STD_VER >= 17
90
91_LIBCPP_POP_MACROS
92
93#endif // _LIBCPP___PSTL_CPU_ALGOS_MINMAX_ELEMENT_H
94