1// -*- C++ -*- 2 3// Copyright (C) 2007-2015 Free Software Foundation, Inc. 4// 5// This file is part of the GNU ISO C++ Library. This library is free 6// software; you can redistribute it and/or modify it under the terms 7// of the GNU General Public License as published by the Free Software 8// Foundation; either version 3, or (at your option) any later 9// version. 10 11// This library is distributed in the hope that it will be useful, but 12// WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14// General Public License for more details. 15 16// Under Section 7 of GPL version 3, you are granted additional 17// permissions described in the GCC Runtime Library Exception, version 18// 3.1, as published by the Free Software Foundation. 19 20// You should have received a copy of the GNU General Public License and 21// a copy of the GCC Runtime Library Exception along with this program; 22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23// <http://www.gnu.org/licenses/>. 24 25/** @file parallel/multiway_merge.h 26* @brief Implementation of sequential and parallel multiway merge. 27* 28* Explanations on the high-speed merging routines in the appendix of 29* 30* P. Sanders. 31* Fast priority queues for cached memory. 32* ACM Journal of Experimental Algorithmics, 5, 2000. 33* 34* This file is a GNU parallel extension to the Standard C++ Library. 35*/ 36 37// Written by Johannes Singler and Manuel Holtgrewe. 38 39#ifndef _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H 40#define _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H 41 42#include <vector> 43 44#include <bits/stl_algo.h> 45#include <parallel/features.h> 46#include <parallel/parallel.h> 47#include <parallel/losertree.h> 48#include <parallel/multiseq_selection.h> 49#if _GLIBCXX_ASSERTIONS 50#include <parallel/checkers.h> 51#endif 52 53/** @brief Length of a sequence described by a pair of iterators. */ 54#define _GLIBCXX_PARALLEL_LENGTH(__s) ((__s).second - (__s).first) 55 56namespace __gnu_parallel 57{ 58 template<typename _RAIter1, typename _RAIter2, typename _OutputIterator, 59 typename _DifferenceTp, typename _Compare> 60 _OutputIterator 61 __merge_advance(_RAIter1&, _RAIter1, _RAIter2&, _RAIter2, 62 _OutputIterator, _DifferenceTp, _Compare); 63 64 /** @brief _Iterator wrapper supporting an implicit supremum at the end 65 * of the sequence, dominating all comparisons. 66 * 67 * The implicit supremum comes with a performance cost. 68 * 69 * Deriving from _RAIter is not possible since 70 * _RAIter need not be a class. 71 */ 72 template<typename _RAIter, typename _Compare> 73 class _GuardedIterator 74 { 75 private: 76 /** @brief Current iterator __position. */ 77 _RAIter _M_current; 78 79 /** @brief End iterator of the sequence. */ 80 _RAIter _M_end; 81 82 /** @brief _Compare. */ 83 _Compare& __comp; 84 85 public: 86 /** @brief Constructor. Sets iterator to beginning of sequence. 87 * @param __begin Begin iterator of sequence. 88 * @param __end End iterator of sequence. 89 * @param __comp Comparator provided for associated overloaded 90 * compare operators. */ 91 _GuardedIterator(_RAIter __begin, _RAIter __end, _Compare& __comp) 92 : _M_current(__begin), _M_end(__end), __comp(__comp) 93 { } 94 95 /** @brief Pre-increment operator. 96 * @return This. */ 97 _GuardedIterator<_RAIter, _Compare>& 98 operator++() 99 { 100 ++_M_current; 101 return *this; 102 } 103 104 /** @brief Dereference operator. 105 * @return Referenced element. */ 106 typename std::iterator_traits<_RAIter>::value_type& 107 operator*() 108 { return *_M_current; } 109 110 /** @brief Convert to wrapped iterator. 111 * @return Wrapped iterator. */ 112 operator _RAIter() 113 { return _M_current; } 114 115 /** @brief Compare two elements referenced by guarded iterators. 116 * @param __bi1 First iterator. 117 * @param __bi2 Second iterator. 118 * @return @c true if less. */ 119 friend bool 120 operator<(_GuardedIterator<_RAIter, _Compare>& __bi1, 121 _GuardedIterator<_RAIter, _Compare>& __bi2) 122 { 123 if (__bi1._M_current == __bi1._M_end) // __bi1 is sup 124 return __bi2._M_current == __bi2._M_end; // __bi2 is not sup 125 if (__bi2._M_current == __bi2._M_end) // __bi2 is sup 126 return true; 127 return (__bi1.__comp)(*__bi1, *__bi2); // normal compare 128 } 129 130 /** @brief Compare two elements referenced by guarded iterators. 131 * @param __bi1 First iterator. 132 * @param __bi2 Second iterator. 133 * @return @c True if less equal. */ 134 friend bool 135 operator<=(_GuardedIterator<_RAIter, _Compare>& __bi1, 136 _GuardedIterator<_RAIter, _Compare>& __bi2) 137 { 138 if (__bi2._M_current == __bi2._M_end) // __bi1 is sup 139 return __bi1._M_current != __bi1._M_end; // __bi2 is not sup 140 if (__bi1._M_current == __bi1._M_end) // __bi2 is sup 141 return false; 142 return !(__bi1.__comp)(*__bi2, *__bi1); // normal compare 143 } 144 }; 145 146 template<typename _RAIter, typename _Compare> 147 class _UnguardedIterator 148 { 149 private: 150 /** @brief Current iterator __position. */ 151 _RAIter _M_current; 152 /** @brief _Compare. */ 153 _Compare& __comp; 154 155 public: 156 /** @brief Constructor. Sets iterator to beginning of sequence. 157 * @param __begin Begin iterator of sequence. 158 * @param __end Unused, only for compatibility. 159 * @param __comp Unused, only for compatibility. */ 160 _UnguardedIterator(_RAIter __begin, 161 _RAIter /* __end */, _Compare& __comp) 162 : _M_current(__begin), __comp(__comp) 163 { } 164 165 /** @brief Pre-increment operator. 166 * @return This. */ 167 _UnguardedIterator<_RAIter, _Compare>& 168 operator++() 169 { 170 ++_M_current; 171 return *this; 172 } 173 174 /** @brief Dereference operator. 175 * @return Referenced element. */ 176 typename std::iterator_traits<_RAIter>::value_type& 177 operator*() 178 { return *_M_current; } 179 180 /** @brief Convert to wrapped iterator. 181 * @return Wrapped iterator. */ 182 operator _RAIter() 183 { return _M_current; } 184 185 /** @brief Compare two elements referenced by unguarded iterators. 186 * @param __bi1 First iterator. 187 * @param __bi2 Second iterator. 188 * @return @c true if less. */ 189 friend bool 190 operator<(_UnguardedIterator<_RAIter, _Compare>& __bi1, 191 _UnguardedIterator<_RAIter, _Compare>& __bi2) 192 { 193 // Normal compare. 194 return (__bi1.__comp)(*__bi1, *__bi2); 195 } 196 197 /** @brief Compare two elements referenced by unguarded iterators. 198 * @param __bi1 First iterator. 199 * @param __bi2 Second iterator. 200 * @return @c True if less equal. */ 201 friend bool 202 operator<=(_UnguardedIterator<_RAIter, _Compare>& __bi1, 203 _UnguardedIterator<_RAIter, _Compare>& __bi2) 204 { 205 // Normal compare. 206 return !(__bi1.__comp)(*__bi2, *__bi1); 207 } 208 }; 209 210 /** @brief Highly efficient 3-way merging procedure. 211 * 212 * Merging is done with the algorithm implementation described by Peter 213 * Sanders. Basically, the idea is to minimize the number of necessary 214 * comparison after merging an element. The implementation trick 215 * that makes this fast is that the order of the sequences is stored 216 * in the instruction pointer (translated into labels in C++). 217 * 218 * This works well for merging up to 4 sequences. 219 * 220 * Note that making the merging stable does @a not come at a 221 * performance hit. 222 * 223 * Whether the merging is done guarded or unguarded is selected by the 224 * used iterator class. 225 * 226 * @param __seqs_begin Begin iterator of iterator pair input sequence. 227 * @param __seqs_end End iterator of iterator pair input sequence. 228 * @param __target Begin iterator of output sequence. 229 * @param __comp Comparator. 230 * @param __length Maximum length to merge, less equal than the 231 * total number of elements available. 232 * 233 * @return End iterator of output sequence. 234 */ 235 template<template<typename RAI, typename C> class iterator, 236 typename _RAIterIterator, 237 typename _RAIter3, 238 typename _DifferenceTp, 239 typename _Compare> 240 _RAIter3 241 multiway_merge_3_variant(_RAIterIterator __seqs_begin, 242 _RAIterIterator __seqs_end, 243 _RAIter3 __target, 244 _DifferenceTp __length, _Compare __comp) 245 { 246 _GLIBCXX_CALL(__length); 247 248 typedef _DifferenceTp _DifferenceType; 249 250 typedef typename std::iterator_traits<_RAIterIterator> 251 ::value_type::first_type 252 _RAIter1; 253 typedef typename std::iterator_traits<_RAIter1>::value_type 254 _ValueType; 255 256 if (__length == 0) 257 return __target; 258 259#if _GLIBCXX_ASSERTIONS 260 _DifferenceTp __orig_length = __length; 261#endif 262 263 iterator<_RAIter1, _Compare> 264 __seq0(__seqs_begin[0].first, __seqs_begin[0].second, __comp), 265 __seq1(__seqs_begin[1].first, __seqs_begin[1].second, __comp), 266 __seq2(__seqs_begin[2].first, __seqs_begin[2].second, __comp); 267 268 if (__seq0 <= __seq1) 269 { 270 if (__seq1 <= __seq2) 271 goto __s012; 272 else 273 if (__seq2 < __seq0) 274 goto __s201; 275 else 276 goto __s021; 277 } 278 else 279 { 280 if (__seq1 <= __seq2) 281 { 282 if (__seq0 <= __seq2) 283 goto __s102; 284 else 285 goto __s120; 286 } 287 else 288 goto __s210; 289 } 290#define _GLIBCXX_PARALLEL_MERGE_3_CASE(__a, __b, __c, __c0, __c1) \ 291 __s ## __a ## __b ## __c : \ 292 *__target = *__seq ## __a; \ 293 ++__target; \ 294 --__length; \ 295 ++__seq ## __a; \ 296 if (__length == 0) goto __finish; \ 297 if (__seq ## __a __c0 __seq ## __b) goto __s ## __a ## __b ## __c; \ 298 if (__seq ## __a __c1 __seq ## __c) goto __s ## __b ## __a ## __c; \ 299 goto __s ## __b ## __c ## __a; 300 301 _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 1, 2, <=, <=); 302 _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 2, 0, <=, < ); 303 _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 0, 1, < , < ); 304 _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 0, 2, < , <=); 305 _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 2, 1, <=, <=); 306 _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 1, 0, < , < ); 307 308#undef _GLIBCXX_PARALLEL_MERGE_3_CASE 309 310 __finish: 311 ; 312 313#if _GLIBCXX_ASSERTIONS 314 _GLIBCXX_PARALLEL_ASSERT( 315 ((_RAIter1)__seq0 - __seqs_begin[0].first) + 316 ((_RAIter1)__seq1 - __seqs_begin[1].first) + 317 ((_RAIter1)__seq2 - __seqs_begin[2].first) 318 == __orig_length); 319#endif 320 321 __seqs_begin[0].first = __seq0; 322 __seqs_begin[1].first = __seq1; 323 __seqs_begin[2].first = __seq2; 324 325 return __target; 326 } 327 328 /** 329 * @brief Highly efficient 4-way merging procedure. 330 * 331 * Merging is done with the algorithm implementation described by Peter 332 * Sanders. Basically, the idea is to minimize the number of necessary 333 * comparison after merging an element. The implementation trick 334 * that makes this fast is that the order of the sequences is stored 335 * in the instruction pointer (translated into goto labels in C++). 336 * 337 * This works well for merging up to 4 sequences. 338 * 339 * Note that making the merging stable does @a not come at a 340 * performance hit. 341 * 342 * Whether the merging is done guarded or unguarded is selected by the 343 * used iterator class. 344 * 345 * @param __seqs_begin Begin iterator of iterator pair input sequence. 346 * @param __seqs_end End iterator of iterator pair input sequence. 347 * @param __target Begin iterator of output sequence. 348 * @param __comp Comparator. 349 * @param __length Maximum length to merge, less equal than the 350 * total number of elements available. 351 * 352 * @return End iterator of output sequence. 353 */ 354 template<template<typename RAI, typename C> class iterator, 355 typename _RAIterIterator, 356 typename _RAIter3, 357 typename _DifferenceTp, 358 typename _Compare> 359 _RAIter3 360 multiway_merge_4_variant(_RAIterIterator __seqs_begin, 361 _RAIterIterator __seqs_end, 362 _RAIter3 __target, 363 _DifferenceTp __length, _Compare __comp) 364 { 365 _GLIBCXX_CALL(__length); 366 typedef _DifferenceTp _DifferenceType; 367 368 typedef typename std::iterator_traits<_RAIterIterator> 369 ::value_type::first_type 370 _RAIter1; 371 typedef typename std::iterator_traits<_RAIter1>::value_type 372 _ValueType; 373 374 iterator<_RAIter1, _Compare> 375 __seq0(__seqs_begin[0].first, __seqs_begin[0].second, __comp), 376 __seq1(__seqs_begin[1].first, __seqs_begin[1].second, __comp), 377 __seq2(__seqs_begin[2].first, __seqs_begin[2].second, __comp), 378 __seq3(__seqs_begin[3].first, __seqs_begin[3].second, __comp); 379 380#define _GLIBCXX_PARALLEL_DECISION(__a, __b, __c, __d) { \ 381 if (__seq ## __d < __seq ## __a) \ 382 goto __s ## __d ## __a ## __b ## __c; \ 383 if (__seq ## __d < __seq ## __b) \ 384 goto __s ## __a ## __d ## __b ## __c; \ 385 if (__seq ## __d < __seq ## __c) \ 386 goto __s ## __a ## __b ## __d ## __c; \ 387 goto __s ## __a ## __b ## __c ## __d; } 388 389 if (__seq0 <= __seq1) 390 { 391 if (__seq1 <= __seq2) 392 _GLIBCXX_PARALLEL_DECISION(0,1,2,3) 393 else 394 if (__seq2 < __seq0) 395 _GLIBCXX_PARALLEL_DECISION(2,0,1,3) 396 else 397 _GLIBCXX_PARALLEL_DECISION(0,2,1,3) 398 } 399 else 400 { 401 if (__seq1 <= __seq2) 402 { 403 if (__seq0 <= __seq2) 404 _GLIBCXX_PARALLEL_DECISION(1,0,2,3) 405 else 406 _GLIBCXX_PARALLEL_DECISION(1,2,0,3) 407 } 408 else 409 _GLIBCXX_PARALLEL_DECISION(2,1,0,3) 410 } 411 412#define _GLIBCXX_PARALLEL_MERGE_4_CASE(__a, __b, __c, __d, \ 413 __c0, __c1, __c2) \ 414 __s ## __a ## __b ## __c ## __d: \ 415 if (__length == 0) goto __finish; \ 416 *__target = *__seq ## __a; \ 417 ++__target; \ 418 --__length; \ 419 ++__seq ## __a; \ 420 if (__seq ## __a __c0 __seq ## __b) \ 421 goto __s ## __a ## __b ## __c ## __d; \ 422 if (__seq ## __a __c1 __seq ## __c) \ 423 goto __s ## __b ## __a ## __c ## __d; \ 424 if (__seq ## __a __c2 __seq ## __d) \ 425 goto __s ## __b ## __c ## __a ## __d; \ 426 goto __s ## __b ## __c ## __d ## __a; 427 428 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 2, 3, <=, <=, <=); 429 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 3, 2, <=, <=, <=); 430 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 1, 3, <=, <=, <=); 431 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 3, 1, <=, <=, <=); 432 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 1, 2, <=, <=, <=); 433 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 2, 1, <=, <=, <=); 434 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 2, 3, < , <=, <=); 435 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 3, 2, < , <=, <=); 436 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 0, 3, <=, < , <=); 437 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 3, 0, <=, <=, < ); 438 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 0, 2, <=, < , <=); 439 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 2, 0, <=, <=, < ); 440 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 1, 3, < , < , <=); 441 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 3, 1, < , <=, < ); 442 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 0, 3, < , < , <=); 443 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 3, 0, < , <=, < ); 444 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 0, 1, <=, < , < ); 445 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 1, 0, <=, < , < ); 446 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 1, 2, < , < , < ); 447 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 2, 1, < , < , < ); 448 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 0, 2, < , < , < ); 449 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 2, 0, < , < , < ); 450 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 0, 1, < , < , < ); 451 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 1, 0, < , < , < ); 452 453#undef _GLIBCXX_PARALLEL_MERGE_4_CASE 454#undef _GLIBCXX_PARALLEL_DECISION 455 456 __finish: 457 ; 458 459 __seqs_begin[0].first = __seq0; 460 __seqs_begin[1].first = __seq1; 461 __seqs_begin[2].first = __seq2; 462 __seqs_begin[3].first = __seq3; 463 464 return __target; 465 } 466 467 /** @brief Multi-way merging procedure for a high branching factor, 468 * guarded case. 469 * 470 * This merging variant uses a LoserTree class as selected by <tt>_LT</tt>. 471 * 472 * Stability is selected through the used LoserTree class <tt>_LT</tt>. 473 * 474 * At least one non-empty sequence is required. 475 * 476 * @param __seqs_begin Begin iterator of iterator pair input sequence. 477 * @param __seqs_end End iterator of iterator pair input sequence. 478 * @param __target Begin iterator of output sequence. 479 * @param __comp Comparator. 480 * @param __length Maximum length to merge, less equal than the 481 * total number of elements available. 482 * 483 * @return End iterator of output sequence. 484 */ 485 template<typename _LT, 486 typename _RAIterIterator, 487 typename _RAIter3, 488 typename _DifferenceTp, 489 typename _Compare> 490 _RAIter3 491 multiway_merge_loser_tree(_RAIterIterator __seqs_begin, 492 _RAIterIterator __seqs_end, 493 _RAIter3 __target, 494 _DifferenceTp __length, _Compare __comp) 495 { 496 _GLIBCXX_CALL(__length) 497 498 typedef _DifferenceTp _DifferenceType; 499 typedef typename std::iterator_traits<_RAIterIterator> 500 ::difference_type _SeqNumber; 501 typedef typename std::iterator_traits<_RAIterIterator> 502 ::value_type::first_type 503 _RAIter1; 504 typedef typename std::iterator_traits<_RAIter1>::value_type 505 _ValueType; 506 507 _SeqNumber __k = static_cast<_SeqNumber>(__seqs_end - __seqs_begin); 508 509 _LT __lt(__k, __comp); 510 511 // Default value for potentially non-default-constructible types. 512 _ValueType* __arbitrary_element = 0; 513 514 for (_SeqNumber __t = 0; __t < __k; ++__t) 515 { 516 if(!__arbitrary_element 517 && _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__t]) > 0) 518 __arbitrary_element = &(*__seqs_begin[__t].first); 519 } 520 521 for (_SeqNumber __t = 0; __t < __k; ++__t) 522 { 523 if (__seqs_begin[__t].first == __seqs_begin[__t].second) 524 __lt.__insert_start(*__arbitrary_element, __t, true); 525 else 526 __lt.__insert_start(*__seqs_begin[__t].first, __t, false); 527 } 528 529 __lt.__init(); 530 531 _SeqNumber __source; 532 533 for (_DifferenceType __i = 0; __i < __length; ++__i) 534 { 535 //take out 536 __source = __lt.__get_min_source(); 537 538 *(__target++) = *(__seqs_begin[__source].first++); 539 540 // Feed. 541 if (__seqs_begin[__source].first == __seqs_begin[__source].second) 542 __lt.__delete_min_insert(*__arbitrary_element, true); 543 else 544 // Replace from same __source. 545 __lt.__delete_min_insert(*__seqs_begin[__source].first, false); 546 } 547 548 return __target; 549 } 550 551 /** @brief Multi-way merging procedure for a high branching factor, 552 * unguarded case. 553 * 554 * Merging is done using the LoserTree class <tt>_LT</tt>. 555 * 556 * Stability is selected by the used LoserTrees. 557 * 558 * @pre No input will run out of elements during the merge. 559 * 560 * @param __seqs_begin Begin iterator of iterator pair input sequence. 561 * @param __seqs_end End iterator of iterator pair input sequence. 562 * @param __target Begin iterator of output sequence. 563 * @param __comp Comparator. 564 * @param __length Maximum length to merge, less equal than the 565 * total number of elements available. 566 * 567 * @return End iterator of output sequence. 568 */ 569 template<typename _LT, 570 typename _RAIterIterator, 571 typename _RAIter3, 572 typename _DifferenceTp, typename _Compare> 573 _RAIter3 574 multiway_merge_loser_tree_unguarded(_RAIterIterator __seqs_begin, 575 _RAIterIterator __seqs_end, 576 _RAIter3 __target, 577 const typename std::iterator_traits<typename std::iterator_traits< 578 _RAIterIterator>::value_type::first_type>::value_type& 579 __sentinel, 580 _DifferenceTp __length, 581 _Compare __comp) 582 { 583 _GLIBCXX_CALL(__length) 584 typedef _DifferenceTp _DifferenceType; 585 586 typedef typename std::iterator_traits<_RAIterIterator> 587 ::difference_type _SeqNumber; 588 typedef typename std::iterator_traits<_RAIterIterator> 589 ::value_type::first_type 590 _RAIter1; 591 typedef typename std::iterator_traits<_RAIter1>::value_type 592 _ValueType; 593 594 _SeqNumber __k = __seqs_end - __seqs_begin; 595 596 _LT __lt(__k, __sentinel, __comp); 597 598 for (_SeqNumber __t = 0; __t < __k; ++__t) 599 { 600#if _GLIBCXX_ASSERTIONS 601 _GLIBCXX_PARALLEL_ASSERT(__seqs_begin[__t].first 602 != __seqs_begin[__t].second); 603#endif 604 __lt.__insert_start(*__seqs_begin[__t].first, __t, false); 605 } 606 607 __lt.__init(); 608 609 _SeqNumber __source; 610 611#if _GLIBCXX_ASSERTIONS 612 _DifferenceType __i = 0; 613#endif 614 615 _RAIter3 __target_end = __target + __length; 616 while (__target < __target_end) 617 { 618 // Take out. 619 __source = __lt.__get_min_source(); 620 621#if _GLIBCXX_ASSERTIONS 622 _GLIBCXX_PARALLEL_ASSERT(0 <= __source && __source < __k); 623 _GLIBCXX_PARALLEL_ASSERT(__i == 0 624 || !__comp(*(__seqs_begin[__source].first), *(__target - 1))); 625#endif 626 627 // Feed. 628 *(__target++) = *(__seqs_begin[__source].first++); 629 630#if _GLIBCXX_ASSERTIONS 631 ++__i; 632#endif 633 // Replace from same __source. 634 __lt.__delete_min_insert(*__seqs_begin[__source].first, false); 635 } 636 637 return __target; 638 } 639 640 641 /** @brief Multi-way merging procedure for a high branching factor, 642 * requiring sentinels to exist. 643 * 644 * @tparam UnguardedLoserTree _Loser Tree variant to use for the unguarded 645 * merging. 646 * 647 * @param __seqs_begin Begin iterator of iterator pair input sequence. 648 * @param __seqs_end End iterator of iterator pair input sequence. 649 * @param __target Begin iterator of output sequence. 650 * @param __comp Comparator. 651 * @param __length Maximum length to merge, less equal than the 652 * total number of elements available. 653 * 654 * @return End iterator of output sequence. 655 */ 656 template<typename UnguardedLoserTree, 657 typename _RAIterIterator, 658 typename _RAIter3, 659 typename _DifferenceTp, 660 typename _Compare> 661 _RAIter3 662 multiway_merge_loser_tree_sentinel(_RAIterIterator __seqs_begin, 663 _RAIterIterator __seqs_end, 664 _RAIter3 __target, 665 const typename std::iterator_traits<typename std::iterator_traits< 666 _RAIterIterator>::value_type::first_type>::value_type& 667 __sentinel, 668 _DifferenceTp __length, 669 _Compare __comp) 670 { 671 _GLIBCXX_CALL(__length) 672 673 typedef _DifferenceTp _DifferenceType; 674 typedef std::iterator_traits<_RAIterIterator> _TraitsType; 675 typedef typename std::iterator_traits<_RAIterIterator> 676 ::value_type::first_type 677 _RAIter1; 678 typedef typename std::iterator_traits<_RAIter1>::value_type 679 _ValueType; 680 681 _RAIter3 __target_end; 682 683 for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s) 684 // Move the sequence ends to the sentinel. This has the 685 // effect that the sentinel appears to be within the sequence. Then, 686 // we can use the unguarded variant if we merge out as many 687 // non-sentinel elements as we have. 688 ++((*__s).second); 689 690 __target_end = multiway_merge_loser_tree_unguarded<UnguardedLoserTree> 691 (__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp); 692 693#if _GLIBCXX_ASSERTIONS 694 _GLIBCXX_PARALLEL_ASSERT(__target_end == __target + __length); 695 _GLIBCXX_PARALLEL_ASSERT(__is_sorted(__target, __target_end, __comp)); 696#endif 697 698 // Restore the sequence ends so the sentinels are not contained in the 699 // sequence any more (see comment in loop above). 700 for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s) 701 --((*__s).second); 702 703 return __target_end; 704 } 705 706 /** 707 * @brief Traits for determining whether the loser tree should 708 * use pointers or copies. 709 * 710 * The field "_M_use_pointer" is used to determine whether to use pointers 711 * in he loser trees or whether to copy the values into the loser tree. 712 * 713 * The default behavior is to use pointers if the data type is 4 times as 714 * big as the pointer to it. 715 * 716 * Specialize for your data type to customize the behavior. 717 * 718 * Example: 719 * 720 * template<> 721 * struct _LoserTreeTraits<int> 722 * { static const bool _M_use_pointer = false; }; 723 * 724 * template<> 725 * struct _LoserTreeTraits<heavyweight_type> 726 * { static const bool _M_use_pointer = true; }; 727 * 728 * @param _Tp type to give the loser tree traits for. 729 */ 730 template <typename _Tp> 731 struct _LoserTreeTraits 732 { 733 /** 734 * @brief True iff to use pointers instead of values in loser trees. 735 * 736 * The default behavior is to use pointers if the data type is four 737 * times as big as the pointer to it. 738 */ 739 static const bool _M_use_pointer = (sizeof(_Tp) > 4 * sizeof(_Tp*)); 740 }; 741 742 /** 743 * @brief Switch for 3-way merging with __sentinels turned off. 744 * 745 * Note that 3-way merging is always stable! 746 */ 747 template<bool __sentinels /*default == false*/, 748 typename _RAIterIterator, 749 typename _RAIter3, 750 typename _DifferenceTp, 751 typename _Compare> 752 struct __multiway_merge_3_variant_sentinel_switch 753 { 754 _RAIter3 755 operator()(_RAIterIterator __seqs_begin, 756 _RAIterIterator __seqs_end, 757 _RAIter3 __target, 758 _DifferenceTp __length, _Compare __comp) 759 { return multiway_merge_3_variant<_GuardedIterator> 760 (__seqs_begin, __seqs_end, __target, __length, __comp); } 761 }; 762 763 /** 764 * @brief Switch for 3-way merging with __sentinels turned on. 765 * 766 * Note that 3-way merging is always stable! 767 */ 768 template<typename _RAIterIterator, 769 typename _RAIter3, 770 typename _DifferenceTp, 771 typename _Compare> 772 struct __multiway_merge_3_variant_sentinel_switch<true, _RAIterIterator, 773 _RAIter3, _DifferenceTp, 774 _Compare> 775 { 776 _RAIter3 777 operator()(_RAIterIterator __seqs_begin, 778 _RAIterIterator __seqs_end, 779 _RAIter3 __target, 780 _DifferenceTp __length, _Compare __comp) 781 { return multiway_merge_3_variant<_UnguardedIterator> 782 (__seqs_begin, __seqs_end, __target, __length, __comp); } 783 }; 784 785 /** 786 * @brief Switch for 4-way merging with __sentinels turned off. 787 * 788 * Note that 4-way merging is always stable! 789 */ 790 template<bool __sentinels /*default == false*/, 791 typename _RAIterIterator, 792 typename _RAIter3, 793 typename _DifferenceTp, 794 typename _Compare> 795 struct __multiway_merge_4_variant_sentinel_switch 796 { 797 _RAIter3 798 operator()(_RAIterIterator __seqs_begin, 799 _RAIterIterator __seqs_end, 800 _RAIter3 __target, 801 _DifferenceTp __length, _Compare __comp) 802 { return multiway_merge_4_variant<_GuardedIterator> 803 (__seqs_begin, __seqs_end, __target, __length, __comp); } 804 }; 805 806 /** 807 * @brief Switch for 4-way merging with __sentinels turned on. 808 * 809 * Note that 4-way merging is always stable! 810 */ 811 template<typename _RAIterIterator, 812 typename _RAIter3, 813 typename _DifferenceTp, 814 typename _Compare> 815 struct __multiway_merge_4_variant_sentinel_switch<true, _RAIterIterator, 816 _RAIter3, _DifferenceTp, 817 _Compare> 818 { 819 _RAIter3 820 operator()(_RAIterIterator __seqs_begin, 821 _RAIterIterator __seqs_end, 822 _RAIter3 __target, 823 _DifferenceTp __length, _Compare __comp) 824 { return multiway_merge_4_variant<_UnguardedIterator> 825 (__seqs_begin, __seqs_end, __target, __length, __comp); } 826 }; 827 828 /** 829 * @brief Switch for k-way merging with __sentinels turned on. 830 */ 831 template<bool __sentinels, 832 bool __stable, 833 typename _RAIterIterator, 834 typename _RAIter3, 835 typename _DifferenceTp, 836 typename _Compare> 837 struct __multiway_merge_k_variant_sentinel_switch 838 { 839 _RAIter3 840 operator()(_RAIterIterator __seqs_begin, 841 _RAIterIterator __seqs_end, 842 _RAIter3 __target, 843 const typename std::iterator_traits<typename std::iterator_traits< 844 _RAIterIterator>::value_type::first_type>::value_type& 845 __sentinel, 846 _DifferenceTp __length, _Compare __comp) 847 { 848 typedef typename std::iterator_traits<_RAIterIterator> 849 ::value_type::first_type 850 _RAIter1; 851 typedef typename std::iterator_traits<_RAIter1>::value_type 852 _ValueType; 853 854 return multiway_merge_loser_tree_sentinel< 855 typename __gnu_cxx::__conditional_type< 856 _LoserTreeTraits<_ValueType>::_M_use_pointer, 857 _LoserTreePointerUnguarded<__stable, _ValueType, _Compare>, 858 _LoserTreeUnguarded<__stable, _ValueType, _Compare> 859 >::__type> 860 (__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp); 861 } 862 }; 863 864 /** 865 * @brief Switch for k-way merging with __sentinels turned off. 866 */ 867 template<bool __stable, 868 typename _RAIterIterator, 869 typename _RAIter3, 870 typename _DifferenceTp, 871 typename _Compare> 872 struct __multiway_merge_k_variant_sentinel_switch<false, __stable, 873 _RAIterIterator, 874 _RAIter3, _DifferenceTp, 875 _Compare> 876 { 877 _RAIter3 878 operator()(_RAIterIterator __seqs_begin, 879 _RAIterIterator __seqs_end, 880 _RAIter3 __target, 881 const typename std::iterator_traits<typename std::iterator_traits< 882 _RAIterIterator>::value_type::first_type>::value_type& 883 __sentinel, 884 _DifferenceTp __length, _Compare __comp) 885 { 886 typedef typename std::iterator_traits<_RAIterIterator> 887 ::value_type::first_type 888 _RAIter1; 889 typedef typename std::iterator_traits<_RAIter1>::value_type 890 _ValueType; 891 892 return multiway_merge_loser_tree< 893 typename __gnu_cxx::__conditional_type< 894 _LoserTreeTraits<_ValueType>::_M_use_pointer, 895 _LoserTreePointer<__stable, _ValueType, _Compare>, 896 _LoserTree<__stable, _ValueType, _Compare> 897 >::__type >(__seqs_begin, __seqs_end, __target, __length, __comp); 898 } 899 }; 900 901 /** @brief Sequential multi-way merging switch. 902 * 903 * The _GLIBCXX_PARALLEL_DECISION is based on the branching factor and 904 * runtime settings. 905 * @param __seqs_begin Begin iterator of iterator pair input sequence. 906 * @param __seqs_end End iterator of iterator pair input sequence. 907 * @param __target Begin iterator of output sequence. 908 * @param __comp Comparator. 909 * @param __length Maximum length to merge, possibly larger than the 910 * number of elements available. 911 * @param __sentinel The sequences have __a __sentinel element. 912 * @return End iterator of output sequence. */ 913 template<bool __stable, 914 bool __sentinels, 915 typename _RAIterIterator, 916 typename _RAIter3, 917 typename _DifferenceTp, 918 typename _Compare> 919 _RAIter3 920 __sequential_multiway_merge(_RAIterIterator __seqs_begin, 921 _RAIterIterator __seqs_end, 922 _RAIter3 __target, 923 const typename std::iterator_traits<typename std::iterator_traits< 924 _RAIterIterator>::value_type::first_type>::value_type& 925 __sentinel, 926 _DifferenceTp __length, _Compare __comp) 927 { 928 _GLIBCXX_CALL(__length) 929 930 typedef _DifferenceTp _DifferenceType; 931 typedef typename std::iterator_traits<_RAIterIterator> 932 ::difference_type _SeqNumber; 933 typedef typename std::iterator_traits<_RAIterIterator> 934 ::value_type::first_type 935 _RAIter1; 936 typedef typename std::iterator_traits<_RAIter1>::value_type 937 _ValueType; 938 939#if _GLIBCXX_ASSERTIONS 940 for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s) 941 { 942 _GLIBCXX_PARALLEL_ASSERT(__is_sorted((*__s).first, 943 (*__s).second, __comp)); 944 } 945#endif 946 947 _DifferenceTp __total_length = 0; 948 for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s) 949 __total_length += _GLIBCXX_PARALLEL_LENGTH(*__s); 950 951 __length = std::min<_DifferenceTp>(__length, __total_length); 952 953 if(__length == 0) 954 return __target; 955 956 _RAIter3 __return_target = __target; 957 _SeqNumber __k = static_cast<_SeqNumber>(__seqs_end - __seqs_begin); 958 959 switch (__k) 960 { 961 case 0: 962 break; 963 case 1: 964 __return_target = std::copy(__seqs_begin[0].first, 965 __seqs_begin[0].first + __length, 966 __target); 967 __seqs_begin[0].first += __length; 968 break; 969 case 2: 970 __return_target = __merge_advance(__seqs_begin[0].first, 971 __seqs_begin[0].second, 972 __seqs_begin[1].first, 973 __seqs_begin[1].second, 974 __target, __length, __comp); 975 break; 976 case 3: 977 __return_target = __multiway_merge_3_variant_sentinel_switch 978 <__sentinels, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare>() 979 (__seqs_begin, __seqs_end, __target, __length, __comp); 980 break; 981 case 4: 982 __return_target = __multiway_merge_4_variant_sentinel_switch 983 <__sentinels, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare>() 984 (__seqs_begin, __seqs_end, __target, __length, __comp); 985 break; 986 default: 987 __return_target = __multiway_merge_k_variant_sentinel_switch 988 <__sentinels, __stable, _RAIterIterator, _RAIter3, _DifferenceTp, 989 _Compare>() 990 (__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp); 991 break; 992 } 993#if _GLIBCXX_ASSERTIONS 994 _GLIBCXX_PARALLEL_ASSERT( 995 __is_sorted(__target, __target + __length, __comp)); 996#endif 997 998 return __return_target; 999 } 1000 1001 /** 1002 * @brief Stable sorting functor. 1003 * 1004 * Used to reduce code instanciation in multiway_merge_sampling_splitting. 1005 */ 1006 template<bool __stable, class _RAIter, class _StrictWeakOrdering> 1007 struct _SamplingSorter 1008 { 1009 void 1010 operator()(_RAIter __first, _RAIter __last, _StrictWeakOrdering __comp) 1011 { __gnu_sequential::stable_sort(__first, __last, __comp); } 1012 }; 1013 1014 /** 1015 * @brief Non-__stable sorting functor. 1016 * 1017 * Used to reduce code instantiation in multiway_merge_sampling_splitting. 1018 */ 1019 template<class _RAIter, class _StrictWeakOrdering> 1020 struct _SamplingSorter<false, _RAIter, _StrictWeakOrdering> 1021 { 1022 void 1023 operator()(_RAIter __first, _RAIter __last, _StrictWeakOrdering __comp) 1024 { __gnu_sequential::sort(__first, __last, __comp); } 1025 }; 1026 1027 /** 1028 * @brief Sampling based splitting for parallel multiway-merge routine. 1029 */ 1030 template<bool __stable, 1031 typename _RAIterIterator, 1032 typename _Compare, 1033 typename _DifferenceType> 1034 void 1035 multiway_merge_sampling_splitting(_RAIterIterator __seqs_begin, 1036 _RAIterIterator __seqs_end, 1037 _DifferenceType __length, 1038 _DifferenceType __total_length, 1039 _Compare __comp, 1040 std::vector<std::pair<_DifferenceType, _DifferenceType> > *__pieces) 1041 { 1042 typedef typename std::iterator_traits<_RAIterIterator> 1043 ::difference_type _SeqNumber; 1044 typedef typename std::iterator_traits<_RAIterIterator> 1045 ::value_type::first_type 1046 _RAIter1; 1047 typedef typename std::iterator_traits<_RAIter1>::value_type 1048 _ValueType; 1049 1050 // __k sequences. 1051 const _SeqNumber __k 1052 = static_cast<_SeqNumber>(__seqs_end - __seqs_begin); 1053 1054 const _ThreadIndex __num_threads = omp_get_num_threads(); 1055 1056 const _DifferenceType __num_samples = 1057 __gnu_parallel::_Settings::get().merge_oversampling * __num_threads; 1058 1059 _ValueType* __samples = static_cast<_ValueType*> 1060 (::operator new(sizeof(_ValueType) * __k * __num_samples)); 1061 // Sample. 1062 for (_SeqNumber __s = 0; __s < __k; ++__s) 1063 for (_DifferenceType __i = 0; __i < __num_samples; ++__i) 1064 { 1065 _DifferenceType sample_index = static_cast<_DifferenceType> 1066 (_GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__s]) 1067 * (double(__i + 1) / (__num_samples + 1)) 1068 * (double(__length) / __total_length)); 1069 new(&(__samples[__s * __num_samples + __i])) 1070 _ValueType(__seqs_begin[__s].first[sample_index]); 1071 } 1072 1073 // Sort stable or non-stable, depending on value of template parameter 1074 // "__stable". 1075 _SamplingSorter<__stable, _ValueType*, _Compare>() 1076 (__samples, __samples + (__num_samples * __k), __comp); 1077 1078 for (_ThreadIndex __slab = 0; __slab < __num_threads; ++__slab) 1079 // For each slab / processor. 1080 for (_SeqNumber __seq = 0; __seq < __k; ++__seq) 1081 { 1082 // For each sequence. 1083 if (__slab > 0) 1084 __pieces[__slab][__seq].first = std::upper_bound 1085 (__seqs_begin[__seq].first, __seqs_begin[__seq].second, 1086 __samples[__num_samples * __k * __slab / __num_threads], 1087 __comp) 1088 - __seqs_begin[__seq].first; 1089 else 1090 // Absolute beginning. 1091 __pieces[__slab][__seq].first = 0; 1092 if ((__slab + 1) < __num_threads) 1093 __pieces[__slab][__seq].second = std::upper_bound 1094 (__seqs_begin[__seq].first, __seqs_begin[__seq].second, 1095 __samples[__num_samples * __k * (__slab + 1) / __num_threads], 1096 __comp) 1097 - __seqs_begin[__seq].first; 1098 else 1099 // Absolute end. 1100 __pieces[__slab][__seq].second = 1101 _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__seq]); 1102 } 1103 1104 for (_SeqNumber __s = 0; __s < __k; ++__s) 1105 for (_DifferenceType __i = 0; __i < __num_samples; ++__i) 1106 __samples[__s * __num_samples + __i].~_ValueType(); 1107 ::operator delete(__samples); 1108 } 1109 1110 /** 1111 * @brief Exact splitting for parallel multiway-merge routine. 1112 * 1113 * None of the passed sequences may be empty. 1114 */ 1115 template<bool __stable, 1116 typename _RAIterIterator, 1117 typename _Compare, 1118 typename _DifferenceType> 1119 void 1120 multiway_merge_exact_splitting(_RAIterIterator __seqs_begin, 1121 _RAIterIterator __seqs_end, 1122 _DifferenceType __length, 1123 _DifferenceType __total_length, 1124 _Compare __comp, 1125 std::vector<std::pair<_DifferenceType, _DifferenceType> > *__pieces) 1126 { 1127 typedef typename std::iterator_traits<_RAIterIterator> 1128 ::difference_type _SeqNumber; 1129 typedef typename std::iterator_traits<_RAIterIterator> 1130 ::value_type::first_type 1131 _RAIter1; 1132 1133 const bool __tight = (__total_length == __length); 1134 1135 // __k sequences. 1136 const _SeqNumber __k = __seqs_end - __seqs_begin; 1137 1138 const _ThreadIndex __num_threads = omp_get_num_threads(); 1139 1140 // (Settings::multiway_merge_splitting 1141 // == __gnu_parallel::_Settings::EXACT). 1142 std::vector<_RAIter1>* __offsets = 1143 new std::vector<_RAIter1>[__num_threads]; 1144 std::vector<std::pair<_RAIter1, _RAIter1> > __se(__k); 1145 1146 copy(__seqs_begin, __seqs_end, __se.begin()); 1147 1148 _DifferenceType* __borders = 1149 new _DifferenceType[__num_threads + 1]; 1150 __equally_split(__length, __num_threads, __borders); 1151 1152 for (_ThreadIndex __s = 0; __s < (__num_threads - 1); ++__s) 1153 { 1154 __offsets[__s].resize(__k); 1155 multiseq_partition(__se.begin(), __se.end(), __borders[__s + 1], 1156 __offsets[__s].begin(), __comp); 1157 1158 // Last one also needed and available. 1159 if (!__tight) 1160 { 1161 __offsets[__num_threads - 1].resize(__k); 1162 multiseq_partition(__se.begin(), __se.end(), 1163 _DifferenceType(__length), 1164 __offsets[__num_threads - 1].begin(), 1165 __comp); 1166 } 1167 } 1168 delete[] __borders; 1169 1170 for (_ThreadIndex __slab = 0; __slab < __num_threads; ++__slab) 1171 { 1172 // For each slab / processor. 1173 for (_SeqNumber __seq = 0; __seq < __k; ++__seq) 1174 { 1175 // For each sequence. 1176 if (__slab == 0) 1177 { 1178 // Absolute beginning. 1179 __pieces[__slab][__seq].first = 0; 1180 } 1181 else 1182 __pieces[__slab][__seq].first = 1183 __pieces[__slab - 1][__seq].second; 1184 if (!__tight || __slab < (__num_threads - 1)) 1185 __pieces[__slab][__seq].second = 1186 __offsets[__slab][__seq] - __seqs_begin[__seq].first; 1187 else 1188 { 1189 // __slab == __num_threads - 1 1190 __pieces[__slab][__seq].second = 1191 _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__seq]); 1192 } 1193 } 1194 } 1195 delete[] __offsets; 1196 } 1197 1198 /** @brief Parallel multi-way merge routine. 1199 * 1200 * The _GLIBCXX_PARALLEL_DECISION is based on the branching factor 1201 * and runtime settings. 1202 * 1203 * Must not be called if the number of sequences is 1. 1204 * 1205 * @tparam _Splitter functor to split input (either __exact or sampling based) 1206 * @tparam __stable Stable merging incurs a performance penalty. 1207 * @tparam __sentinel Ignored. 1208 * 1209 * @param __seqs_begin Begin iterator of iterator pair input sequence. 1210 * @param __seqs_end End iterator of iterator pair input sequence. 1211 * @param __target Begin iterator of output sequence. 1212 * @param __comp Comparator. 1213 * @param __length Maximum length to merge, possibly larger than the 1214 * number of elements available. 1215 * @return End iterator of output sequence. 1216 */ 1217 template<bool __stable, 1218 bool __sentinels, 1219 typename _RAIterIterator, 1220 typename _RAIter3, 1221 typename _DifferenceTp, 1222 typename _Splitter, 1223 typename _Compare> 1224 _RAIter3 1225 parallel_multiway_merge(_RAIterIterator __seqs_begin, 1226 _RAIterIterator __seqs_end, 1227 _RAIter3 __target, 1228 _Splitter __splitter, 1229 _DifferenceTp __length, 1230 _Compare __comp, 1231 _ThreadIndex __num_threads) 1232 { 1233#if _GLIBCXX_ASSERTIONS 1234 _GLIBCXX_PARALLEL_ASSERT(__seqs_end - __seqs_begin > 1); 1235#endif 1236 1237 _GLIBCXX_CALL(__length) 1238 1239 typedef _DifferenceTp _DifferenceType; 1240 typedef typename std::iterator_traits<_RAIterIterator> 1241 ::difference_type _SeqNumber; 1242 typedef typename std::iterator_traits<_RAIterIterator> 1243 ::value_type::first_type 1244 _RAIter1; 1245 typedef typename 1246 std::iterator_traits<_RAIter1>::value_type _ValueType; 1247 1248 // Leave only non-empty sequences. 1249 typedef std::pair<_RAIter1, _RAIter1> seq_type; 1250 seq_type* __ne_seqs = new seq_type[__seqs_end - __seqs_begin]; 1251 _SeqNumber __k = 0; 1252 _DifferenceType __total_length = 0; 1253 for (_RAIterIterator __raii = __seqs_begin; 1254 __raii != __seqs_end; ++__raii) 1255 { 1256 _DifferenceTp __seq_length = _GLIBCXX_PARALLEL_LENGTH(*__raii); 1257 if(__seq_length > 0) 1258 { 1259 __total_length += __seq_length; 1260 __ne_seqs[__k++] = *__raii; 1261 } 1262 } 1263 1264 _GLIBCXX_CALL(__total_length) 1265 1266 __length = std::min<_DifferenceTp>(__length, __total_length); 1267 1268 if (__total_length == 0 || __k == 0) 1269 { 1270 delete[] __ne_seqs; 1271 return __target; 1272 } 1273 1274 std::vector<std::pair<_DifferenceType, _DifferenceType> >* __pieces; 1275 1276 __num_threads = static_cast<_ThreadIndex> 1277 (std::min<_DifferenceType>(__num_threads, __total_length)); 1278 1279# pragma omp parallel num_threads (__num_threads) 1280 { 1281# pragma omp single 1282 { 1283 __num_threads = omp_get_num_threads(); 1284 // Thread __t will have to merge pieces[__iam][0..__k - 1] 1285 __pieces = new std::vector< 1286 std::pair<_DifferenceType, _DifferenceType> >[__num_threads]; 1287 for (_ThreadIndex __s = 0; __s < __num_threads; ++__s) 1288 __pieces[__s].resize(__k); 1289 1290 _DifferenceType __num_samples = 1291 __gnu_parallel::_Settings::get().merge_oversampling 1292 * __num_threads; 1293 1294 __splitter(__ne_seqs, __ne_seqs + __k, __length, __total_length, 1295 __comp, __pieces); 1296 } //single 1297 1298 _ThreadIndex __iam = omp_get_thread_num(); 1299 1300 _DifferenceType __target_position = 0; 1301 1302 for (_SeqNumber __c = 0; __c < __k; ++__c) 1303 __target_position += __pieces[__iam][__c].first; 1304 1305 seq_type* __chunks = new seq_type[__k]; 1306 1307 for (_SeqNumber __s = 0; __s < __k; ++__s) 1308 __chunks[__s] = std::make_pair(__ne_seqs[__s].first 1309 + __pieces[__iam][__s].first, 1310 __ne_seqs[__s].first 1311 + __pieces[__iam][__s].second); 1312 1313 if(__length > __target_position) 1314 __sequential_multiway_merge<__stable, __sentinels> 1315 (__chunks, __chunks + __k, __target + __target_position, 1316 *(__seqs_begin->second), __length - __target_position, __comp); 1317 1318 delete[] __chunks; 1319 } // parallel 1320 1321#if _GLIBCXX_ASSERTIONS 1322 _GLIBCXX_PARALLEL_ASSERT( 1323 __is_sorted(__target, __target + __length, __comp)); 1324#endif 1325 1326 __k = 0; 1327 // Update ends of sequences. 1328 for (_RAIterIterator __raii = __seqs_begin; 1329 __raii != __seqs_end; ++__raii) 1330 { 1331 _DifferenceTp __length = _GLIBCXX_PARALLEL_LENGTH(*__raii); 1332 if(__length > 0) 1333 (*__raii).first += __pieces[__num_threads - 1][__k++].second; 1334 } 1335 1336 delete[] __pieces; 1337 delete[] __ne_seqs; 1338 1339 return __target + __length; 1340 } 1341 1342 /** 1343 * @brief Multiway Merge Frontend. 1344 * 1345 * Merge the sequences specified by seqs_begin and __seqs_end into 1346 * __target. __seqs_begin and __seqs_end must point to a sequence of 1347 * pairs. These pairs must contain an iterator to the beginning 1348 * of a sequence in their first entry and an iterator the _M_end of 1349 * the same sequence in their second entry. 1350 * 1351 * Ties are broken arbitrarily. See stable_multiway_merge for a variant 1352 * that breaks ties by sequence number but is slower. 1353 * 1354 * The first entries of the pairs (i.e. the begin iterators) will be moved 1355 * forward. 1356 * 1357 * The output sequence has to provide enough space for all elements 1358 * that are written to it. 1359 * 1360 * This function will merge the input sequences: 1361 * 1362 * - not stable 1363 * - parallel, depending on the input size and Settings 1364 * - using sampling for splitting 1365 * - not using sentinels 1366 * 1367 * Example: 1368 * 1369 * <pre> 1370 * int sequences[10][10]; 1371 * for (int __i = 0; __i < 10; ++__i) 1372 * for (int __j = 0; __i < 10; ++__j) 1373 * sequences[__i][__j] = __j; 1374 * 1375 * int __out[33]; 1376 * std::vector<std::pair<int*> > seqs; 1377 * for (int __i = 0; __i < 10; ++__i) 1378 * { seqs.push(std::make_pair<int*>(sequences[__i], 1379 * sequences[__i] + 10)) } 1380 * 1381 * multiway_merge(seqs.begin(), seqs.end(), __target, std::less<int>(), 33); 1382 * </pre> 1383 * 1384 * @see stable_multiway_merge 1385 * 1386 * @pre All input sequences must be sorted. 1387 * @pre Target must provide enough space to merge out length elements or 1388 * the number of elements in all sequences, whichever is smaller. 1389 * 1390 * @post [__target, return __value) contains merged __elements from the 1391 * input sequences. 1392 * @post return __value - __target = min(__length, number of elements in all 1393 * sequences). 1394 * 1395 * @tparam _RAIterPairIterator iterator over sequence 1396 * of pairs of iterators 1397 * @tparam _RAIterOut iterator over target sequence 1398 * @tparam _DifferenceTp difference type for the sequence 1399 * @tparam _Compare strict weak ordering type to compare elements 1400 * in sequences 1401 * 1402 * @param __seqs_begin __begin of sequence __sequence 1403 * @param __seqs_end _M_end of sequence __sequence 1404 * @param __target target sequence to merge to. 1405 * @param __comp strict weak ordering to use for element comparison. 1406 * @param __length Maximum length to merge, possibly larger than the 1407 * number of elements available. 1408 * 1409 * @return _M_end iterator of output sequence 1410 */ 1411 // multiway_merge 1412 // public interface 1413 template<typename _RAIterPairIterator, 1414 typename _RAIterOut, 1415 typename _DifferenceTp, 1416 typename _Compare> 1417 _RAIterOut 1418 multiway_merge(_RAIterPairIterator __seqs_begin, 1419 _RAIterPairIterator __seqs_end, 1420 _RAIterOut __target, 1421 _DifferenceTp __length, _Compare __comp, 1422 __gnu_parallel::sequential_tag) 1423 { 1424 typedef _DifferenceTp _DifferenceType; 1425 _GLIBCXX_CALL(__seqs_end - __seqs_begin) 1426 1427 // catch special case: no sequences 1428 if (__seqs_begin == __seqs_end) 1429 return __target; 1430 1431 // Execute multiway merge *sequentially*. 1432 return __sequential_multiway_merge 1433 </* __stable = */ false, /* __sentinels = */ false> 1434 (__seqs_begin, __seqs_end, __target, 1435 *(__seqs_begin->second), __length, __comp); 1436 } 1437 1438 // public interface 1439 template<typename _RAIterPairIterator, 1440 typename _RAIterOut, 1441 typename _DifferenceTp, 1442 typename _Compare> 1443 _RAIterOut 1444 multiway_merge(_RAIterPairIterator __seqs_begin, 1445 _RAIterPairIterator __seqs_end, 1446 _RAIterOut __target, 1447 _DifferenceTp __length, _Compare __comp, 1448 __gnu_parallel::exact_tag __tag) 1449 { 1450 typedef _DifferenceTp _DifferenceType; 1451 _GLIBCXX_CALL(__seqs_end - __seqs_begin) 1452 1453 // catch special case: no sequences 1454 if (__seqs_begin == __seqs_end) 1455 return __target; 1456 1457 // Execute merge; maybe parallel, depending on the number of merged 1458 // elements and the number of sequences and global thresholds in 1459 // Settings. 1460 if ((__seqs_end - __seqs_begin > 1) 1461 && _GLIBCXX_PARALLEL_CONDITION( 1462 ((__seqs_end - __seqs_begin) >= 1463 __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 1464 && ((_SequenceIndex)__length >= 1465 __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 1466 return parallel_multiway_merge 1467 </* __stable = */ false, /* __sentinels = */ false> 1468 (__seqs_begin, __seqs_end, __target, 1469 multiway_merge_exact_splitting</* __stable = */ false, 1470 typename std::iterator_traits<_RAIterPairIterator> 1471 ::value_type*, _Compare, _DifferenceTp>, 1472 static_cast<_DifferenceType>(__length), __comp, 1473 __tag.__get_num_threads()); 1474 else 1475 return __sequential_multiway_merge 1476 </* __stable = */ false, /* __sentinels = */ false> 1477 (__seqs_begin, __seqs_end, __target, 1478 *(__seqs_begin->second), __length, __comp); 1479 } 1480 1481 // public interface 1482 template<typename _RAIterPairIterator, 1483 typename _RAIterOut, 1484 typename _DifferenceTp, 1485 typename _Compare> 1486 _RAIterOut 1487 multiway_merge(_RAIterPairIterator __seqs_begin, 1488 _RAIterPairIterator __seqs_end, 1489 _RAIterOut __target, 1490 _DifferenceTp __length, _Compare __comp, 1491 __gnu_parallel::sampling_tag __tag) 1492 { 1493 typedef _DifferenceTp _DifferenceType; 1494 _GLIBCXX_CALL(__seqs_end - __seqs_begin) 1495 1496 // catch special case: no sequences 1497 if (__seqs_begin == __seqs_end) 1498 return __target; 1499 1500 // Execute merge; maybe parallel, depending on the number of merged 1501 // elements and the number of sequences and global thresholds in 1502 // Settings. 1503 if ((__seqs_end - __seqs_begin > 1) 1504 && _GLIBCXX_PARALLEL_CONDITION( 1505 ((__seqs_end - __seqs_begin) >= 1506 __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 1507 && ((_SequenceIndex)__length >= 1508 __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 1509 return parallel_multiway_merge 1510 </* __stable = */ false, /* __sentinels = */ false> 1511 (__seqs_begin, __seqs_end, __target, 1512 multiway_merge_exact_splitting</* __stable = */ false, 1513 typename std::iterator_traits<_RAIterPairIterator> 1514 ::value_type*, _Compare, _DifferenceTp>, 1515 static_cast<_DifferenceType>(__length), __comp, 1516 __tag.__get_num_threads()); 1517 else 1518 return __sequential_multiway_merge 1519 </* __stable = */ false, /* __sentinels = */ false> 1520 (__seqs_begin, __seqs_end, __target, 1521 *(__seqs_begin->second), __length, __comp); 1522 } 1523 1524 // public interface 1525 template<typename _RAIterPairIterator, 1526 typename _RAIterOut, 1527 typename _DifferenceTp, 1528 typename _Compare> 1529 _RAIterOut 1530 multiway_merge(_RAIterPairIterator __seqs_begin, 1531 _RAIterPairIterator __seqs_end, 1532 _RAIterOut __target, 1533 _DifferenceTp __length, _Compare __comp, 1534 parallel_tag __tag = parallel_tag(0)) 1535 { return multiway_merge(__seqs_begin, __seqs_end, __target, __length, 1536 __comp, exact_tag(__tag.__get_num_threads())); } 1537 1538 // public interface 1539 template<typename _RAIterPairIterator, 1540 typename _RAIterOut, 1541 typename _DifferenceTp, 1542 typename _Compare> 1543 _RAIterOut 1544 multiway_merge(_RAIterPairIterator __seqs_begin, 1545 _RAIterPairIterator __seqs_end, 1546 _RAIterOut __target, 1547 _DifferenceTp __length, _Compare __comp, 1548 default_parallel_tag __tag) 1549 { return multiway_merge(__seqs_begin, __seqs_end, __target, __length, 1550 __comp, exact_tag(__tag.__get_num_threads())); } 1551 1552 // stable_multiway_merge 1553 // public interface 1554 template<typename _RAIterPairIterator, 1555 typename _RAIterOut, 1556 typename _DifferenceTp, 1557 typename _Compare> 1558 _RAIterOut 1559 stable_multiway_merge(_RAIterPairIterator __seqs_begin, 1560 _RAIterPairIterator __seqs_end, 1561 _RAIterOut __target, 1562 _DifferenceTp __length, _Compare __comp, 1563 __gnu_parallel::sequential_tag) 1564 { 1565 typedef _DifferenceTp _DifferenceType; 1566 _GLIBCXX_CALL(__seqs_end - __seqs_begin) 1567 1568 // catch special case: no sequences 1569 if (__seqs_begin == __seqs_end) 1570 return __target; 1571 1572 // Execute multiway merge *sequentially*. 1573 return __sequential_multiway_merge 1574 </* __stable = */ true, /* __sentinels = */ false> 1575 (__seqs_begin, __seqs_end, __target, 1576 *(__seqs_begin->second), __length, __comp); 1577 } 1578 1579 // public interface 1580 template<typename _RAIterPairIterator, 1581 typename _RAIterOut, 1582 typename _DifferenceTp, 1583 typename _Compare> 1584 _RAIterOut 1585 stable_multiway_merge(_RAIterPairIterator __seqs_begin, 1586 _RAIterPairIterator __seqs_end, 1587 _RAIterOut __target, 1588 _DifferenceTp __length, _Compare __comp, 1589 __gnu_parallel::exact_tag __tag) 1590 { 1591 typedef _DifferenceTp _DifferenceType; 1592 _GLIBCXX_CALL(__seqs_end - __seqs_begin) 1593 1594 // catch special case: no sequences 1595 if (__seqs_begin == __seqs_end) 1596 return __target; 1597 1598 // Execute merge; maybe parallel, depending on the number of merged 1599 // elements and the number of sequences and global thresholds in 1600 // Settings. 1601 if ((__seqs_end - __seqs_begin > 1) 1602 && _GLIBCXX_PARALLEL_CONDITION( 1603 ((__seqs_end - __seqs_begin) >= 1604 __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 1605 && ((_SequenceIndex)__length >= 1606 __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 1607 return parallel_multiway_merge 1608 </* __stable = */ true, /* __sentinels = */ false> 1609 (__seqs_begin, __seqs_end, __target, 1610 multiway_merge_exact_splitting</* __stable = */ true, 1611 typename std::iterator_traits<_RAIterPairIterator> 1612 ::value_type*, _Compare, _DifferenceTp>, 1613 static_cast<_DifferenceType>(__length), __comp, 1614 __tag.__get_num_threads()); 1615 else 1616 return __sequential_multiway_merge 1617 </* __stable = */ true, /* __sentinels = */ false> 1618 (__seqs_begin, __seqs_end, __target, 1619 *(__seqs_begin->second), __length, __comp); 1620 } 1621 1622 // public interface 1623 template<typename _RAIterPairIterator, 1624 typename _RAIterOut, 1625 typename _DifferenceTp, 1626 typename _Compare> 1627 _RAIterOut 1628 stable_multiway_merge(_RAIterPairIterator __seqs_begin, 1629 _RAIterPairIterator __seqs_end, 1630 _RAIterOut __target, 1631 _DifferenceTp __length, _Compare __comp, 1632 sampling_tag __tag) 1633 { 1634 typedef _DifferenceTp _DifferenceType; 1635 _GLIBCXX_CALL(__seqs_end - __seqs_begin) 1636 1637 // catch special case: no sequences 1638 if (__seqs_begin == __seqs_end) 1639 return __target; 1640 1641 // Execute merge; maybe parallel, depending on the number of merged 1642 // elements and the number of sequences and global thresholds in 1643 // Settings. 1644 if ((__seqs_end - __seqs_begin > 1) 1645 && _GLIBCXX_PARALLEL_CONDITION( 1646 ((__seqs_end - __seqs_begin) >= 1647 __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 1648 && ((_SequenceIndex)__length >= 1649 __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 1650 return parallel_multiway_merge 1651 </* __stable = */ true, /* __sentinels = */ false> 1652 (__seqs_begin, __seqs_end, __target, 1653 multiway_merge_sampling_splitting</* __stable = */ true, 1654 typename std::iterator_traits<_RAIterPairIterator> 1655 ::value_type*, _Compare, _DifferenceTp>, 1656 static_cast<_DifferenceType>(__length), __comp, 1657 __tag.__get_num_threads()); 1658 else 1659 return __sequential_multiway_merge 1660 </* __stable = */ true, /* __sentinels = */ false> 1661 (__seqs_begin, __seqs_end, __target, 1662 *(__seqs_begin->second), __length, __comp); 1663 } 1664 1665 // public interface 1666 template<typename _RAIterPairIterator, 1667 typename _RAIterOut, 1668 typename _DifferenceTp, 1669 typename _Compare> 1670 _RAIterOut 1671 stable_multiway_merge(_RAIterPairIterator __seqs_begin, 1672 _RAIterPairIterator __seqs_end, 1673 _RAIterOut __target, 1674 _DifferenceTp __length, _Compare __comp, 1675 parallel_tag __tag = parallel_tag(0)) 1676 { 1677 return stable_multiway_merge 1678 (__seqs_begin, __seqs_end, __target, __length, __comp, 1679 exact_tag(__tag.__get_num_threads())); 1680 } 1681 1682 // public interface 1683 template<typename _RAIterPairIterator, 1684 typename _RAIterOut, 1685 typename _DifferenceTp, 1686 typename _Compare> 1687 _RAIterOut 1688 stable_multiway_merge(_RAIterPairIterator __seqs_begin, 1689 _RAIterPairIterator __seqs_end, 1690 _RAIterOut __target, 1691 _DifferenceTp __length, _Compare __comp, 1692 default_parallel_tag __tag) 1693 { 1694 return stable_multiway_merge 1695 (__seqs_begin, __seqs_end, __target, __length, __comp, 1696 exact_tag(__tag.__get_num_threads())); 1697 } 1698 1699 /** 1700 * @brief Multiway Merge Frontend. 1701 * 1702 * Merge the sequences specified by seqs_begin and __seqs_end into 1703 * __target. __seqs_begin and __seqs_end must point to a sequence of 1704 * pairs. These pairs must contain an iterator to the beginning 1705 * of a sequence in their first entry and an iterator the _M_end of 1706 * the same sequence in their second entry. 1707 * 1708 * Ties are broken arbitrarily. See stable_multiway_merge for a variant 1709 * that breaks ties by sequence number but is slower. 1710 * 1711 * The first entries of the pairs (i.e. the begin iterators) will be moved 1712 * forward accordingly. 1713 * 1714 * The output sequence has to provide enough space for all elements 1715 * that are written to it. 1716 * 1717 * This function will merge the input sequences: 1718 * 1719 * - not stable 1720 * - parallel, depending on the input size and Settings 1721 * - using sampling for splitting 1722 * - using sentinels 1723 * 1724 * You have to take care that the element the _M_end iterator points to is 1725 * readable and contains a value that is greater than any other non-sentinel 1726 * value in all sequences. 1727 * 1728 * Example: 1729 * 1730 * <pre> 1731 * int sequences[10][11]; 1732 * for (int __i = 0; __i < 10; ++__i) 1733 * for (int __j = 0; __i < 11; ++__j) 1734 * sequences[__i][__j] = __j; // __last one is sentinel! 1735 * 1736 * int __out[33]; 1737 * std::vector<std::pair<int*> > seqs; 1738 * for (int __i = 0; __i < 10; ++__i) 1739 * { seqs.push(std::make_pair<int*>(sequences[__i], 1740 * sequences[__i] + 10)) } 1741 * 1742 * multiway_merge(seqs.begin(), seqs.end(), __target, std::less<int>(), 33); 1743 * </pre> 1744 * 1745 * @pre All input sequences must be sorted. 1746 * @pre Target must provide enough space to merge out length elements or 1747 * the number of elements in all sequences, whichever is smaller. 1748 * @pre For each @c __i, @c __seqs_begin[__i].second must be the end 1749 * marker of the sequence, but also reference the one more __sentinel 1750 * element. 1751 * 1752 * @post [__target, return __value) contains merged __elements from the 1753 * input sequences. 1754 * @post return __value - __target = min(__length, number of elements in all 1755 * sequences). 1756 * 1757 * @see stable_multiway_merge_sentinels 1758 * 1759 * @tparam _RAIterPairIterator iterator over sequence 1760 * of pairs of iterators 1761 * @tparam _RAIterOut iterator over target sequence 1762 * @tparam _DifferenceTp difference type for the sequence 1763 * @tparam _Compare strict weak ordering type to compare elements 1764 * in sequences 1765 * 1766 * @param __seqs_begin __begin of sequence __sequence 1767 * @param __seqs_end _M_end of sequence __sequence 1768 * @param __target target sequence to merge to. 1769 * @param __comp strict weak ordering to use for element comparison. 1770 * @param __length Maximum length to merge, possibly larger than the 1771 * number of elements available. 1772 * 1773 * @return _M_end iterator of output sequence 1774 */ 1775 // multiway_merge_sentinels 1776 // public interface 1777 template<typename _RAIterPairIterator, 1778 typename _RAIterOut, 1779 typename _DifferenceTp, 1780 typename _Compare> 1781 _RAIterOut 1782 multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, 1783 _RAIterPairIterator __seqs_end, 1784 _RAIterOut __target, 1785 _DifferenceTp __length, _Compare __comp, 1786 __gnu_parallel::sequential_tag) 1787 { 1788 typedef _DifferenceTp _DifferenceType; 1789 _GLIBCXX_CALL(__seqs_end - __seqs_begin) 1790 1791 // catch special case: no sequences 1792 if (__seqs_begin == __seqs_end) 1793 return __target; 1794 1795 // Execute multiway merge *sequentially*. 1796 return __sequential_multiway_merge 1797 </* __stable = */ false, /* __sentinels = */ true> 1798 (__seqs_begin, __seqs_end, 1799 __target, *(__seqs_begin->second), __length, __comp); 1800 } 1801 1802 // public interface 1803 template<typename _RAIterPairIterator, 1804 typename _RAIterOut, 1805 typename _DifferenceTp, 1806 typename _Compare> 1807 _RAIterOut 1808 multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, 1809 _RAIterPairIterator __seqs_end, 1810 _RAIterOut __target, 1811 _DifferenceTp __length, _Compare __comp, 1812 __gnu_parallel::exact_tag __tag) 1813 { 1814 typedef _DifferenceTp _DifferenceType; 1815 _GLIBCXX_CALL(__seqs_end - __seqs_begin) 1816 1817 // catch special case: no sequences 1818 if (__seqs_begin == __seqs_end) 1819 return __target; 1820 1821 // Execute merge; maybe parallel, depending on the number of merged 1822 // elements and the number of sequences and global thresholds in 1823 // Settings. 1824 if ((__seqs_end - __seqs_begin > 1) 1825 && _GLIBCXX_PARALLEL_CONDITION( 1826 ((__seqs_end - __seqs_begin) >= 1827 __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 1828 && ((_SequenceIndex)__length >= 1829 __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 1830 return parallel_multiway_merge 1831 </* __stable = */ false, /* __sentinels = */ true> 1832 (__seqs_begin, __seqs_end, __target, 1833 multiway_merge_exact_splitting</* __stable = */ false, 1834 typename std::iterator_traits<_RAIterPairIterator> 1835 ::value_type*, _Compare, _DifferenceTp>, 1836 static_cast<_DifferenceType>(__length), __comp, 1837 __tag.__get_num_threads()); 1838 else 1839 return __sequential_multiway_merge 1840 </* __stable = */ false, /* __sentinels = */ true> 1841 (__seqs_begin, __seqs_end, __target, 1842 *(__seqs_begin->second), __length, __comp); 1843 } 1844 1845 // public interface 1846 template<typename _RAIterPairIterator, 1847 typename _RAIterOut, 1848 typename _DifferenceTp, 1849 typename _Compare> 1850 _RAIterOut 1851 multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, 1852 _RAIterPairIterator __seqs_end, 1853 _RAIterOut __target, 1854 _DifferenceTp __length, _Compare __comp, 1855 sampling_tag __tag) 1856 { 1857 typedef _DifferenceTp _DifferenceType; 1858 _GLIBCXX_CALL(__seqs_end - __seqs_begin) 1859 1860 // catch special case: no sequences 1861 if (__seqs_begin == __seqs_end) 1862 return __target; 1863 1864 // Execute merge; maybe parallel, depending on the number of merged 1865 // elements and the number of sequences and global thresholds in 1866 // Settings. 1867 if ((__seqs_end - __seqs_begin > 1) 1868 && _GLIBCXX_PARALLEL_CONDITION( 1869 ((__seqs_end - __seqs_begin) >= 1870 __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 1871 && ((_SequenceIndex)__length >= 1872 __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 1873 return parallel_multiway_merge 1874 </* __stable = */ false, /* __sentinels = */ true> 1875 (__seqs_begin, __seqs_end, __target, 1876 multiway_merge_sampling_splitting</* __stable = */ false, 1877 typename std::iterator_traits<_RAIterPairIterator> 1878 ::value_type*, _Compare, _DifferenceTp>, 1879 static_cast<_DifferenceType>(__length), __comp, 1880 __tag.__get_num_threads()); 1881 else 1882 return __sequential_multiway_merge 1883 </* __stable = */false, /* __sentinels = */ true>( 1884 __seqs_begin, __seqs_end, __target, 1885 *(__seqs_begin->second), __length, __comp); 1886 } 1887 1888 // public interface 1889 template<typename _RAIterPairIterator, 1890 typename _RAIterOut, 1891 typename _DifferenceTp, 1892 typename _Compare> 1893 _RAIterOut 1894 multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, 1895 _RAIterPairIterator __seqs_end, 1896 _RAIterOut __target, 1897 _DifferenceTp __length, _Compare __comp, 1898 parallel_tag __tag = parallel_tag(0)) 1899 { 1900 return multiway_merge_sentinels 1901 (__seqs_begin, __seqs_end, __target, __length, __comp, 1902 exact_tag(__tag.__get_num_threads())); 1903 } 1904 1905 // public interface 1906 template<typename _RAIterPairIterator, 1907 typename _RAIterOut, 1908 typename _DifferenceTp, 1909 typename _Compare> 1910 _RAIterOut 1911 multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, 1912 _RAIterPairIterator __seqs_end, 1913 _RAIterOut __target, 1914 _DifferenceTp __length, _Compare __comp, 1915 default_parallel_tag __tag) 1916 { 1917 return multiway_merge_sentinels 1918 (__seqs_begin, __seqs_end, __target, __length, __comp, 1919 exact_tag(__tag.__get_num_threads())); 1920 } 1921 1922 // stable_multiway_merge_sentinels 1923 // public interface 1924 template<typename _RAIterPairIterator, 1925 typename _RAIterOut, 1926 typename _DifferenceTp, 1927 typename _Compare> 1928 _RAIterOut 1929 stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, 1930 _RAIterPairIterator __seqs_end, 1931 _RAIterOut __target, 1932 _DifferenceTp __length, _Compare __comp, 1933 __gnu_parallel::sequential_tag) 1934 { 1935 typedef _DifferenceTp _DifferenceType; 1936 _GLIBCXX_CALL(__seqs_end - __seqs_begin) 1937 1938 // catch special case: no sequences 1939 if (__seqs_begin == __seqs_end) 1940 return __target; 1941 1942 // Execute multiway merge *sequentially*. 1943 return __sequential_multiway_merge 1944 </* __stable = */ true, /* __sentinels = */ true> 1945 (__seqs_begin, __seqs_end, __target, 1946 *(__seqs_begin->second), __length, __comp); 1947 } 1948 1949 // public interface 1950 template<typename _RAIterPairIterator, 1951 typename _RAIterOut, 1952 typename _DifferenceTp, 1953 typename _Compare> 1954 _RAIterOut 1955 stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, 1956 _RAIterPairIterator __seqs_end, 1957 _RAIterOut __target, 1958 _DifferenceTp __length, _Compare __comp, 1959 __gnu_parallel::exact_tag __tag) 1960 { 1961 typedef _DifferenceTp _DifferenceType; 1962 _GLIBCXX_CALL(__seqs_end - __seqs_begin) 1963 1964 // catch special case: no sequences 1965 if (__seqs_begin == __seqs_end) 1966 return __target; 1967 1968 // Execute merge; maybe parallel, depending on the number of merged 1969 // elements and the number of sequences and global thresholds in 1970 // Settings. 1971 if ((__seqs_end - __seqs_begin > 1) 1972 && _GLIBCXX_PARALLEL_CONDITION( 1973 ((__seqs_end - __seqs_begin) >= 1974 __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 1975 && ((_SequenceIndex)__length >= 1976 __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 1977 return parallel_multiway_merge 1978 </* __stable = */ true, /* __sentinels = */ true> 1979 (__seqs_begin, __seqs_end, __target, 1980 multiway_merge_exact_splitting</* __stable = */ true, 1981 typename std::iterator_traits<_RAIterPairIterator> 1982 ::value_type*, _Compare, _DifferenceTp>, 1983 static_cast<_DifferenceType>(__length), __comp, 1984 __tag.__get_num_threads()); 1985 else 1986 return __sequential_multiway_merge 1987 </* __stable = */ true, /* __sentinels = */ true> 1988 (__seqs_begin, __seqs_end, __target, 1989 *(__seqs_begin->second), __length, __comp); 1990 } 1991 1992 // public interface 1993 template<typename _RAIterPairIterator, 1994 typename _RAIterOut, 1995 typename _DifferenceTp, 1996 typename _Compare> 1997 _RAIterOut 1998 stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, 1999 _RAIterPairIterator __seqs_end, 2000 _RAIterOut __target, 2001 _DifferenceTp __length, 2002 _Compare __comp, 2003 sampling_tag __tag) 2004 { 2005 typedef _DifferenceTp _DifferenceType; 2006 _GLIBCXX_CALL(__seqs_end - __seqs_begin) 2007 2008 // catch special case: no sequences 2009 if (__seqs_begin == __seqs_end) 2010 return __target; 2011 2012 // Execute merge; maybe parallel, depending on the number of merged 2013 // elements and the number of sequences and global thresholds in 2014 // Settings. 2015 if ((__seqs_end - __seqs_begin > 1) 2016 && _GLIBCXX_PARALLEL_CONDITION( 2017 ((__seqs_end - __seqs_begin) >= 2018 __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 2019 && ((_SequenceIndex)__length >= 2020 __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 2021 return parallel_multiway_merge 2022 </* __stable = */ true, /* __sentinels = */ true> 2023 (__seqs_begin, __seqs_end, __target, 2024 multiway_merge_sampling_splitting</* __stable = */ true, 2025 typename std::iterator_traits<_RAIterPairIterator> 2026 ::value_type*, _Compare, _DifferenceTp>, 2027 static_cast<_DifferenceType>(__length), __comp, 2028 __tag.__get_num_threads()); 2029 else 2030 return __sequential_multiway_merge 2031 </* __stable = */ true, /* __sentinels = */ true> 2032 (__seqs_begin, __seqs_end, __target, 2033 *(__seqs_begin->second), __length, __comp); 2034 } 2035 2036 // public interface 2037 template<typename _RAIterPairIterator, 2038 typename _RAIterOut, 2039 typename _DifferenceTp, 2040 typename _Compare> 2041 _RAIterOut 2042 stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, 2043 _RAIterPairIterator __seqs_end, 2044 _RAIterOut __target, 2045 _DifferenceTp __length, 2046 _Compare __comp, 2047 parallel_tag __tag = parallel_tag(0)) 2048 { 2049 return stable_multiway_merge_sentinels 2050 (__seqs_begin, __seqs_end, __target, __length, __comp, 2051 exact_tag(__tag.__get_num_threads())); 2052 } 2053 2054 // public interface 2055 template<typename _RAIterPairIterator, 2056 typename _RAIterOut, 2057 typename _DifferenceTp, 2058 typename _Compare> 2059 _RAIterOut 2060 stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, 2061 _RAIterPairIterator __seqs_end, 2062 _RAIterOut __target, 2063 _DifferenceTp __length, _Compare __comp, 2064 default_parallel_tag __tag) 2065 { 2066 return stable_multiway_merge_sentinels 2067 (__seqs_begin, __seqs_end, __target, __length, __comp, 2068 exact_tag(__tag.__get_num_threads())); 2069 } 2070}; // namespace __gnu_parallel 2071 2072#endif /* _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H */ 2073