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