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