3 // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 3, or (at your option) any later
11 // This library is distributed in the hope that it will be useful, but
12 // WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
25 /** @file parallel/multiway_merge.h
26 * @brief Implementation of sequential and parallel multiway merge.
28 * Explanations on the high-speed merging routines in the appendix of
31 * Fast priority queues for cached memory.
32 * ACM Journal of Experimental Algorithmics, 5, 2000.
34 * This file is a GNU parallel extension to the Standard C++ Library.
37 // Written by Johannes Singler and Manuel Holtgrewe.
39 #ifndef _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H
40 #define _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H
44 #include <bits/stl_algo.h>
45 #include <parallel/features.h>
46 #include <parallel/parallel.h>
47 #include <parallel/losertree.h>
48 #if _GLIBCXX_ASSERTIONS
49 #include <parallel/checkers.h>
52 /** @brief Length of a sequence described by a pair of iterators. */
53 #define _GLIBCXX_PARALLEL_LENGTH(__s) ((__s).second - (__s).first)
55 namespace __gnu_parallel
57 /** @brief _Iterator wrapper supporting an implicit supremum at the end
58 * of the sequence, dominating all comparisons.
60 * The implicit supremum comes with a performance cost.
62 * Deriving from _RAIter is not possible since
63 * _RAIter need not be a class.
65 template<typename _RAIter, typename _Compare>
66 class _GuardedIterator
69 /** @brief Current iterator __position. */
72 /** @brief End iterator of the sequence. */
75 /** @brief _Compare. */
79 /** @brief Constructor. Sets iterator to beginning of sequence.
80 * @param __begin Begin iterator of sequence.
81 * @param __end End iterator of sequence.
82 * @param __comp Comparator provided for associated overloaded
83 * compare operators. */
84 _GuardedIterator(_RAIter __begin, _RAIter __end, _Compare& __comp)
85 : _M_current(__begin), _M_end(__end), __comp(__comp)
88 /** @brief Pre-increment operator.
90 _GuardedIterator<_RAIter, _Compare>&
97 /** @brief Dereference operator.
98 * @return Referenced element. */
99 typename std::iterator_traits<_RAIter>::value_type&
101 { return *_M_current; }
103 /** @brief Convert to wrapped iterator.
104 * @return Wrapped iterator. */
106 { return _M_current; }
108 /** @brief Compare two elements referenced by guarded iterators.
109 * @param __bi1 First iterator.
110 * @param __bi2 Second iterator.
111 * @return @c true if less. */
113 operator<(_GuardedIterator<_RAIter, _Compare>& __bi1,
114 _GuardedIterator<_RAIter, _Compare>& __bi2)
116 if (__bi1._M_current == __bi1._M_end) // __bi1 is sup
117 return __bi2._M_current == __bi2._M_end; // __bi2 is not sup
118 if (__bi2._M_current == __bi2._M_end) // __bi2 is sup
120 return (__bi1.__comp)(*__bi1, *__bi2); // normal compare
123 /** @brief Compare two elements referenced by guarded iterators.
124 * @param __bi1 First iterator.
125 * @param __bi2 Second iterator.
126 * @return @c True if less equal. */
128 operator<=(_GuardedIterator<_RAIter, _Compare>& __bi1,
129 _GuardedIterator<_RAIter, _Compare>& __bi2)
131 if (__bi2._M_current == __bi2._M_end) // __bi1 is sup
132 return __bi1._M_current != __bi1._M_end; // __bi2 is not sup
133 if (__bi1._M_current == __bi1._M_end) // __bi2 is sup
135 return !(__bi1.__comp)(*__bi2, *__bi1); // normal compare
139 template<typename _RAIter, typename _Compare>
140 class _UnguardedIterator
143 /** @brief Current iterator __position. */
145 /** @brief _Compare. */
146 mutable _Compare& __comp;
149 /** @brief Constructor. Sets iterator to beginning of sequence.
150 * @param __begin Begin iterator of sequence.
151 * @param __end Unused, only for compatibility.
152 * @param __comp Unused, only for compatibility. */
153 _UnguardedIterator(_RAIter __begin,
154 _RAIter /* __end */, _Compare& __comp)
155 : _M_current(__begin), __comp(__comp)
158 /** @brief Pre-increment operator.
160 _UnguardedIterator<_RAIter, _Compare>&
167 /** @brief Dereference operator.
168 * @return Referenced element. */
169 typename std::iterator_traits<_RAIter>::value_type&
171 { return *_M_current; }
173 /** @brief Convert to wrapped iterator.
174 * @return Wrapped iterator. */
176 { return _M_current; }
178 /** @brief Compare two elements referenced by unguarded iterators.
179 * @param __bi1 First iterator.
180 * @param __bi2 Second iterator.
181 * @return @c true if less. */
183 operator<(_UnguardedIterator<_RAIter, _Compare>& __bi1,
184 _UnguardedIterator<_RAIter, _Compare>& __bi2)
187 return (__bi1.__comp)(*__bi1, *__bi2);
190 /** @brief Compare two elements referenced by unguarded iterators.
191 * @param __bi1 First iterator.
192 * @param __bi2 Second iterator.
193 * @return @c True if less equal. */
195 operator<=(_UnguardedIterator<_RAIter, _Compare>& __bi1,
196 _UnguardedIterator<_RAIter, _Compare>& __bi2)
199 return !(__bi1.__comp)(*__bi2, *__bi1);
203 /** @brief Highly efficient 3-way merging procedure.
205 * Merging is done with the algorithm implementation described by Peter
206 * Sanders. Basically, the idea is to minimize the number of necessary
207 * comparison after merging an element. The implementation trick
208 * that makes this fast is that the order of the sequences is stored
209 * in the instruction pointer (translated into labels in C++).
211 * This works well for merging up to 4 sequences.
213 * Note that making the merging stable does <em>not</em> come at a
216 * Whether the merging is done guarded or unguarded is selected by the
217 * used iterator class.
219 * @param __seqs_begin Begin iterator of iterator pair input sequence.
220 * @param __seqs_end End iterator of iterator pair input sequence.
221 * @param __target Begin iterator of output sequence.
222 * @param __comp Comparator.
223 * @param __length Maximum length to merge, less equal than the
224 * total number of elements available.
226 * @return End iterator of output sequence.
228 template<template<typename RAI, typename C> class iterator,
229 typename _RAIterIterator,
231 typename _DifferenceTp,
234 multiway_merge_3_variant(_RAIterIterator __seqs_begin,
235 _RAIterIterator __seqs_end,
237 _DifferenceTp __length, _Compare __comp)
239 _GLIBCXX_CALL(__length);
241 typedef _DifferenceTp _DifferenceType;
243 typedef typename std::iterator_traits<_RAIterIterator>
244 ::value_type::first_type
246 typedef typename std::iterator_traits<_RAIter1>::value_type
252 #if _GLIBCXX_ASSERTIONS
253 _DifferenceTp __orig_length = __length;
256 iterator<_RAIter1, _Compare>
257 __seq0(__seqs_begin[0].first, __seqs_begin[0].second, __comp),
258 __seq1(__seqs_begin[1].first, __seqs_begin[1].second, __comp),
259 __seq2(__seqs_begin[2].first, __seqs_begin[2].second, __comp);
261 if (__seq0 <= __seq1)
263 if (__seq1 <= __seq2)
273 if (__seq1 <= __seq2)
275 if (__seq0 <= __seq2)
283 #define _GLIBCXX_PARALLEL_MERGE_3_CASE(__a, __b, __c, __c0, __c1) \
284 __s ## __a ## __b ## __c : \
285 *__target = *__seq ## __a; \
289 if (__length == 0) goto __finish; \
290 if (__seq ## __a __c0 __seq ## __b) goto __s ## __a ## __b ## __c; \
291 if (__seq ## __a __c1 __seq ## __c) goto __s ## __b ## __a ## __c; \
292 goto __s ## __b ## __c ## __a;
294 _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 1, 2, <=, <=);
295 _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 2, 0, <=, < );
296 _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 0, 1, < , < );
297 _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 0, 2, < , <=);
298 _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 2, 1, <=, <=);
299 _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 1, 0, < , < );
301 #undef _GLIBCXX_PARALLEL_MERGE_3_CASE
306 #if _GLIBCXX_ASSERTIONS
307 _GLIBCXX_PARALLEL_ASSERT(
308 ((_RAIter1)__seq0 - __seqs_begin[0].first) +
309 ((_RAIter1)__seq1 - __seqs_begin[1].first) +
310 ((_RAIter1)__seq2 - __seqs_begin[2].first)
314 __seqs_begin[0].first = __seq0;
315 __seqs_begin[1].first = __seq1;
316 __seqs_begin[2].first = __seq2;
322 * @brief Highly efficient 4-way merging procedure.
324 * Merging is done with the algorithm implementation described by Peter
325 * Sanders. Basically, the idea is to minimize the number of necessary
326 * comparison after merging an element. The implementation trick
327 * that makes this fast is that the order of the sequences is stored
328 * in the instruction pointer (translated into goto labels in C++).
330 * This works well for merging up to 4 sequences.
332 * Note that making the merging stable does <em>not</em> come at a
335 * Whether the merging is done guarded or unguarded is selected by the
336 * used iterator class.
338 * @param __seqs_begin Begin iterator of iterator pair input sequence.
339 * @param __seqs_end End iterator of iterator pair input sequence.
340 * @param __target Begin iterator of output sequence.
341 * @param __comp Comparator.
342 * @param __length Maximum length to merge, less equal than the
343 * total number of elements available.
345 * @return End iterator of output sequence.
347 template<template<typename RAI, typename C> class iterator,
348 typename _RAIterIterator,
350 typename _DifferenceTp,
353 multiway_merge_4_variant(_RAIterIterator __seqs_begin,
354 _RAIterIterator __seqs_end,
356 _DifferenceTp __length, _Compare __comp)
358 _GLIBCXX_CALL(__length);
359 typedef _DifferenceTp _DifferenceType;
361 typedef typename std::iterator_traits<_RAIterIterator>
362 ::value_type::first_type
364 typedef typename std::iterator_traits<_RAIter1>::value_type
367 iterator<_RAIter1, _Compare>
368 __seq0(__seqs_begin[0].first, __seqs_begin[0].second, __comp),
369 __seq1(__seqs_begin[1].first, __seqs_begin[1].second, __comp),
370 __seq2(__seqs_begin[2].first, __seqs_begin[2].second, __comp),
371 __seq3(__seqs_begin[3].first, __seqs_begin[3].second, __comp);
373 #define _GLIBCXX_PARALLEL_DECISION(__a, __b, __c, __d) { \
374 if (__seq ## __d < __seq ## __a) \
375 goto __s ## __d ## __a ## __b ## __c; \
376 if (__seq ## __d < __seq ## __b) \
377 goto __s ## __a ## __d ## __b ## __c; \
378 if (__seq ## __d < __seq ## __c) \
379 goto __s ## __a ## __b ## __d ## __c; \
380 goto __s ## __a ## __b ## __c ## __d; }
382 if (__seq0 <= __seq1)
384 if (__seq1 <= __seq2)
385 _GLIBCXX_PARALLEL_DECISION(0,1,2,3)
388 _GLIBCXX_PARALLEL_DECISION(2,0,1,3)
390 _GLIBCXX_PARALLEL_DECISION(0,2,1,3)
394 if (__seq1 <= __seq2)
396 if (__seq0 <= __seq2)
397 _GLIBCXX_PARALLEL_DECISION(1,0,2,3)
399 _GLIBCXX_PARALLEL_DECISION(1,2,0,3)
402 _GLIBCXX_PARALLEL_DECISION(2,1,0,3)
405 #define _GLIBCXX_PARALLEL_MERGE_4_CASE(__a, __b, __c, __d, \
407 __s ## __a ## __b ## __c ## __d: \
408 if (__length == 0) goto __finish; \
409 *__target = *__seq ## __a; \
413 if (__seq ## __a __c0 __seq ## __b) \
414 goto __s ## __a ## __b ## __c ## __d; \
415 if (__seq ## __a __c1 __seq ## __c) \
416 goto __s ## __b ## __a ## __c ## __d; \
417 if (__seq ## __a __c2 __seq ## __d) \
418 goto __s ## __b ## __c ## __a ## __d; \
419 goto __s ## __b ## __c ## __d ## __a;
421 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 2, 3, <=, <=, <=);
422 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 3, 2, <=, <=, <=);
423 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 1, 3, <=, <=, <=);
424 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 3, 1, <=, <=, <=);
425 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 1, 2, <=, <=, <=);
426 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 2, 1, <=, <=, <=);
427 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 2, 3, < , <=, <=);
428 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 3, 2, < , <=, <=);
429 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 0, 3, <=, < , <=);
430 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 3, 0, <=, <=, < );
431 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 0, 2, <=, < , <=);
432 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 2, 0, <=, <=, < );
433 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 1, 3, < , < , <=);
434 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 3, 1, < , <=, < );
435 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 0, 3, < , < , <=);
436 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 3, 0, < , <=, < );
437 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 0, 1, <=, < , < );
438 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 1, 0, <=, < , < );
439 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 1, 2, < , < , < );
440 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 2, 1, < , < , < );
441 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 0, 2, < , < , < );
442 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 2, 0, < , < , < );
443 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 0, 1, < , < , < );
444 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 1, 0, < , < , < );
446 #undef _GLIBCXX_PARALLEL_MERGE_4_CASE
447 #undef _GLIBCXX_PARALLEL_DECISION
452 __seqs_begin[0].first = __seq0;
453 __seqs_begin[1].first = __seq1;
454 __seqs_begin[2].first = __seq2;
455 __seqs_begin[3].first = __seq3;
460 /** @brief Multi-way merging procedure for a high branching factor,
463 * This merging variant uses a LoserTree class as selected by <tt>_LT</tt>.
465 * Stability is selected through the used LoserTree class <tt>_LT</tt>.
467 * At least one non-empty sequence is required.
469 * @param __seqs_begin Begin iterator of iterator pair input sequence.
470 * @param __seqs_end End iterator of iterator pair input sequence.
471 * @param __target Begin iterator of output sequence.
472 * @param __comp Comparator.
473 * @param __length Maximum length to merge, less equal than the
474 * total number of elements available.
476 * @return End iterator of output sequence.
478 template<typename _LT,
479 typename _RAIterIterator,
481 typename _DifferenceTp,
484 multiway_merge_loser_tree(_RAIterIterator __seqs_begin,
485 _RAIterIterator __seqs_end,
487 _DifferenceTp __length, _Compare __comp)
489 _GLIBCXX_CALL(__length)
491 typedef _DifferenceTp _DifferenceType;
492 typedef typename std::iterator_traits<_RAIterIterator>
493 ::value_type::first_type
495 typedef typename std::iterator_traits<_RAIter1>::value_type
498 int __k = static_cast<int>(__seqs_end - __seqs_begin);
500 _LT __lt(__k, __comp);
502 // Default value for potentially non-default-constructible types.
503 _ValueType* __arbitrary_element = NULL;
505 for (int __t = 0; __t < __k; ++__t)
507 if(__arbitrary_element == NULL
508 && _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__t]) > 0)
509 __arbitrary_element = &(*__seqs_begin[__t].first);
512 for (int __t = 0; __t < __k; ++__t)
514 if (__seqs_begin[__t].first == __seqs_begin[__t].second)
515 __lt.__insert_start(*__arbitrary_element, __t, true);
517 __lt.__insert_start(*__seqs_begin[__t].first, __t, false);
524 for (_DifferenceType __i = 0; __i < __length; ++__i)
527 __source = __lt.__get_min_source();
529 *(__target++) = *(__seqs_begin[__source].first++);
532 if (__seqs_begin[__source].first == __seqs_begin[__source].second)
533 __lt.__delete_min_insert(*__arbitrary_element, true);
535 // Replace from same __source.
536 __lt.__delete_min_insert(*__seqs_begin[__source].first, false);
542 /** @brief Multi-way merging procedure for a high branching factor,
545 * Merging is done using the LoserTree class <tt>_LT</tt>.
547 * Stability is selected by the used LoserTrees.
549 * @pre No input will run out of elements during the merge.
551 * @param __seqs_begin Begin iterator of iterator pair input sequence.
552 * @param __seqs_end End iterator of iterator pair input sequence.
553 * @param __target Begin iterator of output sequence.
554 * @param __comp Comparator.
555 * @param __length Maximum length to merge, less equal than the
556 * total number of elements available.
558 * @return End iterator of output sequence.
560 template<typename _LT,
561 typename _RAIterIterator,
563 typename _DifferenceTp, typename _Compare>
565 multiway_merge_loser_tree_unguarded(_RAIterIterator __seqs_begin,
566 _RAIterIterator __seqs_end,
568 const typename std::iterator_traits<typename std::iterator_traits<
569 _RAIterIterator>::value_type::first_type>::value_type&
571 _DifferenceTp __length,
574 _GLIBCXX_CALL(__length)
575 typedef _DifferenceTp _DifferenceType;
577 typedef typename std::iterator_traits<_RAIterIterator>
578 ::value_type::first_type
580 typedef typename std::iterator_traits<_RAIter1>::value_type
583 int __k = __seqs_end - __seqs_begin;
585 _LT __lt(__k, __sentinel, __comp);
587 for (int __t = 0; __t < __k; ++__t)
589 #if _GLIBCXX_ASSERTIONS
590 _GLIBCXX_PARALLEL_ASSERT(__seqs_begin[__t].first
591 != __seqs_begin[__t].second);
593 __lt.__insert_start(*__seqs_begin[__t].first, __t, false);
600 #if _GLIBCXX_ASSERTIONS
601 _DifferenceType __i = 0;
604 _RAIter3 __target_end = __target + __length;
605 while (__target < __target_end)
608 __source = __lt.__get_min_source();
610 #if _GLIBCXX_ASSERTIONS
611 _GLIBCXX_PARALLEL_ASSERT(0 <= __source && __source < __k);
612 _GLIBCXX_PARALLEL_ASSERT(__i == 0
613 || !__comp(*(__seqs_begin[__source].first), *(__target - 1)));
617 *(__target++) = *(__seqs_begin[__source].first++);
619 #if _GLIBCXX_ASSERTIONS
622 // Replace from same __source.
623 __lt.__delete_min_insert(*__seqs_begin[__source].first, false);
630 /** @brief Multi-way merging procedure for a high branching factor,
631 * requiring sentinels to exist.
633 * @param __stable The value must the same as for the used LoserTrees.
634 * @param UnguardedLoserTree _Loser Tree variant to use for the unguarded
636 * @param GuardedLoserTree _Loser Tree variant to use for the guarded
639 * @param __seqs_begin Begin iterator of iterator pair input sequence.
640 * @param __seqs_end End iterator of iterator pair input sequence.
641 * @param __target Begin iterator of output sequence.
642 * @param __comp Comparator.
643 * @param __length Maximum length to merge, less equal than the
644 * total number of elements available.
646 * @return End iterator of output sequence.
648 template<typename UnguardedLoserTree,
649 typename _RAIterIterator,
651 typename _DifferenceTp,
654 multiway_merge_loser_tree_sentinel(_RAIterIterator __seqs_begin,
655 _RAIterIterator __seqs_end,
657 const typename std::iterator_traits<typename std::iterator_traits<
658 _RAIterIterator>::value_type::first_type>::value_type&
660 _DifferenceTp __length,
663 _GLIBCXX_CALL(__length)
665 typedef _DifferenceTp _DifferenceType;
666 typedef std::iterator_traits<_RAIterIterator> _TraitsType;
667 typedef typename std::iterator_traits<_RAIterIterator>
668 ::value_type::first_type
670 typedef typename std::iterator_traits<_RAIter1>::value_type
673 _RAIter3 __target_end;
675 for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
676 // Move the sequence ends to the sentinel. This has the
677 // effect that the sentinel appears to be within the sequence. Then,
678 // we can use the unguarded variant if we merge out as many
679 // non-sentinel elements as we have.
682 __target_end = multiway_merge_loser_tree_unguarded<UnguardedLoserTree>
683 (__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp);
685 #if _GLIBCXX_ASSERTIONS
686 _GLIBCXX_PARALLEL_ASSERT(__target_end == __target + __length);
687 _GLIBCXX_PARALLEL_ASSERT(__is_sorted(__target, __target_end, __comp));
690 // Restore the sequence ends so the sentinels are not contained in the
691 // sequence any more (see comment in loop above).
692 for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
699 * @brief Traits for determining whether the loser tree should
700 * use pointers or copies.
702 * The field "_M_use_pointer" is used to determine whether to use pointers
703 * in he loser trees or whether to copy the values into the loser tree.
705 * The default behavior is to use pointers if the data type is 4 times as
706 * big as the pointer to it.
708 * Specialize for your data type to customize the behavior.
713 * struct _LoserTreeTraits<int>
714 * { static const bool _M_use_pointer = false; };
717 * struct _LoserTreeTraits<heavyweight_type>
718 * { static const bool _M_use_pointer = true; };
720 * @param _Tp type to give the loser tree traits for.
722 template <typename _Tp>
723 struct _LoserTreeTraits
726 * @brief True iff to use pointers instead of values in loser trees.
728 * The default behavior is to use pointers if the data type is four
729 * times as big as the pointer to it.
731 static const bool _M_use_pointer = (sizeof(_Tp) > 4 * sizeof(_Tp*));
735 * @brief Switch for 3-way merging with __sentinels turned off.
737 * Note that 3-way merging is always stable!
739 template<bool __sentinels /*default == false*/,
740 typename _RAIterIterator,
742 typename _DifferenceTp,
744 struct __multiway_merge_3_variant_sentinel_switch
747 operator()(_RAIterIterator __seqs_begin,
748 _RAIterIterator __seqs_end,
750 _DifferenceTp __length, _Compare __comp)
751 { return multiway_merge_3_variant<_GuardedIterator>
752 (__seqs_begin, __seqs_end, __target, __length, __comp); }
756 * @brief Switch for 3-way merging with __sentinels turned on.
758 * Note that 3-way merging is always stable!
760 template<typename _RAIterIterator,
762 typename _DifferenceTp,
764 struct __multiway_merge_3_variant_sentinel_switch<true, _RAIterIterator,
765 _RAIter3, _DifferenceTp,
769 operator()(_RAIterIterator __seqs_begin,
770 _RAIterIterator __seqs_end,
772 _DifferenceTp __length, _Compare __comp)
773 { return multiway_merge_3_variant<_UnguardedIterator>
774 (__seqs_begin, __seqs_end, __target, __length, __comp); }
778 * @brief Switch for 4-way merging with __sentinels turned off.
780 * Note that 4-way merging is always stable!
782 template<bool __sentinels /*default == false*/,
783 typename _RAIterIterator,
785 typename _DifferenceTp,
787 struct __multiway_merge_4_variant_sentinel_switch
790 operator()(_RAIterIterator __seqs_begin,
791 _RAIterIterator __seqs_end,
793 _DifferenceTp __length, _Compare __comp)
794 { return multiway_merge_4_variant<_GuardedIterator>
795 (__seqs_begin, __seqs_end, __target, __length, __comp); }
799 * @brief Switch for 4-way merging with __sentinels turned on.
801 * Note that 4-way merging is always stable!
803 template<typename _RAIterIterator,
805 typename _DifferenceTp,
807 struct __multiway_merge_4_variant_sentinel_switch<true, _RAIterIterator,
808 _RAIter3, _DifferenceTp,
812 operator()(_RAIterIterator __seqs_begin,
813 _RAIterIterator __seqs_end,
815 _DifferenceTp __length, _Compare __comp)
816 { return multiway_merge_4_variant<_UnguardedIterator>
817 (__seqs_begin, __seqs_end, __target, __length, __comp); }
821 * @brief Switch for k-way merging with __sentinels turned on.
823 template<bool __sentinels,
825 typename _RAIterIterator,
827 typename _DifferenceTp,
829 struct __multiway_merge_k_variant_sentinel_switch
832 operator()(_RAIterIterator __seqs_begin,
833 _RAIterIterator __seqs_end,
835 const typename std::iterator_traits<typename std::iterator_traits<
836 _RAIterIterator>::value_type::first_type>::value_type&
838 _DifferenceTp __length, _Compare __comp)
840 typedef typename std::iterator_traits<_RAIterIterator>
841 ::value_type::first_type
843 typedef typename std::iterator_traits<_RAIter1>::value_type
846 return multiway_merge_loser_tree_sentinel<
847 typename __gnu_cxx::__conditional_type<
848 _LoserTreeTraits<_ValueType>::_M_use_pointer,
849 _LoserTreePointerUnguarded<__stable, _ValueType, _Compare>,
850 _LoserTreeUnguarded<__stable, _ValueType, _Compare>
852 (__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp);
857 * @brief Switch for k-way merging with __sentinels turned off.
859 template<bool __stable,
860 typename _RAIterIterator,
862 typename _DifferenceTp,
864 struct __multiway_merge_k_variant_sentinel_switch<false, __stable,
865 _RAIterIterator, _RAIter3,
866 _DifferenceTp, _Compare>
869 operator()(_RAIterIterator __seqs_begin,
870 _RAIterIterator __seqs_end,
872 const typename std::iterator_traits<typename std::iterator_traits<
873 _RAIterIterator>::value_type::first_type>::value_type&
875 _DifferenceTp __length, _Compare __comp)
877 typedef typename std::iterator_traits<_RAIterIterator>
878 ::value_type::first_type
880 typedef typename std::iterator_traits<_RAIter1>::value_type
883 return multiway_merge_loser_tree<
884 typename __gnu_cxx::__conditional_type<
885 _LoserTreeTraits<_ValueType>::_M_use_pointer,
886 _LoserTreePointer<__stable, _ValueType, _Compare>,
887 _LoserTree<__stable, _ValueType, _Compare>
888 >::__type >(__seqs_begin, __seqs_end, __target, __length, __comp);
892 /** @brief Sequential multi-way merging switch.
894 * The _GLIBCXX_PARALLEL_DECISION is based on the branching factor and
896 * @param __seqs_begin Begin iterator of iterator pair input sequence.
897 * @param __seqs_end End iterator of iterator pair input sequence.
898 * @param __target Begin iterator of output sequence.
899 * @param __comp Comparator.
900 * @param __length Maximum length to merge, possibly larger than the
901 * number of elements available.
902 * @param __stable Stable merging incurs a performance penalty.
903 * @param __sentinel The sequences have __a __sentinel element.
904 * @return End iterator of output sequence. */
905 template<bool __stable,
907 typename _RAIterIterator,
909 typename _DifferenceTp,
912 __sequential_multiway_merge(_RAIterIterator __seqs_begin,
913 _RAIterIterator __seqs_end,
915 const typename std::iterator_traits<typename std::iterator_traits<
916 _RAIterIterator>::value_type::first_type>::value_type&
918 _DifferenceTp __length, _Compare __comp)
920 _GLIBCXX_CALL(__length)
922 typedef _DifferenceTp _DifferenceType;
923 typedef typename std::iterator_traits<_RAIterIterator>
924 ::value_type::first_type
926 typedef typename std::iterator_traits<_RAIter1>::value_type
929 #if _GLIBCXX_ASSERTIONS
930 for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
932 _GLIBCXX_PARALLEL_ASSERT(__is_sorted((*__s).first,
933 (*__s).second, __comp));
937 _DifferenceTp __total_length = 0;
938 for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
939 __total_length += _GLIBCXX_PARALLEL_LENGTH(*__s);
941 __length = std::min<_DifferenceTp>(__length, __total_length);
946 _RAIter3 __return_target = __target;
947 int __k = static_cast<int>(__seqs_end - __seqs_begin);
954 __return_target = std::copy(__seqs_begin[0].first,
955 __seqs_begin[0].first + __length,
957 __seqs_begin[0].first += __length;
960 __return_target = __merge_advance(__seqs_begin[0].first,
961 __seqs_begin[0].second,
962 __seqs_begin[1].first,
963 __seqs_begin[1].second,
964 __target, __length, __comp);
967 __return_target = __multiway_merge_3_variant_sentinel_switch
968 <__sentinels, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare>()
969 (__seqs_begin, __seqs_end, __target, __length, __comp);
972 __return_target = __multiway_merge_4_variant_sentinel_switch
973 <__sentinels, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare>()
974 (__seqs_begin, __seqs_end, __target, __length, __comp);
977 __return_target = __multiway_merge_k_variant_sentinel_switch
978 <__sentinels, __stable, _RAIterIterator, _RAIter3, _DifferenceTp,
980 (__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp);
983 #if _GLIBCXX_ASSERTIONS
984 _GLIBCXX_PARALLEL_ASSERT(
985 __is_sorted(__target, __target + __length, __comp));
988 return __return_target;
992 * @brief Stable sorting functor.
994 * Used to reduce code instanciation in multiway_merge_sampling_splitting.
996 template<bool __stable, class _RAIter, class _StrictWeakOrdering>
997 struct _SamplingSorter
1000 operator()(_RAIter __first, _RAIter __last, _StrictWeakOrdering __comp)
1001 { __gnu_sequential::stable_sort(__first, __last, __comp); }
1005 * @brief Non-__stable sorting functor.
1007 * Used to reduce code instantiation in multiway_merge_sampling_splitting.
1009 template<class _RAIter, class _StrictWeakOrdering>
1010 struct _SamplingSorter<false, _RAIter, _StrictWeakOrdering>
1013 operator()(_RAIter __first, _RAIter __last, _StrictWeakOrdering __comp)
1014 { __gnu_sequential::sort(__first, __last, __comp); }
1018 * @brief Sampling based splitting for parallel multiway-merge routine.
1020 template<bool __stable,
1021 typename _RAIterIterator,
1023 typename _DifferenceType>
1025 multiway_merge_sampling_splitting(_RAIterIterator __seqs_begin,
1026 _RAIterIterator __seqs_end,
1027 _DifferenceType __length,
1028 _DifferenceType __total_length,
1030 std::vector<std::pair<_DifferenceType, _DifferenceType> > *__pieces)
1032 typedef typename std::iterator_traits<_RAIterIterator>
1033 ::value_type::first_type
1035 typedef typename std::iterator_traits<_RAIter1>::value_type
1039 int __k = static_cast<int>(__seqs_end - __seqs_begin);
1041 int __num_threads = omp_get_num_threads();
1043 _DifferenceType __num_samples =
1044 __gnu_parallel::_Settings::get().merge_oversampling * __num_threads;
1046 _ValueType* __samples = static_cast<_ValueType*>
1047 (::operator new(sizeof(_ValueType) * __k * __num_samples));
1049 for (int __s = 0; __s < __k; ++__s)
1050 for (_DifferenceType __i = 0; __i < __num_samples; ++__i)
1052 _DifferenceType sample_index = static_cast<_DifferenceType>
1053 (_GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__s])
1054 * (double(__i + 1) / (__num_samples + 1))
1055 * (double(__length) / __total_length));
1056 new(&(__samples[__s * __num_samples + __i]))
1057 _ValueType(__seqs_begin[__s].first[sample_index]);
1060 // Sort stable or non-stable, depending on value of template parameter
1062 _SamplingSorter<__stable, _ValueType*, _Compare>()
1063 (__samples, __samples + (__num_samples * __k), __comp);
1065 for (int __slab = 0; __slab < __num_threads; ++__slab)
1066 // For each slab / processor.
1067 for (int __seq = 0; __seq < __k; ++__seq)
1069 // For each sequence.
1071 __pieces[__slab][__seq].first = std::upper_bound
1072 (__seqs_begin[__seq].first, __seqs_begin[__seq].second,
1073 __samples[__num_samples * __k * __slab / __num_threads],
1075 - __seqs_begin[__seq].first;
1077 // Absolute beginning.
1078 __pieces[__slab][__seq].first = 0;
1079 if ((__slab + 1) < __num_threads)
1080 __pieces[__slab][__seq].second = std::upper_bound
1081 (__seqs_begin[__seq].first, __seqs_begin[__seq].second,
1082 __samples[__num_samples * __k * (__slab + 1) / __num_threads],
1084 - __seqs_begin[__seq].first;
1087 __pieces[__slab][__seq].second =
1088 _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__seq]);
1090 ::operator delete(__samples);
1094 * @brief Exact splitting for parallel multiway-merge routine.
1096 * None of the passed sequences may be empty.
1098 template<bool __stable,
1099 typename _RAIterIterator,
1101 typename _DifferenceType>
1103 multiway_merge_exact_splitting(_RAIterIterator __seqs_begin,
1104 _RAIterIterator __seqs_end,
1105 _DifferenceType __length,
1106 _DifferenceType __total_length,
1108 std::vector<std::pair<_DifferenceType, _DifferenceType> > *__pieces)
1110 typedef typename std::iterator_traits<_RAIterIterator>
1111 ::value_type::first_type
1114 const bool __tight = (__total_length == __length);
1117 const int __k = static_cast<int>(__seqs_end - __seqs_begin);
1119 const int __num_threads = omp_get_num_threads();
1121 // (Settings::multiway_merge_splitting
1122 // == __gnu_parallel::_Settings::EXACT).
1123 std::vector<_RAIter1>* __offsets =
1124 new std::vector<_RAIter1>[__num_threads];
1125 std::vector<std::pair<_RAIter1, _RAIter1> > __se(__k);
1127 copy(__seqs_begin, __seqs_end, __se.begin());
1129 _DifferenceType* __borders =
1130 new _DifferenceType[__num_threads + 1];
1131 equally_split(__length, __num_threads, __borders);
1133 for (int __s = 0; __s < (__num_threads - 1); ++__s)
1135 __offsets[__s].resize(__k);
1136 multiseq_partition(__se.begin(), __se.end(), __borders[__s + 1],
1137 __offsets[__s].begin(), __comp);
1139 // Last one also needed and available.
1142 __offsets[__num_threads - 1].resize(__k);
1143 multiseq_partition(__se.begin(), __se.end(),
1144 _DifferenceType(__length),
1145 __offsets[__num_threads - 1].begin(),
1151 for (int __slab = 0; __slab < __num_threads; ++__slab)
1153 // For each slab / processor.
1154 for (int __seq = 0; __seq < __k; ++__seq)
1156 // For each sequence.
1159 // Absolute beginning.
1160 __pieces[__slab][__seq].first = 0;
1163 __pieces[__slab][__seq].first =
1164 __pieces[__slab - 1][__seq].second;
1165 if (!__tight || __slab < (__num_threads - 1))
1166 __pieces[__slab][__seq].second =
1167 __offsets[__slab][__seq] - __seqs_begin[__seq].first;
1170 // __slab == __num_threads - 1
1171 __pieces[__slab][__seq].second =
1172 _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__seq]);
1179 /** @brief Parallel multi-way merge routine.
1181 * The _GLIBCXX_PARALLEL_DECISION is based on the branching factor
1182 * and runtime settings.
1184 * Must not be called if the number of sequences is 1.
1186 * @param _Splitter functor to split input (either __exact or sampling based)
1188 * @param __seqs_begin Begin iterator of iterator pair input sequence.
1189 * @param __seqs_end End iterator of iterator pair input sequence.
1190 * @param __target Begin iterator of output sequence.
1191 * @param __comp Comparator.
1192 * @param __length Maximum length to merge, possibly larger than the
1193 * number of elements available.
1194 * @param __stable Stable merging incurs a performance penalty.
1195 * @param __sentinel Ignored.
1196 * @return End iterator of output sequence.
1198 template<bool __stable,
1200 typename _RAIterIterator,
1202 typename _DifferenceTp,
1206 parallel_multiway_merge(_RAIterIterator __seqs_begin,
1207 _RAIterIterator __seqs_end,
1209 _Splitter __splitter,
1210 _DifferenceTp __length,
1212 _ThreadIndex __num_threads)
1214 #if _GLIBCXX_ASSERTIONS
1215 _GLIBCXX_PARALLEL_ASSERT(__seqs_end - __seqs_begin > 1);
1218 _GLIBCXX_CALL(__length)
1220 typedef _DifferenceTp _DifferenceType;
1221 typedef typename std::iterator_traits<_RAIterIterator>
1222 ::value_type::first_type
1225 std::iterator_traits<_RAIter1>::value_type _ValueType;
1227 // Leave only non-empty sequences.
1228 typedef std::pair<_RAIter1, _RAIter1> seq_type;
1229 seq_type* __ne_seqs = new seq_type[__seqs_end - __seqs_begin];
1231 _DifferenceType __total_length = 0;
1232 for (_RAIterIterator __raii = __seqs_begin;
1233 __raii != __seqs_end; ++__raii)
1235 _DifferenceTp __seq_length = _GLIBCXX_PARALLEL_LENGTH(*__raii);
1236 if(__seq_length > 0)
1238 __total_length += __seq_length;
1239 __ne_seqs[__k++] = *__raii;
1243 _GLIBCXX_CALL(__total_length)
1245 __length = std::min<_DifferenceTp>(__length, __total_length);
1247 if (__total_length == 0 || __k == 0)
1253 std::vector<std::pair<_DifferenceType, _DifferenceType> >* __pieces;
1255 __num_threads = static_cast<_ThreadIndex>
1256 (std::min<_DifferenceType>(__num_threads, __total_length));
1258 # pragma omp parallel num_threads (__num_threads)
1262 __num_threads = omp_get_num_threads();
1263 // Thread __t will have to merge pieces[__iam][0..__k - 1]
1264 __pieces = new std::vector<
1265 std::pair<_DifferenceType, _DifferenceType> >[__num_threads];
1266 for (int __s = 0; __s < __num_threads; ++__s)
1267 __pieces[__s].resize(__k);
1269 _DifferenceType __num_samples =
1270 __gnu_parallel::_Settings::get().merge_oversampling
1273 __splitter(__ne_seqs, __ne_seqs + __k, __length, __total_length,
1277 _ThreadIndex __iam = omp_get_thread_num();
1279 _DifferenceType __target_position = 0;
1281 for (int __c = 0; __c < __k; ++__c)
1282 __target_position += __pieces[__iam][__c].first;
1284 seq_type* __chunks = new seq_type[__k];
1286 for (int __s = 0; __s < __k; ++__s)
1287 __chunks[__s] = std::make_pair(__ne_seqs[__s].first
1288 + __pieces[__iam][__s].first,
1289 __ne_seqs[__s].first
1290 + __pieces[__iam][__s].second);
1292 if(__length > __target_position)
1293 __sequential_multiway_merge<__stable, __sentinels>
1294 (__chunks, __chunks + __k, __target + __target_position,
1295 *(__seqs_begin->second), __length - __target_position, __comp);
1300 #if _GLIBCXX_ASSERTIONS
1301 _GLIBCXX_PARALLEL_ASSERT(
1302 __is_sorted(__target, __target + __length, __comp));
1306 // Update ends of sequences.
1307 for (_RAIterIterator __raii = __seqs_begin;
1308 __raii != __seqs_end; ++__raii)
1310 _DifferenceTp __length = _GLIBCXX_PARALLEL_LENGTH(*__raii);
1312 (*__raii).first += __pieces[__num_threads - 1][__k++].second;
1318 return __target + __length;
1322 * @brief Multiway Merge Frontend.
1324 * Merge the sequences specified by seqs_begin and __seqs_end into
1325 * __target. __seqs_begin and __seqs_end must point to a sequence of
1326 * pairs. These pairs must contain an iterator to the beginning
1327 * of a sequence in their first entry and an iterator the _M_end of
1328 * the same sequence in their second entry.
1330 * Ties are broken arbitrarily. See stable_multiway_merge for a variant
1331 * that breaks ties by sequence number but is slower.
1333 * The first entries of the pairs (i.e. the begin iterators) will be moved
1336 * The output sequence has to provide enough space for all elements
1337 * that are written to it.
1339 * This function will merge the input sequences:
1342 * - parallel, depending on the input size and Settings
1343 * - using sampling for splitting
1344 * - not using sentinels
1349 * int sequences[10][10];
1350 * for (int __i = 0; __i < 10; ++__i)
1351 * for (int __j = 0; __i < 10; ++__j)
1352 * sequences[__i][__j] = __j;
1355 * std::vector<std::pair<int*> > seqs;
1356 * for (int __i = 0; __i < 10; ++__i)
1357 * { seqs.push(std::make_pair<int*>(sequences[__i],
1358 * sequences[__i] + 10)) }
1360 * multiway_merge(seqs.begin(), seqs.end(), __target, std::less<int>(), 33);
1363 * @see stable_multiway_merge
1365 * @pre All input sequences must be sorted.
1366 * @pre Target must provide enough space to merge out length elements or
1367 * the number of elements in all sequences, whichever is smaller.
1369 * @post [__target, return __value) contains merged __elements from the
1371 * @post return __value - __target = min(__length, number of elements in all
1374 * @param _RAIterPairIterator iterator over sequence
1375 * of pairs of iterators
1376 * @param _RAIterOut iterator over target sequence
1377 * @param _DifferenceTp difference type for the sequence
1378 * @param _Compare strict weak ordering type to compare elements
1381 * @param __seqs_begin __begin of sequence __sequence
1382 * @param __seqs_end _M_end of sequence __sequence
1383 * @param __target target sequence to merge to.
1384 * @param __comp strict weak ordering to use for element comparison.
1385 * @param __length Maximum length to merge, possibly larger than the
1386 * number of elements available.
1388 * @return _M_end iterator of output sequence
1392 template<typename _RAIterPairIterator,
1393 typename _RAIterOut,
1394 typename _DifferenceTp,
1397 multiway_merge(_RAIterPairIterator __seqs_begin,
1398 _RAIterPairIterator __seqs_end,
1399 _RAIterOut __target,
1400 _DifferenceTp __length, _Compare __comp,
1401 __gnu_parallel::sequential_tag)
1403 typedef _DifferenceTp _DifferenceType;
1404 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1406 // catch special case: no sequences
1407 if (__seqs_begin == __seqs_end)
1410 // Execute multiway merge *sequentially*.
1411 return __sequential_multiway_merge
1412 </* __stable = */ false, /* __sentinels = */ false>
1413 (__seqs_begin, __seqs_end, __target,
1414 *(__seqs_begin->second), __length, __comp);
1418 template<typename _RAIterPairIterator,
1419 typename _RAIterOut,
1420 typename _DifferenceTp,
1423 multiway_merge(_RAIterPairIterator __seqs_begin,
1424 _RAIterPairIterator __seqs_end,
1425 _RAIterOut __target,
1426 _DifferenceTp __length, _Compare __comp,
1427 __gnu_parallel::exact_tag __tag)
1429 typedef _DifferenceTp _DifferenceType;
1430 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1432 // catch special case: no sequences
1433 if (__seqs_begin == __seqs_end)
1436 // Execute merge; maybe parallel, depending on the number of merged
1437 // elements and the number of sequences and global thresholds in
1439 if ((__seqs_end - __seqs_begin > 1)
1440 && _GLIBCXX_PARALLEL_CONDITION(
1441 ((__seqs_end - __seqs_begin) >=
1442 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1443 && ((_SequenceIndex)__length >=
1444 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1445 return parallel_multiway_merge
1446 </* __stable = */ false, /* __sentinels = */ false>
1447 (__seqs_begin, __seqs_end, __target,
1448 multiway_merge_exact_splitting</* __stable = */ false,
1449 typename std::iterator_traits<_RAIterPairIterator>
1450 ::value_type*, _Compare, _DifferenceTp>,
1451 static_cast<_DifferenceType>(__length), __comp,
1452 __tag.__get_num_threads());
1454 return __sequential_multiway_merge
1455 </* __stable = */ false, /* __sentinels = */ false>
1456 (__seqs_begin, __seqs_end, __target,
1457 *(__seqs_begin->second), __length, __comp);
1461 template<typename _RAIterPairIterator,
1462 typename _RAIterOut,
1463 typename _DifferenceTp,
1466 multiway_merge(_RAIterPairIterator __seqs_begin,
1467 _RAIterPairIterator __seqs_end,
1468 _RAIterOut __target,
1469 _DifferenceTp __length, _Compare __comp,
1470 __gnu_parallel::sampling_tag __tag)
1472 typedef _DifferenceTp _DifferenceType;
1473 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1475 // catch special case: no sequences
1476 if (__seqs_begin == __seqs_end)
1479 // Execute merge; maybe parallel, depending on the number of merged
1480 // elements and the number of sequences and global thresholds in
1482 if ((__seqs_end - __seqs_begin > 1)
1483 && _GLIBCXX_PARALLEL_CONDITION(
1484 ((__seqs_end - __seqs_begin) >=
1485 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1486 && ((_SequenceIndex)__length >=
1487 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1488 return parallel_multiway_merge
1489 </* __stable = */ false, /* __sentinels = */ false>
1490 (__seqs_begin, __seqs_end, __target,
1491 multiway_merge_exact_splitting</* __stable = */ false,
1492 typename std::iterator_traits<_RAIterPairIterator>
1493 ::value_type*, _Compare, _DifferenceTp>,
1494 static_cast<_DifferenceType>(__length), __comp,
1495 __tag.__get_num_threads());
1497 return __sequential_multiway_merge
1498 </* __stable = */ false, /* __sentinels = */ false>
1499 (__seqs_begin, __seqs_end, __target,
1500 *(__seqs_begin->second), __length, __comp);
1504 template<typename _RAIterPairIterator,
1505 typename _RAIterOut,
1506 typename _DifferenceTp,
1509 multiway_merge(_RAIterPairIterator __seqs_begin,
1510 _RAIterPairIterator __seqs_end,
1511 _RAIterOut __target,
1512 _DifferenceTp __length, _Compare __comp,
1513 parallel_tag __tag = parallel_tag(0))
1514 { return multiway_merge(__seqs_begin, __seqs_end, __target, __length,
1515 __comp, exact_tag(__tag.__get_num_threads())); }
1518 template<typename _RAIterPairIterator,
1519 typename _RAIterOut,
1520 typename _DifferenceTp,
1523 multiway_merge(_RAIterPairIterator __seqs_begin,
1524 _RAIterPairIterator __seqs_end,
1525 _RAIterOut __target,
1526 _DifferenceTp __length, _Compare __comp,
1527 default_parallel_tag __tag)
1528 { return multiway_merge(__seqs_begin, __seqs_end, __target, __length,
1529 __comp, exact_tag(__tag.__get_num_threads())); }
1531 // stable_multiway_merge
1533 template<typename _RAIterPairIterator,
1534 typename _RAIterOut,
1535 typename _DifferenceTp,
1538 stable_multiway_merge(_RAIterPairIterator __seqs_begin,
1539 _RAIterPairIterator __seqs_end,
1540 _RAIterOut __target,
1541 _DifferenceTp __length, _Compare __comp,
1542 __gnu_parallel::sequential_tag)
1544 typedef _DifferenceTp _DifferenceType;
1545 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1547 // catch special case: no sequences
1548 if (__seqs_begin == __seqs_end)
1551 // Execute multiway merge *sequentially*.
1552 return __sequential_multiway_merge
1553 </* __stable = */ true, /* __sentinels = */ false>
1554 (__seqs_begin, __seqs_end, __target,
1555 *(__seqs_begin->second), __length, __comp);
1559 template<typename _RAIterPairIterator,
1560 typename _RAIterOut,
1561 typename _DifferenceTp,
1564 stable_multiway_merge(_RAIterPairIterator __seqs_begin,
1565 _RAIterPairIterator __seqs_end,
1566 _RAIterOut __target,
1567 _DifferenceTp __length, _Compare __comp,
1568 __gnu_parallel::exact_tag __tag)
1570 typedef _DifferenceTp _DifferenceType;
1571 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1573 // catch special case: no sequences
1574 if (__seqs_begin == __seqs_end)
1577 // Execute merge; maybe parallel, depending on the number of merged
1578 // elements and the number of sequences and global thresholds in
1580 if ((__seqs_end - __seqs_begin > 1)
1581 && _GLIBCXX_PARALLEL_CONDITION(
1582 ((__seqs_end - __seqs_begin) >=
1583 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1584 && ((_SequenceIndex)__length >=
1585 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1586 return parallel_multiway_merge
1587 </* __stable = */ true, /* __sentinels = */ false>
1588 (__seqs_begin, __seqs_end, __target,
1589 multiway_merge_exact_splitting</* __stable = */ true,
1590 typename std::iterator_traits<_RAIterPairIterator>
1591 ::value_type*, _Compare, _DifferenceTp>,
1592 static_cast<_DifferenceType>(__length), __comp,
1593 __tag.__get_num_threads());
1595 return __sequential_multiway_merge
1596 </* __stable = */ true, /* __sentinels = */ false>
1597 (__seqs_begin, __seqs_end, __target,
1598 *(__seqs_begin->second), __length, __comp);
1602 template<typename _RAIterPairIterator,
1603 typename _RAIterOut,
1604 typename _DifferenceTp,
1607 stable_multiway_merge(_RAIterPairIterator __seqs_begin,
1608 _RAIterPairIterator __seqs_end,
1609 _RAIterOut __target,
1610 _DifferenceTp __length, _Compare __comp,
1613 typedef _DifferenceTp _DifferenceType;
1614 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1616 // catch special case: no sequences
1617 if (__seqs_begin == __seqs_end)
1620 // Execute merge; maybe parallel, depending on the number of merged
1621 // elements and the number of sequences and global thresholds in
1623 if ((__seqs_end - __seqs_begin > 1)
1624 && _GLIBCXX_PARALLEL_CONDITION(
1625 ((__seqs_end - __seqs_begin) >=
1626 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1627 && ((_SequenceIndex)__length >=
1628 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1629 return parallel_multiway_merge
1630 </* __stable = */ true, /* __sentinels = */ false>
1631 (__seqs_begin, __seqs_end, __target,
1632 multiway_merge_sampling_splitting</* __stable = */ true,
1633 typename std::iterator_traits<_RAIterPairIterator>
1634 ::value_type*, _Compare, _DifferenceTp>,
1635 static_cast<_DifferenceType>(__length), __comp,
1636 __tag.__get_num_threads());
1638 return __sequential_multiway_merge
1639 </* __stable = */ true, /* __sentinels = */ false>
1640 (__seqs_begin, __seqs_end, __target,
1641 *(__seqs_begin->second), __length, __comp);
1645 template<typename _RAIterPairIterator,
1646 typename _RAIterOut,
1647 typename _DifferenceTp,
1650 stable_multiway_merge(_RAIterPairIterator __seqs_begin,
1651 _RAIterPairIterator __seqs_end,
1652 _RAIterOut __target,
1653 _DifferenceTp __length, _Compare __comp,
1654 parallel_tag __tag = parallel_tag(0))
1656 return stable_multiway_merge
1657 (__seqs_begin, __seqs_end, __target, __length, __comp,
1658 exact_tag(__tag.__get_num_threads()));
1662 template<typename _RAIterPairIterator,
1663 typename _RAIterOut,
1664 typename _DifferenceTp,
1667 stable_multiway_merge(_RAIterPairIterator __seqs_begin,
1668 _RAIterPairIterator __seqs_end,
1669 _RAIterOut __target,
1670 _DifferenceTp __length, _Compare __comp,
1671 default_parallel_tag __tag)
1673 return stable_multiway_merge
1674 (__seqs_begin, __seqs_end, __target, __length, __comp,
1675 exact_tag(__tag.__get_num_threads()));
1679 * @brief Multiway Merge Frontend.
1681 * Merge the sequences specified by seqs_begin and __seqs_end into
1682 * __target. __seqs_begin and __seqs_end must point to a sequence of
1683 * pairs. These pairs must contain an iterator to the beginning
1684 * of a sequence in their first entry and an iterator the _M_end of
1685 * the same sequence in their second entry.
1687 * Ties are broken arbitrarily. See stable_multiway_merge for a variant
1688 * that breaks ties by sequence number but is slower.
1690 * The first entries of the pairs (i.e. the begin iterators) will be moved
1691 * forward accordingly.
1693 * The output sequence has to provide enough space for all elements
1694 * that are written to it.
1696 * This function will merge the input sequences:
1699 * - parallel, depending on the input size and Settings
1700 * - using sampling for splitting
1703 * You have to take care that the element the _M_end iterator points to is
1704 * readable and contains a value that is greater than any other non-sentinel
1705 * value in all sequences.
1710 * int sequences[10][11];
1711 * for (int __i = 0; __i < 10; ++__i)
1712 * for (int __j = 0; __i < 11; ++__j)
1713 * sequences[__i][__j] = __j; // __last one is sentinel!
1716 * std::vector<std::pair<int*> > seqs;
1717 * for (int __i = 0; __i < 10; ++__i)
1718 * { seqs.push(std::make_pair<int*>(sequences[__i],
1719 * sequences[__i] + 10)) }
1721 * multiway_merge(seqs.begin(), seqs.end(), __target, std::less<int>(), 33);
1724 * @pre All input sequences must be sorted.
1725 * @pre Target must provide enough space to merge out length elements or
1726 * the number of elements in all sequences, whichever is smaller.
1727 * @pre For each @c __i, @c __seqs_begin[__i].second must be the end
1728 * marker of the sequence, but also reference the one more __sentinel
1731 * @post [__target, return __value) contains merged __elements from the
1733 * @post return __value - __target = min(__length, number of elements in all
1736 * @see stable_multiway_merge_sentinels
1738 * @param _RAIterPairIterator iterator over sequence
1739 * of pairs of iterators
1740 * @param _RAIterOut iterator over target sequence
1741 * @param _DifferenceTp difference type for the sequence
1742 * @param _Compare strict weak ordering type to compare elements
1745 * @param __seqs_begin __begin of sequence __sequence
1746 * @param __seqs_end _M_end of sequence __sequence
1747 * @param __target target sequence to merge to.
1748 * @param __comp strict weak ordering to use for element comparison.
1749 * @param __length Maximum length to merge, possibly larger than the
1750 * number of elements available.
1752 * @return _M_end iterator of output sequence
1754 // multiway_merge_sentinels
1756 template<typename _RAIterPairIterator,
1757 typename _RAIterOut,
1758 typename _DifferenceTp,
1761 multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1762 _RAIterPairIterator __seqs_end,
1763 _RAIterOut __target,
1764 _DifferenceTp __length, _Compare __comp,
1765 __gnu_parallel::sequential_tag)
1767 typedef _DifferenceTp _DifferenceType;
1768 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1770 // catch special case: no sequences
1771 if (__seqs_begin == __seqs_end)
1774 // Execute multiway merge *sequentially*.
1775 return __sequential_multiway_merge
1776 </* __stable = */ false, /* __sentinels = */ true>
1777 (__seqs_begin, __seqs_end,
1778 __target, *(__seqs_begin->second), __length, __comp);
1782 template<typename _RAIterPairIterator,
1783 typename _RAIterOut,
1784 typename _DifferenceTp,
1787 multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1788 _RAIterPairIterator __seqs_end,
1789 _RAIterOut __target,
1790 _DifferenceTp __length, _Compare __comp,
1791 __gnu_parallel::exact_tag __tag)
1793 typedef _DifferenceTp _DifferenceType;
1794 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1796 // catch special case: no sequences
1797 if (__seqs_begin == __seqs_end)
1800 // Execute merge; maybe parallel, depending on the number of merged
1801 // elements and the number of sequences and global thresholds in
1803 if ((__seqs_end - __seqs_begin > 1)
1804 && _GLIBCXX_PARALLEL_CONDITION(
1805 ((__seqs_end - __seqs_begin) >=
1806 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1807 && ((_SequenceIndex)__length >=
1808 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1809 return parallel_multiway_merge
1810 </* __stable = */ false, /* __sentinels = */ true>
1811 (__seqs_begin, __seqs_end, __target,
1812 multiway_merge_exact_splitting</* __stable = */ false,
1813 typename std::iterator_traits<_RAIterPairIterator>
1814 ::value_type*, _Compare, _DifferenceTp>,
1815 static_cast<_DifferenceType>(__length), __comp,
1816 __tag.__get_num_threads());
1818 return __sequential_multiway_merge
1819 </* __stable = */ false, /* __sentinels = */ true>
1820 (__seqs_begin, __seqs_end, __target,
1821 *(__seqs_begin->second), __length, __comp);
1825 template<typename _RAIterPairIterator,
1826 typename _RAIterOut,
1827 typename _DifferenceTp,
1830 multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1831 _RAIterPairIterator __seqs_end,
1832 _RAIterOut __target,
1833 _DifferenceTp __length, _Compare __comp,
1836 typedef _DifferenceTp _DifferenceType;
1837 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1839 // catch special case: no sequences
1840 if (__seqs_begin == __seqs_end)
1843 // Execute merge; maybe parallel, depending on the number of merged
1844 // elements and the number of sequences and global thresholds in
1846 if ((__seqs_end - __seqs_begin > 1)
1847 && _GLIBCXX_PARALLEL_CONDITION(
1848 ((__seqs_end - __seqs_begin) >=
1849 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1850 && ((_SequenceIndex)__length >=
1851 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1852 return parallel_multiway_merge
1853 </* __stable = */ false, /* __sentinels = */ true>
1854 (__seqs_begin, __seqs_end, __target,
1855 multiway_merge_sampling_splitting</* __stable = */ false,
1856 typename std::iterator_traits<_RAIterPairIterator>
1857 ::value_type*, _Compare, _DifferenceTp>,
1858 static_cast<_DifferenceType>(__length), __comp,
1859 __tag.__get_num_threads());
1861 return __sequential_multiway_merge
1862 </* __stable = */false, /* __sentinels = */ true>(
1863 __seqs_begin, __seqs_end, __target,
1864 *(__seqs_begin->second), __length, __comp);
1868 template<typename _RAIterPairIterator,
1869 typename _RAIterOut,
1870 typename _DifferenceTp,
1873 multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1874 _RAIterPairIterator __seqs_end,
1875 _RAIterOut __target,
1876 _DifferenceTp __length, _Compare __comp,
1877 parallel_tag __tag = parallel_tag(0))
1879 return multiway_merge_sentinels
1880 (__seqs_begin, __seqs_end, __target, __length, __comp,
1881 exact_tag(__tag.__get_num_threads()));
1885 template<typename _RAIterPairIterator,
1886 typename _RAIterOut,
1887 typename _DifferenceTp,
1890 multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1891 _RAIterPairIterator __seqs_end,
1892 _RAIterOut __target,
1893 _DifferenceTp __length, _Compare __comp,
1894 default_parallel_tag __tag)
1896 return multiway_merge_sentinels
1897 (__seqs_begin, __seqs_end, __target, __length, __comp,
1898 exact_tag(__tag.__get_num_threads()));
1901 // stable_multiway_merge_sentinels
1903 template<typename _RAIterPairIterator,
1904 typename _RAIterOut,
1905 typename _DifferenceTp,
1908 stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1909 _RAIterPairIterator __seqs_end,
1910 _RAIterOut __target,
1911 _DifferenceTp __length, _Compare __comp,
1912 __gnu_parallel::sequential_tag)
1914 typedef _DifferenceTp _DifferenceType;
1915 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1917 // catch special case: no sequences
1918 if (__seqs_begin == __seqs_end)
1921 // Execute multiway merge *sequentially*.
1922 return __sequential_multiway_merge
1923 </* __stable = */ true, /* __sentinels = */ true>
1924 (__seqs_begin, __seqs_end, __target,
1925 *(__seqs_begin->second), __length, __comp);
1929 template<typename _RAIterPairIterator,
1930 typename _RAIterOut,
1931 typename _DifferenceTp,
1934 stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1935 _RAIterPairIterator __seqs_end,
1936 _RAIterOut __target,
1937 _DifferenceTp __length, _Compare __comp,
1938 __gnu_parallel::exact_tag __tag)
1940 typedef _DifferenceTp _DifferenceType;
1941 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1943 // catch special case: no sequences
1944 if (__seqs_begin == __seqs_end)
1947 // Execute merge; maybe parallel, depending on the number of merged
1948 // elements and the number of sequences and global thresholds in
1950 if ((__seqs_end - __seqs_begin > 1)
1951 && _GLIBCXX_PARALLEL_CONDITION(
1952 ((__seqs_end - __seqs_begin) >=
1953 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1954 && ((_SequenceIndex)__length >=
1955 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1956 return parallel_multiway_merge
1957 </* __stable = */ true, /* __sentinels = */ true>
1958 (__seqs_begin, __seqs_end, __target,
1959 multiway_merge_exact_splitting</* __stable = */ true,
1960 typename std::iterator_traits<_RAIterPairIterator>
1961 ::value_type*, _Compare, _DifferenceTp>,
1962 static_cast<_DifferenceType>(__length), __comp,
1963 __tag.__get_num_threads());
1965 return __sequential_multiway_merge
1966 </* __stable = */ true, /* __sentinels = */ true>
1967 (__seqs_begin, __seqs_end, __target,
1968 *(__seqs_begin->second), __length, __comp);
1972 template<typename _RAIterPairIterator,
1973 typename _RAIterOut,
1974 typename _DifferenceTp,
1977 stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1978 _RAIterPairIterator __seqs_end,
1979 _RAIterOut __target,
1980 _DifferenceTp __length,
1984 typedef _DifferenceTp _DifferenceType;
1985 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1987 // catch special case: no sequences
1988 if (__seqs_begin == __seqs_end)
1991 // Execute merge; maybe parallel, depending on the number of merged
1992 // elements and the number of sequences and global thresholds in
1994 if ((__seqs_end - __seqs_begin > 1)
1995 && _GLIBCXX_PARALLEL_CONDITION(
1996 ((__seqs_end - __seqs_begin) >=
1997 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1998 && ((_SequenceIndex)__length >=
1999 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
2000 return parallel_multiway_merge
2001 </* __stable = */ true, /* __sentinels = */ true>
2002 (__seqs_begin, __seqs_end, __target,
2003 multiway_merge_sampling_splitting</* __stable = */ true,
2004 typename std::iterator_traits<_RAIterPairIterator>
2005 ::value_type*, _Compare, _DifferenceTp>,
2006 static_cast<_DifferenceType>(__length), __comp,
2007 __tag.__get_num_threads());
2009 return __sequential_multiway_merge
2010 </* __stable = */ true, /* __sentinels = */ true>
2011 (__seqs_begin, __seqs_end, __target,
2012 *(__seqs_begin->second), __length, __comp);
2016 template<typename _RAIterPairIterator,
2017 typename _RAIterOut,
2018 typename _DifferenceTp,
2021 stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
2022 _RAIterPairIterator __seqs_end,
2023 _RAIterOut __target,
2024 _DifferenceTp __length,
2026 parallel_tag __tag = parallel_tag(0))
2028 return stable_multiway_merge_sentinels
2029 (__seqs_begin, __seqs_end, __target, __length, __comp,
2030 exact_tag(__tag.__get_num_threads()));
2034 template<typename _RAIterPairIterator,
2035 typename _RAIterOut,
2036 typename _DifferenceTp,
2039 stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
2040 _RAIterPairIterator __seqs_end,
2041 _RAIterOut __target,
2042 _DifferenceTp __length, _Compare __comp,
2043 default_parallel_tag __tag)
2045 return stable_multiway_merge_sentinels
2046 (__seqs_begin, __seqs_end, __target, __length, __comp,
2047 exact_tag(__tag.__get_num_threads()));
2049 }; // namespace __gnu_parallel
2051 #endif /* _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H */