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
58 // Announce guarded and unguarded iterator.
60 template<typename RandomAccessIterator
, typename Comparator
>
61 class guarded_iterator
;
63 // Making the arguments const references seems to dangerous,
64 // the user-defined comparator might not be const.
65 template<typename RandomAccessIterator
, typename Comparator
>
67 operator<(guarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
68 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
70 template<typename RandomAccessIterator
, typename Comparator
>
72 operator<=(guarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
73 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
75 /** @brief Iterator wrapper supporting an implicit supremum at the end
76 * of the sequence, dominating all comparisons.
78 * The implicit supremum comes with a performance cost.
80 * Deriving from RandomAccessIterator is not possible since
81 * RandomAccessIterator need not be a class.
83 template<typename RandomAccessIterator
, typename Comparator
>
84 class guarded_iterator
87 /** @brief Current iterator position. */
88 RandomAccessIterator current
;
90 /** @brief End iterator of the sequence. */
91 RandomAccessIterator end
;
93 /** @brief Comparator. */
97 /** @brief Constructor. Sets iterator to beginning of sequence.
98 * @param begin Begin iterator of sequence.
99 * @param end End iterator of sequence.
100 * @param comp Comparator provided for associated overloaded
101 * compare operators. */
102 guarded_iterator(RandomAccessIterator begin
,
103 RandomAccessIterator end
, Comparator
& comp
)
104 : current(begin
), end(end
), comp(comp
)
107 /** @brief Pre-increment operator.
109 guarded_iterator
<RandomAccessIterator
, Comparator
>&
116 /** @brief Dereference operator.
117 * @return Referenced element. */
118 typename
std::iterator_traits
<RandomAccessIterator
>::value_type
&
122 /** @brief Convert to wrapped iterator.
123 * @return Wrapped iterator. */
124 operator RandomAccessIterator()
128 operator< <RandomAccessIterator
, Comparator
>(
129 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
130 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
133 operator<= <RandomAccessIterator
, Comparator
>(
134 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
135 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
138 /** @brief Compare two elements referenced by guarded iterators.
139 * @param bi1 First iterator.
140 * @param bi2 Second iterator.
141 * @return @c True if less. */
142 template<typename RandomAccessIterator
, typename Comparator
>
144 operator<(guarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
145 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
)
147 if (bi1
.current
== bi1
.end
) //bi1 is sup
148 return bi2
.current
== bi2
.end
; //bi2 is not sup
149 if (bi2
.current
== bi2
.end
) //bi2 is sup
151 return (bi1
.comp
)(*bi1
, *bi2
); //normal compare
154 /** @brief Compare two elements referenced by guarded iterators.
155 * @param bi1 First iterator.
156 * @param bi2 Second iterator.
157 * @return @c True if less equal. */
158 template<typename RandomAccessIterator
, typename Comparator
>
160 operator<=(guarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
161 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
)
163 if (bi2
.current
== bi2
.end
) //bi1 is sup
164 return bi1
.current
!= bi1
.end
; //bi2 is not sup
165 if (bi1
.current
== bi1
.end
) //bi2 is sup
167 return !(bi1
.comp
)(*bi2
, *bi1
); //normal compare
170 template<typename RandomAccessIterator
, typename Comparator
>
171 class unguarded_iterator
;
173 template<typename RandomAccessIterator
, typename Comparator
>
175 operator<(unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
176 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
178 template<typename RandomAccessIterator
, typename Comparator
>
180 operator<=(unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
181 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
183 template<typename RandomAccessIterator
, typename Comparator
>
184 class unguarded_iterator
187 /** @brief Current iterator position. */
188 RandomAccessIterator current
;
189 /** @brief Comparator. */
190 mutable Comparator
& comp
;
193 /** @brief Constructor. Sets iterator to beginning of sequence.
194 * @param begin Begin iterator of sequence.
195 * @param end Unused, only for compatibility.
196 * @param comp Unused, only for compatibility. */
197 unguarded_iterator(RandomAccessIterator begin
,
198 RandomAccessIterator end
, Comparator
& comp
)
199 : current(begin
), comp(comp
)
202 /** @brief Pre-increment operator.
204 unguarded_iterator
<RandomAccessIterator
, Comparator
>&
211 /** @brief Dereference operator.
212 * @return Referenced element. */
213 typename
std::iterator_traits
<RandomAccessIterator
>::value_type
&
217 /** @brief Convert to wrapped iterator.
218 * @return Wrapped iterator. */
219 operator RandomAccessIterator()
223 operator< <RandomAccessIterator
, Comparator
>(
224 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
225 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
228 operator<= <RandomAccessIterator
, Comparator
>(
229 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
230 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
233 /** @brief Compare two elements referenced by unguarded iterators.
234 * @param bi1 First iterator.
235 * @param bi2 Second iterator.
236 * @return @c True if less. */
237 template<typename RandomAccessIterator
, typename Comparator
>
239 operator<(unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
240 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
)
243 return (bi1
.comp
)(*bi1
, *bi2
);
246 /** @brief Compare two elements referenced by unguarded iterators.
247 * @param bi1 First iterator.
248 * @param bi2 Second iterator.
249 * @return @c True if less equal. */
250 template<typename RandomAccessIterator
, typename Comparator
>
252 operator<=(unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
253 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
)
256 return !(bi1
.comp
)(*bi2
, *bi1
);
259 /** @brief Highly efficient 3-way merging procedure.
261 * Merging is done with the algorithm implementation described by Peter
262 * Sanders. Basically, the idea is to minimize the number of necessary
263 * comparison after merging out an element. The implementation trick
264 * that makes this fast is that the order of the sequences is stored
265 * in the instruction pointer (translated into labels in C++).
267 * This works well for merging up to 4 sequences.
269 * Note that making the merging stable does <em>not</em> come at a
272 * Whether the merging is done guarded or unguarded is selected by the
273 * used iterator class.
275 * @param seqs_begin Begin iterator of iterator pair input sequence.
276 * @param seqs_end End iterator of iterator pair input sequence.
277 * @param target Begin iterator out output sequence.
278 * @param comp Comparator.
279 * @param length Maximum length to merge, less equal than the
280 * total number of elements available.
282 * @return End iterator of output sequence.
284 template<template<typename RAI
, typename C
> class iterator
,
285 typename RandomAccessIteratorIterator
,
286 typename RandomAccessIterator3
,
287 typename _DifferenceTp
,
289 RandomAccessIterator3
290 multiway_merge_3_variant(
291 RandomAccessIteratorIterator seqs_begin
,
292 RandomAccessIteratorIterator seqs_end
,
293 RandomAccessIterator3 target
,
294 _DifferenceTp length
, Comparator comp
)
296 _GLIBCXX_CALL(length
);
298 typedef _DifferenceTp difference_type
;
300 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
301 ::value_type::first_type
302 RandomAccessIterator1
;
303 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
309 #if _GLIBCXX_ASSERTIONS
310 _DifferenceTp orig_length
= length
;
313 iterator
<RandomAccessIterator1
, Comparator
>
314 seq0(seqs_begin
[0].first
, seqs_begin
[0].second
, comp
),
315 seq1(seqs_begin
[1].first
, seqs_begin
[1].second
, comp
),
316 seq2(seqs_begin
[2].first
, seqs_begin
[2].second
, comp
);
340 #define _GLIBCXX_PARALLEL_MERGE_3_CASE(a,b,c,c0,c1) \
342 *target = *seq ## a; \
346 if (length == 0) goto finish; \
347 if (seq ## a c0 seq ## b) goto s ## a ## b ## c; \
348 if (seq ## a c1 seq ## c) goto s ## b ## a ## c; \
349 goto s ## b ## c ## a;
351 _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 1, 2, <=, <=);
352 _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 2, 0, <=, < );
353 _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 0, 1, < , < );
354 _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 0, 2, < , <=);
355 _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 2, 1, <=, <=);
356 _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 1, 0, < , < );
358 #undef _GLIBCXX_PARALLEL_MERGE_3_CASE
363 #if _GLIBCXX_ASSERTIONS
364 _GLIBCXX_PARALLEL_ASSERT(
365 ((RandomAccessIterator1
)seq0
- seqs_begin
[0].first
) +
366 ((RandomAccessIterator1
)seq1
- seqs_begin
[1].first
) +
367 ((RandomAccessIterator1
)seq2
- seqs_begin
[2].first
)
371 seqs_begin
[0].first
= seq0
;
372 seqs_begin
[1].first
= seq1
;
373 seqs_begin
[2].first
= seq2
;
379 * @brief Highly efficient 4-way merging procedure.
381 * Merging is done with the algorithm implementation described by Peter
382 * Sanders. Basically, the idea is to minimize the number of necessary
383 * comparison after merging out an element. The implementation trick
384 * that makes this fast is that the order of the sequences is stored
385 * in the instruction pointer (translated into goto labels in C++).
387 * This works well for merging up to 4 sequences.
389 * Note that making the merging stable does <em>not</em> come at a
392 * Whether the merging is done guarded or unguarded is selected by the
393 * used iterator class.
395 * @param seqs_begin Begin iterator of iterator pair input sequence.
396 * @param seqs_end End iterator of iterator pair input sequence.
397 * @param target Begin iterator out output sequence.
398 * @param comp Comparator.
399 * @param length Maximum length to merge, less equal than the
400 * total number of elements available.
402 * @return End iterator of output sequence.
404 template<template<typename RAI
, typename C
> class iterator
,
405 typename RandomAccessIteratorIterator
,
406 typename RandomAccessIterator3
,
407 typename _DifferenceTp
,
409 RandomAccessIterator3
410 multiway_merge_4_variant(RandomAccessIteratorIterator seqs_begin
,
411 RandomAccessIteratorIterator seqs_end
,
412 RandomAccessIterator3 target
,
413 _DifferenceTp length
, Comparator comp
)
415 _GLIBCXX_CALL(length
);
416 typedef _DifferenceTp difference_type
;
418 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
419 ::value_type::first_type
420 RandomAccessIterator1
;
421 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
424 iterator
<RandomAccessIterator1
, Comparator
>
425 seq0(seqs_begin
[0].first
, seqs_begin
[0].second
, comp
),
426 seq1(seqs_begin
[1].first
, seqs_begin
[1].second
, comp
),
427 seq2(seqs_begin
[2].first
, seqs_begin
[2].second
, comp
),
428 seq3(seqs_begin
[3].first
, seqs_begin
[3].second
, comp
);
430 #define _GLIBCXX_PARALLEL_DECISION(a,b,c,d) { \
431 if (seq ## d < seq ## a) goto s ## d ## a ## b ## c; \
432 if (seq ## d < seq ## b) goto s ## a ## d ## b ## c; \
433 if (seq ## d < seq ## c) goto s ## a ## b ## d ## c; \
434 goto s ## a ## b ## c ## d; }
439 _GLIBCXX_PARALLEL_DECISION(0,1,2,3)
442 _GLIBCXX_PARALLEL_DECISION(2,0,1,3)
444 _GLIBCXX_PARALLEL_DECISION(0,2,1,3)
451 _GLIBCXX_PARALLEL_DECISION(1,0,2,3)
453 _GLIBCXX_PARALLEL_DECISION(1,2,0,3)
456 _GLIBCXX_PARALLEL_DECISION(2,1,0,3)
459 #define _GLIBCXX_PARALLEL_MERGE_4_CASE(a,b,c,d,c0,c1,c2) \
460 s ## a ## b ## c ## d: \
461 if (length == 0) goto finish; \
462 *target = *seq ## a; \
466 if (seq ## a c0 seq ## b) goto s ## a ## b ## c ## d; \
467 if (seq ## a c1 seq ## c) goto s ## b ## a ## c ## d; \
468 if (seq ## a c2 seq ## d) goto s ## b ## c ## a ## d; \
469 goto s ## b ## c ## d ## a;
471 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 2, 3, <=, <=, <=);
472 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 3, 2, <=, <=, <=);
473 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 1, 3, <=, <=, <=);
474 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 3, 1, <=, <=, <=);
475 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 1, 2, <=, <=, <=);
476 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 2, 1, <=, <=, <=);
477 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 2, 3, < , <=, <=);
478 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 3, 2, < , <=, <=);
479 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 0, 3, <=, < , <=);
480 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 3, 0, <=, <=, < );
481 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 0, 2, <=, < , <=);
482 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 2, 0, <=, <=, < );
483 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 1, 3, < , < , <=);
484 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 3, 1, < , <=, < );
485 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 0, 3, < , < , <=);
486 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 3, 0, < , <=, < );
487 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 0, 1, <=, < , < );
488 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 1, 0, <=, < , < );
489 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 1, 2, < , < , < );
490 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 2, 1, < , < , < );
491 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 0, 2, < , < , < );
492 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 2, 0, < , < , < );
493 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 0, 1, < , < , < );
494 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 1, 0, < , < , < );
496 #undef _GLIBCXX_PARALLEL_MERGE_4_CASE
497 #undef _GLIBCXX_PARALLEL_DECISION
502 seqs_begin
[0].first
= seq0
;
503 seqs_begin
[1].first
= seq1
;
504 seqs_begin
[2].first
= seq2
;
505 seqs_begin
[3].first
= seq3
;
510 /** @brief Multi-way merging procedure for a high branching factor,
513 * This merging variant uses a LoserTree class as selected by <tt>LT</tt>.
515 * Stability is selected through the used LoserTree class <tt>LT</tt>.
517 * At least one non-empty sequence is required.
519 * @param seqs_begin Begin iterator of iterator pair input sequence.
520 * @param seqs_end End iterator of iterator pair input sequence.
521 * @param target Begin iterator out output sequence.
522 * @param comp Comparator.
523 * @param length Maximum length to merge, less equal than the
524 * total number of elements available.
526 * @return End iterator of output sequence.
528 template<typename LT
,
529 typename RandomAccessIteratorIterator
,
530 typename RandomAccessIterator3
,
531 typename _DifferenceTp
,
533 RandomAccessIterator3
534 multiway_merge_loser_tree(RandomAccessIteratorIterator seqs_begin
,
535 RandomAccessIteratorIterator seqs_end
,
536 RandomAccessIterator3 target
,
537 _DifferenceTp length
, Comparator comp
)
539 _GLIBCXX_CALL(length
)
541 typedef _DifferenceTp difference_type
;
542 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
543 ::value_type::first_type
544 RandomAccessIterator1
;
545 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
548 int k
= static_cast<int>(seqs_end
- seqs_begin
);
552 // Default value for potentially non-default-constructible types.
553 value_type
* arbitrary_element
= NULL
;
555 for (int t
= 0; t
< k
; ++t
)
557 if(arbitrary_element
== NULL
558 && _GLIBCXX_PARALLEL_LENGTH(seqs_begin
[t
]) > 0)
559 arbitrary_element
= &(*seqs_begin
[t
].first
);
562 for (int t
= 0; t
< k
; ++t
)
564 if (seqs_begin
[t
].first
== seqs_begin
[t
].second
)
565 lt
.insert_start(*arbitrary_element
, t
, true);
567 lt
.insert_start(*seqs_begin
[t
].first
, t
, false);
574 for (difference_type i
= 0; i
< length
; ++i
)
577 source
= lt
.get_min_source();
579 *(target
++) = *(seqs_begin
[source
].first
++);
582 if (seqs_begin
[source
].first
== seqs_begin
[source
].second
)
583 lt
.delete_min_insert(*arbitrary_element
, true);
585 // Replace from same source.
586 lt
.delete_min_insert(*seqs_begin
[source
].first
, false);
592 /** @brief Multi-way merging procedure for a high branching factor,
595 * Merging is done using the LoserTree class <tt>LT</tt>.
597 * Stability is selected by the used LoserTrees.
599 * @pre No input will run out of elements during the merge.
601 * @param seqs_begin Begin iterator of iterator pair input sequence.
602 * @param seqs_end End iterator of iterator pair input sequence.
603 * @param target Begin iterator out output sequence.
604 * @param comp Comparator.
605 * @param length Maximum length to merge, less equal than the
606 * total number of elements available.
608 * @return End iterator of output sequence.
610 template<typename LT
,
611 typename RandomAccessIteratorIterator
,
612 typename RandomAccessIterator3
,
613 typename _DifferenceTp
, typename Comparator
>
614 RandomAccessIterator3
615 multiway_merge_loser_tree_unguarded(
616 RandomAccessIteratorIterator seqs_begin
,
617 RandomAccessIteratorIterator seqs_end
,
618 RandomAccessIterator3 target
,
619 const typename
std::iterator_traits
<typename
std::iterator_traits
<
620 RandomAccessIteratorIterator
>::value_type::first_type
>::value_type
&
622 _DifferenceTp length
,
625 _GLIBCXX_CALL(length
)
626 typedef _DifferenceTp difference_type
;
628 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
629 ::value_type::first_type
630 RandomAccessIterator1
;
631 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
634 int k
= seqs_end
- seqs_begin
;
636 LT
lt(k
, sentinel
, comp
);
638 for (int t
= 0; t
< k
; ++t
)
640 #if _GLIBCXX_ASSERTIONS
641 _GLIBCXX_PARALLEL_ASSERT(seqs_begin
[t
].first
!= seqs_begin
[t
].second
);
643 lt
.insert_start(*seqs_begin
[t
].first
, t
, false);
650 #if _GLIBCXX_ASSERTIONS
651 difference_type i
= 0;
654 RandomAccessIterator3 target_end
= target
+ length
;
655 while (target
< target_end
)
658 source
= lt
.get_min_source();
660 #if _GLIBCXX_ASSERTIONS
661 _GLIBCXX_PARALLEL_ASSERT(0 <= source
&& source
< k
);
662 _GLIBCXX_PARALLEL_ASSERT(i
== 0
663 || !comp(*(seqs_begin
[source
].first
), *(target
- 1)));
667 *(target
++) = *(seqs_begin
[source
].first
++);
669 #if _GLIBCXX_ASSERTIONS
672 // Replace from same source.
673 lt
.delete_min_insert(*seqs_begin
[source
].first
, false);
680 /** @brief Multi-way merging procedure for a high branching factor,
681 * requiring sentinels to exist.
683 * @param stable The value must the same as for the used LoserTrees.
684 * @param UnguardedLoserTree Loser Tree variant to use for the unguarded
686 * @param GuardedLoserTree Loser Tree variant to use for the guarded
689 * @param seqs_begin Begin iterator of iterator pair input sequence.
690 * @param seqs_end End iterator of iterator pair input sequence.
691 * @param target Begin iterator out output sequence.
692 * @param comp Comparator.
693 * @param length Maximum length to merge, less equal than the
694 * total number of elements available.
696 * @return End iterator of output sequence.
699 typename UnguardedLoserTree
,
700 typename RandomAccessIteratorIterator
,
701 typename RandomAccessIterator3
,
702 typename _DifferenceTp
,
704 RandomAccessIterator3
705 multiway_merge_loser_tree_sentinel(
706 RandomAccessIteratorIterator seqs_begin
,
707 RandomAccessIteratorIterator seqs_end
,
708 RandomAccessIterator3 target
,
709 const typename
std::iterator_traits
<typename
std::iterator_traits
<
710 RandomAccessIteratorIterator
>::value_type::first_type
>::value_type
&
712 _DifferenceTp length
,
715 _GLIBCXX_CALL(length
)
717 typedef _DifferenceTp difference_type
;
718 typedef std::iterator_traits
<RandomAccessIteratorIterator
> traits_type
;
719 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
720 ::value_type::first_type
721 RandomAccessIterator1
;
722 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
725 RandomAccessIterator3 target_end
;
727 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; ++s
)
728 // Move the sequends end behind the sentinel spots. This has the
729 // effect that the sentinel appears to be within the sequence. Then,
730 // we can use the unguarded variant if we merge out as many
731 // non-sentinel elements as we have.
734 target_end
= multiway_merge_loser_tree_unguarded
736 (seqs_begin
, seqs_end
, target
, sentinel
, length
, comp
);
738 #if _GLIBCXX_ASSERTIONS
739 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
);
740 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
743 // Restore the sequence ends so the sentinels are not contained in the
744 // sequence any more (see comment in loop above).
745 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; ++s
)
752 * @brief Traits for determining whether the loser tree should
753 * use pointers or copies.
755 * The field "use_pointer" is used to determine whether to use pointers in
756 * the loser trees or whether to copy the values into the loser tree.
758 * The default behavior is to use pointers if the data type is 4 times as
759 * big as the pointer to it.
761 * Specialize for your data type to customize the behavior.
766 * struct loser_tree_traits<int>
767 * { static const bool use_pointer = false; };
770 * struct loser_tree_traits<heavyweight_type>
771 * { static const bool use_pointer = true; };
773 * @param T type to give the loser tree traits for.
775 template <typename T
>
776 struct loser_tree_traits
779 * @brief True iff to use pointers instead of values in loser trees.
781 * The default behavior is to use pointers if the data type is four
782 * times as big as the pointer to it.
784 static const bool use_pointer
= (sizeof(T
) > 4 * sizeof(T
*));
788 * @brief Switch for 3-way merging with sentinels turned off.
790 * Note that 3-way merging is always stable!
793 bool sentinels
/*default == false*/,
794 typename RandomAccessIteratorIterator
,
795 typename RandomAccessIterator3
,
796 typename _DifferenceTp
,
798 struct multiway_merge_3_variant_sentinel_switch
800 RandomAccessIterator3
operator()(
801 RandomAccessIteratorIterator seqs_begin
,
802 RandomAccessIteratorIterator seqs_end
,
803 RandomAccessIterator3 target
,
804 _DifferenceTp length
, Comparator comp
)
806 return multiway_merge_3_variant
<guarded_iterator
>(
807 seqs_begin
, seqs_end
, target
, length
, comp
);
812 * @brief Switch for 3-way merging with sentinels turned on.
814 * Note that 3-way merging is always stable!
817 typename RandomAccessIteratorIterator
,
818 typename RandomAccessIterator3
,
819 typename _DifferenceTp
,
821 struct multiway_merge_3_variant_sentinel_switch
822 <true, RandomAccessIteratorIterator
, RandomAccessIterator3
,
823 _DifferenceTp
, Comparator
>
825 RandomAccessIterator3
operator()(
826 RandomAccessIteratorIterator seqs_begin
,
827 RandomAccessIteratorIterator seqs_end
,
828 RandomAccessIterator3 target
,
829 _DifferenceTp length
, Comparator comp
)
831 return multiway_merge_3_variant
<unguarded_iterator
>(
832 seqs_begin
, seqs_end
, target
, length
, comp
);
837 * @brief Switch for 4-way merging with sentinels turned off.
839 * Note that 4-way merging is always stable!
842 bool sentinels
/*default == false*/,
843 typename RandomAccessIteratorIterator
,
844 typename RandomAccessIterator3
,
845 typename _DifferenceTp
,
847 struct multiway_merge_4_variant_sentinel_switch
849 RandomAccessIterator3
operator()(
850 RandomAccessIteratorIterator seqs_begin
,
851 RandomAccessIteratorIterator seqs_end
,
852 RandomAccessIterator3 target
,
853 _DifferenceTp length
, Comparator comp
)
855 return multiway_merge_4_variant
<guarded_iterator
>(
856 seqs_begin
, seqs_end
, target
, length
, comp
);
861 * @brief Switch for 4-way merging with sentinels turned on.
863 * Note that 4-way merging is always stable!
866 typename RandomAccessIteratorIterator
,
867 typename RandomAccessIterator3
,
868 typename _DifferenceTp
,
870 struct multiway_merge_4_variant_sentinel_switch
871 <true, RandomAccessIteratorIterator
, RandomAccessIterator3
,
872 _DifferenceTp
, Comparator
>
874 RandomAccessIterator3
operator()(
875 RandomAccessIteratorIterator seqs_begin
,
876 RandomAccessIteratorIterator seqs_end
,
877 RandomAccessIterator3 target
,
878 _DifferenceTp length
, Comparator comp
)
880 return multiway_merge_4_variant
<unguarded_iterator
>(
881 seqs_begin
, seqs_end
, target
, length
, comp
);
886 * @brief Switch for k-way merging with sentinels turned on.
891 typename RandomAccessIteratorIterator
,
892 typename RandomAccessIterator3
,
893 typename _DifferenceTp
,
895 struct multiway_merge_k_variant_sentinel_switch
897 RandomAccessIterator3
operator()(
898 RandomAccessIteratorIterator seqs_begin
,
899 RandomAccessIteratorIterator seqs_end
,
900 RandomAccessIterator3 target
,
901 const typename
std::iterator_traits
<typename
std::iterator_traits
<
902 RandomAccessIteratorIterator
>::value_type::first_type
>::value_type
&
904 _DifferenceTp length
, Comparator comp
)
906 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
907 ::value_type::first_type
908 RandomAccessIterator1
;
909 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
912 return multiway_merge_loser_tree_sentinel
<
913 typename
__gnu_cxx::__conditional_type
<
914 loser_tree_traits
<value_type
>::use_pointer
915 , LoserTreePointerUnguarded
<stable
, value_type
, Comparator
>
916 , LoserTreeUnguarded
<stable
, value_type
, Comparator
>
917 >::__type
>(seqs_begin
, seqs_end
, target
, sentinel
, length
, comp
);
922 * @brief Switch for k-way merging with sentinels turned off.
926 typename RandomAccessIteratorIterator
,
927 typename RandomAccessIterator3
,
928 typename _DifferenceTp
,
930 struct multiway_merge_k_variant_sentinel_switch
931 <false, stable
, RandomAccessIteratorIterator
, RandomAccessIterator3
,
932 _DifferenceTp
, Comparator
>
934 RandomAccessIterator3
operator()(
935 RandomAccessIteratorIterator seqs_begin
,
936 RandomAccessIteratorIterator seqs_end
,
937 RandomAccessIterator3 target
,
938 const typename
std::iterator_traits
<typename
std::iterator_traits
<
939 RandomAccessIteratorIterator
>::value_type::first_type
>::value_type
&
941 _DifferenceTp length
, Comparator comp
)
943 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
944 ::value_type::first_type
945 RandomAccessIterator1
;
946 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
949 return multiway_merge_loser_tree
<
950 typename
__gnu_cxx::__conditional_type
<
951 loser_tree_traits
<value_type
>::use_pointer
952 , LoserTreePointer
<stable
, value_type
, Comparator
>
953 , LoserTree
<stable
, value_type
, Comparator
>
954 >::__type
>(seqs_begin
, seqs_end
, target
, length
, comp
);
958 /** @brief Sequential multi-way merging switch.
960 * The _GLIBCXX_PARALLEL_DECISION is based on the branching factor and
962 * @param seqs_begin Begin iterator of iterator pair input sequence.
963 * @param seqs_end End iterator of iterator pair input sequence.
964 * @param target Begin iterator out output sequence.
965 * @param comp Comparator.
966 * @param length Maximum length to merge, possibly larger than the
967 * number of elements available.
968 * @param stable Stable merging incurs a performance penalty.
969 * @param sentinel The sequences have a sentinel element.
970 * @return End iterator of output sequence. */
974 typename RandomAccessIteratorIterator
,
975 typename RandomAccessIterator3
,
976 typename _DifferenceTp
,
978 RandomAccessIterator3
979 sequential_multiway_merge(
980 RandomAccessIteratorIterator seqs_begin
,
981 RandomAccessIteratorIterator seqs_end
,
982 RandomAccessIterator3 target
,
983 const typename
std::iterator_traits
<typename
std::iterator_traits
<
984 RandomAccessIteratorIterator
>::value_type::first_type
>::value_type
&
986 _DifferenceTp length
, Comparator comp
)
988 _GLIBCXX_CALL(length
)
990 typedef _DifferenceTp difference_type
;
991 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
992 ::value_type::first_type
993 RandomAccessIterator1
;
994 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
997 #if _GLIBCXX_ASSERTIONS
998 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; ++s
)
1000 _GLIBCXX_PARALLEL_ASSERT(is_sorted((*s
).first
, (*s
).second
, comp
));
1004 _DifferenceTp total_length
= 0;
1005 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; ++s
)
1006 total_length
+= _GLIBCXX_PARALLEL_LENGTH(*s
);
1008 length
= std::min
<_DifferenceTp
>(length
, total_length
);
1013 RandomAccessIterator3 return_target
= target
;
1014 int k
= static_cast<int>(seqs_end
- seqs_begin
);
1021 return_target
= std::copy(seqs_begin
[0].first
,
1022 seqs_begin
[0].first
+ length
,
1024 seqs_begin
[0].first
+= length
;
1027 return_target
= merge_advance(seqs_begin
[0].first
,
1028 seqs_begin
[0].second
,
1029 seqs_begin
[1].first
,
1030 seqs_begin
[1].second
,
1031 target
, length
, comp
);
1034 return_target
= multiway_merge_3_variant_sentinel_switch
<
1036 , RandomAccessIteratorIterator
1037 , RandomAccessIterator3
1039 , Comparator
>()(seqs_begin
, seqs_end
, target
, length
, comp
);
1042 return_target
= multiway_merge_4_variant_sentinel_switch
<
1044 , RandomAccessIteratorIterator
1045 , RandomAccessIterator3
1047 , Comparator
>()(seqs_begin
, seqs_end
, target
, length
, comp
);
1050 return_target
= multiway_merge_k_variant_sentinel_switch
<
1053 , RandomAccessIteratorIterator
1054 , RandomAccessIterator3
1056 , Comparator
>()(seqs_begin
, seqs_end
, target
, sentinel
, length
, comp
);
1059 #if _GLIBCXX_ASSERTIONS
1060 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target
+ length
, comp
));
1063 return return_target
;
1067 * @brief Stable sorting functor.
1069 * Used to reduce code instanciation in multiway_merge_sampling_splitting.
1071 template<bool stable
, class RandomAccessIterator
, class StrictWeakOrdering
>
1072 struct sampling_sorter
1074 void operator()(RandomAccessIterator first
, RandomAccessIterator last
,
1075 StrictWeakOrdering comp
)
1076 { __gnu_sequential::stable_sort(first
, last
, comp
); }
1080 * @brief Non-stable sorting functor.
1082 * Used to reduce code instantiation in multiway_merge_sampling_splitting.
1084 template<class RandomAccessIterator
, class StrictWeakOrdering
>
1085 struct sampling_sorter
<false, RandomAccessIterator
, StrictWeakOrdering
>
1087 void operator()(RandomAccessIterator first
, RandomAccessIterator last
,
1088 StrictWeakOrdering comp
)
1089 { __gnu_sequential::sort(first
, last
, comp
); }
1093 * @brief Sampling based splitting for parallel multiway-merge routine.
1097 , typename RandomAccessIteratorIterator
1098 , typename Comparator
1099 , typename difference_type
>
1100 void multiway_merge_sampling_splitting(
1101 RandomAccessIteratorIterator seqs_begin
,
1102 RandomAccessIteratorIterator seqs_end
,
1103 difference_type length
, difference_type total_length
, Comparator comp
,
1104 std::vector
<std::pair
<difference_type
, difference_type
> > *pieces
)
1106 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
1107 ::value_type::first_type
1108 RandomAccessIterator1
;
1109 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
1113 int k
= static_cast<int>(seqs_end
- seqs_begin
);
1115 int num_threads
= omp_get_num_threads();
1117 difference_type num_samples
=
1118 __gnu_parallel::_Settings::get().merge_oversampling
* num_threads
;
1120 value_type
* samples
= static_cast<value_type
*>(
1121 ::operator new(sizeof(value_type
) * k
* num_samples
));
1123 for (int s
= 0; s
< k
; ++s
)
1124 for (difference_type i
= 0; i
< num_samples
; ++i
)
1126 difference_type sample_index
=
1127 static_cast<difference_type
>(
1128 _GLIBCXX_PARALLEL_LENGTH(seqs_begin
[s
])
1129 * (double(i
+ 1) / (num_samples
+ 1))
1130 * (double(length
) / total_length
));
1131 new(&(samples
[s
* num_samples
+ i
]))
1132 value_type(seqs_begin
[s
].first
[sample_index
]);
1135 // Sort stable or non-stable, depending on value of template parameter
1137 sampling_sorter
<stable
, value_type
*, Comparator
>()(
1138 samples
, samples
+ (num_samples
* k
), comp
);
1140 for (int slab
= 0; slab
< num_threads
; ++slab
)
1141 // For each slab / processor.
1142 for (int seq
= 0; seq
< k
; ++seq
)
1144 // For each sequence.
1146 pieces
[slab
][seq
].first
=
1148 seqs_begin
[seq
].first
,
1149 seqs_begin
[seq
].second
,
1150 samples
[num_samples
* k
* slab
/ num_threads
],
1152 - seqs_begin
[seq
].first
;
1154 // Absolute beginning.
1155 pieces
[slab
][seq
].first
= 0;
1156 if ((slab
+ 1) < num_threads
)
1157 pieces
[slab
][seq
].second
=
1159 seqs_begin
[seq
].first
,
1160 seqs_begin
[seq
].second
,
1161 samples
[num_samples
* k
* (slab
+ 1) /
1163 - seqs_begin
[seq
].first
;
1166 pieces
[slab
][seq
].second
= _GLIBCXX_PARALLEL_LENGTH(seqs_begin
[seq
]);
1168 ::operator delete(samples
);
1172 * @brief Exact splitting for parallel multiway-merge routine.
1174 * None of the passed sequences may be empty.
1178 , typename RandomAccessIteratorIterator
1179 , typename Comparator
1180 , typename difference_type
>
1181 void multiway_merge_exact_splitting(
1182 RandomAccessIteratorIterator seqs_begin
,
1183 RandomAccessIteratorIterator seqs_end
,
1184 difference_type length
, difference_type total_length
, Comparator comp
,
1185 std::vector
<std::pair
<difference_type
, difference_type
> > *pieces
)
1187 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
1188 ::value_type::first_type
1189 RandomAccessIterator1
;
1191 const bool tight
= (total_length
== length
);
1194 const int k
= static_cast<int>(seqs_end
- seqs_begin
);
1196 const int num_threads
= omp_get_num_threads();
1198 // (Settings::multiway_merge_splitting == __gnu_parallel::_Settings::EXACT).
1199 std::vector
<RandomAccessIterator1
>* offsets
=
1200 new std::vector
<RandomAccessIterator1
>[num_threads
];
1202 std::pair
<RandomAccessIterator1
, RandomAccessIterator1
>
1205 copy(seqs_begin
, seqs_end
, se
.begin());
1207 difference_type
* borders
=
1208 new difference_type
[num_threads
+ 1];
1209 equally_split(length
, num_threads
, borders
);
1211 for (int s
= 0; s
< (num_threads
- 1); ++s
)
1213 offsets
[s
].resize(k
);
1215 se
.begin(), se
.end(), borders
[s
+ 1],
1216 offsets
[s
].begin(), comp
);
1218 // Last one also needed and available.
1221 offsets
[num_threads
- 1].resize(k
);
1222 multiseq_partition(se
.begin(), se
.end(),
1223 difference_type(length
),
1224 offsets
[num_threads
- 1].begin(), comp
);
1229 for (int slab
= 0; slab
< num_threads
; ++slab
)
1231 // For each slab / processor.
1232 for (int seq
= 0; seq
< k
; ++seq
)
1234 // For each sequence.
1237 // Absolute beginning.
1238 pieces
[slab
][seq
].first
= 0;
1241 pieces
[slab
][seq
].first
=
1242 pieces
[slab
- 1][seq
].second
;
1243 if (!tight
|| slab
< (num_threads
- 1))
1244 pieces
[slab
][seq
].second
=
1245 offsets
[slab
][seq
] - seqs_begin
[seq
].first
;
1248 // slab == num_threads - 1
1249 pieces
[slab
][seq
].second
=
1250 _GLIBCXX_PARALLEL_LENGTH(seqs_begin
[seq
]);
1257 /** @brief Parallel multi-way merge routine.
1259 * The _GLIBCXX_PARALLEL_DECISION is based on the branching factor
1260 * and runtime settings.
1262 * Must not be called if the number of sequences is 1.
1264 * @param Splitter functor to split input (either exact or sampling based)
1266 * @param seqs_begin Begin iterator of iterator pair input sequence.
1267 * @param seqs_end End iterator of iterator pair input sequence.
1268 * @param target Begin iterator out output sequence.
1269 * @param comp Comparator.
1270 * @param length Maximum length to merge, possibly larger than the
1271 * number of elements available.
1272 * @param stable Stable merging incurs a performance penalty.
1273 * @param sentinel Ignored.
1274 * @return End iterator of output sequence.
1279 typename RandomAccessIteratorIterator
,
1280 typename RandomAccessIterator3
,
1281 typename _DifferenceTp
,
1285 RandomAccessIterator3
1286 parallel_multiway_merge(RandomAccessIteratorIterator seqs_begin
,
1287 RandomAccessIteratorIterator seqs_end
,
1288 RandomAccessIterator3 target
,
1290 _DifferenceTp length
,
1292 thread_index_t num_threads
)
1294 #if _GLIBCXX_ASSERTIONS
1295 _GLIBCXX_PARALLEL_ASSERT(seqs_end
- seqs_begin
> 1);
1298 _GLIBCXX_CALL(length
)
1300 typedef _DifferenceTp difference_type
;
1301 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
1302 ::value_type::first_type
1303 RandomAccessIterator1
;
1305 std::iterator_traits
<RandomAccessIterator1
>::value_type value_type
;
1307 // Leave only non-empty sequences.
1308 typedef std::pair
<RandomAccessIterator1
, RandomAccessIterator1
> seq_type
;
1309 seq_type
* ne_seqs
= new seq_type
[seqs_end
- seqs_begin
];
1311 difference_type total_length
= 0;
1312 for (RandomAccessIteratorIterator raii
= seqs_begin
;
1313 raii
!= seqs_end
; ++raii
)
1315 _DifferenceTp seq_length
= _GLIBCXX_PARALLEL_LENGTH(*raii
);
1318 total_length
+= seq_length
;
1319 ne_seqs
[k
++] = *raii
;
1323 _GLIBCXX_CALL(total_length
)
1325 length
= std::min
<_DifferenceTp
>(length
, total_length
);
1327 if (total_length
== 0 || k
== 0)
1333 std::vector
<std::pair
<difference_type
, difference_type
> >* pieces
;
1335 num_threads
= static_cast<thread_index_t
>
1336 (std::min
<difference_type
>(num_threads
, total_length
));
1338 # pragma omp parallel num_threads (num_threads)
1342 num_threads
= omp_get_num_threads();
1343 // Thread t will have to merge pieces[iam][0..k - 1]
1344 pieces
= new std::vector
<
1345 std::pair
<difference_type
, difference_type
> >[num_threads
];
1346 for (int s
= 0; s
< num_threads
; ++s
)
1347 pieces
[s
].resize(k
);
1349 difference_type num_samples
=
1350 __gnu_parallel::_Settings::get().merge_oversampling
*
1353 splitter(ne_seqs
, ne_seqs
+ k
, length
, total_length
,
1357 thread_index_t iam
= omp_get_thread_num();
1359 difference_type target_position
= 0;
1361 for (int c
= 0; c
< k
; ++c
)
1362 target_position
+= pieces
[iam
][c
].first
;
1364 seq_type
* chunks
= new seq_type
[k
];
1366 for (int s
= 0; s
< k
; ++s
)
1368 chunks
[s
] = std::make_pair(
1369 ne_seqs
[s
].first
+ pieces
[iam
][s
].first
,
1370 ne_seqs
[s
].first
+ pieces
[iam
][s
].second
);
1373 if(length
> target_position
)
1374 sequential_multiway_merge
<stable
, sentinels
>(
1375 chunks
, chunks
+ k
, target
+ target_position
,
1376 *(seqs_begin
->second
), length
- target_position
, comp
);
1381 #if _GLIBCXX_ASSERTIONS
1382 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target
+ length
, comp
));
1386 // Update ends of sequences.
1387 for (RandomAccessIteratorIterator raii
= seqs_begin
;
1388 raii
!= seqs_end
; ++raii
)
1390 _DifferenceTp length
= _GLIBCXX_PARALLEL_LENGTH(*raii
);
1392 (*raii
).first
+= pieces
[num_threads
- 1][k
++].second
;
1398 return target
+ length
;
1402 * @brief Multiway Merge Frontend.
1404 * Merge the sequences specified by seqs_begin and seqs_end into
1405 * target. seqs_begin and seqs_end must point to a sequence of
1406 * pairs. These pairs must contain an iterator to the beginning
1407 * of a sequence in their first entry and an iterator the end of
1408 * the same sequence in their second entry.
1410 * Ties are broken arbitrarily. See stable_multiway_merge for a variant
1411 * that breaks ties by sequence number but is slower.
1413 * The first entries of the pairs (i.e. the begin iterators) will be moved
1416 * The output sequence has to provide enough space for all elements
1417 * that are written to it.
1419 * This function will merge the input sequences:
1422 * - parallel, depending on the input size and Settings
1423 * - using sampling for splitting
1424 * - not using sentinels
1429 * int sequences[10][10];
1430 * for (int i = 0; i < 10; ++i)
1431 * for (int j = 0; i < 10; ++j)
1432 * sequences[i][j] = j;
1435 * std::vector<std::pair<int*> > seqs;
1436 * for (int i = 0; i < 10; ++i)
1437 * { seqs.push(std::make_pair<int*>(sequences[i], sequences[i] + 10)) }
1439 * multiway_merge(seqs.begin(), seqs.end(), target, std::less<int>(), 33);
1442 * @see stable_multiway_merge
1444 * @pre All input sequences must be sorted.
1445 * @pre Target must provide enough space to merge out length elements or
1446 * the number of elements in all sequences, whichever is smaller.
1448 * @post [target, return value) contains merged elements from the
1450 * @post return value - target = min(length, number of elements in all
1453 * @param RandomAccessIteratorPairIterator iterator over sequence
1454 * of pairs of iterators
1455 * @param RandomAccessIteratorOut iterator over target sequence
1456 * @param _DifferenceTp difference type for the sequence
1457 * @param Comparator strict weak ordering type to compare elements
1460 * @param seqs_begin begin of sequence sequence
1461 * @param seqs_end end of sequence sequence
1462 * @param target target sequence to merge to.
1463 * @param comp strict weak ordering to use for element comparison.
1464 * @param length Maximum length to merge, possibly larger than the
1465 * number of elements available.
1467 * @return end iterator of output sequence
1472 typename RandomAccessIteratorPairIterator
1473 , typename RandomAccessIteratorOut
1474 , typename _DifferenceTp
1475 , typename Comparator
>
1476 RandomAccessIteratorOut
1477 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1478 , RandomAccessIteratorPairIterator seqs_end
1479 , RandomAccessIteratorOut target
1480 , _DifferenceTp length
, Comparator comp
1481 , __gnu_parallel::sequential_tag
)
1483 typedef _DifferenceTp difference_type
;
1484 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1486 // catch special case: no sequences
1487 if (seqs_begin
== seqs_end
)
1490 // Execute multiway merge *sequentially*.
1491 return sequential_multiway_merge
1492 </* stable = */ false, /* sentinels = */ false>
1493 (seqs_begin
, seqs_end
, target
, *(seqs_begin
->second
), length
, comp
);
1498 typename RandomAccessIteratorPairIterator
1499 , typename RandomAccessIteratorOut
1500 , typename _DifferenceTp
1501 , typename Comparator
>
1502 RandomAccessIteratorOut
1503 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1504 , RandomAccessIteratorPairIterator seqs_end
1505 , RandomAccessIteratorOut target
1506 , _DifferenceTp length
, Comparator comp
1507 , __gnu_parallel::exact_tag tag
)
1509 typedef _DifferenceTp difference_type
;
1510 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1512 // catch special case: no sequences
1513 if (seqs_begin
== seqs_end
)
1516 // Execute merge; maybe parallel, depending on the number of merged
1517 // elements and the number of sequences and global thresholds in
1519 if ((seqs_end
- seqs_begin
> 1) &&
1520 _GLIBCXX_PARALLEL_CONDITION(
1521 ((seqs_end
- seqs_begin
) >=
1522 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1523 && ((sequence_index_t
)length
>=
1524 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1525 return parallel_multiway_merge
1526 </* stable = */ false, /* sentinels = */ false>(
1527 seqs_begin
, seqs_end
, target
,
1528 multiway_merge_exact_splitting
</* stable = */ false,
1529 typename
std::iterator_traits
<RandomAccessIteratorPairIterator
>
1530 ::value_type
*, Comparator
, _DifferenceTp
>,
1531 static_cast<difference_type
>(length
), comp
, tag
.get_num_threads());
1533 return sequential_multiway_merge
1534 </* stable = */ false, /* sentinels = */ false>(
1535 seqs_begin
, seqs_end
, target
, *(seqs_begin
->second
), length
, comp
);
1540 typename RandomAccessIteratorPairIterator
1541 , typename RandomAccessIteratorOut
1542 , typename _DifferenceTp
1543 , typename Comparator
>
1544 RandomAccessIteratorOut
1545 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1546 , RandomAccessIteratorPairIterator seqs_end
1547 , RandomAccessIteratorOut target
1548 , _DifferenceTp length
, Comparator comp
1549 , __gnu_parallel::sampling_tag tag
)
1551 typedef _DifferenceTp difference_type
;
1552 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1554 // catch special case: no sequences
1555 if (seqs_begin
== seqs_end
)
1558 // Execute merge; maybe parallel, depending on the number of merged
1559 // elements and the number of sequences and global thresholds in
1561 if ((seqs_end
- seqs_begin
> 1) &&
1562 _GLIBCXX_PARALLEL_CONDITION(
1563 ((seqs_end
- seqs_begin
) >=
1564 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1565 && ((sequence_index_t
)length
>=
1566 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1567 return parallel_multiway_merge
1568 </* stable = */ false, /* sentinels = */ false>(
1569 seqs_begin
, seqs_end
,
1571 multiway_merge_exact_splitting
</* stable = */ false,
1572 typename
std::iterator_traits
<RandomAccessIteratorPairIterator
>
1573 ::value_type
*, Comparator
, _DifferenceTp
>,
1574 static_cast<difference_type
>(length
), comp
, tag
.get_num_threads());
1576 return sequential_multiway_merge
1577 </* stable = */ false, /* sentinels = */ false>(
1578 seqs_begin
, seqs_end
,
1579 target
, *(seqs_begin
->second
), length
, comp
);
1584 typename RandomAccessIteratorPairIterator
1585 , typename RandomAccessIteratorOut
1586 , typename _DifferenceTp
1587 , typename Comparator
>
1588 RandomAccessIteratorOut
1589 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1590 , RandomAccessIteratorPairIterator seqs_end
1591 , RandomAccessIteratorOut target
1592 , _DifferenceTp length
, Comparator comp
1593 , parallel_tag tag
= parallel_tag(0))
1595 return multiway_merge(seqs_begin
, seqs_end
, target
, length
, comp
,
1596 exact_tag(tag
.get_num_threads()));
1601 typename RandomAccessIteratorPairIterator
1602 , typename RandomAccessIteratorOut
1603 , typename _DifferenceTp
1604 , typename Comparator
>
1605 RandomAccessIteratorOut
1606 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1607 , RandomAccessIteratorPairIterator seqs_end
1608 , RandomAccessIteratorOut target
1609 , _DifferenceTp length
, Comparator comp
1610 , default_parallel_tag tag
)
1612 return multiway_merge(seqs_begin
, seqs_end
, target
, length
, comp
,
1613 exact_tag(tag
.get_num_threads()));
1616 // stable_multiway_merge
1619 typename RandomAccessIteratorPairIterator
1620 , typename RandomAccessIteratorOut
1621 , typename _DifferenceTp
1622 , typename Comparator
>
1623 RandomAccessIteratorOut
1624 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1625 , RandomAccessIteratorPairIterator seqs_end
1626 , RandomAccessIteratorOut target
1627 , _DifferenceTp length
, Comparator comp
1628 , __gnu_parallel::sequential_tag
)
1630 typedef _DifferenceTp difference_type
;
1631 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1633 // catch special case: no sequences
1634 if (seqs_begin
== seqs_end
)
1637 // Execute multiway merge *sequentially*.
1638 return sequential_multiway_merge
1639 </* stable = */ true, /* sentinels = */ false>
1640 (seqs_begin
, seqs_end
, target
, *(seqs_begin
->second
), length
, comp
);
1645 typename RandomAccessIteratorPairIterator
1646 , typename RandomAccessIteratorOut
1647 , typename _DifferenceTp
1648 , typename Comparator
>
1649 RandomAccessIteratorOut
1650 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1651 , RandomAccessIteratorPairIterator seqs_end
1652 , RandomAccessIteratorOut target
1653 , _DifferenceTp length
, Comparator comp
1654 , __gnu_parallel::exact_tag tag
)
1656 typedef _DifferenceTp difference_type
;
1657 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1659 // catch special case: no sequences
1660 if (seqs_begin
== seqs_end
)
1663 // Execute merge; maybe parallel, depending on the number of merged
1664 // elements and the number of sequences and global thresholds in
1666 if ((seqs_end
- seqs_begin
> 1) &&
1667 _GLIBCXX_PARALLEL_CONDITION(
1668 ((seqs_end
- seqs_begin
) >=
1669 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1670 && ((sequence_index_t
)length
>=
1671 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1672 return parallel_multiway_merge
1673 </* stable = */ true, /* sentinels = */ false>(
1674 seqs_begin
, seqs_end
,
1676 multiway_merge_exact_splitting
</* stable = */ true,
1677 typename
std::iterator_traits
<RandomAccessIteratorPairIterator
>
1678 ::value_type
*, Comparator
, _DifferenceTp
>,
1679 static_cast<difference_type
>(length
), comp
, tag
.get_num_threads());
1681 return sequential_multiway_merge
</* stable = */ true,
1682 /* sentinels = */ false>(
1683 seqs_begin
, seqs_end
,
1684 target
, *(seqs_begin
->second
), length
, comp
);
1689 typename RandomAccessIteratorPairIterator
1690 , typename RandomAccessIteratorOut
1691 , typename _DifferenceTp
1692 , typename Comparator
>
1693 RandomAccessIteratorOut
1694 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1695 , RandomAccessIteratorPairIterator seqs_end
1696 , RandomAccessIteratorOut target
1697 , _DifferenceTp length
, Comparator comp
1700 typedef _DifferenceTp difference_type
;
1701 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1703 // catch special case: no sequences
1704 if (seqs_begin
== seqs_end
)
1707 // Execute merge; maybe parallel, depending on the number of merged
1708 // elements and the number of sequences and global thresholds in
1710 if ((seqs_end
- seqs_begin
> 1) &&
1711 _GLIBCXX_PARALLEL_CONDITION(
1712 ((seqs_end
- seqs_begin
) >=
1713 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1714 && ((sequence_index_t
)length
>=
1715 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1716 return parallel_multiway_merge
1717 </* stable = */ true, /* sentinels = */ false>(
1718 seqs_begin
, seqs_end
,
1720 multiway_merge_sampling_splitting
</* stable = */ true,
1721 typename
std::iterator_traits
<RandomAccessIteratorPairIterator
>
1722 ::value_type
*, Comparator
, _DifferenceTp
>,
1723 static_cast<difference_type
>(length
), comp
, tag
.get_num_threads());
1725 return sequential_multiway_merge
1726 </* stable = */ true, /* sentinels = */ false>(
1727 seqs_begin
, seqs_end
,
1728 target
, *(seqs_begin
->second
), length
, comp
);
1734 typename RandomAccessIteratorPairIterator
1735 , typename RandomAccessIteratorOut
1736 , typename _DifferenceTp
1737 , typename Comparator
>
1738 RandomAccessIteratorOut
1739 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1740 , RandomAccessIteratorPairIterator seqs_end
1741 , RandomAccessIteratorOut target
1742 , _DifferenceTp length
, Comparator comp
1743 , parallel_tag tag
= parallel_tag(0))
1745 return stable_multiway_merge(seqs_begin
, seqs_end
, target
, length
, comp
,
1746 exact_tag(tag
.get_num_threads()));
1751 typename RandomAccessIteratorPairIterator
1752 , typename RandomAccessIteratorOut
1753 , typename _DifferenceTp
1754 , typename Comparator
>
1755 RandomAccessIteratorOut
1756 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1757 , RandomAccessIteratorPairIterator seqs_end
1758 , RandomAccessIteratorOut target
1759 , _DifferenceTp length
, Comparator comp
1760 , default_parallel_tag tag
)
1762 return stable_multiway_merge(seqs_begin
, seqs_end
, target
, length
, comp
,
1763 exact_tag(tag
.get_num_threads()));
1767 * @brief Multiway Merge Frontend.
1769 * Merge the sequences specified by seqs_begin and seqs_end into
1770 * target. seqs_begin and seqs_end must point to a sequence of
1771 * pairs. These pairs must contain an iterator to the beginning
1772 * of a sequence in their first entry and an iterator the end of
1773 * the same sequence in their second entry.
1775 * Ties are broken arbitrarily. See stable_multiway_merge for a variant
1776 * that breaks ties by sequence number but is slower.
1778 * The first entries of the pairs (i.e. the begin iterators) will be moved
1779 * forward accordingly.
1781 * The output sequence has to provide enough space for all elements
1782 * that are written to it.
1784 * This function will merge the input sequences:
1787 * - parallel, depending on the input size and Settings
1788 * - using sampling for splitting
1791 * You have to take care that the element the end iterator points to is
1792 * readable and contains a value that is greater than any other non-sentinel
1793 * value in all sequences.
1798 * int sequences[10][11];
1799 * for (int i = 0; i < 10; ++i)
1800 * for (int j = 0; i < 11; ++j)
1801 * sequences[i][j] = j; // last one is sentinel!
1804 * std::vector<std::pair<int*> > seqs;
1805 * for (int i = 0; i < 10; ++i)
1806 * { seqs.push(std::make_pair<int*>(sequences[i], sequences[i] + 10)) }
1808 * multiway_merge(seqs.begin(), seqs.end(), target, std::less<int>(), 33);
1811 * @pre All input sequences must be sorted.
1812 * @pre Target must provide enough space to merge out length elements or
1813 * the number of elements in all sequences, whichever is smaller.
1814 * @pre For each @c i, @c seqs_begin[i].second must be the end
1815 * marker of the sequence, but also reference the one more sentinel
1818 * @post [target, return value) contains merged elements from the
1820 * @post return value - target = min(length, number of elements in all
1823 * @see stable_multiway_merge_sentinels
1825 * @param RandomAccessIteratorPairIterator iterator over sequence
1826 * of pairs of iterators
1827 * @param RandomAccessIteratorOut iterator over target sequence
1828 * @param _DifferenceTp difference type for the sequence
1829 * @param Comparator strict weak ordering type to compare elements
1832 * @param seqs_begin begin of sequence sequence
1833 * @param seqs_end end of sequence sequence
1834 * @param target target sequence to merge to.
1835 * @param comp strict weak ordering to use for element comparison.
1836 * @param length Maximum length to merge, possibly larger than the
1837 * number of elements available.
1839 * @return end iterator of output sequence
1841 // multiway_merge_sentinels
1844 typename RandomAccessIteratorPairIterator
1845 , typename RandomAccessIteratorOut
1846 , typename _DifferenceTp
1847 , typename Comparator
>
1848 RandomAccessIteratorOut
1849 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1850 , RandomAccessIteratorPairIterator seqs_end
1851 , RandomAccessIteratorOut target
1852 , _DifferenceTp length
, Comparator comp
1853 , __gnu_parallel::sequential_tag
)
1855 typedef _DifferenceTp difference_type
;
1856 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1858 // catch special case: no sequences
1859 if (seqs_begin
== seqs_end
)
1862 // Execute multiway merge *sequentially*.
1863 return sequential_multiway_merge
1864 </* stable = */ false, /* sentinels = */ true>
1865 (seqs_begin
, seqs_end
,
1866 target
, *(seqs_begin
->second
), length
, comp
);
1871 typename RandomAccessIteratorPairIterator
1872 , typename RandomAccessIteratorOut
1873 , typename _DifferenceTp
1874 , typename Comparator
>
1875 RandomAccessIteratorOut
1876 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1877 , RandomAccessIteratorPairIterator seqs_end
1878 , RandomAccessIteratorOut target
1879 , _DifferenceTp length
, Comparator comp
1880 , __gnu_parallel::exact_tag tag
)
1882 typedef _DifferenceTp difference_type
;
1883 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1885 // catch special case: no sequences
1886 if (seqs_begin
== seqs_end
)
1889 // Execute merge; maybe parallel, depending on the number of merged
1890 // elements and the number of sequences and global thresholds in
1892 if ((seqs_end
- seqs_begin
> 1) &&
1893 _GLIBCXX_PARALLEL_CONDITION(
1894 ((seqs_end
- seqs_begin
) >=
1895 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1896 && ((sequence_index_t
)length
>=
1897 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1898 return parallel_multiway_merge
1899 </* stable = */ false, /* sentinels = */ true>(
1900 seqs_begin
, seqs_end
,
1902 multiway_merge_exact_splitting
</* stable = */ false,
1903 typename
std::iterator_traits
<RandomAccessIteratorPairIterator
>
1904 ::value_type
*, Comparator
, _DifferenceTp
>,
1905 static_cast<difference_type
>(length
), comp
, tag
.get_num_threads());
1907 return sequential_multiway_merge
1908 </* stable = */ false, /* sentinels = */ true>(
1909 seqs_begin
, seqs_end
,
1910 target
, *(seqs_begin
->second
), length
, comp
);
1915 typename RandomAccessIteratorPairIterator
1916 , typename RandomAccessIteratorOut
1917 , typename _DifferenceTp
1918 , typename Comparator
>
1919 RandomAccessIteratorOut
1920 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1921 , RandomAccessIteratorPairIterator seqs_end
1922 , RandomAccessIteratorOut target
1923 , _DifferenceTp length
, Comparator comp
1926 typedef _DifferenceTp difference_type
;
1927 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1929 // catch special case: no sequences
1930 if (seqs_begin
== seqs_end
)
1933 // Execute merge; maybe parallel, depending on the number of merged
1934 // elements and the number of sequences and global thresholds in
1936 if ((seqs_end
- seqs_begin
> 1) &&
1937 _GLIBCXX_PARALLEL_CONDITION(
1938 ((seqs_end
- seqs_begin
) >=
1939 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1940 && ((sequence_index_t
)length
>=
1941 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1942 return parallel_multiway_merge
1943 </* stable = */ false, /* sentinels = */ true>
1944 (seqs_begin
, seqs_end
, target
,
1945 multiway_merge_sampling_splitting
</* stable = */ false,
1946 typename
std::iterator_traits
<RandomAccessIteratorPairIterator
>
1947 ::value_type
*, Comparator
, _DifferenceTp
>,
1948 static_cast<difference_type
>(length
), comp
, tag
.get_num_threads());
1950 return sequential_multiway_merge
1951 </* stable = */false, /* sentinels = */ true>(
1952 seqs_begin
, seqs_end
,
1953 target
, *(seqs_begin
->second
), length
, comp
);
1958 typename RandomAccessIteratorPairIterator
1959 , typename RandomAccessIteratorOut
1960 , typename _DifferenceTp
1961 , typename Comparator
>
1962 RandomAccessIteratorOut
1963 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1964 , RandomAccessIteratorPairIterator seqs_end
1965 , RandomAccessIteratorOut target
1966 , _DifferenceTp length
, Comparator comp
1967 , parallel_tag tag
= parallel_tag(0))
1969 return multiway_merge_sentinels(seqs_begin
, seqs_end
, target
, length
, comp
,
1970 exact_tag(tag
.get_num_threads()));
1975 typename RandomAccessIteratorPairIterator
1976 , typename RandomAccessIteratorOut
1977 , typename _DifferenceTp
1978 , typename Comparator
>
1979 RandomAccessIteratorOut
1980 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1981 , RandomAccessIteratorPairIterator seqs_end
1982 , RandomAccessIteratorOut target
1983 , _DifferenceTp length
, Comparator comp
1984 , default_parallel_tag tag
)
1986 return multiway_merge_sentinels(seqs_begin
, seqs_end
, target
, length
, comp
,
1987 exact_tag(tag
.get_num_threads()));
1990 // stable_multiway_merge_sentinels
1993 typename RandomAccessIteratorPairIterator
1994 , typename RandomAccessIteratorOut
1995 , typename _DifferenceTp
1996 , typename Comparator
>
1997 RandomAccessIteratorOut
1998 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1999 , RandomAccessIteratorPairIterator seqs_end
2000 , RandomAccessIteratorOut target
2001 , _DifferenceTp length
, Comparator comp
2002 , __gnu_parallel::sequential_tag
)
2004 typedef _DifferenceTp difference_type
;
2005 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
2007 // catch special case: no sequences
2008 if (seqs_begin
== seqs_end
)
2011 // Execute multiway merge *sequentially*.
2012 return sequential_multiway_merge
2013 </* stable = */ true, /* sentinels = */ true>
2014 (seqs_begin
, seqs_end
, target
, *(seqs_begin
->second
), length
, comp
);
2019 typename RandomAccessIteratorPairIterator
2020 , typename RandomAccessIteratorOut
2021 , typename _DifferenceTp
2022 , typename Comparator
>
2023 RandomAccessIteratorOut
2024 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
2025 , RandomAccessIteratorPairIterator seqs_end
2026 , RandomAccessIteratorOut target
2027 , _DifferenceTp length
, Comparator comp
2028 , __gnu_parallel::exact_tag tag
)
2030 typedef _DifferenceTp difference_type
;
2031 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
2033 // catch special case: no sequences
2034 if (seqs_begin
== seqs_end
)
2037 // Execute merge; maybe parallel, depending on the number of merged
2038 // elements and the number of sequences and global thresholds in
2040 if ((seqs_end
- seqs_begin
> 1) &&
2041 _GLIBCXX_PARALLEL_CONDITION(
2042 ((seqs_end
- seqs_begin
) >=
2043 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
2044 && ((sequence_index_t
)length
>=
2045 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
2046 return parallel_multiway_merge
2047 </* stable = */ true, /* sentinels = */ true>(
2048 seqs_begin
, seqs_end
,
2050 multiway_merge_exact_splitting
</* stable = */ true,
2051 typename
std::iterator_traits
<RandomAccessIteratorPairIterator
>
2052 ::value_type
*, Comparator
, _DifferenceTp
>,
2053 static_cast<difference_type
>(length
), comp
, tag
.get_num_threads());
2055 return sequential_multiway_merge
2056 </* stable = */ true, /* sentinels = */ true>(
2057 seqs_begin
, seqs_end
, target
, *(seqs_begin
->second
), length
, comp
);
2062 typename RandomAccessIteratorPairIterator
2063 , typename RandomAccessIteratorOut
2064 , typename _DifferenceTp
2065 , typename Comparator
>
2066 RandomAccessIteratorOut
2067 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
2068 , RandomAccessIteratorPairIterator seqs_end
2069 , RandomAccessIteratorOut target
2070 , _DifferenceTp length
, Comparator comp
2073 typedef _DifferenceTp difference_type
;
2074 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
2076 // catch special case: no sequences
2077 if (seqs_begin
== seqs_end
)
2080 // Execute merge; maybe parallel, depending on the number of merged
2081 // elements and the number of sequences and global thresholds in
2083 if ((seqs_end
- seqs_begin
> 1) &&
2084 _GLIBCXX_PARALLEL_CONDITION(
2085 ((seqs_end
- seqs_begin
) >=
2086 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
2087 && ((sequence_index_t
)length
>=
2088 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
2089 return parallel_multiway_merge
2090 </* stable = */ true, /* sentinels = */ true>(
2091 seqs_begin
, seqs_end
,
2093 multiway_merge_sampling_splitting
</* stable = */ true,
2094 typename
std::iterator_traits
<RandomAccessIteratorPairIterator
>
2095 ::value_type
*, Comparator
, _DifferenceTp
>,
2096 static_cast<difference_type
>(length
), comp
, tag
.get_num_threads());
2098 return sequential_multiway_merge
2099 </* stable = */ true, /* sentinels = */ true>(
2100 seqs_begin
, seqs_end
,
2101 target
, *(seqs_begin
->second
), length
, comp
);
2106 typename RandomAccessIteratorPairIterator
2107 , typename RandomAccessIteratorOut
2108 , typename _DifferenceTp
2109 , typename Comparator
>
2110 RandomAccessIteratorOut
2111 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
2112 , RandomAccessIteratorPairIterator seqs_end
2113 , RandomAccessIteratorOut target
2114 , _DifferenceTp length
, Comparator comp
2115 , parallel_tag tag
= parallel_tag(0))
2117 return stable_multiway_merge_sentinels(seqs_begin
, seqs_end
, target
, length
, comp
,
2118 exact_tag(tag
.get_num_threads()));
2123 typename RandomAccessIteratorPairIterator
2124 , typename RandomAccessIteratorOut
2125 , typename _DifferenceTp
2126 , typename Comparator
>
2127 RandomAccessIteratorOut
2128 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
2129 , RandomAccessIteratorPairIterator seqs_end
2130 , RandomAccessIteratorOut target
2131 , _DifferenceTp length
, Comparator comp
2132 , default_parallel_tag tag
)
2134 return stable_multiway_merge_sentinels(seqs_begin
, seqs_end
, target
, length
, comp
,
2135 exact_tag(tag
.get_num_threads()));
2138 }; // namespace __gnu_parallel
2140 #endif /* _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H */