1 // -*- C++ -*-
2 // -*-===----------------------------------------------------------------------===//
3 //
4 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
5 //
6 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
7 // See https://llvm.org/LICENSE.txt for license information.
8 //
9 //===----------------------------------------------------------------------===//
10
11 #ifndef _PSTL_INTERNAL_OMP_PARALLEL_STABLE_SORT_H
12 #define _PSTL_INTERNAL_OMP_PARALLEL_STABLE_SORT_H
13
14 #include "util.h"
15 #include "parallel_merge.h"
16
17 namespace __pstl
18 {
19 namespace __omp_backend
20 {
21
22 namespace __sort_details
23 {
24 struct __move_value
25 {
26 template <typename _Iterator, typename _OutputIterator>
27 void
operator__move_value28 operator()(_Iterator __x, _OutputIterator __z) const
29 {
30 *__z = std::move(*__x);
31 }
32 };
33
34 template <typename _RandomAccessIterator, typename _OutputIterator>
35 _OutputIterator
__parallel_move_range(_RandomAccessIterator __first1,_RandomAccessIterator __last1,_OutputIterator __d_first)36 __parallel_move_range(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _OutputIterator __d_first)
37 {
38 std::size_t __size = __last1 - __first1;
39
40 // Perform serial moving of small chunks
41
42 if (__size <= __default_chunk_size)
43 {
44 return std::move(__first1, __last1, __d_first);
45 }
46
47 // Perform parallel moving of larger chunks
48 auto __policy = __pstl::__omp_backend::__chunk_partitioner(__first1, __last1);
49
50 _PSTL_PRAGMA(omp taskloop)
51 for (std::size_t __chunk = 0; __chunk < __policy.__n_chunks; ++__chunk)
52 {
53 __pstl::__omp_backend::__process_chunk(__policy, __first1, __chunk,
54 [&](auto __chunk_first, auto __chunk_last)
55 {
56 auto __chunk_offset = __chunk_first - __first1;
57 auto __output_it = __d_first + __chunk_offset;
58 std::move(__chunk_first, __chunk_last, __output_it);
59 });
60 }
61
62 return __d_first + __size;
63 }
64
65 struct __move_range
66 {
67 template <typename _RandomAccessIterator, typename _OutputIterator>
68 _OutputIterator
operator__move_range69 operator()(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _OutputIterator __d_first) const
70 {
71 return __pstl::__omp_backend::__sort_details::__parallel_move_range(__first1, __last1, __d_first);
72 }
73 };
74 } // namespace __sort_details
75
76 template <typename _RandomAccessIterator, typename _Compare, typename _LeafSort>
77 void
__parallel_stable_sort_body(_RandomAccessIterator __xs,_RandomAccessIterator __xe,_Compare __comp,_LeafSort __leaf_sort)78 __parallel_stable_sort_body(_RandomAccessIterator __xs, _RandomAccessIterator __xe, _Compare __comp,
79 _LeafSort __leaf_sort)
80 {
81 using _ValueType = typename std::iterator_traits<_RandomAccessIterator>::value_type;
82 using _VecType = typename std::vector<_ValueType>;
83 using _OutputIterator = typename _VecType::iterator;
84 using _MoveValue = typename __omp_backend::__sort_details::__move_value;
85 using _MoveRange = __omp_backend::__sort_details::__move_range;
86
87 if (__should_run_serial(__xs, __xe))
88 {
89 __leaf_sort(__xs, __xe, __comp);
90 }
91 else
92 {
93 std::size_t __size = __xe - __xs;
94 auto __mid = __xs + (__size / 2);
95 __pstl::__omp_backend::__parallel_invoke_body(
96 [&]() { __parallel_stable_sort_body(__xs, __mid, __comp, __leaf_sort); },
97 [&]() { __parallel_stable_sort_body(__mid, __xe, __comp, __leaf_sort); });
98
99 // Perform a parallel merge of the sorted ranges into __output_data.
100 _VecType __output_data(__size);
101 _MoveValue __move_value;
102 _MoveRange __move_range;
103 __utils::__serial_move_merge __merge(__size);
104 __pstl::__omp_backend::__parallel_merge_body(
105 __mid - __xs, __xe - __mid, __xs, __mid, __mid, __xe, __output_data.begin(), __comp,
106 [&__merge, &__move_value, &__move_range](_RandomAccessIterator __as, _RandomAccessIterator __ae,
107 _RandomAccessIterator __bs, _RandomAccessIterator __be,
108 _OutputIterator __cs, _Compare __comp)
109 { __merge(__as, __ae, __bs, __be, __cs, __comp, __move_value, __move_value, __move_range, __move_range); });
110
111 // Move the values from __output_data back in the original source range.
112 __pstl::__omp_backend::__sort_details::__parallel_move_range(__output_data.begin(), __output_data.end(), __xs);
113 }
114 }
115
116 template <class _ExecutionPolicy, typename _RandomAccessIterator, typename _Compare, typename _LeafSort>
117 void
118 __parallel_stable_sort(__pstl::__internal::__openmp_backend_tag __tag, _ExecutionPolicy&& /*__exec*/,
119 _RandomAccessIterator __xs, _RandomAccessIterator __xe, _Compare __comp, _LeafSort __leaf_sort,
120 std::size_t __nsort = 0)
121 {
122 auto __count = static_cast<std::size_t>(__xe - __xs);
123 if (__count <= __default_chunk_size || __nsort < __count)
124 {
125 __leaf_sort(__xs, __xe, __comp);
126 return;
127 }
128
129 // TODO: the partial sort implementation should
130 // be shared with the other backends.
131
132 if (omp_in_parallel())
133 {
134 if (__count <= __nsort)
135 {
136 __pstl::__omp_backend::__parallel_stable_sort_body(__xs, __xe, __comp, __leaf_sort);
137 }
138 else
139 {
140 __pstl::__omp_backend::__parallel_stable_partial_sort(__tag, __xs, __xe, __comp, __leaf_sort, __nsort);
141 }
142 }
143 else
144 {
145 _PSTL_PRAGMA(omp parallel)
146 _PSTL_PRAGMA(omp single nowait)
147 if (__count <= __nsort)
148 {
149 __pstl::__omp_backend::__parallel_stable_sort_body(__xs, __xe, __comp, __leaf_sort);
150 }
151 else
152 {
153 __pstl::__omp_backend::__parallel_stable_partial_sort(__tag, __xs, __xe, __comp, __leaf_sort, __nsort);
154 }
155 }
156 }
157
158 } // namespace __omp_backend
159 } // namespace __pstl
160 #endif // _PSTL_INTERNAL_OMP_PARALLEL_STABLE_SORT_H
161