1 // -*- C++ -*-
2 //===----------------------------------------------------------------------===//
3 //
4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5 // See https://llvm.org/LICENSE.txt for license information.
6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //
8 //===----------------------------------------------------------------------===//
9
10 #ifndef _PSTL_PARALLEL_BACKEND_UTILS_H
11 #define _PSTL_PARALLEL_BACKEND_UTILS_H
12
13 #include <iterator>
14 #include <utility>
15 #include "utils.h"
16
17 #include "pstl_config.h"
18
19 _PSTL_HIDE_FROM_ABI_PUSH
20
21 namespace __pstl
22 {
23
24 namespace __utils
25 {
26
27 //! Destroy sequence [xs,xe)
28 struct __serial_destroy
29 {
30 template <typename _RandomAccessIterator>
31 void
operator__serial_destroy32 operator()(_RandomAccessIterator __zs, _RandomAccessIterator __ze)
33 {
34 typedef typename std::iterator_traits<_RandomAccessIterator>::value_type _ValueType;
35 while (__zs != __ze)
36 {
37 --__ze;
38 (*__ze).~_ValueType();
39 }
40 }
41 };
42
43 //! Merge sequences [__xs,__xe) and [__ys,__ye) to output sequence [__zs,(__xe-__xs)+(__ye-__ys)), using std::move
44 struct __serial_move_merge
45 {
46 const std::size_t _M_nmerge;
47
__serial_move_merge__serial_move_merge48 explicit __serial_move_merge(std::size_t __nmerge) : _M_nmerge(__nmerge) {}
49 template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _RandomAccessIterator3, class _Compare,
50 class _MoveValueX, class _MoveValueY, class _MoveSequenceX, class _MoveSequenceY>
51 void
operator__serial_move_merge52 operator()(_RandomAccessIterator1 __xs, _RandomAccessIterator1 __xe, _RandomAccessIterator2 __ys,
53 _RandomAccessIterator2 __ye, _RandomAccessIterator3 __zs, _Compare __comp, _MoveValueX __move_value_x,
54 _MoveValueY __move_value_y, _MoveSequenceX __move_sequence_x, _MoveSequenceY __move_sequence_y)
55 {
56 constexpr bool __same_move_val = std::is_same<_MoveValueX, _MoveValueY>::value;
57 constexpr bool __same_move_seq = std::is_same<_MoveSequenceX, _MoveSequenceY>::value;
58
59 auto __n = _M_nmerge;
60 _PSTL_ASSERT(__n > 0);
61
62 auto __nx = __xe - __xs;
63 //auto __ny = __ye - __ys;
64 _RandomAccessIterator3 __zs_beg = __zs;
65
66 if (__xs != __xe)
67 {
68 if (__ys != __ye)
69 {
70 for (;;)
71 {
72 if (__comp(*__ys, *__xs))
73 {
74 const auto __i = __zs - __zs_beg;
75 if (__i < __nx)
76 __move_value_x(__ys, __zs);
77 else
78 __move_value_y(__ys, __zs);
79 ++__zs, --__n;
80 if (++__ys == __ye)
81 {
82 break;
83 }
84 else if (__n == 0)
85 {
86 const auto __j = __zs - __zs_beg;
87 if (__same_move_seq || __j < __nx)
88 __zs = __move_sequence_x(__ys, __ye, __zs);
89 else
90 __zs = __move_sequence_y(__ys, __ye, __zs);
91 break;
92 }
93 }
94 else
95 {
96 const auto __i = __zs - __zs_beg;
97 if (__same_move_val || __i < __nx)
98 __move_value_x(__xs, __zs);
99 else
100 __move_value_y(__xs, __zs);
101 ++__zs, --__n;
102 if (++__xs == __xe)
103 {
104 const auto __j = __zs - __zs_beg;
105 if (__same_move_seq || __j < __nx)
106 __move_sequence_x(__ys, __ye, __zs);
107 else
108 __move_sequence_y(__ys, __ye, __zs);
109 return;
110 }
111 else if (__n == 0)
112 {
113 const auto __j = __zs - __zs_beg;
114 if (__same_move_seq || __j < __nx)
115 {
116 __zs = __move_sequence_x(__xs, __xe, __zs);
117 __move_sequence_x(__ys, __ye, __zs);
118 }
119 else
120 {
121 __zs = __move_sequence_y(__xs, __xe, __zs);
122 __move_sequence_y(__ys, __ye, __zs);
123 }
124 return;
125 }
126 }
127 }
128 }
129 __ys = __xs;
130 __ye = __xe;
131 }
132 const auto __i = __zs - __zs_beg;
133 if (__same_move_seq || __i < __nx)
134 __move_sequence_x(__ys, __ye, __zs);
135 else
136 __move_sequence_y(__ys, __ye, __zs);
137 }
138 };
139
140 template <typename _ForwardIterator1, typename _ForwardIterator2, typename _OutputIterator, typename _Compare,
141 typename _CopyConstructRange>
142 _OutputIterator
__set_union_construct(_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_ForwardIterator2 __last2,_OutputIterator __result,_Compare __comp,_CopyConstructRange __cc_range)143 __set_union_construct(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
144 _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp,
145 _CopyConstructRange __cc_range)
146 {
147 using _Tp = typename std::iterator_traits<_OutputIterator>::value_type;
148
149 for (; __first1 != __last1; ++__result)
150 {
151 if (__first2 == __last2)
152 return __cc_range(__first1, __last1, __result);
153 if (__comp(*__first2, *__first1))
154 {
155 ::new (std::addressof(*__result)) _Tp(*__first2);
156 ++__first2;
157 }
158 else
159 {
160 ::new (std::addressof(*__result)) _Tp(*__first1);
161 if (!__comp(*__first1, *__first2))
162 ++__first2;
163 ++__first1;
164 }
165 }
166 return __cc_range(__first2, __last2, __result);
167 }
168
169 template <typename _ForwardIterator1, typename _ForwardIterator2, typename _OutputIterator, typename _Compare>
170 _OutputIterator
__set_intersection_construct(_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_ForwardIterator2 __last2,_OutputIterator __result,_Compare __comp)171 __set_intersection_construct(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
172 _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp)
173 {
174 using _Tp = typename std::iterator_traits<_OutputIterator>::value_type;
175
176 for (; __first1 != __last1 && __first2 != __last2;)
177 {
178 if (__comp(*__first1, *__first2))
179 ++__first1;
180 else
181 {
182 if (!__comp(*__first2, *__first1))
183 {
184 ::new (std::addressof(*__result)) _Tp(*__first1);
185 ++__result;
186 ++__first1;
187 }
188 ++__first2;
189 }
190 }
191 return __result;
192 }
193
194 template <typename _ForwardIterator1, typename _ForwardIterator2, typename _OutputIterator, typename _Compare,
195 typename _CopyConstructRange>
196 _OutputIterator
__set_difference_construct(_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_ForwardIterator2 __last2,_OutputIterator __result,_Compare __comp,_CopyConstructRange __cc_range)197 __set_difference_construct(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
198 _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp,
199 _CopyConstructRange __cc_range)
200 {
201 using _Tp = typename std::iterator_traits<_OutputIterator>::value_type;
202
203 for (; __first1 != __last1;)
204 {
205 if (__first2 == __last2)
206 return __cc_range(__first1, __last1, __result);
207
208 if (__comp(*__first1, *__first2))
209 {
210 ::new (std::addressof(*__result)) _Tp(*__first1);
211 ++__result;
212 ++__first1;
213 }
214 else
215 {
216 if (!__comp(*__first2, *__first1))
217 ++__first1;
218 ++__first2;
219 }
220 }
221 return __result;
222 }
223 template <typename _ForwardIterator1, typename _ForwardIterator2, typename _OutputIterator, typename _Compare,
224 typename _CopyConstructRange>
225 _OutputIterator
__set_symmetric_difference_construct(_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_ForwardIterator2 __last2,_OutputIterator __result,_Compare __comp,_CopyConstructRange __cc_range)226 __set_symmetric_difference_construct(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
227 _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp,
228 _CopyConstructRange __cc_range)
229 {
230 using _Tp = typename std::iterator_traits<_OutputIterator>::value_type;
231
232 for (; __first1 != __last1;)
233 {
234 if (__first2 == __last2)
235 return __cc_range(__first1, __last1, __result);
236
237 if (__comp(*__first1, *__first2))
238 {
239 ::new (std::addressof(*__result)) _Tp(*__first1);
240 ++__result;
241 ++__first1;
242 }
243 else
244 {
245 if (__comp(*__first2, *__first1))
246 {
247 ::new (std::addressof(*__result)) _Tp(*__first2);
248 ++__result;
249 }
250 else
251 ++__first1;
252 ++__first2;
253 }
254 }
255 return __cc_range(__first2, __last2, __result);
256 }
257
258 } // namespace __utils
259 } // namespace __pstl
260
261 _PSTL_HIDE_FROM_ABI_POP
262
263 #endif /* _PSTL_PARALLEL_BACKEND_UTILS_H */
264