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