libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** @file parallel/multiway_merge.h 00026 * @brief Implementation of sequential and parallel multiway merge. 00027 * 00028 * Explanations on the high-speed merging routines in the appendix of 00029 * 00030 * P. Sanders. 00031 * Fast priority queues for cached memory. 00032 * ACM Journal of Experimental Algorithmics, 5, 2000. 00033 * 00034 * This file is a GNU parallel extension to the Standard C++ Library. 00035 */ 00036 00037 // Written by Johannes Singler and Manuel Holtgrewe. 00038 00039 #ifndef _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H 00040 #define _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H 00041 00042 #include <vector> 00043 00044 #include <bits/stl_algo.h> 00045 #include <parallel/features.h> 00046 #include <parallel/parallel.h> 00047 #include <parallel/losertree.h> 00048 #if _GLIBCXX_ASSERTIONS 00049 #include <parallel/checkers.h> 00050 #endif 00051 00052 /** @brief Length of a sequence described by a pair of iterators. */ 00053 #define _GLIBCXX_PARALLEL_LENGTH(s) ((s).second - (s).first) 00054 00055 namespace __gnu_parallel 00056 { 00057 00058 // Announce guarded and unguarded iterator. 00059 00060 template<typename RandomAccessIterator, typename Comparator> 00061 class guarded_iterator; 00062 00063 // Making the arguments const references seems to dangerous, 00064 // the user-defined comparator might not be const. 00065 template<typename RandomAccessIterator, typename Comparator> 00066 inline bool 00067 operator<(guarded_iterator<RandomAccessIterator, Comparator>& bi1, 00068 guarded_iterator<RandomAccessIterator, Comparator>& bi2); 00069 00070 template<typename RandomAccessIterator, typename Comparator> 00071 inline bool 00072 operator<=(guarded_iterator<RandomAccessIterator, Comparator>& bi1, 00073 guarded_iterator<RandomAccessIterator, Comparator>& bi2); 00074 00075 /** @brief Iterator wrapper supporting an implicit supremum at the end 00076 * of the sequence, dominating all comparisons. 00077 * 00078 * The implicit supremum comes with a performance cost. 00079 * 00080 * Deriving from RandomAccessIterator is not possible since 00081 * RandomAccessIterator need not be a class. 00082 */ 00083 template<typename RandomAccessIterator, typename Comparator> 00084 class guarded_iterator 00085 { 00086 private: 00087 /** @brief Current iterator position. */ 00088 RandomAccessIterator current; 00089 00090 /** @brief End iterator of the sequence. */ 00091 RandomAccessIterator end; 00092 00093 /** @brief Comparator. */ 00094 Comparator& comp; 00095 00096 public: 00097 /** @brief Constructor. Sets iterator to beginning of sequence. 00098 * @param begin Begin iterator of sequence. 00099 * @param end End iterator of sequence. 00100 * @param comp Comparator provided for associated overloaded 00101 * compare operators. */ 00102 guarded_iterator(RandomAccessIterator begin, 00103 RandomAccessIterator end, Comparator& comp) 00104 : current(begin), end(end), comp(comp) 00105 { } 00106 00107 /** @brief Pre-increment operator. 00108 * @return This. */ 00109 guarded_iterator<RandomAccessIterator, Comparator>& 00110 operator++() 00111 { 00112 ++current; 00113 return *this; 00114 } 00115 00116 /** @brief Dereference operator. 00117 * @return Referenced element. */ 00118 typename std::iterator_traits<RandomAccessIterator>::value_type& 00119 operator*() 00120 { return *current; } 00121 00122 /** @brief Convert to wrapped iterator. 00123 * @return Wrapped iterator. */ 00124 operator RandomAccessIterator() 00125 { return current; } 00126 00127 friend bool 00128 operator< <RandomAccessIterator, Comparator>( 00129 guarded_iterator<RandomAccessIterator, Comparator>& bi1, 00130 guarded_iterator<RandomAccessIterator, Comparator>& bi2); 00131 00132 friend bool 00133 operator<= <RandomAccessIterator, Comparator>( 00134 guarded_iterator<RandomAccessIterator, Comparator>& bi1, 00135 guarded_iterator<RandomAccessIterator, Comparator>& bi2); 00136 }; 00137 00138 /** @brief Compare two elements referenced by guarded iterators. 00139 * @param bi1 First iterator. 00140 * @param bi2 Second iterator. 00141 * @return @c True if less. */ 00142 template<typename RandomAccessIterator, typename Comparator> 00143 inline bool 00144 operator<(guarded_iterator<RandomAccessIterator, Comparator>& bi1, 00145 guarded_iterator<RandomAccessIterator, Comparator>& bi2) 00146 { 00147 if (bi1.current == bi1.end) //bi1 is sup 00148 return bi2.current == bi2.end; //bi2 is not sup 00149 if (bi2.current == bi2.end) //bi2 is sup 00150 return true; 00151 return (bi1.comp)(*bi1, *bi2); //normal compare 00152 } 00153 00154 /** @brief Compare two elements referenced by guarded iterators. 00155 * @param bi1 First iterator. 00156 * @param bi2 Second iterator. 00157 * @return @c True if less equal. */ 00158 template<typename RandomAccessIterator, typename Comparator> 00159 inline bool 00160 operator<=(guarded_iterator<RandomAccessIterator, Comparator>& bi1, 00161 guarded_iterator<RandomAccessIterator, Comparator>& bi2) 00162 { 00163 if (bi2.current == bi2.end) //bi1 is sup 00164 return bi1.current != bi1.end; //bi2 is not sup 00165 if (bi1.current == bi1.end) //bi2 is sup 00166 return false; 00167 return !(bi1.comp)(*bi2, *bi1); //normal compare 00168 } 00169 00170 template<typename RandomAccessIterator, typename Comparator> 00171 class unguarded_iterator; 00172 00173 template<typename RandomAccessIterator, typename Comparator> 00174 inline bool 00175 operator<(unguarded_iterator<RandomAccessIterator, Comparator>& bi1, 00176 unguarded_iterator<RandomAccessIterator, Comparator>& bi2); 00177 00178 template<typename RandomAccessIterator, typename Comparator> 00179 inline bool 00180 operator<=(unguarded_iterator<RandomAccessIterator, Comparator>& bi1, 00181 unguarded_iterator<RandomAccessIterator, Comparator>& bi2); 00182 00183 template<typename RandomAccessIterator, typename Comparator> 00184 class unguarded_iterator 00185 { 00186 private: 00187 /** @brief Current iterator position. */ 00188 RandomAccessIterator current; 00189 /** @brief Comparator. */ 00190 mutable Comparator& comp; 00191 00192 public: 00193 /** @brief Constructor. Sets iterator to beginning of sequence. 00194 * @param begin Begin iterator of sequence. 00195 * @param end Unused, only for compatibility. 00196 * @param comp Unused, only for compatibility. */ 00197 unguarded_iterator(RandomAccessIterator begin, 00198 RandomAccessIterator end, Comparator& comp) 00199 : current(begin), comp(comp) 00200 { } 00201 00202 /** @brief Pre-increment operator. 00203 * @return This. */ 00204 unguarded_iterator<RandomAccessIterator, Comparator>& 00205 operator++() 00206 { 00207 ++current; 00208 return *this; 00209 } 00210 00211 /** @brief Dereference operator. 00212 * @return Referenced element. */ 00213 typename std::iterator_traits<RandomAccessIterator>::value_type& 00214 operator*() 00215 { return *current; } 00216 00217 /** @brief Convert to wrapped iterator. 00218 * @return Wrapped iterator. */ 00219 operator RandomAccessIterator() 00220 { return current; } 00221 00222 friend bool 00223 operator< <RandomAccessIterator, Comparator>( 00224 unguarded_iterator<RandomAccessIterator, Comparator>& bi1, 00225 unguarded_iterator<RandomAccessIterator, Comparator>& bi2); 00226 00227 friend bool 00228 operator<= <RandomAccessIterator, Comparator>( 00229 unguarded_iterator<RandomAccessIterator, Comparator>& bi1, 00230 unguarded_iterator<RandomAccessIterator, Comparator>& bi2); 00231 }; 00232 00233 /** @brief Compare two elements referenced by unguarded iterators. 00234 * @param bi1 First iterator. 00235 * @param bi2 Second iterator. 00236 * @return @c True if less. */ 00237 template<typename RandomAccessIterator, typename Comparator> 00238 inline bool 00239 operator<(unguarded_iterator<RandomAccessIterator, Comparator>& bi1, 00240 unguarded_iterator<RandomAccessIterator, Comparator>& bi2) 00241 { 00242 // Normal compare. 00243 return (bi1.comp)(*bi1, *bi2); 00244 } 00245 00246 /** @brief Compare two elements referenced by unguarded iterators. 00247 * @param bi1 First iterator. 00248 * @param bi2 Second iterator. 00249 * @return @c True if less equal. */ 00250 template<typename RandomAccessIterator, typename Comparator> 00251 inline bool 00252 operator<=(unguarded_iterator<RandomAccessIterator, Comparator>& bi1, 00253 unguarded_iterator<RandomAccessIterator, Comparator>& bi2) 00254 { 00255 // Normal compare. 00256 return !(bi1.comp)(*bi2, *bi1); 00257 } 00258 00259 /** @brief Highly efficient 3-way merging procedure. 00260 * 00261 * Merging is done with the algorithm implementation described by Peter 00262 * Sanders. Basically, the idea is to minimize the number of necessary 00263 * comparison after merging out an element. The implementation trick 00264 * that makes this fast is that the order of the sequences is stored 00265 * in the instruction pointer (translated into labels in C++). 00266 * 00267 * This works well for merging up to 4 sequences. 00268 * 00269 * Note that making the merging stable does <em>not</em> come at a 00270 * performance hit. 00271 * 00272 * Whether the merging is done guarded or unguarded is selected by the 00273 * used iterator class. 00274 * 00275 * @param seqs_begin Begin iterator of iterator pair input sequence. 00276 * @param seqs_end End iterator of iterator pair input sequence. 00277 * @param target Begin iterator out output sequence. 00278 * @param comp Comparator. 00279 * @param length Maximum length to merge, less equal than the 00280 * total number of elements available. 00281 * 00282 * @return End iterator of output sequence. 00283 */ 00284 template<template<typename RAI, typename C> class iterator, 00285 typename RandomAccessIteratorIterator, 00286 typename RandomAccessIterator3, 00287 typename _DifferenceTp, 00288 typename Comparator> 00289 RandomAccessIterator3 00290 multiway_merge_3_variant( 00291 RandomAccessIteratorIterator seqs_begin, 00292 RandomAccessIteratorIterator seqs_end, 00293 RandomAccessIterator3 target, 00294 _DifferenceTp length, Comparator comp) 00295 { 00296 _GLIBCXX_CALL(length); 00297 00298 typedef _DifferenceTp difference_type; 00299 00300 typedef typename std::iterator_traits<RandomAccessIteratorIterator> 00301 ::value_type::first_type 00302 RandomAccessIterator1; 00303 typedef typename std::iterator_traits<RandomAccessIterator1>::value_type 00304 value_type; 00305 00306 if (length == 0) 00307 return target; 00308 00309 #if _GLIBCXX_ASSERTIONS 00310 _DifferenceTp orig_length = length; 00311 #endif 00312 00313 iterator<RandomAccessIterator1, Comparator> 00314 seq0(seqs_begin[0].first, seqs_begin[0].second, comp), 00315 seq1(seqs_begin[1].first, seqs_begin[1].second, comp), 00316 seq2(seqs_begin[2].first, seqs_begin[2].second, comp); 00317 00318 if (seq0 <= seq1) 00319 { 00320 if (seq1 <= seq2) 00321 goto s012; 00322 else 00323 if (seq2 < seq0) 00324 goto s201; 00325 else 00326 goto s021; 00327 } 00328 else 00329 { 00330 if (seq1 <= seq2) 00331 { 00332 if (seq0 <= seq2) 00333 goto s102; 00334 else 00335 goto s120; 00336 } 00337 else 00338 goto s210; 00339 } 00340 #define _GLIBCXX_PARALLEL_MERGE_3_CASE(a,b,c,c0,c1) \ 00341 s ## a ## b ## c : \ 00342 *target = *seq ## a; \ 00343 ++target; \ 00344 --length; \ 00345 ++seq ## a; \ 00346 if (length == 0) goto finish; \ 00347 if (seq ## a c0 seq ## b) goto s ## a ## b ## c; \ 00348 if (seq ## a c1 seq ## c) goto s ## b ## a ## c; \ 00349 goto s ## b ## c ## a; 00350 00351 _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 1, 2, <=, <=); 00352 _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 2, 0, <=, < ); 00353 _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 0, 1, < , < ); 00354 _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 0, 2, < , <=); 00355 _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 2, 1, <=, <=); 00356 _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 1, 0, < , < ); 00357 00358 #undef _GLIBCXX_PARALLEL_MERGE_3_CASE 00359 00360 finish: 00361 ; 00362 00363 #if _GLIBCXX_ASSERTIONS 00364 _GLIBCXX_PARALLEL_ASSERT( 00365 ((RandomAccessIterator1)seq0 - seqs_begin[0].first) + 00366 ((RandomAccessIterator1)seq1 - seqs_begin[1].first) + 00367 ((RandomAccessIterator1)seq2 - seqs_begin[2].first) 00368 == orig_length); 00369 #endif 00370 00371 seqs_begin[0].first = seq0; 00372 seqs_begin[1].first = seq1; 00373 seqs_begin[2].first = seq2; 00374 00375 return target; 00376 } 00377 00378 /** 00379 * @brief Highly efficient 4-way merging procedure. 00380 * 00381 * Merging is done with the algorithm implementation described by Peter 00382 * Sanders. Basically, the idea is to minimize the number of necessary 00383 * comparison after merging out an element. The implementation trick 00384 * that makes this fast is that the order of the sequences is stored 00385 * in the instruction pointer (translated into goto labels in C++). 00386 * 00387 * This works well for merging up to 4 sequences. 00388 * 00389 * Note that making the merging stable does <em>not</em> come at a 00390 * performance hit. 00391 * 00392 * Whether the merging is done guarded or unguarded is selected by the 00393 * used iterator class. 00394 * 00395 * @param seqs_begin Begin iterator of iterator pair input sequence. 00396 * @param seqs_end End iterator of iterator pair input sequence. 00397 * @param target Begin iterator out output sequence. 00398 * @param comp Comparator. 00399 * @param length Maximum length to merge, less equal than the 00400 * total number of elements available. 00401 * 00402 * @return End iterator of output sequence. 00403 */ 00404 template<template<typename RAI, typename C> class iterator, 00405 typename RandomAccessIteratorIterator, 00406 typename RandomAccessIterator3, 00407 typename _DifferenceTp, 00408 typename Comparator> 00409 RandomAccessIterator3 00410 multiway_merge_4_variant(RandomAccessIteratorIterator seqs_begin, 00411 RandomAccessIteratorIterator seqs_end, 00412 RandomAccessIterator3 target, 00413 _DifferenceTp length, Comparator comp) 00414 { 00415 _GLIBCXX_CALL(length); 00416 typedef _DifferenceTp difference_type; 00417 00418 typedef typename std::iterator_traits<RandomAccessIteratorIterator> 00419 ::value_type::first_type 00420 RandomAccessIterator1; 00421 typedef typename std::iterator_traits<RandomAccessIterator1>::value_type 00422 value_type; 00423 00424 iterator<RandomAccessIterator1, Comparator> 00425 seq0(seqs_begin[0].first, seqs_begin[0].second, comp), 00426 seq1(seqs_begin[1].first, seqs_begin[1].second, comp), 00427 seq2(seqs_begin[2].first, seqs_begin[2].second, comp), 00428 seq3(seqs_begin[3].first, seqs_begin[3].second, comp); 00429 00430 #define _GLIBCXX_PARALLEL_DECISION(a,b,c,d) { \ 00431 if (seq ## d < seq ## a) goto s ## d ## a ## b ## c; \ 00432 if (seq ## d < seq ## b) goto s ## a ## d ## b ## c; \ 00433 if (seq ## d < seq ## c) goto s ## a ## b ## d ## c; \ 00434 goto s ## a ## b ## c ## d; } 00435 00436 if (seq0 <= seq1) 00437 { 00438 if (seq1 <= seq2) 00439 _GLIBCXX_PARALLEL_DECISION(0,1,2,3) 00440 else 00441 if (seq2 < seq0) 00442 _GLIBCXX_PARALLEL_DECISION(2,0,1,3) 00443 else 00444 _GLIBCXX_PARALLEL_DECISION(0,2,1,3) 00445 } 00446 else 00447 { 00448 if (seq1 <= seq2) 00449 { 00450 if (seq0 <= seq2) 00451 _GLIBCXX_PARALLEL_DECISION(1,0,2,3) 00452 else 00453 _GLIBCXX_PARALLEL_DECISION(1,2,0,3) 00454 } 00455 else 00456 _GLIBCXX_PARALLEL_DECISION(2,1,0,3) 00457 } 00458 00459 #define _GLIBCXX_PARALLEL_MERGE_4_CASE(a,b,c,d,c0,c1,c2) \ 00460 s ## a ## b ## c ## d: \ 00461 if (length == 0) goto finish; \ 00462 *target = *seq ## a; \ 00463 ++target; \ 00464 --length; \ 00465 ++seq ## a; \ 00466 if (seq ## a c0 seq ## b) goto s ## a ## b ## c ## d; \ 00467 if (seq ## a c1 seq ## c) goto s ## b ## a ## c ## d; \ 00468 if (seq ## a c2 seq ## d) goto s ## b ## c ## a ## d; \ 00469 goto s ## b ## c ## d ## a; 00470 00471 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 2, 3, <=, <=, <=); 00472 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 3, 2, <=, <=, <=); 00473 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 1, 3, <=, <=, <=); 00474 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 3, 1, <=, <=, <=); 00475 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 1, 2, <=, <=, <=); 00476 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 2, 1, <=, <=, <=); 00477 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 2, 3, < , <=, <=); 00478 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 3, 2, < , <=, <=); 00479 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 0, 3, <=, < , <=); 00480 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 3, 0, <=, <=, < ); 00481 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 0, 2, <=, < , <=); 00482 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 2, 0, <=, <=, < ); 00483 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 1, 3, < , < , <=); 00484 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 3, 1, < , <=, < ); 00485 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 0, 3, < , < , <=); 00486 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 3, 0, < , <=, < ); 00487 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 0, 1, <=, < , < ); 00488 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 1, 0, <=, < , < ); 00489 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 1, 2, < , < , < ); 00490 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 2, 1, < , < , < ); 00491 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 0, 2, < , < , < ); 00492 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 2, 0, < , < , < ); 00493 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 0, 1, < , < , < ); 00494 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 1, 0, < , < , < ); 00495 00496 #undef _GLIBCXX_PARALLEL_MERGE_4_CASE 00497 #undef _GLIBCXX_PARALLEL_DECISION 00498 00499 finish: 00500 ; 00501 00502 seqs_begin[0].first = seq0; 00503 seqs_begin[1].first = seq1; 00504 seqs_begin[2].first = seq2; 00505 seqs_begin[3].first = seq3; 00506 00507 return target; 00508 } 00509 00510 /** @brief Multi-way merging procedure for a high branching factor, 00511 * guarded case. 00512 * 00513 * This merging variant uses a LoserTree class as selected by <tt>LT</tt>. 00514 * 00515 * Stability is selected through the used LoserTree class <tt>LT</tt>. 00516 * 00517 * At least one non-empty sequence is required. 00518 * 00519 * @param seqs_begin Begin iterator of iterator pair input sequence. 00520 * @param seqs_end End iterator of iterator pair input sequence. 00521 * @param target Begin iterator out output sequence. 00522 * @param comp Comparator. 00523 * @param length Maximum length to merge, less equal than the 00524 * total number of elements available. 00525 * 00526 * @return End iterator of output sequence. 00527 */ 00528 template<typename LT, 00529 typename RandomAccessIteratorIterator, 00530 typename RandomAccessIterator3, 00531 typename _DifferenceTp, 00532 typename Comparator> 00533 RandomAccessIterator3 00534 multiway_merge_loser_tree(RandomAccessIteratorIterator seqs_begin, 00535 RandomAccessIteratorIterator seqs_end, 00536 RandomAccessIterator3 target, 00537 _DifferenceTp length, Comparator comp) 00538 { 00539 _GLIBCXX_CALL(length) 00540 00541 typedef _DifferenceTp difference_type; 00542 typedef typename std::iterator_traits<RandomAccessIteratorIterator> 00543 ::value_type::first_type 00544 RandomAccessIterator1; 00545 typedef typename std::iterator_traits<RandomAccessIterator1>::value_type 00546 value_type; 00547 00548 int k = static_cast<int>(seqs_end - seqs_begin); 00549 00550 LT lt(k, comp); 00551 00552 // Default value for potentially non-default-constructible types. 00553 value_type* arbitrary_element = NULL; 00554 00555 for (int t = 0; t < k; ++t) 00556 { 00557 if(arbitrary_element == NULL 00558 && _GLIBCXX_PARALLEL_LENGTH(seqs_begin[t]) > 0) 00559 arbitrary_element = &(*seqs_begin[t].first); 00560 } 00561 00562 for (int t = 0; t < k; ++t) 00563 { 00564 if (seqs_begin[t].first == seqs_begin[t].second) 00565 lt.insert_start(*arbitrary_element, t, true); 00566 else 00567 lt.insert_start(*seqs_begin[t].first, t, false); 00568 } 00569 00570 lt.init(); 00571 00572 int source; 00573 00574 for (difference_type i = 0; i < length; ++i) 00575 { 00576 //take out 00577 source = lt.get_min_source(); 00578 00579 *(target++) = *(seqs_begin[source].first++); 00580 00581 // Feed. 00582 if (seqs_begin[source].first == seqs_begin[source].second) 00583 lt.delete_min_insert(*arbitrary_element, true); 00584 else 00585 // Replace from same source. 00586 lt.delete_min_insert(*seqs_begin[source].first, false); 00587 } 00588 00589 return target; 00590 } 00591 00592 /** @brief Multi-way merging procedure for a high branching factor, 00593 * unguarded case. 00594 * 00595 * Merging is done using the LoserTree class <tt>LT</tt>. 00596 * 00597 * Stability is selected by the used LoserTrees. 00598 * 00599 * @pre No input will run out of elements during the merge. 00600 * 00601 * @param seqs_begin Begin iterator of iterator pair input sequence. 00602 * @param seqs_end End iterator of iterator pair input sequence. 00603 * @param target Begin iterator out output sequence. 00604 * @param comp Comparator. 00605 * @param length Maximum length to merge, less equal than the 00606 * total number of elements available. 00607 * 00608 * @return End iterator of output sequence. 00609 */ 00610 template<typename LT, 00611 typename RandomAccessIteratorIterator, 00612 typename RandomAccessIterator3, 00613 typename _DifferenceTp, typename Comparator> 00614 RandomAccessIterator3 00615 multiway_merge_loser_tree_unguarded( 00616 RandomAccessIteratorIterator seqs_begin, 00617 RandomAccessIteratorIterator seqs_end, 00618 RandomAccessIterator3 target, 00619 const typename std::iterator_traits<typename std::iterator_traits< 00620 RandomAccessIteratorIterator>::value_type::first_type>::value_type& 00621 sentinel, 00622 _DifferenceTp length, 00623 Comparator comp) 00624 { 00625 _GLIBCXX_CALL(length) 00626 typedef _DifferenceTp difference_type; 00627 00628 typedef typename std::iterator_traits<RandomAccessIteratorIterator> 00629 ::value_type::first_type 00630 RandomAccessIterator1; 00631 typedef typename std::iterator_traits<RandomAccessIterator1>::value_type 00632 value_type; 00633 00634 int k = seqs_end - seqs_begin; 00635 00636 LT lt(k, sentinel, comp); 00637 00638 for (int t = 0; t < k; ++t) 00639 { 00640 #if _GLIBCXX_ASSERTIONS 00641 _GLIBCXX_PARALLEL_ASSERT(seqs_begin[t].first != seqs_begin[t].second); 00642 #endif 00643 lt.insert_start(*seqs_begin[t].first, t, false); 00644 } 00645 00646 lt.init(); 00647 00648 int source; 00649 00650 #if _GLIBCXX_ASSERTIONS 00651 difference_type i = 0; 00652 #endif 00653 00654 RandomAccessIterator3 target_end = target + length; 00655 while (target < target_end) 00656 { 00657 // Take out. 00658 source = lt.get_min_source(); 00659 00660 #if _GLIBCXX_ASSERTIONS 00661 _GLIBCXX_PARALLEL_ASSERT(0 <= source && source < k); 00662 _GLIBCXX_PARALLEL_ASSERT(i == 0 00663 || !comp(*(seqs_begin[source].first), *(target - 1))); 00664 #endif 00665 00666 // Feed. 00667 *(target++) = *(seqs_begin[source].first++); 00668 00669 #if _GLIBCXX_ASSERTIONS 00670 ++i; 00671 #endif 00672 // Replace from same source. 00673 lt.delete_min_insert(*seqs_begin[source].first, false); 00674 } 00675 00676 return target; 00677 } 00678 00679 00680 /** @brief Multi-way merging procedure for a high branching factor, 00681 * requiring sentinels to exist. 00682 * 00683 * @param stable The value must the same as for the used LoserTrees. 00684 * @param UnguardedLoserTree Loser Tree variant to use for the unguarded 00685 * merging. 00686 * @param GuardedLoserTree Loser Tree variant to use for the guarded 00687 * merging. 00688 * 00689 * @param seqs_begin Begin iterator of iterator pair input sequence. 00690 * @param seqs_end End iterator of iterator pair input sequence. 00691 * @param target Begin iterator out output sequence. 00692 * @param comp Comparator. 00693 * @param length Maximum length to merge, less equal than the 00694 * total number of elements available. 00695 * 00696 * @return End iterator of output sequence. 00697 */ 00698 template< 00699 typename UnguardedLoserTree, 00700 typename RandomAccessIteratorIterator, 00701 typename RandomAccessIterator3, 00702 typename _DifferenceTp, 00703 typename Comparator> 00704 RandomAccessIterator3 00705 multiway_merge_loser_tree_sentinel( 00706 RandomAccessIteratorIterator seqs_begin, 00707 RandomAccessIteratorIterator seqs_end, 00708 RandomAccessIterator3 target, 00709 const typename std::iterator_traits<typename std::iterator_traits< 00710 RandomAccessIteratorIterator>::value_type::first_type>::value_type& 00711 sentinel, 00712 _DifferenceTp length, 00713 Comparator comp) 00714 { 00715 _GLIBCXX_CALL(length) 00716 00717 typedef _DifferenceTp difference_type; 00718 typedef std::iterator_traits<RandomAccessIteratorIterator> traits_type; 00719 typedef typename std::iterator_traits<RandomAccessIteratorIterator> 00720 ::value_type::first_type 00721 RandomAccessIterator1; 00722 typedef typename std::iterator_traits<RandomAccessIterator1>::value_type 00723 value_type; 00724 00725 RandomAccessIterator3 target_end; 00726 00727 for (RandomAccessIteratorIterator s = seqs_begin; s != seqs_end; ++s) 00728 // Move the sequends end behind the sentinel spots. This has the 00729 // effect that the sentinel appears to be within the sequence. Then, 00730 // we can use the unguarded variant if we merge out as many 00731 // non-sentinel elements as we have. 00732 ++((*s).second); 00733 00734 target_end = multiway_merge_loser_tree_unguarded 00735 <UnguardedLoserTree> 00736 (seqs_begin, seqs_end, target, sentinel, length, comp); 00737 00738 #if _GLIBCXX_ASSERTIONS 00739 _GLIBCXX_PARALLEL_ASSERT(target_end == target + length); 00740 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target, target_end, comp)); 00741 #endif 00742 00743 // Restore the sequence ends so the sentinels are not contained in the 00744 // sequence any more (see comment in loop above). 00745 for (RandomAccessIteratorIterator s = seqs_begin; s != seqs_end; ++s) 00746 --((*s).second); 00747 00748 return target_end; 00749 } 00750 00751 /** 00752 * @brief Traits for determining whether the loser tree should 00753 * use pointers or copies. 00754 * 00755 * The field "use_pointer" is used to determine whether to use pointers in 00756 * the loser trees or whether to copy the values into the loser tree. 00757 * 00758 * The default behavior is to use pointers if the data type is 4 times as 00759 * big as the pointer to it. 00760 * 00761 * Specialize for your data type to customize the behavior. 00762 * 00763 * Example: 00764 * 00765 * template<> 00766 * struct loser_tree_traits<int> 00767 * { static const bool use_pointer = false; }; 00768 * 00769 * template<> 00770 * struct loser_tree_traits<heavyweight_type> 00771 * { static const bool use_pointer = true; }; 00772 * 00773 * @param T type to give the loser tree traits for. 00774 */ 00775 template <typename T> 00776 struct loser_tree_traits 00777 { 00778 /** 00779 * @brief True iff to use pointers instead of values in loser trees. 00780 * 00781 * The default behavior is to use pointers if the data type is four 00782 * times as big as the pointer to it. 00783 */ 00784 static const bool use_pointer = (sizeof(T) > 4 * sizeof(T*)); 00785 }; 00786 00787 /** 00788 * @brief Switch for 3-way merging with sentinels turned off. 00789 * 00790 * Note that 3-way merging is always stable! 00791 */ 00792 template< 00793 bool sentinels /*default == false*/, 00794 typename RandomAccessIteratorIterator, 00795 typename RandomAccessIterator3, 00796 typename _DifferenceTp, 00797 typename Comparator> 00798 struct multiway_merge_3_variant_sentinel_switch 00799 { 00800 RandomAccessIterator3 operator()( 00801 RandomAccessIteratorIterator seqs_begin, 00802 RandomAccessIteratorIterator seqs_end, 00803 RandomAccessIterator3 target, 00804 _DifferenceTp length, Comparator comp) 00805 { 00806 return multiway_merge_3_variant<guarded_iterator>( 00807 seqs_begin, seqs_end, target, length, comp); 00808 } 00809 }; 00810 00811 /** 00812 * @brief Switch for 3-way merging with sentinels turned on. 00813 * 00814 * Note that 3-way merging is always stable! 00815 */ 00816 template< 00817 typename RandomAccessIteratorIterator, 00818 typename RandomAccessIterator3, 00819 typename _DifferenceTp, 00820 typename Comparator> 00821 struct multiway_merge_3_variant_sentinel_switch 00822 <true, RandomAccessIteratorIterator, RandomAccessIterator3, 00823 _DifferenceTp, Comparator> 00824 { 00825 RandomAccessIterator3 operator()( 00826 RandomAccessIteratorIterator seqs_begin, 00827 RandomAccessIteratorIterator seqs_end, 00828 RandomAccessIterator3 target, 00829 _DifferenceTp length, Comparator comp) 00830 { 00831 return multiway_merge_3_variant<unguarded_iterator>( 00832 seqs_begin, seqs_end, target, length, comp); 00833 } 00834 }; 00835 00836 /** 00837 * @brief Switch for 4-way merging with sentinels turned off. 00838 * 00839 * Note that 4-way merging is always stable! 00840 */ 00841 template< 00842 bool sentinels /*default == false*/, 00843 typename RandomAccessIteratorIterator, 00844 typename RandomAccessIterator3, 00845 typename _DifferenceTp, 00846 typename Comparator> 00847 struct multiway_merge_4_variant_sentinel_switch 00848 { 00849 RandomAccessIterator3 operator()( 00850 RandomAccessIteratorIterator seqs_begin, 00851 RandomAccessIteratorIterator seqs_end, 00852 RandomAccessIterator3 target, 00853 _DifferenceTp length, Comparator comp) 00854 { 00855 return multiway_merge_4_variant<guarded_iterator>( 00856 seqs_begin, seqs_end, target, length, comp); 00857 } 00858 }; 00859 00860 /** 00861 * @brief Switch for 4-way merging with sentinels turned on. 00862 * 00863 * Note that 4-way merging is always stable! 00864 */ 00865 template< 00866 typename RandomAccessIteratorIterator, 00867 typename RandomAccessIterator3, 00868 typename _DifferenceTp, 00869 typename Comparator> 00870 struct multiway_merge_4_variant_sentinel_switch 00871 <true, RandomAccessIteratorIterator, RandomAccessIterator3, 00872 _DifferenceTp, Comparator> 00873 { 00874 RandomAccessIterator3 operator()( 00875 RandomAccessIteratorIterator seqs_begin, 00876 RandomAccessIteratorIterator seqs_end, 00877 RandomAccessIterator3 target, 00878 _DifferenceTp length, Comparator comp) 00879 { 00880 return multiway_merge_4_variant<unguarded_iterator>( 00881 seqs_begin, seqs_end, target, length, comp); 00882 } 00883 }; 00884 00885 /** 00886 * @brief Switch for k-way merging with sentinels turned on. 00887 */ 00888 template< 00889 bool sentinels, 00890 bool stable, 00891 typename RandomAccessIteratorIterator, 00892 typename RandomAccessIterator3, 00893 typename _DifferenceTp, 00894 typename Comparator> 00895 struct multiway_merge_k_variant_sentinel_switch 00896 { 00897 RandomAccessIterator3 operator()( 00898 RandomAccessIteratorIterator seqs_begin, 00899 RandomAccessIteratorIterator seqs_end, 00900 RandomAccessIterator3 target, 00901 const typename std::iterator_traits<typename std::iterator_traits< 00902 RandomAccessIteratorIterator>::value_type::first_type>::value_type& 00903 sentinel, 00904 _DifferenceTp length, Comparator comp) 00905 { 00906 typedef typename std::iterator_traits<RandomAccessIteratorIterator> 00907 ::value_type::first_type 00908 RandomAccessIterator1; 00909 typedef typename std::iterator_traits<RandomAccessIterator1>::value_type 00910 value_type; 00911 00912 return multiway_merge_loser_tree_sentinel< 00913 typename __gnu_cxx::__conditional_type< 00914 loser_tree_traits<value_type>::use_pointer 00915 , LoserTreePointerUnguarded<stable, value_type, Comparator> 00916 , LoserTreeUnguarded<stable, value_type, Comparator> 00917 >::__type>(seqs_begin, seqs_end, target, sentinel, length, comp); 00918 } 00919 }; 00920 00921 /** 00922 * @brief Switch for k-way merging with sentinels turned off. 00923 */ 00924 template< 00925 bool stable, 00926 typename RandomAccessIteratorIterator, 00927 typename RandomAccessIterator3, 00928 typename _DifferenceTp, 00929 typename Comparator> 00930 struct multiway_merge_k_variant_sentinel_switch 00931 <false, stable, RandomAccessIteratorIterator, RandomAccessIterator3, 00932 _DifferenceTp, Comparator> 00933 { 00934 RandomAccessIterator3 operator()( 00935 RandomAccessIteratorIterator seqs_begin, 00936 RandomAccessIteratorIterator seqs_end, 00937 RandomAccessIterator3 target, 00938 const typename std::iterator_traits<typename std::iterator_traits< 00939 RandomAccessIteratorIterator>::value_type::first_type>::value_type& 00940 sentinel, 00941 _DifferenceTp length, Comparator comp) 00942 { 00943 typedef typename std::iterator_traits<RandomAccessIteratorIterator> 00944 ::value_type::first_type 00945 RandomAccessIterator1; 00946 typedef typename std::iterator_traits<RandomAccessIterator1>::value_type 00947 value_type; 00948 00949 return multiway_merge_loser_tree< 00950 typename __gnu_cxx::__conditional_type< 00951 loser_tree_traits<value_type>::use_pointer 00952 , LoserTreePointer<stable, value_type, Comparator> 00953 , LoserTree<stable, value_type, Comparator> 00954 >::__type >(seqs_begin, seqs_end, target, length, comp); 00955 } 00956 }; 00957 00958 /** @brief Sequential multi-way merging switch. 00959 * 00960 * The _GLIBCXX_PARALLEL_DECISION is based on the branching factor and 00961 * runtime settings. 00962 * @param seqs_begin Begin iterator of iterator pair input sequence. 00963 * @param seqs_end End iterator of iterator pair input sequence. 00964 * @param target Begin iterator out output sequence. 00965 * @param comp Comparator. 00966 * @param length Maximum length to merge, possibly larger than the 00967 * number of elements available. 00968 * @param stable Stable merging incurs a performance penalty. 00969 * @param sentinel The sequences have a sentinel element. 00970 * @return End iterator of output sequence. */ 00971 template< 00972 bool stable, 00973 bool sentinels, 00974 typename RandomAccessIteratorIterator, 00975 typename RandomAccessIterator3, 00976 typename _DifferenceTp, 00977 typename Comparator> 00978 RandomAccessIterator3 00979 sequential_multiway_merge( 00980 RandomAccessIteratorIterator seqs_begin, 00981 RandomAccessIteratorIterator seqs_end, 00982 RandomAccessIterator3 target, 00983 const typename std::iterator_traits<typename std::iterator_traits< 00984 RandomAccessIteratorIterator>::value_type::first_type>::value_type& 00985 sentinel, 00986 _DifferenceTp length, Comparator comp) 00987 { 00988 _GLIBCXX_CALL(length) 00989 00990 typedef _DifferenceTp difference_type; 00991 typedef typename std::iterator_traits<RandomAccessIteratorIterator> 00992 ::value_type::first_type 00993 RandomAccessIterator1; 00994 typedef typename std::iterator_traits<RandomAccessIterator1>::value_type 00995 value_type; 00996 00997 #if _GLIBCXX_ASSERTIONS 00998 for (RandomAccessIteratorIterator s = seqs_begin; s != seqs_end; ++s) 00999 { 01000 _GLIBCXX_PARALLEL_ASSERT(is_sorted((*s).first, (*s).second, comp)); 01001 } 01002 #endif 01003 01004 _DifferenceTp total_length = 0; 01005 for (RandomAccessIteratorIterator s = seqs_begin; s != seqs_end; ++s) 01006 total_length += _GLIBCXX_PARALLEL_LENGTH(*s); 01007 01008 length = std::min<_DifferenceTp>(length, total_length); 01009 01010 if(length == 0) 01011 return target; 01012 01013 RandomAccessIterator3 return_target = target; 01014 int k = static_cast<int>(seqs_end - seqs_begin); 01015 01016 switch (k) 01017 { 01018 case 0: 01019 break; 01020 case 1: 01021 return_target = std::copy(seqs_begin[0].first, 01022 seqs_begin[0].first + length, 01023 target); 01024 seqs_begin[0].first += length; 01025 break; 01026 case 2: 01027 return_target = merge_advance(seqs_begin[0].first, 01028 seqs_begin[0].second, 01029 seqs_begin[1].first, 01030 seqs_begin[1].second, 01031 target, length, comp); 01032 break; 01033 case 3: 01034 return_target = multiway_merge_3_variant_sentinel_switch< 01035 sentinels 01036 , RandomAccessIteratorIterator 01037 , RandomAccessIterator3 01038 , _DifferenceTp 01039 , Comparator>()(seqs_begin, seqs_end, target, length, comp); 01040 break; 01041 case 4: 01042 return_target = multiway_merge_4_variant_sentinel_switch< 01043 sentinels 01044 , RandomAccessIteratorIterator 01045 , RandomAccessIterator3 01046 , _DifferenceTp 01047 , Comparator>()(seqs_begin, seqs_end, target, length, comp); 01048 break; 01049 default: 01050 return_target = multiway_merge_k_variant_sentinel_switch< 01051 sentinels 01052 , stable 01053 , RandomAccessIteratorIterator 01054 , RandomAccessIterator3 01055 , _DifferenceTp 01056 , Comparator>()(seqs_begin, seqs_end, target, sentinel, length, comp); 01057 break; 01058 } 01059 #if _GLIBCXX_ASSERTIONS 01060 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target, target + length, comp)); 01061 #endif 01062 01063 return return_target; 01064 } 01065 01066 /** 01067 * @brief Stable sorting functor. 01068 * 01069 * Used to reduce code instanciation in multiway_merge_sampling_splitting. 01070 */ 01071 template<bool stable, class RandomAccessIterator, class StrictWeakOrdering> 01072 struct sampling_sorter 01073 { 01074 void operator()(RandomAccessIterator first, RandomAccessIterator last, 01075 StrictWeakOrdering comp) 01076 { __gnu_sequential::stable_sort(first, last, comp); } 01077 }; 01078 01079 /** 01080 * @brief Non-stable sorting functor. 01081 * 01082 * Used to reduce code instantiation in multiway_merge_sampling_splitting. 01083 */ 01084 template<class RandomAccessIterator, class StrictWeakOrdering> 01085 struct sampling_sorter<false, RandomAccessIterator, StrictWeakOrdering> 01086 { 01087 void operator()(RandomAccessIterator first, RandomAccessIterator last, 01088 StrictWeakOrdering comp) 01089 { __gnu_sequential::sort(first, last, comp); } 01090 }; 01091 01092 /** 01093 * @brief Sampling based splitting for parallel multiway-merge routine. 01094 */ 01095 template< 01096 bool stable 01097 , typename RandomAccessIteratorIterator 01098 , typename Comparator 01099 , typename difference_type> 01100 void multiway_merge_sampling_splitting( 01101 RandomAccessIteratorIterator seqs_begin, 01102 RandomAccessIteratorIterator seqs_end, 01103 difference_type length, difference_type total_length, Comparator comp, 01104 std::vector<std::pair<difference_type, difference_type> > *pieces) 01105 { 01106 typedef typename std::iterator_traits<RandomAccessIteratorIterator> 01107 ::value_type::first_type 01108 RandomAccessIterator1; 01109 typedef typename std::iterator_traits<RandomAccessIterator1>::value_type 01110 value_type; 01111 01112 // k sequences. 01113 int k = static_cast<int>(seqs_end - seqs_begin); 01114 01115 int num_threads = omp_get_num_threads(); 01116 01117 difference_type num_samples = 01118 __gnu_parallel::_Settings::get().merge_oversampling * num_threads; 01119 01120 value_type* samples = static_cast<value_type*>( 01121 ::operator new(sizeof(value_type) * k * num_samples)); 01122 // Sample. 01123 for (int s = 0; s < k; ++s) 01124 for (difference_type i = 0; i < num_samples; ++i) 01125 { 01126 difference_type sample_index = 01127 static_cast<difference_type>( 01128 _GLIBCXX_PARALLEL_LENGTH(seqs_begin[s]) 01129 * (double(i + 1) / (num_samples + 1)) 01130 * (double(length) / total_length)); 01131 new(&(samples[s * num_samples + i])) 01132 value_type(seqs_begin[s].first[sample_index]); 01133 } 01134 01135 // Sort stable or non-stable, depending on value of template parameter 01136 // "stable". 01137 sampling_sorter<stable, value_type*, Comparator>()( 01138 samples, samples + (num_samples * k), comp); 01139 01140 for (int slab = 0; slab < num_threads; ++slab) 01141 // For each slab / processor. 01142 for (int seq = 0; seq < k; ++seq) 01143 { 01144 // For each sequence. 01145 if (slab > 0) 01146 pieces[slab][seq].first = 01147 std::upper_bound( 01148 seqs_begin[seq].first, 01149 seqs_begin[seq].second, 01150 samples[num_samples * k * slab / num_threads], 01151 comp) 01152 - seqs_begin[seq].first; 01153 else 01154 // Absolute beginning. 01155 pieces[slab][seq].first = 0; 01156 if ((slab + 1) < num_threads) 01157 pieces[slab][seq].second = 01158 std::upper_bound( 01159 seqs_begin[seq].first, 01160 seqs_begin[seq].second, 01161 samples[num_samples * k * (slab + 1) / 01162 num_threads], comp) 01163 - seqs_begin[seq].first; 01164 else 01165 // Absolute end. 01166 pieces[slab][seq].second = _GLIBCXX_PARALLEL_LENGTH(seqs_begin[seq]); 01167 } 01168 ::operator delete(samples); 01169 } 01170 01171 /** 01172 * @brief Exact splitting for parallel multiway-merge routine. 01173 * 01174 * None of the passed sequences may be empty. 01175 */ 01176 template< 01177 bool stable 01178 , typename RandomAccessIteratorIterator 01179 , typename Comparator 01180 , typename difference_type> 01181 void multiway_merge_exact_splitting( 01182 RandomAccessIteratorIterator seqs_begin, 01183 RandomAccessIteratorIterator seqs_end, 01184 difference_type length, difference_type total_length, Comparator comp, 01185 std::vector<std::pair<difference_type, difference_type> > *pieces) 01186 { 01187 typedef typename std::iterator_traits<RandomAccessIteratorIterator> 01188 ::value_type::first_type 01189 RandomAccessIterator1; 01190 01191 const bool tight = (total_length == length); 01192 01193 // k sequences. 01194 const int k = static_cast<int>(seqs_end - seqs_begin); 01195 01196 const int num_threads = omp_get_num_threads(); 01197 01198 // (Settings::multiway_merge_splitting == __gnu_parallel::_Settings::EXACT). 01199 std::vector<RandomAccessIterator1>* offsets = 01200 new std::vector<RandomAccessIterator1>[num_threads]; 01201 std::vector< 01202 std::pair<RandomAccessIterator1, RandomAccessIterator1> 01203 > se(k); 01204 01205 copy(seqs_begin, seqs_end, se.begin()); 01206 01207 difference_type* borders = 01208 new difference_type[num_threads + 1]; 01209 equally_split(length, num_threads, borders); 01210 01211 for (int s = 0; s < (num_threads - 1); ++s) 01212 { 01213 offsets[s].resize(k); 01214 multiseq_partition( 01215 se.begin(), se.end(), borders[s + 1], 01216 offsets[s].begin(), comp); 01217 01218 // Last one also needed and available. 01219 if (!tight) 01220 { 01221 offsets[num_threads - 1].resize(k); 01222 multiseq_partition(se.begin(), se.end(), 01223 difference_type(length), 01224 offsets[num_threads - 1].begin(), comp); 01225 } 01226 } 01227 delete[] borders; 01228 01229 for (int slab = 0; slab < num_threads; ++slab) 01230 { 01231 // For each slab / processor. 01232 for (int seq = 0; seq < k; ++seq) 01233 { 01234 // For each sequence. 01235 if (slab == 0) 01236 { 01237 // Absolute beginning. 01238 pieces[slab][seq].first = 0; 01239 } 01240 else 01241 pieces[slab][seq].first = 01242 pieces[slab - 1][seq].second; 01243 if (!tight || slab < (num_threads - 1)) 01244 pieces[slab][seq].second = 01245 offsets[slab][seq] - seqs_begin[seq].first; 01246 else 01247 { 01248 // slab == num_threads - 1 01249 pieces[slab][seq].second = 01250 _GLIBCXX_PARALLEL_LENGTH(seqs_begin[seq]); 01251 } 01252 } 01253 } 01254 delete[] offsets; 01255 } 01256 01257 /** @brief Parallel multi-way merge routine. 01258 * 01259 * The _GLIBCXX_PARALLEL_DECISION is based on the branching factor 01260 * and runtime settings. 01261 * 01262 * Must not be called if the number of sequences is 1. 01263 * 01264 * @param Splitter functor to split input (either exact or sampling based) 01265 * 01266 * @param seqs_begin Begin iterator of iterator pair input sequence. 01267 * @param seqs_end End iterator of iterator pair input sequence. 01268 * @param target Begin iterator out output sequence. 01269 * @param comp Comparator. 01270 * @param length Maximum length to merge, possibly larger than the 01271 * number of elements available. 01272 * @param stable Stable merging incurs a performance penalty. 01273 * @param sentinel Ignored. 01274 * @return End iterator of output sequence. 01275 */ 01276 template< 01277 bool stable, 01278 bool sentinels, 01279 typename RandomAccessIteratorIterator, 01280 typename RandomAccessIterator3, 01281 typename _DifferenceTp, 01282 typename Splitter, 01283 typename Comparator 01284 > 01285 RandomAccessIterator3 01286 parallel_multiway_merge(RandomAccessIteratorIterator seqs_begin, 01287 RandomAccessIteratorIterator seqs_end, 01288 RandomAccessIterator3 target, 01289 Splitter splitter, 01290 _DifferenceTp length, 01291 Comparator comp, 01292 thread_index_t num_threads) 01293 { 01294 #if _GLIBCXX_ASSERTIONS 01295 _GLIBCXX_PARALLEL_ASSERT(seqs_end - seqs_begin > 1); 01296 #endif 01297 01298 _GLIBCXX_CALL(length) 01299 01300 typedef _DifferenceTp difference_type; 01301 typedef typename std::iterator_traits<RandomAccessIteratorIterator> 01302 ::value_type::first_type 01303 RandomAccessIterator1; 01304 typedef typename 01305 std::iterator_traits<RandomAccessIterator1>::value_type value_type; 01306 01307 // Leave only non-empty sequences. 01308 typedef std::pair<RandomAccessIterator1, RandomAccessIterator1> seq_type; 01309 seq_type* ne_seqs = new seq_type[seqs_end - seqs_begin]; 01310 int k = 0; 01311 difference_type total_length = 0; 01312 for (RandomAccessIteratorIterator raii = seqs_begin; 01313 raii != seqs_end; ++raii) 01314 { 01315 _DifferenceTp seq_length = _GLIBCXX_PARALLEL_LENGTH(*raii); 01316 if(seq_length > 0) 01317 { 01318 total_length += seq_length; 01319 ne_seqs[k++] = *raii; 01320 } 01321 } 01322 01323 _GLIBCXX_CALL(total_length) 01324 01325 length = std::min<_DifferenceTp>(length, total_length); 01326 01327 if (total_length == 0 || k == 0) 01328 { 01329 delete[] ne_seqs; 01330 return target; 01331 } 01332 01333 std::vector<std::pair<difference_type, difference_type> >* pieces; 01334 01335 num_threads = static_cast<thread_index_t> 01336 (std::min<difference_type>(num_threads, total_length)); 01337 01338 # pragma omp parallel num_threads (num_threads) 01339 { 01340 # pragma omp single 01341 { 01342 num_threads = omp_get_num_threads(); 01343 // Thread t will have to merge pieces[iam][0..k - 1] 01344 pieces = new std::vector< 01345 std::pair<difference_type, difference_type> >[num_threads]; 01346 for (int s = 0; s < num_threads; ++s) 01347 pieces[s].resize(k); 01348 01349 difference_type num_samples = 01350 __gnu_parallel::_Settings::get().merge_oversampling * 01351 num_threads; 01352 01353 splitter(ne_seqs, ne_seqs + k, length, total_length, 01354 comp, pieces); 01355 } //single 01356 01357 thread_index_t iam = omp_get_thread_num(); 01358 01359 difference_type target_position = 0; 01360 01361 for (int c = 0; c < k; ++c) 01362 target_position += pieces[iam][c].first; 01363 01364 seq_type* chunks = new seq_type[k]; 01365 01366 for (int s = 0; s < k; ++s) 01367 { 01368 chunks[s] = std::make_pair( 01369 ne_seqs[s].first + pieces[iam][s].first, 01370 ne_seqs[s].first + pieces[iam][s].second); 01371 } 01372 01373 if(length > target_position) 01374 sequential_multiway_merge<stable, sentinels>( 01375 chunks, chunks + k, target + target_position, 01376 *(seqs_begin->second), length - target_position, comp); 01377 01378 delete[] chunks; 01379 } // parallel 01380 01381 #if _GLIBCXX_ASSERTIONS 01382 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target, target + length, comp)); 01383 #endif 01384 01385 k = 0; 01386 // Update ends of sequences. 01387 for (RandomAccessIteratorIterator raii = seqs_begin; 01388 raii != seqs_end; ++raii) 01389 { 01390 _DifferenceTp length = _GLIBCXX_PARALLEL_LENGTH(*raii); 01391 if(length > 0) 01392 (*raii).first += pieces[num_threads - 1][k++].second; 01393 } 01394 01395 delete[] pieces; 01396 delete[] ne_seqs; 01397 01398 return target + length; 01399 } 01400 01401 /** 01402 * @brief Multiway Merge Frontend. 01403 * 01404 * Merge the sequences specified by seqs_begin and seqs_end into 01405 * target. seqs_begin and seqs_end must point to a sequence of 01406 * pairs. These pairs must contain an iterator to the beginning 01407 * of a sequence in their first entry and an iterator the end of 01408 * the same sequence in their second entry. 01409 * 01410 * Ties are broken arbitrarily. See stable_multiway_merge for a variant 01411 * that breaks ties by sequence number but is slower. 01412 * 01413 * The first entries of the pairs (i.e. the begin iterators) will be moved 01414 * forward. 01415 * 01416 * The output sequence has to provide enough space for all elements 01417 * that are written to it. 01418 * 01419 * This function will merge the input sequences: 01420 * 01421 * - not stable 01422 * - parallel, depending on the input size and Settings 01423 * - using sampling for splitting 01424 * - not using sentinels 01425 * 01426 * Example: 01427 * 01428 * <pre> 01429 * int sequences[10][10]; 01430 * for (int i = 0; i < 10; ++i) 01431 * for (int j = 0; i < 10; ++j) 01432 * sequences[i][j] = j; 01433 * 01434 * int out[33]; 01435 * std::vector<std::pair<int*> > seqs; 01436 * for (int i = 0; i < 10; ++i) 01437 * { seqs.push(std::make_pair<int*>(sequences[i], sequences[i] + 10)) } 01438 * 01439 * multiway_merge(seqs.begin(), seqs.end(), target, std::less<int>(), 33); 01440 * </pre> 01441 * 01442 * @see stable_multiway_merge 01443 * 01444 * @pre All input sequences must be sorted. 01445 * @pre Target must provide enough space to merge out length elements or 01446 * the number of elements in all sequences, whichever is smaller. 01447 * 01448 * @post [target, return value) contains merged elements from the 01449 * input sequences. 01450 * @post return value - target = min(length, number of elements in all 01451 * sequences). 01452 * 01453 * @param RandomAccessIteratorPairIterator iterator over sequence 01454 * of pairs of iterators 01455 * @param RandomAccessIteratorOut iterator over target sequence 01456 * @param _DifferenceTp difference type for the sequence 01457 * @param Comparator strict weak ordering type to compare elements 01458 * in sequences 01459 * 01460 * @param seqs_begin begin of sequence sequence 01461 * @param seqs_end end of sequence sequence 01462 * @param target target sequence to merge to. 01463 * @param comp strict weak ordering to use for element comparison. 01464 * @param length Maximum length to merge, possibly larger than the 01465 * number of elements available. 01466 * 01467 * @return end iterator of output sequence 01468 */ 01469 // multiway_merge 01470 // public interface 01471 template< 01472 typename RandomAccessIteratorPairIterator 01473 , typename RandomAccessIteratorOut 01474 , typename _DifferenceTp 01475 , typename Comparator> 01476 RandomAccessIteratorOut 01477 multiway_merge(RandomAccessIteratorPairIterator seqs_begin 01478 , RandomAccessIteratorPairIterator seqs_end 01479 , RandomAccessIteratorOut target 01480 , _DifferenceTp length, Comparator comp 01481 , __gnu_parallel::sequential_tag) 01482 { 01483 typedef _DifferenceTp difference_type; 01484 _GLIBCXX_CALL(seqs_end - seqs_begin) 01485 01486 // catch special case: no sequences 01487 if (seqs_begin == seqs_end) 01488 return target; 01489 01490 // Execute multiway merge *sequentially*. 01491 return sequential_multiway_merge 01492 </* stable = */ false, /* sentinels = */ false> 01493 (seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp); 01494 } 01495 01496 // public interface 01497 template< 01498 typename RandomAccessIteratorPairIterator 01499 , typename RandomAccessIteratorOut 01500 , typename _DifferenceTp 01501 , typename Comparator> 01502 RandomAccessIteratorOut 01503 multiway_merge(RandomAccessIteratorPairIterator seqs_begin 01504 , RandomAccessIteratorPairIterator seqs_end 01505 , RandomAccessIteratorOut target 01506 , _DifferenceTp length, Comparator comp 01507 , __gnu_parallel::exact_tag tag) 01508 { 01509 typedef _DifferenceTp difference_type; 01510 _GLIBCXX_CALL(seqs_end - seqs_begin) 01511 01512 // catch special case: no sequences 01513 if (seqs_begin == seqs_end) 01514 return target; 01515 01516 // Execute merge; maybe parallel, depending on the number of merged 01517 // elements and the number of sequences and global thresholds in 01518 // Settings. 01519 if ((seqs_end - seqs_begin > 1) && 01520 _GLIBCXX_PARALLEL_CONDITION( 01521 ((seqs_end - seqs_begin) >= 01522 __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 01523 && ((sequence_index_t)length >= 01524 __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 01525 return parallel_multiway_merge 01526 </* stable = */ false, /* sentinels = */ false>( 01527 seqs_begin, seqs_end, target, 01528 multiway_merge_exact_splitting</* stable = */ false, 01529 typename std::iterator_traits<RandomAccessIteratorPairIterator> 01530 ::value_type*, Comparator, _DifferenceTp>, 01531 static_cast<difference_type>(length), comp, tag.get_num_threads()); 01532 else 01533 return sequential_multiway_merge 01534 </* stable = */ false, /* sentinels = */ false>( 01535 seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp); 01536 } 01537 01538 // public interface 01539 template< 01540 typename RandomAccessIteratorPairIterator 01541 , typename RandomAccessIteratorOut 01542 , typename _DifferenceTp 01543 , typename Comparator> 01544 RandomAccessIteratorOut 01545 multiway_merge(RandomAccessIteratorPairIterator seqs_begin 01546 , RandomAccessIteratorPairIterator seqs_end 01547 , RandomAccessIteratorOut target 01548 , _DifferenceTp length, Comparator comp 01549 , __gnu_parallel::sampling_tag tag) 01550 { 01551 typedef _DifferenceTp difference_type; 01552 _GLIBCXX_CALL(seqs_end - seqs_begin) 01553 01554 // catch special case: no sequences 01555 if (seqs_begin == seqs_end) 01556 return target; 01557 01558 // Execute merge; maybe parallel, depending on the number of merged 01559 // elements and the number of sequences and global thresholds in 01560 // Settings. 01561 if ((seqs_end - seqs_begin > 1) && 01562 _GLIBCXX_PARALLEL_CONDITION( 01563 ((seqs_end - seqs_begin) >= 01564 __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 01565 && ((sequence_index_t)length >= 01566 __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 01567 return parallel_multiway_merge 01568 </* stable = */ false, /* sentinels = */ false>( 01569 seqs_begin, seqs_end, 01570 target, 01571 multiway_merge_exact_splitting</* stable = */ false, 01572 typename std::iterator_traits<RandomAccessIteratorPairIterator> 01573 ::value_type*, Comparator, _DifferenceTp>, 01574 static_cast<difference_type>(length), comp, tag.get_num_threads()); 01575 else 01576 return sequential_multiway_merge 01577 </* stable = */ false, /* sentinels = */ false>( 01578 seqs_begin, seqs_end, 01579 target, *(seqs_begin->second), length, comp); 01580 } 01581 01582 // public interface 01583 template< 01584 typename RandomAccessIteratorPairIterator 01585 , typename RandomAccessIteratorOut 01586 , typename _DifferenceTp 01587 , typename Comparator> 01588 RandomAccessIteratorOut 01589 multiway_merge(RandomAccessIteratorPairIterator seqs_begin 01590 , RandomAccessIteratorPairIterator seqs_end 01591 , RandomAccessIteratorOut target 01592 , _DifferenceTp length, Comparator comp 01593 , parallel_tag tag = parallel_tag(0)) 01594 { 01595 return multiway_merge(seqs_begin, seqs_end, target, length, comp, 01596 exact_tag(tag.get_num_threads())); 01597 } 01598 01599 // public interface 01600 template< 01601 typename RandomAccessIteratorPairIterator 01602 , typename RandomAccessIteratorOut 01603 , typename _DifferenceTp 01604 , typename Comparator> 01605 RandomAccessIteratorOut 01606 multiway_merge(RandomAccessIteratorPairIterator seqs_begin 01607 , RandomAccessIteratorPairIterator seqs_end 01608 , RandomAccessIteratorOut target 01609 , _DifferenceTp length, Comparator comp 01610 , default_parallel_tag tag) 01611 { 01612 return multiway_merge(seqs_begin, seqs_end, target, length, comp, 01613 exact_tag(tag.get_num_threads())); 01614 } 01615 01616 // stable_multiway_merge 01617 // public interface 01618 template< 01619 typename RandomAccessIteratorPairIterator 01620 , typename RandomAccessIteratorOut 01621 , typename _DifferenceTp 01622 , typename Comparator> 01623 RandomAccessIteratorOut 01624 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin 01625 , RandomAccessIteratorPairIterator seqs_end 01626 , RandomAccessIteratorOut target 01627 , _DifferenceTp length, Comparator comp 01628 , __gnu_parallel::sequential_tag) 01629 { 01630 typedef _DifferenceTp difference_type; 01631 _GLIBCXX_CALL(seqs_end - seqs_begin) 01632 01633 // catch special case: no sequences 01634 if (seqs_begin == seqs_end) 01635 return target; 01636 01637 // Execute multiway merge *sequentially*. 01638 return sequential_multiway_merge 01639 </* stable = */ true, /* sentinels = */ false> 01640 (seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp); 01641 } 01642 01643 // public interface 01644 template< 01645 typename RandomAccessIteratorPairIterator 01646 , typename RandomAccessIteratorOut 01647 , typename _DifferenceTp 01648 , typename Comparator> 01649 RandomAccessIteratorOut 01650 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin 01651 , RandomAccessIteratorPairIterator seqs_end 01652 , RandomAccessIteratorOut target 01653 , _DifferenceTp length, Comparator comp 01654 , __gnu_parallel::exact_tag tag) 01655 { 01656 typedef _DifferenceTp difference_type; 01657 _GLIBCXX_CALL(seqs_end - seqs_begin) 01658 01659 // catch special case: no sequences 01660 if (seqs_begin == seqs_end) 01661 return target; 01662 01663 // Execute merge; maybe parallel, depending on the number of merged 01664 // elements and the number of sequences and global thresholds in 01665 // Settings. 01666 if ((seqs_end - seqs_begin > 1) && 01667 _GLIBCXX_PARALLEL_CONDITION( 01668 ((seqs_end - seqs_begin) >= 01669 __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 01670 && ((sequence_index_t)length >= 01671 __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 01672 return parallel_multiway_merge 01673 </* stable = */ true, /* sentinels = */ false>( 01674 seqs_begin, seqs_end, 01675 target, 01676 multiway_merge_exact_splitting</* stable = */ true, 01677 typename std::iterator_traits<RandomAccessIteratorPairIterator> 01678 ::value_type*, Comparator, _DifferenceTp>, 01679 static_cast<difference_type>(length), comp, tag.get_num_threads()); 01680 else 01681 return sequential_multiway_merge</* stable = */ true, 01682 /* sentinels = */ false>( 01683 seqs_begin, seqs_end, 01684 target, *(seqs_begin->second), length, comp); 01685 } 01686 01687 // public interface 01688 template< 01689 typename RandomAccessIteratorPairIterator 01690 , typename RandomAccessIteratorOut 01691 , typename _DifferenceTp 01692 , typename Comparator> 01693 RandomAccessIteratorOut 01694 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin 01695 , RandomAccessIteratorPairIterator seqs_end 01696 , RandomAccessIteratorOut target 01697 , _DifferenceTp length, Comparator comp 01698 , sampling_tag tag) 01699 { 01700 typedef _DifferenceTp difference_type; 01701 _GLIBCXX_CALL(seqs_end - seqs_begin) 01702 01703 // catch special case: no sequences 01704 if (seqs_begin == seqs_end) 01705 return target; 01706 01707 // Execute merge; maybe parallel, depending on the number of merged 01708 // elements and the number of sequences and global thresholds in 01709 // Settings. 01710 if ((seqs_end - seqs_begin > 1) && 01711 _GLIBCXX_PARALLEL_CONDITION( 01712 ((seqs_end - seqs_begin) >= 01713 __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 01714 && ((sequence_index_t)length >= 01715 __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 01716 return parallel_multiway_merge 01717 </* stable = */ true, /* sentinels = */ false>( 01718 seqs_begin, seqs_end, 01719 target, 01720 multiway_merge_sampling_splitting</* stable = */ true, 01721 typename std::iterator_traits<RandomAccessIteratorPairIterator> 01722 ::value_type*, Comparator, _DifferenceTp>, 01723 static_cast<difference_type>(length), comp, tag.get_num_threads()); 01724 else 01725 return sequential_multiway_merge 01726 </* stable = */ true, /* sentinels = */ false>( 01727 seqs_begin, seqs_end, 01728 target, *(seqs_begin->second), length, comp); 01729 } 01730 01731 01732 // public interface 01733 template< 01734 typename RandomAccessIteratorPairIterator 01735 , typename RandomAccessIteratorOut 01736 , typename _DifferenceTp 01737 , typename Comparator> 01738 RandomAccessIteratorOut 01739 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin 01740 , RandomAccessIteratorPairIterator seqs_end 01741 , RandomAccessIteratorOut target 01742 , _DifferenceTp length, Comparator comp 01743 , parallel_tag tag = parallel_tag(0)) 01744 { 01745 return stable_multiway_merge(seqs_begin, seqs_end, target, length, comp, 01746 exact_tag(tag.get_num_threads())); 01747 } 01748 01749 // public interface 01750 template< 01751 typename RandomAccessIteratorPairIterator 01752 , typename RandomAccessIteratorOut 01753 , typename _DifferenceTp 01754 , typename Comparator> 01755 RandomAccessIteratorOut 01756 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin 01757 , RandomAccessIteratorPairIterator seqs_end 01758 , RandomAccessIteratorOut target 01759 , _DifferenceTp length, Comparator comp 01760 , default_parallel_tag tag) 01761 { 01762 return stable_multiway_merge(seqs_begin, seqs_end, target, length, comp, 01763 exact_tag(tag.get_num_threads())); 01764 } 01765 01766 /** 01767 * @brief Multiway Merge Frontend. 01768 * 01769 * Merge the sequences specified by seqs_begin and seqs_end into 01770 * target. seqs_begin and seqs_end must point to a sequence of 01771 * pairs. These pairs must contain an iterator to the beginning 01772 * of a sequence in their first entry and an iterator the end of 01773 * the same sequence in their second entry. 01774 * 01775 * Ties are broken arbitrarily. See stable_multiway_merge for a variant 01776 * that breaks ties by sequence number but is slower. 01777 * 01778 * The first entries of the pairs (i.e. the begin iterators) will be moved 01779 * forward accordingly. 01780 * 01781 * The output sequence has to provide enough space for all elements 01782 * that are written to it. 01783 * 01784 * This function will merge the input sequences: 01785 * 01786 * - not stable 01787 * - parallel, depending on the input size and Settings 01788 * - using sampling for splitting 01789 * - using sentinels 01790 * 01791 * You have to take care that the element the end iterator points to is 01792 * readable and contains a value that is greater than any other non-sentinel 01793 * value in all sequences. 01794 * 01795 * Example: 01796 * 01797 * <pre> 01798 * int sequences[10][11]; 01799 * for (int i = 0; i < 10; ++i) 01800 * for (int j = 0; i < 11; ++j) 01801 * sequences[i][j] = j; // last one is sentinel! 01802 * 01803 * int out[33]; 01804 * std::vector<std::pair<int*> > seqs; 01805 * for (int i = 0; i < 10; ++i) 01806 * { seqs.push(std::make_pair<int*>(sequences[i], sequences[i] + 10)) } 01807 * 01808 * multiway_merge(seqs.begin(), seqs.end(), target, std::less<int>(), 33); 01809 * </pre> 01810 * 01811 * @pre All input sequences must be sorted. 01812 * @pre Target must provide enough space to merge out length elements or 01813 * the number of elements in all sequences, whichever is smaller. 01814 * @pre For each @c i, @c seqs_begin[i].second must be the end 01815 * marker of the sequence, but also reference the one more sentinel 01816 * element. 01817 * 01818 * @post [target, return value) contains merged elements from the 01819 * input sequences. 01820 * @post return value - target = min(length, number of elements in all 01821 * sequences). 01822 * 01823 * @see stable_multiway_merge_sentinels 01824 * 01825 * @param RandomAccessIteratorPairIterator iterator over sequence 01826 * of pairs of iterators 01827 * @param RandomAccessIteratorOut iterator over target sequence 01828 * @param _DifferenceTp difference type for the sequence 01829 * @param Comparator strict weak ordering type to compare elements 01830 * in sequences 01831 * 01832 * @param seqs_begin begin of sequence sequence 01833 * @param seqs_end end of sequence sequence 01834 * @param target target sequence to merge to. 01835 * @param comp strict weak ordering to use for element comparison. 01836 * @param length Maximum length to merge, possibly larger than the 01837 * number of elements available. 01838 * 01839 * @return end iterator of output sequence 01840 */ 01841 // multiway_merge_sentinels 01842 // public interface 01843 template< 01844 typename RandomAccessIteratorPairIterator 01845 , typename RandomAccessIteratorOut 01846 , typename _DifferenceTp 01847 , typename Comparator> 01848 RandomAccessIteratorOut 01849 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin 01850 , RandomAccessIteratorPairIterator seqs_end 01851 , RandomAccessIteratorOut target 01852 , _DifferenceTp length, Comparator comp 01853 , __gnu_parallel::sequential_tag) 01854 { 01855 typedef _DifferenceTp difference_type; 01856 _GLIBCXX_CALL(seqs_end - seqs_begin) 01857 01858 // catch special case: no sequences 01859 if (seqs_begin == seqs_end) 01860 return target; 01861 01862 // Execute multiway merge *sequentially*. 01863 return sequential_multiway_merge 01864 </* stable = */ false, /* sentinels = */ true> 01865 (seqs_begin, seqs_end, 01866 target, *(seqs_begin->second), length, comp); 01867 } 01868 01869 // public interface 01870 template< 01871 typename RandomAccessIteratorPairIterator 01872 , typename RandomAccessIteratorOut 01873 , typename _DifferenceTp 01874 , typename Comparator> 01875 RandomAccessIteratorOut 01876 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin 01877 , RandomAccessIteratorPairIterator seqs_end 01878 , RandomAccessIteratorOut target 01879 , _DifferenceTp length, Comparator comp 01880 , __gnu_parallel::exact_tag tag) 01881 { 01882 typedef _DifferenceTp difference_type; 01883 _GLIBCXX_CALL(seqs_end - seqs_begin) 01884 01885 // catch special case: no sequences 01886 if (seqs_begin == seqs_end) 01887 return target; 01888 01889 // Execute merge; maybe parallel, depending on the number of merged 01890 // elements and the number of sequences and global thresholds in 01891 // Settings. 01892 if ((seqs_end - seqs_begin > 1) && 01893 _GLIBCXX_PARALLEL_CONDITION( 01894 ((seqs_end - seqs_begin) >= 01895 __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 01896 && ((sequence_index_t)length >= 01897 __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 01898 return parallel_multiway_merge 01899 </* stable = */ false, /* sentinels = */ true>( 01900 seqs_begin, seqs_end, 01901 target, 01902 multiway_merge_exact_splitting</* stable = */ false, 01903 typename std::iterator_traits<RandomAccessIteratorPairIterator> 01904 ::value_type*, Comparator, _DifferenceTp>, 01905 static_cast<difference_type>(length), comp, tag.get_num_threads()); 01906 else 01907 return sequential_multiway_merge 01908 </* stable = */ false, /* sentinels = */ true>( 01909 seqs_begin, seqs_end, 01910 target, *(seqs_begin->second), length, comp); 01911 } 01912 01913 // public interface 01914 template< 01915 typename RandomAccessIteratorPairIterator 01916 , typename RandomAccessIteratorOut 01917 , typename _DifferenceTp 01918 , typename Comparator> 01919 RandomAccessIteratorOut 01920 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin 01921 , RandomAccessIteratorPairIterator seqs_end 01922 , RandomAccessIteratorOut target 01923 , _DifferenceTp length, Comparator comp 01924 , sampling_tag tag) 01925 { 01926 typedef _DifferenceTp difference_type; 01927 _GLIBCXX_CALL(seqs_end - seqs_begin) 01928 01929 // catch special case: no sequences 01930 if (seqs_begin == seqs_end) 01931 return target; 01932 01933 // Execute merge; maybe parallel, depending on the number of merged 01934 // elements and the number of sequences and global thresholds in 01935 // Settings. 01936 if ((seqs_end - seqs_begin > 1) && 01937 _GLIBCXX_PARALLEL_CONDITION( 01938 ((seqs_end - seqs_begin) >= 01939 __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 01940 && ((sequence_index_t)length >= 01941 __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 01942 return parallel_multiway_merge 01943 </* stable = */ false, /* sentinels = */ true> 01944 (seqs_begin, seqs_end, target, 01945 multiway_merge_sampling_splitting</* stable = */ false, 01946 typename std::iterator_traits<RandomAccessIteratorPairIterator> 01947 ::value_type*, Comparator, _DifferenceTp>, 01948 static_cast<difference_type>(length), comp, tag.get_num_threads()); 01949 else 01950 return sequential_multiway_merge 01951 </* stable = */false, /* sentinels = */ true>( 01952 seqs_begin, seqs_end, 01953 target, *(seqs_begin->second), length, comp); 01954 } 01955 01956 // public interface 01957 template< 01958 typename RandomAccessIteratorPairIterator 01959 , typename RandomAccessIteratorOut 01960 , typename _DifferenceTp 01961 , typename Comparator> 01962 RandomAccessIteratorOut 01963 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin 01964 , RandomAccessIteratorPairIterator seqs_end 01965 , RandomAccessIteratorOut target 01966 , _DifferenceTp length, Comparator comp 01967 , parallel_tag tag = parallel_tag(0)) 01968 { 01969 return multiway_merge_sentinels(seqs_begin, seqs_end, target, length, comp, 01970 exact_tag(tag.get_num_threads())); 01971 } 01972 01973 // public interface 01974 template< 01975 typename RandomAccessIteratorPairIterator 01976 , typename RandomAccessIteratorOut 01977 , typename _DifferenceTp 01978 , typename Comparator> 01979 RandomAccessIteratorOut 01980 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin 01981 , RandomAccessIteratorPairIterator seqs_end 01982 , RandomAccessIteratorOut target 01983 , _DifferenceTp length, Comparator comp 01984 , default_parallel_tag tag) 01985 { 01986 return multiway_merge_sentinels(seqs_begin, seqs_end, target, length, comp, 01987 exact_tag(tag.get_num_threads())); 01988 } 01989 01990 // stable_multiway_merge_sentinels 01991 // public interface 01992 template< 01993 typename RandomAccessIteratorPairIterator 01994 , typename RandomAccessIteratorOut 01995 , typename _DifferenceTp 01996 , typename Comparator> 01997 RandomAccessIteratorOut 01998 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin 01999 , RandomAccessIteratorPairIterator seqs_end 02000 , RandomAccessIteratorOut target 02001 , _DifferenceTp length, Comparator comp 02002 , __gnu_parallel::sequential_tag) 02003 { 02004 typedef _DifferenceTp difference_type; 02005 _GLIBCXX_CALL(seqs_end - seqs_begin) 02006 02007 // catch special case: no sequences 02008 if (seqs_begin == seqs_end) 02009 return target; 02010 02011 // Execute multiway merge *sequentially*. 02012 return sequential_multiway_merge 02013 </* stable = */ true, /* sentinels = */ true> 02014 (seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp); 02015 } 02016 02017 // public interface 02018 template< 02019 typename RandomAccessIteratorPairIterator 02020 , typename RandomAccessIteratorOut 02021 , typename _DifferenceTp 02022 , typename Comparator> 02023 RandomAccessIteratorOut 02024 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin 02025 , RandomAccessIteratorPairIterator seqs_end 02026 , RandomAccessIteratorOut target 02027 , _DifferenceTp length, Comparator comp 02028 , __gnu_parallel::exact_tag tag) 02029 { 02030 typedef _DifferenceTp difference_type; 02031 _GLIBCXX_CALL(seqs_end - seqs_begin) 02032 02033 // catch special case: no sequences 02034 if (seqs_begin == seqs_end) 02035 return target; 02036 02037 // Execute merge; maybe parallel, depending on the number of merged 02038 // elements and the number of sequences and global thresholds in 02039 // Settings. 02040 if ((seqs_end - seqs_begin > 1) && 02041 _GLIBCXX_PARALLEL_CONDITION( 02042 ((seqs_end - seqs_begin) >= 02043 __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 02044 && ((sequence_index_t)length >= 02045 __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 02046 return parallel_multiway_merge 02047 </* stable = */ true, /* sentinels = */ true>( 02048 seqs_begin, seqs_end, 02049 target, 02050 multiway_merge_exact_splitting</* stable = */ true, 02051 typename std::iterator_traits<RandomAccessIteratorPairIterator> 02052 ::value_type*, Comparator, _DifferenceTp>, 02053 static_cast<difference_type>(length), comp, tag.get_num_threads()); 02054 else 02055 return sequential_multiway_merge 02056 </* stable = */ true, /* sentinels = */ true>( 02057 seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp); 02058 } 02059 02060 // public interface 02061 template< 02062 typename RandomAccessIteratorPairIterator 02063 , typename RandomAccessIteratorOut 02064 , typename _DifferenceTp 02065 , typename Comparator> 02066 RandomAccessIteratorOut 02067 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin 02068 , RandomAccessIteratorPairIterator seqs_end 02069 , RandomAccessIteratorOut target 02070 , _DifferenceTp length, Comparator comp 02071 , sampling_tag tag) 02072 { 02073 typedef _DifferenceTp difference_type; 02074 _GLIBCXX_CALL(seqs_end - seqs_begin) 02075 02076 // catch special case: no sequences 02077 if (seqs_begin == seqs_end) 02078 return target; 02079 02080 // Execute merge; maybe parallel, depending on the number of merged 02081 // elements and the number of sequences and global thresholds in 02082 // Settings. 02083 if ((seqs_end - seqs_begin > 1) && 02084 _GLIBCXX_PARALLEL_CONDITION( 02085 ((seqs_end - seqs_begin) >= 02086 __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 02087 && ((sequence_index_t)length >= 02088 __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 02089 return parallel_multiway_merge 02090 </* stable = */ true, /* sentinels = */ true>( 02091 seqs_begin, seqs_end, 02092 target, 02093 multiway_merge_sampling_splitting</* stable = */ true, 02094 typename std::iterator_traits<RandomAccessIteratorPairIterator> 02095 ::value_type*, Comparator, _DifferenceTp>, 02096 static_cast<difference_type>(length), comp, tag.get_num_threads()); 02097 else 02098 return sequential_multiway_merge 02099 </* stable = */ true, /* sentinels = */ true>( 02100 seqs_begin, seqs_end, 02101 target, *(seqs_begin->second), length, comp); 02102 } 02103 02104 // public interface 02105 template< 02106 typename RandomAccessIteratorPairIterator 02107 , typename RandomAccessIteratorOut 02108 , typename _DifferenceTp 02109 , typename Comparator> 02110 RandomAccessIteratorOut 02111 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin 02112 , RandomAccessIteratorPairIterator seqs_end 02113 , RandomAccessIteratorOut target 02114 , _DifferenceTp length, Comparator comp 02115 , parallel_tag tag = parallel_tag(0)) 02116 { 02117 return stable_multiway_merge_sentinels(seqs_begin, seqs_end, target, length, comp, 02118 exact_tag(tag.get_num_threads())); 02119 } 02120 02121 // public interface 02122 template< 02123 typename RandomAccessIteratorPairIterator 02124 , typename RandomAccessIteratorOut 02125 , typename _DifferenceTp 02126 , typename Comparator> 02127 RandomAccessIteratorOut 02128 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin 02129 , RandomAccessIteratorPairIterator seqs_end 02130 , RandomAccessIteratorOut target 02131 , _DifferenceTp length, Comparator comp 02132 , default_parallel_tag tag) 02133 { 02134 return stable_multiway_merge_sentinels(seqs_begin, seqs_end, target, length, comp, 02135 exact_tag(tag.get_num_threads())); 02136 } 02137 02138 }; // namespace __gnu_parallel 02139 02140 #endif /* _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H */