3 // Copyright (C) 2007 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.
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/merge.h>
54 #include <parallel/losertree.h>
55 #if _GLIBCXX_ASSERTIONS
56 #include <parallel/checkers.h>
59 /** @brief Length of a sequence described by a pair of iterators. */
60 #define _GLIBCXX_PARALLEL_LENGTH(s) ((s).second - (s).first)
62 // XXX need iterator typedefs
63 namespace __gnu_parallel
65 template<typename RandomAccessIterator
, typename Comparator
>
66 class guarded_iterator
;
68 template<typename RandomAccessIterator
, typename Comparator
>
70 operator<(guarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
71 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
73 template<typename RandomAccessIterator
, typename Comparator
>
75 operator<=(guarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
76 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
78 /** @brief Iterator wrapper supporting an implicit supremum at the end
79 of the sequence, dominating all comparisons.
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 inline guarded_iterator(RandomAccessIterator begin
,
103 RandomAccessIterator end
, Comparator
& comp
)
104 : current(begin
), end(end
), comp(comp
)
107 /** @brief Pre-increment operator.
109 inline guarded_iterator
<RandomAccessIterator
, Comparator
>&
116 /** @brief Dereference operator.
117 * @return Referenced element. */
118 inline typename
std::iterator_traits
<RandomAccessIterator
>::value_type
122 /** @brief Convert to wrapped iterator.
123 * @return Wrapped iterator. */
124 inline 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 inline unguarded_iterator(RandomAccessIterator begin
,
198 RandomAccessIterator end
, Comparator
& comp
)
199 : current(begin
), comp(comp
)
202 /** @brief Pre-increment operator.
204 inline unguarded_iterator
<RandomAccessIterator
, Comparator
>&
211 /** @brief Dereference operator.
212 * @return Referenced element. */
213 inline typename
std::iterator_traits
<RandomAccessIterator
>::value_type
217 /** @brief Convert to wrapped iterator.
218 * @return Wrapped iterator. */
220 operator RandomAccessIterator()
224 operator< <RandomAccessIterator
, Comparator
>(
225 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
226 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
229 operator<= <RandomAccessIterator
, Comparator
>(
230 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
231 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
234 /** @brief Compare two elements referenced by unguarded iterators.
235 * @param bi1 First iterator.
236 * @param bi2 Second iterator.
237 * @return @c True if less. */
238 template<typename RandomAccessIterator
, typename Comparator
>
240 operator<(unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
241 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
)
244 return (bi1
.comp
)(*bi1
, *bi2
);
247 /** @brief Compare two elements referenced by unguarded iterators.
248 * @param bi1 First iterator.
249 * @param bi2 Second iterator.
250 * @return @c True if less equal. */
251 template<typename RandomAccessIterator
, typename Comparator
>
253 operator<=(unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
254 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
)
257 return !(bi1
.comp
)(*bi2
, *bi1
);
260 /** Prepare a set of sequences to be merged without a (end) guard
264 * @param min_sequence
266 * @pre (seqs_end - seqs_begin > 0) */
267 template<typename RandomAccessIteratorIterator
, typename Comparator
>
268 typename
std::iterator_traits
<
269 typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type
270 ::first_type
>::difference_type
271 prepare_unguarded(RandomAccessIteratorIterator seqs_begin
,
272 RandomAccessIteratorIterator seqs_end
, Comparator comp
,
273 int& min_sequence
, bool stable
)
275 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
277 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
278 ::value_type::first_type
279 RandomAccessIterator1
;
280 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
282 typedef typename
std::iterator_traits
<RandomAccessIterator1
>
286 if ((*seqs_begin
).first
== (*seqs_begin
).second
)
288 // Empty sequence found, it's the first one.
293 // Last element in sequence.
294 value_type min
= *((*seqs_begin
).second
- 1);
296 for (RandomAccessIteratorIterator s
= seqs_begin
+ 1; s
!= seqs_end
; ++s
)
298 if ((*s
).first
== (*s
).second
)
300 // Empty sequence found.
301 min_sequence
= static_cast<int>(s
- seqs_begin
);
305 // Last element in sequence.
306 const value_type
& v
= *((*s
).second
- 1);
307 if (comp(v
, min
)) //strictly smaller
310 min_sequence
= static_cast<int>(s
- seqs_begin
);
314 difference_type overhang_size
= 0;
317 for (s
= 0; s
<= min_sequence
; ++s
)
319 RandomAccessIterator1 split
;
321 split
= std::upper_bound(seqs_begin
[s
].first
, seqs_begin
[s
].second
,
324 split
= std::lower_bound(seqs_begin
[s
].first
, seqs_begin
[s
].second
,
327 overhang_size
+= seqs_begin
[s
].second
- split
;
330 for (; s
< (seqs_end
- seqs_begin
); ++s
)
332 RandomAccessIterator1 split
= std::lower_bound(
333 seqs_begin
[s
].first
, seqs_begin
[s
].second
, min
, comp
);
334 overhang_size
+= seqs_begin
[s
].second
- split
;
337 // So many elements will be left over afterwards.
338 return overhang_size
;
341 /** Prepare a set of sequences to be merged with a (end) guard (sentinel)
345 template<typename RandomAccessIteratorIterator
, typename Comparator
>
346 typename
std::iterator_traits
<typename
std::iterator_traits
<
347 RandomAccessIteratorIterator
>::value_type::first_type
>::difference_type
348 prepare_unguarded_sentinel(RandomAccessIteratorIterator seqs_begin
,
349 RandomAccessIteratorIterator seqs_end
,
352 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
354 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
355 ::value_type::first_type
356 RandomAccessIterator1
;
357 typedef typename
std::iterator_traits
<RandomAccessIterator1
>
360 typedef typename
std::iterator_traits
<RandomAccessIterator1
>
364 // Last element in sequence.
365 value_type
* max
= NULL
;
366 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; ++s
)
368 if ((*s
).first
== (*s
).second
)
371 // Last element in sequence.
372 value_type
& v
= *((*s
).second
- 1);
375 if (!max
|| comp(*max
, v
))
379 difference_type overhang_size
= 0;
380 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; ++s
)
382 RandomAccessIterator1 split
=
383 std::lower_bound((*s
).first
, (*s
).second
, *max
, comp
);
384 overhang_size
+= (*s
).second
- split
;
387 *((*s
).second
) = *max
;
390 // So many elements will be left over afterwards.
391 return overhang_size
;
394 /** @brief Highly efficient 3-way merging procedure.
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.
400 * @param stable Unused, stable anyway.
401 * @return End iterator of output sequence. */
403 template<typename RAI
, typename C
> class iterator
,
404 typename RandomAccessIteratorIterator
,
405 typename RandomAccessIterator3
,
406 typename _DifferenceTp
,
408 RandomAccessIterator3
409 multiway_merge_3_variant(
410 RandomAccessIteratorIterator seqs_begin
,
411 RandomAccessIteratorIterator seqs_end
,
412 RandomAccessIterator3 target
,
413 Comparator comp
, _DifferenceTp length
, bool stable
)
415 _GLIBCXX_CALL(length
);
417 typedef _DifferenceTp difference_type
;
419 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
420 ::value_type::first_type
421 RandomAccessIterator1
;
422 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
428 iterator
<RandomAccessIterator1
, Comparator
>
429 seq0(seqs_begin
[0].first
, seqs_begin
[0].second
, comp
),
430 seq1(seqs_begin
[1].first
, seqs_begin
[1].second
, comp
),
431 seq2(seqs_begin
[2].first
, seqs_begin
[2].second
, comp
);
456 #define _GLIBCXX_PARALLEL_MERGE_3_CASE(a,b,c,c0,c1)\
458 *target = *seq ## a; \
462 if (length == 0) goto finish; \
463 if (seq ## a c0 seq ## b) goto s ## a ## b ## c; \
464 if (seq ## a c1 seq ## c) goto s ## b ## a ## c; \
465 goto s ## b ## c ## a;
467 _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 1, 2, <=, <=);
468 _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 2, 0, <=, < );
469 _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 0, 1, < , < );
470 _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 0, 2, < , <=);
471 _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 2, 1, <=, <=);
472 _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 1, 0, < , < );
474 #undef _GLIBCXX_PARALLEL_MERGE_3_CASE
479 seqs_begin
[0].first
= seq0
;
480 seqs_begin
[1].first
= seq1
;
481 seqs_begin
[2].first
= seq2
;
487 typename RandomAccessIteratorIterator
,
488 typename RandomAccessIterator3
,
489 typename _DifferenceTp
,
491 RandomAccessIterator3
492 multiway_merge_3_combined(RandomAccessIteratorIterator seqs_begin
,
493 RandomAccessIteratorIterator seqs_end
,
494 RandomAccessIterator3 target
,
496 _DifferenceTp length
, bool stable
)
498 _GLIBCXX_CALL(length
);
500 typedef _DifferenceTp difference_type
;
501 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
502 ::value_type::first_type
503 RandomAccessIterator1
;
504 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
508 RandomAccessIterator3 target_end
;
511 difference_type overhang
=
512 prepare_unguarded(seqs_begin
, seqs_end
, comp
, min_seq
, true);
514 difference_type total_length
= 0;
515 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; ++s
)
516 total_length
+= _GLIBCXX_PARALLEL_LENGTH(*s
);
520 difference_type unguarded_length
=
521 std::min(length
, total_length
- overhang
);
522 target_end
= multiway_merge_3_variant
<unguarded_iterator
>
523 (seqs_begin
, seqs_end
, target
, comp
, unguarded_length
, stable
);
524 overhang
= length
- unguarded_length
;
528 // Empty sequence found.
533 #if _GLIBCXX_ASSERTIONS
534 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
- overhang
);
535 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
541 // Iterators will be advanced accordingly.
542 target_end
= merge_advance(seqs_begin
[1].first
, seqs_begin
[1].second
,
543 seqs_begin
[2].first
, seqs_begin
[2].second
,
544 target_end
, overhang
, comp
);
547 target_end
= merge_advance(seqs_begin
[0].first
, seqs_begin
[0].second
,
548 seqs_begin
[2].first
, seqs_begin
[2].second
,
549 target_end
, overhang
, comp
);
552 target_end
= merge_advance(seqs_begin
[0].first
, seqs_begin
[0].second
,
553 seqs_begin
[1].first
, seqs_begin
[1].second
,
554 target_end
, overhang
, comp
);
557 _GLIBCXX_PARALLEL_ASSERT(false);
560 #if _GLIBCXX_ASSERTIONS
561 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
);
562 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
568 /** @brief Highly efficient 4-way merging procedure.
569 * @param seqs_begin Begin iterator of iterator pair input sequence.
570 * @param seqs_end End iterator of iterator pair input sequence.
571 * @param target Begin iterator out output sequence.
572 * @param comp Comparator.
573 * @param length Maximum length to merge.
574 * @param stable Unused, stable anyway.
575 * @return End iterator of output sequence. */
577 template<typename RAI
, typename C
> class iterator
,
578 typename RandomAccessIteratorIterator
,
579 typename RandomAccessIterator3
,
580 typename _DifferenceTp
,
582 RandomAccessIterator3
583 multiway_merge_4_variant(RandomAccessIteratorIterator seqs_begin
,
584 RandomAccessIteratorIterator seqs_end
,
585 RandomAccessIterator3 target
,
586 Comparator comp
, _DifferenceTp length
, bool stable
)
588 _GLIBCXX_CALL(length
);
589 typedef _DifferenceTp difference_type
;
591 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
592 ::value_type::first_type
593 RandomAccessIterator1
;
594 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
597 iterator
<RandomAccessIterator1
, Comparator
>
598 seq0(seqs_begin
[0].first
, seqs_begin
[0].second
, comp
),
599 seq1(seqs_begin
[1].first
, seqs_begin
[1].second
, comp
),
600 seq2(seqs_begin
[2].first
, seqs_begin
[2].second
, comp
),
601 seq3(seqs_begin
[3].first
, seqs_begin
[3].second
, comp
);
603 #define _GLIBCXX_PARALLEL_DECISION(a,b,c,d) { \
604 if (seq ## d < seq ## a) goto s ## d ## a ## b ## c; \
605 if (seq ## d < seq ## b) goto s ## a ## d ## b ## c; \
606 if (seq ## d < seq ## c) goto s ## a ## b ## d ## c; \
607 goto s ## a ## b ## c ## d; }
612 _GLIBCXX_PARALLEL_DECISION(0,1,2,3)
615 _GLIBCXX_PARALLEL_DECISION(2,0,1,3)
617 _GLIBCXX_PARALLEL_DECISION(0,2,1,3)
624 _GLIBCXX_PARALLEL_DECISION(1,0,2,3)
626 _GLIBCXX_PARALLEL_DECISION(1,2,0,3)
629 _GLIBCXX_PARALLEL_DECISION(2,1,0,3)
632 #define _GLIBCXX_PARALLEL_MERGE_4_CASE(a,b,c,d,c0,c1,c2) \
633 s ## a ## b ## c ## d: \
634 if (length == 0) goto finish; \
635 *target = *seq ## a; \
639 if (seq ## a c0 seq ## b) goto s ## a ## b ## c ## d; \
640 if (seq ## a c1 seq ## c) goto s ## b ## a ## c ## d; \
641 if (seq ## a c2 seq ## d) goto s ## b ## c ## a ## d; \
642 goto s ## b ## c ## d ## a;
644 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 2, 3, <=, <=, <=);
645 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 3, 2, <=, <=, <=);
646 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 1, 3, <=, <=, <=);
647 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 3, 1, <=, <=, <=);
648 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 1, 2, <=, <=, <=);
649 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 2, 1, <=, <=, <=);
650 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 2, 3, < , <=, <=);
651 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 3, 2, < , <=, <=);
652 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 0, 3, <=, < , <=);
653 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 3, 0, <=, <=, < );
654 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 0, 2, <=, < , <=);
655 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 2, 0, <=, <=, < );
656 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 1, 3, < , < , <=);
657 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 3, 1, < , <=, < );
658 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 0, 3, < , < , <=);
659 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 3, 0, < , <=, < );
660 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 0, 1, <=, < , < );
661 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 1, 0, <=, < , < );
662 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 1, 2, < , < , < );
663 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 2, 1, < , < , < );
664 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 0, 2, < , < , < );
665 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 2, 0, < , < , < );
666 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 0, 1, < , < , < );
667 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 1, 0, < , < , < );
669 #undef _GLIBCXX_PARALLEL_MERGE_4_CASE
670 #undef _GLIBCXX_PARALLEL_DECISION
675 seqs_begin
[0].first
= seq0
;
676 seqs_begin
[1].first
= seq1
;
677 seqs_begin
[2].first
= seq2
;
678 seqs_begin
[3].first
= seq3
;
684 typename RandomAccessIteratorIterator
,
685 typename RandomAccessIterator3
,
686 typename _DifferenceTp
,
688 RandomAccessIterator3
689 multiway_merge_4_combined(RandomAccessIteratorIterator seqs_begin
,
690 RandomAccessIteratorIterator seqs_end
,
691 RandomAccessIterator3 target
,
693 _DifferenceTp length
, bool stable
)
695 _GLIBCXX_CALL(length
);
696 typedef _DifferenceTp difference_type
;
698 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
699 ::value_type::first_type
700 RandomAccessIterator1
;
701 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
705 RandomAccessIterator3 target_end
;
708 difference_type overhang
=
709 prepare_unguarded(seqs_begin
, seqs_end
, comp
, min_seq
, true);
711 difference_type total_length
= 0;
712 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; ++s
)
713 total_length
+= _GLIBCXX_PARALLEL_LENGTH(*s
);
717 difference_type unguarded_length
=
718 std::min(length
, total_length
- overhang
);
719 target_end
= multiway_merge_4_variant
<unguarded_iterator
>
720 (seqs_begin
, seqs_end
, target
, comp
, unguarded_length
, stable
);
721 overhang
= length
- unguarded_length
;
725 // Empty sequence found.
730 #if _GLIBCXX_ASSERTIONS
731 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
- overhang
);
732 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
735 std::vector
<std::pair
<RandomAccessIterator1
, RandomAccessIterator1
> >
736 one_missing(seqs_begin
, seqs_end
);
737 one_missing
.erase(one_missing
.begin() + min_seq
); //remove
739 target_end
= multiway_merge_3_variant
<guarded_iterator
>(
740 one_missing
.begin(), one_missing
.end(),
741 target_end
, comp
, overhang
, stable
);
743 // Insert back again.
744 one_missing
.insert(one_missing
.begin() + min_seq
, seqs_begin
[min_seq
]);
745 // Write back modified iterators.
746 copy(one_missing
.begin(), one_missing
.end(), seqs_begin
);
748 #if _GLIBCXX_ASSERTIONS
749 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
);
750 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
756 /** @brief Basic multi-way merging procedure.
758 * The head elements are kept in a sorted array, new heads are
760 * @param seqs_begin Begin iterator of iterator pair input sequence.
761 * @param seqs_end End iterator of iterator pair input sequence.
762 * @param target Begin iterator out output sequence.
763 * @param comp Comparator.
764 * @param length Maximum length to merge.
765 * @param stable Stable merging incurs a performance penalty.
766 * @return End iterator of output sequence.
769 typename RandomAccessIteratorIterator
,
770 typename RandomAccessIterator3
,
771 typename _DifferenceTp
,
773 RandomAccessIterator3
774 multiway_merge_bubble(RandomAccessIteratorIterator seqs_begin
,
775 RandomAccessIteratorIterator seqs_end
,
776 RandomAccessIterator3 target
,
777 Comparator comp
, _DifferenceTp length
, bool stable
)
779 _GLIBCXX_CALL(length
)
781 typedef _DifferenceTp difference_type
;
782 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
783 ::value_type::first_type
784 RandomAccessIterator1
;
785 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
788 int k
= static_cast<int>(seqs_end
- seqs_begin
);
789 int nrs
; // Number of remaining sequences.
791 // Avoid default constructor.
792 value_type
* fe
= static_cast<value_type
*>(
793 ::operator new(sizeof(value_type
) * k
)); // Front elements.
794 int* source
= new int[k
];
795 difference_type total_length
= 0;
797 // Write entries into queue.
799 for (int pi
= 0; pi
< k
; ++pi
)
801 if (seqs_begin
[pi
].first
!= seqs_begin
[pi
].second
)
803 ::new(&(fe
[nrs
])) value_type(*(seqs_begin
[pi
].first
));
806 total_length
+= _GLIBCXX_PARALLEL_LENGTH(seqs_begin
[pi
]);
812 // Bubble sort fe and source by fe.
813 for (int k
= 0; k
< nrs
- 1; ++k
)
814 for (int pi
= nrs
- 1; pi
> k
; --pi
)
815 if (comp(fe
[pi
], fe
[pi
- 1]) ||
816 (!comp(fe
[pi
- 1], fe
[pi
]) && source
[pi
] < source
[pi
- 1]))
818 std::swap(fe
[pi
- 1], fe
[pi
]);
819 std::swap(source
[pi
- 1], source
[pi
]);
824 for (int k
= 0; k
< nrs
- 1; ++k
)
825 for (int pi
= nrs
- 1; pi
> k
; --pi
)
826 if (comp(fe
[pi
], fe
[pi
-1]))
828 std::swap(fe
[pi
-1], fe
[pi
]);
829 std::swap(source
[pi
-1], source
[pi
]);
837 while (nrs
> 0 && length
> 0)
839 if (source
[0] < source
[1])
842 while ((nrs
== 1 || !comp(fe
[1], fe
[0])) && length
> 0)
846 ++(seqs_begin
[source
[0]].first
);
848 if (seqs_begin
[source
[0]].first
== seqs_begin
[source
[0]].second
)
850 // Move everything to the left.
851 for (int s
= 0; s
< nrs
- 1; ++s
)
854 source
[s
] = source
[s
+ 1];
856 fe
[nrs
- 1].~value_type(); //Destruct explicitly.
861 fe
[0] = *(seqs_begin
[source
[0]].first
);
867 while ((nrs
== 1 || comp(fe
[0], fe
[1])) && length
> 0)
871 ++(seqs_begin
[source
[0]].first
);
873 if (seqs_begin
[source
[0]].first
== seqs_begin
[source
[0]].second
)
875 for (int s
= 0; s
< nrs
- 1; ++s
)
878 source
[s
] = source
[s
+ 1];
880 fe
[nrs
- 1].~value_type(); //Destruct explicitly.
885 fe
[0] = *(seqs_begin
[source
[0]].first
);
891 while ((j
< nrs
) && (comp(fe
[j
], fe
[j
- 1]) ||
892 (!comp(fe
[j
- 1], fe
[j
])
893 && (source
[j
] < source
[j
- 1]))))
895 std::swap(fe
[j
- 1], fe
[j
]);
896 std::swap(source
[j
- 1], source
[j
]);
904 while (nrs
> 0 && length
> 0)
907 while (nrs
== 1 || (!comp(fe
[1], fe
[0])) && length
> 0)
911 ++seqs_begin
[source
[0]].first
;
913 if (seqs_begin
[source
[0]].first
== seqs_begin
[source
[0]].second
)
915 for (int s
= 0; s
< (nrs
- 1); ++s
)
918 source
[s
] = source
[s
+ 1];
920 fe
[nrs
- 1].~value_type(); //Destruct explicitly.
925 fe
[0] = *(seqs_begin
[source
[0]].first
);
930 while ((j
< nrs
) && comp(fe
[j
], fe
[j
- 1]))
932 std::swap(fe
[j
- 1], fe
[j
]);
933 std::swap(source
[j
- 1], source
[j
]);
939 delete fe
; //Destructors already called.
945 /** @brief Multi-way merging procedure for a high branching factor,
948 * The head elements are kept in a loser tree.
949 * @param seqs_begin Begin iterator of iterator pair input sequence.
950 * @param seqs_end End iterator of iterator pair input sequence.
951 * @param target Begin iterator out output sequence.
952 * @param comp Comparator.
953 * @param length Maximum length to merge.
954 * @param stable Stable merging incurs a performance penalty.
955 * @return End iterator of output sequence.
959 typename RandomAccessIteratorIterator
,
960 typename RandomAccessIterator3
,
961 typename _DifferenceTp
,
963 RandomAccessIterator3
964 multiway_merge_loser_tree(RandomAccessIteratorIterator seqs_begin
,
965 RandomAccessIteratorIterator seqs_end
,
966 RandomAccessIterator3 target
,
968 _DifferenceTp length
, bool stable
)
970 _GLIBCXX_CALL(length
)
972 typedef _DifferenceTp difference_type
;
973 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
974 ::value_type::first_type
975 RandomAccessIterator1
;
976 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
979 int k
= static_cast<int>(seqs_end
- seqs_begin
);
983 difference_type total_length
= 0;
985 // Default value for potentially non-default-constructible types.
986 value_type
* arbitrary_element
= NULL
;
988 for (int t
= 0; t
< k
; ++t
)
990 if(arbitrary_element
== NULL
&& _GLIBCXX_PARALLEL_LENGTH(seqs_begin
[t
]) > 0)
991 arbitrary_element
= &(*seqs_begin
[t
].first
);
992 total_length
+= _GLIBCXX_PARALLEL_LENGTH(seqs_begin
[t
]);
995 if(total_length
== 0)
998 for (int t
= 0; t
< k
; ++t
)
1002 if (seqs_begin
[t
].first
== seqs_begin
[t
].second
)
1003 lt
.insert_start_stable(*arbitrary_element
, t
, true);
1005 lt
.insert_start_stable(*seqs_begin
[t
].first
, t
, false);
1009 if (seqs_begin
[t
].first
== seqs_begin
[t
].second
)
1010 lt
.insert_start(*arbitrary_element
, t
, true);
1012 lt
.insert_start(*seqs_begin
[t
].first
, t
, false);
1021 total_length
= std::min(total_length
, length
);
1027 for (difference_type i
= 0; i
< total_length
; ++i
)
1030 source
= lt
.get_min_source();
1032 *(target
++) = *(seqs_begin
[source
].first
++);
1035 if (seqs_begin
[source
].first
== seqs_begin
[source
].second
)
1036 lt
.delete_min_insert_stable(*arbitrary_element
, true);
1038 // Replace from same source.
1039 lt
.delete_min_insert_stable(*seqs_begin
[source
].first
, false);
1045 for (difference_type i
= 0; i
< total_length
; ++i
)
1048 source
= lt
.get_min_source();
1050 *(target
++) = *(seqs_begin
[source
].first
++);
1053 if (seqs_begin
[source
].first
== seqs_begin
[source
].second
)
1054 lt
.delete_min_insert(*arbitrary_element
, true);
1056 // Replace from same source.
1057 lt
.delete_min_insert(*seqs_begin
[source
].first
, false);
1064 /** @brief Multi-way merging procedure for a high branching factor,
1067 * The head elements are kept in a loser tree.
1068 * @param seqs_begin Begin iterator of iterator pair input sequence.
1069 * @param seqs_end End iterator of iterator pair input sequence.
1070 * @param target Begin iterator out output sequence.
1071 * @param comp Comparator.
1072 * @param length Maximum length to merge.
1073 * @param stable Stable merging incurs a performance penalty.
1074 * @return End iterator of output sequence.
1075 * @pre No input will run out of elements during the merge.
1079 typename RandomAccessIteratorIterator
,
1080 typename RandomAccessIterator3
,
1081 typename _DifferenceTp
, typename Comparator
>
1082 RandomAccessIterator3
1083 multiway_merge_loser_tree_unguarded(RandomAccessIteratorIterator seqs_begin
,
1084 RandomAccessIteratorIterator seqs_end
,
1085 RandomAccessIterator3 target
,
1087 _DifferenceTp length
, bool stable
)
1089 _GLIBCXX_CALL(length
)
1090 typedef _DifferenceTp difference_type
;
1092 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
1093 ::value_type::first_type
1094 RandomAccessIterator1
;
1095 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
1098 int k
= seqs_end
- seqs_begin
;
1102 difference_type total_length
= 0;
1104 for (int t
= 0; t
< k
; ++t
)
1106 #if _GLIBCXX_ASSERTIONS
1107 _GLIBCXX_PARALLEL_ASSERT(seqs_begin
[t
].first
!= seqs_begin
[t
].second
);
1110 lt
.insert_start_stable(*seqs_begin
[t
].first
, t
, false);
1112 lt
.insert_start(*seqs_begin
[t
].first
, t
, false);
1114 total_length
+= _GLIBCXX_PARALLEL_LENGTH(seqs_begin
[t
]);
1122 // Do not go past end.
1123 length
= std::min(total_length
, length
);
1127 #if _GLIBCXX_ASSERTIONS
1128 difference_type i
= 0;
1133 RandomAccessIterator3 target_end
= target
+ length
;
1134 while (target
< target_end
)
1137 source
= lt
.get_min_source();
1139 #if _GLIBCXX_ASSERTIONS
1140 _GLIBCXX_PARALLEL_ASSERT(i
== 0
1141 || !comp(*(seqs_begin
[source
].first
), *(target
- 1)));
1144 *(target
++) = *(seqs_begin
[source
].first
++);
1146 #if _GLIBCXX_ASSERTIONS
1147 _GLIBCXX_PARALLEL_ASSERT(
1148 (seqs_begin
[source
].first
!= seqs_begin
[source
].second
)
1149 || (i
== length
- 1));
1153 // Replace from same source.
1154 lt
.delete_min_insert_stable(*seqs_begin
[source
].first
, false);
1160 RandomAccessIterator3 target_end
= target
+ length
;
1161 while (target
< target_end
)
1164 source
= lt
.get_min_source();
1166 #if _GLIBCXX_ASSERTIONS
1167 if (i
> 0 && comp(*(seqs_begin
[source
].first
), *(target
- 1)))
1168 printf(" %i %i %i\n", length
, i
, source
);
1169 _GLIBCXX_PARALLEL_ASSERT(i
== 0
1170 || !comp(*(seqs_begin
[source
].first
), *(target
- 1)));
1173 *(target
++) = *(seqs_begin
[source
].first
++);
1175 #if _GLIBCXX_ASSERTIONS
1176 if (!((seqs_begin
[source
].first
!= seqs_begin
[source
].second
)
1177 || (i
>= length
- 1)))
1178 printf(" %i %i %i\n", length
, i
, source
);
1179 _GLIBCXX_PARALLEL_ASSERT(
1180 (seqs_begin
[source
].first
!= seqs_begin
[source
].second
)
1181 || (i
>= length
- 1));
1185 // Replace from same source.
1186 lt
.delete_min_insert(*seqs_begin
[source
].first
, false);
1194 typename RandomAccessIteratorIterator
,
1195 typename RandomAccessIterator3
,
1196 typename _DifferenceTp
,
1197 typename Comparator
>
1198 RandomAccessIterator3
1199 multiway_merge_loser_tree_combined(RandomAccessIteratorIterator seqs_begin
,
1200 RandomAccessIteratorIterator seqs_end
,
1201 RandomAccessIterator3 target
,
1203 _DifferenceTp length
, bool stable
)
1205 _GLIBCXX_CALL(length
)
1207 typedef _DifferenceTp difference_type
;
1209 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
1210 ::value_type::first_type
1211 RandomAccessIterator1
;
1212 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
1216 RandomAccessIterator3 target_end
;
1217 difference_type overhang
= prepare_unguarded(seqs_begin
, seqs_end
,
1218 comp
, min_seq
, stable
);
1220 difference_type total_length
= 0;
1221 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; ++s
)
1222 total_length
+= _GLIBCXX_PARALLEL_LENGTH(*s
);
1226 difference_type unguarded_length
=
1227 std::min(length
, total_length
- overhang
);
1228 target_end
= multiway_merge_loser_tree_unguarded
1229 <typename loser_tree_unguarded_traits
<value_type
, Comparator
>::LT
>
1230 (seqs_begin
, seqs_end
, target
, comp
, unguarded_length
, stable
);
1231 overhang
= length
- unguarded_length
;
1235 // Empty sequence found.
1237 target_end
= target
;
1240 #if _GLIBCXX_ASSERTIONS
1241 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
- overhang
);
1242 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
1245 target_end
= multiway_merge_loser_tree
1246 <typename loser_tree_traits
<value_type
, Comparator
>::LT
>
1247 (seqs_begin
, seqs_end
, target_end
, comp
, overhang
, stable
);
1249 #if _GLIBCXX_ASSERTIONS
1250 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
);
1251 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
1258 typename RandomAccessIteratorIterator
,
1259 typename RandomAccessIterator3
,
1260 typename _DifferenceTp
,
1261 typename Comparator
>
1262 RandomAccessIterator3
1263 multiway_merge_loser_tree_sentinel(RandomAccessIteratorIterator seqs_begin
,
1264 RandomAccessIteratorIterator seqs_end
,
1265 RandomAccessIterator3 target
,
1267 _DifferenceTp length
, bool stable
)
1269 _GLIBCXX_CALL(length
)
1271 typedef _DifferenceTp difference_type
;
1272 typedef std::iterator_traits
<RandomAccessIteratorIterator
> traits_type
;
1273 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
1274 ::value_type::first_type
1275 RandomAccessIterator1
;
1276 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
1279 RandomAccessIterator3 target_end
;
1280 difference_type overhang
=
1281 prepare_unguarded_sentinel(seqs_begin
, seqs_end
, comp
);
1283 difference_type total_length
= 0;
1284 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; ++s
)
1286 total_length
+= _GLIBCXX_PARALLEL_LENGTH(*s
);
1292 difference_type unguarded_length
=
1293 std::min(length
, total_length
- overhang
);
1294 target_end
= multiway_merge_loser_tree_unguarded
1295 <typename loser_tree_unguarded_traits
<value_type
, Comparator
>::LT
>
1296 (seqs_begin
, seqs_end
, target
, comp
, unguarded_length
, stable
);
1297 overhang
= length
- unguarded_length
;
1299 #if _GLIBCXX_ASSERTIONS
1300 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
- overhang
);
1301 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
1304 // Copy rest stable.
1305 for (RandomAccessIteratorIterator s
= seqs_begin
;
1306 s
!= seqs_end
&& overhang
> 0; ++s
)
1310 difference_type local_length
=
1311 std::min
<difference_type
>(overhang
, _GLIBCXX_PARALLEL_LENGTH(*s
));
1312 target_end
= std::copy((*s
).first
, (*s
).first
+ local_length
,
1314 (*s
).first
+= local_length
;
1315 overhang
-= local_length
;
1318 #if _GLIBCXX_ASSERTIONS
1319 _GLIBCXX_PARALLEL_ASSERT(overhang
== 0);
1320 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
);
1321 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
1327 /** @brief Sequential multi-way merging switch.
1329 * The _GLIBCXX_PARALLEL_DECISION if based on the branching factor and runtime settings.
1330 * @param seqs_begin Begin iterator of iterator pair input sequence.
1331 * @param seqs_end End iterator of iterator pair input sequence.
1332 * @param target Begin iterator out output sequence.
1333 * @param comp Comparator.
1334 * @param length Maximum length to merge.
1335 * @param stable Stable merging incurs a performance penalty.
1336 * @param sentinel The sequences have a sentinel element.
1337 * @return End iterator of output sequence. */
1339 typename RandomAccessIteratorIterator
,
1340 typename RandomAccessIterator3
,
1341 typename _DifferenceTp
,
1342 typename Comparator
>
1343 RandomAccessIterator3
1344 multiway_merge(RandomAccessIteratorIterator seqs_begin
,
1345 RandomAccessIteratorIterator seqs_end
,
1346 RandomAccessIterator3 target
,
1347 Comparator comp
, _DifferenceTp length
,
1348 bool stable
, bool sentinel
,
1351 _GLIBCXX_CALL(length
)
1353 typedef _DifferenceTp difference_type
;
1354 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
1355 ::value_type::first_type
1356 RandomAccessIterator1
;
1357 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
1360 #if _GLIBCXX_ASSERTIONS
1361 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; ++s
)
1362 _GLIBCXX_PARALLEL_ASSERT(is_sorted((*s
).first
, (*s
).second
, comp
));
1365 RandomAccessIterator3 return_target
= target
;
1366 int k
= static_cast<int>(seqs_end
- seqs_begin
);
1368 Settings::MultiwayMergeAlgorithm mwma
=
1369 Settings::multiway_merge_algorithm
;
1371 if (!sentinel
&& mwma
== Settings::LOSER_TREE_SENTINEL
)
1372 mwma
= Settings::LOSER_TREE_COMBINED
;
1379 return_target
= std::copy(seqs_begin
[0].first
,
1380 seqs_begin
[0].first
+ length
,
1382 seqs_begin
[0].first
+= length
;
1385 return_target
= merge_advance(seqs_begin
[0].first
,
1386 seqs_begin
[0].second
,
1387 seqs_begin
[1].first
,
1388 seqs_begin
[1].second
,
1389 target
, length
, comp
);
1394 case Settings::LOSER_TREE_COMBINED
:
1395 return_target
= multiway_merge_3_combined(seqs_begin
,
1398 comp
, length
, stable
);
1400 case Settings::LOSER_TREE_SENTINEL
:
1401 return_target
= multiway_merge_3_variant
<unguarded_iterator
>(
1405 comp
, length
, stable
);
1408 return_target
= multiway_merge_3_variant
<guarded_iterator
>(
1412 comp
, length
, stable
);
1419 case Settings::LOSER_TREE_COMBINED
:
1420 return_target
= multiway_merge_4_combined(
1424 comp
, length
, stable
);
1426 case Settings::LOSER_TREE_SENTINEL
:
1427 return_target
= multiway_merge_4_variant
<unguarded_iterator
>(
1431 comp
, length
, stable
);
1434 return_target
= multiway_merge_4_variant
<guarded_iterator
>(
1438 comp
, length
, stable
);
1446 case Settings::BUBBLE
:
1447 return_target
= multiway_merge_bubble(
1451 comp
, length
, stable
);
1453 #if _GLIBCXX_LOSER_TREE_EXPLICIT
1454 case Settings::LOSER_TREE_EXPLICIT
:
1455 return_target
= multiway_merge_loser_tree
<
1456 LoserTreeExplicit
<value_type
, Comparator
> >(
1460 comp
, length
, stable
);
1463 #if _GLIBCXX_LOSER_TREE
1464 case Settings::LOSER_TREE
:
1465 return_target
= multiway_merge_loser_tree
<
1466 LoserTree
<value_type
, Comparator
> >(
1470 comp
, length
, stable
);
1473 #if _GLIBCXX_LOSER_TREE_COMBINED
1474 case Settings::LOSER_TREE_COMBINED
:
1475 return_target
= multiway_merge_loser_tree_combined(
1479 comp
, length
, stable
);
1482 #if _GLIBCXX_LOSER_TREE_SENTINEL
1483 case Settings::LOSER_TREE_SENTINEL
:
1484 return_target
= multiway_merge_loser_tree_sentinel(
1488 comp
, length
, stable
);
1492 // multiway_merge algorithm not implemented.
1493 _GLIBCXX_PARALLEL_ASSERT(0);
1498 #if _GLIBCXX_ASSERTIONS
1499 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target
+ length
, comp
));
1502 return return_target
;
1505 /** @brief Parallel multi-way merge routine.
1507 * The _GLIBCXX_PARALLEL_DECISION if based on the branching factor and runtime settings.
1508 * @param seqs_begin Begin iterator of iterator pair input sequence.
1509 * @param seqs_end End iterator of iterator pair input sequence.
1510 * @param target Begin iterator out output sequence.
1511 * @param comp Comparator.
1512 * @param length Maximum length to merge.
1513 * @param stable Stable merging incurs a performance penalty.
1514 * @param sentinel Ignored.
1515 * @return End iterator of output sequence.
1518 typename RandomAccessIteratorIterator
,
1519 typename RandomAccessIterator3
,
1520 typename _DifferenceTp
,
1521 typename Comparator
>
1522 RandomAccessIterator3
1523 parallel_multiway_merge(RandomAccessIteratorIterator seqs_begin
,
1524 RandomAccessIteratorIterator seqs_end
,
1525 RandomAccessIterator3 target
,
1527 _DifferenceTp length
, bool stable
, bool sentinel
)
1529 _GLIBCXX_CALL(length
)
1531 typedef _DifferenceTp difference_type
;
1532 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
1533 ::value_type::first_type
1534 RandomAccessIterator1
;
1535 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
1539 int k
= static_cast<int>(seqs_end
- seqs_begin
);
1541 difference_type total_length
= 0;
1542 for (RandomAccessIteratorIterator raii
= seqs_begin
;
1543 raii
!= seqs_end
; ++raii
)
1544 total_length
+= _GLIBCXX_PARALLEL_LENGTH(*raii
);
1546 _GLIBCXX_CALL(total_length
)
1548 if (total_length
== 0 || k
== 0)
1551 bool tight
= (total_length
== length
);
1553 std::vector
<std::pair
<difference_type
, difference_type
> >* pieces
;
1555 thread_index_t num_threads
= static_cast<thread_index_t
>(
1556 std::min
<difference_type
>(get_max_threads(), total_length
));
1558 # pragma omp parallel num_threads (num_threads)
1562 num_threads
= omp_get_num_threads();
1563 // Thread t will have to merge pieces[iam][0..k - 1]
1564 pieces
= new std::vector
<
1565 std::pair
<difference_type
, difference_type
> >[num_threads
];
1566 for (int s
= 0; s
< num_threads
; ++s
)
1567 pieces
[s
].resize(k
);
1569 difference_type num_samples
=
1570 Settings::merge_oversampling
* num_threads
;
1572 if (Settings::multiway_merge_splitting
== Settings::SAMPLING
)
1574 value_type
* samples
= static_cast<value_type
*>(
1575 ::operator new(sizeof(value_type
) * k
* num_samples
));
1577 for (int s
= 0; s
< k
; ++s
)
1578 for (difference_type i
= 0; i
< num_samples
; ++i
)
1580 difference_type sample_index
=
1581 static_cast<difference_type
>(
1582 _GLIBCXX_PARALLEL_LENGTH(seqs_begin
[s
]) * (double(i
+ 1) /
1583 (num_samples
+ 1)) * (double(length
)
1585 ::new(&(samples
[s
* num_samples
+ i
])) value_type(
1586 seqs_begin
[s
].first
[sample_index
]);
1590 __gnu_sequential::stable_sort(
1591 samples
, samples
+ (num_samples
* k
), comp
);
1593 __gnu_sequential::sort(
1594 samples
, samples
+ (num_samples
* k
), comp
);
1596 for (int slab
= 0; slab
< num_threads
; ++slab
)
1597 // For each slab / processor.
1598 for (int seq
= 0; seq
< k
; ++seq
)
1600 // For each sequence.
1602 pieces
[slab
][seq
].first
=
1604 seqs_begin
[seq
].first
,
1605 seqs_begin
[seq
].second
,
1606 samples
[num_samples
* k
* slab
/ num_threads
],
1608 - seqs_begin
[seq
].first
;
1611 // Absolute beginning.
1612 pieces
[slab
][seq
].first
= 0;
1614 if ((slab
+ 1) < num_threads
)
1615 pieces
[slab
][seq
].second
=
1617 seqs_begin
[seq
].first
,
1618 seqs_begin
[seq
].second
,
1619 samples
[num_samples
* k
* (slab
+ 1) /
1621 - seqs_begin
[seq
].first
;
1623 pieces
[slab
][seq
].second
= _GLIBCXX_PARALLEL_LENGTH(seqs_begin
[seq
]);
1629 // (Settings::multiway_merge_splitting == Settings::EXACT).
1630 std::vector
<RandomAccessIterator1
>* offsets
=
1631 new std::vector
<RandomAccessIterator1
>[num_threads
];
1633 std::pair
<RandomAccessIterator1
, RandomAccessIterator1
>
1636 copy(seqs_begin
, seqs_end
, se
.begin());
1638 difference_type
* borders
=
1639 new difference_type
[num_threads
+ 1];
1640 equally_split(length
, num_threads
, borders
);
1642 for (int s
= 0; s
< (num_threads
- 1); ++s
)
1644 offsets
[s
].resize(k
);
1646 se
.begin(), se
.end(), borders
[s
+ 1],
1647 offsets
[s
].begin(), comp
);
1649 // Last one also needed and available.
1652 offsets
[num_threads
- 1].resize(k
);
1653 multiseq_partition(se
.begin(), se
.end(),
1654 difference_type(length
),
1655 offsets
[num_threads
- 1].begin(), comp
);
1660 for (int slab
= 0; slab
< num_threads
; ++slab
)
1662 // For each slab / processor.
1663 for (int seq
= 0; seq
< k
; ++seq
)
1665 // For each sequence.
1668 // Absolute beginning.
1669 pieces
[slab
][seq
].first
= 0;
1672 pieces
[slab
][seq
].first
=
1673 pieces
[slab
- 1][seq
].second
;
1674 if (!tight
|| slab
< (num_threads
- 1))
1675 pieces
[slab
][seq
].second
=
1676 offsets
[slab
][seq
] - seqs_begin
[seq
].first
;
1679 // slab == num_threads - 1
1680 pieces
[slab
][seq
].second
=
1681 _GLIBCXX_PARALLEL_LENGTH(seqs_begin
[seq
]);
1689 thread_index_t iam
= omp_get_thread_num();
1691 difference_type target_position
= 0;
1693 for (int c
= 0; c
< k
; ++c
)
1694 target_position
+= pieces
[iam
][c
].first
;
1698 std::pair
<RandomAccessIterator1
, RandomAccessIterator1
>* chunks
1700 std::pair
<RandomAccessIterator1
, RandomAccessIterator1
>[k
];
1702 difference_type local_length
= 0;
1703 for (int s
= 0; s
< k
; ++s
)
1705 chunks
[s
] = std::make_pair(
1706 seqs_begin
[s
].first
+ pieces
[iam
][s
].first
,
1707 seqs_begin
[s
].first
+ pieces
[iam
][s
].second
);
1708 local_length
+= _GLIBCXX_PARALLEL_LENGTH(chunks
[s
]);
1712 chunks
, chunks
+ k
, target
+ target_position
, comp
,
1713 std::min(local_length
, length
- target_position
),
1714 stable
, false, sequential_tag());
1720 RandomAccessIterator1
1721 begin0
= seqs_begin
[0].first
+ pieces
[iam
][0].first
,
1722 begin1
= seqs_begin
[1].first
+ pieces
[iam
][1].first
;
1723 merge_advance(begin0
,
1724 seqs_begin
[0].first
+ pieces
[iam
][0].second
,
1726 seqs_begin
[1].first
+ pieces
[iam
][1].second
,
1727 target
+ target_position
,
1728 (pieces
[iam
][0].second
- pieces
[iam
][0].first
) +
1729 (pieces
[iam
][1].second
- pieces
[iam
][1].first
),
1734 #if _GLIBCXX_ASSERTIONS
1735 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target
+ length
, comp
));
1738 // Update ends of sequences.
1739 for (int s
= 0; s
< k
; ++s
)
1740 seqs_begin
[s
].first
+= pieces
[num_threads
- 1][s
].second
;
1744 return target
+ length
;
1748 * @brief Multi-way merging front-end.
1749 * @param seqs_begin Begin iterator of iterator pair input sequence.
1750 * @param seqs_end End iterator of iterator pair input sequence.
1751 * @param target Begin iterator out output sequence.
1752 * @param comp Comparator.
1753 * @param length Maximum length to merge.
1754 * @param stable Stable merging incurs a performance penalty.
1755 * @return End iterator of output sequence.
1758 typename RandomAccessIteratorPairIterator
,
1759 typename RandomAccessIterator3
,
1760 typename _DifferenceTp
,
1761 typename Comparator
>
1762 RandomAccessIterator3
1763 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
,
1764 RandomAccessIteratorPairIterator seqs_end
,
1765 RandomAccessIterator3 target
, Comparator comp
,
1766 _DifferenceTp length
, bool stable
)
1768 typedef _DifferenceTp difference_type
;
1769 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1771 if (seqs_begin
== seqs_end
)
1774 RandomAccessIterator3 target_end
;
1775 if (_GLIBCXX_PARALLEL_CONDITION(
1776 ((seqs_end
- seqs_begin
) >= Settings::multiway_merge_minimal_k
)
1777 && ((sequence_index_t
)length
>= Settings::multiway_merge_minimal_n
)))
1778 target_end
= parallel_multiway_merge(
1779 seqs_begin
, seqs_end
,
1780 target
, comp
, static_cast<difference_type
>(length
), stable
, false);
1782 target_end
= multiway_merge(
1783 seqs_begin
, seqs_end
,
1784 target
, comp
, length
, stable
, false, sequential_tag());
1789 /** @brief Multi-way merging front-end.
1790 * @param seqs_begin Begin iterator of iterator pair input sequence.
1791 * @param seqs_end End iterator of iterator pair input sequence.
1792 * @param target Begin iterator out output sequence.
1793 * @param comp Comparator.
1794 * @param length Maximum length to merge.
1795 * @param stable Stable merging incurs a performance penalty.
1796 * @return End iterator of output sequence.
1797 * @pre For each @c i, @c seqs_begin[i].second must be the end
1798 * marker of the sequence, but also reference the one more sentinel
1801 typename RandomAccessIteratorPairIterator
,
1802 typename RandomAccessIterator3
,
1803 typename _DifferenceTp
,
1804 typename Comparator
>
1805 RandomAccessIterator3
1806 multiway_merge_sentinel(RandomAccessIteratorPairIterator seqs_begin
,
1807 RandomAccessIteratorPairIterator seqs_end
,
1808 RandomAccessIterator3 target
,
1810 _DifferenceTp length
,
1813 typedef _DifferenceTp difference_type
;
1815 if (seqs_begin
== seqs_end
)
1818 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1820 if (_GLIBCXX_PARALLEL_CONDITION(
1821 ((seqs_end
- seqs_begin
) >= Settings::multiway_merge_minimal_k
)
1822 && ((sequence_index_t
)length
>= Settings::multiway_merge_minimal_n
)))
1823 return parallel_multiway_merge(
1824 seqs_begin
, seqs_end
,
1825 target
, comp
, static_cast<difference_type
>(length
), stable
, true);
1827 return multiway_merge(
1828 seqs_begin
, seqs_end
,
1829 target
, comp
, length
, stable
, true, sequential_tag());