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 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
>(guarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
, guarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
131 operator<= <RandomAccessIterator
, Comparator
>(guarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
, guarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
134 /** @brief Compare two elements referenced by guarded iterators.
135 * @param bi1 First iterator.
136 * @param bi2 Second iterator.
137 * @return @c True if less. */
138 template<typename RandomAccessIterator
, typename Comparator
>
140 operator<(guarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
141 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
)
143 if (bi1
.current
== bi1
.end
) //bi1 is sup
144 return bi2
.current
== bi2
.end
; //bi2 is not sup
145 if (bi2
.current
== bi2
.end
) //bi2 is sup
147 return (bi1
.comp
)(*bi1
, *bi2
); //normal compare
150 /** @brief Compare two elements referenced by guarded iterators.
151 * @param bi1 First iterator.
152 * @param bi2 Second iterator.
153 * @return @c True if less equal. */
154 template<typename RandomAccessIterator
, typename Comparator
>
156 operator<=(guarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
157 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
)
159 if (bi2
.current
== bi2
.end
) //bi1 is sup
160 return bi1
.current
!= bi1
.end
; //bi2 is not sup
161 if (bi1
.current
== bi1
.end
) //bi2 is sup
163 return !(bi1
.comp
)(*bi2
, *bi1
); //normal compare
166 template<typename RandomAccessIterator
, typename Comparator
>
167 class unguarded_iterator
;
169 template<typename RandomAccessIterator
, typename Comparator
>
171 operator<(unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
172 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
174 template<typename RandomAccessIterator
, typename Comparator
>
176 operator<=(unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
177 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
179 template<typename RandomAccessIterator
, typename Comparator
>
180 class unguarded_iterator
183 /** @brief Current iterator position. */
184 RandomAccessIterator
& current
;
185 /** @brief Comparator. */
186 mutable Comparator
& comp
;
189 /** @brief Constructor. Sets iterator to beginning of sequence.
190 * @param begin Begin iterator of sequence.
191 * @param end Unused, only for compatibility.
192 * @param comp Unused, only for compatibility. */
193 inline unguarded_iterator(RandomAccessIterator begin
,
194 RandomAccessIterator end
, Comparator
& comp
)
195 : current(begin
), comp(comp
)
198 /** @brief Pre-increment operator.
200 inline unguarded_iterator
<RandomAccessIterator
, Comparator
>&
207 /** @brief Dereference operator.
208 * @return Referenced element. */
209 inline typename
std::iterator_traits
<RandomAccessIterator
>::value_type
213 /** @brief Convert to wrapped iterator.
214 * @return Wrapped iterator. */
216 operator RandomAccessIterator()
220 operator< <RandomAccessIterator
, Comparator
>(unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
, unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
223 operator<= <RandomAccessIterator
, Comparator
>(unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
, unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
226 /** @brief Compare two elements referenced by unguarded iterators.
227 * @param bi1 First iterator.
228 * @param bi2 Second iterator.
229 * @return @c True if less. */
230 template<typename RandomAccessIterator
, typename Comparator
>
232 operator<(unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
233 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
)
236 return (bi1
.comp
)(*bi1
, *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 equal. */
243 template<typename RandomAccessIterator
, typename Comparator
>
245 operator<=(unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
246 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
)
249 return !(bi1
.comp
)(*bi2
, *bi1
);
252 /** Prepare a set of sequences to be merged without a (end) guard
256 * @param min_sequence
258 * @pre (seqs_end - seqs_begin > 0) */
259 template<typename RandomAccessIteratorIterator
, typename Comparator
>
260 typename
std::iterator_traits
<typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
>::difference_type
261 prepare_unguarded(RandomAccessIteratorIterator seqs_begin
,
262 RandomAccessIteratorIterator seqs_end
, Comparator comp
,
263 int& min_sequence
, bool stable
)
265 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
267 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
268 RandomAccessIterator1
;
269 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
271 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::difference_type
274 if ((*seqs_begin
).first
== (*seqs_begin
).second
)
276 // Empty sequence found, it's the first one.
281 // Last element in sequence.
282 value_type min
= *((*seqs_begin
).second
- 1);
284 for (RandomAccessIteratorIterator s
= seqs_begin
+ 1; s
!= seqs_end
; s
++)
286 if ((*s
).first
== (*s
).second
)
288 // Empty sequence found.
289 min_sequence
= static_cast<int>(s
- seqs_begin
);
293 // Last element in sequence.
294 const value_type
& v
= *((*s
).second
- 1);
295 if (comp(v
, min
)) //strictly smaller
298 min_sequence
= static_cast<int>(s
- seqs_begin
);
302 difference_type overhang_size
= 0;
305 for (s
= 0; s
<= min_sequence
; s
++)
307 RandomAccessIterator1 split
;
309 split
= std::upper_bound(seqs_begin
[s
].first
, seqs_begin
[s
].second
,
312 split
= std::lower_bound(seqs_begin
[s
].first
, seqs_begin
[s
].second
,
315 overhang_size
+= seqs_begin
[s
].second
- split
;
318 for (; s
< (seqs_end
- seqs_begin
); s
++)
320 RandomAccessIterator1 split
= std::lower_bound(seqs_begin
[s
].first
, seqs_begin
[s
].second
, min
, comp
);
321 overhang_size
+= seqs_begin
[s
].second
- split
;
324 // So many elements will be left over afterwards.
325 return overhang_size
;
328 /** Prepare a set of sequences to be merged with a (end) guard (sentinel)
332 template<typename RandomAccessIteratorIterator
, typename Comparator
>
333 typename
std::iterator_traits
<typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
>::difference_type
334 prepare_unguarded_sentinel(RandomAccessIteratorIterator seqs_begin
,
335 RandomAccessIteratorIterator seqs_end
,
338 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
340 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
341 RandomAccessIterator1
;
342 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
344 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::difference_type
347 // Last element in sequence.
348 value_type
* max
= NULL
;
349 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; s
++)
351 if ((*s
).first
== (*s
).second
)
354 // Last element in sequence.
355 value_type
& v
= *((*s
).second
- 1);
358 if (!max
|| comp(*max
, v
))
362 difference_type overhang_size
= 0;
363 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; s
++)
365 RandomAccessIterator1 split
= std::lower_bound((*s
).first
, (*s
).second
,
367 overhang_size
+= (*s
).second
- split
;
370 *((*s
).second
) = *max
;
373 // So many elements will be left over afterwards.
374 return overhang_size
;
377 /** @brief Highly efficient 3-way merging procedure.
378 * @param seqs_begin Begin iterator of iterator pair input sequence.
379 * @param seqs_end End iterator of iterator pair input sequence.
380 * @param target Begin iterator out output sequence.
381 * @param comp Comparator.
382 * @param length Maximum length to merge.
383 * @param stable Unused, stable anyway.
384 * @return End iterator of output sequence. */
385 template<template<typename RAI
, typename C
> class iterator
, typename RandomAccessIteratorIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
386 RandomAccessIterator3
387 multiway_merge_3_variant(RandomAccessIteratorIterator seqs_begin
, RandomAccessIteratorIterator seqs_end
, RandomAccessIterator3 target
, Comparator comp
, _DifferenceTp length
, bool stable
)
389 _GLIBCXX_CALL(length
);
391 typedef _DifferenceTp difference_type
;
393 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
394 RandomAccessIterator1
;
395 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
401 iterator
<RandomAccessIterator1
, Comparator
>
402 seq0(seqs_begin
[0].first
, seqs_begin
[0].second
, comp
),
403 seq1(seqs_begin
[1].first
, seqs_begin
[1].second
, comp
),
404 seq2(seqs_begin
[2].first
, seqs_begin
[2].second
, comp
);
429 #define Merge3Case(a,b,c,c0,c1) \
431 *target = *seq ## a; \
435 if (length == 0) goto finish; \
436 if (seq ## a c0 seq ## b) goto s ## a ## b ## c; \
437 if (seq ## a c1 seq ## c) goto s ## b ## a ## c; \
438 goto s ## b ## c ## a;
440 Merge3Case(0, 1, 2, <=, <=);
441 Merge3Case(1, 2, 0, <=, < );
442 Merge3Case(2, 0, 1, < , < );
443 Merge3Case(1, 0, 2, < , <=);
444 Merge3Case(0, 2, 1, <=, <=);
445 Merge3Case(2, 1, 0, < , < );
452 seqs_begin
[0].first
= seq0
;
453 seqs_begin
[1].first
= seq1
;
454 seqs_begin
[2].first
= seq2
;
459 template<typename RandomAccessIteratorIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
460 RandomAccessIterator3
461 multiway_merge_3_combined(RandomAccessIteratorIterator seqs_begin
, RandomAccessIteratorIterator seqs_end
, RandomAccessIterator3 target
, Comparator comp
, _DifferenceTp length
, bool stable
)
463 _GLIBCXX_CALL(length
);
465 typedef _DifferenceTp difference_type
;
466 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
467 RandomAccessIterator1
;
468 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
472 RandomAccessIterator3 target_end
;
475 difference_type overhang
= prepare_unguarded(seqs_begin
, seqs_end
, comp
, min_seq
, true);
477 difference_type total_length
= 0;
478 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; ++s
)
479 total_length
+= LENGTH(*s
);
483 difference_type unguarded_length
= std::min(length
, total_length
- overhang
);
484 target_end
= multiway_merge_3_variant
<unguarded_iterator
>
485 (seqs_begin
, seqs_end
, target
, comp
, unguarded_length
, stable
);
486 overhang
= length
- unguarded_length
;
490 // Empty sequence found.
495 #if _GLIBCXX_ASSERTIONS
496 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
- overhang
);
497 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
503 // Iterators will be advanced accordingly.
504 target_end
= merge_advance(seqs_begin
[1].first
, seqs_begin
[1].second
,
505 seqs_begin
[2].first
, seqs_begin
[2].second
,
506 target_end
, overhang
, comp
);
509 target_end
= merge_advance(seqs_begin
[0].first
, seqs_begin
[0].second
,
510 seqs_begin
[2].first
, seqs_begin
[2].second
,
511 target_end
, overhang
, comp
);
514 target_end
= merge_advance(seqs_begin
[0].first
, seqs_begin
[0].second
,
515 seqs_begin
[1].first
, seqs_begin
[1].second
,
516 target_end
, overhang
, comp
);
519 _GLIBCXX_PARALLEL_ASSERT(false);
522 #if _GLIBCXX_ASSERTIONS
523 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
);
524 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
530 /** @brief Highly efficient 4-way merging procedure.
531 * @param seqs_begin Begin iterator of iterator pair input sequence.
532 * @param seqs_end End iterator of iterator pair input sequence.
533 * @param target Begin iterator out output sequence.
534 * @param comp Comparator.
535 * @param length Maximum length to merge.
536 * @param stable Unused, stable anyway.
537 * @return End iterator of output sequence. */
538 template<template<typename RAI
, typename C
> class iterator
, typename RandomAccessIteratorIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
539 RandomAccessIterator3
540 multiway_merge_4_variant(RandomAccessIteratorIterator seqs_begin
, RandomAccessIteratorIterator seqs_end
, RandomAccessIterator3 target
, Comparator comp
, _DifferenceTp length
, bool stable
)
542 _GLIBCXX_CALL(length
);
543 typedef _DifferenceTp difference_type
;
545 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
546 RandomAccessIterator1
;
547 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
550 iterator
<RandomAccessIterator1
, Comparator
>
551 seq0(seqs_begin
[0].first
, seqs_begin
[0].second
, comp
),
552 seq1(seqs_begin
[1].first
, seqs_begin
[1].second
, comp
),
553 seq2(seqs_begin
[2].first
, seqs_begin
[2].second
, comp
),
554 seq3(seqs_begin
[3].first
, seqs_begin
[3].second
, comp
);
556 #define Decision(a,b,c,d) { \
557 if (seq ## d < seq ## a) goto s ## d ## a ## b ## c; \
558 if (seq ## d < seq ## b) goto s ## a ## d ## b ## c; \
559 if (seq ## d < seq ## c) goto s ## a ## b ## d ## c; \
560 goto s ## a ## b ## c ## d; }
585 #define Merge4Case(a,b,c,d,c0,c1,c2) \
586 s ## a ## b ## c ## d: \
587 if (length == 0) goto finish; \
588 *target = *seq ## a; \
592 if (seq ## a c0 seq ## b) goto s ## a ## b ## c ## d; \
593 if (seq ## a c1 seq ## c) goto s ## b ## a ## c ## d; \
594 if (seq ## a c2 seq ## d) goto s ## b ## c ## a ## d; \
595 goto s ## b ## c ## d ## a;
597 Merge4Case(0, 1, 2, 3, <=, <=, <=);
598 Merge4Case(0, 1, 3, 2, <=, <=, <=);
599 Merge4Case(0, 2, 1, 3, <=, <=, <=);
600 Merge4Case(0, 2, 3, 1, <=, <=, <=);
601 Merge4Case(0, 3, 1, 2, <=, <=, <=);
602 Merge4Case(0, 3, 2, 1, <=, <=, <=);
603 Merge4Case(1, 0, 2, 3, < , <=, <=);
604 Merge4Case(1, 0, 3, 2, < , <=, <=);
605 Merge4Case(1, 2, 0, 3, <=, < , <=);
606 Merge4Case(1, 2, 3, 0, <=, <=, < );
607 Merge4Case(1, 3, 0, 2, <=, < , <=);
608 Merge4Case(1, 3, 2, 0, <=, <=, < );
609 Merge4Case(2, 0, 1, 3, < , < , <=);
610 Merge4Case(2, 0, 3, 1, < , <=, < );
611 Merge4Case(2, 1, 0, 3, < , < , <=);
612 Merge4Case(2, 1, 3, 0, < , <=, < );
613 Merge4Case(2, 3, 0, 1, <=, < , < );
614 Merge4Case(2, 3, 1, 0, <=, < , < );
615 Merge4Case(3, 0, 1, 2, < , < , < );
616 Merge4Case(3, 0, 2, 1, < , < , < );
617 Merge4Case(3, 1, 0, 2, < , < , < );
618 Merge4Case(3, 1, 2, 0, < , < , < );
619 Merge4Case(3, 2, 0, 1, < , < , < );
620 Merge4Case(3, 2, 1, 0, < , < , < );
628 seqs_begin
[0].first
= seq0
;
629 seqs_begin
[1].first
= seq1
;
630 seqs_begin
[2].first
= seq2
;
631 seqs_begin
[3].first
= seq3
;
636 template<typename RandomAccessIteratorIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
637 RandomAccessIterator3
638 multiway_merge_4_combined(RandomAccessIteratorIterator seqs_begin
, RandomAccessIteratorIterator seqs_end
, RandomAccessIterator3 target
, Comparator comp
, _DifferenceTp length
, bool stable
)
640 _GLIBCXX_CALL(length
);
641 typedef _DifferenceTp difference_type
;
643 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
644 RandomAccessIterator1
;
645 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
649 RandomAccessIterator3 target_end
;
652 difference_type overhang
= prepare_unguarded(seqs_begin
, seqs_end
, comp
, min_seq
, true);
654 difference_type total_length
= 0;
655 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; ++s
)
656 total_length
+= LENGTH(*s
);
660 difference_type unguarded_length
= std::min(length
, total_length
- overhang
);
661 target_end
= multiway_merge_4_variant
<unguarded_iterator
>
662 (seqs_begin
, seqs_end
, target
, comp
, unguarded_length
, stable
);
663 overhang
= length
- unguarded_length
;
667 // Empty sequence found.
672 #if _GLIBCXX_ASSERTIONS
673 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
- overhang
);
674 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
677 std::vector
<std::pair
<RandomAccessIterator1
, RandomAccessIterator1
> > one_missing(seqs_begin
, seqs_end
);
678 one_missing
.erase(one_missing
.begin() + min_seq
); //remove
680 target_end
= multiway_merge_3_variant
<guarded_iterator
>(one_missing
.begin(), one_missing
.end(), target_end
, comp
, overhang
, stable
);
682 // Insert back again.
683 one_missing
.insert(one_missing
.begin() + min_seq
, seqs_begin
[min_seq
]);
684 // Write back modified iterators.
685 copy(one_missing
.begin(), one_missing
.end(), seqs_begin
);
687 #if _GLIBCXX_ASSERTIONS
688 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
);
689 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
695 /** @brief Basic multi-way merging procedure.
697 * The head elements are kept in a sorted array, new heads are
699 * @param seqs_begin Begin iterator of iterator pair input sequence.
700 * @param seqs_end End iterator of iterator pair input sequence.
701 * @param target Begin iterator out output sequence.
702 * @param comp Comparator.
703 * @param length Maximum length to merge.
704 * @param stable Stable merging incurs a performance penalty.
705 * @return End iterator of output sequence.
707 template<typename RandomAccessIteratorIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
708 RandomAccessIterator3
709 multiway_merge_bubble(RandomAccessIteratorIterator seqs_begin
, RandomAccessIteratorIterator seqs_end
, RandomAccessIterator3 target
, Comparator comp
, _DifferenceTp length
, bool stable
)
711 _GLIBCXX_CALL(length
)
713 typedef _DifferenceTp difference_type
;
714 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
715 RandomAccessIterator1
;
716 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
719 // Num remaining pieces.
720 int k
= static_cast<int>(seqs_end
- seqs_begin
), nrp
;
722 value_type
* pl
= static_cast<value_type
*>(::operator new(sizeof(value_type
) * k
));
723 int* source
= new int[k
];
724 difference_type total_length
= 0;
726 #define POS(i) seqs_begin[(i)].first
727 #define STOPS(i) seqs_begin[(i)].second
729 // Write entries into queue.
731 for (int pi
= 0; pi
< k
; pi
++)
733 if (STOPS(pi
) != POS(pi
))
735 pl
[nrp
] = *(POS(pi
));
738 total_length
+= LENGTH(seqs_begin
[pi
]);
744 for (int k
= 0; k
< nrp
- 1; k
++)
745 for (int pi
= nrp
- 1; pi
> k
; pi
--)
746 if (comp(pl
[pi
], pl
[pi
- 1]) ||
747 (!comp(pl
[pi
- 1], pl
[pi
]) && source
[pi
] < source
[pi
- 1]))
749 std::swap(pl
[pi
- 1], pl
[pi
]);
750 std::swap(source
[pi
- 1], source
[pi
]);
755 for (int k
= 0; k
< nrp
- 1; k
++)
756 for (int pi
= nrp
- 1; pi
> k
; pi
--)
757 if (comp(pl
[pi
], pl
[pi
-1]))
759 std::swap(pl
[pi
-1], pl
[pi
]);
760 std::swap(source
[pi
-1], source
[pi
]);
768 while (nrp
> 0 && length
> 0)
770 if (source
[0] < source
[1])
773 while ((nrp
== 1 || !(comp(pl
[1], pl
[0]))) && length
> 0)
779 if (POS(source
[0]) == STOPS(source
[0]))
781 // Move everything to the left.
782 for (int s
= 0; s
< nrp
- 1; s
++)
785 source
[s
] = source
[s
+ 1];
791 pl
[0] = *(POS(source
[0]));
797 while ((nrp
== 1 || comp(pl
[0], pl
[1])) && length
> 0)
803 if (POS(source
[0]) == STOPS(source
[0]))
805 for (int s
= 0; s
< nrp
- 1; s
++)
808 source
[s
] = source
[s
+ 1];
814 pl
[0] = *(POS(source
[0]));
820 while ((j
< nrp
) && (comp(pl
[j
], pl
[j
- 1]) ||
821 (!comp(pl
[j
- 1], pl
[j
]) && (source
[j
] < source
[j
- 1]))))
823 std::swap(pl
[j
- 1], pl
[j
]);
824 std::swap(source
[j
- 1], source
[j
]);
832 while (nrp
> 0 && length
> 0)
835 while (nrp
== 1 || (!comp(pl
[1], pl
[0])) && length
> 0)
841 if (POS(source
[0]) == STOPS(source
[0]))
843 for (int s
= 0; s
< (nrp
- 1); s
++)
846 source
[s
] = source
[s
+ 1];
852 pl
[0] = *(POS(source
[0]));
857 while ((j
< nrp
) && comp(pl
[j
], pl
[j
- 1]))
859 std::swap(pl
[j
- 1], pl
[j
]);
860 std::swap(source
[j
- 1], source
[j
]);
872 /** @brief Multi-way merging procedure for a high branching factor,
875 * The head elements are kept in a loser tree.
876 * @param seqs_begin Begin iterator of iterator pair input sequence.
877 * @param seqs_end End iterator of iterator pair input sequence.
878 * @param target Begin iterator out output sequence.
879 * @param comp Comparator.
880 * @param length Maximum length to merge.
881 * @param stable Stable merging incurs a performance penalty.
882 * @return End iterator of output sequence.
884 template<typename LT
, typename RandomAccessIteratorIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
885 RandomAccessIterator3
886 multiway_merge_loser_tree(RandomAccessIteratorIterator seqs_begin
, RandomAccessIteratorIterator seqs_end
, RandomAccessIterator3 target
, Comparator comp
, _DifferenceTp length
, bool stable
)
888 _GLIBCXX_CALL(length
)
890 typedef _DifferenceTp difference_type
;
891 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
892 RandomAccessIterator1
;
893 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
896 int k
= static_cast<int>(seqs_end
- seqs_begin
);
900 difference_type total_length
= 0;
902 // Default value for potentially non-default-constructible types.
903 value_type
* defaultcons
= NULL
;
904 for (int t
= 0; t
< k
; t
++)
908 if (seqs_begin
[t
].first
== seqs_begin
[t
].second
)
909 lt
.insert_start_stable(*defaultcons
, t
, true);
911 lt
.insert_start_stable(*seqs_begin
[t
].first
, t
, false);
915 if (seqs_begin
[t
].first
== seqs_begin
[t
].second
)
916 lt
.insert_start(*defaultcons
, t
, true);
918 lt
.insert_start(*seqs_begin
[t
].first
, t
, false);
921 total_length
+= LENGTH(seqs_begin
[t
]);
929 total_length
= std::min(total_length
, length
);
935 for (difference_type i
= 0; i
< total_length
; i
++)
938 source
= lt
.get_min_source();
940 *(target
++) = *(seqs_begin
[source
].first
++);
943 if (seqs_begin
[source
].first
== seqs_begin
[source
].second
)
944 lt
.delete_min_insert_stable(*defaultcons
, true);
946 // Replace from same source.
947 lt
.delete_min_insert_stable(*seqs_begin
[source
].first
, false);
953 for (difference_type i
= 0; i
< total_length
; i
++)
956 source
= lt
.get_min_source();
958 *(target
++) = *(seqs_begin
[source
].first
++);
961 if (seqs_begin
[source
].first
== seqs_begin
[source
].second
)
962 lt
.delete_min_insert(*defaultcons
, true);
964 // Replace from same source.
965 lt
.delete_min_insert(*seqs_begin
[source
].first
, false);
972 /** @brief Multi-way merging procedure for a high branching factor,
975 * The head elements are kept in a loser tree.
976 * @param seqs_begin Begin iterator of iterator pair input sequence.
977 * @param seqs_end End iterator of iterator pair input sequence.
978 * @param target Begin iterator out output sequence.
979 * @param comp Comparator.
980 * @param length Maximum length to merge.
981 * @param stable Stable merging incurs a performance penalty.
982 * @return End iterator of output sequence.
983 * @pre No input will run out of elements during the merge.
985 template<typename LT
, typename RandomAccessIteratorIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
986 RandomAccessIterator3
987 multiway_merge_loser_tree_unguarded(RandomAccessIteratorIterator seqs_begin
, RandomAccessIteratorIterator seqs_end
, RandomAccessIterator3 target
, Comparator comp
, _DifferenceTp length
, bool stable
)
989 _GLIBCXX_CALL(length
)
990 typedef _DifferenceTp difference_type
;
992 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
993 RandomAccessIterator1
;
994 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
997 int k
= seqs_end
- seqs_begin
;
1001 difference_type total_length
= 0;
1003 for (int t
= 0; t
< k
; t
++)
1005 #if _GLIBCXX_ASSERTIONS
1006 _GLIBCXX_PARALLEL_ASSERT(seqs_begin
[t
].first
!= seqs_begin
[t
].second
);
1009 lt
.insert_start_stable(*seqs_begin
[t
].first
, t
, false);
1011 lt
.insert_start(*seqs_begin
[t
].first
, t
, false);
1013 total_length
+= LENGTH(seqs_begin
[t
]);
1021 // Do not go past end.
1022 length
= std::min(total_length
, length
);
1026 #if _GLIBCXX_ASSERTIONS
1027 difference_type i
= 0;
1032 RandomAccessIterator3 target_end
= target
+ length
;
1033 while (target
< target_end
)
1036 source
= lt
.get_min_source();
1038 #if _GLIBCXX_ASSERTIONS
1039 _GLIBCXX_PARALLEL_ASSERT(i
== 0 || !comp(*(seqs_begin
[source
].first
), *(target
- 1)));
1042 *(target
++) = *(seqs_begin
[source
].first
++);
1044 #if _GLIBCXX_ASSERTIONS
1045 _GLIBCXX_PARALLEL_ASSERT((seqs_begin
[source
].first
!= seqs_begin
[source
].second
) || (i
== length
- 1));
1049 // Replace from same source.
1050 lt
.delete_min_insert_stable(*seqs_begin
[source
].first
, false);
1056 RandomAccessIterator3 target_end
= target
+ length
;
1057 while (target
< target_end
)
1060 source
= lt
.get_min_source();
1062 #if _GLIBCXX_ASSERTIONS
1063 if (i
> 0 && comp(*(seqs_begin
[source
].first
), *(target
- 1)))
1064 printf(" %i %i %i\n", length
, i
, source
);
1065 _GLIBCXX_PARALLEL_ASSERT(i
== 0 || !comp(*(seqs_begin
[source
].first
), *(target
- 1)));
1068 *(target
++) = *(seqs_begin
[source
].first
++);
1070 #if _GLIBCXX_ASSERTIONS
1071 if (!((seqs_begin
[source
].first
!= seqs_begin
[source
].second
) || (i
>= length
- 1)))
1072 printf(" %i %i %i\n", length
, i
, source
);
1073 _GLIBCXX_PARALLEL_ASSERT((seqs_begin
[source
].first
!= seqs_begin
[source
].second
) || (i
>= length
- 1));
1077 // Replace from same source.
1078 lt
.delete_min_insert(*seqs_begin
[source
].first
, false);
1085 template<typename RandomAccessIteratorIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
1086 RandomAccessIterator3
1087 multiway_merge_loser_tree_combined(RandomAccessIteratorIterator seqs_begin
, RandomAccessIteratorIterator seqs_end
, RandomAccessIterator3 target
, Comparator comp
, _DifferenceTp length
, bool stable
)
1089 _GLIBCXX_CALL(length
)
1091 typedef _DifferenceTp difference_type
;
1093 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
1094 RandomAccessIterator1
;
1095 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
1099 RandomAccessIterator3 target_end
;
1100 difference_type overhang
= prepare_unguarded(seqs_begin
, seqs_end
,
1101 comp
, min_seq
, stable
);
1103 difference_type total_length
= 0;
1104 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; s
++)
1105 total_length
+= LENGTH(*s
);
1109 difference_type unguarded_length
= std::min(length
, total_length
- overhang
);
1110 target_end
= multiway_merge_loser_tree_unguarded
1111 <typename loser_tree_unguarded_traits
<value_type
, Comparator
>::LT
>
1112 (seqs_begin
, seqs_end
, target
, comp
, unguarded_length
, stable
);
1113 overhang
= length
- unguarded_length
;
1117 // Empty sequence found.
1119 target_end
= target
;
1122 #if _GLIBCXX_ASSERTIONS
1123 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
- overhang
);
1124 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
1127 target_end
= multiway_merge_loser_tree
1128 <typename loser_tree_traits
<value_type
, Comparator
>::LT
>
1129 (seqs_begin
, seqs_end
, target_end
, comp
, overhang
, stable
);
1131 #if _GLIBCXX_ASSERTIONS
1132 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
);
1133 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
1139 template<typename RandomAccessIteratorIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
1140 RandomAccessIterator3
1141 multiway_merge_loser_tree_sentinel(RandomAccessIteratorIterator seqs_begin
, RandomAccessIteratorIterator seqs_end
, RandomAccessIterator3 target
, Comparator comp
, _DifferenceTp length
, bool stable
)
1143 _GLIBCXX_CALL(length
)
1145 typedef _DifferenceTp difference_type
;
1146 typedef std::iterator_traits
<RandomAccessIteratorIterator
> traits_type
;
1147 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
1148 RandomAccessIterator1
;
1149 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
1151 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
1152 RandomAccessIterator1
;
1154 RandomAccessIterator3 target_end
;
1155 difference_type overhang
= prepare_unguarded_sentinel(seqs_begin
, seqs_end
, comp
);
1157 difference_type total_length
= 0;
1158 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; s
++)
1160 total_length
+= LENGTH(*s
);
1166 difference_type unguarded_length
= std::min(length
, total_length
- overhang
);
1167 target_end
= multiway_merge_loser_tree_unguarded
1168 <typename loser_tree_unguarded_traits
<value_type
, Comparator
>::LT
>
1169 (seqs_begin
, seqs_end
, target
, comp
, unguarded_length
, stable
);
1170 overhang
= length
- unguarded_length
;
1172 #if _GLIBCXX_ASSERTIONS
1173 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
- overhang
);
1174 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
1177 // Copy rest stable.
1178 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
&& overhang
> 0; s
++)
1182 difference_type local_length
= std::min((difference_type
)overhang
, (difference_type
)LENGTH(*s
));
1183 target_end
= std::copy((*s
).first
, (*s
).first
+ local_length
, target_end
);
1184 (*s
).first
+= local_length
;
1185 overhang
-= local_length
;
1188 #if _GLIBCXX_ASSERTIONS
1189 _GLIBCXX_PARALLEL_ASSERT(overhang
== 0);
1190 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
);
1191 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
1197 /** @brief Sequential multi-way merging switch.
1199 * The decision if based on the branching factor and runtime settings.
1200 * @param seqs_begin Begin iterator of iterator pair input sequence.
1201 * @param seqs_end End iterator of iterator pair input sequence.
1202 * @param target Begin iterator out output sequence.
1203 * @param comp Comparator.
1204 * @param length Maximum length to merge.
1205 * @param stable Stable merging incurs a performance penalty.
1206 * @param sentinel The sequences have a sentinel element.
1207 * @return End iterator of output sequence. */
1208 template<typename RandomAccessIteratorIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
1209 RandomAccessIterator3
1210 multiway_merge(RandomAccessIteratorIterator seqs_begin
, RandomAccessIteratorIterator seqs_end
, RandomAccessIterator3 target
, Comparator comp
, _DifferenceTp length
, bool stable
, bool sentinel
, sequential_tag
)
1212 _GLIBCXX_CALL(length
)
1214 typedef _DifferenceTp difference_type
;
1215 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
1216 RandomAccessIterator1
;
1217 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
1220 #if _GLIBCXX_ASSERTIONS
1221 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; s
++)
1222 _GLIBCXX_PARALLEL_ASSERT(is_sorted((*s
).first
, (*s
).second
, comp
));
1225 RandomAccessIterator3 return_target
= target
;
1226 int k
= static_cast<int>(seqs_end
- seqs_begin
);
1228 Settings::MultiwayMergeAlgorithm mwma
= Settings::multiway_merge_algorithm
;
1230 if (!sentinel
&& mwma
== Settings::LOSER_TREE_SENTINEL
)
1231 mwma
= Settings::LOSER_TREE_COMBINED
;
1238 return_target
= std::copy(seqs_begin
[0].first
, seqs_begin
[0].first
+ length
, target
);
1239 seqs_begin
[0].first
+= length
;
1242 return_target
= merge_advance(seqs_begin
[0].first
, seqs_begin
[0].second
, seqs_begin
[1].first
, seqs_begin
[1].second
, target
, length
, comp
);
1247 case Settings::LOSER_TREE_COMBINED
:
1248 return_target
= multiway_merge_3_combined(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1250 case Settings::LOSER_TREE_SENTINEL
:
1251 return_target
= multiway_merge_3_variant
<unguarded_iterator
>(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1254 return_target
= multiway_merge_3_variant
<guarded_iterator
>(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1261 case Settings::LOSER_TREE_COMBINED
:
1262 return_target
= multiway_merge_4_combined(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1264 case Settings::LOSER_TREE_SENTINEL
:
1265 return_target
= multiway_merge_4_variant
<unguarded_iterator
>(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1268 return_target
= multiway_merge_4_variant
<guarded_iterator
>(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1276 case Settings::BUBBLE
:
1277 return_target
= multiway_merge_bubble(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1279 #if _GLIBCXX_LOSER_TREE_EXPLICIT
1280 case Settings::LOSER_TREE_EXPLICIT
:
1281 return_target
= multiway_merge_loser_tree
<LoserTreeExplicit
<value_type
, Comparator
> >(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1284 #if _GLIBCXX_LOSER_TREE
1285 case Settings::LOSER_TREE
:
1286 return_target
= multiway_merge_loser_tree
<LoserTree
<value_type
, Comparator
> >(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1289 #if _GLIBCXX_LOSER_TREE_COMBINED
1290 case Settings::LOSER_TREE_COMBINED
:
1291 return_target
= multiway_merge_loser_tree_combined(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1294 #if _GLIBCXX_LOSER_TREE_SENTINEL
1295 case Settings::LOSER_TREE_SENTINEL
:
1296 return_target
= multiway_merge_loser_tree_sentinel(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1300 // multiway_merge algorithm not implemented.
1301 _GLIBCXX_PARALLEL_ASSERT(0);
1306 #if _GLIBCXX_ASSERTIONS
1307 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target
+ length
, comp
));
1310 return return_target
;
1313 /** @brief Parallel multi-way merge routine.
1315 * The decision if based on the branching factor and runtime settings.
1316 * @param seqs_begin Begin iterator of iterator pair input sequence.
1317 * @param seqs_end End iterator of iterator pair input sequence.
1318 * @param target Begin iterator out output sequence.
1319 * @param comp Comparator.
1320 * @param length Maximum length to merge.
1321 * @param stable Stable merging incurs a performance penalty.
1322 * @param sentinel Ignored.
1323 * @return End iterator of output sequence.
1325 template<typename RandomAccessIteratorIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
1326 RandomAccessIterator3
1327 parallel_multiway_merge(RandomAccessIteratorIterator seqs_begin
, RandomAccessIteratorIterator seqs_end
, RandomAccessIterator3 target
, Comparator comp
, _DifferenceTp length
, bool stable
, bool sentinel
)
1329 _GLIBCXX_CALL(length
)
1331 typedef _DifferenceTp difference_type
;
1332 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
1333 RandomAccessIterator1
;
1334 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
1337 #if _GLIBCXX_ASSERTIONS
1338 for (RandomAccessIteratorIterator rii
= seqs_begin
; rii
!= seqs_end
; rii
++)
1339 _GLIBCXX_PARALLEL_ASSERT(is_sorted((*rii
).first
, (*rii
).second
, comp
));
1343 int k
= static_cast<int>(seqs_end
- seqs_begin
);
1345 difference_type total_length
= 0;
1346 for (RandomAccessIteratorIterator raii
= seqs_begin
; raii
!= seqs_end
; raii
++)
1347 total_length
+= LENGTH(*raii
);
1349 _GLIBCXX_CALL(total_length
)
1351 if (total_length
== 0 || k
== 0)
1354 thread_index_t num_threads
= static_cast<thread_index_t
>(std::min(static_cast<difference_type
>(get_max_threads()), total_length
));
1356 bool tight
= (total_length
== length
);
1358 // Thread t will have to merge pieces[iam][0..k - 1]
1359 std::vector
<std::pair
<difference_type
, difference_type
> >* pieces
= new std::vector
<std::pair
<difference_type
, difference_type
> >[num_threads
];
1360 for (int s
= 0; s
< num_threads
; s
++)
1361 pieces
[s
].resize(k
);
1363 difference_type num_samples
= Settings::merge_oversampling
* num_threads
;
1365 if (Settings::multiway_merge_splitting
== Settings::SAMPLING
)
1367 value_type
* samples
= static_cast<value_type
*>(::operator new(sizeof(value_type
) * k
* num_samples
));
1369 for (int s
= 0; s
< k
; s
++)
1370 for (int i
= 0; (difference_type
)i
< num_samples
; i
++)
1372 difference_type sample_index
= static_cast<difference_type
>(LENGTH(seqs_begin
[s
]) * (double(i
+ 1) / (num_samples
+ 1)) * (double(length
) / total_length
));
1373 samples
[s
* num_samples
+ i
] = seqs_begin
[s
].first
[sample_index
];
1377 __gnu_sequential::stable_sort(samples
, samples
+ (num_samples
* k
), comp
);
1379 __gnu_sequential::sort(samples
, samples
+ (num_samples
* k
), comp
);
1381 for (int slab
= 0; slab
< num_threads
; slab
++)
1382 // For each slab / processor.
1383 for (int seq
= 0; seq
< k
; seq
++)
1385 // For each sequence.
1387 pieces
[slab
][seq
].first
= std::upper_bound(seqs_begin
[seq
].first
, seqs_begin
[seq
].second
, samples
[num_samples
* k
* slab
/ num_threads
], comp
) - seqs_begin
[seq
].first
;
1390 // Absolute beginning.
1391 pieces
[slab
][seq
].first
= 0;
1393 if ((slab
+ 1) < num_threads
)
1394 pieces
[slab
][seq
].second
= std::upper_bound(seqs_begin
[seq
].first
, seqs_begin
[seq
].second
, samples
[num_samples
* k
* (slab
+ 1) / num_threads
], comp
) - seqs_begin
[seq
].first
;
1396 pieces
[slab
][seq
].second
= LENGTH(seqs_begin
[seq
]); //absolute ending
1402 // (Settings::multiway_merge_splitting == Settings::EXACT).
1403 std::vector
<RandomAccessIterator1
>* offsets
= new std::vector
<RandomAccessIterator1
>[num_threads
];
1404 std::vector
<std::pair
<RandomAccessIterator1
, RandomAccessIterator1
> > se(k
);
1406 copy(seqs_begin
, seqs_end
, se
.begin());
1408 difference_type
* borders
= static_cast<difference_type
*>(__builtin_alloca(sizeof(difference_type
) * (num_threads
+ 1)));
1409 equally_split(length
, num_threads
, borders
);
1411 for (int s
= 0; s
< (num_threads
- 1); s
++)
1413 offsets
[s
].resize(k
);
1414 multiseq_partition(se
.begin(), se
.end(), borders
[s
+ 1],
1415 offsets
[s
].begin(), comp
);
1417 // Last one also needed and available.
1420 offsets
[num_threads
- 1].resize(k
);
1421 multiseq_partition(se
.begin(), se
.end(),
1422 difference_type(length
),
1423 offsets
[num_threads
- 1].begin(), comp
);
1428 for (int slab
= 0; slab
< num_threads
; slab
++)
1430 // For each slab / processor.
1431 for (int seq
= 0; seq
< k
; seq
++)
1433 // For each sequence.
1436 // Absolute beginning.
1437 pieces
[slab
][seq
].first
= 0;
1440 pieces
[slab
][seq
].first
= pieces
[slab
- 1][seq
].second
;
1441 if (!tight
|| slab
< (num_threads
- 1))
1442 pieces
[slab
][seq
].second
= offsets
[slab
][seq
] - seqs_begin
[seq
].first
;
1445 // slab == num_threads - 1
1446 pieces
[slab
][seq
].second
= LENGTH(seqs_begin
[seq
]);
1453 # pragma omp parallel num_threads(num_threads)
1455 thread_index_t iam
= omp_get_thread_num();
1457 difference_type target_position
= 0;
1459 for (int c
= 0; c
< k
; c
++)
1460 target_position
+= pieces
[iam
][c
].first
;
1464 std::pair
<RandomAccessIterator1
, RandomAccessIterator1
>* chunks
= new std::pair
<RandomAccessIterator1
, RandomAccessIterator1
>[k
];
1466 difference_type local_length
= 0;
1467 for (int s
= 0; s
< k
; s
++)
1469 chunks
[s
] = std::make_pair(seqs_begin
[s
].first
+ pieces
[iam
][s
].first
, seqs_begin
[s
].first
+ pieces
[iam
][s
].second
);
1470 local_length
+= LENGTH(chunks
[s
]);
1473 multiway_merge(chunks
, chunks
+ k
, target
+ target_position
, comp
,
1474 std::min(local_length
, length
- target_position
),
1475 stable
, false, sequential_tag());
1481 RandomAccessIterator1 begin0
= seqs_begin
[0].first
+ pieces
[iam
][0].first
, begin1
= seqs_begin
[1].first
+ pieces
[iam
][1].first
;
1482 merge_advance(begin0
,
1483 seqs_begin
[0].first
+ pieces
[iam
][0].second
,
1485 seqs_begin
[1].first
+ pieces
[iam
][1].second
,
1486 target
+ target_position
,
1487 (pieces
[iam
][0].second
- pieces
[iam
][0].first
) + (pieces
[iam
][1].second
- pieces
[iam
][1].first
),
1492 #if _GLIBCXX_ASSERTIONS
1493 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target
+ length
, comp
));
1496 // Update ends of sequences.
1497 for (int s
= 0; s
< k
; s
++)
1498 seqs_begin
[s
].first
+= pieces
[num_threads
- 1][s
].second
;
1502 return target
+ length
;
1506 * @brief Multi-way merging front-end.
1507 * @param seqs_begin Begin iterator of iterator pair input sequence.
1508 * @param seqs_end End iterator of iterator pair input sequence.
1509 * @param target Begin iterator out output sequence.
1510 * @param comp Comparator.
1511 * @param length Maximum length to merge.
1512 * @param stable Stable merging incurs a performance penalty.
1513 * @return End iterator of output sequence.
1515 template<typename RandomAccessIteratorPairIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
1516 RandomAccessIterator3
1517 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
,
1518 RandomAccessIteratorPairIterator seqs_end
,
1519 RandomAccessIterator3 target
, Comparator comp
,
1520 _DifferenceTp length
, bool stable
)
1522 typedef _DifferenceTp difference_type
;
1523 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1525 if (seqs_begin
== seqs_end
)
1528 RandomAccessIterator3 target_end
;
1529 if (_GLIBCXX_PARALLEL_CONDITION(((seqs_end
- seqs_begin
) >= Settings::multiway_merge_minimal_k
) && ((sequence_index_t
)length
>= Settings::multiway_merge_minimal_n
)))
1530 target_end
= parallel_multiway_merge(seqs_begin
, seqs_end
, target
, comp
, (difference_type
)length
, stable
, false);
1532 target_end
= multiway_merge(seqs_begin
, seqs_end
, target
, comp
, length
, stable
, false, sequential_tag());
1537 /** @brief Multi-way merging front-end.
1538 * @param seqs_begin Begin iterator of iterator pair input sequence.
1539 * @param seqs_end End iterator of iterator pair input sequence.
1540 * @param target Begin iterator out output sequence.
1541 * @param comp Comparator.
1542 * @param length Maximum length to merge.
1543 * @param stable Stable merging incurs a performance penalty.
1544 * @return End iterator of output sequence.
1545 * @pre For each @c i, @c seqs_begin[i].second must be the end
1546 * marker of the sequence, but also reference the one more sentinel
1548 template<typename RandomAccessIteratorPairIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
1549 RandomAccessIterator3
1550 multiway_merge_sentinel(RandomAccessIteratorPairIterator seqs_begin
,
1551 RandomAccessIteratorPairIterator seqs_end
,
1552 RandomAccessIterator3 target
,
1554 _DifferenceTp length
,
1557 typedef _DifferenceTp difference_type
;
1559 if (seqs_begin
== seqs_end
)
1562 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1564 if (_GLIBCXX_PARALLEL_CONDITION(((seqs_end
- seqs_begin
) >= Settings::multiway_merge_minimal_k
) && ((sequence_index_t
)length
>= Settings::multiway_merge_minimal_n
)))
1565 return parallel_multiway_merge(seqs_begin
, seqs_end
, target
, comp
, (typename
std::iterator_traits
<RandomAccessIterator3
>::difference_type
)length
, stable
, true);
1567 return multiway_merge(seqs_begin
, seqs_end
, target
, comp
, length
, stable
, true, sequential_tag());