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_ALGORITHM_IMPL_H
11 #define _PSTL_ALGORITHM_IMPL_H
12
13 #include <__assert>
14 #include <__config>
15 #include <algorithm>
16 #include <functional>
17 #include <iterator>
18 #include <type_traits>
19 #include <utility>
20
21 #include "execution_impl.h"
22 #include "memory_impl.h"
23 #include "parallel_backend.h"
24 #include "parallel_backend_utils.h"
25 #include "parallel_impl.h"
26 #include "unseq_backend_simd.h"
27
28 namespace __pstl {
29 namespace __internal {
30
31 // [alg.foreach]
32 // for_each_n with no policy
33
34 template <class _ForwardIterator, class _Size, class _Function>
__for_each_n_it_serial(_ForwardIterator __first,_Size __n,_Function __f)35 _ForwardIterator __for_each_n_it_serial(_ForwardIterator __first, _Size __n, _Function __f) {
36 for (; __n > 0; ++__first, --__n)
37 __f(__first);
38 return __first;
39 }
40
41 //------------------------------------------------------------------------
42 // walk1 (pseudo)
43 //
44 // walk1 evaluates f(x) for each dereferenced value x drawn from [first,last)
45 //------------------------------------------------------------------------
46 template <class _ForwardIterator, class _Function>
__brick_walk1(_ForwardIterator __first,_ForwardIterator __last,_Function __f,std::false_type)47 void __brick_walk1(
48 _ForwardIterator __first, _ForwardIterator __last, _Function __f, /*vector=*/std::false_type) noexcept {
49 std::for_each(__first, __last, __f);
50 }
51
52 template <class _RandomAccessIterator, class _Function>
__brick_walk1(_RandomAccessIterator __first,_RandomAccessIterator __last,_Function __f,std::true_type)53 void __brick_walk1(_RandomAccessIterator __first,
54 _RandomAccessIterator __last,
55 _Function __f,
56 /*vector=*/std::true_type) noexcept {
57 __unseq_backend::__simd_walk_1(__first, __last - __first, __f);
58 }
59
60 template <class _Tag, class _ExecutionPolicy, class _ForwardIterator, class _Function>
__pattern_walk1(_Tag,_ExecutionPolicy &&,_ForwardIterator __first,_ForwardIterator __last,_Function __f)61 void __pattern_walk1(
62 _Tag, _ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterator __last, _Function __f) noexcept {
63 __internal::__brick_walk1(__first, __last, __f, typename _Tag::__is_vector{});
64 }
65
66 template <class _IsVector, class _ExecutionPolicy, class _RandomAccessIterator, class _Function>
__pattern_walk1(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator __first,_RandomAccessIterator __last,_Function __f)67 void __pattern_walk1(__parallel_tag<_IsVector> __tag,
68 _ExecutionPolicy&& __exec,
69 _RandomAccessIterator __first,
70 _RandomAccessIterator __last,
71 _Function __f) {
72 using __backend_tag = typename decltype(__tag)::__backend_tag;
73
74 __internal::__except_handler([&]() {
75 __par_backend::__parallel_for(
76 __backend_tag{},
77 std::forward<_ExecutionPolicy>(__exec),
78 __first,
79 __last,
80 [__f](_RandomAccessIterator __i, _RandomAccessIterator __j) {
81 __internal::__brick_walk1(__i, __j, __f, _IsVector{});
82 });
83 });
84 }
85
86 template <class _Tag, class _ExecutionPolicy, class _ForwardIterator, class _Brick>
__pattern_walk_brick(_Tag,_ExecutionPolicy &&,_ForwardIterator __first,_ForwardIterator __last,_Brick __brick)87 void __pattern_walk_brick(
88 _Tag, _ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterator __last, _Brick __brick) noexcept {
89 __brick(__first, __last);
90 }
91
92 template <class _IsVector, class _ExecutionPolicy, class _RandomAccessIterator, class _Brick>
__pattern_walk_brick(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator __first,_RandomAccessIterator __last,_Brick __brick)93 void __pattern_walk_brick(
94 __parallel_tag<_IsVector> __tag,
95 _ExecutionPolicy&& __exec,
96 _RandomAccessIterator __first,
97 _RandomAccessIterator __last,
98 _Brick __brick) {
99 using __backend_tag = typename decltype(__tag)::__backend_tag;
100
101 __internal::__except_handler([&]() {
102 __par_backend::__parallel_for(
103 __backend_tag{},
104 std::forward<_ExecutionPolicy>(__exec),
105 __first,
106 __last,
107 [__brick](_RandomAccessIterator __i, _RandomAccessIterator __j) { __brick(__i, __j); });
108 });
109 }
110
111 //------------------------------------------------------------------------
112 // walk1_n
113 //------------------------------------------------------------------------
114 template <class _ForwardIterator, class _Size, class _Function>
__brick_walk1_n(_ForwardIterator __first,_Size __n,_Function __f,std::false_type)115 _ForwardIterator __brick_walk1_n(_ForwardIterator __first, _Size __n, _Function __f, /*_IsVectorTag=*/std::false_type) {
116 return __internal::__for_each_n_it_serial(__first, __n, [&__f](_ForwardIterator __it) {
117 __f(*__it);
118 }); // calling serial version
119 }
120
121 template <class _RandomAccessIterator, class _DifferenceType, class _Function>
122 _RandomAccessIterator
__brick_walk1_n(_RandomAccessIterator __first,_DifferenceType __n,_Function __f,std::true_type)123 __brick_walk1_n(_RandomAccessIterator __first,
124 _DifferenceType __n,
125 _Function __f,
126 /*vectorTag=*/std::true_type) noexcept {
127 return __unseq_backend::__simd_walk_1(__first, __n, __f);
128 }
129
130 template <class _Tag, class _ExecutionPolicy, class _ForwardIterator, class _Size, class _Function>
131 _ForwardIterator
__pattern_walk1_n(_Tag,_ExecutionPolicy &&,_ForwardIterator __first,_Size __n,_Function __f)132 __pattern_walk1_n(_Tag, _ExecutionPolicy&&, _ForwardIterator __first, _Size __n, _Function __f) noexcept {
133 return __internal::__brick_walk1_n(__first, __n, __f, typename _Tag::__is_vector{});
134 }
135
136 template <class _IsVector, class _ExecutionPolicy, class _RandomAccessIterator, class _Size, class _Function>
__pattern_walk1_n(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator __first,_Size __n,_Function __f)137 _RandomAccessIterator __pattern_walk1_n(
138 __parallel_tag<_IsVector> __tag,
139 _ExecutionPolicy&& __exec,
140 _RandomAccessIterator __first,
141 _Size __n,
142 _Function __f) {
143 __internal::__pattern_walk1(__tag, std::forward<_ExecutionPolicy>(__exec), __first, __first + __n, __f);
144
145 return __first + __n;
146 }
147
148 template <class _Tag, class _ExecutionPolicy, class _ForwardIterator, class _Size, class _Brick>
149 _ForwardIterator
__pattern_walk_brick_n(_Tag,_ExecutionPolicy &&,_ForwardIterator __first,_Size __n,_Brick __brick)150 __pattern_walk_brick_n(_Tag, _ExecutionPolicy&&, _ForwardIterator __first, _Size __n, _Brick __brick) noexcept {
151 return __brick(__first, __n);
152 }
153
154 template <class _IsVector, class _ExecutionPolicy, class _RandomAccessIterator, class _Size, class _Brick>
__pattern_walk_brick_n(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator __first,_Size __n,_Brick __brick)155 _RandomAccessIterator __pattern_walk_brick_n(
156 __parallel_tag<_IsVector> __tag,
157 _ExecutionPolicy&& __exec,
158 _RandomAccessIterator __first,
159 _Size __n,
160 _Brick __brick) {
161 using __backend_tag = typename decltype(__tag)::__backend_tag;
162
163 return __internal::__except_handler([&]() {
164 __par_backend::__parallel_for(
165 __backend_tag{},
166 std::forward<_ExecutionPolicy>(__exec),
167 __first,
168 __first + __n,
169 [__brick](_RandomAccessIterator __i, _RandomAccessIterator __j) { __brick(__i, __j - __i); });
170 return __first + __n;
171 });
172 }
173
174 //------------------------------------------------------------------------
175 // walk2 (pseudo)
176 //
177 // walk2 evaluates f(x,y) for deferenced values (x,y) drawn from [first1,last1) and [first2,...)
178 //------------------------------------------------------------------------
179 template <class _ForwardIterator1, class _ForwardIterator2, class _Function>
180 _ForwardIterator2
__brick_walk2(_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_Function __f,std::false_type)181 __brick_walk2(_ForwardIterator1 __first1,
182 _ForwardIterator1 __last1,
183 _ForwardIterator2 __first2,
184 _Function __f,
185 /*vector=*/std::false_type) noexcept {
186 for (; __first1 != __last1; ++__first1, ++__first2)
187 __f(*__first1, *__first2);
188 return __first2;
189 }
190
191 template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _Function>
192 _RandomAccessIterator2
__brick_walk2(_RandomAccessIterator1 __first1,_RandomAccessIterator1 __last1,_RandomAccessIterator2 __first2,_Function __f,std::true_type)193 __brick_walk2(_RandomAccessIterator1 __first1,
194 _RandomAccessIterator1 __last1,
195 _RandomAccessIterator2 __first2,
196 _Function __f,
197 /*vector=*/std::true_type) noexcept {
198 return __unseq_backend::__simd_walk_2(__first1, __last1 - __first1, __first2, __f);
199 }
200
201 template <class _ForwardIterator1, class _Size, class _ForwardIterator2, class _Function>
__brick_walk2_n(_ForwardIterator1 __first1,_Size __n,_ForwardIterator2 __first2,_Function __f,std::false_type)202 _ForwardIterator2 __brick_walk2_n(
203 _ForwardIterator1 __first1,
204 _Size __n,
205 _ForwardIterator2 __first2,
206 _Function __f,
207 /*vector=*/std::false_type) noexcept {
208 for (; __n > 0; --__n, ++__first1, ++__first2)
209 __f(*__first1, *__first2);
210 return __first2;
211 }
212
213 template <class _RandomAccessIterator1, class _Size, class _RandomAccessIterator2, class _Function>
__brick_walk2_n(_RandomAccessIterator1 __first1,_Size __n,_RandomAccessIterator2 __first2,_Function __f,std::true_type)214 _RandomAccessIterator2 __brick_walk2_n(
215 _RandomAccessIterator1 __first1,
216 _Size __n,
217 _RandomAccessIterator2 __first2,
218 _Function __f,
219 /*vector=*/std::true_type) noexcept {
220 return __unseq_backend::__simd_walk_2(__first1, __n, __first2, __f);
221 }
222
223 template <class _Tag, class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Function>
__pattern_walk2(_Tag,_ExecutionPolicy &&,_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_Function __f)224 _ForwardIterator2 __pattern_walk2(
225 _Tag,
226 _ExecutionPolicy&&,
227 _ForwardIterator1 __first1,
228 _ForwardIterator1 __last1,
229 _ForwardIterator2 __first2,
230 _Function __f) noexcept {
231 return __internal::__brick_walk2(__first1, __last1, __first2, __f, typename _Tag::__is_vector{});
232 }
233
234 template <class _IsVector,
235 class _ExecutionPolicy,
236 class _RandomAccessIterator1,
237 class _RandomAccessIterator2,
238 class _Function>
__pattern_walk2(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator1 __first1,_RandomAccessIterator1 __last1,_RandomAccessIterator2 __first2,_Function __f)239 _RandomAccessIterator2 __pattern_walk2(
240 __parallel_tag<_IsVector> __tag,
241 _ExecutionPolicy&& __exec,
242 _RandomAccessIterator1 __first1,
243 _RandomAccessIterator1 __last1,
244 _RandomAccessIterator2 __first2,
245 _Function __f) {
246 using __backend_tag = typename decltype(__tag)::__backend_tag;
247
248 return __internal::__except_handler([&]() {
249 __par_backend::__parallel_for(
250 __backend_tag{},
251 std::forward<_ExecutionPolicy>(__exec),
252 __first1,
253 __last1,
254 [__f, __first1, __first2](_RandomAccessIterator1 __i, _RandomAccessIterator1 __j) {
255 __internal::__brick_walk2(__i, __j, __first2 + (__i - __first1), __f, _IsVector{});
256 });
257 return __first2 + (__last1 - __first1);
258 });
259 }
260
261 template <class _Tag,
262 class _ExecutionPolicy,
263 class _ForwardIterator1,
264 class _Size,
265 class _ForwardIterator2,
266 class _Function>
__pattern_walk2_n(_Tag,_ExecutionPolicy &&,_ForwardIterator1 __first1,_Size __n,_ForwardIterator2 __first2,_Function __f)267 _ForwardIterator2 __pattern_walk2_n(
268 _Tag,
269 _ExecutionPolicy&&,
270 _ForwardIterator1 __first1,
271 _Size __n,
272 _ForwardIterator2 __first2,
273 _Function __f) noexcept {
274 return __internal::__brick_walk2_n(__first1, __n, __first2, __f, typename _Tag::__is_vector{});
275 }
276
277 template <class _IsVector,
278 class _ExecutionPolicy,
279 class _RandomAccessIterator1,
280 class _Size,
281 class _RandomAccessIterator2,
282 class _Function>
__pattern_walk2_n(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator1 __first1,_Size __n,_RandomAccessIterator2 __first2,_Function __f)283 _RandomAccessIterator2 __pattern_walk2_n(
284 __parallel_tag<_IsVector> __tag,
285 _ExecutionPolicy&& __exec,
286 _RandomAccessIterator1 __first1,
287 _Size __n,
288 _RandomAccessIterator2 __first2,
289 _Function __f) {
290 return __internal::__pattern_walk2(
291 __tag, std::forward<_ExecutionPolicy>(__exec), __first1, __first1 + __n, __first2, __f);
292 }
293
294 template <class _Tag, class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Brick>
__pattern_walk2_brick(_Tag,_ExecutionPolicy &&,_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_Brick __brick)295 _ForwardIterator2 __pattern_walk2_brick(
296 _Tag,
297 _ExecutionPolicy&&,
298 _ForwardIterator1 __first1,
299 _ForwardIterator1 __last1,
300 _ForwardIterator2 __first2,
301 _Brick __brick) noexcept {
302 return __brick(__first1, __last1, __first2);
303 }
304
305 template <class _IsVector,
306 class _ExecutionPolicy,
307 class _RandomAccessIterator1,
308 class _RandomAccessIterator2,
309 class _Brick>
__pattern_walk2_brick(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator1 __first1,_RandomAccessIterator1 __last1,_RandomAccessIterator2 __first2,_Brick __brick)310 _RandomAccessIterator2 __pattern_walk2_brick(
311 __parallel_tag<_IsVector> __tag,
312 _ExecutionPolicy&& __exec,
313 _RandomAccessIterator1 __first1,
314 _RandomAccessIterator1 __last1,
315 _RandomAccessIterator2 __first2,
316 _Brick __brick) {
317 using __backend_tag = typename decltype(__tag)::__backend_tag;
318
319 return __internal::__except_handler([&]() {
320 __par_backend::__parallel_for(
321 __backend_tag{},
322 std::forward<_ExecutionPolicy>(__exec),
323 __first1,
324 __last1,
325 [__first1, __first2, __brick](_RandomAccessIterator1 __i, _RandomAccessIterator1 __j) {
326 __brick(__i, __j, __first2 + (__i - __first1));
327 });
328 return __first2 + (__last1 - __first1);
329 });
330 }
331
332 template <class _Tag,
333 class _ExecutionPolicy,
334 class _ForwardIterator1,
335 class _Size,
336 class _ForwardIterator2,
337 class _Brick>
__pattern_walk2_brick_n(_Tag,_ExecutionPolicy &&,_ForwardIterator1 __first1,_Size __n,_ForwardIterator2 __first2,_Brick __brick)338 _ForwardIterator2 __pattern_walk2_brick_n(
339 _Tag,
340 _ExecutionPolicy&&,
341 _ForwardIterator1 __first1,
342 _Size __n,
343 _ForwardIterator2 __first2,
344 _Brick __brick) noexcept {
345 return __brick(__first1, __n, __first2);
346 }
347
348 template <class _IsVector,
349 class _ExecutionPolicy,
350 class _RandomAccessIterator1,
351 class _Size,
352 class _RandomAccessIterator2,
353 class _Brick>
__pattern_walk2_brick_n(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator1 __first1,_Size __n,_RandomAccessIterator2 __first2,_Brick __brick)354 _RandomAccessIterator2 __pattern_walk2_brick_n(
355 __parallel_tag<_IsVector> __tag,
356 _ExecutionPolicy&& __exec,
357 _RandomAccessIterator1 __first1,
358 _Size __n,
359 _RandomAccessIterator2 __first2,
360 _Brick __brick) {
361 using __backend_tag = typename decltype(__tag)::__backend_tag;
362
363 return __internal::__except_handler([&]() {
364 __par_backend::__parallel_for(
365 __backend_tag{},
366 std::forward<_ExecutionPolicy>(__exec),
367 __first1,
368 __first1 + __n,
369 [__first1, __first2, __brick](_RandomAccessIterator1 __i, _RandomAccessIterator1 __j) {
370 __brick(__i, __j - __i, __first2 + (__i - __first1));
371 });
372 return __first2 + __n;
373 });
374 }
375
376 //------------------------------------------------------------------------
377 // walk3 (pseudo)
378 //
379 // walk3 evaluates f(x,y,z) for (x,y,z) drawn from [first1,last1), [first2,...), [first3,...)
380 //------------------------------------------------------------------------
381 template <class _ForwardIterator1, class _ForwardIterator2, class _ForwardIterator3, class _Function>
__brick_walk3(_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_ForwardIterator3 __first3,_Function __f,std::false_type)382 _ForwardIterator3 __brick_walk3(
383 _ForwardIterator1 __first1,
384 _ForwardIterator1 __last1,
385 _ForwardIterator2 __first2,
386 _ForwardIterator3 __first3,
387 _Function __f,
388 /*vector=*/std::false_type) noexcept {
389 for (; __first1 != __last1; ++__first1, ++__first2, ++__first3)
390 __f(*__first1, *__first2, *__first3);
391 return __first3;
392 }
393
394 template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _RandomAccessIterator3, class _Function>
__brick_walk3(_RandomAccessIterator1 __first1,_RandomAccessIterator1 __last1,_RandomAccessIterator2 __first2,_RandomAccessIterator3 __first3,_Function __f,std::true_type)395 _RandomAccessIterator3 __brick_walk3(
396 _RandomAccessIterator1 __first1,
397 _RandomAccessIterator1 __last1,
398 _RandomAccessIterator2 __first2,
399 _RandomAccessIterator3 __first3,
400 _Function __f,
401 /*vector=*/std::true_type) noexcept {
402 return __unseq_backend::__simd_walk_3(__first1, __last1 - __first1, __first2, __first3, __f);
403 }
404
405 template <class _Tag,
406 class _ExecutionPolicy,
407 class _ForwardIterator1,
408 class _ForwardIterator2,
409 class _ForwardIterator3,
410 class _Function>
__pattern_walk3(_Tag,_ExecutionPolicy &&,_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_ForwardIterator3 __first3,_Function __f)411 _ForwardIterator3 __pattern_walk3(
412 _Tag,
413 _ExecutionPolicy&&,
414 _ForwardIterator1 __first1,
415 _ForwardIterator1 __last1,
416 _ForwardIterator2 __first2,
417 _ForwardIterator3 __first3,
418 _Function __f) noexcept {
419 return __internal::__brick_walk3(__first1, __last1, __first2, __first3, __f, typename _Tag::__is_vector{});
420 }
421
422 template <class _IsVector,
423 class _ExecutionPolicy,
424 class _RandomAccessIterator1,
425 class _RandomAccessIterator2,
426 class _RandomAccessIterator3,
427 class _Function>
__pattern_walk3(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator1 __first1,_RandomAccessIterator1 __last1,_RandomAccessIterator2 __first2,_RandomAccessIterator3 __first3,_Function __f)428 _RandomAccessIterator3 __pattern_walk3(
429 __parallel_tag<_IsVector> __tag,
430 _ExecutionPolicy&& __exec,
431 _RandomAccessIterator1 __first1,
432 _RandomAccessIterator1 __last1,
433 _RandomAccessIterator2 __first2,
434 _RandomAccessIterator3 __first3,
435 _Function __f) {
436 using __backend_tag = typename decltype(__tag)::__backend_tag;
437
438 return __internal::__except_handler([&]() {
439 __par_backend::__parallel_for(
440 __backend_tag{},
441 std::forward<_ExecutionPolicy>(__exec),
442 __first1,
443 __last1,
444 [__f, __first1, __first2, __first3](_RandomAccessIterator1 __i, _RandomAccessIterator1 __j) {
445 __internal::__brick_walk3(
446 __i, __j, __first2 + (__i - __first1), __first3 + (__i - __first1), __f, _IsVector{});
447 });
448 return __first3 + (__last1 - __first1);
449 });
450 }
451
452 //------------------------------------------------------------------------
453 // equal
454 //------------------------------------------------------------------------
455
456 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
__brick_equal(_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_ForwardIterator2 __last2,_BinaryPredicate __p,std::false_type)457 bool __brick_equal(_ForwardIterator1 __first1,
458 _ForwardIterator1 __last1,
459 _ForwardIterator2 __first2,
460 _ForwardIterator2 __last2,
461 _BinaryPredicate __p,
462 /* IsVector = */ std::false_type) noexcept {
463 return std::equal(__first1, __last1, __first2, __last2, __p);
464 }
465
466 template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _BinaryPredicate>
__brick_equal(_RandomAccessIterator1 __first1,_RandomAccessIterator1 __last1,_RandomAccessIterator2 __first2,_RandomAccessIterator2 __last2,_BinaryPredicate __p,std::true_type)467 bool __brick_equal(_RandomAccessIterator1 __first1,
468 _RandomAccessIterator1 __last1,
469 _RandomAccessIterator2 __first2,
470 _RandomAccessIterator2 __last2,
471 _BinaryPredicate __p,
472 /* is_vector = */ std::true_type) noexcept {
473 if (__last1 - __first1 != __last2 - __first2)
474 return false;
475
476 return __unseq_backend::__simd_first(__first1, __last1 - __first1, __first2, std::not_fn(__p)).first == __last1;
477 }
478
479 template <class _Tag, class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
__pattern_equal(_Tag,_ExecutionPolicy &&,_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_ForwardIterator2 __last2,_BinaryPredicate __p)480 bool __pattern_equal(
481 _Tag,
482 _ExecutionPolicy&&,
483 _ForwardIterator1 __first1,
484 _ForwardIterator1 __last1,
485 _ForwardIterator2 __first2,
486 _ForwardIterator2 __last2,
487 _BinaryPredicate __p) noexcept {
488 return __internal::__brick_equal(__first1, __last1, __first2, __last2, __p, typename _Tag::__is_vector{});
489 }
490
491 template <class _IsVector,
492 class _ExecutionPolicy,
493 class _RandomAccessIterator1,
494 class _RandomAccessIterator2,
495 class _BinaryPredicate>
__pattern_equal(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator1 __first1,_RandomAccessIterator1 __last1,_RandomAccessIterator2 __first2,_RandomAccessIterator2 __last2,_BinaryPredicate __p)496 bool __pattern_equal(
497 __parallel_tag<_IsVector> __tag,
498 _ExecutionPolicy&& __exec,
499 _RandomAccessIterator1 __first1,
500 _RandomAccessIterator1 __last1,
501 _RandomAccessIterator2 __first2,
502 _RandomAccessIterator2 __last2,
503 _BinaryPredicate __p) {
504 using __backend_tag = typename decltype(__tag)::__backend_tag;
505
506 if (__last1 - __first1 != __last2 - __first2)
507 return false;
508
509 return __internal::__except_handler([&]() {
510 return !__internal::__parallel_or(
511 __backend_tag{},
512 std::forward<_ExecutionPolicy>(__exec),
513 __first1,
514 __last1,
515 [__first1, __first2, __p](_RandomAccessIterator1 __i, _RandomAccessIterator1 __j) {
516 return !__internal::__brick_equal(
517 __i, __j, __first2 + (__i - __first1), __first2 + (__j - __first1), __p, _IsVector{});
518 });
519 });
520 }
521
522 //------------------------------------------------------------------------
523 // equal version for sequences with equal length
524 //------------------------------------------------------------------------
525
526 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
__brick_equal(_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_BinaryPredicate __p,std::false_type)527 bool __brick_equal(_ForwardIterator1 __first1,
528 _ForwardIterator1 __last1,
529 _ForwardIterator2 __first2,
530 _BinaryPredicate __p,
531 /* IsVector = */ std::false_type) noexcept {
532 return std::equal(__first1, __last1, __first2, __p);
533 }
534
535 template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _BinaryPredicate>
__brick_equal(_RandomAccessIterator1 __first1,_RandomAccessIterator1 __last1,_RandomAccessIterator2 __first2,_BinaryPredicate __p,std::true_type)536 bool __brick_equal(_RandomAccessIterator1 __first1,
537 _RandomAccessIterator1 __last1,
538 _RandomAccessIterator2 __first2,
539 _BinaryPredicate __p,
540 /* is_vector = */ std::true_type) noexcept {
541 return __unseq_backend::__simd_first(__first1, __last1 - __first1, __first2, std::not_fn(__p)).first == __last1;
542 }
543
544 template <class _Tag, class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
__pattern_equal(_Tag,_ExecutionPolicy &&,_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_BinaryPredicate __p)545 bool __pattern_equal(
546 _Tag,
547 _ExecutionPolicy&&,
548 _ForwardIterator1 __first1,
549 _ForwardIterator1 __last1,
550 _ForwardIterator2 __first2,
551 _BinaryPredicate __p) noexcept {
552 return __internal::__brick_equal(__first1, __last1, __first2, __p, typename _Tag::__is_vector{});
553 }
554
555 template <class _IsVector,
556 class _ExecutionPolicy,
557 class _RandomAccessIterator1,
558 class _RandomAccessIterator2,
559 class _BinaryPredicate>
__pattern_equal(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator1 __first1,_RandomAccessIterator1 __last1,_RandomAccessIterator2 __first2,_BinaryPredicate __p)560 bool __pattern_equal(
561 __parallel_tag<_IsVector> __tag,
562 _ExecutionPolicy&& __exec,
563 _RandomAccessIterator1 __first1,
564 _RandomAccessIterator1 __last1,
565 _RandomAccessIterator2 __first2,
566 _BinaryPredicate __p) {
567 using __backend_tag = typename decltype(__tag)::__backend_tag;
568
569 return __internal::__except_handler([&]() {
570 return !__internal::__parallel_or(
571 __backend_tag{},
572 std::forward<_ExecutionPolicy>(__exec),
573 __first1,
574 __last1,
575 [__first1, __first2, __p](_RandomAccessIterator1 __i, _RandomAccessIterator1 __j) {
576 return !__internal::__brick_equal(__i, __j, __first2 + (__i - __first1), __p, _IsVector{});
577 });
578 });
579 }
580
581 //------------------------------------------------------------------------
582 // find_end
583 //------------------------------------------------------------------------
584
585 // find the first occurrence of the subsequence [s_first, s_last)
586 // or the last occurrence of the subsequence in the range [first, last)
587 // b_first determines what occurrence we want to find (first or last)
588 template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _BinaryPredicate, class _IsVector>
__find_subrange(_RandomAccessIterator1 __first,_RandomAccessIterator1 __last,_RandomAccessIterator1 __global_last,_RandomAccessIterator2 __s_first,_RandomAccessIterator2 __s_last,_BinaryPredicate __pred,bool __b_first,_IsVector __is_vector)589 _RandomAccessIterator1 __find_subrange(
590 _RandomAccessIterator1 __first,
591 _RandomAccessIterator1 __last,
592 _RandomAccessIterator1 __global_last,
593 _RandomAccessIterator2 __s_first,
594 _RandomAccessIterator2 __s_last,
595 _BinaryPredicate __pred,
596 bool __b_first,
597 _IsVector __is_vector) noexcept {
598 typedef typename std::iterator_traits<_RandomAccessIterator2>::value_type _ValueType;
599 auto __n2 = __s_last - __s_first;
600 if (__n2 < 1) {
601 return __b_first ? __first : __last;
602 }
603
604 auto __n1 = __global_last - __first;
605 if (__n1 < __n2) {
606 return __last;
607 }
608
609 auto __cur = __last;
610 while (__first != __last && (__global_last - __first >= __n2)) {
611 // find position of *s_first in [first, last) (it can be start of subsequence)
612 __first = __internal::__brick_find_if(
613 __first, __last, __equal_value_by_pred<_ValueType, _BinaryPredicate>(*__s_first, __pred), __is_vector);
614
615 // if position that was found previously is the start of subsequence
616 // then we can exit the loop (b_first == true) or keep the position
617 // (b_first == false)
618 if (__first != __last && (__global_last - __first >= __n2) &&
619 __internal::__brick_equal(__s_first + 1, __s_last, __first + 1, __pred, __is_vector)) {
620 if (__b_first) {
621 return __first;
622 } else {
623 __cur = __first;
624 }
625 } else if (__first == __last) {
626 break;
627 } else {
628 }
629
630 // in case of b_first == false we try to find new start position
631 // for the next subsequence
632 ++__first;
633 }
634 return __cur;
635 }
636
637 template <class _RandomAccessIterator, class _Size, class _Tp, class _BinaryPredicate, class _IsVector>
__find_subrange(_RandomAccessIterator __first,_RandomAccessIterator __last,_RandomAccessIterator __global_last,_Size __count,const _Tp & __value,_BinaryPredicate __pred,_IsVector __is_vector)638 _RandomAccessIterator __find_subrange(
639 _RandomAccessIterator __first,
640 _RandomAccessIterator __last,
641 _RandomAccessIterator __global_last,
642 _Size __count,
643 const _Tp& __value,
644 _BinaryPredicate __pred,
645 _IsVector __is_vector) noexcept {
646 if (static_cast<_Size>(__global_last - __first) < __count || __count < 1) {
647 return __last; // According to the standard last shall be returned when count < 1
648 }
649
650 auto __unary_pred = __equal_value_by_pred<_Tp, _BinaryPredicate>(__value, __pred);
651 while (__first != __last && (static_cast<_Size>(__global_last - __first) >= __count)) {
652 __first = __internal::__brick_find_if(__first, __last, __unary_pred, __is_vector);
653
654 // check that all of elements in [first+1, first+count) equal to value
655 if (__first != __last && (static_cast<_Size>(__global_last - __first) >= __count) &&
656 !__internal::__brick_any_of(__first + 1, __first + __count, std::not_fn(__unary_pred), __is_vector)) {
657 return __first;
658 } else if (__first == __last) {
659 break;
660 } else {
661 ++__first;
662 }
663 }
664 return __last;
665 }
666
667 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
__brick_find_end(_ForwardIterator1 __first,_ForwardIterator1 __last,_ForwardIterator2 __s_first,_ForwardIterator2 __s_last,_BinaryPredicate __pred,std::false_type)668 _ForwardIterator1 __brick_find_end(
669 _ForwardIterator1 __first,
670 _ForwardIterator1 __last,
671 _ForwardIterator2 __s_first,
672 _ForwardIterator2 __s_last,
673 _BinaryPredicate __pred,
674 /*__is_vector=*/std::false_type) noexcept {
675 return std::find_end(__first, __last, __s_first, __s_last, __pred);
676 }
677
678 template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _BinaryPredicate>
__brick_find_end(_RandomAccessIterator1 __first,_RandomAccessIterator1 __last,_RandomAccessIterator2 __s_first,_RandomAccessIterator2 __s_last,_BinaryPredicate __pred,std::true_type)679 _RandomAccessIterator1 __brick_find_end(
680 _RandomAccessIterator1 __first,
681 _RandomAccessIterator1 __last,
682 _RandomAccessIterator2 __s_first,
683 _RandomAccessIterator2 __s_last,
684 _BinaryPredicate __pred,
685 /*__is_vector=*/std::true_type) noexcept {
686 return __find_subrange(__first, __last, __last, __s_first, __s_last, __pred, false, std::true_type());
687 }
688
689 template <class _Tag, class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
__pattern_find_end(_Tag,_ExecutionPolicy &&,_ForwardIterator1 __first,_ForwardIterator1 __last,_ForwardIterator2 __s_first,_ForwardIterator2 __s_last,_BinaryPredicate __pred)690 _ForwardIterator1 __pattern_find_end(
691 _Tag,
692 _ExecutionPolicy&&,
693 _ForwardIterator1 __first,
694 _ForwardIterator1 __last,
695 _ForwardIterator2 __s_first,
696 _ForwardIterator2 __s_last,
697 _BinaryPredicate __pred) noexcept {
698 return __internal::__brick_find_end(__first, __last, __s_first, __s_last, __pred, typename _Tag::__is_vector{});
699 }
700
701 template <class _IsVector,
702 class _ExecutionPolicy,
703 class _RandomAccessIterator1,
704 class _RandomAccessIterator2,
705 class _BinaryPredicate>
__pattern_find_end(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator1 __first,_RandomAccessIterator1 __last,_RandomAccessIterator2 __s_first,_RandomAccessIterator2 __s_last,_BinaryPredicate __pred)706 _RandomAccessIterator1 __pattern_find_end(
707 __parallel_tag<_IsVector> __tag,
708 _ExecutionPolicy&& __exec,
709 _RandomAccessIterator1 __first,
710 _RandomAccessIterator1 __last,
711 _RandomAccessIterator2 __s_first,
712 _RandomAccessIterator2 __s_last,
713 _BinaryPredicate __pred) noexcept {
714 using __backend_tag = typename decltype(__tag)::__backend_tag;
715
716 if (__last - __first == __s_last - __s_first) {
717 const bool __res =
718 __internal::__pattern_equal(__tag, std::forward<_ExecutionPolicy>(__exec), __first, __last, __s_first, __pred);
719 return __res ? __first : __last;
720 } else {
721 return __internal::__except_handler([&]() {
722 return __internal::__parallel_find(
723 __backend_tag{},
724 std::forward<_ExecutionPolicy>(__exec),
725 __first,
726 __last,
727 [__last, __s_first, __s_last, __pred](_RandomAccessIterator1 __i, _RandomAccessIterator1 __j) {
728 return __internal::__find_subrange(__i, __j, __last, __s_first, __s_last, __pred, false, _IsVector{});
729 },
730 std::greater<typename std::iterator_traits<_RandomAccessIterator1>::difference_type>(),
731 /*is_first=*/false);
732 });
733 }
734 }
735
736 //------------------------------------------------------------------------
737 // find_first_of
738 //------------------------------------------------------------------------
739 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
__brick_find_first_of(_ForwardIterator1 __first,_ForwardIterator1 __last,_ForwardIterator2 __s_first,_ForwardIterator2 __s_last,_BinaryPredicate __pred,std::false_type)740 _ForwardIterator1 __brick_find_first_of(
741 _ForwardIterator1 __first,
742 _ForwardIterator1 __last,
743 _ForwardIterator2 __s_first,
744 _ForwardIterator2 __s_last,
745 _BinaryPredicate __pred,
746 /*__is_vector=*/std::false_type) noexcept {
747 return std::find_first_of(__first, __last, __s_first, __s_last, __pred);
748 }
749
750 template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _BinaryPredicate>
__brick_find_first_of(_RandomAccessIterator1 __first,_RandomAccessIterator1 __last,_RandomAccessIterator2 __s_first,_RandomAccessIterator2 __s_last,_BinaryPredicate __pred,std::true_type)751 _RandomAccessIterator1 __brick_find_first_of(
752 _RandomAccessIterator1 __first,
753 _RandomAccessIterator1 __last,
754 _RandomAccessIterator2 __s_first,
755 _RandomAccessIterator2 __s_last,
756 _BinaryPredicate __pred,
757 /*__is_vector=*/std::true_type) noexcept {
758 return __unseq_backend::__simd_find_first_of(__first, __last, __s_first, __s_last, __pred);
759 }
760
761 template <class _Tag, class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
__pattern_find_first_of(_Tag,_ExecutionPolicy &&,_ForwardIterator1 __first,_ForwardIterator1 __last,_ForwardIterator2 __s_first,_ForwardIterator2 __s_last,_BinaryPredicate __pred)762 _ForwardIterator1 __pattern_find_first_of(
763 _Tag,
764 _ExecutionPolicy&&,
765 _ForwardIterator1 __first,
766 _ForwardIterator1 __last,
767 _ForwardIterator2 __s_first,
768 _ForwardIterator2 __s_last,
769 _BinaryPredicate __pred) noexcept {
770 return __internal::__brick_find_first_of(__first, __last, __s_first, __s_last, __pred, typename _Tag::__is_vector{});
771 }
772
773 template <class _IsVector,
774 class _ExecutionPolicy,
775 class _RandomAccessIterator1,
776 class _RandomAccessIterator2,
777 class _BinaryPredicate>
__pattern_find_first_of(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator1 __first,_RandomAccessIterator1 __last,_RandomAccessIterator2 __s_first,_RandomAccessIterator2 __s_last,_BinaryPredicate __pred)778 _RandomAccessIterator1 __pattern_find_first_of(
779 __parallel_tag<_IsVector> __tag,
780 _ExecutionPolicy&& __exec,
781 _RandomAccessIterator1 __first,
782 _RandomAccessIterator1 __last,
783 _RandomAccessIterator2 __s_first,
784 _RandomAccessIterator2 __s_last,
785 _BinaryPredicate __pred) noexcept {
786 using __backend_tag = typename decltype(__tag)::__backend_tag;
787
788 return __internal::__except_handler([&]() {
789 return __internal::__parallel_find(
790 __backend_tag{},
791 std::forward<_ExecutionPolicy>(__exec),
792 __first,
793 __last,
794 [__s_first, __s_last, __pred](_RandomAccessIterator1 __i, _RandomAccessIterator1 __j) {
795 return __internal::__brick_find_first_of(__i, __j, __s_first, __s_last, __pred, _IsVector{});
796 },
797 std::less<typename std::iterator_traits<_RandomAccessIterator1>::difference_type>(),
798 /*is_first=*/true);
799 });
800 }
801
802 //------------------------------------------------------------------------
803 // search
804 //------------------------------------------------------------------------
805 template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _BinaryPredicate>
__brick_search(_RandomAccessIterator1 __first,_RandomAccessIterator1 __last,_RandomAccessIterator2 __s_first,_RandomAccessIterator2 __s_last,_BinaryPredicate __pred,std::false_type)806 _RandomAccessIterator1 __brick_search(
807 _RandomAccessIterator1 __first,
808 _RandomAccessIterator1 __last,
809 _RandomAccessIterator2 __s_first,
810 _RandomAccessIterator2 __s_last,
811 _BinaryPredicate __pred,
812 /*vector=*/std::false_type) noexcept {
813 return std::search(__first, __last, __s_first, __s_last, __pred);
814 }
815
816 template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _BinaryPredicate>
__brick_search(_RandomAccessIterator1 __first,_RandomAccessIterator1 __last,_RandomAccessIterator2 __s_first,_RandomAccessIterator2 __s_last,_BinaryPredicate __pred,std::true_type)817 _RandomAccessIterator1 __brick_search(
818 _RandomAccessIterator1 __first,
819 _RandomAccessIterator1 __last,
820 _RandomAccessIterator2 __s_first,
821 _RandomAccessIterator2 __s_last,
822 _BinaryPredicate __pred,
823 /*vector=*/std::true_type) noexcept {
824 return __internal::__find_subrange(__first, __last, __last, __s_first, __s_last, __pred, true, std::true_type());
825 }
826
827 template <class _Tag, class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
__pattern_search(_Tag,_ExecutionPolicy &&,_ForwardIterator1 __first,_ForwardIterator1 __last,_ForwardIterator2 __s_first,_ForwardIterator2 __s_last,_BinaryPredicate __pred)828 _ForwardIterator1 __pattern_search(
829 _Tag,
830 _ExecutionPolicy&&,
831 _ForwardIterator1 __first,
832 _ForwardIterator1 __last,
833 _ForwardIterator2 __s_first,
834 _ForwardIterator2 __s_last,
835 _BinaryPredicate __pred) noexcept {
836 return __internal::__brick_search(__first, __last, __s_first, __s_last, __pred, typename _Tag::__is_vector{});
837 }
838
839 template <class _IsVector,
840 class _ExecutionPolicy,
841 class _RandomAccessIterator1,
842 class _RandomAccessIterator2,
843 class _BinaryPredicate>
__pattern_search(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator1 __first,_RandomAccessIterator1 __last,_RandomAccessIterator2 __s_first,_RandomAccessIterator2 __s_last,_BinaryPredicate __pred)844 _RandomAccessIterator1 __pattern_search(
845 __parallel_tag<_IsVector> __tag,
846 _ExecutionPolicy&& __exec,
847 _RandomAccessIterator1 __first,
848 _RandomAccessIterator1 __last,
849 _RandomAccessIterator2 __s_first,
850 _RandomAccessIterator2 __s_last,
851 _BinaryPredicate __pred) noexcept {
852 using __backend_tag = typename decltype(__tag)::__backend_tag;
853
854 if (__last - __first == __s_last - __s_first) {
855 const bool __res =
856 __internal::__pattern_equal(__tag, std::forward<_ExecutionPolicy>(__exec), __first, __last, __s_first, __pred);
857 return __res ? __first : __last;
858 } else {
859 return __internal::__except_handler([&]() {
860 return __internal::__parallel_find(
861 __backend_tag{},
862 std::forward<_ExecutionPolicy>(__exec),
863 __first,
864 __last,
865 [__last, __s_first, __s_last, __pred](_RandomAccessIterator1 __i, _RandomAccessIterator1 __j) {
866 return __internal::__find_subrange(__i, __j, __last, __s_first, __s_last, __pred, true, _IsVector{});
867 },
868 std::less<typename std::iterator_traits<_RandomAccessIterator1>::difference_type>(),
869 /*is_first=*/true);
870 });
871 }
872 }
873
874 //------------------------------------------------------------------------
875 // search_n
876 //------------------------------------------------------------------------
877 template <class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate>
__brick_search_n(_ForwardIterator __first,_ForwardIterator __last,_Size __count,const _Tp & __value,_BinaryPredicate __pred,std::false_type)878 _ForwardIterator __brick_search_n(
879 _ForwardIterator __first,
880 _ForwardIterator __last,
881 _Size __count,
882 const _Tp& __value,
883 _BinaryPredicate __pred,
884 /*vector=*/std::false_type) noexcept {
885 return std::search_n(__first, __last, __count, __value, __pred);
886 }
887
888 template <class _RandomAccessIterator, class _Size, class _Tp, class _BinaryPredicate>
__brick_search_n(_RandomAccessIterator __first,_RandomAccessIterator __last,_Size __count,const _Tp & __value,_BinaryPredicate __pred,std::true_type)889 _RandomAccessIterator __brick_search_n(
890 _RandomAccessIterator __first,
891 _RandomAccessIterator __last,
892 _Size __count,
893 const _Tp& __value,
894 _BinaryPredicate __pred,
895 /*vector=*/std::true_type) noexcept {
896 return __internal::__find_subrange(__first, __last, __last, __count, __value, __pred, std::true_type());
897 }
898
899 template <class _Tag, class _ExecutionPolicy, class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate>
__pattern_search_n(_Tag,_ExecutionPolicy &&,_ForwardIterator __first,_ForwardIterator __last,_Size __count,const _Tp & __value,_BinaryPredicate __pred)900 _ForwardIterator __pattern_search_n(
901 _Tag,
902 _ExecutionPolicy&&,
903 _ForwardIterator __first,
904 _ForwardIterator __last,
905 _Size __count,
906 const _Tp& __value,
907 _BinaryPredicate __pred) noexcept {
908 return __internal::__brick_search_n(__first, __last, __count, __value, __pred, typename _Tag::__is_vector{});
909 }
910
911 template <class _IsVector,
912 class _ExecutionPolicy,
913 class _RandomAccessIterator,
914 class _Size,
915 class _Tp,
916 class _BinaryPredicate>
__pattern_search_n(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator __first,_RandomAccessIterator __last,_Size __count,const _Tp & __value,_BinaryPredicate __pred)917 _RandomAccessIterator __pattern_search_n(
918 __parallel_tag<_IsVector> __tag,
919 _ExecutionPolicy&& __exec,
920 _RandomAccessIterator __first,
921 _RandomAccessIterator __last,
922 _Size __count,
923 const _Tp& __value,
924 _BinaryPredicate __pred) noexcept {
925 using __backend_tag = typename decltype(__tag)::__backend_tag;
926
927 if (static_cast<_Size>(__last - __first) == __count) {
928 const bool __result = !__internal::__pattern_any_of(
929 __tag, std::forward<_ExecutionPolicy>(__exec), __first, __last, [&__value, &__pred](const _Tp& __val) {
930 return !__pred(__val, __value);
931 });
932 return __result ? __first : __last;
933 } else {
934 return __internal::__except_handler([&__exec, __first, __last, __count, &__value, __pred]() {
935 return __internal::__parallel_find(
936 __backend_tag{},
937 std::forward<_ExecutionPolicy>(__exec),
938 __first,
939 __last,
940 [__last, __count, &__value, __pred](_RandomAccessIterator __i, _RandomAccessIterator __j) {
941 return __internal::__find_subrange(__i, __j, __last, __count, __value, __pred, _IsVector{});
942 },
943 std::less<typename std::iterator_traits<_RandomAccessIterator>::difference_type>(),
944 /*is_first=*/true);
945 });
946 }
947 }
948
949 //------------------------------------------------------------------------
950 // copy_n
951 //------------------------------------------------------------------------
952
953 template <class _ForwardIterator, class _Size, class _OutputIterator>
954 _OutputIterator
__brick_copy_n(_ForwardIterator __first,_Size __n,_OutputIterator __result,std::false_type)955 __brick_copy_n(_ForwardIterator __first, _Size __n, _OutputIterator __result, /*vector=*/std::false_type) noexcept {
956 return std::copy_n(__first, __n, __result);
957 }
958
959 template <class _RandomAccessIterator1, class _Size, class _RandomAccessIterator2>
960 _RandomAccessIterator2
__brick_copy_n(_RandomAccessIterator1 __first,_Size __n,_RandomAccessIterator2 __result,std::true_type)961 __brick_copy_n(_RandomAccessIterator1 __first,
962 _Size __n,
963 _RandomAccessIterator2 __result,
964 /*vector=*/std::true_type) noexcept {
965 return __unseq_backend::__simd_assign(
966 __first, __n, __result, [](_RandomAccessIterator1 __first, _RandomAccessIterator2 __result) {
967 *__result = *__first;
968 });
969 }
970
971 //------------------------------------------------------------------------
972 // copy
973 //------------------------------------------------------------------------
974 template <class _ForwardIterator, class _OutputIterator>
975 _OutputIterator
__brick_copy(_ForwardIterator __first,_ForwardIterator __last,_OutputIterator __result,std::false_type)976 __brick_copy(_ForwardIterator __first,
977 _ForwardIterator __last,
978 _OutputIterator __result,
979 /*vector=*/std::false_type) noexcept {
980 return std::copy(__first, __last, __result);
981 }
982
983 template <class _RandomAccessIterator1, class _RandomAccessIterator2>
984 _RandomAccessIterator2
__brick_copy(_RandomAccessIterator1 __first,_RandomAccessIterator1 __last,_RandomAccessIterator2 __result,std::true_type)985 __brick_copy(_RandomAccessIterator1 __first,
986 _RandomAccessIterator1 __last,
987 _RandomAccessIterator2 __result,
988 /*vector=*/std::true_type) noexcept {
989 return __unseq_backend::__simd_assign(
990 __first, __last - __first, __result, [](_RandomAccessIterator1 __first, _RandomAccessIterator2 __result) {
991 *__result = *__first;
992 });
993 }
994
995 //------------------------------------------------------------------------
996 // move
997 //------------------------------------------------------------------------
998 template <class _ForwardIterator, class _OutputIterator>
999 _OutputIterator
__brick_move(_ForwardIterator __first,_ForwardIterator __last,_OutputIterator __result,std::false_type)1000 __brick_move(_ForwardIterator __first,
1001 _ForwardIterator __last,
1002 _OutputIterator __result,
1003 /*vector=*/std::false_type) noexcept {
1004 return std::move(__first, __last, __result);
1005 }
1006
1007 template <class _RandomAccessIterator1, class _RandomAccessIterator2>
1008 _RandomAccessIterator2
__brick_move(_RandomAccessIterator1 __first,_RandomAccessIterator1 __last,_RandomAccessIterator2 __result,std::true_type)1009 __brick_move(_RandomAccessIterator1 __first,
1010 _RandomAccessIterator1 __last,
1011 _RandomAccessIterator2 __result,
1012 /*vector=*/std::true_type) noexcept {
1013 return __unseq_backend::__simd_assign(
1014 __first, __last - __first, __result, [](_RandomAccessIterator1 __first, _RandomAccessIterator2 __result) {
1015 *__result = std::move(*__first);
1016 });
1017 }
1018
1019 struct __brick_move_destroy {
1020 template <typename _RandomAccessIterator1, typename _RandomAccessIterator2>
1021 _RandomAccessIterator2
operator__brick_move_destroy1022 operator()(_RandomAccessIterator1 __first,
1023 _RandomAccessIterator1 __last,
1024 _RandomAccessIterator2 __result,
1025 /*vec*/ std::true_type) const {
1026 using _IteratorValueType = typename std::iterator_traits<_RandomAccessIterator1>::value_type;
1027
1028 return __unseq_backend::__simd_assign(
1029 __first, __last - __first, __result, [](_RandomAccessIterator1 __first, _RandomAccessIterator2 __result) {
1030 *__result = std::move(*__first);
1031 (*__first).~_IteratorValueType();
1032 });
1033 }
1034
1035 template <typename _RandomAccessIterator1, typename _RandomAccessIterator2>
1036 _RandomAccessIterator2
operator__brick_move_destroy1037 operator()(_RandomAccessIterator1 __first,
1038 _RandomAccessIterator1 __last,
1039 _RandomAccessIterator2 __result,
1040 /*vec*/ std::false_type) const {
1041 using _IteratorValueType = typename std::iterator_traits<_RandomAccessIterator1>::value_type;
1042
1043 for (; __first != __last; ++__first, ++__result) {
1044 *__result = std::move(*__first);
1045 (*__first).~_IteratorValueType();
1046 }
1047 return __result;
1048 }
1049 };
1050
1051 //------------------------------------------------------------------------
1052 // swap_ranges
1053 //------------------------------------------------------------------------
1054 template <class _ForwardIterator, class _OutputIterator>
__brick_swap_ranges(_ForwardIterator __first,_ForwardIterator __last,_OutputIterator __result,std::false_type)1055 _OutputIterator __brick_swap_ranges(
1056 _ForwardIterator __first,
1057 _ForwardIterator __last,
1058 _OutputIterator __result,
1059 /*vector=*/std::false_type) noexcept {
1060 return std::swap_ranges(__first, __last, __result);
1061 }
1062
1063 template <class _RandomAccessIterator1, class _RandomAccessIterator2>
__brick_swap_ranges(_RandomAccessIterator1 __first,_RandomAccessIterator1 __last,_RandomAccessIterator2 __result,std::true_type)1064 _RandomAccessIterator2 __brick_swap_ranges(
1065 _RandomAccessIterator1 __first,
1066 _RandomAccessIterator1 __last,
1067 _RandomAccessIterator2 __result,
1068 /*vector=*/std::true_type) noexcept {
1069 using std::iter_swap;
1070 return __unseq_backend::__simd_assign(
1071 __first, __last - __first, __result, iter_swap<_RandomAccessIterator1, _RandomAccessIterator2>);
1072 }
1073
1074 //------------------------------------------------------------------------
1075 // copy_if
1076 //------------------------------------------------------------------------
1077 template <class _ForwardIterator, class _OutputIterator, class _UnaryPredicate>
__brick_copy_if(_ForwardIterator __first,_ForwardIterator __last,_OutputIterator __result,_UnaryPredicate __pred,std::false_type)1078 _OutputIterator __brick_copy_if(
1079 _ForwardIterator __first,
1080 _ForwardIterator __last,
1081 _OutputIterator __result,
1082 _UnaryPredicate __pred,
1083 /*vector=*/std::false_type) noexcept {
1084 return std::copy_if(__first, __last, __result, __pred);
1085 }
1086
1087 template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _UnaryPredicate>
__brick_copy_if(_RandomAccessIterator1 __first,_RandomAccessIterator1 __last,_RandomAccessIterator2 __result,_UnaryPredicate __pred,std::true_type)1088 _RandomAccessIterator2 __brick_copy_if(
1089 _RandomAccessIterator1 __first,
1090 _RandomAccessIterator1 __last,
1091 _RandomAccessIterator2 __result,
1092 _UnaryPredicate __pred,
1093 /*vector=*/std::true_type) noexcept {
1094 #if defined(_PSTL_MONOTONIC_PRESENT)
1095 return __unseq_backend::__simd_copy_if(__first, __last - __first, __result, __pred);
1096 #else
1097 return std::copy_if(__first, __last, __result, __pred);
1098 #endif
1099 }
1100
1101 // TODO: Try to use transform_reduce for combining __brick_copy_if_phase1 on IsVector.
1102 template <class _DifferenceType, class _ForwardIterator, class _UnaryPredicate>
__brick_calc_mask_1(_ForwardIterator __first,_ForwardIterator __last,bool * __restrict __mask,_UnaryPredicate __pred,std::false_type)1103 std::pair<_DifferenceType, _DifferenceType> __brick_calc_mask_1(
1104 _ForwardIterator __first,
1105 _ForwardIterator __last,
1106 bool* __restrict __mask,
1107 _UnaryPredicate __pred,
1108 /*vector=*/std::false_type) noexcept {
1109 auto __count_true = _DifferenceType(0);
1110 auto __size = __last - __first;
1111
1112 static_assert(__are_random_access_iterators<_ForwardIterator>::value,
1113 "Pattern-brick error. Should be a random access iterator.");
1114
1115 for (; __first != __last; ++__first, ++__mask) {
1116 *__mask = __pred(*__first);
1117 if (*__mask) {
1118 ++__count_true;
1119 }
1120 }
1121 return std::make_pair(__count_true, __size - __count_true);
1122 }
1123
1124 template <class _DifferenceType, class _RandomAccessIterator, class _UnaryPredicate>
__brick_calc_mask_1(_RandomAccessIterator __first,_RandomAccessIterator __last,bool * __mask,_UnaryPredicate __pred,std::true_type)1125 std::pair<_DifferenceType, _DifferenceType> __brick_calc_mask_1(
1126 _RandomAccessIterator __first,
1127 _RandomAccessIterator __last,
1128 bool* __mask,
1129 _UnaryPredicate __pred,
1130 /*vector=*/std::true_type) noexcept {
1131 auto __result = __unseq_backend::__simd_calc_mask_1(__first, __last - __first, __mask, __pred);
1132 return std::make_pair(__result, (__last - __first) - __result);
1133 }
1134
1135 template <class _ForwardIterator, class _OutputIterator, class _Assigner>
__brick_copy_by_mask(_ForwardIterator __first,_ForwardIterator __last,_OutputIterator __result,bool * __mask,_Assigner __assigner,std::false_type)1136 void __brick_copy_by_mask(
1137 _ForwardIterator __first,
1138 _ForwardIterator __last,
1139 _OutputIterator __result,
1140 bool* __mask,
1141 _Assigner __assigner,
1142 /*vector=*/std::false_type) noexcept {
1143 for (; __first != __last; ++__first, ++__mask) {
1144 if (*__mask) {
1145 __assigner(__first, __result);
1146 ++__result;
1147 }
1148 }
1149 }
1150
1151 template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _Assigner>
__brick_copy_by_mask(_RandomAccessIterator1 __first,_RandomAccessIterator1 __last,_RandomAccessIterator2 __result,bool * __restrict __mask,_Assigner __assigner,std::true_type)1152 void __brick_copy_by_mask(
1153 _RandomAccessIterator1 __first,
1154 _RandomAccessIterator1 __last,
1155 _RandomAccessIterator2 __result,
1156 bool* __restrict __mask,
1157 _Assigner __assigner,
1158 /*vector=*/std::true_type) noexcept {
1159 #if defined(_PSTL_MONOTONIC_PRESENT)
1160 __unseq_backend::__simd_copy_by_mask(__first, __last - __first, __result, __mask, __assigner);
1161 #else
1162 __internal::__brick_copy_by_mask(__first, __last, __result, __mask, __assigner, std::false_type());
1163 #endif
1164 }
1165
1166 template <class _ForwardIterator, class _OutputIterator1, class _OutputIterator2>
__brick_partition_by_mask(_ForwardIterator __first,_ForwardIterator __last,_OutputIterator1 __out_true,_OutputIterator2 __out_false,bool * __mask,std::false_type)1167 void __brick_partition_by_mask(
1168 _ForwardIterator __first,
1169 _ForwardIterator __last,
1170 _OutputIterator1 __out_true,
1171 _OutputIterator2 __out_false,
1172 bool* __mask,
1173 /*vector=*/std::false_type) noexcept {
1174 for (; __first != __last; ++__first, ++__mask) {
1175 if (*__mask) {
1176 *__out_true = *__first;
1177 ++__out_true;
1178 } else {
1179 *__out_false = *__first;
1180 ++__out_false;
1181 }
1182 }
1183 }
1184
1185 template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _RandomAccessIterator3>
__brick_partition_by_mask(_RandomAccessIterator1 __first,_RandomAccessIterator1 __last,_RandomAccessIterator2 __out_true,_RandomAccessIterator3 __out_false,bool * __mask,std::true_type)1186 void __brick_partition_by_mask(
1187 _RandomAccessIterator1 __first,
1188 _RandomAccessIterator1 __last,
1189 _RandomAccessIterator2 __out_true,
1190 _RandomAccessIterator3 __out_false,
1191 bool* __mask,
1192 /*vector=*/std::true_type) noexcept {
1193 #if defined(_PSTL_MONOTONIC_PRESENT)
1194 __unseq_backend::__simd_partition_by_mask(__first, __last - __first, __out_true, __out_false, __mask);
1195 #else
1196 __internal::__brick_partition_by_mask(__first, __last, __out_true, __out_false, __mask, std::false_type());
1197 #endif
1198 }
1199
1200 template <class _Tag, class _ExecutionPolicy, class _ForwardIterator, class _OutputIterator, class _UnaryPredicate>
__pattern_copy_if(_Tag,_ExecutionPolicy &&,_ForwardIterator __first,_ForwardIterator __last,_OutputIterator __result,_UnaryPredicate __pred)1201 _OutputIterator __pattern_copy_if(
1202 _Tag,
1203 _ExecutionPolicy&&,
1204 _ForwardIterator __first,
1205 _ForwardIterator __last,
1206 _OutputIterator __result,
1207 _UnaryPredicate __pred) noexcept {
1208 return __internal::__brick_copy_if(__first, __last, __result, __pred, typename _Tag::__is_vector{});
1209 }
1210
1211 template <class _IsVector,
1212 class _ExecutionPolicy,
1213 class _RandomAccessIterator1,
1214 class _RandomAccessIterator2,
1215 class _UnaryPredicate>
__pattern_copy_if(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator1 __first,_RandomAccessIterator1 __last,_RandomAccessIterator2 __result,_UnaryPredicate __pred)1216 _RandomAccessIterator2 __pattern_copy_if(
1217 __parallel_tag<_IsVector> __tag,
1218 _ExecutionPolicy&& __exec,
1219 _RandomAccessIterator1 __first,
1220 _RandomAccessIterator1 __last,
1221 _RandomAccessIterator2 __result,
1222 _UnaryPredicate __pred) {
1223 using __backend_tag = typename decltype(__tag)::__backend_tag;
1224
1225 typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _DifferenceType;
1226 const _DifferenceType __n = __last - __first;
1227 if (_DifferenceType(1) < __n) {
1228 __par_backend::__buffer<bool> __mask_buf(__n);
1229 return __internal::__except_handler([&__exec, __n, __first, __result, __pred, &__mask_buf]() {
1230 bool* __mask = __mask_buf.get();
1231 _DifferenceType __m{};
1232 __par_backend::__parallel_strict_scan(
1233 __backend_tag{},
1234 std::forward<_ExecutionPolicy>(__exec),
1235 __n,
1236 _DifferenceType(0),
1237 [=](_DifferenceType __i, _DifferenceType __len) { // Reduce
1238 return __internal::__brick_calc_mask_1<_DifferenceType>(
1239 __first + __i, __first + (__i + __len), __mask + __i, __pred, _IsVector{})
1240 .first;
1241 },
1242 std::plus<_DifferenceType>(), // Combine
1243 [=](_DifferenceType __i, _DifferenceType __len, _DifferenceType __initial) { // Scan
1244 __internal::__brick_copy_by_mask(
1245 __first + __i,
1246 __first + (__i + __len),
1247 __result + __initial,
1248 __mask + __i,
1249 [](_RandomAccessIterator1 __x, _RandomAccessIterator2 __z) { *__z = *__x; },
1250 _IsVector{});
1251 },
1252 [&__m](_DifferenceType __total) { __m = __total; });
1253 return __result + __m;
1254 });
1255 }
1256 // trivial sequence - use serial algorithm
1257 return __internal::__brick_copy_if(__first, __last, __result, __pred, _IsVector{});
1258 }
1259
1260 //------------------------------------------------------------------------
1261 // count
1262 //------------------------------------------------------------------------
1263 template <class _RandomAccessIterator, class _Predicate>
1264 typename std::iterator_traits<_RandomAccessIterator>::difference_type
__brick_count(_RandomAccessIterator __first,_RandomAccessIterator __last,_Predicate __pred,std::true_type)1265 __brick_count(_RandomAccessIterator __first,
1266 _RandomAccessIterator __last,
1267 _Predicate __pred,
1268 /* is_vector = */ std::true_type) noexcept {
1269 return __unseq_backend::__simd_count(__first, __last - __first, __pred);
1270 }
1271
1272 template <class _ForwardIterator, class _Predicate>
1273 typename std::iterator_traits<_ForwardIterator>::difference_type
__brick_count(_ForwardIterator __first,_ForwardIterator __last,_Predicate __pred,std::false_type)1274 __brick_count(_ForwardIterator __first,
1275 _ForwardIterator __last,
1276 _Predicate __pred,
1277 /* is_vector = */ std::false_type) noexcept {
1278 return std::count_if(__first, __last, __pred);
1279 }
1280
1281 template <class _Tag, class _ExecutionPolicy, class _ForwardIterator, class _Predicate>
__pattern_count(_Tag,_ExecutionPolicy &&,_ForwardIterator __first,_ForwardIterator __last,_Predicate __pred)1282 typename std::iterator_traits<_ForwardIterator>::difference_type __pattern_count(
1283 _Tag, _ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) noexcept {
1284 return __internal::__brick_count(__first, __last, __pred, typename _Tag::__is_vector{});
1285 }
1286
1287 template <class _IsVector, class _ExecutionPolicy, class _RandomAccessIterator, class _Predicate>
__pattern_count(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator __first,_RandomAccessIterator __last,_Predicate __pred)1288 typename std::iterator_traits<_RandomAccessIterator>::difference_type __pattern_count(
1289 __parallel_tag<_IsVector> __tag,
1290 _ExecutionPolicy&& __exec,
1291 _RandomAccessIterator __first,
1292 _RandomAccessIterator __last,
1293 _Predicate __pred) {
1294 using __backend_tag = typename decltype(__tag)::__backend_tag;
1295
1296 typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _SizeType;
1297 return __internal::__except_handler([&]() {
1298 return __par_backend::__parallel_reduce(
1299 __backend_tag{},
1300 std::forward<_ExecutionPolicy>(__exec),
1301 __first,
1302 __last,
1303 _SizeType(0),
1304 [__pred](_RandomAccessIterator __begin, _RandomAccessIterator __end, _SizeType __value) -> _SizeType {
1305 return __value + __internal::__brick_count(__begin, __end, __pred, _IsVector{});
1306 },
1307 std::plus<_SizeType>());
1308 });
1309 }
1310
1311 //------------------------------------------------------------------------
1312 // unique
1313 //------------------------------------------------------------------------
1314
1315 template <class _RandomAccessIterator, class _BinaryPredicate>
1316 _RandomAccessIterator
__brick_unique(_RandomAccessIterator __first,_RandomAccessIterator __last,_BinaryPredicate __pred,std::false_type)1317 __brick_unique(_RandomAccessIterator __first,
1318 _RandomAccessIterator __last,
1319 _BinaryPredicate __pred,
1320 /*is_vector=*/std::false_type) noexcept {
1321 return std::unique(__first, __last, __pred);
1322 }
1323
1324 template <class _RandomAccessIterator, class _BinaryPredicate>
1325 _RandomAccessIterator
__brick_unique(_RandomAccessIterator __first,_RandomAccessIterator __last,_BinaryPredicate __pred,std::true_type)1326 __brick_unique(_RandomAccessIterator __first,
1327 _RandomAccessIterator __last,
1328 _BinaryPredicate __pred,
1329 /*is_vector=*/std::true_type) noexcept {
1330 // TODO: vectorize
1331 return std::unique(__first, __last, __pred);
1332 }
1333
1334 template <class _Tag, class _ExecutionPolicy, class _ForwardIterator, class _BinaryPredicate>
__pattern_unique(_Tag,_ExecutionPolicy &&,_ForwardIterator __first,_ForwardIterator __last,_BinaryPredicate __pred)1335 _ForwardIterator __pattern_unique(
1336 _Tag, _ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred) noexcept {
1337 return __internal::__brick_unique(__first, __last, __pred, typename _Tag::__is_vector{});
1338 }
1339
1340 // That function is shared between two algorithms - remove_if (__pattern_remove_if) and unique (pattern unique). But a
1341 // mask calculation is different. So, a caller passes _CalcMask brick into remove_elements.
1342 template <class _IsVector, class _ExecutionPolicy, class _ForwardIterator, class _CalcMask>
__remove_elements(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_ForwardIterator __first,_ForwardIterator __last,_CalcMask __calc_mask)1343 _ForwardIterator __remove_elements(
1344 __parallel_tag<_IsVector> __tag,
1345 _ExecutionPolicy&& __exec,
1346 _ForwardIterator __first,
1347 _ForwardIterator __last,
1348 _CalcMask __calc_mask) {
1349 using __backend_tag = typename decltype(__tag)::__backend_tag;
1350
1351 typedef typename std::iterator_traits<_ForwardIterator>::difference_type _DifferenceType;
1352 typedef typename std::iterator_traits<_ForwardIterator>::value_type _Tp;
1353 _DifferenceType __n = __last - __first;
1354 __par_backend::__buffer<bool> __mask_buf(__n);
1355 // 1. find a first iterator that should be removed
1356 return __internal::__except_handler([&]() {
1357 bool* __mask = __mask_buf.get();
1358 _DifferenceType __min = __par_backend::__parallel_reduce(
1359 __backend_tag{},
1360 std::forward<_ExecutionPolicy>(__exec),
1361 _DifferenceType(0),
1362 __n,
1363 __n,
1364 [__first, __mask, &__calc_mask](
1365 _DifferenceType __i, _DifferenceType __j, _DifferenceType __local_min) -> _DifferenceType {
1366 // Create mask
1367 __calc_mask(__mask + __i, __mask + __j, __first + __i);
1368
1369 // if minimum was found in a previous range we shouldn't do anymore
1370 if (__local_min < __i) {
1371 return __local_min;
1372 }
1373 // find first iterator that should be removed
1374 bool* __result = __internal::__brick_find_if(
1375 __mask + __i, __mask + __j, [](bool __val) { return !__val; }, _IsVector{});
1376 if (__result - __mask == __j) {
1377 return __local_min;
1378 }
1379 return std::min(__local_min, _DifferenceType(__result - __mask));
1380 },
1381 [](_DifferenceType __local_min1, _DifferenceType __local_min2) -> _DifferenceType {
1382 return std::min(__local_min1, __local_min2);
1383 });
1384
1385 // No elements to remove - exit
1386 if (__min == __n) {
1387 return __last;
1388 }
1389 __n -= __min;
1390 __first += __min;
1391
1392 __par_backend::__buffer<_Tp> __buf(__n);
1393 _Tp* __result = __buf.get();
1394 __mask += __min;
1395 _DifferenceType __m{};
1396 // 2. Elements that doesn't satisfy pred are moved to result
1397 __par_backend::__parallel_strict_scan(
1398 __backend_tag{},
1399 std::forward<_ExecutionPolicy>(__exec),
1400 __n,
1401 _DifferenceType(0),
1402 [__mask](_DifferenceType __i, _DifferenceType __len) {
1403 return __internal::__brick_count(
1404 __mask + __i, __mask + __i + __len, [](bool __val) { return __val; }, _IsVector{});
1405 },
1406 std::plus<_DifferenceType>(),
1407 [=](_DifferenceType __i, _DifferenceType __len, _DifferenceType __initial) {
1408 __internal::__brick_copy_by_mask(
1409 __first + __i,
1410 __first + __i + __len,
1411 __result + __initial,
1412 __mask + __i,
1413 [](_ForwardIterator __x, _Tp* __z) {
1414 __internal::__invoke_if_else(
1415 std::is_trivial<_Tp>(),
1416 [&]() { *__z = std::move(*__x); },
1417 [&]() { ::new (std::addressof(*__z)) _Tp(std::move(*__x)); });
1418 },
1419 _IsVector{});
1420 },
1421 [&__m](_DifferenceType __total) { __m = __total; });
1422
1423 // 3. Elements from result are moved to [first, last)
1424 __par_backend::__parallel_for(
1425 __backend_tag{},
1426 std::forward<_ExecutionPolicy>(__exec),
1427 __result,
1428 __result + __m,
1429 [__result, __first](_Tp* __i, _Tp* __j) {
1430 __invoke_if_else(
1431 std::is_trivial<_Tp>(),
1432 [&]() { __brick_move(__i, __j, __first + (__i - __result), _IsVector{}); },
1433 [&]() { __brick_move_destroy()(__i, __j, __first + (__i - __result), _IsVector{}); });
1434 });
1435 return __first + __m;
1436 });
1437 }
1438
1439 template <class _IsVector, class _ExecutionPolicy, class _RandomAccessIterator, class _BinaryPredicate>
__pattern_unique(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator __first,_RandomAccessIterator __last,_BinaryPredicate __pred)1440 _RandomAccessIterator __pattern_unique(
1441 __parallel_tag<_IsVector> __tag,
1442 _ExecutionPolicy&& __exec,
1443 _RandomAccessIterator __first,
1444 _RandomAccessIterator __last,
1445 _BinaryPredicate __pred) noexcept {
1446 typedef typename std::iterator_traits<_RandomAccessIterator>::reference _ReferenceType;
1447
1448 if (__first == __last) {
1449 return __last;
1450 }
1451 if (__first + 1 == __last || __first + 2 == __last) {
1452 // Trivial sequence - use serial algorithm
1453 return __internal::__brick_unique(__first, __last, __pred, _IsVector{});
1454 }
1455 return __internal::__remove_elements(
1456 __tag,
1457 std::forward<_ExecutionPolicy>(__exec),
1458 ++__first,
1459 __last,
1460 [&__pred](bool* __b, bool* __e, _RandomAccessIterator __it) {
1461 __internal::__brick_walk3(
1462 __b,
1463 __e,
1464 __it - 1,
1465 __it,
1466 [&__pred](bool& __x, _ReferenceType __y, _ReferenceType __z) { __x = !__pred(__y, __z); },
1467 _IsVector{});
1468 });
1469 }
1470
1471 //------------------------------------------------------------------------
1472 // unique_copy
1473 //------------------------------------------------------------------------
1474
1475 template <class _ForwardIterator, class OutputIterator, class _BinaryPredicate>
__brick_unique_copy(_ForwardIterator __first,_ForwardIterator __last,OutputIterator __result,_BinaryPredicate __pred,std::false_type)1476 OutputIterator __brick_unique_copy(
1477 _ForwardIterator __first,
1478 _ForwardIterator __last,
1479 OutputIterator __result,
1480 _BinaryPredicate __pred,
1481 /*vector=*/std::false_type) noexcept {
1482 return std::unique_copy(__first, __last, __result, __pred);
1483 }
1484
1485 template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _BinaryPredicate>
__brick_unique_copy(_RandomAccessIterator1 __first,_RandomAccessIterator1 __last,_RandomAccessIterator2 __result,_BinaryPredicate __pred,std::true_type)1486 _RandomAccessIterator2 __brick_unique_copy(
1487 _RandomAccessIterator1 __first,
1488 _RandomAccessIterator1 __last,
1489 _RandomAccessIterator2 __result,
1490 _BinaryPredicate __pred,
1491 /*vector=*/std::true_type) noexcept {
1492 #if defined(_PSTL_MONOTONIC_PRESENT)
1493 return __unseq_backend::__simd_unique_copy(__first, __last - __first, __result, __pred);
1494 #else
1495 return std::unique_copy(__first, __last, __result, __pred);
1496 #endif
1497 }
1498
1499 template <class _Tag, class _ExecutionPolicy, class _ForwardIterator, class _OutputIterator, class _BinaryPredicate>
__pattern_unique_copy(_Tag,_ExecutionPolicy &&,_ForwardIterator __first,_ForwardIterator __last,_OutputIterator __result,_BinaryPredicate __pred)1500 _OutputIterator __pattern_unique_copy(
1501 _Tag,
1502 _ExecutionPolicy&&,
1503 _ForwardIterator __first,
1504 _ForwardIterator __last,
1505 _OutputIterator __result,
1506 _BinaryPredicate __pred) noexcept {
1507 return __internal::__brick_unique_copy(__first, __last, __result, __pred, typename _Tag::__is_vector{});
1508 }
1509
1510 template <class _DifferenceType, class _RandomAccessIterator, class _BinaryPredicate>
__brick_calc_mask_2(_RandomAccessIterator __first,_RandomAccessIterator __last,bool * __restrict __mask,_BinaryPredicate __pred,std::false_type)1511 _DifferenceType __brick_calc_mask_2(
1512 _RandomAccessIterator __first,
1513 _RandomAccessIterator __last,
1514 bool* __restrict __mask,
1515 _BinaryPredicate __pred,
1516 /*vector=*/std::false_type) noexcept {
1517 _DifferenceType __count = 0;
1518 for (; __first != __last; ++__first, ++__mask) {
1519 *__mask = !__pred(*__first, *(__first - 1));
1520 __count += *__mask;
1521 }
1522 return __count;
1523 }
1524
1525 template <class _DifferenceType, class _RandomAccessIterator, class _BinaryPredicate>
__brick_calc_mask_2(_RandomAccessIterator __first,_RandomAccessIterator __last,bool * __restrict __mask,_BinaryPredicate __pred,std::true_type)1526 _DifferenceType __brick_calc_mask_2(
1527 _RandomAccessIterator __first,
1528 _RandomAccessIterator __last,
1529 bool* __restrict __mask,
1530 _BinaryPredicate __pred,
1531 /*vector=*/std::true_type) noexcept {
1532 return __unseq_backend::__simd_calc_mask_2(__first, __last - __first, __mask, __pred);
1533 }
1534
1535 template <class _IsVector,
1536 class _ExecutionPolicy,
1537 class _RandomAccessIterator1,
1538 class _RandomAccessIterator2,
1539 class _BinaryPredicate>
__pattern_unique_copy(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator1 __first,_RandomAccessIterator1 __last,_RandomAccessIterator2 __result,_BinaryPredicate __pred)1540 _RandomAccessIterator2 __pattern_unique_copy(
1541 __parallel_tag<_IsVector> __tag,
1542 _ExecutionPolicy&& __exec,
1543 _RandomAccessIterator1 __first,
1544 _RandomAccessIterator1 __last,
1545 _RandomAccessIterator2 __result,
1546 _BinaryPredicate __pred) {
1547 using __backend_tag = typename decltype(__tag)::__backend_tag;
1548
1549 typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _DifferenceType;
1550 const _DifferenceType __n = __last - __first;
1551 if (_DifferenceType(2) < __n) {
1552 __par_backend::__buffer<bool> __mask_buf(__n);
1553 if (_DifferenceType(2) < __n) {
1554 return __internal::__except_handler([&__exec, __n, __first, __result, __pred, &__mask_buf]() {
1555 bool* __mask = __mask_buf.get();
1556 _DifferenceType __m{};
1557 __par_backend::__parallel_strict_scan(
1558 __backend_tag{},
1559 std::forward<_ExecutionPolicy>(__exec),
1560 __n,
1561 _DifferenceType(0),
1562 [=](_DifferenceType __i, _DifferenceType __len) -> _DifferenceType { // Reduce
1563 _DifferenceType __extra = 0;
1564 if (__i == 0) {
1565 // Special boundary case
1566 __mask[__i] = true;
1567 if (--__len == 0)
1568 return 1;
1569 ++__i;
1570 ++__extra;
1571 }
1572 return __internal::__brick_calc_mask_2<_DifferenceType>(
1573 __first + __i, __first + (__i + __len), __mask + __i, __pred, _IsVector{}) +
1574 __extra;
1575 },
1576 std::plus<_DifferenceType>(), // Combine
1577 [=](_DifferenceType __i, _DifferenceType __len, _DifferenceType __initial) { // Scan
1578 // Phase 2 is same as for __pattern_copy_if
1579 __internal::__brick_copy_by_mask(
1580 __first + __i,
1581 __first + (__i + __len),
1582 __result + __initial,
1583 __mask + __i,
1584 [](_RandomAccessIterator1 __x, _RandomAccessIterator2 __z) { *__z = *__x; },
1585 _IsVector{});
1586 },
1587 [&__m](_DifferenceType __total) { __m = __total; });
1588 return __result + __m;
1589 });
1590 }
1591 }
1592 // trivial sequence - use serial algorithm
1593 return __internal::__brick_unique_copy(__first, __last, __result, __pred, _IsVector{});
1594 }
1595
1596 //------------------------------------------------------------------------
1597 // reverse
1598 //------------------------------------------------------------------------
1599 template <class _BidirectionalIterator>
__brick_reverse(_BidirectionalIterator __first,_BidirectionalIterator __last,std::false_type)1600 void __brick_reverse(
1601 _BidirectionalIterator __first, _BidirectionalIterator __last, /*__is_vector=*/std::false_type) noexcept {
1602 std::reverse(__first, __last);
1603 }
1604
1605 template <class _RandomAccessIterator>
__brick_reverse(_RandomAccessIterator __first,_RandomAccessIterator __last,std::true_type)1606 void __brick_reverse(
1607 _RandomAccessIterator __first, _RandomAccessIterator __last, /*__is_vector=*/std::true_type) noexcept {
1608 typedef typename std::iterator_traits<_RandomAccessIterator>::reference _ReferenceType;
1609
1610 const auto __n = (__last - __first) / 2;
1611 __unseq_backend::__simd_walk_2(
1612 __first, __n, std::reverse_iterator<_RandomAccessIterator>(__last), [](_ReferenceType __x, _ReferenceType __y) {
1613 using std::swap;
1614 swap(__x, __y);
1615 });
1616 }
1617
1618 // this brick is called in parallel version, so we can use iterator arithmetic
1619 template <class _BidirectionalIterator>
__brick_reverse(_BidirectionalIterator __first,_BidirectionalIterator __last,_BidirectionalIterator __d_last,std::false_type)1620 void __brick_reverse(_BidirectionalIterator __first,
1621 _BidirectionalIterator __last,
1622 _BidirectionalIterator __d_last,
1623 /*is_vector=*/std::false_type) noexcept {
1624 for (--__d_last; __first != __last; ++__first, --__d_last) {
1625 using std::iter_swap;
1626 iter_swap(__first, __d_last);
1627 }
1628 }
1629
1630 // this brick is called in parallel version, so we can use iterator arithmetic
1631 template <class _RandomAccessIterator>
__brick_reverse(_RandomAccessIterator __first,_RandomAccessIterator __last,_RandomAccessIterator __d_last,std::true_type)1632 void __brick_reverse(_RandomAccessIterator __first,
1633 _RandomAccessIterator __last,
1634 _RandomAccessIterator __d_last,
1635 /*is_vector=*/std::true_type) noexcept {
1636 typedef typename std::iterator_traits<_RandomAccessIterator>::reference _ReferenceType;
1637
1638 __unseq_backend::__simd_walk_2(
1639 __first,
1640 __last - __first,
1641 std::reverse_iterator<_RandomAccessIterator>(__d_last),
1642 [](_ReferenceType __x, _ReferenceType __y) {
1643 using std::swap;
1644 swap(__x, __y);
1645 });
1646 }
1647
1648 template <class _Tag, class _ExecutionPolicy, class _BidirectionalIterator>
__pattern_reverse(_Tag,_ExecutionPolicy &&,_BidirectionalIterator __first,_BidirectionalIterator __last)1649 void __pattern_reverse(
1650 _Tag, _ExecutionPolicy&&, _BidirectionalIterator __first, _BidirectionalIterator __last) noexcept {
1651 __internal::__brick_reverse(__first, __last, typename _Tag::__is_vector{});
1652 }
1653
1654 template <class _IsVector, class _ExecutionPolicy, class _RandomAccessIterator>
__pattern_reverse(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator __first,_RandomAccessIterator __last)1655 void __pattern_reverse(__parallel_tag<_IsVector> __tag,
1656 _ExecutionPolicy&& __exec,
1657 _RandomAccessIterator __first,
1658 _RandomAccessIterator __last) {
1659 using __backend_tag = typename decltype(__tag)::__backend_tag;
1660
1661 __par_backend::__parallel_for(
1662 __backend_tag{},
1663 std::forward<_ExecutionPolicy>(__exec),
1664 __first,
1665 __first + (__last - __first) / 2,
1666 [__first, __last](_RandomAccessIterator __inner_first, _RandomAccessIterator __inner_last) {
1667 __internal::__brick_reverse(__inner_first, __inner_last, __last - (__inner_first - __first), _IsVector{});
1668 });
1669 }
1670
1671 //------------------------------------------------------------------------
1672 // reverse_copy
1673 //------------------------------------------------------------------------
1674
1675 template <class _BidirectionalIterator, class _OutputIterator>
__brick_reverse_copy(_BidirectionalIterator __first,_BidirectionalIterator __last,_OutputIterator __d_first,std::false_type)1676 _OutputIterator __brick_reverse_copy(
1677 _BidirectionalIterator __first,
1678 _BidirectionalIterator __last,
1679 _OutputIterator __d_first,
1680 /*is_vector=*/std::false_type) noexcept {
1681 return std::reverse_copy(__first, __last, __d_first);
1682 }
1683
1684 template <class _RandomAccessIterator1, class _RandomAccessIterator2>
__brick_reverse_copy(_RandomAccessIterator1 __first,_RandomAccessIterator1 __last,_RandomAccessIterator2 __d_first,std::true_type)1685 _RandomAccessIterator2 __brick_reverse_copy(
1686 _RandomAccessIterator1 __first,
1687 _RandomAccessIterator1 __last,
1688 _RandomAccessIterator2 __d_first,
1689 /*is_vector=*/std::true_type) noexcept {
1690 typedef typename std::iterator_traits<_RandomAccessIterator1>::reference _ReferenceType1;
1691 typedef typename std::iterator_traits<_RandomAccessIterator2>::reference _ReferenceType2;
1692
1693 return __unseq_backend::__simd_walk_2(
1694 std::reverse_iterator<_RandomAccessIterator1>(__last),
1695 __last - __first,
1696 __d_first,
1697 [](_ReferenceType1 __x, _ReferenceType2 __y) { __y = __x; });
1698 }
1699
1700 template <class _Tag, class _ExecutionPolicy, class _BidirectionalIterator, class _OutputIterator>
__pattern_reverse_copy(_Tag,_ExecutionPolicy &&,_BidirectionalIterator __first,_BidirectionalIterator __last,_OutputIterator __d_first)1701 _OutputIterator __pattern_reverse_copy(
1702 _Tag,
1703 _ExecutionPolicy&&,
1704 _BidirectionalIterator __first,
1705 _BidirectionalIterator __last,
1706 _OutputIterator __d_first) noexcept {
1707 return __internal::__brick_reverse_copy(__first, __last, __d_first, typename _Tag::__is_vector{});
1708 }
1709
1710 template <class _IsVector, class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2>
__pattern_reverse_copy(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator1 __first,_RandomAccessIterator1 __last,_RandomAccessIterator2 __d_first)1711 _RandomAccessIterator2 __pattern_reverse_copy(
1712 __parallel_tag<_IsVector> __tag,
1713 _ExecutionPolicy&& __exec,
1714 _RandomAccessIterator1 __first,
1715 _RandomAccessIterator1 __last,
1716 _RandomAccessIterator2 __d_first) {
1717 using __backend_tag = typename decltype(__tag)::__backend_tag;
1718
1719 auto __len = __last - __first;
1720 __par_backend::__parallel_for(
1721 __backend_tag{},
1722 std::forward<_ExecutionPolicy>(__exec),
1723 __first,
1724 __last,
1725 [__first, __len, __d_first](_RandomAccessIterator1 __inner_first, _RandomAccessIterator1 __inner_last) {
1726 __internal::__brick_reverse_copy(
1727 __inner_first, __inner_last, __d_first + (__len - (__inner_last - __first)), _IsVector{});
1728 });
1729 return __d_first + __len;
1730 }
1731
1732 //------------------------------------------------------------------------
1733 // rotate
1734 //------------------------------------------------------------------------
1735 template <class _ForwardIterator>
1736 _ForwardIterator
__brick_rotate(_ForwardIterator __first,_ForwardIterator __middle,_ForwardIterator __last,std::false_type)1737 __brick_rotate(_ForwardIterator __first,
1738 _ForwardIterator __middle,
1739 _ForwardIterator __last,
1740 /*is_vector=*/std::false_type) noexcept {
1741 #if defined(_PSTL_CPP11_STD_ROTATE_BROKEN)
1742 std::rotate(__first, __middle, __last);
1743 return std::next(__first, std::distance(__middle, __last));
1744 #else
1745 return std::rotate(__first, __middle, __last);
1746 #endif
1747 }
1748
1749 template <class _RandomAccessIterator>
1750 _RandomAccessIterator
__brick_rotate(_RandomAccessIterator __first,_RandomAccessIterator __middle,_RandomAccessIterator __last,std::true_type)1751 __brick_rotate(_RandomAccessIterator __first,
1752 _RandomAccessIterator __middle,
1753 _RandomAccessIterator __last,
1754 /*is_vector=*/std::true_type) noexcept {
1755 auto __n = __last - __first;
1756 auto __m = __middle - __first;
1757 const _RandomAccessIterator __ret = __first + (__last - __middle);
1758
1759 bool __is_left = (__m <= __n / 2);
1760 if (!__is_left)
1761 __m = __n - __m;
1762
1763 while (__n > 1 && __m > 0) {
1764 using std::iter_swap;
1765 const auto __m_2 = __m * 2;
1766 if (__is_left) {
1767 for (; __last - __first >= __m_2; __first += __m) {
1768 __unseq_backend::__simd_assign(
1769 __first, __m, __first + __m, iter_swap<_RandomAccessIterator, _RandomAccessIterator>);
1770 }
1771 } else {
1772 for (; __last - __first >= __m_2; __last -= __m) {
1773 __unseq_backend::__simd_assign(
1774 __last - __m, __m, __last - __m_2, iter_swap<_RandomAccessIterator, _RandomAccessIterator>);
1775 }
1776 }
1777 __is_left = !__is_left;
1778 __m = __n % __m;
1779 __n = __last - __first;
1780 }
1781
1782 return __ret;
1783 }
1784
1785 template <class _Tag, class _ExecutionPolicy, class _ForwardIterator>
__pattern_rotate(_Tag,_ExecutionPolicy &&,_ForwardIterator __first,_ForwardIterator __middle,_ForwardIterator __last)1786 _ForwardIterator __pattern_rotate(
1787 _Tag, _ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last) noexcept {
1788 return __internal::__brick_rotate(__first, __middle, __last, typename _Tag::__is_vector{});
1789 }
1790
1791 template <class _IsVector, class _ExecutionPolicy, class _RandomAccessIterator>
__pattern_rotate(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator __first,_RandomAccessIterator __middle,_RandomAccessIterator __last)1792 _RandomAccessIterator __pattern_rotate(
1793 __parallel_tag<_IsVector> __tag,
1794 _ExecutionPolicy&& __exec,
1795 _RandomAccessIterator __first,
1796 _RandomAccessIterator __middle,
1797 _RandomAccessIterator __last) {
1798 using __backend_tag = typename decltype(__tag)::__backend_tag;
1799
1800 typedef typename std::iterator_traits<_RandomAccessIterator>::value_type _Tp;
1801 auto __n = __last - __first;
1802 auto __m = __middle - __first;
1803 if (__m <= __n / 2) {
1804 __par_backend::__buffer<_Tp> __buf(__n - __m);
1805 return __internal::__except_handler([&__exec, __n, __m, __first, __middle, __last, &__buf]() {
1806 _Tp* __result = __buf.get();
1807 __par_backend::__parallel_for(
1808 __backend_tag{},
1809 std::forward<_ExecutionPolicy>(__exec),
1810 __middle,
1811 __last,
1812 [__middle, __result](_RandomAccessIterator __b, _RandomAccessIterator __e) {
1813 __internal::__brick_uninitialized_move(__b, __e, __result + (__b - __middle), _IsVector{});
1814 });
1815
1816 __par_backend::__parallel_for(
1817 __backend_tag{},
1818 std::forward<_ExecutionPolicy>(__exec),
1819 __first,
1820 __middle,
1821 [__last, __middle](_RandomAccessIterator __b, _RandomAccessIterator __e) {
1822 __internal::__brick_move(__b, __e, __b + (__last - __middle), _IsVector{});
1823 });
1824
1825 __par_backend::__parallel_for(
1826 __backend_tag{},
1827 std::forward<_ExecutionPolicy>(__exec),
1828 __result,
1829 __result + (__n - __m),
1830 [__first, __result](_Tp* __b, _Tp* __e) {
1831 __brick_move_destroy()(__b, __e, __first + (__b - __result), _IsVector{});
1832 });
1833
1834 return __first + (__last - __middle);
1835 });
1836 } else {
1837 __par_backend::__buffer<_Tp> __buf(__m);
1838 return __internal::__except_handler([&__exec, __n, __m, __first, __middle, __last, &__buf]() {
1839 _Tp* __result = __buf.get();
1840 __par_backend::__parallel_for(
1841 __backend_tag{},
1842 std::forward<_ExecutionPolicy>(__exec),
1843 __first,
1844 __middle,
1845 [__first, __result](_RandomAccessIterator __b, _RandomAccessIterator __e) {
1846 __internal::__brick_uninitialized_move(__b, __e, __result + (__b - __first), _IsVector{});
1847 });
1848
1849 __par_backend::__parallel_for(
1850 __backend_tag{},
1851 std::forward<_ExecutionPolicy>(__exec),
1852 __middle,
1853 __last,
1854 [__first, __middle](_RandomAccessIterator __b, _RandomAccessIterator __e) {
1855 __internal::__brick_move(__b, __e, __first + (__b - __middle), _IsVector{});
1856 });
1857
1858 __par_backend::__parallel_for(
1859 __backend_tag{},
1860 std::forward<_ExecutionPolicy>(__exec),
1861 __result,
1862 __result + __m,
1863 [__n, __m, __first, __result](_Tp* __b, _Tp* __e) {
1864 __brick_move_destroy()(__b, __e, __first + ((__n - __m) + (__b - __result)), _IsVector{});
1865 });
1866
1867 return __first + (__last - __middle);
1868 });
1869 }
1870 }
1871
1872 //------------------------------------------------------------------------
1873 // rotate_copy
1874 //------------------------------------------------------------------------
1875
1876 template <class _ForwardIterator, class _OutputIterator>
__brick_rotate_copy(_ForwardIterator __first,_ForwardIterator __middle,_ForwardIterator __last,_OutputIterator __result,std::false_type)1877 _OutputIterator __brick_rotate_copy(
1878 _ForwardIterator __first,
1879 _ForwardIterator __middle,
1880 _ForwardIterator __last,
1881 _OutputIterator __result,
1882 /*__is_vector=*/std::false_type) noexcept {
1883 return std::rotate_copy(__first, __middle, __last, __result);
1884 }
1885
1886 template <class _RandomAccessIterator1, class _RandomAccessIterator2>
__brick_rotate_copy(_RandomAccessIterator1 __first,_RandomAccessIterator1 __middle,_RandomAccessIterator1 __last,_RandomAccessIterator2 __result,std::true_type)1887 _RandomAccessIterator2 __brick_rotate_copy(
1888 _RandomAccessIterator1 __first,
1889 _RandomAccessIterator1 __middle,
1890 _RandomAccessIterator1 __last,
1891 _RandomAccessIterator2 __result,
1892 /*__is_vector=*/std::true_type) noexcept {
1893 _RandomAccessIterator2 __res = __internal::__brick_copy(__middle, __last, __result, std::true_type());
1894 return __internal::__brick_copy(__first, __middle, __res, std::true_type());
1895 }
1896
1897 template <class _Tag, class _ExecutionPolicy, class _ForwardIterator, class _OutputIterator>
__pattern_rotate_copy(_Tag,_ExecutionPolicy &&,_ForwardIterator __first,_ForwardIterator __middle,_ForwardIterator __last,_OutputIterator __result)1898 _OutputIterator __pattern_rotate_copy(
1899 _Tag,
1900 _ExecutionPolicy&&,
1901 _ForwardIterator __first,
1902 _ForwardIterator __middle,
1903 _ForwardIterator __last,
1904 _OutputIterator __result) noexcept {
1905 return __internal::__brick_rotate_copy(__first, __middle, __last, __result, typename _Tag::__is_vector{});
1906 }
1907
1908 template <class _IsVector, class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2>
__pattern_rotate_copy(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator1 __first,_RandomAccessIterator1 __middle,_RandomAccessIterator1 __last,_RandomAccessIterator2 __result)1909 _RandomAccessIterator2 __pattern_rotate_copy(
1910 __parallel_tag<_IsVector> __tag,
1911 _ExecutionPolicy&& __exec,
1912 _RandomAccessIterator1 __first,
1913 _RandomAccessIterator1 __middle,
1914 _RandomAccessIterator1 __last,
1915 _RandomAccessIterator2 __result) {
1916 using __backend_tag = typename decltype(__tag)::__backend_tag;
1917
1918 __par_backend::__parallel_for(
1919 __backend_tag{},
1920 std::forward<_ExecutionPolicy>(__exec),
1921 __first,
1922 __last,
1923 [__first, __last, __middle, __result](_RandomAccessIterator1 __b, _RandomAccessIterator1 __e) {
1924 if (__b > __middle) {
1925 __internal::__brick_copy(__b, __e, __result + (__b - __middle), _IsVector{});
1926 } else {
1927 _RandomAccessIterator2 __new_result = __result + ((__last - __middle) + (__b - __first));
1928 if (__e < __middle) {
1929 __internal::__brick_copy(__b, __e, __new_result, _IsVector{});
1930 } else {
1931 __internal::__brick_copy(__b, __middle, __new_result, _IsVector{});
1932 __internal::__brick_copy(__middle, __e, __result, _IsVector{});
1933 }
1934 }
1935 });
1936 return __result + (__last - __first);
1937 }
1938
1939 //------------------------------------------------------------------------
1940 // is_partitioned
1941 //------------------------------------------------------------------------
1942
1943 template <class _ForwardIterator, class _UnaryPredicate>
__brick_is_partitioned(_ForwardIterator __first,_ForwardIterator __last,_UnaryPredicate __pred,std::false_type)1944 bool __brick_is_partitioned(_ForwardIterator __first,
1945 _ForwardIterator __last,
1946 _UnaryPredicate __pred,
1947 /*is_vector=*/std::false_type) noexcept {
1948 return std::is_partitioned(__first, __last, __pred);
1949 }
1950
1951 template <class _RandomAccessIterator, class _UnaryPredicate>
__brick_is_partitioned(_RandomAccessIterator __first,_RandomAccessIterator __last,_UnaryPredicate __pred,std::true_type)1952 bool __brick_is_partitioned(_RandomAccessIterator __first,
1953 _RandomAccessIterator __last,
1954 _UnaryPredicate __pred,
1955 /*is_vector=*/std::true_type) noexcept {
1956 typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _SizeType;
1957 if (__first == __last) {
1958 return true;
1959 } else {
1960 _RandomAccessIterator __result = __unseq_backend::__simd_first(
1961 __first, _SizeType(0), __last - __first, [&__pred](_RandomAccessIterator __it, _SizeType __i) {
1962 return !__pred(__it[__i]);
1963 });
1964 if (__result == __last) {
1965 return true;
1966 } else {
1967 ++__result;
1968 return !__unseq_backend::__simd_or(__result, __last - __result, __pred);
1969 }
1970 }
1971 }
1972
1973 template <class _Tag, class _ExecutionPolicy, class _ForwardIterator, class _UnaryPredicate>
__pattern_is_partitioned(_Tag,_ExecutionPolicy &&,_ForwardIterator __first,_ForwardIterator __last,_UnaryPredicate __pred)1974 bool __pattern_is_partitioned(
1975 _Tag, _ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterator __last, _UnaryPredicate __pred) noexcept {
1976 return __internal::__brick_is_partitioned(__first, __last, __pred, typename _Tag::__is_vector{});
1977 }
1978
1979 template <class _IsVector, class _ExecutionPolicy, class _RandomAccessIterator, class _UnaryPredicate>
__pattern_is_partitioned(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator __first,_RandomAccessIterator __last,_UnaryPredicate __pred)1980 bool __pattern_is_partitioned(
1981 __parallel_tag<_IsVector> __tag,
1982 _ExecutionPolicy&& __exec,
1983 _RandomAccessIterator __first,
1984 _RandomAccessIterator __last,
1985 _UnaryPredicate __pred) {
1986 if (__first == __last) {
1987 return true;
1988 } else {
1989 using __backend_tag = typename decltype(__tag)::__backend_tag;
1990
1991 return __internal::__except_handler([&]() {
1992 // State of current range:
1993 // broken - current range is not partitioned by pred
1994 // all_true - all elements in current range satisfy pred
1995 // all_false - all elements in current range don't satisfy pred
1996 // true_false - elements satisfy pred are placed before elements that don't satisfy pred
1997 enum _ReduceType { __not_init = -1, __broken, __all_true, __all_false, __true_false };
1998 _ReduceType __init = __not_init;
1999
2000 // Array with states that we'll have when state from the left branch is merged with state from the right branch.
2001 // State is calculated by formula: new_state = table[left_state * 4 + right_state]
2002 _ReduceType __table[] = {
2003 __broken,
2004 __broken,
2005 __broken,
2006 __broken,
2007 __broken,
2008 __all_true,
2009 __true_false,
2010 __true_false,
2011 __broken,
2012 __broken,
2013 __all_false,
2014 __broken,
2015 __broken,
2016 __broken,
2017 __true_false,
2018 __broken};
2019
2020 __init = __par_backend::__parallel_reduce(
2021 __backend_tag{},
2022 std::forward<_ExecutionPolicy>(__exec),
2023 __first,
2024 __last,
2025 __init,
2026 [&__pred,
2027 &__table](_RandomAccessIterator __i, _RandomAccessIterator __j, _ReduceType __value) -> _ReduceType {
2028 if (__value == __broken) {
2029 return __broken;
2030 }
2031 _ReduceType __res = __not_init;
2032 // if first element satisfy pred
2033 if (__pred(*__i)) {
2034 // find first element that don't satisfy pred
2035 _RandomAccessIterator __x = __internal::__brick_find_if(__i + 1, __j, std::not_fn(__pred), _IsVector{});
2036 if (__x != __j) {
2037 // find first element after "x" that satisfy pred
2038 _RandomAccessIterator __y = __internal::__brick_find_if(__x + 1, __j, __pred, _IsVector{});
2039 // if it was found then range isn't partitioned by pred
2040 if (__y != __j) {
2041 return __broken;
2042 } else {
2043 __res = __true_false;
2044 }
2045 } else {
2046 __res = __all_true;
2047 }
2048 } else { // if first element doesn't satisfy pred
2049 // then we should find the first element that satisfy pred.
2050 // If we found it then range isn't partitioned by pred
2051 if (__internal::__brick_find_if(__i + 1, __j, __pred, _IsVector{}) != __j) {
2052 return __broken;
2053 } else {
2054 __res = __all_false;
2055 }
2056 }
2057 // if we have value from left range then we should calculate the result
2058 return (__value == -1) ? __res : __table[__value * 4 + __res];
2059 },
2060
2061 [&__table](_ReduceType __val1, _ReduceType __val2) -> _ReduceType {
2062 if (__val1 == __broken || __val2 == __broken) {
2063 return __broken;
2064 }
2065 // calculate the result for new big range
2066 return __table[__val1 * 4 + __val2];
2067 });
2068 return __init != __broken;
2069 });
2070 }
2071 }
2072
2073 //------------------------------------------------------------------------
2074 // partition
2075 //------------------------------------------------------------------------
2076
2077 template <class _ForwardIterator, class _UnaryPredicate>
__brick_partition(_ForwardIterator __first,_ForwardIterator __last,_UnaryPredicate __pred,std::false_type)2078 _ForwardIterator __brick_partition(
2079 _ForwardIterator __first,
2080 _ForwardIterator __last,
2081 _UnaryPredicate __pred,
2082 /*is_vector=*/std::false_type) noexcept {
2083 return std::partition(__first, __last, __pred);
2084 }
2085
2086 template <class _RandomAccessIterator, class _UnaryPredicate>
__brick_partition(_RandomAccessIterator __first,_RandomAccessIterator __last,_UnaryPredicate __pred,std::true_type)2087 _RandomAccessIterator __brick_partition(
2088 _RandomAccessIterator __first,
2089 _RandomAccessIterator __last,
2090 _UnaryPredicate __pred,
2091 /*is_vector=*/std::true_type) noexcept {
2092 // TODO: vectorize
2093 return std::partition(__first, __last, __pred);
2094 }
2095
2096 template <class _Tag, class _ExecutionPolicy, class _ForwardIterator, class _UnaryPredicate>
__pattern_partition(_Tag,_ExecutionPolicy &&,_ForwardIterator __first,_ForwardIterator __last,_UnaryPredicate __pred)2097 _ForwardIterator __pattern_partition(
2098 _Tag, _ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterator __last, _UnaryPredicate __pred) noexcept {
2099 return __internal::__brick_partition(__first, __last, __pred, typename _Tag::__is_vector{});
2100 }
2101
2102 template <class _IsVector, class _ExecutionPolicy, class _RandomAccessIterator, class _UnaryPredicate>
__pattern_partition(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator __first,_RandomAccessIterator __last,_UnaryPredicate __pred)2103 _RandomAccessIterator __pattern_partition(
2104 __parallel_tag<_IsVector> __tag,
2105 _ExecutionPolicy&& __exec,
2106 _RandomAccessIterator __first,
2107 _RandomAccessIterator __last,
2108 _UnaryPredicate __pred) {
2109 using __backend_tag = typename decltype(__tag)::__backend_tag;
2110
2111 // partitioned range: elements before pivot satisfy pred (true part),
2112 // elements after pivot don't satisfy pred (false part)
2113 struct _PartitionRange {
2114 _RandomAccessIterator __begin;
2115 _RandomAccessIterator __pivot;
2116 _RandomAccessIterator __end;
2117 };
2118
2119 return __internal::__except_handler([&]() {
2120 _PartitionRange __init{__last, __last, __last};
2121
2122 // lambda for merging two partitioned ranges to one partitioned range
2123 auto __reductor = [&__exec](_PartitionRange __val1, _PartitionRange __val2) -> _PartitionRange {
2124 auto __size1 = __val1.__end - __val1.__pivot;
2125 auto __size2 = __val2.__pivot - __val2.__begin;
2126 auto __new_begin = __val2.__begin - (__val1.__end - __val1.__begin);
2127
2128 // if all elements in left range satisfy pred then we can move new pivot to pivot of right range
2129 if (__val1.__end == __val1.__pivot) {
2130 return {__new_begin, __val2.__pivot, __val2.__end};
2131 }
2132 // if true part of right range greater than false part of left range
2133 // then we should swap the false part of left range and last part of true part of right range
2134 else if (__size2 > __size1) {
2135 __par_backend::__parallel_for(
2136 __backend_tag{},
2137 std::forward<_ExecutionPolicy>(__exec),
2138 __val1.__pivot,
2139 __val1.__pivot + __size1,
2140 [__val1, __val2, __size1](_RandomAccessIterator __i, _RandomAccessIterator __j) {
2141 __internal::__brick_swap_ranges(
2142 __i, __j, (__val2.__pivot - __size1) + (__i - __val1.__pivot), _IsVector{});
2143 });
2144 return {__new_begin, __val2.__pivot - __size1, __val2.__end};
2145 }
2146 // else we should swap the first part of false part of left range and true part of right range
2147 else {
2148 __par_backend::__parallel_for(
2149 __backend_tag{},
2150 std::forward<_ExecutionPolicy>(__exec),
2151 __val1.__pivot,
2152 __val1.__pivot + __size2,
2153 [__val1, __val2](_RandomAccessIterator __i, _RandomAccessIterator __j) {
2154 __internal::__brick_swap_ranges(__i, __j, __val2.__begin + (__i - __val1.__pivot), _IsVector{});
2155 });
2156 return {__new_begin, __val1.__pivot + __size2, __val2.__end};
2157 }
2158 };
2159
2160 _PartitionRange __result = __par_backend::__parallel_reduce(
2161 __backend_tag{},
2162 std::forward<_ExecutionPolicy>(__exec),
2163 __first,
2164 __last,
2165 __init,
2166 [__pred,
2167 __reductor](_RandomAccessIterator __i, _RandomAccessIterator __j, _PartitionRange __value) -> _PartitionRange {
2168 // 1. serial partition
2169 _RandomAccessIterator __pivot = __internal::__brick_partition(__i, __j, __pred, _IsVector{});
2170
2171 // 2. merging of two ranges (left and right respectively)
2172 return __reductor(__value, {__i, __pivot, __j});
2173 },
2174 __reductor);
2175 return __result.__pivot;
2176 });
2177 }
2178
2179 //------------------------------------------------------------------------
2180 // stable_partition
2181 //------------------------------------------------------------------------
2182
2183 template <class _BidirectionalIterator, class _UnaryPredicate>
__brick_stable_partition(_BidirectionalIterator __first,_BidirectionalIterator __last,_UnaryPredicate __pred,std::false_type)2184 _BidirectionalIterator __brick_stable_partition(
2185 _BidirectionalIterator __first,
2186 _BidirectionalIterator __last,
2187 _UnaryPredicate __pred,
2188 /*__is_vector=*/std::false_type) noexcept {
2189 return std::stable_partition(__first, __last, __pred);
2190 }
2191
2192 template <class _RandomAccessIterator, class _UnaryPredicate>
__brick_stable_partition(_RandomAccessIterator __first,_RandomAccessIterator __last,_UnaryPredicate __pred,std::true_type)2193 _RandomAccessIterator __brick_stable_partition(
2194 _RandomAccessIterator __first,
2195 _RandomAccessIterator __last,
2196 _UnaryPredicate __pred,
2197 /*__is_vector=*/std::true_type) noexcept {
2198 // TODO: vectorize
2199 return std::stable_partition(__first, __last, __pred);
2200 }
2201
2202 template <class _Tag, class _ExecutionPolicy, class _BidirectionalIterator, class _UnaryPredicate>
__pattern_stable_partition(_Tag,_ExecutionPolicy &&,_BidirectionalIterator __first,_BidirectionalIterator __last,_UnaryPredicate __pred)2203 _BidirectionalIterator __pattern_stable_partition(
2204 _Tag,
2205 _ExecutionPolicy&&,
2206 _BidirectionalIterator __first,
2207 _BidirectionalIterator __last,
2208 _UnaryPredicate __pred) noexcept {
2209 return __internal::__brick_stable_partition(__first, __last, __pred, typename _Tag::__is_vector{});
2210 }
2211
2212 template <class _IsVector, class _ExecutionPolicy, class _RandomAccessIterator, class _UnaryPredicate>
__pattern_stable_partition(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator __first,_RandomAccessIterator __last,_UnaryPredicate __pred)2213 _RandomAccessIterator __pattern_stable_partition(
2214 __parallel_tag<_IsVector> __tag,
2215 _ExecutionPolicy&& __exec,
2216 _RandomAccessIterator __first,
2217 _RandomAccessIterator __last,
2218 _UnaryPredicate __pred) noexcept {
2219 using __backend_tag = typename decltype(__tag)::__backend_tag;
2220
2221 // partitioned range: elements before pivot satisfy pred (true part),
2222 // elements after pivot don't satisfy pred (false part)
2223 struct _PartitionRange {
2224 _RandomAccessIterator __begin;
2225 _RandomAccessIterator __pivot;
2226 _RandomAccessIterator __end;
2227 };
2228
2229 return __internal::__except_handler([&]() {
2230 _PartitionRange __init{__last, __last, __last};
2231
2232 // lambda for merging two partitioned ranges to one partitioned range
2233 auto __reductor = [](_PartitionRange __val1, _PartitionRange __val2) -> _PartitionRange {
2234 auto __size1 = __val1.__end - __val1.__pivot;
2235 auto __new_begin = __val2.__begin - (__val1.__end - __val1.__begin);
2236
2237 // if all elements in left range satisfy pred then we can move new pivot to pivot of right range
2238 if (__val1.__end == __val1.__pivot) {
2239 return {__new_begin, __val2.__pivot, __val2.__end};
2240 }
2241 // if true part of right range greater than false part of left range
2242 // then we should swap the false part of left range and last part of true part of right range
2243 else {
2244 __internal::__brick_rotate(__val1.__pivot, __val2.__begin, __val2.__pivot, _IsVector{});
2245 return {__new_begin, __val2.__pivot - __size1, __val2.__end};
2246 }
2247 };
2248
2249 _PartitionRange __result = __par_backend::__parallel_reduce(
2250 __backend_tag{},
2251 std::forward<_ExecutionPolicy>(__exec),
2252 __first,
2253 __last,
2254 __init,
2255 [&__pred,
2256 __reductor](_RandomAccessIterator __i, _RandomAccessIterator __j, _PartitionRange __value) -> _PartitionRange {
2257 // 1. serial stable_partition
2258 _RandomAccessIterator __pivot = __internal::__brick_stable_partition(__i, __j, __pred, _IsVector{});
2259
2260 // 2. merging of two ranges (left and right respectively)
2261 return __reductor(__value, {__i, __pivot, __j});
2262 },
2263 __reductor);
2264 return __result.__pivot;
2265 });
2266 }
2267
2268 //------------------------------------------------------------------------
2269 // partition_copy
2270 //------------------------------------------------------------------------
2271
2272 template <class _ForwardIterator, class _OutputIterator1, class _OutputIterator2, class _UnaryPredicate>
__brick_partition_copy(_ForwardIterator __first,_ForwardIterator __last,_OutputIterator1 __out_true,_OutputIterator2 __out_false,_UnaryPredicate __pred,std::false_type)2273 std::pair<_OutputIterator1, _OutputIterator2> __brick_partition_copy(
2274 _ForwardIterator __first,
2275 _ForwardIterator __last,
2276 _OutputIterator1 __out_true,
2277 _OutputIterator2 __out_false,
2278 _UnaryPredicate __pred,
2279 /*is_vector=*/std::false_type) noexcept {
2280 return std::partition_copy(__first, __last, __out_true, __out_false, __pred);
2281 }
2282
2283 template <class _RandomAccessIterator1,
2284 class _RandomAccessIterator2,
2285 class _RandomAccessIterator3,
2286 class _UnaryPredicate>
__brick_partition_copy(_RandomAccessIterator1 __first,_RandomAccessIterator1 __last,_RandomAccessIterator2 __out_true,_RandomAccessIterator3 __out_false,_UnaryPredicate __pred,std::true_type)2287 std::pair<_RandomAccessIterator2, _RandomAccessIterator3> __brick_partition_copy(
2288 _RandomAccessIterator1 __first,
2289 _RandomAccessIterator1 __last,
2290 _RandomAccessIterator2 __out_true,
2291 _RandomAccessIterator3 __out_false,
2292 _UnaryPredicate __pred,
2293 /*is_vector=*/std::true_type) noexcept {
2294 #if defined(_PSTL_MONOTONIC_PRESENT)
2295 return __unseq_backend::__simd_partition_copy(__first, __last - __first, __out_true, __out_false, __pred);
2296 #else
2297 return std::partition_copy(__first, __last, __out_true, __out_false, __pred);
2298 #endif
2299 }
2300
2301 template <class _Tag,
2302 class _ExecutionPolicy,
2303 class _ForwardIterator,
2304 class _OutputIterator1,
2305 class _OutputIterator2,
2306 class _UnaryPredicate>
__pattern_partition_copy(_Tag,_ExecutionPolicy &&,_ForwardIterator __first,_ForwardIterator __last,_OutputIterator1 __out_true,_OutputIterator2 __out_false,_UnaryPredicate __pred)2307 std::pair<_OutputIterator1, _OutputIterator2> __pattern_partition_copy(
2308 _Tag,
2309 _ExecutionPolicy&&,
2310 _ForwardIterator __first,
2311 _ForwardIterator __last,
2312 _OutputIterator1 __out_true,
2313 _OutputIterator2 __out_false,
2314 _UnaryPredicate __pred) noexcept {
2315 return __internal::__brick_partition_copy(
2316 __first, __last, __out_true, __out_false, __pred, typename _Tag::__is_vector{});
2317 }
2318
2319 template <class _IsVector,
2320 class _ExecutionPolicy,
2321 class _RandomAccessIterator1,
2322 class _RandomAccessIterator2,
2323 class _RandomAccessIterator3,
2324 class _UnaryPredicate>
__pattern_partition_copy(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator1 __first,_RandomAccessIterator1 __last,_RandomAccessIterator2 __out_true,_RandomAccessIterator3 __out_false,_UnaryPredicate __pred)2325 std::pair<_RandomAccessIterator2, _RandomAccessIterator3> __pattern_partition_copy(
2326 __parallel_tag<_IsVector> __tag,
2327 _ExecutionPolicy&& __exec,
2328 _RandomAccessIterator1 __first,
2329 _RandomAccessIterator1 __last,
2330 _RandomAccessIterator2 __out_true,
2331 _RandomAccessIterator3 __out_false,
2332 _UnaryPredicate __pred) {
2333 using __backend_tag = typename decltype(__tag)::__backend_tag;
2334
2335 typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _DifferenceType;
2336 typedef std::pair<_DifferenceType, _DifferenceType> _ReturnType;
2337 const _DifferenceType __n = __last - __first;
2338 if (_DifferenceType(1) < __n) {
2339 __par_backend::__buffer<bool> __mask_buf(__n);
2340 return __internal::__except_handler([&__exec, __n, __first, __out_true, __out_false, __pred, &__mask_buf]() {
2341 bool* __mask = __mask_buf.get();
2342 _ReturnType __m{};
2343 __par_backend::__parallel_strict_scan(
2344 __backend_tag{},
2345 std::forward<_ExecutionPolicy>(__exec),
2346 __n,
2347 std::make_pair(_DifferenceType(0), _DifferenceType(0)),
2348 [=](_DifferenceType __i, _DifferenceType __len) { // Reduce
2349 return __internal::__brick_calc_mask_1<_DifferenceType>(
2350 __first + __i, __first + (__i + __len), __mask + __i, __pred, _IsVector{});
2351 },
2352 [](const _ReturnType& __x, const _ReturnType& __y) -> _ReturnType {
2353 return std::make_pair(__x.first + __y.first, __x.second + __y.second);
2354 }, // Combine
2355 [=](_DifferenceType __i, _DifferenceType __len, _ReturnType __initial) { // Scan
2356 __internal::__brick_partition_by_mask(
2357 __first + __i,
2358 __first + (__i + __len),
2359 __out_true + __initial.first,
2360 __out_false + __initial.second,
2361 __mask + __i,
2362 _IsVector{});
2363 },
2364 [&__m](_ReturnType __total) { __m = __total; });
2365 return std::make_pair(__out_true + __m.first, __out_false + __m.second);
2366 });
2367 }
2368 // trivial sequence - use serial algorithm
2369 return __internal::__brick_partition_copy(__first, __last, __out_true, __out_false, __pred, _IsVector{});
2370 }
2371
2372 //------------------------------------------------------------------------
2373 // sort
2374 //------------------------------------------------------------------------
2375
2376 template <class _Tag, class _ExecutionPolicy, class _RandomAccessIterator, class _Compare, class _IsMoveConstructible>
__pattern_sort(_Tag,_ExecutionPolicy &&,_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp,_IsMoveConstructible)2377 void __pattern_sort(_Tag,
2378 _ExecutionPolicy&&,
2379 _RandomAccessIterator __first,
2380 _RandomAccessIterator __last,
2381 _Compare __comp,
2382 _IsMoveConstructible) noexcept {
2383 std::sort(__first, __last, __comp);
2384 }
2385
2386 template <class _IsVector, class _ExecutionPolicy, class _RandomAccessIterator, class _Compare>
__pattern_sort(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp,std::true_type)2387 void __pattern_sort(__parallel_tag<_IsVector> __tag,
2388 _ExecutionPolicy&& __exec,
2389 _RandomAccessIterator __first,
2390 _RandomAccessIterator __last,
2391 _Compare __comp,
2392 /*is_move_constructible=*/std::true_type) {
2393 using __backend_tag = typename decltype(__tag)::__backend_tag;
2394
2395 __internal::__except_handler([&]() {
2396 __par_backend::__parallel_stable_sort(
2397 __backend_tag{},
2398 std::forward<_ExecutionPolicy>(__exec),
2399 __first,
2400 __last,
2401 __comp,
2402 [](_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
2403 std::sort(__first, __last, __comp);
2404 });
2405 });
2406 }
2407
2408 //------------------------------------------------------------------------
2409 // stable_sort
2410 //------------------------------------------------------------------------
2411
2412 template <class _Tag, class _ExecutionPolicy, class _RandomAccessIterator, class _Compare>
__pattern_stable_sort(_Tag,_ExecutionPolicy &&,_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp)2413 void __pattern_stable_sort(
2414 _Tag, _ExecutionPolicy&&, _RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) noexcept {
2415 std::stable_sort(__first, __last, __comp);
2416 }
2417
2418 template <class _IsVector, class _ExecutionPolicy, class _RandomAccessIterator, class _Compare>
__pattern_stable_sort(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp)2419 void __pattern_stable_sort(
2420 __parallel_tag<_IsVector> __tag,
2421 _ExecutionPolicy&& __exec,
2422 _RandomAccessIterator __first,
2423 _RandomAccessIterator __last,
2424 _Compare __comp) {
2425 using __backend_tag = typename decltype(__tag)::__backend_tag;
2426
2427 __internal::__except_handler([&]() {
2428 __par_backend::__parallel_stable_sort(
2429 __backend_tag{},
2430 std::forward<_ExecutionPolicy>(__exec),
2431 __first,
2432 __last,
2433 __comp,
2434 [](_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
2435 std::stable_sort(__first, __last, __comp);
2436 });
2437 });
2438 }
2439
2440 //------------------------------------------------------------------------
2441 // partial_sort
2442 //------------------------------------------------------------------------
2443
2444 template <class _Tag, class _ExecutionPolicy, class _RandomAccessIterator, class _Compare>
__pattern_partial_sort(_Tag,_ExecutionPolicy &&,_RandomAccessIterator __first,_RandomAccessIterator __middle,_RandomAccessIterator __last,_Compare __comp)2445 void __pattern_partial_sort(
2446 _Tag,
2447 _ExecutionPolicy&&,
2448 _RandomAccessIterator __first,
2449 _RandomAccessIterator __middle,
2450 _RandomAccessIterator __last,
2451 _Compare __comp) noexcept {
2452 std::partial_sort(__first, __middle, __last, __comp);
2453 }
2454
2455 template <class _IsVector, class _ExecutionPolicy, class _RandomAccessIterator, class _Compare>
__pattern_partial_sort(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator __first,_RandomAccessIterator __middle,_RandomAccessIterator __last,_Compare __comp)2456 void __pattern_partial_sort(
2457 __parallel_tag<_IsVector> __tag,
2458 _ExecutionPolicy&& __exec,
2459 _RandomAccessIterator __first,
2460 _RandomAccessIterator __middle,
2461 _RandomAccessIterator __last,
2462 _Compare __comp) {
2463 using __backend_tag = typename decltype(__tag)::__backend_tag;
2464
2465 const auto __n = __middle - __first;
2466 if (__n == 0)
2467 return;
2468
2469 __internal::__except_handler([&]() {
2470 __par_backend::__parallel_stable_sort(
2471 __backend_tag{},
2472 std::forward<_ExecutionPolicy>(__exec),
2473 __first,
2474 __last,
2475 __comp,
2476 [__n](_RandomAccessIterator __begin, _RandomAccessIterator __end, _Compare __comp) {
2477 if (__n < __end - __begin)
2478 std::partial_sort(__begin, __begin + __n, __end, __comp);
2479 else
2480 std::sort(__begin, __end, __comp);
2481 },
2482 __n);
2483 });
2484 }
2485
2486 //------------------------------------------------------------------------
2487 // partial_sort_copy
2488 //------------------------------------------------------------------------
2489
2490 template <class _Tag, class _ExecutionPolicy, class _ForwardIterator, class _RandomAccessIterator, class _Compare>
__pattern_partial_sort_copy(_Tag,_ExecutionPolicy &&,_ForwardIterator __first,_ForwardIterator __last,_RandomAccessIterator __d_first,_RandomAccessIterator __d_last,_Compare __comp)2491 _RandomAccessIterator __pattern_partial_sort_copy(
2492 _Tag,
2493 _ExecutionPolicy&&,
2494 _ForwardIterator __first,
2495 _ForwardIterator __last,
2496 _RandomAccessIterator __d_first,
2497 _RandomAccessIterator __d_last,
2498 _Compare __comp) noexcept {
2499 return std::partial_sort_copy(__first, __last, __d_first, __d_last, __comp);
2500 }
2501
2502 template <class _IsVector,
2503 class _ExecutionPolicy,
2504 class _RandomAccessIterator1,
2505 class _RandomAccessIterator2,
2506 class _Compare>
__pattern_partial_sort_copy(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator1 __first,_RandomAccessIterator1 __last,_RandomAccessIterator2 __d_first,_RandomAccessIterator2 __d_last,_Compare __comp)2507 _RandomAccessIterator2 __pattern_partial_sort_copy(
2508 __parallel_tag<_IsVector> __tag,
2509 _ExecutionPolicy&& __exec,
2510 _RandomAccessIterator1 __first,
2511 _RandomAccessIterator1 __last,
2512 _RandomAccessIterator2 __d_first,
2513 _RandomAccessIterator2 __d_last,
2514 _Compare __comp) {
2515 using __backend_tag = typename decltype(__tag)::__backend_tag;
2516
2517 if (__last == __first || __d_last == __d_first) {
2518 return __d_first;
2519 }
2520 auto __n1 = __last - __first;
2521 auto __n2 = __d_last - __d_first;
2522 return __internal::__except_handler([&]() {
2523 if (__n2 >= __n1) {
2524 __par_backend::__parallel_stable_sort(
2525 __backend_tag{},
2526 std::forward<_ExecutionPolicy>(__exec),
2527 __d_first,
2528 __d_first + __n1,
2529 __comp,
2530 [__first, __d_first](_RandomAccessIterator2 __i, _RandomAccessIterator2 __j, _Compare __comp) {
2531 _RandomAccessIterator1 __i1 = __first + (__i - __d_first);
2532 _RandomAccessIterator1 __j1 = __first + (__j - __d_first);
2533
2534 // 1. Copy elements from input to output
2535 #if !defined(_PSTL_ICC_18_OMP_SIMD_BROKEN)
2536 __internal::__brick_copy(__i1, __j1, __i, _IsVector{});
2537 #else
2538 std::copy(__i1, __j1, __i);
2539 #endif
2540 // 2. Sort elements in output sequence
2541 std::sort(__i, __j, __comp);
2542 },
2543 __n1);
2544 return __d_first + __n1;
2545 } else {
2546 typedef typename std::iterator_traits<_RandomAccessIterator1>::value_type _T1;
2547 typedef typename std::iterator_traits<_RandomAccessIterator2>::value_type _T2;
2548 __par_backend::__buffer<_T1> __buf(__n1);
2549 _T1* __r = __buf.get();
2550
2551 __par_backend::__parallel_stable_sort(
2552 __backend_tag{},
2553 std::forward<_ExecutionPolicy>(__exec),
2554 __r,
2555 __r + __n1,
2556 __comp,
2557 [__n2, __first, __r](_T1* __i, _T1* __j, _Compare __comp) {
2558 _RandomAccessIterator1 __it = __first + (__i - __r);
2559
2560 // 1. Copy elements from input to raw memory
2561 for (_T1* __k = __i; __k != __j; ++__k, ++__it) {
2562 ::new (__k) _T2(*__it);
2563 }
2564
2565 // 2. Sort elements in temporary __buffer
2566 if (__n2 < __j - __i)
2567 std::partial_sort(__i, __i + __n2, __j, __comp);
2568 else
2569 std::sort(__i, __j, __comp);
2570 },
2571 __n2);
2572
2573 // 3. Move elements from temporary __buffer to output
2574 __par_backend::__parallel_for(
2575 __backend_tag{},
2576 std::forward<_ExecutionPolicy>(__exec),
2577 __r,
2578 __r + __n2,
2579 [__r, __d_first](_T1* __i, _T1* __j) {
2580 __brick_move_destroy()(__i, __j, __d_first + (__i - __r), _IsVector{});
2581 });
2582 __par_backend::__parallel_for(
2583 __backend_tag{}, std::forward<_ExecutionPolicy>(__exec), __r + __n2, __r + __n1, [](_T1* __i, _T1* __j) {
2584 __brick_destroy(__i, __j, _IsVector{});
2585 });
2586
2587 return __d_first + __n2;
2588 }
2589 });
2590 }
2591
2592 //------------------------------------------------------------------------
2593 // adjacent_find
2594 //------------------------------------------------------------------------
2595 template <class _RandomAccessIterator, class _BinaryPredicate>
__brick_adjacent_find(_RandomAccessIterator __first,_RandomAccessIterator __last,_BinaryPredicate __pred,std::true_type,bool __or_semantic)2596 _RandomAccessIterator __brick_adjacent_find(
2597 _RandomAccessIterator __first,
2598 _RandomAccessIterator __last,
2599 _BinaryPredicate __pred,
2600 /* IsVector = */ std::true_type,
2601 bool __or_semantic) noexcept {
2602 return __unseq_backend::__simd_adjacent_find(__first, __last, __pred, __or_semantic);
2603 }
2604
2605 template <class _ForwardIterator, class _BinaryPredicate>
__brick_adjacent_find(_ForwardIterator __first,_ForwardIterator __last,_BinaryPredicate __pred,std::false_type,bool)2606 _ForwardIterator __brick_adjacent_find(
2607 _ForwardIterator __first,
2608 _ForwardIterator __last,
2609 _BinaryPredicate __pred,
2610 /* IsVector = */ std::false_type,
2611 bool) noexcept {
2612 return std::adjacent_find(__first, __last, __pred);
2613 }
2614
2615 template <class _Tag, class _ExecutionPolicy, class _ForwardIterator, class _BinaryPredicate>
__pattern_adjacent_find(_Tag,_ExecutionPolicy &&,_ForwardIterator __first,_ForwardIterator __last,_BinaryPredicate __pred,bool __or_semantic)2616 _ForwardIterator __pattern_adjacent_find(
2617 _Tag,
2618 _ExecutionPolicy&&,
2619 _ForwardIterator __first,
2620 _ForwardIterator __last,
2621 _BinaryPredicate __pred,
2622 bool __or_semantic) noexcept {
2623 return __internal::__brick_adjacent_find(__first, __last, __pred, typename _Tag::__is_vector{}, __or_semantic);
2624 }
2625
2626 template <class _IsVector, class _ExecutionPolicy, class _RandomAccessIterator, class _BinaryPredicate>
__pattern_adjacent_find(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator __first,_RandomAccessIterator __last,_BinaryPredicate __pred,bool __or_semantic)2627 _RandomAccessIterator __pattern_adjacent_find(
2628 __parallel_tag<_IsVector> __tag,
2629 _ExecutionPolicy&& __exec,
2630 _RandomAccessIterator __first,
2631 _RandomAccessIterator __last,
2632 _BinaryPredicate __pred,
2633 bool __or_semantic) {
2634 if (__last - __first < 2)
2635 return __last;
2636
2637 using __backend_tag = typename decltype(__tag)::__backend_tag;
2638
2639 return __internal::__except_handler([&]() {
2640 return __par_backend::__parallel_reduce(
2641 __backend_tag{},
2642 std::forward<_ExecutionPolicy>(__exec),
2643 __first,
2644 __last,
2645 __last,
2646 [__last, __pred, __or_semantic](
2647 _RandomAccessIterator __begin, _RandomAccessIterator __end, _RandomAccessIterator __value)
2648 -> _RandomAccessIterator {
2649 // TODO: investigate performance benefits from the use of shared variable for the result,
2650 // checking (compare_and_swap idiom) its __value at __first.
2651 if (__or_semantic && __value < __last) { // found
2652 __par_backend::__cancel_execution();
2653 return __value;
2654 }
2655
2656 if (__value > __begin) {
2657 // modify __end to check the predicate on the boundary __values;
2658 // TODO: to use a custom range with boundaries overlapping
2659 // TODO: investigate what if we remove "if" below and run algorithm on range [__first, __last-1)
2660 // then check the pair [__last-1, __last)
2661 if (__end != __last)
2662 ++__end;
2663
2664 // correct the global result iterator if the "brick" returns a local "__last"
2665 const _RandomAccessIterator __res =
2666 __internal::__brick_adjacent_find(__begin, __end, __pred, _IsVector{}, __or_semantic);
2667 if (__res < __end)
2668 __value = __res;
2669 }
2670 return __value;
2671 },
2672 [](_RandomAccessIterator __x, _RandomAccessIterator __y) -> _RandomAccessIterator {
2673 return __x < __y ? __x : __y;
2674 } // reduce a __value
2675 );
2676 });
2677 }
2678
2679 //------------------------------------------------------------------------
2680 // nth_element
2681 //------------------------------------------------------------------------
2682
2683 template <class _Tag, class _ExecutionPolicy, class _RandomAccessIterator, class _Compare>
__pattern_nth_element(_Tag,_ExecutionPolicy &&,_RandomAccessIterator __first,_RandomAccessIterator __nth,_RandomAccessIterator __last,_Compare __comp)2684 void __pattern_nth_element(
2685 _Tag,
2686 _ExecutionPolicy&&,
2687 _RandomAccessIterator __first,
2688 _RandomAccessIterator __nth,
2689 _RandomAccessIterator __last,
2690 _Compare __comp) noexcept {
2691 std::nth_element(__first, __nth, __last, __comp);
2692 }
2693
2694 template <class _IsVector, class _ExecutionPolicy, class _RandomAccessIterator, class _Compare>
__pattern_nth_element(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator __first,_RandomAccessIterator __nth,_RandomAccessIterator __last,_Compare __comp)2695 void __pattern_nth_element(
2696 __parallel_tag<_IsVector> __tag,
2697 _ExecutionPolicy&& __exec,
2698 _RandomAccessIterator __first,
2699 _RandomAccessIterator __nth,
2700 _RandomAccessIterator __last,
2701 _Compare __comp) noexcept {
2702 if (__first == __last || __nth == __last) {
2703 return;
2704 }
2705
2706 using std::iter_swap;
2707 typedef typename std::iterator_traits<_RandomAccessIterator>::value_type _Tp;
2708 _RandomAccessIterator __x;
2709 do {
2710 __x = __internal::__pattern_partition(
2711 __tag, std::forward<_ExecutionPolicy>(__exec), __first + 1, __last, [&__comp, __first](const _Tp& __x) {
2712 return __comp(__x, *__first);
2713 });
2714 --__x;
2715 if (__x != __first) {
2716 iter_swap(__first, __x);
2717 }
2718 // if x > nth then our new range for partition is [first, x)
2719 if (__x - __nth > 0) {
2720 __last = __x;
2721 }
2722 // if x < nth then our new range for partition is [x, last)
2723 else if (__x - __nth < 0) {
2724 // if *x == *nth then we can start new partition with x+1
2725 if (!__comp(*__nth, *__x) && !__comp(*__x, *__nth)) {
2726 ++__x;
2727 } else {
2728 iter_swap(__nth, __x);
2729 }
2730 __first = __x;
2731 }
2732 } while (__x != __nth);
2733 }
2734
2735 //------------------------------------------------------------------------
2736 // generate, generate_n
2737 //------------------------------------------------------------------------
2738 template <class _RandomAccessIterator, class _Generator>
__brick_generate(_RandomAccessIterator __first,_RandomAccessIterator __last,_Generator __g,std::true_type)2739 void __brick_generate(_RandomAccessIterator __first,
2740 _RandomAccessIterator __last,
2741 _Generator __g,
2742 /* is_vector = */ std::true_type) noexcept {
2743 __unseq_backend::__simd_generate_n(__first, __last - __first, __g);
2744 }
2745
2746 template <class _ForwardIterator, class _Generator>
__brick_generate(_ForwardIterator __first,_ForwardIterator __last,_Generator __g,std::false_type)2747 void __brick_generate(_ForwardIterator __first,
2748 _ForwardIterator __last,
2749 _Generator __g,
2750 /* is_vector = */ std::false_type) noexcept {
2751 std::generate(__first, __last, __g);
2752 }
2753
2754 template <class _Tag, class _ExecutionPolicy, class _ForwardIterator, class _Generator>
__pattern_generate(_Tag,_ExecutionPolicy &&,_ForwardIterator __first,_ForwardIterator __last,_Generator __g)2755 void __pattern_generate(
2756 _Tag, _ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterator __last, _Generator __g) noexcept {
2757 __internal::__brick_generate(__first, __last, __g, typename _Tag::__is_vector{});
2758 }
2759
2760 template <class _IsVector, class _ExecutionPolicy, class _RandomAccessIterator, class _Generator>
__pattern_generate(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator __first,_RandomAccessIterator __last,_Generator __g)2761 _RandomAccessIterator __pattern_generate(
2762 __parallel_tag<_IsVector> __tag,
2763 _ExecutionPolicy&& __exec,
2764 _RandomAccessIterator __first,
2765 _RandomAccessIterator __last,
2766 _Generator __g) {
2767 using __backend_tag = typename decltype(__tag)::__backend_tag;
2768
2769 return __internal::__except_handler([&]() {
2770 __par_backend::__parallel_for(
2771 __backend_tag{},
2772 std::forward<_ExecutionPolicy>(__exec),
2773 __first,
2774 __last,
2775 [__g](_RandomAccessIterator __begin, _RandomAccessIterator __end) {
2776 __internal::__brick_generate(__begin, __end, __g, _IsVector{});
2777 });
2778 return __last;
2779 });
2780 }
2781
2782 template <class _RandomAccessIterator, class Size, class _Generator>
__brick_generate_n(_RandomAccessIterator __first,Size __count,_Generator __g,std::true_type)2783 _RandomAccessIterator __brick_generate_n(
2784 _RandomAccessIterator __first,
2785 Size __count,
2786 _Generator __g,
2787 /* is_vector = */ std::true_type) noexcept {
2788 return __unseq_backend::__simd_generate_n(__first, __count, __g);
2789 }
2790
2791 template <class OutputIterator, class Size, class _Generator>
2792 OutputIterator
__brick_generate_n(OutputIterator __first,Size __count,_Generator __g,std::false_type)2793 __brick_generate_n(OutputIterator __first, Size __count, _Generator __g, /* is_vector = */ std::false_type) noexcept {
2794 return std::generate_n(__first, __count, __g);
2795 }
2796
2797 template <class _Tag, class _ExecutionPolicy, class _OutputIterator, class _Size, class _Generator>
2798 _OutputIterator
__pattern_generate_n(_Tag,_ExecutionPolicy &&,_OutputIterator __first,_Size __count,_Generator __g)2799 __pattern_generate_n(_Tag, _ExecutionPolicy&&, _OutputIterator __first, _Size __count, _Generator __g) noexcept {
2800 return __internal::__brick_generate_n(__first, __count, __g, typename _Tag::__is_vector{});
2801 }
2802
2803 template <class _IsVector, class _ExecutionPolicy, class _RandomAccessIterator, class _Size, class _Generator>
__pattern_generate_n(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator __first,_Size __count,_Generator __g)2804 _RandomAccessIterator __pattern_generate_n(
2805 __parallel_tag<_IsVector> __tag,
2806 _ExecutionPolicy&& __exec,
2807 _RandomAccessIterator __first,
2808 _Size __count,
2809 _Generator __g) {
2810 static_assert(__are_random_access_iterators<_RandomAccessIterator>::value,
2811 "Pattern-brick error. Should be a random access iterator.");
2812 return __internal::__pattern_generate(__tag, std::forward<_ExecutionPolicy>(__exec), __first, __first + __count, __g);
2813 }
2814
2815 //------------------------------------------------------------------------
2816 // remove
2817 //------------------------------------------------------------------------
2818
2819 template <class _ForwardIterator, class _UnaryPredicate>
__brick_remove_if(_ForwardIterator __first,_ForwardIterator __last,_UnaryPredicate __pred,std::false_type)2820 _ForwardIterator __brick_remove_if(
2821 _ForwardIterator __first,
2822 _ForwardIterator __last,
2823 _UnaryPredicate __pred,
2824 /* __is_vector = */ std::false_type) noexcept {
2825 return std::remove_if(__first, __last, __pred);
2826 }
2827
2828 template <class _RandomAccessIterator, class _UnaryPredicate>
__brick_remove_if(_RandomAccessIterator __first,_RandomAccessIterator __last,_UnaryPredicate __pred,std::true_type)2829 _RandomAccessIterator __brick_remove_if(
2830 _RandomAccessIterator __first,
2831 _RandomAccessIterator __last,
2832 _UnaryPredicate __pred,
2833 /* __is_vector = */ std::true_type) noexcept {
2834 #if defined(_PSTL_MONOTONIC_PRESENT)
2835 return __unseq_backend::__simd_remove_if(__first, __last - __first, __pred);
2836 #else
2837 return std::remove_if(__first, __last, __pred);
2838 #endif
2839 }
2840
2841 template <class _Tag, class _ExecutionPolicy, class _ForwardIterator, class _UnaryPredicate>
__pattern_remove_if(_Tag,_ExecutionPolicy &&,_ForwardIterator __first,_ForwardIterator __last,_UnaryPredicate __pred)2842 _ForwardIterator __pattern_remove_if(
2843 _Tag, _ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterator __last, _UnaryPredicate __pred) noexcept {
2844 return __internal::__brick_remove_if(__first, __last, __pred, typename _Tag::__is_vector{});
2845 }
2846
2847 template <class _IsVector, class _ExecutionPolicy, class _RandomAccessIterator, class _UnaryPredicate>
__pattern_remove_if(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator __first,_RandomAccessIterator __last,_UnaryPredicate __pred)2848 _RandomAccessIterator __pattern_remove_if(
2849 __parallel_tag<_IsVector> __tag,
2850 _ExecutionPolicy&& __exec,
2851 _RandomAccessIterator __first,
2852 _RandomAccessIterator __last,
2853 _UnaryPredicate __pred) noexcept {
2854 typedef typename std::iterator_traits<_RandomAccessIterator>::reference _ReferenceType;
2855
2856 if (__first == __last || __first + 1 == __last) {
2857 // Trivial sequence - use serial algorithm
2858 return __internal::__brick_remove_if(__first, __last, __pred, _IsVector{});
2859 }
2860
2861 return __internal::__remove_elements(
2862 __tag,
2863 std::forward<_ExecutionPolicy>(__exec),
2864 __first,
2865 __last,
2866 [&__pred](bool* __b, bool* __e, _RandomAccessIterator __it) {
2867 __internal::__brick_walk2(
2868 __b, __e, __it, [&__pred](bool& __x, _ReferenceType __y) { __x = !__pred(__y); }, _IsVector{});
2869 });
2870 }
2871
2872 //------------------------------------------------------------------------
2873 // inplace_merge
2874 //------------------------------------------------------------------------
2875 template <class _BidirectionalIterator, class _Compare>
__brick_inplace_merge(_BidirectionalIterator __first,_BidirectionalIterator __middle,_BidirectionalIterator __last,_Compare __comp,std::false_type)2876 void __brick_inplace_merge(
2877 _BidirectionalIterator __first,
2878 _BidirectionalIterator __middle,
2879 _BidirectionalIterator __last,
2880 _Compare __comp,
2881 /* __is_vector = */ std::false_type) noexcept {
2882 std::inplace_merge(__first, __middle, __last, __comp);
2883 }
2884
2885 template <class _RandomAccessIterator, class _Compare>
__brick_inplace_merge(_RandomAccessIterator __first,_RandomAccessIterator __middle,_RandomAccessIterator __last,_Compare __comp,std::true_type)2886 void __brick_inplace_merge(
2887 _RandomAccessIterator __first,
2888 _RandomAccessIterator __middle,
2889 _RandomAccessIterator __last,
2890 _Compare __comp,
2891 /* __is_vector = */ std::true_type) noexcept {
2892 // TODO: vectorize
2893 std::inplace_merge(__first, __middle, __last, __comp);
2894 }
2895
2896 template <class _Tag, class _ExecutionPolicy, class _BidirectionalIterator, class _Compare>
__pattern_inplace_merge(_Tag,_ExecutionPolicy &&,_BidirectionalIterator __first,_BidirectionalIterator __middle,_BidirectionalIterator __last,_Compare __comp)2897 void __pattern_inplace_merge(
2898 _Tag,
2899 _ExecutionPolicy&&,
2900 _BidirectionalIterator __first,
2901 _BidirectionalIterator __middle,
2902 _BidirectionalIterator __last,
2903 _Compare __comp) noexcept {
2904 __internal::__brick_inplace_merge(__first, __middle, __last, __comp, typename _Tag::__is_vector{});
2905 }
2906
2907 template <class _IsVector, class _ExecutionPolicy, class _RandomAccessIterator, class _Compare>
__pattern_inplace_merge(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator __first,_RandomAccessIterator __middle,_RandomAccessIterator __last,_Compare __comp)2908 void __pattern_inplace_merge(
2909 __parallel_tag<_IsVector> __tag,
2910 _ExecutionPolicy&& __exec,
2911 _RandomAccessIterator __first,
2912 _RandomAccessIterator __middle,
2913 _RandomAccessIterator __last,
2914 _Compare __comp) {
2915 using __backend_tag = typename decltype(__tag)::__backend_tag;
2916
2917 if (__first == __last || __first == __middle || __middle == __last) {
2918 return;
2919 }
2920 typedef typename std::iterator_traits<_RandomAccessIterator>::value_type _Tp;
2921 auto __n = __last - __first;
2922 __par_backend::__buffer<_Tp> __buf(__n);
2923 _Tp* __r = __buf.get();
2924 __internal::__except_handler([&]() {
2925 auto __move_values = [](_RandomAccessIterator __x, _Tp* __z) {
2926 __internal::__invoke_if_else(
2927 std::is_trivial<_Tp>(),
2928 [&]() { *__z = std::move(*__x); },
2929 [&]() { ::new (std::addressof(*__z)) _Tp(std::move(*__x)); });
2930 };
2931
2932 auto __move_sequences = [](_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Tp* __first2) {
2933 return __internal::__brick_uninitialized_move(__first1, __last1, __first2, _IsVector());
2934 };
2935
2936 __par_backend::__parallel_merge(
2937 __backend_tag{},
2938 std::forward<_ExecutionPolicy>(__exec),
2939 __first,
2940 __middle,
2941 __middle,
2942 __last,
2943 __r,
2944 __comp,
2945 [__n, __move_values, __move_sequences](
2946 _RandomAccessIterator __f1,
2947 _RandomAccessIterator __l1,
2948 _RandomAccessIterator __f2,
2949 _RandomAccessIterator __l2,
2950 _Tp* __f3,
2951 _Compare __comp) {
2952 (__utils::__serial_move_merge(__n))(
2953 __f1, __l1, __f2, __l2, __f3, __comp, __move_values, __move_values, __move_sequences, __move_sequences);
2954 return __f3 + (__l1 - __f1) + (__l2 - __f2);
2955 });
2956 __par_backend::__parallel_for(
2957 __backend_tag{}, std::forward<_ExecutionPolicy>(__exec), __r, __r + __n, [__r, __first](_Tp* __i, _Tp* __j) {
2958 __brick_move_destroy()(__i, __j, __first + (__i - __r), _IsVector{});
2959 });
2960 });
2961 }
2962
2963 //------------------------------------------------------------------------
2964 // includes
2965 //------------------------------------------------------------------------
2966
2967 template <class _Tag, class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Compare>
__pattern_includes(_Tag,_ExecutionPolicy &&,_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_ForwardIterator2 __last2,_Compare __comp)2968 bool __pattern_includes(
2969 _Tag,
2970 _ExecutionPolicy&&,
2971 _ForwardIterator1 __first1,
2972 _ForwardIterator1 __last1,
2973 _ForwardIterator2 __first2,
2974 _ForwardIterator2 __last2,
2975 _Compare __comp) noexcept {
2976 return std::includes(__first1, __last1, __first2, __last2, __comp);
2977 }
2978
2979 template <class _IsVector,
2980 class _ExecutionPolicy,
2981 class _RandomAccessIterator1,
2982 class _RandomAccessIterator2,
2983 class _Compare>
__pattern_includes(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator1 __first1,_RandomAccessIterator1 __last1,_RandomAccessIterator2 __first2,_RandomAccessIterator2 __last2,_Compare __comp)2984 bool __pattern_includes(
2985 __parallel_tag<_IsVector> __tag,
2986 _ExecutionPolicy&& __exec,
2987 _RandomAccessIterator1 __first1,
2988 _RandomAccessIterator1 __last1,
2989 _RandomAccessIterator2 __first2,
2990 _RandomAccessIterator2 __last2,
2991 _Compare __comp) {
2992 using __backend_tag = typename decltype(__tag)::__backend_tag;
2993
2994 if (__first2 >= __last2)
2995 return true;
2996
2997 if (__first1 >= __last1 || __comp(*__first2, *__first1) || __comp(*(__last1 - 1), *(__last2 - 1)))
2998 return false;
2999
3000 __first1 = std::lower_bound(__first1, __last1, *__first2, __comp);
3001 if (__first1 == __last1)
3002 return false;
3003
3004 if (__last2 - __first2 == 1)
3005 return !__comp(*__first1, *__first2) && !__comp(*__first2, *__first1);
3006
3007 return __internal::__except_handler([&]() {
3008 return !__internal::__parallel_or(
3009 __backend_tag{},
3010 std::forward<_ExecutionPolicy>(__exec),
3011 __first2,
3012 __last2,
3013 [__first1, __last1, __first2, __last2, &__comp](_RandomAccessIterator2 __i, _RandomAccessIterator2 __j) {
3014 _LIBCPP_ASSERT_UNCATEGORIZED(__j > __i, "");
3015 //_LIBCPP_ASSERT_UNCATEGORIZED(__j - __i > 1, "");
3016
3017 // 1. moving boundaries to "consume" subsequence of equal elements
3018 auto __is_equal = [&__comp](_RandomAccessIterator2 __a, _RandomAccessIterator2 __b) -> bool {
3019 return !__comp(*__a, *__b) && !__comp(*__b, *__a);
3020 };
3021
3022 // 1.1 left bound, case "aaa[aaaxyz...]" - searching "x"
3023 if (__i > __first2 && __is_equal(__i, __i - 1)) {
3024 // whole subrange continues to content equal elements - return "no op"
3025 if (__is_equal(__i, __j - 1))
3026 return false;
3027
3028 __i = std::upper_bound(__i, __last2, *__i, __comp);
3029 }
3030
3031 // 1.2 right bound, case "[...aaa]aaaxyz" - searching "x"
3032 if (__j < __last2 && __is_equal(__j - 1, __j))
3033 __j = std::upper_bound(__j, __last2, *__j, __comp);
3034
3035 // 2. testing is __a subsequence of the second range included into the first range
3036 auto __b = std::lower_bound(__first1, __last1, *__i, __comp);
3037
3038 _LIBCPP_ASSERT_UNCATEGORIZED(!__comp(*(__last1 - 1), *__b), "");
3039 _LIBCPP_ASSERT_UNCATEGORIZED(!__comp(*(__j - 1), *__i), "");
3040 return !std::includes(__b, __last1, __i, __j, __comp);
3041 });
3042 });
3043 }
3044
3045 constexpr auto __set_algo_cut_off = 1000;
3046
3047 template <class _IsVector,
3048 class _ExecutionPolicy,
3049 class _ForwardIterator1,
3050 class _ForwardIterator2,
3051 class _OutputIterator,
3052 class _Compare,
3053 class _SizeFunction,
3054 class _SetOP>
__parallel_set_op(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_ForwardIterator2 __last2,_OutputIterator __result,_Compare __comp,_SizeFunction __size_func,_SetOP __set_op)3055 _OutputIterator __parallel_set_op(
3056 __parallel_tag<_IsVector> __tag,
3057 _ExecutionPolicy&& __exec,
3058 _ForwardIterator1 __first1,
3059 _ForwardIterator1 __last1,
3060 _ForwardIterator2 __first2,
3061 _ForwardIterator2 __last2,
3062 _OutputIterator __result,
3063 _Compare __comp,
3064 _SizeFunction __size_func,
3065 _SetOP __set_op) {
3066 using __backend_tag = typename decltype(__tag)::__backend_tag;
3067
3068 typedef typename std::iterator_traits<_ForwardIterator1>::difference_type _DifferenceType;
3069 typedef typename std::iterator_traits<_OutputIterator>::value_type _Tp;
3070
3071 struct _SetRange {
3072 _DifferenceType __pos, __len, __buf_pos;
3073 bool empty() const { return __len == 0; }
3074 };
3075
3076 const _DifferenceType __n1 = __last1 - __first1;
3077 const _DifferenceType __n2 = __last2 - __first2;
3078
3079 __par_backend::__buffer<_Tp> __buf(__size_func(__n1, __n2));
3080
3081 return __internal::__except_handler(
3082 [&__exec, __n1, __first1, __last1, __first2, __last2, __result, __comp, __size_func, __set_op, &__buf]() {
3083 auto __buffer = __buf.get();
3084 _DifferenceType __m{};
3085 auto __scan = [=](_DifferenceType, _DifferenceType, const _SetRange& __s) { // Scan
3086 if (!__s.empty())
3087 __brick_move_destroy()(
3088 __buffer + __s.__buf_pos, __buffer + (__s.__buf_pos + __s.__len), __result + __s.__pos, _IsVector{});
3089 };
3090 __par_backend::__parallel_strict_scan(
3091 __backend_tag{},
3092 std::forward<_ExecutionPolicy>(__exec),
3093 __n1,
3094 _SetRange{0, 0, 0}, //-1, 0},
3095 [=](_DifferenceType __i, _DifferenceType __len) { // Reduce
3096 //[__b; __e) - a subrange of the first sequence, to reduce
3097 _ForwardIterator1 __b = __first1 + __i, __e = __first1 + (__i + __len);
3098
3099 // try searching for the first element which not equal to *__b
3100 if (__b != __first1)
3101 __b = std::upper_bound(__b, __last1, *__b, __comp);
3102
3103 // try searching for the first element which not equal to *__e
3104 if (__e != __last1)
3105 __e = std::upper_bound(__e, __last1, *__e, __comp);
3106
3107 // check is [__b; __e) empty
3108 if (__e - __b < 1) {
3109 _ForwardIterator2 __bb = __last2;
3110 if (__b != __last1)
3111 __bb = std::lower_bound(__first2, __last2, *__b, __comp);
3112
3113 const _DifferenceType __buf_pos = __size_func((__b - __first1), (__bb - __first2));
3114 return _SetRange{0, 0, __buf_pos};
3115 }
3116
3117 // try searching for "corresponding" subrange [__bb; __ee) in the second sequence
3118 _ForwardIterator2 __bb = __first2;
3119 if (__b != __first1)
3120 __bb = std::lower_bound(__first2, __last2, *__b, __comp);
3121
3122 _ForwardIterator2 __ee = __last2;
3123 if (__e != __last1)
3124 __ee = std::lower_bound(__bb, __last2, *__e, __comp);
3125
3126 const _DifferenceType __buf_pos = __size_func((__b - __first1), (__bb - __first2));
3127 auto __buffer_b = __buffer + __buf_pos;
3128 auto __res = __set_op(__b, __e, __bb, __ee, __buffer_b, __comp);
3129
3130 return _SetRange{0, __res - __buffer_b, __buf_pos};
3131 },
3132 [](const _SetRange& __a, const _SetRange& __b) { // Combine
3133 if (__b.__buf_pos > __a.__buf_pos || ((__b.__buf_pos == __a.__buf_pos) && !__b.empty()))
3134 return _SetRange{__a.__pos + __a.__len + __b.__pos, __b.__len, __b.__buf_pos};
3135 return _SetRange{__b.__pos + __b.__len + __a.__pos, __a.__len, __a.__buf_pos};
3136 },
3137 __scan, // Scan
3138 [&__m, &__scan](const _SetRange& __total) { // Apex
3139 // final scan
3140 __scan(0, 0, __total);
3141 __m = __total.__pos + __total.__len;
3142 });
3143 return __result + __m;
3144 });
3145 }
3146
3147 // a shared parallel pattern for '__pattern_set_union' and '__pattern_set_symmetric_difference'
3148 template <class _Tag,
3149 class _ExecutionPolicy,
3150 class _ForwardIterator1,
3151 class _ForwardIterator2,
3152 class _OutputIterator,
3153 class _Compare,
3154 class _SetUnionOp>
__parallel_set_union_op(_Tag __tag,_ExecutionPolicy && __exec,_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_ForwardIterator2 __last2,_OutputIterator __result,_Compare __comp,_SetUnionOp __set_union_op)3155 _OutputIterator __parallel_set_union_op(
3156 _Tag __tag,
3157 _ExecutionPolicy&& __exec,
3158 _ForwardIterator1 __first1,
3159 _ForwardIterator1 __last1,
3160 _ForwardIterator2 __first2,
3161 _ForwardIterator2 __last2,
3162 _OutputIterator __result,
3163 _Compare __comp,
3164 _SetUnionOp __set_union_op) {
3165 using __backend_tag = typename decltype(__tag)::__backend_tag;
3166
3167 typedef typename std::iterator_traits<_ForwardIterator1>::difference_type _DifferenceType;
3168
3169 const auto __n1 = __last1 - __first1;
3170 const auto __n2 = __last2 - __first2;
3171
3172 auto copy_range1 = [](_ForwardIterator1 __begin, _ForwardIterator1 __end, _OutputIterator __res) {
3173 return __internal::__brick_copy(__begin, __end, __res, typename _Tag::__is_vector{});
3174 };
3175 auto copy_range2 = [](_ForwardIterator2 __begin, _ForwardIterator2 __end, _OutputIterator __res) {
3176 return __internal::__brick_copy(__begin, __end, __res, typename _Tag::__is_vector{});
3177 };
3178
3179 // {1} {}: parallel copying just first sequence
3180 if (__n2 == 0)
3181 return __internal::__pattern_walk2_brick(
3182 __tag, std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __result, copy_range1);
3183
3184 // {} {2}: parallel copying justmake second sequence
3185 if (__n1 == 0)
3186 return __internal::__pattern_walk2_brick(
3187 __tag, std::forward<_ExecutionPolicy>(__exec), __first2, __last2, __result, copy_range2);
3188
3189 // testing whether the sequences are intersected
3190 _ForwardIterator1 __left_bound_seq_1 = std::lower_bound(__first1, __last1, *__first2, __comp);
3191
3192 if (__left_bound_seq_1 == __last1) {
3193 //{1} < {2}: seq2 is wholly greater than seq1, so, do parallel copying seq1 and seq2
3194 __par_backend::__parallel_invoke(
3195 __backend_tag{},
3196 std::forward<_ExecutionPolicy>(__exec),
3197 [=] {
3198 __internal::__pattern_walk2_brick(
3199 __tag, std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __result, copy_range1);
3200 },
3201 [=] {
3202 __internal::__pattern_walk2_brick(
3203 __tag, std::forward<_ExecutionPolicy>(__exec), __first2, __last2, __result + __n1, copy_range2);
3204 });
3205 return __result + __n1 + __n2;
3206 }
3207
3208 // testing whether the sequences are intersected
3209 _ForwardIterator2 __left_bound_seq_2 = std::lower_bound(__first2, __last2, *__first1, __comp);
3210
3211 if (__left_bound_seq_2 == __last2) {
3212 //{2} < {1}: seq2 is wholly greater than seq1, so, do parallel copying seq1 and seq2
3213 __par_backend::__parallel_invoke(
3214 __backend_tag{},
3215 std::forward<_ExecutionPolicy>(__exec),
3216 [=] {
3217 __internal::__pattern_walk2_brick(
3218 __tag, std::forward<_ExecutionPolicy>(__exec), __first2, __last2, __result, copy_range2);
3219 },
3220 [=] {
3221 __internal::__pattern_walk2_brick(
3222 __tag, std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __result + __n2, copy_range1);
3223 });
3224 return __result + __n1 + __n2;
3225 }
3226
3227 const auto __m1 = __left_bound_seq_1 - __first1;
3228 if (__m1 > __set_algo_cut_off) {
3229 auto __res_or = __result;
3230 __result += __m1; // we know proper offset due to [first1; left_bound_seq_1) < [first2; last2)
3231 __par_backend::__parallel_invoke(
3232 __backend_tag{},
3233 std::forward<_ExecutionPolicy>(__exec),
3234 // do parallel copying of [first1; left_bound_seq_1)
3235 [=] {
3236 __internal::__pattern_walk2_brick(
3237 __tag, std::forward<_ExecutionPolicy>(__exec), __first1, __left_bound_seq_1, __res_or, copy_range1);
3238 },
3239 [=, &__result] {
3240 __result = __internal::__parallel_set_op(
3241 __tag,
3242 std::forward<_ExecutionPolicy>(__exec),
3243 __left_bound_seq_1,
3244 __last1,
3245 __first2,
3246 __last2,
3247 __result,
3248 __comp,
3249 [](_DifferenceType __n, _DifferenceType __m) { return __n + __m; },
3250 __set_union_op);
3251 });
3252 return __result;
3253 }
3254
3255 const auto __m2 = __left_bound_seq_2 - __first2;
3256 _LIBCPP_ASSERT_UNCATEGORIZED(__m1 == 0 || __m2 == 0, "");
3257 if (__m2 > __set_algo_cut_off) {
3258 auto __res_or = __result;
3259 __result += __m2; // we know proper offset due to [first2; left_bound_seq_2) < [first1; last1)
3260 __par_backend::__parallel_invoke(
3261 __backend_tag{},
3262 std::forward<_ExecutionPolicy>(__exec),
3263 // do parallel copying of [first2; left_bound_seq_2)
3264 [=] {
3265 __internal::__pattern_walk2_brick(
3266 __tag, std::forward<_ExecutionPolicy>(__exec), __first2, __left_bound_seq_2, __res_or, copy_range2);
3267 },
3268 [=, &__result] {
3269 __result = __internal::__parallel_set_op(
3270 __tag,
3271 std::forward<_ExecutionPolicy>(__exec),
3272 __first1,
3273 __last1,
3274 __left_bound_seq_2,
3275 __last2,
3276 __result,
3277 __comp,
3278 [](_DifferenceType __n, _DifferenceType __m) { return __n + __m; },
3279 __set_union_op);
3280 });
3281 return __result;
3282 }
3283
3284 return __internal::__parallel_set_op(
3285 __tag,
3286 std::forward<_ExecutionPolicy>(__exec),
3287 __first1,
3288 __last1,
3289 __first2,
3290 __last2,
3291 __result,
3292 __comp,
3293 [](_DifferenceType __n, _DifferenceType __m) { return __n + __m; },
3294 __set_union_op);
3295 }
3296
3297 //------------------------------------------------------------------------
3298 // set_union
3299 //------------------------------------------------------------------------
3300
3301 template <class _ForwardIterator1, class _ForwardIterator2, class _OutputIterator, class _Compare>
__brick_set_union(_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_ForwardIterator2 __last2,_OutputIterator __result,_Compare __comp,std::false_type)3302 _OutputIterator __brick_set_union(
3303 _ForwardIterator1 __first1,
3304 _ForwardIterator1 __last1,
3305 _ForwardIterator2 __first2,
3306 _ForwardIterator2 __last2,
3307 _OutputIterator __result,
3308 _Compare __comp,
3309 /*__is_vector=*/std::false_type) noexcept {
3310 return std::set_union(__first1, __last1, __first2, __last2, __result, __comp);
3311 }
3312
3313 template <typename _IsVector>
3314 struct __BrickCopyConstruct {
3315 template <typename _ForwardIterator, typename _OutputIterator>
operator__BrickCopyConstruct3316 _OutputIterator operator()(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result) {
3317 return __brick_uninitialized_copy(__first, __last, __result, _IsVector());
3318 }
3319 };
3320
3321 template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _OutputIterator, class _Compare>
__brick_set_union(_RandomAccessIterator1 __first1,_RandomAccessIterator1 __last1,_RandomAccessIterator2 __first2,_RandomAccessIterator2 __last2,_OutputIterator __result,_Compare __comp,std::true_type)3322 _OutputIterator __brick_set_union(
3323 _RandomAccessIterator1 __first1,
3324 _RandomAccessIterator1 __last1,
3325 _RandomAccessIterator2 __first2,
3326 _RandomAccessIterator2 __last2,
3327 _OutputIterator __result,
3328 _Compare __comp,
3329 /*__is_vector=*/std::true_type) noexcept {
3330 // TODO: vectorize
3331 return std::set_union(__first1, __last1, __first2, __last2, __result, __comp);
3332 }
3333
3334 template <class _Tag,
3335 class _ExecutionPolicy,
3336 class _ForwardIterator1,
3337 class _ForwardIterator2,
3338 class _OutputIterator,
3339 class _Compare>
__pattern_set_union(_Tag,_ExecutionPolicy &&,_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_ForwardIterator2 __last2,_OutputIterator __result,_Compare __comp)3340 _OutputIterator __pattern_set_union(
3341 _Tag,
3342 _ExecutionPolicy&&,
3343 _ForwardIterator1 __first1,
3344 _ForwardIterator1 __last1,
3345 _ForwardIterator2 __first2,
3346 _ForwardIterator2 __last2,
3347 _OutputIterator __result,
3348 _Compare __comp) noexcept {
3349 return __internal::__brick_set_union(
3350 __first1, __last1, __first2, __last2, __result, __comp, typename _Tag::__is_vector{});
3351 }
3352
3353 template <class _IsVector,
3354 class _ExecutionPolicy,
3355 class _RandomAccessIterator1,
3356 class _RandomAccessIterator2,
3357 class _OutputIterator,
3358 class _Compare>
__pattern_set_union(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator1 __first1,_RandomAccessIterator1 __last1,_RandomAccessIterator2 __first2,_RandomAccessIterator2 __last2,_OutputIterator __result,_Compare __comp)3359 _OutputIterator __pattern_set_union(
3360 __parallel_tag<_IsVector> __tag,
3361 _ExecutionPolicy&& __exec,
3362 _RandomAccessIterator1 __first1,
3363 _RandomAccessIterator1 __last1,
3364 _RandomAccessIterator2 __first2,
3365 _RandomAccessIterator2 __last2,
3366 _OutputIterator __result,
3367 _Compare __comp) {
3368 const auto __n1 = __last1 - __first1;
3369 const auto __n2 = __last2 - __first2;
3370
3371 // use serial algorithm
3372 if (__n1 + __n2 <= __set_algo_cut_off)
3373 return std::set_union(__first1, __last1, __first2, __last2, __result, __comp);
3374
3375 typedef typename std::iterator_traits<_OutputIterator>::value_type _Tp;
3376 return __parallel_set_union_op(
3377 __tag,
3378 std::forward<_ExecutionPolicy>(__exec),
3379 __first1,
3380 __last1,
3381 __first2,
3382 __last2,
3383 __result,
3384 __comp,
3385 [](_RandomAccessIterator1 __first1,
3386 _RandomAccessIterator1 __last1,
3387 _RandomAccessIterator2 __first2,
3388 _RandomAccessIterator2 __last2,
3389 _Tp* __result,
3390 _Compare __comp) {
3391 return __pstl::__utils::__set_union_construct(
3392 __first1, __last1, __first2, __last2, __result, __comp, __BrickCopyConstruct<_IsVector>());
3393 });
3394 }
3395
3396 //------------------------------------------------------------------------
3397 // set_intersection
3398 //------------------------------------------------------------------------
3399
3400 template <class _ForwardIterator1, class _ForwardIterator2, class _OutputIterator, class _Compare>
__brick_set_intersection(_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_ForwardIterator2 __last2,_OutputIterator __result,_Compare __comp,std::false_type)3401 _OutputIterator __brick_set_intersection(
3402 _ForwardIterator1 __first1,
3403 _ForwardIterator1 __last1,
3404 _ForwardIterator2 __first2,
3405 _ForwardIterator2 __last2,
3406 _OutputIterator __result,
3407 _Compare __comp,
3408 /*__is_vector=*/std::false_type) noexcept {
3409 return std::set_intersection(__first1, __last1, __first2, __last2, __result, __comp);
3410 }
3411
3412 template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _RandomAccessIterator3, class _Compare>
__brick_set_intersection(_RandomAccessIterator1 __first1,_RandomAccessIterator1 __last1,_RandomAccessIterator2 __first2,_RandomAccessIterator2 __last2,_RandomAccessIterator3 __result,_Compare __comp,std::true_type)3413 _RandomAccessIterator3 __brick_set_intersection(
3414 _RandomAccessIterator1 __first1,
3415 _RandomAccessIterator1 __last1,
3416 _RandomAccessIterator2 __first2,
3417 _RandomAccessIterator2 __last2,
3418 _RandomAccessIterator3 __result,
3419 _Compare __comp,
3420 /*__is_vector=*/std::true_type) noexcept {
3421 // TODO: vectorize
3422 return std::set_intersection(__first1, __last1, __first2, __last2, __result, __comp);
3423 }
3424
3425 template <class _Tag,
3426 class _ExecutionPolicy,
3427 class _ForwardIterator1,
3428 class _ForwardIterator2,
3429 class _OutputIterator,
3430 class _Compare>
__pattern_set_intersection(_Tag,_ExecutionPolicy &&,_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_ForwardIterator2 __last2,_OutputIterator __result,_Compare __comp)3431 _OutputIterator __pattern_set_intersection(
3432 _Tag,
3433 _ExecutionPolicy&&,
3434 _ForwardIterator1 __first1,
3435 _ForwardIterator1 __last1,
3436 _ForwardIterator2 __first2,
3437 _ForwardIterator2 __last2,
3438 _OutputIterator __result,
3439 _Compare __comp) noexcept {
3440 return __internal::__brick_set_intersection(
3441 __first1, __last1, __first2, __last2, __result, __comp, typename _Tag::__is_vector{});
3442 }
3443
3444 template <class _IsVector,
3445 class _ExecutionPolicy,
3446 class _RandomAccessIterator1,
3447 class _RandomAccessIterator2,
3448 class _RandomAccessIterator3,
3449 class _Compare>
__pattern_set_intersection(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator1 __first1,_RandomAccessIterator1 __last1,_RandomAccessIterator2 __first2,_RandomAccessIterator2 __last2,_RandomAccessIterator3 __result,_Compare __comp)3450 _RandomAccessIterator3 __pattern_set_intersection(
3451 __parallel_tag<_IsVector> __tag,
3452 _ExecutionPolicy&& __exec,
3453 _RandomAccessIterator1 __first1,
3454 _RandomAccessIterator1 __last1,
3455 _RandomAccessIterator2 __first2,
3456 _RandomAccessIterator2 __last2,
3457 _RandomAccessIterator3 __result,
3458 _Compare __comp) {
3459 typedef typename std::iterator_traits<_RandomAccessIterator3>::value_type _Tp;
3460 typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _DifferenceType;
3461
3462 const auto __n1 = __last1 - __first1;
3463 const auto __n2 = __last2 - __first2;
3464
3465 // intersection is empty
3466 if (__n1 == 0 || __n2 == 0)
3467 return __result;
3468
3469 // testing whether the sequences are intersected
3470 _RandomAccessIterator1 __left_bound_seq_1 = std::lower_bound(__first1, __last1, *__first2, __comp);
3471 //{1} < {2}: seq 2 is wholly greater than seq 1, so, the intersection is empty
3472 if (__left_bound_seq_1 == __last1)
3473 return __result;
3474
3475 // testing whether the sequences are intersected
3476 _RandomAccessIterator2 __left_bound_seq_2 = std::lower_bound(__first2, __last2, *__first1, __comp);
3477 //{2} < {1}: seq 1 is wholly greater than seq 2, so, the intersection is empty
3478 if (__left_bound_seq_2 == __last2)
3479 return __result;
3480
3481 const auto __m1 = __last1 - __left_bound_seq_1 + __n2;
3482 if (__m1 > __set_algo_cut_off) {
3483 // we know proper offset due to [first1; left_bound_seq_1) < [first2; last2)
3484 return __internal::__parallel_set_op(
3485 __tag,
3486 std::forward<_ExecutionPolicy>(__exec),
3487 __left_bound_seq_1,
3488 __last1,
3489 __first2,
3490 __last2,
3491 __result,
3492 __comp,
3493 [](_DifferenceType __n, _DifferenceType __m) { return std::min(__n, __m); },
3494 [](_RandomAccessIterator1 __first1,
3495 _RandomAccessIterator1 __last1,
3496 _RandomAccessIterator2 __first2,
3497 _RandomAccessIterator2 __last2,
3498 _Tp* __result,
3499 _Compare __comp) {
3500 return __pstl::__utils::__set_intersection_construct(__first1, __last1, __first2, __last2, __result, __comp);
3501 });
3502 }
3503
3504 const auto __m2 = __last2 - __left_bound_seq_2 + __n1;
3505 if (__m2 > __set_algo_cut_off) {
3506 // we know proper offset due to [first2; left_bound_seq_2) < [first1; last1)
3507 __result = __internal::__parallel_set_op(
3508 __tag,
3509 std::forward<_ExecutionPolicy>(__exec),
3510 __first1,
3511 __last1,
3512 __left_bound_seq_2,
3513 __last2,
3514 __result,
3515 __comp,
3516 [](_DifferenceType __n, _DifferenceType __m) { return std::min(__n, __m); },
3517 [](_RandomAccessIterator1 __first1,
3518 _RandomAccessIterator1 __last1,
3519 _RandomAccessIterator2 __first2,
3520 _RandomAccessIterator2 __last2,
3521 _Tp* __result,
3522 _Compare __comp) {
3523 return __pstl::__utils::__set_intersection_construct(__first2, __last2, __first1, __last1, __result, __comp);
3524 });
3525 return __result;
3526 }
3527
3528 // [left_bound_seq_1; last1) and [left_bound_seq_2; last2) - use serial algorithm
3529 return std::set_intersection(__left_bound_seq_1, __last1, __left_bound_seq_2, __last2, __result, __comp);
3530 }
3531
3532 //------------------------------------------------------------------------
3533 // set_difference
3534 //------------------------------------------------------------------------
3535
3536 template <class _ForwardIterator1, class _ForwardIterator2, class _OutputIterator, class _Compare>
__brick_set_difference(_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_ForwardIterator2 __last2,_OutputIterator __result,_Compare __comp,std::false_type)3537 _OutputIterator __brick_set_difference(
3538 _ForwardIterator1 __first1,
3539 _ForwardIterator1 __last1,
3540 _ForwardIterator2 __first2,
3541 _ForwardIterator2 __last2,
3542 _OutputIterator __result,
3543 _Compare __comp,
3544 /*__is_vector=*/std::false_type) noexcept {
3545 return std::set_difference(__first1, __last1, __first2, __last2, __result, __comp);
3546 }
3547
3548 template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _RandomAccessIterator3, class _Compare>
__brick_set_difference(_RandomAccessIterator1 __first1,_RandomAccessIterator1 __last1,_RandomAccessIterator2 __first2,_RandomAccessIterator2 __last2,_RandomAccessIterator3 __result,_Compare __comp,std::true_type)3549 _RandomAccessIterator3 __brick_set_difference(
3550 _RandomAccessIterator1 __first1,
3551 _RandomAccessIterator1 __last1,
3552 _RandomAccessIterator2 __first2,
3553 _RandomAccessIterator2 __last2,
3554 _RandomAccessIterator3 __result,
3555 _Compare __comp,
3556 /*__is_vector=*/std::true_type) noexcept {
3557 // TODO: vectorize
3558 return std::set_difference(__first1, __last1, __first2, __last2, __result, __comp);
3559 }
3560
3561 template <class _Tag,
3562 class _ExecutionPolicy,
3563 class _ForwardIterator1,
3564 class _ForwardIterator2,
3565 class _OutputIterator,
3566 class _Compare>
__pattern_set_difference(_Tag,_ExecutionPolicy &&,_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_ForwardIterator2 __last2,_OutputIterator __result,_Compare __comp)3567 _OutputIterator __pattern_set_difference(
3568 _Tag,
3569 _ExecutionPolicy&&,
3570 _ForwardIterator1 __first1,
3571 _ForwardIterator1 __last1,
3572 _ForwardIterator2 __first2,
3573 _ForwardIterator2 __last2,
3574 _OutputIterator __result,
3575 _Compare __comp) noexcept {
3576 return __internal::__brick_set_difference(
3577 __first1, __last1, __first2, __last2, __result, __comp, typename _Tag::__is_vector{});
3578 }
3579
3580 template <class _IsVector,
3581 class _ExecutionPolicy,
3582 class _RandomAccessIterator1,
3583 class _RandomAccessIterator2,
3584 class _RandomAccessIterator3,
3585 class _Compare>
__pattern_set_difference(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator1 __first1,_RandomAccessIterator1 __last1,_RandomAccessIterator2 __first2,_RandomAccessIterator2 __last2,_RandomAccessIterator3 __result,_Compare __comp)3586 _RandomAccessIterator3 __pattern_set_difference(
3587 __parallel_tag<_IsVector> __tag,
3588 _ExecutionPolicy&& __exec,
3589 _RandomAccessIterator1 __first1,
3590 _RandomAccessIterator1 __last1,
3591 _RandomAccessIterator2 __first2,
3592 _RandomAccessIterator2 __last2,
3593 _RandomAccessIterator3 __result,
3594 _Compare __comp) {
3595 typedef typename std::iterator_traits<_RandomAccessIterator3>::value_type _Tp;
3596 typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _DifferenceType;
3597
3598 const auto __n1 = __last1 - __first1;
3599 const auto __n2 = __last2 - __first2;
3600
3601 // {} \ {2}: the difference is empty
3602 if (__n1 == 0)
3603 return __result;
3604
3605 // {1} \ {}: parallel copying just first sequence
3606 if (__n2 == 0)
3607 return __internal::__pattern_walk2_brick(
3608 __tag,
3609 std::forward<_ExecutionPolicy>(__exec),
3610 __first1,
3611 __last1,
3612 __result,
3613 [](_RandomAccessIterator1 __begin, _RandomAccessIterator1 __end, _RandomAccessIterator3 __res) {
3614 return __internal::__brick_copy(__begin, __end, __res, _IsVector{});
3615 });
3616
3617 // testing whether the sequences are intersected
3618 _RandomAccessIterator1 __left_bound_seq_1 = std::lower_bound(__first1, __last1, *__first2, __comp);
3619 //{1} < {2}: seq 2 is wholly greater than seq 1, so, parallel copying just first sequence
3620 if (__left_bound_seq_1 == __last1)
3621 return __internal::__pattern_walk2_brick(
3622 __tag,
3623 std::forward<_ExecutionPolicy>(__exec),
3624 __first1,
3625 __last1,
3626 __result,
3627 [](_RandomAccessIterator1 __begin, _RandomAccessIterator1 __end, _RandomAccessIterator3 __res) {
3628 return __internal::__brick_copy(__begin, __end, __res, _IsVector{});
3629 });
3630
3631 // testing whether the sequences are intersected
3632 _RandomAccessIterator2 __left_bound_seq_2 = std::lower_bound(__first2, __last2, *__first1, __comp);
3633 //{2} < {1}: seq 1 is wholly greater than seq 2, so, parallel copying just first sequence
3634 if (__left_bound_seq_2 == __last2)
3635 return __internal::__pattern_walk2_brick(
3636 __tag,
3637 std::forward<_ExecutionPolicy>(__exec),
3638 __first1,
3639 __last1,
3640 __result,
3641 [](_RandomAccessIterator1 __begin, _RandomAccessIterator1 __end, _RandomAccessIterator3 __res) {
3642 return __internal::__brick_copy(__begin, __end, __res, _IsVector{});
3643 });
3644
3645 if (__n1 + __n2 > __set_algo_cut_off)
3646 return __parallel_set_op(
3647 __tag,
3648 std::forward<_ExecutionPolicy>(__exec),
3649 __first1,
3650 __last1,
3651 __first2,
3652 __last2,
3653 __result,
3654 __comp,
3655 [](_DifferenceType __n, _DifferenceType) { return __n; },
3656 [](_RandomAccessIterator1 __first1,
3657 _RandomAccessIterator1 __last1,
3658 _RandomAccessIterator2 __first2,
3659 _RandomAccessIterator2 __last2,
3660 _Tp* __result,
3661 _Compare __comp) {
3662 return __pstl::__utils::__set_difference_construct(
3663 __first1, __last1, __first2, __last2, __result, __comp, __BrickCopyConstruct<_IsVector>());
3664 });
3665
3666 // use serial algorithm
3667 return std::set_difference(__first1, __last1, __first2, __last2, __result, __comp);
3668 }
3669
3670 //------------------------------------------------------------------------
3671 // set_symmetric_difference
3672 //------------------------------------------------------------------------
3673
3674 template <class _ForwardIterator1, class _ForwardIterator2, class _OutputIterator, class _Compare>
__brick_set_symmetric_difference(_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_ForwardIterator2 __last2,_OutputIterator __result,_Compare __comp,std::false_type)3675 _OutputIterator __brick_set_symmetric_difference(
3676 _ForwardIterator1 __first1,
3677 _ForwardIterator1 __last1,
3678 _ForwardIterator2 __first2,
3679 _ForwardIterator2 __last2,
3680 _OutputIterator __result,
3681 _Compare __comp,
3682 /*__is_vector=*/std::false_type) noexcept {
3683 return std::set_symmetric_difference(__first1, __last1, __first2, __last2, __result, __comp);
3684 }
3685
3686 template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _RandomAccessIterator3, class _Compare>
__brick_set_symmetric_difference(_RandomAccessIterator1 __first1,_RandomAccessIterator1 __last1,_RandomAccessIterator2 __first2,_RandomAccessIterator2 __last2,_RandomAccessIterator3 __result,_Compare __comp,std::true_type)3687 _RandomAccessIterator3 __brick_set_symmetric_difference(
3688 _RandomAccessIterator1 __first1,
3689 _RandomAccessIterator1 __last1,
3690 _RandomAccessIterator2 __first2,
3691 _RandomAccessIterator2 __last2,
3692 _RandomAccessIterator3 __result,
3693 _Compare __comp,
3694 /*__is_vector=*/std::true_type) noexcept {
3695 // TODO: vectorize
3696 return std::set_symmetric_difference(__first1, __last1, __first2, __last2, __result, __comp);
3697 }
3698
3699 template <class _Tag,
3700 class _ExecutionPolicy,
3701 class _ForwardIterator1,
3702 class _ForwardIterator2,
3703 class _OutputIterator,
3704 class _Compare>
__pattern_set_symmetric_difference(_Tag,_ExecutionPolicy &&,_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_ForwardIterator2 __last2,_OutputIterator __result,_Compare __comp)3705 _OutputIterator __pattern_set_symmetric_difference(
3706 _Tag,
3707 _ExecutionPolicy&&,
3708 _ForwardIterator1 __first1,
3709 _ForwardIterator1 __last1,
3710 _ForwardIterator2 __first2,
3711 _ForwardIterator2 __last2,
3712 _OutputIterator __result,
3713 _Compare __comp) noexcept {
3714 return __internal::__brick_set_symmetric_difference(
3715 __first1, __last1, __first2, __last2, __result, __comp, typename _Tag::__is_vector{});
3716 }
3717
3718 template <class _IsVector,
3719 class _ExecutionPolicy,
3720 class _RandomAccessIterator1,
3721 class _RandomAccessIterator2,
3722 class _RandomAccessIterator3,
3723 class _Compare>
__pattern_set_symmetric_difference(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator1 __first1,_RandomAccessIterator1 __last1,_RandomAccessIterator2 __first2,_RandomAccessIterator2 __last2,_RandomAccessIterator3 __result,_Compare __comp)3724 _RandomAccessIterator3 __pattern_set_symmetric_difference(
3725 __parallel_tag<_IsVector> __tag,
3726 _ExecutionPolicy&& __exec,
3727 _RandomAccessIterator1 __first1,
3728 _RandomAccessIterator1 __last1,
3729 _RandomAccessIterator2 __first2,
3730 _RandomAccessIterator2 __last2,
3731 _RandomAccessIterator3 __result,
3732 _Compare __comp) {
3733 const auto __n1 = __last1 - __first1;
3734 const auto __n2 = __last2 - __first2;
3735
3736 // use serial algorithm
3737 if (__n1 + __n2 <= __set_algo_cut_off)
3738 return std::set_symmetric_difference(__first1, __last1, __first2, __last2, __result, __comp);
3739
3740 typedef typename std::iterator_traits<_RandomAccessIterator3>::value_type _Tp;
3741 return __internal::__parallel_set_union_op(
3742 __tag,
3743 std::forward<_ExecutionPolicy>(__exec),
3744 __first1,
3745 __last1,
3746 __first2,
3747 __last2,
3748 __result,
3749 __comp,
3750 [](_RandomAccessIterator1 __first1,
3751 _RandomAccessIterator1 __last1,
3752 _RandomAccessIterator2 __first2,
3753 _RandomAccessIterator2 __last2,
3754 _Tp* __result,
3755 _Compare __comp) {
3756 return __pstl::__utils::__set_symmetric_difference_construct(
3757 __first1, __last1, __first2, __last2, __result, __comp, __BrickCopyConstruct<_IsVector>());
3758 });
3759 }
3760
3761 //------------------------------------------------------------------------
3762 // is_heap_until
3763 //------------------------------------------------------------------------
3764
3765 template <class _RandomAccessIterator, class _Compare>
__brick_is_heap_until(_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp,std::false_type)3766 _RandomAccessIterator __brick_is_heap_until(
3767 _RandomAccessIterator __first,
3768 _RandomAccessIterator __last,
3769 _Compare __comp,
3770 /* __is_vector = */ std::false_type) noexcept {
3771 return std::is_heap_until(__first, __last, __comp);
3772 }
3773
3774 template <class _RandomAccessIterator, class _Compare>
__brick_is_heap_until(_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp,std::true_type)3775 _RandomAccessIterator __brick_is_heap_until(
3776 _RandomAccessIterator __first,
3777 _RandomAccessIterator __last,
3778 _Compare __comp,
3779 /* __is_vector = */ std::true_type) noexcept {
3780 if (__last - __first < 2)
3781 return __last;
3782 typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _SizeType;
3783 return __unseq_backend::__simd_first(
3784 __first, _SizeType(0), __last - __first, [&__comp](_RandomAccessIterator __it, _SizeType __i) {
3785 return __comp(__it[(__i - 1) / 2], __it[__i]);
3786 });
3787 }
3788
3789 template <class _Tag, class _ExecutionPolicy, class _RandomAccessIterator, class _Compare>
__pattern_is_heap_until(_Tag,_ExecutionPolicy &&,_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp)3790 _RandomAccessIterator __pattern_is_heap_until(
3791 _Tag, _ExecutionPolicy&&, _RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) noexcept {
3792 return __internal::__brick_is_heap_until(__first, __last, __comp, typename _Tag::__is_vector{});
3793 }
3794
3795 template <class _RandomAccessIterator, class _DifferenceType, class _Compare>
__is_heap_until_local(_RandomAccessIterator __first,_DifferenceType __begin,_DifferenceType __end,_Compare __comp,std::false_type)3796 _RandomAccessIterator __is_heap_until_local(
3797 _RandomAccessIterator __first,
3798 _DifferenceType __begin,
3799 _DifferenceType __end,
3800 _Compare __comp,
3801 /* __is_vector = */ std::false_type) noexcept {
3802 _DifferenceType __i = __begin;
3803 for (; __i < __end; ++__i) {
3804 if (__comp(__first[(__i - 1) / 2], __first[__i])) {
3805 break;
3806 }
3807 }
3808 return __first + __i;
3809 }
3810
3811 template <class _RandomAccessIterator, class _DifferenceType, class _Compare>
__is_heap_until_local(_RandomAccessIterator __first,_DifferenceType __begin,_DifferenceType __end,_Compare __comp,std::true_type)3812 _RandomAccessIterator __is_heap_until_local(
3813 _RandomAccessIterator __first,
3814 _DifferenceType __begin,
3815 _DifferenceType __end,
3816 _Compare __comp,
3817 /* __is_vector = */ std::true_type) noexcept {
3818 return __unseq_backend::__simd_first(
3819 __first, __begin, __end, [&__comp](_RandomAccessIterator __it, _DifferenceType __i) {
3820 return __comp(__it[(__i - 1) / 2], __it[__i]);
3821 });
3822 }
3823
3824 template <class _IsVector, class _ExecutionPolicy, class _RandomAccessIterator, class _Compare>
__pattern_is_heap_until(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp)3825 _RandomAccessIterator __pattern_is_heap_until(
3826 __parallel_tag<_IsVector> __tag,
3827 _ExecutionPolicy&& __exec,
3828 _RandomAccessIterator __first,
3829 _RandomAccessIterator __last,
3830 _Compare __comp) noexcept {
3831 using __backend_tag = typename decltype(__tag)::__backend_tag;
3832
3833 if (__last - __first < 2)
3834 return __last;
3835
3836 return __internal::__except_handler([&]() {
3837 return __parallel_find(
3838 __backend_tag{},
3839 std::forward<_ExecutionPolicy>(__exec),
3840 __first,
3841 __last,
3842 [__first, __comp](_RandomAccessIterator __i, _RandomAccessIterator __j) {
3843 return __internal::__is_heap_until_local(__first, __i - __first, __j - __first, __comp, _IsVector{});
3844 },
3845 std::less<typename std::iterator_traits<_RandomAccessIterator>::difference_type>(),
3846 /*is_first=*/true);
3847 });
3848 }
3849
3850 //------------------------------------------------------------------------
3851 // min_element
3852 //------------------------------------------------------------------------
3853
3854 template <typename _ForwardIterator, typename _Compare>
__brick_min_element(_ForwardIterator __first,_ForwardIterator __last,_Compare __comp,std::false_type)3855 _ForwardIterator __brick_min_element(
3856 _ForwardIterator __first,
3857 _ForwardIterator __last,
3858 _Compare __comp,
3859 /* __is_vector = */ std::false_type) noexcept {
3860 return std::min_element(__first, __last, __comp);
3861 }
3862
3863 template <typename _RandomAccessIterator, typename _Compare>
__brick_min_element(_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp,std::true_type)3864 _RandomAccessIterator __brick_min_element(
3865 _RandomAccessIterator __first,
3866 _RandomAccessIterator __last,
3867 _Compare __comp,
3868 /* __is_vector = */ std::true_type) noexcept {
3869 #if defined(_PSTL_UDR_PRESENT)
3870 return __unseq_backend::__simd_min_element(__first, __last - __first, __comp);
3871 #else
3872 return std::min_element(__first, __last, __comp);
3873 #endif
3874 }
3875
3876 template <typename _Tag, typename _ExecutionPolicy, typename _ForwardIterator, typename _Compare>
__pattern_min_element(_Tag,_ExecutionPolicy &&,_ForwardIterator __first,_ForwardIterator __last,_Compare __comp)3877 _ForwardIterator __pattern_min_element(
3878 _Tag, _ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterator __last, _Compare __comp) noexcept {
3879 return __internal::__brick_min_element(__first, __last, __comp, typename _Tag::__is_vector{});
3880 }
3881
3882 template <typename _IsVector, typename _ExecutionPolicy, typename _RandomAccessIterator, typename _Compare>
__pattern_min_element(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp)3883 _RandomAccessIterator __pattern_min_element(
3884 __parallel_tag<_IsVector> __tag,
3885 _ExecutionPolicy&& __exec,
3886 _RandomAccessIterator __first,
3887 _RandomAccessIterator __last,
3888 _Compare __comp) {
3889 if (__first == __last)
3890 return __last;
3891
3892 using __backend_tag = typename decltype(__tag)::__backend_tag;
3893
3894 return __internal::__except_handler([&]() {
3895 return __par_backend::__parallel_reduce(
3896 __backend_tag{},
3897 std::forward<_ExecutionPolicy>(__exec),
3898 __first + 1,
3899 __last,
3900 __first,
3901 [=](_RandomAccessIterator __begin, _RandomAccessIterator __end, _RandomAccessIterator __init)
3902 -> _RandomAccessIterator {
3903 const _RandomAccessIterator subresult = __internal::__brick_min_element(__begin, __end, __comp, _IsVector{});
3904 return __internal::__cmp_iterators_by_values(__init, subresult, __comp);
3905 },
3906 [=](_RandomAccessIterator __it1, _RandomAccessIterator __it2) -> _RandomAccessIterator {
3907 return __internal::__cmp_iterators_by_values(__it1, __it2, __comp);
3908 });
3909 });
3910 }
3911
3912 //------------------------------------------------------------------------
3913 // minmax_element
3914 //------------------------------------------------------------------------
3915
3916 template <typename _ForwardIterator, typename _Compare>
__brick_minmax_element(_ForwardIterator __first,_ForwardIterator __last,_Compare __comp,std::false_type)3917 std::pair<_ForwardIterator, _ForwardIterator> __brick_minmax_element(
3918 _ForwardIterator __first,
3919 _ForwardIterator __last,
3920 _Compare __comp,
3921 /* __is_vector = */ std::false_type) noexcept {
3922 return std::minmax_element(__first, __last, __comp);
3923 }
3924
3925 template <typename _RandomAccessIterator, typename _Compare>
__brick_minmax_element(_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp,std::true_type)3926 std::pair<_RandomAccessIterator, _RandomAccessIterator> __brick_minmax_element(
3927 _RandomAccessIterator __first,
3928 _RandomAccessIterator __last,
3929 _Compare __comp,
3930 /* __is_vector = */ std::true_type) noexcept {
3931 #if defined(_PSTL_UDR_PRESENT)
3932 return __unseq_backend::__simd_minmax_element(__first, __last - __first, __comp);
3933 #else
3934 return std::minmax_element(__first, __last, __comp);
3935 #endif
3936 }
3937
3938 template <typename _Tag, typename _ExecutionPolicy, typename _ForwardIterator, typename _Compare>
__pattern_minmax_element(_Tag,_ExecutionPolicy &&,_ForwardIterator __first,_ForwardIterator __last,_Compare __comp)3939 std::pair<_ForwardIterator, _ForwardIterator> __pattern_minmax_element(
3940 _Tag, _ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterator __last, _Compare __comp) noexcept {
3941 return __internal::__brick_minmax_element(__first, __last, __comp, typename _Tag::__is_vector{});
3942 }
3943
3944 template <typename _IsVector, typename _ExecutionPolicy, typename _RandomAccessIterator, typename _Compare>
__pattern_minmax_element(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp)3945 std::pair<_RandomAccessIterator, _RandomAccessIterator> __pattern_minmax_element(
3946 __parallel_tag<_IsVector> __tag,
3947 _ExecutionPolicy&& __exec,
3948 _RandomAccessIterator __first,
3949 _RandomAccessIterator __last,
3950 _Compare __comp) {
3951 if (__first == __last)
3952 return std::make_pair(__first, __first);
3953
3954 using __backend_tag = typename decltype(__tag)::__backend_tag;
3955
3956 return __internal::__except_handler([&]() {
3957 typedef std::pair<_RandomAccessIterator, _RandomAccessIterator> _Result;
3958
3959 return __par_backend::__parallel_reduce(
3960 __backend_tag{},
3961 std::forward<_ExecutionPolicy>(__exec),
3962 __first + 1,
3963 __last,
3964 std::make_pair(__first, __first),
3965 [=](_RandomAccessIterator __begin, _RandomAccessIterator __end, _Result __init) -> _Result {
3966 const _Result __subresult = __internal::__brick_minmax_element(__begin, __end, __comp, _IsVector{});
3967 return std::make_pair(
3968 __internal::__cmp_iterators_by_values(__subresult.first, __init.first, __comp),
3969 __internal::__cmp_iterators_by_values(__init.second, __subresult.second, std::not_fn(__comp)));
3970 },
3971 [=](_Result __p1, _Result __p2) -> _Result {
3972 return std::make_pair(__internal::__cmp_iterators_by_values(__p1.first, __p2.first, __comp),
3973 __internal::__cmp_iterators_by_values(__p2.second, __p1.second, std::not_fn(__comp)));
3974 });
3975 });
3976 }
3977
3978 //------------------------------------------------------------------------
3979 // mismatch
3980 //------------------------------------------------------------------------
3981 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
__mismatch_serial(_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_ForwardIterator2 __last2,_BinaryPredicate __pred)3982 std::pair<_ForwardIterator1, _ForwardIterator2> __mismatch_serial(
3983 _ForwardIterator1 __first1,
3984 _ForwardIterator1 __last1,
3985 _ForwardIterator2 __first2,
3986 _ForwardIterator2 __last2,
3987 _BinaryPredicate __pred) {
3988 return std::mismatch(__first1, __last1, __first2, __last2, __pred);
3989 }
3990
3991 template <class _ForwardIterator1, class _ForwardIterator2, class _Predicate>
__brick_mismatch(_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_ForwardIterator2 __last2,_Predicate __pred,std::false_type)3992 std::pair<_ForwardIterator1, _ForwardIterator2> __brick_mismatch(
3993 _ForwardIterator1 __first1,
3994 _ForwardIterator1 __last1,
3995 _ForwardIterator2 __first2,
3996 _ForwardIterator2 __last2,
3997 _Predicate __pred,
3998 /* __is_vector = */ std::false_type) noexcept {
3999 return __mismatch_serial(__first1, __last1, __first2, __last2, __pred);
4000 }
4001
4002 template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _Predicate>
__brick_mismatch(_RandomAccessIterator1 __first1,_RandomAccessIterator1 __last1,_RandomAccessIterator2 __first2,_RandomAccessIterator2 __last2,_Predicate __pred,std::true_type)4003 std::pair<_RandomAccessIterator1, _RandomAccessIterator2> __brick_mismatch(
4004 _RandomAccessIterator1 __first1,
4005 _RandomAccessIterator1 __last1,
4006 _RandomAccessIterator2 __first2,
4007 _RandomAccessIterator2 __last2,
4008 _Predicate __pred,
4009 /* __is_vector = */ std::true_type) noexcept {
4010 auto __n = std::min(__last1 - __first1, __last2 - __first2);
4011 return __unseq_backend::__simd_first(__first1, __n, __first2, std::not_fn(__pred));
4012 }
4013
4014 template <class _Tag, class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate>
__pattern_mismatch(_Tag,_ExecutionPolicy &&,_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_ForwardIterator2 __last2,_Predicate __pred)4015 std::pair<_ForwardIterator1, _ForwardIterator2> __pattern_mismatch(
4016 _Tag,
4017 _ExecutionPolicy&&,
4018 _ForwardIterator1 __first1,
4019 _ForwardIterator1 __last1,
4020 _ForwardIterator2 __first2,
4021 _ForwardIterator2 __last2,
4022 _Predicate __pred) noexcept {
4023 return __internal::__brick_mismatch(__first1, __last1, __first2, __last2, __pred, typename _Tag::__is_vector{});
4024 }
4025
4026 template <class _IsVector,
4027 class _ExecutionPolicy,
4028 class _RandomAccessIterator1,
4029 class _RandomAccessIterator2,
4030 class _Predicate>
__pattern_mismatch(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator1 __first1,_RandomAccessIterator1 __last1,_RandomAccessIterator2 __first2,_RandomAccessIterator2 __last2,_Predicate __pred)4031 std::pair<_RandomAccessIterator1, _RandomAccessIterator2> __pattern_mismatch(
4032 __parallel_tag<_IsVector> __tag,
4033 _ExecutionPolicy&& __exec,
4034 _RandomAccessIterator1 __first1,
4035 _RandomAccessIterator1 __last1,
4036 _RandomAccessIterator2 __first2,
4037 _RandomAccessIterator2 __last2,
4038 _Predicate __pred) noexcept {
4039 using __backend_tag = typename decltype(__tag)::__backend_tag;
4040
4041 return __internal::__except_handler([&]() {
4042 auto __n = std::min(__last1 - __first1, __last2 - __first2);
4043 auto __result = __internal::__parallel_find(
4044 __backend_tag{},
4045 std::forward<_ExecutionPolicy>(__exec),
4046 __first1,
4047 __first1 + __n,
4048 [__first1, __first2, __pred](_RandomAccessIterator1 __i, _RandomAccessIterator1 __j) {
4049 return __internal::__brick_mismatch(
4050 __i, __j, __first2 + (__i - __first1), __first2 + (__j - __first1), __pred, _IsVector{})
4051 .first;
4052 },
4053 std::less<typename std::iterator_traits<_RandomAccessIterator1>::difference_type>(),
4054 /*is_first=*/true);
4055 return std::make_pair(__result, __first2 + (__result - __first1));
4056 });
4057 }
4058
4059 //------------------------------------------------------------------------
4060 // lexicographical_compare
4061 //------------------------------------------------------------------------
4062
4063 template <class _ForwardIterator1, class _ForwardIterator2, class _Compare>
__brick_lexicographical_compare(_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_ForwardIterator2 __last2,_Compare __comp,std::false_type)4064 bool __brick_lexicographical_compare(
4065 _ForwardIterator1 __first1,
4066 _ForwardIterator1 __last1,
4067 _ForwardIterator2 __first2,
4068 _ForwardIterator2 __last2,
4069 _Compare __comp,
4070 /* __is_vector = */ std::false_type) noexcept {
4071 return std::lexicographical_compare(__first1, __last1, __first2, __last2, __comp);
4072 }
4073
4074 template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _Compare>
__brick_lexicographical_compare(_RandomAccessIterator1 __first1,_RandomAccessIterator1 __last1,_RandomAccessIterator2 __first2,_RandomAccessIterator2 __last2,_Compare __comp,std::true_type)4075 bool __brick_lexicographical_compare(
4076 _RandomAccessIterator1 __first1,
4077 _RandomAccessIterator1 __last1,
4078 _RandomAccessIterator2 __first2,
4079 _RandomAccessIterator2 __last2,
4080 _Compare __comp,
4081 /* __is_vector = */ std::true_type) noexcept {
4082 if (__first2 == __last2) { // if second sequence is empty
4083 return false;
4084 } else if (__first1 == __last1) { // if first sequence is empty
4085 return true;
4086 } else {
4087 typedef typename std::iterator_traits<_RandomAccessIterator1>::reference ref_type1;
4088 typedef typename std::iterator_traits<_RandomAccessIterator2>::reference ref_type2;
4089 --__last1;
4090 --__last2;
4091 auto __n = std::min(__last1 - __first1, __last2 - __first2);
4092 std::pair<_RandomAccessIterator1, _RandomAccessIterator2> __result = __unseq_backend::__simd_first(
4093 __first1, __n, __first2, [__comp](const ref_type1 __x, const ref_type2 __y) mutable {
4094 return __comp(__x, __y) || __comp(__y, __x);
4095 });
4096
4097 if (__result.first == __last1 && __result.second != __last2) { // if first sequence shorter than second
4098 return !__comp(*__result.second, *__result.first);
4099 } else { // if second sequence shorter than first or both have the same number of elements
4100 return __comp(*__result.first, *__result.second);
4101 }
4102 }
4103 }
4104
4105 template <class _Tag, class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Compare>
__pattern_lexicographical_compare(_Tag,_ExecutionPolicy &&,_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_ForwardIterator2 __last2,_Compare __comp)4106 bool __pattern_lexicographical_compare(
4107 _Tag,
4108 _ExecutionPolicy&&,
4109 _ForwardIterator1 __first1,
4110 _ForwardIterator1 __last1,
4111 _ForwardIterator2 __first2,
4112 _ForwardIterator2 __last2,
4113 _Compare __comp) noexcept {
4114 return __internal::__brick_lexicographical_compare(
4115 __first1, __last1, __first2, __last2, __comp, typename _Tag::__is_vector{});
4116 }
4117
4118 template <class _IsVector,
4119 class _ExecutionPolicy,
4120 class _RandomAccessIterator1,
4121 class _RandomAccessIterator2,
4122 class _Compare>
__pattern_lexicographical_compare(__parallel_tag<_IsVector> __tag,_ExecutionPolicy && __exec,_RandomAccessIterator1 __first1,_RandomAccessIterator1 __last1,_RandomAccessIterator2 __first2,_RandomAccessIterator2 __last2,_Compare __comp)4123 bool __pattern_lexicographical_compare(
4124 __parallel_tag<_IsVector> __tag,
4125 _ExecutionPolicy&& __exec,
4126 _RandomAccessIterator1 __first1,
4127 _RandomAccessIterator1 __last1,
4128 _RandomAccessIterator2 __first2,
4129 _RandomAccessIterator2 __last2,
4130 _Compare __comp) noexcept {
4131 using __backend_tag = typename decltype(__tag)::__backend_tag;
4132
4133 if (__first2 == __last2) { // if second sequence is empty
4134 return false;
4135 } else if (__first1 == __last1) { // if first sequence is empty
4136 return true;
4137 } else {
4138 typedef typename std::iterator_traits<_RandomAccessIterator1>::reference _RefType1;
4139 typedef typename std::iterator_traits<_RandomAccessIterator2>::reference _RefType2;
4140 --__last1;
4141 --__last2;
4142 auto __n = std::min(__last1 - __first1, __last2 - __first2);
4143 auto __result = __internal::__parallel_find(
4144 __backend_tag{},
4145 std::forward<_ExecutionPolicy>(__exec),
4146 __first1,
4147 __first1 + __n,
4148 [__first1, __first2, &__comp](_RandomAccessIterator1 __i, _RandomAccessIterator1 __j) {
4149 return __internal::__brick_mismatch(
4150 __i,
4151 __j,
4152 __first2 + (__i - __first1),
4153 __first2 + (__j - __first1),
4154 [&__comp](const _RefType1 __x, const _RefType2 __y) {
4155 return !__comp(__x, __y) && !__comp(__y, __x);
4156 },
4157 _IsVector{})
4158 .first;
4159 },
4160 std::less<typename std::iterator_traits<_RandomAccessIterator1>::difference_type>(),
4161 /*is_first=*/true);
4162
4163 if (__result == __last1 && __first2 + (__result - __first1) != __last2) { // if first sequence shorter than second
4164 return !__comp(*(__first2 + (__result - __first1)), *__result);
4165 } else { // if second sequence shorter than first or both have the same number of elements
4166 return __comp(*__result, *(__first2 + (__result - __first1)));
4167 }
4168 }
4169 }
4170
4171 } // namespace __internal
4172 } // namespace __pstl
4173
4174 #endif /* _PSTL_ALGORITHM_IMPL_H */
4175