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