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