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