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
* arbitrary_element
= NULL
;
905 for (int t
= 0; t
< k
; t
++)
907 if(arbitrary_element
== NULL
&& LENGTH(seqs_begin
[t
]) > 0)
908 arbitrary_element
= &(*seqs_begin
[t
].first
);
909 total_length
+= LENGTH(seqs_begin
[t
]);
912 if(total_length
== 0)
915 for (int t
= 0; t
< k
; t
++)
919 if (seqs_begin
[t
].first
== seqs_begin
[t
].second
)
920 lt
.insert_start_stable(*arbitrary_element
, t
, true);
922 lt
.insert_start_stable(*seqs_begin
[t
].first
, t
, false);
926 if (seqs_begin
[t
].first
== seqs_begin
[t
].second
)
927 lt
.insert_start(*arbitrary_element
, t
, true);
929 lt
.insert_start(*seqs_begin
[t
].first
, t
, false);
938 total_length
= std::min(total_length
, length
);
944 for (difference_type i
= 0; i
< total_length
; i
++)
947 source
= lt
.get_min_source();
949 *(target
++) = *(seqs_begin
[source
].first
++);
952 if (seqs_begin
[source
].first
== seqs_begin
[source
].second
)
953 lt
.delete_min_insert_stable(*arbitrary_element
, true);
955 // Replace from same source.
956 lt
.delete_min_insert_stable(*seqs_begin
[source
].first
, false);
962 for (difference_type i
= 0; i
< total_length
; i
++)
965 source
= lt
.get_min_source();
967 *(target
++) = *(seqs_begin
[source
].first
++);
970 if (seqs_begin
[source
].first
== seqs_begin
[source
].second
)
971 lt
.delete_min_insert(*arbitrary_element
, true);
973 // Replace from same source.
974 lt
.delete_min_insert(*seqs_begin
[source
].first
, false);
981 /** @brief Multi-way merging procedure for a high branching factor,
984 * The head elements are kept in a loser tree.
985 * @param seqs_begin Begin iterator of iterator pair input sequence.
986 * @param seqs_end End iterator of iterator pair input sequence.
987 * @param target Begin iterator out output sequence.
988 * @param comp Comparator.
989 * @param length Maximum length to merge.
990 * @param stable Stable merging incurs a performance penalty.
991 * @return End iterator of output sequence.
992 * @pre No input will run out of elements during the merge.
994 template<typename LT
, typename RandomAccessIteratorIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
995 RandomAccessIterator3
996 multiway_merge_loser_tree_unguarded(RandomAccessIteratorIterator seqs_begin
, RandomAccessIteratorIterator seqs_end
, RandomAccessIterator3 target
, Comparator comp
, _DifferenceTp length
, bool stable
)
998 _GLIBCXX_CALL(length
)
999 typedef _DifferenceTp difference_type
;
1001 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
1002 RandomAccessIterator1
;
1003 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
1006 int k
= seqs_end
- seqs_begin
;
1010 difference_type total_length
= 0;
1012 for (int t
= 0; t
< k
; t
++)
1014 #if _GLIBCXX_ASSERTIONS
1015 _GLIBCXX_PARALLEL_ASSERT(seqs_begin
[t
].first
!= seqs_begin
[t
].second
);
1018 lt
.insert_start_stable(*seqs_begin
[t
].first
, t
, false);
1020 lt
.insert_start(*seqs_begin
[t
].first
, t
, false);
1022 total_length
+= LENGTH(seqs_begin
[t
]);
1030 // Do not go past end.
1031 length
= std::min(total_length
, length
);
1035 #if _GLIBCXX_ASSERTIONS
1036 difference_type i
= 0;
1041 RandomAccessIterator3 target_end
= target
+ length
;
1042 while (target
< target_end
)
1045 source
= lt
.get_min_source();
1047 #if _GLIBCXX_ASSERTIONS
1048 _GLIBCXX_PARALLEL_ASSERT(i
== 0 || !comp(*(seqs_begin
[source
].first
), *(target
- 1)));
1051 *(target
++) = *(seqs_begin
[source
].first
++);
1053 #if _GLIBCXX_ASSERTIONS
1054 _GLIBCXX_PARALLEL_ASSERT((seqs_begin
[source
].first
!= seqs_begin
[source
].second
) || (i
== length
- 1));
1058 // Replace from same source.
1059 lt
.delete_min_insert_stable(*seqs_begin
[source
].first
, false);
1065 RandomAccessIterator3 target_end
= target
+ length
;
1066 while (target
< target_end
)
1069 source
= lt
.get_min_source();
1071 #if _GLIBCXX_ASSERTIONS
1072 if (i
> 0 && comp(*(seqs_begin
[source
].first
), *(target
- 1)))
1073 printf(" %i %i %i\n", length
, i
, source
);
1074 _GLIBCXX_PARALLEL_ASSERT(i
== 0 || !comp(*(seqs_begin
[source
].first
), *(target
- 1)));
1077 *(target
++) = *(seqs_begin
[source
].first
++);
1079 #if _GLIBCXX_ASSERTIONS
1080 if (!((seqs_begin
[source
].first
!= seqs_begin
[source
].second
) || (i
>= length
- 1)))
1081 printf(" %i %i %i\n", length
, i
, source
);
1082 _GLIBCXX_PARALLEL_ASSERT((seqs_begin
[source
].first
!= seqs_begin
[source
].second
) || (i
>= length
- 1));
1086 // Replace from same source.
1087 lt
.delete_min_insert(*seqs_begin
[source
].first
, false);
1094 template<typename RandomAccessIteratorIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
1095 RandomAccessIterator3
1096 multiway_merge_loser_tree_combined(RandomAccessIteratorIterator seqs_begin
, RandomAccessIteratorIterator seqs_end
, RandomAccessIterator3 target
, Comparator comp
, _DifferenceTp length
, bool stable
)
1098 _GLIBCXX_CALL(length
)
1100 typedef _DifferenceTp difference_type
;
1102 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
1103 RandomAccessIterator1
;
1104 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
1108 RandomAccessIterator3 target_end
;
1109 difference_type overhang
= prepare_unguarded(seqs_begin
, seqs_end
,
1110 comp
, min_seq
, stable
);
1112 difference_type total_length
= 0;
1113 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; s
++)
1114 total_length
+= LENGTH(*s
);
1118 difference_type unguarded_length
= std::min(length
, total_length
- overhang
);
1119 target_end
= multiway_merge_loser_tree_unguarded
1120 <typename loser_tree_unguarded_traits
<value_type
, Comparator
>::LT
>
1121 (seqs_begin
, seqs_end
, target
, comp
, unguarded_length
, stable
);
1122 overhang
= length
- unguarded_length
;
1126 // Empty sequence found.
1128 target_end
= target
;
1131 #if _GLIBCXX_ASSERTIONS
1132 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
- overhang
);
1133 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
1136 target_end
= multiway_merge_loser_tree
1137 <typename loser_tree_traits
<value_type
, Comparator
>::LT
>
1138 (seqs_begin
, seqs_end
, target_end
, comp
, overhang
, stable
);
1140 #if _GLIBCXX_ASSERTIONS
1141 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
);
1142 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
1148 template<typename RandomAccessIteratorIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
1149 RandomAccessIterator3
1150 multiway_merge_loser_tree_sentinel(RandomAccessIteratorIterator seqs_begin
, RandomAccessIteratorIterator seqs_end
, RandomAccessIterator3 target
, Comparator comp
, _DifferenceTp length
, bool stable
)
1152 _GLIBCXX_CALL(length
)
1154 typedef _DifferenceTp difference_type
;
1155 typedef std::iterator_traits
<RandomAccessIteratorIterator
> traits_type
;
1156 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
1157 RandomAccessIterator1
;
1158 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
1160 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
1161 RandomAccessIterator1
;
1163 RandomAccessIterator3 target_end
;
1164 difference_type overhang
= prepare_unguarded_sentinel(seqs_begin
, seqs_end
, comp
);
1166 difference_type total_length
= 0;
1167 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; s
++)
1169 total_length
+= LENGTH(*s
);
1175 difference_type unguarded_length
= std::min(length
, total_length
- overhang
);
1176 target_end
= multiway_merge_loser_tree_unguarded
1177 <typename loser_tree_unguarded_traits
<value_type
, Comparator
>::LT
>
1178 (seqs_begin
, seqs_end
, target
, comp
, unguarded_length
, stable
);
1179 overhang
= length
- unguarded_length
;
1181 #if _GLIBCXX_ASSERTIONS
1182 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
- overhang
);
1183 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
1186 // Copy rest stable.
1187 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
&& overhang
> 0; s
++)
1191 difference_type local_length
= std::min((difference_type
)overhang
, (difference_type
)LENGTH(*s
));
1192 target_end
= std::copy((*s
).first
, (*s
).first
+ local_length
, target_end
);
1193 (*s
).first
+= local_length
;
1194 overhang
-= local_length
;
1197 #if _GLIBCXX_ASSERTIONS
1198 _GLIBCXX_PARALLEL_ASSERT(overhang
== 0);
1199 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
);
1200 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
1206 /** @brief Sequential multi-way merging switch.
1208 * The decision if based on the branching factor and runtime settings.
1209 * @param seqs_begin Begin iterator of iterator pair input sequence.
1210 * @param seqs_end End iterator of iterator pair input sequence.
1211 * @param target Begin iterator out output sequence.
1212 * @param comp Comparator.
1213 * @param length Maximum length to merge.
1214 * @param stable Stable merging incurs a performance penalty.
1215 * @param sentinel The sequences have a sentinel element.
1216 * @return End iterator of output sequence. */
1217 template<typename RandomAccessIteratorIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
1218 RandomAccessIterator3
1219 multiway_merge(RandomAccessIteratorIterator seqs_begin
, RandomAccessIteratorIterator seqs_end
, RandomAccessIterator3 target
, Comparator comp
, _DifferenceTp length
, bool stable
, bool sentinel
, sequential_tag
)
1221 _GLIBCXX_CALL(length
)
1223 typedef _DifferenceTp difference_type
;
1224 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
1225 RandomAccessIterator1
;
1226 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
1229 #if _GLIBCXX_ASSERTIONS
1230 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; s
++)
1231 _GLIBCXX_PARALLEL_ASSERT(is_sorted((*s
).first
, (*s
).second
, comp
));
1234 RandomAccessIterator3 return_target
= target
;
1235 int k
= static_cast<int>(seqs_end
- seqs_begin
);
1237 Settings::MultiwayMergeAlgorithm mwma
= Settings::multiway_merge_algorithm
;
1239 if (!sentinel
&& mwma
== Settings::LOSER_TREE_SENTINEL
)
1240 mwma
= Settings::LOSER_TREE_COMBINED
;
1247 return_target
= std::copy(seqs_begin
[0].first
, seqs_begin
[0].first
+ length
, target
);
1248 seqs_begin
[0].first
+= length
;
1251 return_target
= merge_advance(seqs_begin
[0].first
, seqs_begin
[0].second
, seqs_begin
[1].first
, seqs_begin
[1].second
, target
, length
, comp
);
1256 case Settings::LOSER_TREE_COMBINED
:
1257 return_target
= multiway_merge_3_combined(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1259 case Settings::LOSER_TREE_SENTINEL
:
1260 return_target
= multiway_merge_3_variant
<unguarded_iterator
>(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1263 return_target
= multiway_merge_3_variant
<guarded_iterator
>(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1270 case Settings::LOSER_TREE_COMBINED
:
1271 return_target
= multiway_merge_4_combined(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1273 case Settings::LOSER_TREE_SENTINEL
:
1274 return_target
= multiway_merge_4_variant
<unguarded_iterator
>(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1277 return_target
= multiway_merge_4_variant
<guarded_iterator
>(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1285 case Settings::BUBBLE
:
1286 return_target
= multiway_merge_bubble(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1288 #if _GLIBCXX_LOSER_TREE_EXPLICIT
1289 case Settings::LOSER_TREE_EXPLICIT
:
1290 return_target
= multiway_merge_loser_tree
<LoserTreeExplicit
<value_type
, Comparator
> >(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1293 #if _GLIBCXX_LOSER_TREE
1294 case Settings::LOSER_TREE
:
1295 return_target
= multiway_merge_loser_tree
<LoserTree
<value_type
, Comparator
> >(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1298 #if _GLIBCXX_LOSER_TREE_COMBINED
1299 case Settings::LOSER_TREE_COMBINED
:
1300 return_target
= multiway_merge_loser_tree_combined(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1303 #if _GLIBCXX_LOSER_TREE_SENTINEL
1304 case Settings::LOSER_TREE_SENTINEL
:
1305 return_target
= multiway_merge_loser_tree_sentinel(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1309 // multiway_merge algorithm not implemented.
1310 _GLIBCXX_PARALLEL_ASSERT(0);
1315 #if _GLIBCXX_ASSERTIONS
1316 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target
+ length
, comp
));
1319 return return_target
;
1322 /** @brief Parallel multi-way merge routine.
1324 * The decision if based on the branching factor and runtime settings.
1325 * @param seqs_begin Begin iterator of iterator pair input sequence.
1326 * @param seqs_end End iterator of iterator pair input sequence.
1327 * @param target Begin iterator out output sequence.
1328 * @param comp Comparator.
1329 * @param length Maximum length to merge.
1330 * @param stable Stable merging incurs a performance penalty.
1331 * @param sentinel Ignored.
1332 * @return End iterator of output sequence.
1334 template<typename RandomAccessIteratorIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
1335 RandomAccessIterator3
1336 parallel_multiway_merge(RandomAccessIteratorIterator seqs_begin
, RandomAccessIteratorIterator seqs_end
, RandomAccessIterator3 target
, Comparator comp
, _DifferenceTp length
, bool stable
, bool sentinel
)
1338 _GLIBCXX_CALL(length
)
1340 typedef _DifferenceTp difference_type
;
1341 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
1342 RandomAccessIterator1
;
1343 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
1346 #if _GLIBCXX_ASSERTIONS
1347 for (RandomAccessIteratorIterator rii
= seqs_begin
; rii
!= seqs_end
; rii
++)
1348 _GLIBCXX_PARALLEL_ASSERT(is_sorted((*rii
).first
, (*rii
).second
, comp
));
1352 int k
= static_cast<int>(seqs_end
- seqs_begin
);
1354 difference_type total_length
= 0;
1355 for (RandomAccessIteratorIterator raii
= seqs_begin
; raii
!= seqs_end
; raii
++)
1356 total_length
+= LENGTH(*raii
);
1358 _GLIBCXX_CALL(total_length
)
1360 if (total_length
== 0 || k
== 0)
1363 thread_index_t num_threads
= static_cast<thread_index_t
>(std::min(static_cast<difference_type
>(get_max_threads()), total_length
));
1365 bool tight
= (total_length
== length
);
1367 // Thread t will have to merge pieces[iam][0..k - 1]
1368 std::vector
<std::pair
<difference_type
, difference_type
> >* pieces
= new std::vector
<std::pair
<difference_type
, difference_type
> >[num_threads
];
1369 for (int s
= 0; s
< num_threads
; s
++)
1370 pieces
[s
].resize(k
);
1372 difference_type num_samples
= Settings::merge_oversampling
* num_threads
;
1374 if (Settings::multiway_merge_splitting
== Settings::SAMPLING
)
1376 value_type
* samples
= static_cast<value_type
*>(::operator new(sizeof(value_type
) * k
* num_samples
));
1378 for (int s
= 0; s
< k
; s
++)
1379 for (int i
= 0; (difference_type
)i
< num_samples
; i
++)
1381 difference_type sample_index
= static_cast<difference_type
>(LENGTH(seqs_begin
[s
]) * (double(i
+ 1) / (num_samples
+ 1)) * (double(length
) / total_length
));
1382 samples
[s
* num_samples
+ i
] = seqs_begin
[s
].first
[sample_index
];
1386 __gnu_sequential::stable_sort(samples
, samples
+ (num_samples
* k
), comp
);
1388 __gnu_sequential::sort(samples
, samples
+ (num_samples
* k
), comp
);
1390 for (int slab
= 0; slab
< num_threads
; slab
++)
1391 // For each slab / processor.
1392 for (int seq
= 0; seq
< k
; seq
++)
1394 // For each sequence.
1396 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
;
1399 // Absolute beginning.
1400 pieces
[slab
][seq
].first
= 0;
1402 if ((slab
+ 1) < num_threads
)
1403 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
;
1405 pieces
[slab
][seq
].second
= LENGTH(seqs_begin
[seq
]); //absolute ending
1411 // (Settings::multiway_merge_splitting == Settings::EXACT).
1412 std::vector
<RandomAccessIterator1
>* offsets
= new std::vector
<RandomAccessIterator1
>[num_threads
];
1413 std::vector
<std::pair
<RandomAccessIterator1
, RandomAccessIterator1
> > se(k
);
1415 copy(seqs_begin
, seqs_end
, se
.begin());
1417 difference_type
* borders
= static_cast<difference_type
*>(__builtin_alloca(sizeof(difference_type
) * (num_threads
+ 1)));
1418 equally_split(length
, num_threads
, borders
);
1420 for (int s
= 0; s
< (num_threads
- 1); s
++)
1422 offsets
[s
].resize(k
);
1423 multiseq_partition(se
.begin(), se
.end(), borders
[s
+ 1],
1424 offsets
[s
].begin(), comp
);
1426 // Last one also needed and available.
1429 offsets
[num_threads
- 1].resize(k
);
1430 multiseq_partition(se
.begin(), se
.end(),
1431 difference_type(length
),
1432 offsets
[num_threads
- 1].begin(), comp
);
1437 for (int slab
= 0; slab
< num_threads
; slab
++)
1439 // For each slab / processor.
1440 for (int seq
= 0; seq
< k
; seq
++)
1442 // For each sequence.
1445 // Absolute beginning.
1446 pieces
[slab
][seq
].first
= 0;
1449 pieces
[slab
][seq
].first
= pieces
[slab
- 1][seq
].second
;
1450 if (!tight
|| slab
< (num_threads
- 1))
1451 pieces
[slab
][seq
].second
= offsets
[slab
][seq
] - seqs_begin
[seq
].first
;
1454 // slab == num_threads - 1
1455 pieces
[slab
][seq
].second
= LENGTH(seqs_begin
[seq
]);
1462 # pragma omp parallel num_threads(num_threads)
1464 thread_index_t iam
= omp_get_thread_num();
1466 difference_type target_position
= 0;
1468 for (int c
= 0; c
< k
; c
++)
1469 target_position
+= pieces
[iam
][c
].first
;
1473 std::pair
<RandomAccessIterator1
, RandomAccessIterator1
>* chunks
= new std::pair
<RandomAccessIterator1
, RandomAccessIterator1
>[k
];
1475 difference_type local_length
= 0;
1476 for (int s
= 0; s
< k
; s
++)
1478 chunks
[s
] = std::make_pair(seqs_begin
[s
].first
+ pieces
[iam
][s
].first
, seqs_begin
[s
].first
+ pieces
[iam
][s
].second
);
1479 local_length
+= LENGTH(chunks
[s
]);
1482 multiway_merge(chunks
, chunks
+ k
, target
+ target_position
, comp
,
1483 std::min(local_length
, length
- target_position
),
1484 stable
, false, sequential_tag());
1490 RandomAccessIterator1 begin0
= seqs_begin
[0].first
+ pieces
[iam
][0].first
, begin1
= seqs_begin
[1].first
+ pieces
[iam
][1].first
;
1491 merge_advance(begin0
,
1492 seqs_begin
[0].first
+ pieces
[iam
][0].second
,
1494 seqs_begin
[1].first
+ pieces
[iam
][1].second
,
1495 target
+ target_position
,
1496 (pieces
[iam
][0].second
- pieces
[iam
][0].first
) + (pieces
[iam
][1].second
- pieces
[iam
][1].first
),
1501 #if _GLIBCXX_ASSERTIONS
1502 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target
+ length
, comp
));
1505 // Update ends of sequences.
1506 for (int s
= 0; s
< k
; s
++)
1507 seqs_begin
[s
].first
+= pieces
[num_threads
- 1][s
].second
;
1511 return target
+ length
;
1515 * @brief Multi-way merging front-end.
1516 * @param seqs_begin Begin iterator of iterator pair input sequence.
1517 * @param seqs_end End iterator of iterator pair input sequence.
1518 * @param target Begin iterator out output sequence.
1519 * @param comp Comparator.
1520 * @param length Maximum length to merge.
1521 * @param stable Stable merging incurs a performance penalty.
1522 * @return End iterator of output sequence.
1524 template<typename RandomAccessIteratorPairIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
1525 RandomAccessIterator3
1526 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
,
1527 RandomAccessIteratorPairIterator seqs_end
,
1528 RandomAccessIterator3 target
, Comparator comp
,
1529 _DifferenceTp length
, bool stable
)
1531 typedef _DifferenceTp difference_type
;
1532 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1534 if (seqs_begin
== seqs_end
)
1537 RandomAccessIterator3 target_end
;
1538 if (_GLIBCXX_PARALLEL_CONDITION(((seqs_end
- seqs_begin
) >= Settings::multiway_merge_minimal_k
) && ((sequence_index_t
)length
>= Settings::multiway_merge_minimal_n
)))
1539 target_end
= parallel_multiway_merge(seqs_begin
, seqs_end
, target
, comp
, (difference_type
)length
, stable
, false);
1541 target_end
= multiway_merge(seqs_begin
, seqs_end
, target
, comp
, length
, stable
, false, sequential_tag());
1546 /** @brief Multi-way merging front-end.
1547 * @param seqs_begin Begin iterator of iterator pair input sequence.
1548 * @param seqs_end End iterator of iterator pair input sequence.
1549 * @param target Begin iterator out output sequence.
1550 * @param comp Comparator.
1551 * @param length Maximum length to merge.
1552 * @param stable Stable merging incurs a performance penalty.
1553 * @return End iterator of output sequence.
1554 * @pre For each @c i, @c seqs_begin[i].second must be the end
1555 * marker of the sequence, but also reference the one more sentinel
1557 template<typename RandomAccessIteratorPairIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
1558 RandomAccessIterator3
1559 multiway_merge_sentinel(RandomAccessIteratorPairIterator seqs_begin
,
1560 RandomAccessIteratorPairIterator seqs_end
,
1561 RandomAccessIterator3 target
,
1563 _DifferenceTp length
,
1566 typedef _DifferenceTp difference_type
;
1568 if (seqs_begin
== seqs_end
)
1571 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1573 if (_GLIBCXX_PARALLEL_CONDITION(((seqs_end
- seqs_begin
) >= Settings::multiway_merge_minimal_k
) && ((sequence_index_t
)length
>= Settings::multiway_merge_minimal_n
)))
1574 return parallel_multiway_merge(seqs_begin
, seqs_end
, target
, comp
, (typename
std::iterator_traits
<RandomAccessIterator3
>::difference_type
)length
, stable
, true);
1576 return multiway_merge(seqs_begin
, seqs_end
, target
, comp
, length
, stable
, true, sequential_tag());