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