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