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 _SeqNumber __k = static_cast<_SeqNumber>(__seqs_end - __seqs_begin); 01049 01050 _ThreadIndex __num_threads = omp_get_num_threads(); 01051 01052 _DifferenceType __num_samples = 01053 __gnu_parallel::_Settings::get().merge_oversampling * __num_threads; 01054 01055 _ValueType* __samples = static_cast<_ValueType*> 01056 (::operator new(sizeof(_ValueType) * __k * __num_samples)); 01057 // Sample. 01058 for (_SeqNumber __s = 0; __s < __k; ++__s) 01059 for (_DifferenceType __i = 0; __i < __num_samples; ++__i) 01060 { 01061 _DifferenceType sample_index = static_cast<_DifferenceType> 01062 (_GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__s]) 01063 * (double(__i + 1) / (__num_samples + 1)) 01064 * (double(__length) / __total_length)); 01065 new(&(__samples[__s * __num_samples + __i])) 01066 _ValueType(__seqs_begin[__s].first[sample_index]); 01067 } 01068 01069 // Sort stable or non-stable, depending on value of template parameter 01070 // "__stable". 01071 _SamplingSorter<__stable, _ValueType*, _Compare>() 01072 (__samples, __samples + (__num_samples * __k), __comp); 01073 01074 for (_ThreadIndex __slab = 0; __slab < __num_threads; ++__slab) 01075 // For each slab / processor. 01076 for (_SeqNumber __seq = 0; __seq < __k; ++__seq) 01077 { 01078 // For each sequence. 01079 if (__slab > 0) 01080 __pieces[__slab][__seq].first = std::upper_bound 01081 (__seqs_begin[__seq].first, __seqs_begin[__seq].second, 01082 __samples[__num_samples * __k * __slab / __num_threads], 01083 __comp) 01084 - __seqs_begin[__seq].first; 01085 else 01086 // Absolute beginning. 01087 __pieces[__slab][__seq].first = 0; 01088 if ((__slab + 1) < __num_threads) 01089 __pieces[__slab][__seq].second = std::upper_bound 01090 (__seqs_begin[__seq].first, __seqs_begin[__seq].second, 01091 __samples[__num_samples * __k * (__slab + 1) / __num_threads], 01092 __comp) 01093 - __seqs_begin[__seq].first; 01094 else 01095 // Absolute end. 01096 __pieces[__slab][__seq].second = 01097 _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__seq]); 01098 } 01099 ::operator delete(__samples); 01100 } 01101 01102 /** 01103 * @brief Exact splitting for parallel multiway-merge routine. 01104 * 01105 * None of the passed sequences may be empty. 01106 */ 01107 template<bool __stable, 01108 typename _RAIterIterator, 01109 typename _Compare, 01110 typename _DifferenceType> 01111 void 01112 multiway_merge_exact_splitting(_RAIterIterator __seqs_begin, 01113 _RAIterIterator __seqs_end, 01114 _DifferenceType __length, 01115 _DifferenceType __total_length, 01116 _Compare __comp, 01117 std::vector<std::pair<_DifferenceType, _DifferenceType> > *__pieces) 01118 { 01119 typedef typename std::iterator_traits<_RAIterIterator> 01120 ::difference_type _SeqNumber; 01121 typedef typename std::iterator_traits<_RAIterIterator> 01122 ::value_type::first_type 01123 _RAIter1; 01124 01125 const bool __tight = (__total_length == __length); 01126 01127 // __k sequences. 01128 const _SeqNumber __k = __seqs_end - __seqs_begin; 01129 01130 const _ThreadIndex __num_threads = omp_get_num_threads(); 01131 01132 // (Settings::multiway_merge_splitting 01133 // == __gnu_parallel::_Settings::EXACT). 01134 std::vector<_RAIter1>* __offsets = 01135 new std::vector<_RAIter1>[__num_threads]; 01136 std::vector<std::pair<_RAIter1, _RAIter1> > __se(__k); 01137 01138 copy(__seqs_begin, __seqs_end, __se.begin()); 01139 01140 _DifferenceType* __borders = 01141 new _DifferenceType[__num_threads + 1]; 01142 equally_split(__length, __num_threads, __borders); 01143 01144 for (_ThreadIndex __s = 0; __s < (__num_threads - 1); ++__s) 01145 { 01146 __offsets[__s].resize(__k); 01147 multiseq_partition(__se.begin(), __se.end(), __borders[__s + 1], 01148 __offsets[__s].begin(), __comp); 01149 01150 // Last one also needed and available. 01151 if (!__tight) 01152 { 01153 __offsets[__num_threads - 1].resize(__k); 01154 multiseq_partition(__se.begin(), __se.end(), 01155 _DifferenceType(__length), 01156 __offsets[__num_threads - 1].begin(), 01157 __comp); 01158 } 01159 } 01160 delete[] __borders; 01161 01162 for (_ThreadIndex __slab = 0; __slab < __num_threads; ++__slab) 01163 { 01164 // For each slab / processor. 01165 for (_SeqNumber __seq = 0; __seq < __k; ++__seq) 01166 { 01167 // For each sequence. 01168 if (__slab == 0) 01169 { 01170 // Absolute beginning. 01171 __pieces[__slab][__seq].first = 0; 01172 } 01173 else 01174 __pieces[__slab][__seq].first = 01175 __pieces[__slab - 1][__seq].second; 01176 if (!__tight || __slab < (__num_threads - 1)) 01177 __pieces[__slab][__seq].second = 01178 __offsets[__slab][__seq] - __seqs_begin[__seq].first; 01179 else 01180 { 01181 // __slab == __num_threads - 1 01182 __pieces[__slab][__seq].second = 01183 _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__seq]); 01184 } 01185 } 01186 } 01187 delete[] __offsets; 01188 } 01189 01190 /** @brief Parallel multi-way merge routine. 01191 * 01192 * The _GLIBCXX_PARALLEL_DECISION is based on the branching factor 01193 * and runtime settings. 01194 * 01195 * Must not be called if the number of sequences is 1. 01196 * 01197 * @param _Splitter functor to split input (either __exact or sampling based) 01198 * 01199 * @param __seqs_begin Begin iterator of iterator pair input sequence. 01200 * @param __seqs_end End iterator of iterator pair input sequence. 01201 * @param __target Begin iterator of output sequence. 01202 * @param __comp Comparator. 01203 * @param __length Maximum length to merge, possibly larger than the 01204 * number of elements available. 01205 * @param __stable Stable merging incurs a performance penalty. 01206 * @param __sentinel Ignored. 01207 * @return End iterator of output sequence. 01208 */ 01209 template<bool __stable, 01210 bool __sentinels, 01211 typename _RAIterIterator, 01212 typename _RAIter3, 01213 typename _DifferenceTp, 01214 typename _Splitter, 01215 typename _Compare> 01216 _RAIter3 01217 parallel_multiway_merge(_RAIterIterator __seqs_begin, 01218 _RAIterIterator __seqs_end, 01219 _RAIter3 __target, 01220 _Splitter __splitter, 01221 _DifferenceTp __length, 01222 _Compare __comp, 01223 _ThreadIndex __num_threads) 01224 { 01225 #if _GLIBCXX_ASSERTIONS 01226 _GLIBCXX_PARALLEL_ASSERT(__seqs_end - __seqs_begin > 1); 01227 #endif 01228 01229 _GLIBCXX_CALL(__length) 01230 01231 typedef _DifferenceTp _DifferenceType; 01232 typedef typename std::iterator_traits<_RAIterIterator> 01233 ::difference_type _SeqNumber; 01234 typedef typename std::iterator_traits<_RAIterIterator> 01235 ::value_type::first_type 01236 _RAIter1; 01237 typedef typename 01238 std::iterator_traits<_RAIter1>::value_type _ValueType; 01239 01240 // Leave only non-empty sequences. 01241 typedef std::pair<_RAIter1, _RAIter1> seq_type; 01242 seq_type* __ne_seqs = new seq_type[__seqs_end - __seqs_begin]; 01243 _SeqNumber __k = 0; 01244 _DifferenceType __total_length = 0; 01245 for (_RAIterIterator __raii = __seqs_begin; 01246 __raii != __seqs_end; ++__raii) 01247 { 01248 _DifferenceTp __seq_length = _GLIBCXX_PARALLEL_LENGTH(*__raii); 01249 if(__seq_length > 0) 01250 { 01251 __total_length += __seq_length; 01252 __ne_seqs[__k++] = *__raii; 01253 } 01254 } 01255 01256 _GLIBCXX_CALL(__total_length) 01257 01258 __length = std::min<_DifferenceTp>(__length, __total_length); 01259 01260 if (__total_length == 0 || __k == 0) 01261 { 01262 delete[] __ne_seqs; 01263 return __target; 01264 } 01265 01266 std::vector<std::pair<_DifferenceType, _DifferenceType> >* __pieces; 01267 01268 __num_threads = static_cast<_ThreadIndex> 01269 (std::min<_DifferenceType>(__num_threads, __total_length)); 01270 01271 # pragma omp parallel num_threads (__num_threads) 01272 { 01273 # pragma omp single 01274 { 01275 __num_threads = omp_get_num_threads(); 01276 // Thread __t will have to merge pieces[__iam][0..__k - 1] 01277 __pieces = new std::vector< 01278 std::pair<_DifferenceType, _DifferenceType> >[__num_threads]; 01279 for (_ThreadIndex __s = 0; __s < __num_threads; ++__s) 01280 __pieces[__s].resize(__k); 01281 01282 _DifferenceType __num_samples = 01283 __gnu_parallel::_Settings::get().merge_oversampling 01284 * __num_threads; 01285 01286 __splitter(__ne_seqs, __ne_seqs + __k, __length, __total_length, 01287 __comp, __pieces); 01288 } //single 01289 01290 _ThreadIndex __iam = omp_get_thread_num(); 01291 01292 _DifferenceType __target_position = 0; 01293 01294 for (_SeqNumber __c = 0; __c < __k; ++__c) 01295 __target_position += __pieces[__iam][__c].first; 01296 01297 seq_type* __chunks = new seq_type[__k]; 01298 01299 for (_SeqNumber __s = 0; __s < __k; ++__s) 01300 __chunks[__s] = std::make_pair(__ne_seqs[__s].first 01301 + __pieces[__iam][__s].first, 01302 __ne_seqs[__s].first 01303 + __pieces[__iam][__s].second); 01304 01305 if(__length > __target_position) 01306 __sequential_multiway_merge<__stable, __sentinels> 01307 (__chunks, __chunks + __k, __target + __target_position, 01308 *(__seqs_begin->second), __length - __target_position, __comp); 01309 01310 delete[] __chunks; 01311 } // parallel 01312 01313 #if _GLIBCXX_ASSERTIONS 01314 _GLIBCXX_PARALLEL_ASSERT( 01315 __is_sorted(__target, __target + __length, __comp)); 01316 #endif 01317 01318 __k = 0; 01319 // Update ends of sequences. 01320 for (_RAIterIterator __raii = __seqs_begin; 01321 __raii != __seqs_end; ++__raii) 01322 { 01323 _DifferenceTp __length = _GLIBCXX_PARALLEL_LENGTH(*__raii); 01324 if(__length > 0) 01325 (*__raii).first += __pieces[__num_threads - 1][__k++].second; 01326 } 01327 01328 delete[] __pieces; 01329 delete[] __ne_seqs; 01330 01331 return __target + __length; 01332 } 01333 01334 /** 01335 * @brief Multiway Merge Frontend. 01336 * 01337 * Merge the sequences specified by seqs_begin and __seqs_end into 01338 * __target. __seqs_begin and __seqs_end must point to a sequence of 01339 * pairs. These pairs must contain an iterator to the beginning 01340 * of a sequence in their first entry and an iterator the _M_end of 01341 * the same sequence in their second entry. 01342 * 01343 * Ties are broken arbitrarily. See stable_multiway_merge for a variant 01344 * that breaks ties by sequence number but is slower. 01345 * 01346 * The first entries of the pairs (i.e. the begin iterators) will be moved 01347 * forward. 01348 * 01349 * The output sequence has to provide enough space for all elements 01350 * that are written to it. 01351 * 01352 * This function will merge the input sequences: 01353 * 01354 * - not stable 01355 * - parallel, depending on the input size and Settings 01356 * - using sampling for splitting 01357 * - not using sentinels 01358 * 01359 * Example: 01360 * 01361 * <pre> 01362 * int sequences[10][10]; 01363 * for (int __i = 0; __i < 10; ++__i) 01364 * for (int __j = 0; __i < 10; ++__j) 01365 * sequences[__i][__j] = __j; 01366 * 01367 * int __out[33]; 01368 * std::vector<std::pair<int*> > seqs; 01369 * for (int __i = 0; __i < 10; ++__i) 01370 * { seqs.push(std::make_pair<int*>(sequences[__i], 01371 * sequences[__i] + 10)) } 01372 * 01373 * multiway_merge(seqs.begin(), seqs.end(), __target, std::less<int>(), 33); 01374 * </pre> 01375 * 01376 * @see stable_multiway_merge 01377 * 01378 * @pre All input sequences must be sorted. 01379 * @pre Target must provide enough space to merge out length elements or 01380 * the number of elements in all sequences, whichever is smaller. 01381 * 01382 * @post [__target, return __value) contains merged __elements from the 01383 * input sequences. 01384 * @post return __value - __target = min(__length, number of elements in all 01385 * sequences). 01386 * 01387 * @param _RAIterPairIterator iterator over sequence 01388 * of pairs of iterators 01389 * @param _RAIterOut iterator over target sequence 01390 * @param _DifferenceTp difference type for the sequence 01391 * @param _Compare strict weak ordering type to compare elements 01392 * in sequences 01393 * 01394 * @param __seqs_begin __begin of sequence __sequence 01395 * @param __seqs_end _M_end of sequence __sequence 01396 * @param __target target sequence to merge to. 01397 * @param __comp strict weak ordering to use for element comparison. 01398 * @param __length Maximum length to merge, possibly larger than the 01399 * number of elements available. 01400 * 01401 * @return _M_end iterator of output sequence 01402 */ 01403 // multiway_merge 01404 // public interface 01405 template<typename _RAIterPairIterator, 01406 typename _RAIterOut, 01407 typename _DifferenceTp, 01408 typename _Compare> 01409 _RAIterOut 01410 multiway_merge(_RAIterPairIterator __seqs_begin, 01411 _RAIterPairIterator __seqs_end, 01412 _RAIterOut __target, 01413 _DifferenceTp __length, _Compare __comp, 01414 __gnu_parallel::sequential_tag) 01415 { 01416 typedef _DifferenceTp _DifferenceType; 01417 _GLIBCXX_CALL(__seqs_end - __seqs_begin) 01418 01419 // catch special case: no sequences 01420 if (__seqs_begin == __seqs_end) 01421 return __target; 01422 01423 // Execute multiway merge *sequentially*. 01424 return __sequential_multiway_merge 01425 </* __stable = */ false, /* __sentinels = */ false> 01426 (__seqs_begin, __seqs_end, __target, 01427 *(__seqs_begin->second), __length, __comp); 01428 } 01429 01430 // public interface 01431 template<typename _RAIterPairIterator, 01432 typename _RAIterOut, 01433 typename _DifferenceTp, 01434 typename _Compare> 01435 _RAIterOut 01436 multiway_merge(_RAIterPairIterator __seqs_begin, 01437 _RAIterPairIterator __seqs_end, 01438 _RAIterOut __target, 01439 _DifferenceTp __length, _Compare __comp, 01440 __gnu_parallel::exact_tag __tag) 01441 { 01442 typedef _DifferenceTp _DifferenceType; 01443 _GLIBCXX_CALL(__seqs_end - __seqs_begin) 01444 01445 // catch special case: no sequences 01446 if (__seqs_begin == __seqs_end) 01447 return __target; 01448 01449 // Execute merge; maybe parallel, depending on the number of merged 01450 // elements and the number of sequences and global thresholds in 01451 // Settings. 01452 if ((__seqs_end - __seqs_begin > 1) 01453 && _GLIBCXX_PARALLEL_CONDITION( 01454 ((__seqs_end - __seqs_begin) >= 01455 __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 01456 && ((_SequenceIndex)__length >= 01457 __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 01458 return parallel_multiway_merge 01459 </* __stable = */ false, /* __sentinels = */ false> 01460 (__seqs_begin, __seqs_end, __target, 01461 multiway_merge_exact_splitting</* __stable = */ false, 01462 typename std::iterator_traits<_RAIterPairIterator> 01463 ::value_type*, _Compare, _DifferenceTp>, 01464 static_cast<_DifferenceType>(__length), __comp, 01465 __tag.__get_num_threads()); 01466 else 01467 return __sequential_multiway_merge 01468 </* __stable = */ false, /* __sentinels = */ false> 01469 (__seqs_begin, __seqs_end, __target, 01470 *(__seqs_begin->second), __length, __comp); 01471 } 01472 01473 // public interface 01474 template<typename _RAIterPairIterator, 01475 typename _RAIterOut, 01476 typename _DifferenceTp, 01477 typename _Compare> 01478 _RAIterOut 01479 multiway_merge(_RAIterPairIterator __seqs_begin, 01480 _RAIterPairIterator __seqs_end, 01481 _RAIterOut __target, 01482 _DifferenceTp __length, _Compare __comp, 01483 __gnu_parallel::sampling_tag __tag) 01484 { 01485 typedef _DifferenceTp _DifferenceType; 01486 _GLIBCXX_CALL(__seqs_end - __seqs_begin) 01487 01488 // catch special case: no sequences 01489 if (__seqs_begin == __seqs_end) 01490 return __target; 01491 01492 // Execute merge; maybe parallel, depending on the number of merged 01493 // elements and the number of sequences and global thresholds in 01494 // Settings. 01495 if ((__seqs_end - __seqs_begin > 1) 01496 && _GLIBCXX_PARALLEL_CONDITION( 01497 ((__seqs_end - __seqs_begin) >= 01498 __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 01499 && ((_SequenceIndex)__length >= 01500 __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 01501 return parallel_multiway_merge 01502 </* __stable = */ false, /* __sentinels = */ false> 01503 (__seqs_begin, __seqs_end, __target, 01504 multiway_merge_exact_splitting</* __stable = */ false, 01505 typename std::iterator_traits<_RAIterPairIterator> 01506 ::value_type*, _Compare, _DifferenceTp>, 01507 static_cast<_DifferenceType>(__length), __comp, 01508 __tag.__get_num_threads()); 01509 else 01510 return __sequential_multiway_merge 01511 </* __stable = */ false, /* __sentinels = */ false> 01512 (__seqs_begin, __seqs_end, __target, 01513 *(__seqs_begin->second), __length, __comp); 01514 } 01515 01516 // public interface 01517 template<typename _RAIterPairIterator, 01518 typename _RAIterOut, 01519 typename _DifferenceTp, 01520 typename _Compare> 01521 _RAIterOut 01522 multiway_merge(_RAIterPairIterator __seqs_begin, 01523 _RAIterPairIterator __seqs_end, 01524 _RAIterOut __target, 01525 _DifferenceTp __length, _Compare __comp, 01526 parallel_tag __tag = parallel_tag(0)) 01527 { return multiway_merge(__seqs_begin, __seqs_end, __target, __length, 01528 __comp, exact_tag(__tag.__get_num_threads())); } 01529 01530 // public interface 01531 template<typename _RAIterPairIterator, 01532 typename _RAIterOut, 01533 typename _DifferenceTp, 01534 typename _Compare> 01535 _RAIterOut 01536 multiway_merge(_RAIterPairIterator __seqs_begin, 01537 _RAIterPairIterator __seqs_end, 01538 _RAIterOut __target, 01539 _DifferenceTp __length, _Compare __comp, 01540 default_parallel_tag __tag) 01541 { return multiway_merge(__seqs_begin, __seqs_end, __target, __length, 01542 __comp, exact_tag(__tag.__get_num_threads())); } 01543 01544 // stable_multiway_merge 01545 // public interface 01546 template<typename _RAIterPairIterator, 01547 typename _RAIterOut, 01548 typename _DifferenceTp, 01549 typename _Compare> 01550 _RAIterOut 01551 stable_multiway_merge(_RAIterPairIterator __seqs_begin, 01552 _RAIterPairIterator __seqs_end, 01553 _RAIterOut __target, 01554 _DifferenceTp __length, _Compare __comp, 01555 __gnu_parallel::sequential_tag) 01556 { 01557 typedef _DifferenceTp _DifferenceType; 01558 _GLIBCXX_CALL(__seqs_end - __seqs_begin) 01559 01560 // catch special case: no sequences 01561 if (__seqs_begin == __seqs_end) 01562 return __target; 01563 01564 // Execute multiway merge *sequentially*. 01565 return __sequential_multiway_merge 01566 </* __stable = */ true, /* __sentinels = */ false> 01567 (__seqs_begin, __seqs_end, __target, 01568 *(__seqs_begin->second), __length, __comp); 01569 } 01570 01571 // public interface 01572 template<typename _RAIterPairIterator, 01573 typename _RAIterOut, 01574 typename _DifferenceTp, 01575 typename _Compare> 01576 _RAIterOut 01577 stable_multiway_merge(_RAIterPairIterator __seqs_begin, 01578 _RAIterPairIterator __seqs_end, 01579 _RAIterOut __target, 01580 _DifferenceTp __length, _Compare __comp, 01581 __gnu_parallel::exact_tag __tag) 01582 { 01583 typedef _DifferenceTp _DifferenceType; 01584 _GLIBCXX_CALL(__seqs_end - __seqs_begin) 01585 01586 // catch special case: no sequences 01587 if (__seqs_begin == __seqs_end) 01588 return __target; 01589 01590 // Execute merge; maybe parallel, depending on the number of merged 01591 // elements and the number of sequences and global thresholds in 01592 // Settings. 01593 if ((__seqs_end - __seqs_begin > 1) 01594 && _GLIBCXX_PARALLEL_CONDITION( 01595 ((__seqs_end - __seqs_begin) >= 01596 __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 01597 && ((_SequenceIndex)__length >= 01598 __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 01599 return parallel_multiway_merge 01600 </* __stable = */ true, /* __sentinels = */ false> 01601 (__seqs_begin, __seqs_end, __target, 01602 multiway_merge_exact_splitting</* __stable = */ true, 01603 typename std::iterator_traits<_RAIterPairIterator> 01604 ::value_type*, _Compare, _DifferenceTp>, 01605 static_cast<_DifferenceType>(__length), __comp, 01606 __tag.__get_num_threads()); 01607 else 01608 return __sequential_multiway_merge 01609 </* __stable = */ true, /* __sentinels = */ false> 01610 (__seqs_begin, __seqs_end, __target, 01611 *(__seqs_begin->second), __length, __comp); 01612 } 01613 01614 // public interface 01615 template<typename _RAIterPairIterator, 01616 typename _RAIterOut, 01617 typename _DifferenceTp, 01618 typename _Compare> 01619 _RAIterOut 01620 stable_multiway_merge(_RAIterPairIterator __seqs_begin, 01621 _RAIterPairIterator __seqs_end, 01622 _RAIterOut __target, 01623 _DifferenceTp __length, _Compare __comp, 01624 sampling_tag __tag) 01625 { 01626 typedef _DifferenceTp _DifferenceType; 01627 _GLIBCXX_CALL(__seqs_end - __seqs_begin) 01628 01629 // catch special case: no sequences 01630 if (__seqs_begin == __seqs_end) 01631 return __target; 01632 01633 // Execute merge; maybe parallel, depending on the number of merged 01634 // elements and the number of sequences and global thresholds in 01635 // Settings. 01636 if ((__seqs_end - __seqs_begin > 1) 01637 && _GLIBCXX_PARALLEL_CONDITION( 01638 ((__seqs_end - __seqs_begin) >= 01639 __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 01640 && ((_SequenceIndex)__length >= 01641 __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 01642 return parallel_multiway_merge 01643 </* __stable = */ true, /* __sentinels = */ false> 01644 (__seqs_begin, __seqs_end, __target, 01645 multiway_merge_sampling_splitting</* __stable = */ true, 01646 typename std::iterator_traits<_RAIterPairIterator> 01647 ::value_type*, _Compare, _DifferenceTp>, 01648 static_cast<_DifferenceType>(__length), __comp, 01649 __tag.__get_num_threads()); 01650 else 01651 return __sequential_multiway_merge 01652 </* __stable = */ true, /* __sentinels = */ false> 01653 (__seqs_begin, __seqs_end, __target, 01654 *(__seqs_begin->second), __length, __comp); 01655 } 01656 01657 // public interface 01658 template<typename _RAIterPairIterator, 01659 typename _RAIterOut, 01660 typename _DifferenceTp, 01661 typename _Compare> 01662 _RAIterOut 01663 stable_multiway_merge(_RAIterPairIterator __seqs_begin, 01664 _RAIterPairIterator __seqs_end, 01665 _RAIterOut __target, 01666 _DifferenceTp __length, _Compare __comp, 01667 parallel_tag __tag = parallel_tag(0)) 01668 { 01669 return stable_multiway_merge 01670 (__seqs_begin, __seqs_end, __target, __length, __comp, 01671 exact_tag(__tag.__get_num_threads())); 01672 } 01673 01674 // public interface 01675 template<typename _RAIterPairIterator, 01676 typename _RAIterOut, 01677 typename _DifferenceTp, 01678 typename _Compare> 01679 _RAIterOut 01680 stable_multiway_merge(_RAIterPairIterator __seqs_begin, 01681 _RAIterPairIterator __seqs_end, 01682 _RAIterOut __target, 01683 _DifferenceTp __length, _Compare __comp, 01684 default_parallel_tag __tag) 01685 { 01686 return stable_multiway_merge 01687 (__seqs_begin, __seqs_end, __target, __length, __comp, 01688 exact_tag(__tag.__get_num_threads())); 01689 } 01690 01691 /** 01692 * @brief Multiway Merge Frontend. 01693 * 01694 * Merge the sequences specified by seqs_begin and __seqs_end into 01695 * __target. __seqs_begin and __seqs_end must point to a sequence of 01696 * pairs. These pairs must contain an iterator to the beginning 01697 * of a sequence in their first entry and an iterator the _M_end of 01698 * the same sequence in their second entry. 01699 * 01700 * Ties are broken arbitrarily. See stable_multiway_merge for a variant 01701 * that breaks ties by sequence number but is slower. 01702 * 01703 * The first entries of the pairs (i.e. the begin iterators) will be moved 01704 * forward accordingly. 01705 * 01706 * The output sequence has to provide enough space for all elements 01707 * that are written to it. 01708 * 01709 * This function will merge the input sequences: 01710 * 01711 * - not stable 01712 * - parallel, depending on the input size and Settings 01713 * - using sampling for splitting 01714 * - using sentinels 01715 * 01716 * You have to take care that the element the _M_end iterator points to is 01717 * readable and contains a value that is greater than any other non-sentinel 01718 * value in all sequences. 01719 * 01720 * Example: 01721 * 01722 * <pre> 01723 * int sequences[10][11]; 01724 * for (int __i = 0; __i < 10; ++__i) 01725 * for (int __j = 0; __i < 11; ++__j) 01726 * sequences[__i][__j] = __j; // __last one is sentinel! 01727 * 01728 * int __out[33]; 01729 * std::vector<std::pair<int*> > seqs; 01730 * for (int __i = 0; __i < 10; ++__i) 01731 * { seqs.push(std::make_pair<int*>(sequences[__i], 01732 * sequences[__i] + 10)) } 01733 * 01734 * multiway_merge(seqs.begin(), seqs.end(), __target, std::less<int>(), 33); 01735 * </pre> 01736 * 01737 * @pre All input sequences must be sorted. 01738 * @pre Target must provide enough space to merge out length elements or 01739 * the number of elements in all sequences, whichever is smaller. 01740 * @pre For each @c __i, @c __seqs_begin[__i].second must be the end 01741 * marker of the sequence, but also reference the one more __sentinel 01742 * element. 01743 * 01744 * @post [__target, return __value) contains merged __elements from the 01745 * input sequences. 01746 * @post return __value - __target = min(__length, number of elements in all 01747 * sequences). 01748 * 01749 * @see stable_multiway_merge_sentinels 01750 * 01751 * @param _RAIterPairIterator iterator over sequence 01752 * of pairs of iterators 01753 * @param _RAIterOut iterator over target sequence 01754 * @param _DifferenceTp difference type for the sequence 01755 * @param _Compare strict weak ordering type to compare elements 01756 * in sequences 01757 * 01758 * @param __seqs_begin __begin of sequence __sequence 01759 * @param __seqs_end _M_end of sequence __sequence 01760 * @param __target target sequence to merge to. 01761 * @param __comp strict weak ordering to use for element comparison. 01762 * @param __length Maximum length to merge, possibly larger than the 01763 * number of elements available. 01764 * 01765 * @return _M_end iterator of output sequence 01766 */ 01767 // multiway_merge_sentinels 01768 // public interface 01769 template<typename _RAIterPairIterator, 01770 typename _RAIterOut, 01771 typename _DifferenceTp, 01772 typename _Compare> 01773 _RAIterOut 01774 multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, 01775 _RAIterPairIterator __seqs_end, 01776 _RAIterOut __target, 01777 _DifferenceTp __length, _Compare __comp, 01778 __gnu_parallel::sequential_tag) 01779 { 01780 typedef _DifferenceTp _DifferenceType; 01781 _GLIBCXX_CALL(__seqs_end - __seqs_begin) 01782 01783 // catch special case: no sequences 01784 if (__seqs_begin == __seqs_end) 01785 return __target; 01786 01787 // Execute multiway merge *sequentially*. 01788 return __sequential_multiway_merge 01789 </* __stable = */ false, /* __sentinels = */ true> 01790 (__seqs_begin, __seqs_end, 01791 __target, *(__seqs_begin->second), __length, __comp); 01792 } 01793 01794 // public interface 01795 template<typename _RAIterPairIterator, 01796 typename _RAIterOut, 01797 typename _DifferenceTp, 01798 typename _Compare> 01799 _RAIterOut 01800 multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, 01801 _RAIterPairIterator __seqs_end, 01802 _RAIterOut __target, 01803 _DifferenceTp __length, _Compare __comp, 01804 __gnu_parallel::exact_tag __tag) 01805 { 01806 typedef _DifferenceTp _DifferenceType; 01807 _GLIBCXX_CALL(__seqs_end - __seqs_begin) 01808 01809 // catch special case: no sequences 01810 if (__seqs_begin == __seqs_end) 01811 return __target; 01812 01813 // Execute merge; maybe parallel, depending on the number of merged 01814 // elements and the number of sequences and global thresholds in 01815 // Settings. 01816 if ((__seqs_end - __seqs_begin > 1) 01817 && _GLIBCXX_PARALLEL_CONDITION( 01818 ((__seqs_end - __seqs_begin) >= 01819 __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 01820 && ((_SequenceIndex)__length >= 01821 __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 01822 return parallel_multiway_merge 01823 </* __stable = */ false, /* __sentinels = */ true> 01824 (__seqs_begin, __seqs_end, __target, 01825 multiway_merge_exact_splitting</* __stable = */ false, 01826 typename std::iterator_traits<_RAIterPairIterator> 01827 ::value_type*, _Compare, _DifferenceTp>, 01828 static_cast<_DifferenceType>(__length), __comp, 01829 __tag.__get_num_threads()); 01830 else 01831 return __sequential_multiway_merge 01832 </* __stable = */ false, /* __sentinels = */ true> 01833 (__seqs_begin, __seqs_end, __target, 01834 *(__seqs_begin->second), __length, __comp); 01835 } 01836 01837 // public interface 01838 template<typename _RAIterPairIterator, 01839 typename _RAIterOut, 01840 typename _DifferenceTp, 01841 typename _Compare> 01842 _RAIterOut 01843 multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, 01844 _RAIterPairIterator __seqs_end, 01845 _RAIterOut __target, 01846 _DifferenceTp __length, _Compare __comp, 01847 sampling_tag __tag) 01848 { 01849 typedef _DifferenceTp _DifferenceType; 01850 _GLIBCXX_CALL(__seqs_end - __seqs_begin) 01851 01852 // catch special case: no sequences 01853 if (__seqs_begin == __seqs_end) 01854 return __target; 01855 01856 // Execute merge; maybe parallel, depending on the number of merged 01857 // elements and the number of sequences and global thresholds in 01858 // Settings. 01859 if ((__seqs_end - __seqs_begin > 1) 01860 && _GLIBCXX_PARALLEL_CONDITION( 01861 ((__seqs_end - __seqs_begin) >= 01862 __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 01863 && ((_SequenceIndex)__length >= 01864 __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 01865 return parallel_multiway_merge 01866 </* __stable = */ false, /* __sentinels = */ true> 01867 (__seqs_begin, __seqs_end, __target, 01868 multiway_merge_sampling_splitting</* __stable = */ false, 01869 typename std::iterator_traits<_RAIterPairIterator> 01870 ::value_type*, _Compare, _DifferenceTp>, 01871 static_cast<_DifferenceType>(__length), __comp, 01872 __tag.__get_num_threads()); 01873 else 01874 return __sequential_multiway_merge 01875 </* __stable = */false, /* __sentinels = */ true>( 01876 __seqs_begin, __seqs_end, __target, 01877 *(__seqs_begin->second), __length, __comp); 01878 } 01879 01880 // public interface 01881 template<typename _RAIterPairIterator, 01882 typename _RAIterOut, 01883 typename _DifferenceTp, 01884 typename _Compare> 01885 _RAIterOut 01886 multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, 01887 _RAIterPairIterator __seqs_end, 01888 _RAIterOut __target, 01889 _DifferenceTp __length, _Compare __comp, 01890 parallel_tag __tag = parallel_tag(0)) 01891 { 01892 return multiway_merge_sentinels 01893 (__seqs_begin, __seqs_end, __target, __length, __comp, 01894 exact_tag(__tag.__get_num_threads())); 01895 } 01896 01897 // public interface 01898 template<typename _RAIterPairIterator, 01899 typename _RAIterOut, 01900 typename _DifferenceTp, 01901 typename _Compare> 01902 _RAIterOut 01903 multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, 01904 _RAIterPairIterator __seqs_end, 01905 _RAIterOut __target, 01906 _DifferenceTp __length, _Compare __comp, 01907 default_parallel_tag __tag) 01908 { 01909 return multiway_merge_sentinels 01910 (__seqs_begin, __seqs_end, __target, __length, __comp, 01911 exact_tag(__tag.__get_num_threads())); 01912 } 01913 01914 // stable_multiway_merge_sentinels 01915 // public interface 01916 template<typename _RAIterPairIterator, 01917 typename _RAIterOut, 01918 typename _DifferenceTp, 01919 typename _Compare> 01920 _RAIterOut 01921 stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, 01922 _RAIterPairIterator __seqs_end, 01923 _RAIterOut __target, 01924 _DifferenceTp __length, _Compare __comp, 01925 __gnu_parallel::sequential_tag) 01926 { 01927 typedef _DifferenceTp _DifferenceType; 01928 _GLIBCXX_CALL(__seqs_end - __seqs_begin) 01929 01930 // catch special case: no sequences 01931 if (__seqs_begin == __seqs_end) 01932 return __target; 01933 01934 // Execute multiway merge *sequentially*. 01935 return __sequential_multiway_merge 01936 </* __stable = */ true, /* __sentinels = */ true> 01937 (__seqs_begin, __seqs_end, __target, 01938 *(__seqs_begin->second), __length, __comp); 01939 } 01940 01941 // public interface 01942 template<typename _RAIterPairIterator, 01943 typename _RAIterOut, 01944 typename _DifferenceTp, 01945 typename _Compare> 01946 _RAIterOut 01947 stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, 01948 _RAIterPairIterator __seqs_end, 01949 _RAIterOut __target, 01950 _DifferenceTp __length, _Compare __comp, 01951 __gnu_parallel::exact_tag __tag) 01952 { 01953 typedef _DifferenceTp _DifferenceType; 01954 _GLIBCXX_CALL(__seqs_end - __seqs_begin) 01955 01956 // catch special case: no sequences 01957 if (__seqs_begin == __seqs_end) 01958 return __target; 01959 01960 // Execute merge; maybe parallel, depending on the number of merged 01961 // elements and the number of sequences and global thresholds in 01962 // Settings. 01963 if ((__seqs_end - __seqs_begin > 1) 01964 && _GLIBCXX_PARALLEL_CONDITION( 01965 ((__seqs_end - __seqs_begin) >= 01966 __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 01967 && ((_SequenceIndex)__length >= 01968 __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 01969 return parallel_multiway_merge 01970 </* __stable = */ true, /* __sentinels = */ true> 01971 (__seqs_begin, __seqs_end, __target, 01972 multiway_merge_exact_splitting</* __stable = */ true, 01973 typename std::iterator_traits<_RAIterPairIterator> 01974 ::value_type*, _Compare, _DifferenceTp>, 01975 static_cast<_DifferenceType>(__length), __comp, 01976 __tag.__get_num_threads()); 01977 else 01978 return __sequential_multiway_merge 01979 </* __stable = */ true, /* __sentinels = */ true> 01980 (__seqs_begin, __seqs_end, __target, 01981 *(__seqs_begin->second), __length, __comp); 01982 } 01983 01984 // public interface 01985 template<typename _RAIterPairIterator, 01986 typename _RAIterOut, 01987 typename _DifferenceTp, 01988 typename _Compare> 01989 _RAIterOut 01990 stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, 01991 _RAIterPairIterator __seqs_end, 01992 _RAIterOut __target, 01993 _DifferenceTp __length, 01994 _Compare __comp, 01995 sampling_tag __tag) 01996 { 01997 typedef _DifferenceTp _DifferenceType; 01998 _GLIBCXX_CALL(__seqs_end - __seqs_begin) 01999 02000 // catch special case: no sequences 02001 if (__seqs_begin == __seqs_end) 02002 return __target; 02003 02004 // Execute merge; maybe parallel, depending on the number of merged 02005 // elements and the number of sequences and global thresholds in 02006 // Settings. 02007 if ((__seqs_end - __seqs_begin > 1) 02008 && _GLIBCXX_PARALLEL_CONDITION( 02009 ((__seqs_end - __seqs_begin) >= 02010 __gnu_parallel::_Settings::get().multiway_merge_minimal_k) 02011 && ((_SequenceIndex)__length >= 02012 __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) 02013 return parallel_multiway_merge 02014 </* __stable = */ true, /* __sentinels = */ true> 02015 (__seqs_begin, __seqs_end, __target, 02016 multiway_merge_sampling_splitting</* __stable = */ true, 02017 typename std::iterator_traits<_RAIterPairIterator> 02018 ::value_type*, _Compare, _DifferenceTp>, 02019 static_cast<_DifferenceType>(__length), __comp, 02020 __tag.__get_num_threads()); 02021 else 02022 return __sequential_multiway_merge 02023 </* __stable = */ true, /* __sentinels = */ true> 02024 (__seqs_begin, __seqs_end, __target, 02025 *(__seqs_begin->second), __length, __comp); 02026 } 02027 02028 // public interface 02029 template<typename _RAIterPairIterator, 02030 typename _RAIterOut, 02031 typename _DifferenceTp, 02032 typename _Compare> 02033 _RAIterOut 02034 stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, 02035 _RAIterPairIterator __seqs_end, 02036 _RAIterOut __target, 02037 _DifferenceTp __length, 02038 _Compare __comp, 02039 parallel_tag __tag = parallel_tag(0)) 02040 { 02041 return stable_multiway_merge_sentinels 02042 (__seqs_begin, __seqs_end, __target, __length, __comp, 02043 exact_tag(__tag.__get_num_threads())); 02044 } 02045 02046 // public interface 02047 template<typename _RAIterPairIterator, 02048 typename _RAIterOut, 02049 typename _DifferenceTp, 02050 typename _Compare> 02051 _RAIterOut 02052 stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, 02053 _RAIterPairIterator __seqs_end, 02054 _RAIterOut __target, 02055 _DifferenceTp __length, _Compare __comp, 02056 default_parallel_tag __tag) 02057 { 02058 return stable_multiway_merge_sentinels 02059 (__seqs_begin, __seqs_end, __target, __length, __comp, 02060 exact_tag(__tag.__get_num_threads())); 02061 } 02062 }; // namespace __gnu_parallel 02063 02064 #endif /* _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H */