3 // Copyright (C) 2007, 2008 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 2, 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 // You should have received a copy of the GNU General Public License
17 // along with this library; see the file COPYING. If not, write to
18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
19 // MA 02111-1307, USA.
21 // As a special exception, you may use this file as part of a free
22 // software library without restriction. Specifically, if other files
23 // instantiate templates or use macros or inline functions from this
24 // file, or you compile this file and link it with other files to
25 // produce an executable, this file does not by itself cause the
26 // resulting executable to be covered by the GNU General Public
27 // License. This exception does not however invalidate any other
28 // reasons why the executable file might be covered by the GNU General
31 /** @file parallel/multiway_merge.h
32 * @brief Implementation of sequential and parallel multiway merge.
34 * Explanations on the high-speed merging routines in the appendix of
37 * Fast priority queues for cached memory.
38 * ACM Journal of Experimental Algorithmics, 5, 2000.
40 * This file is a GNU parallel extension to the Standard C++ Library.
43 // Written by Johannes Singler and Manuel Holtgrewe.
45 #ifndef _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H
46 #define _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H
50 #include <bits/stl_algo.h>
51 #include <parallel/features.h>
52 #include <parallel/parallel.h>
53 #include <parallel/losertree.h>
54 #if _GLIBCXX_ASSERTIONS
55 #include <parallel/checkers.h>
58 /** @brief Length of a sequence described by a pair of iterators. */
59 #define _GLIBCXX_PARALLEL_LENGTH(s) ((s).second - (s).first)
61 namespace __gnu_parallel
64 // Announce guarded and unguarded iterator.
66 template<typename RandomAccessIterator
, typename Comparator
>
67 class guarded_iterator
;
69 // Making the arguments const references seems to dangerous,
70 // the user-defined comparator might not be const.
71 template<typename RandomAccessIterator
, typename Comparator
>
73 operator<(guarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
74 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
76 template<typename RandomAccessIterator
, typename Comparator
>
78 operator<=(guarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
79 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
81 /** @brief Iterator wrapper supporting an implicit supremum at the end
82 * of the sequence, dominating all comparisons.
84 * The implicit supremum comes with a performance cost.
86 * Deriving from RandomAccessIterator is not possible since
87 * RandomAccessIterator need not be a class.
89 template<typename RandomAccessIterator
, typename Comparator
>
90 class guarded_iterator
93 /** @brief Current iterator position. */
94 RandomAccessIterator current
;
96 /** @brief End iterator of the sequence. */
97 RandomAccessIterator end
;
99 /** @brief Comparator. */
103 /** @brief Constructor. Sets iterator to beginning of sequence.
104 * @param begin Begin iterator of sequence.
105 * @param end End iterator of sequence.
106 * @param comp Comparator provided for associated overloaded
107 * compare operators. */
108 guarded_iterator(RandomAccessIterator begin
,
109 RandomAccessIterator end
, Comparator
& comp
)
110 : current(begin
), end(end
), comp(comp
)
113 /** @brief Pre-increment operator.
115 guarded_iterator
<RandomAccessIterator
, Comparator
>&
122 /** @brief Dereference operator.
123 * @return Referenced element. */
124 typename
std::iterator_traits
<RandomAccessIterator
>::value_type
&
128 /** @brief Convert to wrapped iterator.
129 * @return Wrapped iterator. */
130 operator RandomAccessIterator()
134 operator< <RandomAccessIterator
, Comparator
>(
135 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
136 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
139 operator<= <RandomAccessIterator
, Comparator
>(
140 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
141 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
144 /** @brief Compare two elements referenced by guarded iterators.
145 * @param bi1 First iterator.
146 * @param bi2 Second iterator.
147 * @return @c True if less. */
148 template<typename RandomAccessIterator
, typename Comparator
>
150 operator<(guarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
151 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
)
153 if (bi1
.current
== bi1
.end
) //bi1 is sup
154 return bi2
.current
== bi2
.end
; //bi2 is not sup
155 if (bi2
.current
== bi2
.end
) //bi2 is sup
157 return (bi1
.comp
)(*bi1
, *bi2
); //normal compare
160 /** @brief Compare two elements referenced by guarded iterators.
161 * @param bi1 First iterator.
162 * @param bi2 Second iterator.
163 * @return @c True if less equal. */
164 template<typename RandomAccessIterator
, typename Comparator
>
166 operator<=(guarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
167 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
)
169 if (bi2
.current
== bi2
.end
) //bi1 is sup
170 return bi1
.current
!= bi1
.end
; //bi2 is not sup
171 if (bi1
.current
== bi1
.end
) //bi2 is sup
173 return !(bi1
.comp
)(*bi2
, *bi1
); //normal compare
176 template<typename RandomAccessIterator
, typename Comparator
>
177 class unguarded_iterator
;
179 template<typename RandomAccessIterator
, typename Comparator
>
181 operator<(unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
182 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
184 template<typename RandomAccessIterator
, typename Comparator
>
186 operator<=(unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
187 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
189 template<typename RandomAccessIterator
, typename Comparator
>
190 class unguarded_iterator
193 /** @brief Current iterator position. */
194 RandomAccessIterator current
;
195 /** @brief Comparator. */
196 mutable Comparator
& comp
;
199 /** @brief Constructor. Sets iterator to beginning of sequence.
200 * @param begin Begin iterator of sequence.
201 * @param end Unused, only for compatibility.
202 * @param comp Unused, only for compatibility. */
203 unguarded_iterator(RandomAccessIterator begin
,
204 RandomAccessIterator end
, Comparator
& comp
)
205 : current(begin
), comp(comp
)
208 /** @brief Pre-increment operator.
210 unguarded_iterator
<RandomAccessIterator
, Comparator
>&
217 /** @brief Dereference operator.
218 * @return Referenced element. */
219 typename
std::iterator_traits
<RandomAccessIterator
>::value_type
&
223 /** @brief Convert to wrapped iterator.
224 * @return Wrapped iterator. */
225 operator RandomAccessIterator()
229 operator< <RandomAccessIterator
, Comparator
>(
230 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
231 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
234 operator<= <RandomAccessIterator
, Comparator
>(
235 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
236 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
239 /** @brief Compare two elements referenced by unguarded iterators.
240 * @param bi1 First iterator.
241 * @param bi2 Second iterator.
242 * @return @c True if less. */
243 template<typename RandomAccessIterator
, typename Comparator
>
245 operator<(unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
246 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
)
249 return (bi1
.comp
)(*bi1
, *bi2
);
252 /** @brief Compare two elements referenced by unguarded iterators.
253 * @param bi1 First iterator.
254 * @param bi2 Second iterator.
255 * @return @c True if less equal. */
256 template<typename RandomAccessIterator
, typename Comparator
>
258 operator<=(unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
259 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
)
262 return !(bi1
.comp
)(*bi2
, *bi1
);
265 /** @brief Highly efficient 3-way merging procedure.
267 * Merging is done with the algorithm implementation described by Peter
268 * Sanders. Basically, the idea is to minimize the number of necessary
269 * comparison after merging out an element. The implementation trick
270 * that makes this fast is that the order of the sequences is stored
271 * in the instruction pointer (translated into labels in C++).
273 * This works well for merging up to 4 sequences.
275 * Note that making the merging stable does <em>not</em> come at a
278 * Whether the merging is done guarded or unguarded is selected by the
279 * used iterator class.
281 * @param seqs_begin Begin iterator of iterator pair input sequence.
282 * @param seqs_end End iterator of iterator pair input sequence.
283 * @param target Begin iterator out output sequence.
284 * @param comp Comparator.
285 * @param length Maximum length to merge, less equal than the
286 * total number of elements available.
288 * @return End iterator of output sequence.
290 template<template<typename RAI
, typename C
> class iterator
,
291 typename RandomAccessIteratorIterator
,
292 typename RandomAccessIterator3
,
293 typename _DifferenceTp
,
295 RandomAccessIterator3
296 multiway_merge_3_variant(
297 RandomAccessIteratorIterator seqs_begin
,
298 RandomAccessIteratorIterator seqs_end
,
299 RandomAccessIterator3 target
,
300 _DifferenceTp length
, Comparator comp
)
302 _GLIBCXX_CALL(length
);
304 typedef _DifferenceTp difference_type
;
306 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
307 ::value_type::first_type
308 RandomAccessIterator1
;
309 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
315 #if _GLIBCXX_ASSERTIONS
316 _DifferenceTp orig_length
= length
;
319 iterator
<RandomAccessIterator1
, Comparator
>
320 seq0(seqs_begin
[0].first
, seqs_begin
[0].second
, comp
),
321 seq1(seqs_begin
[1].first
, seqs_begin
[1].second
, comp
),
322 seq2(seqs_begin
[2].first
, seqs_begin
[2].second
, comp
);
346 #define _GLIBCXX_PARALLEL_MERGE_3_CASE(a,b,c,c0,c1) \
348 *target = *seq ## a; \
352 if (length == 0) goto finish; \
353 if (seq ## a c0 seq ## b) goto s ## a ## b ## c; \
354 if (seq ## a c1 seq ## c) goto s ## b ## a ## c; \
355 goto s ## b ## c ## a;
357 _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 1, 2, <=, <=);
358 _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 2, 0, <=, < );
359 _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 0, 1, < , < );
360 _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 0, 2, < , <=);
361 _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 2, 1, <=, <=);
362 _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 1, 0, < , < );
364 #undef _GLIBCXX_PARALLEL_MERGE_3_CASE
369 #if _GLIBCXX_ASSERTIONS
370 _GLIBCXX_PARALLEL_ASSERT(
371 ((RandomAccessIterator1
)seq0
- seqs_begin
[0].first
) +
372 ((RandomAccessIterator1
)seq1
- seqs_begin
[1].first
) +
373 ((RandomAccessIterator1
)seq2
- seqs_begin
[2].first
)
377 seqs_begin
[0].first
= seq0
;
378 seqs_begin
[1].first
= seq1
;
379 seqs_begin
[2].first
= seq2
;
385 * @brief Highly efficient 4-way merging procedure.
387 * Merging is done with the algorithm implementation described by Peter
388 * Sanders. Basically, the idea is to minimize the number of necessary
389 * comparison after merging out an element. The implementation trick
390 * that makes this fast is that the order of the sequences is stored
391 * in the instruction pointer (translated into goto labels in C++).
393 * This works well for merging up to 4 sequences.
395 * Note that making the merging stable does <em>not</em> come at a
398 * Whether the merging is done guarded or unguarded is selected by the
399 * used iterator class.
401 * @param seqs_begin Begin iterator of iterator pair input sequence.
402 * @param seqs_end End iterator of iterator pair input sequence.
403 * @param target Begin iterator out output sequence.
404 * @param comp Comparator.
405 * @param length Maximum length to merge, less equal than the
406 * total number of elements available.
408 * @return End iterator of output sequence.
410 template<template<typename RAI
, typename C
> class iterator
,
411 typename RandomAccessIteratorIterator
,
412 typename RandomAccessIterator3
,
413 typename _DifferenceTp
,
415 RandomAccessIterator3
416 multiway_merge_4_variant(RandomAccessIteratorIterator seqs_begin
,
417 RandomAccessIteratorIterator seqs_end
,
418 RandomAccessIterator3 target
,
419 _DifferenceTp length
, Comparator comp
)
421 _GLIBCXX_CALL(length
);
422 typedef _DifferenceTp difference_type
;
424 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
425 ::value_type::first_type
426 RandomAccessIterator1
;
427 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
430 iterator
<RandomAccessIterator1
, Comparator
>
431 seq0(seqs_begin
[0].first
, seqs_begin
[0].second
, comp
),
432 seq1(seqs_begin
[1].first
, seqs_begin
[1].second
, comp
),
433 seq2(seqs_begin
[2].first
, seqs_begin
[2].second
, comp
),
434 seq3(seqs_begin
[3].first
, seqs_begin
[3].second
, comp
);
436 #define _GLIBCXX_PARALLEL_DECISION(a,b,c,d) { \
437 if (seq ## d < seq ## a) goto s ## d ## a ## b ## c; \
438 if (seq ## d < seq ## b) goto s ## a ## d ## b ## c; \
439 if (seq ## d < seq ## c) goto s ## a ## b ## d ## c; \
440 goto s ## a ## b ## c ## d; }
445 _GLIBCXX_PARALLEL_DECISION(0,1,2,3)
448 _GLIBCXX_PARALLEL_DECISION(2,0,1,3)
450 _GLIBCXX_PARALLEL_DECISION(0,2,1,3)
457 _GLIBCXX_PARALLEL_DECISION(1,0,2,3)
459 _GLIBCXX_PARALLEL_DECISION(1,2,0,3)
462 _GLIBCXX_PARALLEL_DECISION(2,1,0,3)
465 #define _GLIBCXX_PARALLEL_MERGE_4_CASE(a,b,c,d,c0,c1,c2) \
466 s ## a ## b ## c ## d: \
467 if (length == 0) goto finish; \
468 *target = *seq ## a; \
472 if (seq ## a c0 seq ## b) goto s ## a ## b ## c ## d; \
473 if (seq ## a c1 seq ## c) goto s ## b ## a ## c ## d; \
474 if (seq ## a c2 seq ## d) goto s ## b ## c ## a ## d; \
475 goto s ## b ## c ## d ## a;
477 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 2, 3, <=, <=, <=);
478 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 3, 2, <=, <=, <=);
479 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 1, 3, <=, <=, <=);
480 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 3, 1, <=, <=, <=);
481 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 1, 2, <=, <=, <=);
482 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 2, 1, <=, <=, <=);
483 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 2, 3, < , <=, <=);
484 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 3, 2, < , <=, <=);
485 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 0, 3, <=, < , <=);
486 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 3, 0, <=, <=, < );
487 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 0, 2, <=, < , <=);
488 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 2, 0, <=, <=, < );
489 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 1, 3, < , < , <=);
490 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 3, 1, < , <=, < );
491 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 0, 3, < , < , <=);
492 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 3, 0, < , <=, < );
493 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 0, 1, <=, < , < );
494 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 1, 0, <=, < , < );
495 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 1, 2, < , < , < );
496 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 2, 1, < , < , < );
497 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 0, 2, < , < , < );
498 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 2, 0, < , < , < );
499 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 0, 1, < , < , < );
500 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 1, 0, < , < , < );
502 #undef _GLIBCXX_PARALLEL_MERGE_4_CASE
503 #undef _GLIBCXX_PARALLEL_DECISION
508 seqs_begin
[0].first
= seq0
;
509 seqs_begin
[1].first
= seq1
;
510 seqs_begin
[2].first
= seq2
;
511 seqs_begin
[3].first
= seq3
;
516 /** @brief Multi-way merging procedure for a high branching factor,
519 * This merging variant uses a LoserTree class as selected by <tt>LT</tt>.
521 * Stability is selected through the used LoserTree class <tt>LT</tt>.
523 * At least one non-empty sequence is required.
525 * @param seqs_begin Begin iterator of iterator pair input sequence.
526 * @param seqs_end End iterator of iterator pair input sequence.
527 * @param target Begin iterator out output sequence.
528 * @param comp Comparator.
529 * @param length Maximum length to merge, less equal than the
530 * total number of elements available.
532 * @return End iterator of output sequence.
534 template<typename LT
,
535 typename RandomAccessIteratorIterator
,
536 typename RandomAccessIterator3
,
537 typename _DifferenceTp
,
539 RandomAccessIterator3
540 multiway_merge_loser_tree(RandomAccessIteratorIterator seqs_begin
,
541 RandomAccessIteratorIterator seqs_end
,
542 RandomAccessIterator3 target
,
543 _DifferenceTp length
, Comparator comp
)
545 _GLIBCXX_CALL(length
)
547 typedef _DifferenceTp difference_type
;
548 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
549 ::value_type::first_type
550 RandomAccessIterator1
;
551 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
554 int k
= static_cast<int>(seqs_end
- seqs_begin
);
558 // Default value for potentially non-default-constructible types.
559 value_type
* arbitrary_element
= NULL
;
561 for (int t
= 0; t
< k
; ++t
)
563 if(arbitrary_element
== NULL
564 && _GLIBCXX_PARALLEL_LENGTH(seqs_begin
[t
]) > 0)
565 arbitrary_element
= &(*seqs_begin
[t
].first
);
568 for (int t
= 0; t
< k
; ++t
)
570 if (seqs_begin
[t
].first
== seqs_begin
[t
].second
)
571 lt
.insert_start(*arbitrary_element
, t
, true);
573 lt
.insert_start(*seqs_begin
[t
].first
, t
, false);
580 for (difference_type i
= 0; i
< length
; ++i
)
583 source
= lt
.get_min_source();
585 *(target
++) = *(seqs_begin
[source
].first
++);
588 if (seqs_begin
[source
].first
== seqs_begin
[source
].second
)
589 lt
.delete_min_insert(*arbitrary_element
, true);
591 // Replace from same source.
592 lt
.delete_min_insert(*seqs_begin
[source
].first
, false);
598 /** @brief Multi-way merging procedure for a high branching factor,
601 * Merging is done using the LoserTree class <tt>LT</tt>.
603 * Stability is selected by the used LoserTrees.
605 * @pre No input will run out of elements during the merge.
607 * @param seqs_begin Begin iterator of iterator pair input sequence.
608 * @param seqs_end End iterator of iterator pair input sequence.
609 * @param target Begin iterator out output sequence.
610 * @param comp Comparator.
611 * @param length Maximum length to merge, less equal than the
612 * total number of elements available.
614 * @return End iterator of output sequence.
616 template<typename LT
,
617 typename RandomAccessIteratorIterator
,
618 typename RandomAccessIterator3
,
619 typename _DifferenceTp
, typename Comparator
>
620 RandomAccessIterator3
621 multiway_merge_loser_tree_unguarded(
622 RandomAccessIteratorIterator seqs_begin
,
623 RandomAccessIteratorIterator seqs_end
,
624 RandomAccessIterator3 target
,
625 const typename
std::iterator_traits
<typename
std::iterator_traits
<
626 RandomAccessIteratorIterator
>::value_type::first_type
>::value_type
&
628 _DifferenceTp length
,
631 _GLIBCXX_CALL(length
)
632 typedef _DifferenceTp difference_type
;
634 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
635 ::value_type::first_type
636 RandomAccessIterator1
;
637 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
640 int k
= seqs_end
- seqs_begin
;
642 LT
lt(k
, sentinel
, comp
);
644 for (int t
= 0; t
< k
; ++t
)
646 #if _GLIBCXX_ASSERTIONS
647 _GLIBCXX_PARALLEL_ASSERT(seqs_begin
[t
].first
!= seqs_begin
[t
].second
);
649 lt
.insert_start(*seqs_begin
[t
].first
, t
, false);
656 #if _GLIBCXX_ASSERTIONS
657 difference_type i
= 0;
660 RandomAccessIterator3 target_end
= target
+ length
;
661 while (target
< target_end
)
664 source
= lt
.get_min_source();
666 #if _GLIBCXX_ASSERTIONS
667 _GLIBCXX_PARALLEL_ASSERT(0 <= source
&& source
< k
);
668 _GLIBCXX_PARALLEL_ASSERT(i
== 0
669 || !comp(*(seqs_begin
[source
].first
), *(target
- 1)));
673 *(target
++) = *(seqs_begin
[source
].first
++);
675 #if _GLIBCXX_ASSERTIONS
678 // Replace from same source.
679 lt
.delete_min_insert(*seqs_begin
[source
].first
, false);
686 /** @brief Multi-way merging procedure for a high branching factor,
687 * requiring sentinels to exist.
689 * @param stable The value must the same as for the used LoserTrees.
690 * @param UnguardedLoserTree Loser Tree variant to use for the unguarded
692 * @param GuardedLoserTree Loser Tree variant to use for the guarded
695 * @param seqs_begin Begin iterator of iterator pair input sequence.
696 * @param seqs_end End iterator of iterator pair input sequence.
697 * @param target Begin iterator out output sequence.
698 * @param comp Comparator.
699 * @param length Maximum length to merge, less equal than the
700 * total number of elements available.
702 * @return End iterator of output sequence.
705 typename UnguardedLoserTree
,
706 typename RandomAccessIteratorIterator
,
707 typename RandomAccessIterator3
,
708 typename _DifferenceTp
,
710 RandomAccessIterator3
711 multiway_merge_loser_tree_sentinel(
712 RandomAccessIteratorIterator seqs_begin
,
713 RandomAccessIteratorIterator seqs_end
,
714 RandomAccessIterator3 target
,
715 const typename
std::iterator_traits
<typename
std::iterator_traits
<
716 RandomAccessIteratorIterator
>::value_type::first_type
>::value_type
&
718 _DifferenceTp length
,
721 _GLIBCXX_CALL(length
)
723 typedef _DifferenceTp difference_type
;
724 typedef std::iterator_traits
<RandomAccessIteratorIterator
> traits_type
;
725 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
726 ::value_type::first_type
727 RandomAccessIterator1
;
728 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
731 RandomAccessIterator3 target_end
;
733 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; ++s
)
734 // Move the sequends end behind the sentinel spots. This has the
735 // effect that the sentinel appears to be within the sequence. Then,
736 // we can use the unguarded variant if we merge out as many
737 // non-sentinel elements as we have.
740 target_end
= multiway_merge_loser_tree_unguarded
742 (seqs_begin
, seqs_end
, target
, sentinel
, length
, comp
);
744 #if _GLIBCXX_ASSERTIONS
745 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
);
746 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
749 // Restore the sequence ends so the sentinels are not contained in the
750 // sequence any more (see comment in loop above).
751 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; ++s
)
758 * @brief Traits for determining whether the loser tree should
759 * use pointers or copies.
761 * The field "use_pointer" is used to determine whether to use pointers in
762 * the loser trees or whether to copy the values into the loser tree.
764 * The default behavior is to use pointers if the data type is 4 times as
765 * big as the pointer to it.
767 * Specialize for your data type to customize the behavior.
772 * struct loser_tree_traits<int>
773 * { static const bool use_pointer = false; };
776 * struct loser_tree_traits<heavyweight_type>
777 * { static const bool use_pointer = true; };
779 * @param T type to give the loser tree traits for.
781 template <typename T
>
782 struct loser_tree_traits
785 * @brief True iff to use pointers instead of values in loser trees.
787 * The default behavior is to use pointers if the data type is four
788 * times as big as the pointer to it.
790 static const bool use_pointer
= (sizeof(T
) > 4 * sizeof(T
*));
794 * @brief Switch for 3-way merging with sentinels turned off.
796 * Note that 3-way merging is always stable!
799 bool sentinels
/*default == false*/,
800 typename RandomAccessIteratorIterator
,
801 typename RandomAccessIterator3
,
802 typename _DifferenceTp
,
804 struct multiway_merge_3_variant_sentinel_switch
806 RandomAccessIterator3
operator()(
807 RandomAccessIteratorIterator seqs_begin
,
808 RandomAccessIteratorIterator seqs_end
,
809 RandomAccessIterator3 target
,
810 _DifferenceTp length
, Comparator comp
)
812 return multiway_merge_3_variant
<guarded_iterator
>(
813 seqs_begin
, seqs_end
, target
, length
, comp
);
818 * @brief Switch for 3-way merging with sentinels turned on.
820 * Note that 3-way merging is always stable!
823 typename RandomAccessIteratorIterator
,
824 typename RandomAccessIterator3
,
825 typename _DifferenceTp
,
827 struct multiway_merge_3_variant_sentinel_switch
828 <true, RandomAccessIteratorIterator
, RandomAccessIterator3
,
829 _DifferenceTp
, Comparator
>
831 RandomAccessIterator3
operator()(
832 RandomAccessIteratorIterator seqs_begin
,
833 RandomAccessIteratorIterator seqs_end
,
834 RandomAccessIterator3 target
,
835 _DifferenceTp length
, Comparator comp
)
837 return multiway_merge_3_variant
<unguarded_iterator
>(
838 seqs_begin
, seqs_end
, target
, length
, comp
);
843 * @brief Switch for 4-way merging with sentinels turned off.
845 * Note that 4-way merging is always stable!
848 bool sentinels
/*default == false*/,
849 typename RandomAccessIteratorIterator
,
850 typename RandomAccessIterator3
,
851 typename _DifferenceTp
,
853 struct multiway_merge_4_variant_sentinel_switch
855 RandomAccessIterator3
operator()(
856 RandomAccessIteratorIterator seqs_begin
,
857 RandomAccessIteratorIterator seqs_end
,
858 RandomAccessIterator3 target
,
859 _DifferenceTp length
, Comparator comp
)
861 return multiway_merge_4_variant
<guarded_iterator
>(
862 seqs_begin
, seqs_end
, target
, length
, comp
);
867 * @brief Switch for 4-way merging with sentinels turned on.
869 * Note that 4-way merging is always stable!
872 typename RandomAccessIteratorIterator
,
873 typename RandomAccessIterator3
,
874 typename _DifferenceTp
,
876 struct multiway_merge_4_variant_sentinel_switch
877 <true, RandomAccessIteratorIterator
, RandomAccessIterator3
,
878 _DifferenceTp
, Comparator
>
880 RandomAccessIterator3
operator()(
881 RandomAccessIteratorIterator seqs_begin
,
882 RandomAccessIteratorIterator seqs_end
,
883 RandomAccessIterator3 target
,
884 _DifferenceTp length
, Comparator comp
)
886 return multiway_merge_4_variant
<unguarded_iterator
>(
887 seqs_begin
, seqs_end
, target
, length
, comp
);
892 * @brief Switch for k-way merging with sentinels turned on.
897 typename RandomAccessIteratorIterator
,
898 typename RandomAccessIterator3
,
899 typename _DifferenceTp
,
901 struct multiway_merge_k_variant_sentinel_switch
903 RandomAccessIterator3
operator()(
904 RandomAccessIteratorIterator seqs_begin
,
905 RandomAccessIteratorIterator seqs_end
,
906 RandomAccessIterator3 target
,
907 const typename
std::iterator_traits
<typename
std::iterator_traits
<
908 RandomAccessIteratorIterator
>::value_type::first_type
>::value_type
&
910 _DifferenceTp length
, Comparator comp
)
912 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
913 ::value_type::first_type
914 RandomAccessIterator1
;
915 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
918 return multiway_merge_loser_tree_sentinel
<
919 typename
__gnu_cxx::__conditional_type
<
920 loser_tree_traits
<value_type
>::use_pointer
921 , LoserTreePointerUnguarded
<stable
, value_type
, Comparator
>
922 , LoserTreeUnguarded
<stable
, value_type
, Comparator
>
923 >::__type
>(seqs_begin
, seqs_end
, target
, sentinel
, length
, comp
);
928 * @brief Switch for k-way merging with sentinels turned off.
932 typename RandomAccessIteratorIterator
,
933 typename RandomAccessIterator3
,
934 typename _DifferenceTp
,
936 struct multiway_merge_k_variant_sentinel_switch
937 <false, stable
, RandomAccessIteratorIterator
, RandomAccessIterator3
,
938 _DifferenceTp
, Comparator
>
940 RandomAccessIterator3
operator()(
941 RandomAccessIteratorIterator seqs_begin
,
942 RandomAccessIteratorIterator seqs_end
,
943 RandomAccessIterator3 target
,
944 const typename
std::iterator_traits
<typename
std::iterator_traits
<
945 RandomAccessIteratorIterator
>::value_type::first_type
>::value_type
&
947 _DifferenceTp length
, Comparator comp
)
949 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
950 ::value_type::first_type
951 RandomAccessIterator1
;
952 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
955 return multiway_merge_loser_tree
<
956 typename
__gnu_cxx::__conditional_type
<
957 loser_tree_traits
<value_type
>::use_pointer
958 , LoserTreePointer
<stable
, value_type
, Comparator
>
959 , LoserTree
<stable
, value_type
, Comparator
>
960 >::__type
>(seqs_begin
, seqs_end
, target
, length
, comp
);
964 /** @brief Sequential multi-way merging switch.
966 * The _GLIBCXX_PARALLEL_DECISION is based on the branching factor and
968 * @param seqs_begin Begin iterator of iterator pair input sequence.
969 * @param seqs_end End iterator of iterator pair input sequence.
970 * @param target Begin iterator out output sequence.
971 * @param comp Comparator.
972 * @param length Maximum length to merge, possibly larger than the
973 * number of elements available.
974 * @param stable Stable merging incurs a performance penalty.
975 * @param sentinel The sequences have a sentinel element.
976 * @return End iterator of output sequence. */
980 typename RandomAccessIteratorIterator
,
981 typename RandomAccessIterator3
,
982 typename _DifferenceTp
,
984 RandomAccessIterator3
985 sequential_multiway_merge(
986 RandomAccessIteratorIterator seqs_begin
,
987 RandomAccessIteratorIterator seqs_end
,
988 RandomAccessIterator3 target
,
989 const typename
std::iterator_traits
<typename
std::iterator_traits
<
990 RandomAccessIteratorIterator
>::value_type::first_type
>::value_type
&
992 _DifferenceTp length
, Comparator comp
)
994 _GLIBCXX_CALL(length
)
996 typedef _DifferenceTp difference_type
;
997 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
998 ::value_type::first_type
999 RandomAccessIterator1
;
1000 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
1003 #if _GLIBCXX_ASSERTIONS
1004 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; ++s
)
1006 _GLIBCXX_PARALLEL_ASSERT(is_sorted((*s
).first
, (*s
).second
, comp
));
1010 _DifferenceTp total_length
= 0;
1011 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; ++s
)
1012 total_length
+= _GLIBCXX_PARALLEL_LENGTH(*s
);
1014 length
= std::min
<_DifferenceTp
>(length
, total_length
);
1019 RandomAccessIterator3 return_target
= target
;
1020 int k
= static_cast<int>(seqs_end
- seqs_begin
);
1027 return_target
= std::copy(seqs_begin
[0].first
,
1028 seqs_begin
[0].first
+ length
,
1030 seqs_begin
[0].first
+= length
;
1033 return_target
= merge_advance(seqs_begin
[0].first
,
1034 seqs_begin
[0].second
,
1035 seqs_begin
[1].first
,
1036 seqs_begin
[1].second
,
1037 target
, length
, comp
);
1040 return_target
= multiway_merge_3_variant_sentinel_switch
<
1042 , RandomAccessIteratorIterator
1043 , RandomAccessIterator3
1045 , Comparator
>()(seqs_begin
, seqs_end
, target
, length
, comp
);
1048 return_target
= multiway_merge_4_variant_sentinel_switch
<
1050 , RandomAccessIteratorIterator
1051 , RandomAccessIterator3
1053 , Comparator
>()(seqs_begin
, seqs_end
, target
, length
, comp
);
1056 return_target
= multiway_merge_k_variant_sentinel_switch
<
1059 , RandomAccessIteratorIterator
1060 , RandomAccessIterator3
1062 , Comparator
>()(seqs_begin
, seqs_end
, target
, sentinel
, length
, comp
);
1065 #if _GLIBCXX_ASSERTIONS
1066 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target
+ length
, comp
));
1069 return return_target
;
1073 * @brief Stable sorting functor.
1075 * Used to reduce code instanciation in multiway_merge_sampling_splitting.
1077 template<bool stable
, class RandomAccessIterator
, class StrictWeakOrdering
>
1078 struct sampling_sorter
1080 void operator()(RandomAccessIterator first
, RandomAccessIterator last
,
1081 StrictWeakOrdering comp
)
1082 { __gnu_sequential::stable_sort(first
, last
, comp
); }
1086 * @brief Non-stable sorting functor.
1088 * Used to reduce code instantiation in multiway_merge_sampling_splitting.
1090 template<class RandomAccessIterator
, class StrictWeakOrdering
>
1091 struct sampling_sorter
<false, RandomAccessIterator
, StrictWeakOrdering
>
1093 void operator()(RandomAccessIterator first
, RandomAccessIterator last
,
1094 StrictWeakOrdering comp
)
1095 { __gnu_sequential::sort(first
, last
, comp
); }
1099 * @brief Sampling based splitting for parallel multiway-merge routine.
1103 , typename RandomAccessIteratorIterator
1104 , typename Comparator
1105 , typename difference_type
>
1106 void multiway_merge_sampling_splitting(
1107 RandomAccessIteratorIterator seqs_begin
,
1108 RandomAccessIteratorIterator seqs_end
,
1109 difference_type length
, difference_type total_length
, Comparator comp
,
1110 std::vector
<std::pair
<difference_type
, difference_type
> > *pieces
)
1112 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
1113 ::value_type::first_type
1114 RandomAccessIterator1
;
1115 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
1119 int k
= static_cast<int>(seqs_end
- seqs_begin
);
1121 int num_threads
= omp_get_num_threads();
1123 difference_type num_samples
=
1124 __gnu_parallel::_Settings::get().merge_oversampling
* num_threads
;
1126 value_type
* samples
= static_cast<value_type
*>(
1127 ::operator new(sizeof(value_type
) * k
* num_samples
));
1129 for (int s
= 0; s
< k
; ++s
)
1130 for (difference_type i
= 0; i
< num_samples
; ++i
)
1132 difference_type sample_index
=
1133 static_cast<difference_type
>(
1134 _GLIBCXX_PARALLEL_LENGTH(seqs_begin
[s
])
1135 * (double(i
+ 1) / (num_samples
+ 1))
1136 * (double(length
) / total_length
));
1137 new(&(samples
[s
* num_samples
+ i
]))
1138 value_type(seqs_begin
[s
].first
[sample_index
]);
1141 // Sort stable or non-stable, depending on value of template parameter
1143 sampling_sorter
<stable
, value_type
*, Comparator
>()(
1144 samples
, samples
+ (num_samples
* k
), comp
);
1146 for (int slab
= 0; slab
< num_threads
; ++slab
)
1147 // For each slab / processor.
1148 for (int seq
= 0; seq
< k
; ++seq
)
1150 // For each sequence.
1152 pieces
[slab
][seq
].first
=
1154 seqs_begin
[seq
].first
,
1155 seqs_begin
[seq
].second
,
1156 samples
[num_samples
* k
* slab
/ num_threads
],
1158 - seqs_begin
[seq
].first
;
1160 // Absolute beginning.
1161 pieces
[slab
][seq
].first
= 0;
1162 if ((slab
+ 1) < num_threads
)
1163 pieces
[slab
][seq
].second
=
1165 seqs_begin
[seq
].first
,
1166 seqs_begin
[seq
].second
,
1167 samples
[num_samples
* k
* (slab
+ 1) /
1169 - seqs_begin
[seq
].first
;
1172 pieces
[slab
][seq
].second
= _GLIBCXX_PARALLEL_LENGTH(seqs_begin
[seq
]);
1174 ::operator delete(samples
);
1178 * @brief Exact splitting for parallel multiway-merge routine.
1180 * None of the passed sequences may be empty.
1184 , typename RandomAccessIteratorIterator
1185 , typename Comparator
1186 , typename difference_type
>
1187 void multiway_merge_exact_splitting(
1188 RandomAccessIteratorIterator seqs_begin
,
1189 RandomAccessIteratorIterator seqs_end
,
1190 difference_type length
, difference_type total_length
, Comparator comp
,
1191 std::vector
<std::pair
<difference_type
, difference_type
> > *pieces
)
1193 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
1194 ::value_type::first_type
1195 RandomAccessIterator1
;
1197 const bool tight
= (total_length
== length
);
1200 const int k
= static_cast<int>(seqs_end
- seqs_begin
);
1202 const int num_threads
= omp_get_num_threads();
1204 // (Settings::multiway_merge_splitting == __gnu_parallel::_Settings::EXACT).
1205 std::vector
<RandomAccessIterator1
>* offsets
=
1206 new std::vector
<RandomAccessIterator1
>[num_threads
];
1208 std::pair
<RandomAccessIterator1
, RandomAccessIterator1
>
1211 copy(seqs_begin
, seqs_end
, se
.begin());
1213 difference_type
* borders
=
1214 new difference_type
[num_threads
+ 1];
1215 equally_split(length
, num_threads
, borders
);
1217 for (int s
= 0; s
< (num_threads
- 1); ++s
)
1219 offsets
[s
].resize(k
);
1221 se
.begin(), se
.end(), borders
[s
+ 1],
1222 offsets
[s
].begin(), comp
);
1224 // Last one also needed and available.
1227 offsets
[num_threads
- 1].resize(k
);
1228 multiseq_partition(se
.begin(), se
.end(),
1229 difference_type(length
),
1230 offsets
[num_threads
- 1].begin(), comp
);
1235 for (int slab
= 0; slab
< num_threads
; ++slab
)
1237 // For each slab / processor.
1238 for (int seq
= 0; seq
< k
; ++seq
)
1240 // For each sequence.
1243 // Absolute beginning.
1244 pieces
[slab
][seq
].first
= 0;
1247 pieces
[slab
][seq
].first
=
1248 pieces
[slab
- 1][seq
].second
;
1249 if (!tight
|| slab
< (num_threads
- 1))
1250 pieces
[slab
][seq
].second
=
1251 offsets
[slab
][seq
] - seqs_begin
[seq
].first
;
1254 // slab == num_threads - 1
1255 pieces
[slab
][seq
].second
=
1256 _GLIBCXX_PARALLEL_LENGTH(seqs_begin
[seq
]);
1263 /** @brief Parallel multi-way merge routine.
1265 * The _GLIBCXX_PARALLEL_DECISION is based on the branching factor
1266 * and runtime settings.
1268 * Must not be called if the number of sequences is 1.
1270 * @param Splitter functor to split input (either exact or sampling based)
1272 * @param seqs_begin Begin iterator of iterator pair input sequence.
1273 * @param seqs_end End iterator of iterator pair input sequence.
1274 * @param target Begin iterator out output sequence.
1275 * @param comp Comparator.
1276 * @param length Maximum length to merge, possibly larger than the
1277 * number of elements available.
1278 * @param stable Stable merging incurs a performance penalty.
1279 * @param sentinel Ignored.
1280 * @return End iterator of output sequence.
1285 typename RandomAccessIteratorIterator
,
1286 typename RandomAccessIterator3
,
1287 typename _DifferenceTp
,
1291 RandomAccessIterator3
1292 parallel_multiway_merge(RandomAccessIteratorIterator seqs_begin
,
1293 RandomAccessIteratorIterator seqs_end
,
1294 RandomAccessIterator3 target
,
1296 _DifferenceTp length
,
1298 thread_index_t num_threads
)
1300 #if _GLIBCXX_ASSERTIONS
1301 _GLIBCXX_PARALLEL_ASSERT(seqs_end
- seqs_begin
> 1);
1304 _GLIBCXX_CALL(length
)
1306 typedef _DifferenceTp difference_type
;
1307 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
1308 ::value_type::first_type
1309 RandomAccessIterator1
;
1311 std::iterator_traits
<RandomAccessIterator1
>::value_type value_type
;
1313 // Leave only non-empty sequences.
1314 std::pair
<RandomAccessIterator1
, RandomAccessIterator1
>* ne_seqs
=
1315 static_cast<std::pair
<RandomAccessIterator1
, RandomAccessIterator1
>*>(
1317 sizeof(std::pair
<RandomAccessIterator1
, RandomAccessIterator1
>)
1318 * (seqs_end
- seqs_begin
)));
1320 difference_type total_length
= 0;
1321 for (RandomAccessIteratorIterator raii
= seqs_begin
;
1322 raii
!= seqs_end
; ++raii
)
1324 _DifferenceTp seq_length
= _GLIBCXX_PARALLEL_LENGTH(*raii
);
1327 total_length
+= seq_length
;
1328 //ne_seqs[k] = *raii;
1329 new(&(ne_seqs
[k
++]))
1330 std::pair
<RandomAccessIterator1
, RandomAccessIterator1
>(*raii
);
1334 _GLIBCXX_CALL(total_length
)
1336 length
= std::min
<_DifferenceTp
>(length
, total_length
);
1338 if (total_length
== 0 || k
== 0)
1340 ::operator delete(ne_seqs
);
1344 std::vector
<std::pair
<difference_type
, difference_type
> >* pieces
;
1346 num_threads
= static_cast<thread_index_t
>
1347 (std::min
<difference_type
>(num_threads
, total_length
));
1349 # pragma omp parallel num_threads (num_threads)
1353 num_threads
= omp_get_num_threads();
1354 // Thread t will have to merge pieces[iam][0..k - 1]
1355 pieces
= new std::vector
<
1356 std::pair
<difference_type
, difference_type
> >[num_threads
];
1357 for (int s
= 0; s
< num_threads
; ++s
)
1358 pieces
[s
].resize(k
);
1360 difference_type num_samples
=
1361 __gnu_parallel::_Settings::get().merge_oversampling
*
1364 splitter(ne_seqs
, ne_seqs
+ k
, length
, total_length
,
1368 thread_index_t iam
= omp_get_thread_num();
1370 difference_type target_position
= 0;
1372 for (int c
= 0; c
< k
; ++c
)
1373 target_position
+= pieces
[iam
][c
].first
;
1375 std::pair
<RandomAccessIterator1
, RandomAccessIterator1
>* chunks
1376 = new std::pair
<RandomAccessIterator1
, RandomAccessIterator1
>[k
];
1378 for (int s
= 0; s
< k
; ++s
)
1380 chunks
[s
] = std::make_pair(
1381 ne_seqs
[s
].first
+ pieces
[iam
][s
].first
,
1382 ne_seqs
[s
].first
+ pieces
[iam
][s
].second
);
1385 if(length
> target_position
)
1386 sequential_multiway_merge
<stable
, sentinels
>(
1387 chunks
, chunks
+ k
, target
+ target_position
,
1388 *(seqs_begin
->second
), length
- target_position
, comp
);
1393 #if _GLIBCXX_ASSERTIONS
1394 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target
+ length
, comp
));
1398 // Update ends of sequences.
1399 for (RandomAccessIteratorIterator raii
= seqs_begin
;
1400 raii
!= seqs_end
; ++raii
)
1402 _DifferenceTp length
= _GLIBCXX_PARALLEL_LENGTH(*raii
);
1404 (*raii
).first
+= pieces
[num_threads
- 1][k
++].second
;
1409 return target
+ length
;
1413 * @brief Multiway Merge Frontend.
1415 * Merge the sequences specified by seqs_begin and seqs_end into
1416 * target. seqs_begin and seqs_end must point to a sequence of
1417 * pairs. These pairs must contain an iterator to the beginning
1418 * of a sequence in their first entry and an iterator the end of
1419 * the same sequence in their second entry.
1421 * Ties are broken arbitrarily. See stable_multiway_merge for a variant
1422 * that breaks ties by sequence number but is slower.
1424 * The first entries of the pairs (i.e. the begin iterators) will be moved
1427 * The output sequence has to provide enough space for all elements
1428 * that are written to it.
1430 * This function will merge the input sequences:
1433 * - parallel, depending on the input size and Settings
1434 * - using sampling for splitting
1435 * - not using sentinels
1440 * int sequences[10][10];
1441 * for (int i = 0; i < 10; ++i)
1442 * for (int j = 0; i < 10; ++j)
1443 * sequences[i][j] = j;
1446 * std::vector<std::pair<int*> > seqs;
1447 * for (int i = 0; i < 10; ++i)
1448 * { seqs.push(std::make_pair<int*>(sequences[i], sequences[i] + 10)) }
1450 * multiway_merge(seqs.begin(), seqs.end(), target, std::less<int>(), 33);
1453 * @see stable_multiway_merge
1455 * @pre All input sequences must be sorted.
1456 * @pre Target must provide enough space to merge out length elements or
1457 * the number of elements in all sequences, whichever is smaller.
1459 * @post [target, return value) contains merged elements from the
1461 * @post return value - target = min(length, number of elements in all
1464 * @param RandomAccessIteratorPairIterator iterator over sequence
1465 * of pairs of iterators
1466 * @param RandomAccessIteratorOut iterator over target sequence
1467 * @param _DifferenceTp difference type for the sequence
1468 * @param Comparator strict weak ordering type to compare elements
1471 * @param seqs_begin begin of sequence sequence
1472 * @param seqs_end end of sequence sequence
1473 * @param target target sequence to merge to.
1474 * @param comp strict weak ordering to use for element comparison.
1475 * @param length Maximum length to merge, possibly larger than the
1476 * number of elements available.
1478 * @return end iterator of output sequence
1483 typename RandomAccessIteratorPairIterator
1484 , typename RandomAccessIteratorOut
1485 , typename _DifferenceTp
1486 , typename Comparator
>
1487 RandomAccessIteratorOut
1488 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1489 , RandomAccessIteratorPairIterator seqs_end
1490 , RandomAccessIteratorOut target
1491 , _DifferenceTp length
, Comparator comp
1492 , __gnu_parallel::sequential_tag
)
1494 typedef _DifferenceTp difference_type
;
1495 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1497 // catch special case: no sequences
1498 if (seqs_begin
== seqs_end
)
1501 // Execute multiway merge *sequentially*.
1502 return sequential_multiway_merge
1503 </* stable = */ false, /* sentinels = */ false>
1504 (seqs_begin
, seqs_end
, target
, *(seqs_begin
->second
), length
, comp
);
1509 typename RandomAccessIteratorPairIterator
1510 , typename RandomAccessIteratorOut
1511 , typename _DifferenceTp
1512 , typename Comparator
>
1513 RandomAccessIteratorOut
1514 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1515 , RandomAccessIteratorPairIterator seqs_end
1516 , RandomAccessIteratorOut target
1517 , _DifferenceTp length
, Comparator comp
1518 , __gnu_parallel::exact_tag tag
)
1520 typedef _DifferenceTp difference_type
;
1521 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1523 // catch special case: no sequences
1524 if (seqs_begin
== seqs_end
)
1527 // Execute merge; maybe parallel, depending on the number of merged
1528 // elements and the number of sequences and global thresholds in
1530 if ((seqs_end
- seqs_begin
> 1) &&
1531 _GLIBCXX_PARALLEL_CONDITION(
1532 ((seqs_end
- seqs_begin
) >=
1533 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1534 && ((sequence_index_t
)length
>=
1535 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1536 return parallel_multiway_merge
1537 </* stable = */ false, /* sentinels = */ false>(
1538 seqs_begin
, seqs_end
, target
,
1539 multiway_merge_exact_splitting
</* stable = */ false,
1540 typename
std::iterator_traits
<RandomAccessIteratorPairIterator
>
1541 ::value_type
*, Comparator
, _DifferenceTp
>,
1542 static_cast<difference_type
>(length
), comp
, tag
.get_num_threads());
1544 return sequential_multiway_merge
1545 </* stable = */ false, /* sentinels = */ false>(
1546 seqs_begin
, seqs_end
, target
, *(seqs_begin
->second
), length
, comp
);
1551 typename RandomAccessIteratorPairIterator
1552 , typename RandomAccessIteratorOut
1553 , typename _DifferenceTp
1554 , typename Comparator
>
1555 RandomAccessIteratorOut
1556 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1557 , RandomAccessIteratorPairIterator seqs_end
1558 , RandomAccessIteratorOut target
1559 , _DifferenceTp length
, Comparator comp
1560 , __gnu_parallel::sampling_tag tag
)
1562 typedef _DifferenceTp difference_type
;
1563 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1565 // catch special case: no sequences
1566 if (seqs_begin
== seqs_end
)
1569 // Execute merge; maybe parallel, depending on the number of merged
1570 // elements and the number of sequences and global thresholds in
1572 if ((seqs_end
- seqs_begin
> 1) &&
1573 _GLIBCXX_PARALLEL_CONDITION(
1574 ((seqs_end
- seqs_begin
) >=
1575 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1576 && ((sequence_index_t
)length
>=
1577 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1578 return parallel_multiway_merge
1579 </* stable = */ false, /* sentinels = */ false>(
1580 seqs_begin
, seqs_end
,
1582 multiway_merge_exact_splitting
</* stable = */ false,
1583 typename
std::iterator_traits
<RandomAccessIteratorPairIterator
>
1584 ::value_type
*, Comparator
, _DifferenceTp
>,
1585 static_cast<difference_type
>(length
), comp
, tag
.get_num_threads());
1587 return sequential_multiway_merge
1588 </* stable = */ false, /* sentinels = */ false>(
1589 seqs_begin
, seqs_end
,
1590 target
, *(seqs_begin
->second
), length
, comp
);
1595 typename RandomAccessIteratorPairIterator
1596 , typename RandomAccessIteratorOut
1597 , typename _DifferenceTp
1598 , typename Comparator
>
1599 RandomAccessIteratorOut
1600 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1601 , RandomAccessIteratorPairIterator seqs_end
1602 , RandomAccessIteratorOut target
1603 , _DifferenceTp length
, Comparator comp
1604 , parallel_tag tag
= parallel_tag(0))
1606 return multiway_merge(seqs_begin
, seqs_end
, target
, length
, comp
,
1607 exact_tag(tag
.get_num_threads()));
1612 typename RandomAccessIteratorPairIterator
1613 , typename RandomAccessIteratorOut
1614 , typename _DifferenceTp
1615 , typename Comparator
>
1616 RandomAccessIteratorOut
1617 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1618 , RandomAccessIteratorPairIterator seqs_end
1619 , RandomAccessIteratorOut target
1620 , _DifferenceTp length
, Comparator comp
1621 , default_parallel_tag tag
)
1623 return multiway_merge(seqs_begin
, seqs_end
, target
, length
, comp
,
1624 exact_tag(tag
.get_num_threads()));
1627 // stable_multiway_merge
1630 typename RandomAccessIteratorPairIterator
1631 , typename RandomAccessIteratorOut
1632 , typename _DifferenceTp
1633 , typename Comparator
>
1634 RandomAccessIteratorOut
1635 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1636 , RandomAccessIteratorPairIterator seqs_end
1637 , RandomAccessIteratorOut target
1638 , _DifferenceTp length
, Comparator comp
1639 , __gnu_parallel::sequential_tag
)
1641 typedef _DifferenceTp difference_type
;
1642 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1644 // catch special case: no sequences
1645 if (seqs_begin
== seqs_end
)
1648 // Execute multiway merge *sequentially*.
1649 return sequential_multiway_merge
1650 </* stable = */ true, /* sentinels = */ false>
1651 (seqs_begin
, seqs_end
, target
, *(seqs_begin
->second
), length
, comp
);
1656 typename RandomAccessIteratorPairIterator
1657 , typename RandomAccessIteratorOut
1658 , typename _DifferenceTp
1659 , typename Comparator
>
1660 RandomAccessIteratorOut
1661 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1662 , RandomAccessIteratorPairIterator seqs_end
1663 , RandomAccessIteratorOut target
1664 , _DifferenceTp length
, Comparator comp
1665 , __gnu_parallel::exact_tag tag
)
1667 typedef _DifferenceTp difference_type
;
1668 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1670 // catch special case: no sequences
1671 if (seqs_begin
== seqs_end
)
1674 // Execute merge; maybe parallel, depending on the number of merged
1675 // elements and the number of sequences and global thresholds in
1677 if ((seqs_end
- seqs_begin
> 1) &&
1678 _GLIBCXX_PARALLEL_CONDITION(
1679 ((seqs_end
- seqs_begin
) >=
1680 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1681 && ((sequence_index_t
)length
>=
1682 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1683 return parallel_multiway_merge
1684 </* stable = */ true, /* sentinels = */ false>(
1685 seqs_begin
, seqs_end
,
1687 multiway_merge_exact_splitting
</* stable = */ true,
1688 typename
std::iterator_traits
<RandomAccessIteratorPairIterator
>
1689 ::value_type
*, Comparator
, _DifferenceTp
>,
1690 static_cast<difference_type
>(length
), comp
, tag
.get_num_threads());
1692 return sequential_multiway_merge
</* stable = */ true,
1693 /* sentinels = */ false>(
1694 seqs_begin
, seqs_end
,
1695 target
, *(seqs_begin
->second
), length
, comp
);
1700 typename RandomAccessIteratorPairIterator
1701 , typename RandomAccessIteratorOut
1702 , typename _DifferenceTp
1703 , typename Comparator
>
1704 RandomAccessIteratorOut
1705 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1706 , RandomAccessIteratorPairIterator seqs_end
1707 , RandomAccessIteratorOut target
1708 , _DifferenceTp length
, Comparator comp
1711 typedef _DifferenceTp difference_type
;
1712 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1714 // catch special case: no sequences
1715 if (seqs_begin
== seqs_end
)
1718 // Execute merge; maybe parallel, depending on the number of merged
1719 // elements and the number of sequences and global thresholds in
1721 if ((seqs_end
- seqs_begin
> 1) &&
1722 _GLIBCXX_PARALLEL_CONDITION(
1723 ((seqs_end
- seqs_begin
) >=
1724 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1725 && ((sequence_index_t
)length
>=
1726 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1727 return parallel_multiway_merge
1728 </* stable = */ true, /* sentinels = */ false>(
1729 seqs_begin
, seqs_end
,
1731 multiway_merge_sampling_splitting
</* stable = */ true,
1732 typename
std::iterator_traits
<RandomAccessIteratorPairIterator
>
1733 ::value_type
*, Comparator
, _DifferenceTp
>,
1734 static_cast<difference_type
>(length
), comp
, tag
.get_num_threads());
1736 return sequential_multiway_merge
1737 </* stable = */ true, /* sentinels = */ false>(
1738 seqs_begin
, seqs_end
,
1739 target
, *(seqs_begin
->second
), length
, comp
);
1745 typename RandomAccessIteratorPairIterator
1746 , typename RandomAccessIteratorOut
1747 , typename _DifferenceTp
1748 , typename Comparator
>
1749 RandomAccessIteratorOut
1750 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1751 , RandomAccessIteratorPairIterator seqs_end
1752 , RandomAccessIteratorOut target
1753 , _DifferenceTp length
, Comparator comp
1754 , parallel_tag tag
= parallel_tag(0))
1756 return stable_multiway_merge(seqs_begin
, seqs_end
, target
, length
, comp
,
1757 exact_tag(tag
.get_num_threads()));
1762 typename RandomAccessIteratorPairIterator
1763 , typename RandomAccessIteratorOut
1764 , typename _DifferenceTp
1765 , typename Comparator
>
1766 RandomAccessIteratorOut
1767 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1768 , RandomAccessIteratorPairIterator seqs_end
1769 , RandomAccessIteratorOut target
1770 , _DifferenceTp length
, Comparator comp
1771 , default_parallel_tag tag
)
1773 return stable_multiway_merge(seqs_begin
, seqs_end
, target
, length
, comp
,
1774 exact_tag(tag
.get_num_threads()));
1778 * @brief Multiway Merge Frontend.
1780 * Merge the sequences specified by seqs_begin and seqs_end into
1781 * target. seqs_begin and seqs_end must point to a sequence of
1782 * pairs. These pairs must contain an iterator to the beginning
1783 * of a sequence in their first entry and an iterator the end of
1784 * the same sequence in their second entry.
1786 * Ties are broken arbitrarily. See stable_multiway_merge for a variant
1787 * that breaks ties by sequence number but is slower.
1789 * The first entries of the pairs (i.e. the begin iterators) will be moved
1790 * forward accordingly.
1792 * The output sequence has to provide enough space for all elements
1793 * that are written to it.
1795 * This function will merge the input sequences:
1798 * - parallel, depending on the input size and Settings
1799 * - using sampling for splitting
1802 * You have to take care that the element the end iterator points to is
1803 * readable and contains a value that is greater than any other non-sentinel
1804 * value in all sequences.
1809 * int sequences[10][11];
1810 * for (int i = 0; i < 10; ++i)
1811 * for (int j = 0; i < 11; ++j)
1812 * sequences[i][j] = j; // last one is sentinel!
1815 * std::vector<std::pair<int*> > seqs;
1816 * for (int i = 0; i < 10; ++i)
1817 * { seqs.push(std::make_pair<int*>(sequences[i], sequences[i] + 10)) }
1819 * multiway_merge(seqs.begin(), seqs.end(), target, std::less<int>(), 33);
1822 * @pre All input sequences must be sorted.
1823 * @pre Target must provide enough space to merge out length elements or
1824 * the number of elements in all sequences, whichever is smaller.
1825 * @pre For each @c i, @c seqs_begin[i].second must be the end
1826 * marker of the sequence, but also reference the one more sentinel
1829 * @post [target, return value) contains merged elements from the
1831 * @post return value - target = min(length, number of elements in all
1834 * @see stable_multiway_merge_sentinels
1836 * @param RandomAccessIteratorPairIterator iterator over sequence
1837 * of pairs of iterators
1838 * @param RandomAccessIteratorOut iterator over target sequence
1839 * @param _DifferenceTp difference type for the sequence
1840 * @param Comparator strict weak ordering type to compare elements
1843 * @param seqs_begin begin of sequence sequence
1844 * @param seqs_end end of sequence sequence
1845 * @param target target sequence to merge to.
1846 * @param comp strict weak ordering to use for element comparison.
1847 * @param length Maximum length to merge, possibly larger than the
1848 * number of elements available.
1850 * @return end iterator of output sequence
1852 // multiway_merge_sentinels
1855 typename RandomAccessIteratorPairIterator
1856 , typename RandomAccessIteratorOut
1857 , typename _DifferenceTp
1858 , typename Comparator
>
1859 RandomAccessIteratorOut
1860 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1861 , RandomAccessIteratorPairIterator seqs_end
1862 , RandomAccessIteratorOut target
1863 , _DifferenceTp length
, Comparator comp
1864 , __gnu_parallel::sequential_tag
)
1866 typedef _DifferenceTp difference_type
;
1867 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1869 // catch special case: no sequences
1870 if (seqs_begin
== seqs_end
)
1873 // Execute multiway merge *sequentially*.
1874 return sequential_multiway_merge
1875 </* stable = */ false, /* sentinels = */ true>
1876 (seqs_begin
, seqs_end
,
1877 target
, *(seqs_begin
->second
), length
, comp
);
1882 typename RandomAccessIteratorPairIterator
1883 , typename RandomAccessIteratorOut
1884 , typename _DifferenceTp
1885 , typename Comparator
>
1886 RandomAccessIteratorOut
1887 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1888 , RandomAccessIteratorPairIterator seqs_end
1889 , RandomAccessIteratorOut target
1890 , _DifferenceTp length
, Comparator comp
1891 , __gnu_parallel::exact_tag tag
)
1893 typedef _DifferenceTp difference_type
;
1894 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1896 // catch special case: no sequences
1897 if (seqs_begin
== seqs_end
)
1900 // Execute merge; maybe parallel, depending on the number of merged
1901 // elements and the number of sequences and global thresholds in
1903 if ((seqs_end
- seqs_begin
> 1) &&
1904 _GLIBCXX_PARALLEL_CONDITION(
1905 ((seqs_end
- seqs_begin
) >=
1906 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1907 && ((sequence_index_t
)length
>=
1908 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1909 return parallel_multiway_merge
1910 </* stable = */ false, /* sentinels = */ true>(
1911 seqs_begin
, seqs_end
,
1913 multiway_merge_exact_splitting
</* stable = */ false,
1914 typename
std::iterator_traits
<RandomAccessIteratorPairIterator
>
1915 ::value_type
*, Comparator
, _DifferenceTp
>,
1916 static_cast<difference_type
>(length
), comp
, tag
.get_num_threads());
1918 return sequential_multiway_merge
1919 </* stable = */ false, /* sentinels = */ true>(
1920 seqs_begin
, seqs_end
,
1921 target
, *(seqs_begin
->second
), length
, comp
);
1926 typename RandomAccessIteratorPairIterator
1927 , typename RandomAccessIteratorOut
1928 , typename _DifferenceTp
1929 , typename Comparator
>
1930 RandomAccessIteratorOut
1931 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1932 , RandomAccessIteratorPairIterator seqs_end
1933 , RandomAccessIteratorOut target
1934 , _DifferenceTp length
, Comparator comp
1937 typedef _DifferenceTp difference_type
;
1938 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1940 // catch special case: no sequences
1941 if (seqs_begin
== seqs_end
)
1944 // Execute merge; maybe parallel, depending on the number of merged
1945 // elements and the number of sequences and global thresholds in
1947 if ((seqs_end
- seqs_begin
> 1) &&
1948 _GLIBCXX_PARALLEL_CONDITION(
1949 ((seqs_end
- seqs_begin
) >=
1950 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1951 && ((sequence_index_t
)length
>=
1952 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1953 return parallel_multiway_merge
1954 </* stable = */ false, /* sentinels = */ true>
1955 (seqs_begin
, seqs_end
, target
,
1956 multiway_merge_sampling_splitting
</* stable = */ false,
1957 typename
std::iterator_traits
<RandomAccessIteratorPairIterator
>
1958 ::value_type
*, Comparator
, _DifferenceTp
>,
1959 static_cast<difference_type
>(length
), comp
, tag
.get_num_threads());
1961 return sequential_multiway_merge
1962 </* stable = */false, /* sentinels = */ true>(
1963 seqs_begin
, seqs_end
,
1964 target
, *(seqs_begin
->second
), length
, comp
);
1969 typename RandomAccessIteratorPairIterator
1970 , typename RandomAccessIteratorOut
1971 , typename _DifferenceTp
1972 , typename Comparator
>
1973 RandomAccessIteratorOut
1974 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1975 , RandomAccessIteratorPairIterator seqs_end
1976 , RandomAccessIteratorOut target
1977 , _DifferenceTp length
, Comparator comp
1978 , parallel_tag tag
= parallel_tag(0))
1980 return multiway_merge_sentinels(seqs_begin
, seqs_end
, target
, length
, comp
,
1981 exact_tag(tag
.get_num_threads()));
1986 typename RandomAccessIteratorPairIterator
1987 , typename RandomAccessIteratorOut
1988 , typename _DifferenceTp
1989 , typename Comparator
>
1990 RandomAccessIteratorOut
1991 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1992 , RandomAccessIteratorPairIterator seqs_end
1993 , RandomAccessIteratorOut target
1994 , _DifferenceTp length
, Comparator comp
1995 , default_parallel_tag tag
)
1997 return multiway_merge_sentinels(seqs_begin
, seqs_end
, target
, length
, comp
,
1998 exact_tag(tag
.get_num_threads()));
2001 // stable_multiway_merge_sentinels
2004 typename RandomAccessIteratorPairIterator
2005 , typename RandomAccessIteratorOut
2006 , typename _DifferenceTp
2007 , typename Comparator
>
2008 RandomAccessIteratorOut
2009 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
2010 , RandomAccessIteratorPairIterator seqs_end
2011 , RandomAccessIteratorOut target
2012 , _DifferenceTp length
, Comparator comp
2013 , __gnu_parallel::sequential_tag
)
2015 typedef _DifferenceTp difference_type
;
2016 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
2018 // catch special case: no sequences
2019 if (seqs_begin
== seqs_end
)
2022 // Execute multiway merge *sequentially*.
2023 return sequential_multiway_merge
2024 </* stable = */ true, /* sentinels = */ true>
2025 (seqs_begin
, seqs_end
, target
, *(seqs_begin
->second
), length
, comp
);
2030 typename RandomAccessIteratorPairIterator
2031 , typename RandomAccessIteratorOut
2032 , typename _DifferenceTp
2033 , typename Comparator
>
2034 RandomAccessIteratorOut
2035 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
2036 , RandomAccessIteratorPairIterator seqs_end
2037 , RandomAccessIteratorOut target
2038 , _DifferenceTp length
, Comparator comp
2039 , __gnu_parallel::exact_tag tag
)
2041 typedef _DifferenceTp difference_type
;
2042 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
2044 // catch special case: no sequences
2045 if (seqs_begin
== seqs_end
)
2048 // Execute merge; maybe parallel, depending on the number of merged
2049 // elements and the number of sequences and global thresholds in
2051 if ((seqs_end
- seqs_begin
> 1) &&
2052 _GLIBCXX_PARALLEL_CONDITION(
2053 ((seqs_end
- seqs_begin
) >=
2054 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
2055 && ((sequence_index_t
)length
>=
2056 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
2057 return parallel_multiway_merge
2058 </* stable = */ true, /* sentinels = */ true>(
2059 seqs_begin
, seqs_end
,
2061 multiway_merge_exact_splitting
</* stable = */ true,
2062 typename
std::iterator_traits
<RandomAccessIteratorPairIterator
>
2063 ::value_type
*, Comparator
, _DifferenceTp
>,
2064 static_cast<difference_type
>(length
), comp
, tag
.get_num_threads());
2066 return sequential_multiway_merge
2067 </* stable = */ true, /* sentinels = */ true>(
2068 seqs_begin
, seqs_end
, target
, *(seqs_begin
->second
), length
, comp
);
2073 typename RandomAccessIteratorPairIterator
2074 , typename RandomAccessIteratorOut
2075 , typename _DifferenceTp
2076 , typename Comparator
>
2077 RandomAccessIteratorOut
2078 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
2079 , RandomAccessIteratorPairIterator seqs_end
2080 , RandomAccessIteratorOut target
2081 , _DifferenceTp length
, Comparator comp
2084 typedef _DifferenceTp difference_type
;
2085 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
2087 // catch special case: no sequences
2088 if (seqs_begin
== seqs_end
)
2091 // Execute merge; maybe parallel, depending on the number of merged
2092 // elements and the number of sequences and global thresholds in
2094 if ((seqs_end
- seqs_begin
> 1) &&
2095 _GLIBCXX_PARALLEL_CONDITION(
2096 ((seqs_end
- seqs_begin
) >=
2097 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
2098 && ((sequence_index_t
)length
>=
2099 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
2100 return parallel_multiway_merge
2101 </* stable = */ true, /* sentinels = */ true>(
2102 seqs_begin
, seqs_end
,
2104 multiway_merge_sampling_splitting
</* stable = */ true,
2105 typename
std::iterator_traits
<RandomAccessIteratorPairIterator
>
2106 ::value_type
*, Comparator
, _DifferenceTp
>,
2107 static_cast<difference_type
>(length
), comp
, tag
.get_num_threads());
2109 return sequential_multiway_merge
2110 </* stable = */ true, /* sentinels = */ true>(
2111 seqs_begin
, seqs_end
,
2112 target
, *(seqs_begin
->second
), length
, comp
);
2117 typename RandomAccessIteratorPairIterator
2118 , typename RandomAccessIteratorOut
2119 , typename _DifferenceTp
2120 , typename Comparator
>
2121 RandomAccessIteratorOut
2122 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
2123 , RandomAccessIteratorPairIterator seqs_end
2124 , RandomAccessIteratorOut target
2125 , _DifferenceTp length
, Comparator comp
2126 , parallel_tag tag
= parallel_tag(0))
2128 return stable_multiway_merge_sentinels(seqs_begin
, seqs_end
, target
, length
, comp
,
2129 exact_tag(tag
.get_num_threads()));
2134 typename RandomAccessIteratorPairIterator
2135 , typename RandomAccessIteratorOut
2136 , typename _DifferenceTp
2137 , typename Comparator
>
2138 RandomAccessIteratorOut
2139 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
2140 , RandomAccessIteratorPairIterator seqs_end
2141 , RandomAccessIteratorOut target
2142 , _DifferenceTp length
, Comparator comp
2143 , default_parallel_tag tag
)
2145 return stable_multiway_merge_sentinels(seqs_begin
, seqs_end
, target
, length
, comp
,
2146 exact_tag(tag
.get_num_threads()));
2149 }; // namespace __gnu_parallel
2151 #endif /* _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H */