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