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