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.
33 * This file is a GNU parallel extension to the Standard C++ Library.
36 // Written by Johannes Singler.
38 #ifndef _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H
39 #define _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H
43 #include <bits/stl_algo.h>
44 #include <parallel/features.h>
45 #include <parallel/parallel.h>
46 #include <parallel/merge.h>
47 #include <parallel/losertree.h>
48 #include <parallel/timing.h>
49 #if _GLIBCXX_ASSERTIONS
50 #include <parallel/checkers.h>
53 /** @brief Length of a sequence described by a pair of iterators. */
54 #define LENGTH(s) ((s).second - (s).first)
56 // XXX need iterator typedefs
57 namespace __gnu_parallel
59 template<typename RandomAccessIterator
, typename Comparator
>
60 class guarded_iterator
;
62 template<typename RandomAccessIterator
, typename Comparator
>
64 operator<(guarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
65 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
67 template<typename RandomAccessIterator
, typename Comparator
>
69 operator<=(guarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
70 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
72 /** @brief Iterator wrapper supporting an implicit supremum at the end
73 of the sequence, dominating all comparisons.
74 * Deriving from RandomAccessIterator is not possible since
75 * RandomAccessIterator need not be a class.
77 template<typename RandomAccessIterator
, typename Comparator
>
78 class guarded_iterator
81 /** @brief Current iterator position. */
82 RandomAccessIterator current
;
84 /** @brief End iterator of the sequence. */
85 RandomAccessIterator end
;
87 /** @brief Comparator. */
91 /** @brief Constructor. Sets iterator to beginning of sequence.
92 * @param begin Begin iterator of sequence.
93 * @param end End iterator of sequence.
94 * @param comp Comparator provided for associated overloaded
95 * compare operators. */
96 inline guarded_iterator(RandomAccessIterator begin
,
97 RandomAccessIterator end
, Comparator
& comp
)
98 : current(begin
), end(end
), comp(comp
)
101 /** @brief Pre-increment operator.
103 inline guarded_iterator
<RandomAccessIterator
, Comparator
>&
110 /** @brief Dereference operator.
111 * @return Referenced element. */
112 inline typename
std::iterator_traits
<RandomAccessIterator
>::value_type
116 /** @brief Convert to wrapped iterator.
117 * @return Wrapped iterator. */
118 inline operator RandomAccessIterator()
122 operator< <RandomAccessIterator
, Comparator
>(guarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
, guarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
125 operator<= <RandomAccessIterator
, Comparator
>(guarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
, guarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
128 /** @brief Compare two elements referenced by guarded iterators.
129 * @param bi1 First iterator.
130 * @param bi2 Second iterator.
131 * @return @c True if less. */
132 template<typename RandomAccessIterator
, typename Comparator
>
134 operator<(guarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
135 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
)
137 if (bi1
.current
== bi1
.end
) //bi1 is sup
138 return bi2
.current
== bi2
.end
; //bi2 is not sup
139 if (bi2
.current
== bi2
.end
) //bi2 is sup
141 return (bi1
.comp
)(*bi1
, *bi2
); //normal compare
144 /** @brief Compare two elements referenced by guarded iterators.
145 * @param bi1 First iterator.
146 * @param bi2 Second iterator.
147 * @return @c True if less equal. */
148 template<typename RandomAccessIterator
, typename Comparator
>
150 operator<=(guarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
151 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
)
153 if (bi2
.current
== bi2
.end
) //bi1 is sup
154 return bi1
.current
!= bi1
.end
; //bi2 is not sup
155 if (bi1
.current
== bi1
.end
) //bi2 is sup
157 return !(bi1
.comp
)(*bi2
, *bi1
); //normal compare
160 template<typename RandomAccessIterator
, typename Comparator
>
161 class unguarded_iterator
;
163 template<typename RandomAccessIterator
, typename Comparator
>
165 operator<(unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
166 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
168 template<typename RandomAccessIterator
, typename Comparator
>
170 operator<=(unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
171 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
173 template<typename RandomAccessIterator
, typename Comparator
>
174 class unguarded_iterator
177 /** @brief Current iterator position. */
178 RandomAccessIterator
& current
;
179 /** @brief Comparator. */
180 mutable Comparator
& comp
;
183 /** @brief Constructor. Sets iterator to beginning of sequence.
184 * @param begin Begin iterator of sequence.
185 * @param end Unused, only for compatibility.
186 * @param comp Unused, only for compatibility. */
187 inline unguarded_iterator(RandomAccessIterator begin
,
188 RandomAccessIterator end
, Comparator
& comp
)
189 : current(begin
), comp(comp
)
192 /** @brief Pre-increment operator.
194 inline unguarded_iterator
<RandomAccessIterator
, Comparator
>&
201 /** @brief Dereference operator.
202 * @return Referenced element. */
203 inline typename
std::iterator_traits
<RandomAccessIterator
>::value_type
207 /** @brief Convert to wrapped iterator.
208 * @return Wrapped iterator. */
210 operator RandomAccessIterator()
214 operator< <RandomAccessIterator
, Comparator
>(unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
, unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
217 operator<= <RandomAccessIterator
, Comparator
>(unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
, unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
220 /** @brief Compare two elements referenced by unguarded iterators.
221 * @param bi1 First iterator.
222 * @param bi2 Second iterator.
223 * @return @c True if less. */
224 template<typename RandomAccessIterator
, typename Comparator
>
226 operator<(unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
227 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
)
230 return (bi1
.comp
)(*bi1
, *bi2
);
233 /** @brief Compare two elements referenced by unguarded iterators.
234 * @param bi1 First iterator.
235 * @param bi2 Second iterator.
236 * @return @c True if less equal. */
237 template<typename RandomAccessIterator
, typename Comparator
>
239 operator<=(unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
240 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
)
243 return !(bi1
.comp
)(*bi2
, *bi1
);
246 /** Prepare a set of sequences to be merged without a (end) guard
250 * @param min_sequence
252 * @pre (seqs_end - seqs_begin > 0) */
253 template<typename RandomAccessIteratorIterator
, typename Comparator
>
254 typename
std::iterator_traits
<typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
>::difference_type
255 prepare_unguarded(RandomAccessIteratorIterator seqs_begin
,
256 RandomAccessIteratorIterator seqs_end
, Comparator comp
,
257 int& min_sequence
, bool stable
)
259 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
261 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
262 RandomAccessIterator1
;
263 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
265 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::difference_type
268 if ((*seqs_begin
).first
== (*seqs_begin
).second
)
270 // Empty sequence found, it's the first one.
275 // Last element in sequence.
276 value_type min
= *((*seqs_begin
).second
- 1);
278 for (RandomAccessIteratorIterator s
= seqs_begin
+ 1; s
!= seqs_end
; s
++)
280 if ((*s
).first
== (*s
).second
)
282 // Empty sequence found.
283 min_sequence
= static_cast<int>(s
- seqs_begin
);
287 // Last element in sequence.
288 const value_type
& v
= *((*s
).second
- 1);
289 if (comp(v
, min
)) //strictly smaller
292 min_sequence
= static_cast<int>(s
- seqs_begin
);
296 difference_type overhang_size
= 0;
299 for (s
= 0; s
<= min_sequence
; s
++)
301 RandomAccessIterator1 split
;
303 split
= std::upper_bound(seqs_begin
[s
].first
, seqs_begin
[s
].second
,
306 split
= std::lower_bound(seqs_begin
[s
].first
, seqs_begin
[s
].second
,
309 overhang_size
+= seqs_begin
[s
].second
- split
;
312 for (; s
< (seqs_end
- seqs_begin
); s
++)
314 RandomAccessIterator1 split
= std::lower_bound(seqs_begin
[s
].first
, seqs_begin
[s
].second
, min
, comp
);
315 overhang_size
+= seqs_begin
[s
].second
- split
;
318 // So many elements will be left over afterwards.
319 return overhang_size
;
322 /** Prepare a set of sequences to be merged with a (end) guard (sentinel)
326 template<typename RandomAccessIteratorIterator
, typename Comparator
>
327 typename
std::iterator_traits
<typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
>::difference_type
328 prepare_unguarded_sentinel(RandomAccessIteratorIterator seqs_begin
,
329 RandomAccessIteratorIterator seqs_end
,
332 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
334 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
335 RandomAccessIterator1
;
336 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
338 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::difference_type
341 // Last element in sequence.
343 bool max_found
= false;
344 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; s
++)
346 if ((*s
).first
== (*s
).second
)
349 // Last element in sequence.
350 value_type
& v
= *((*s
).second
- 1);
353 if (!max_found
|| comp(max
, v
))
358 difference_type overhang_size
= 0;
360 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; s
++)
362 RandomAccessIterator1 split
= std::lower_bound((*s
).first
, (*s
).second
, max
, comp
);
363 overhang_size
+= (*s
).second
- split
;
366 *((*s
).second
) = max
;
369 // So many elements will be left over afterwards.
370 return overhang_size
;
373 /** @brief Highly efficient 3-way merging procedure.
374 * @param seqs_begin Begin iterator of iterator pair input sequence.
375 * @param seqs_end End iterator of iterator pair input sequence.
376 * @param target Begin iterator out output sequence.
377 * @param comp Comparator.
378 * @param length Maximum length to merge.
379 * @param stable Unused, stable anyway.
380 * @return End iterator of output sequence. */
381 template<template<typename RAI
, typename C
> class iterator
, typename RandomAccessIteratorIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
382 RandomAccessIterator3
383 multiway_merge_3_variant(RandomAccessIteratorIterator seqs_begin
, RandomAccessIteratorIterator seqs_end
, RandomAccessIterator3 target
, Comparator comp
, _DifferenceTp length
, bool stable
)
385 _GLIBCXX_CALL(length
);
387 typedef _DifferenceTp difference_type
;
389 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
390 RandomAccessIterator1
;
391 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
397 iterator
<RandomAccessIterator1
, Comparator
>
398 seq0(seqs_begin
[0].first
, seqs_begin
[0].second
, comp
),
399 seq1(seqs_begin
[1].first
, seqs_begin
[1].second
, comp
),
400 seq2(seqs_begin
[2].first
, seqs_begin
[2].second
, comp
);
425 #define Merge3Case(a,b,c,c0,c1) \
427 *target = *seq ## a; \
431 if (length == 0) goto finish; \
432 if (seq ## a c0 seq ## b) goto s ## a ## b ## c; \
433 if (seq ## a c1 seq ## c) goto s ## b ## a ## c; \
434 goto s ## b ## c ## a;
436 Merge3Case(0, 1, 2, <=, <=);
437 Merge3Case(1, 2, 0, <=, < );
438 Merge3Case(2, 0, 1, < , < );
439 Merge3Case(1, 0, 2, < , <=);
440 Merge3Case(0, 2, 1, <=, <=);
441 Merge3Case(2, 1, 0, < , < );
448 seqs_begin
[0].first
= seq0
;
449 seqs_begin
[1].first
= seq1
;
450 seqs_begin
[2].first
= seq2
;
455 template<typename RandomAccessIteratorIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
456 RandomAccessIterator3
457 multiway_merge_3_combined(RandomAccessIteratorIterator seqs_begin
, RandomAccessIteratorIterator seqs_end
, RandomAccessIterator3 target
, Comparator comp
, _DifferenceTp length
, bool stable
)
459 _GLIBCXX_CALL(length
);
461 typedef _DifferenceTp difference_type
;
462 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
463 RandomAccessIterator1
;
464 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
468 RandomAccessIterator3 target_end
;
471 difference_type overhang
= prepare_unguarded(seqs_begin
, seqs_end
, comp
, min_seq
, true);
473 difference_type total_length
= 0;
474 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; ++s
)
475 total_length
+= LENGTH(*s
);
479 difference_type unguarded_length
= std::min(length
, total_length
- overhang
);
480 target_end
= multiway_merge_3_variant
<unguarded_iterator
>
481 (seqs_begin
, seqs_end
, target
, comp
, unguarded_length
, stable
);
482 overhang
= length
- unguarded_length
;
486 // Empty sequence found.
491 #if _GLIBCXX_ASSERTIONS
492 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
- overhang
);
493 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
499 // Iterators will be advanced accordingly.
500 target_end
= merge_advance(seqs_begin
[1].first
, seqs_begin
[1].second
,
501 seqs_begin
[2].first
, seqs_begin
[2].second
,
502 target_end
, overhang
, comp
);
505 target_end
= merge_advance(seqs_begin
[0].first
, seqs_begin
[0].second
,
506 seqs_begin
[2].first
, seqs_begin
[2].second
,
507 target_end
, overhang
, comp
);
510 target_end
= merge_advance(seqs_begin
[0].first
, seqs_begin
[0].second
,
511 seqs_begin
[1].first
, seqs_begin
[1].second
,
512 target_end
, overhang
, comp
);
515 _GLIBCXX_PARALLEL_ASSERT(false);
518 #if _GLIBCXX_ASSERTIONS
519 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
);
520 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
526 /** @brief Highly efficient 4-way merging procedure.
527 * @param seqs_begin Begin iterator of iterator pair input sequence.
528 * @param seqs_end End iterator of iterator pair input sequence.
529 * @param target Begin iterator out output sequence.
530 * @param comp Comparator.
531 * @param length Maximum length to merge.
532 * @param stable Unused, stable anyway.
533 * @return End iterator of output sequence. */
534 template<template<typename RAI
, typename C
> class iterator
, typename RandomAccessIteratorIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
535 RandomAccessIterator3
536 multiway_merge_4_variant(RandomAccessIteratorIterator seqs_begin
, RandomAccessIteratorIterator seqs_end
, RandomAccessIterator3 target
, Comparator comp
, _DifferenceTp length
, bool stable
)
538 _GLIBCXX_CALL(length
);
539 typedef _DifferenceTp difference_type
;
541 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
542 RandomAccessIterator1
;
543 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
546 iterator
<RandomAccessIterator1
, Comparator
>
547 seq0(seqs_begin
[0].first
, seqs_begin
[0].second
, comp
),
548 seq1(seqs_begin
[1].first
, seqs_begin
[1].second
, comp
),
549 seq2(seqs_begin
[2].first
, seqs_begin
[2].second
, comp
),
550 seq3(seqs_begin
[3].first
, seqs_begin
[3].second
, comp
);
552 #define Decision(a,b,c,d) { \
553 if (seq ## d < seq ## a) goto s ## d ## a ## b ## c; \
554 if (seq ## d < seq ## b) goto s ## a ## d ## b ## c; \
555 if (seq ## d < seq ## c) goto s ## a ## b ## d ## c; \
556 goto s ## a ## b ## c ## d; }
581 #define Merge4Case(a,b,c,d,c0,c1,c2) \
582 s ## a ## b ## c ## d: \
583 if (length == 0) goto finish; \
584 *target = *seq ## a; \
588 if (seq ## a c0 seq ## b) goto s ## a ## b ## c ## d; \
589 if (seq ## a c1 seq ## c) goto s ## b ## a ## c ## d; \
590 if (seq ## a c2 seq ## d) goto s ## b ## c ## a ## d; \
591 goto s ## b ## c ## d ## a;
593 Merge4Case(0, 1, 2, 3, <=, <=, <=);
594 Merge4Case(0, 1, 3, 2, <=, <=, <=);
595 Merge4Case(0, 2, 1, 3, <=, <=, <=);
596 Merge4Case(0, 2, 3, 1, <=, <=, <=);
597 Merge4Case(0, 3, 1, 2, <=, <=, <=);
598 Merge4Case(0, 3, 2, 1, <=, <=, <=);
599 Merge4Case(1, 0, 2, 3, < , <=, <=);
600 Merge4Case(1, 0, 3, 2, < , <=, <=);
601 Merge4Case(1, 2, 0, 3, <=, < , <=);
602 Merge4Case(1, 2, 3, 0, <=, <=, < );
603 Merge4Case(1, 3, 0, 2, <=, < , <=);
604 Merge4Case(1, 3, 2, 0, <=, <=, < );
605 Merge4Case(2, 0, 1, 3, < , < , <=);
606 Merge4Case(2, 0, 3, 1, < , <=, < );
607 Merge4Case(2, 1, 0, 3, < , < , <=);
608 Merge4Case(2, 1, 3, 0, < , <=, < );
609 Merge4Case(2, 3, 0, 1, <=, < , < );
610 Merge4Case(2, 3, 1, 0, <=, < , < );
611 Merge4Case(3, 0, 1, 2, < , < , < );
612 Merge4Case(3, 0, 2, 1, < , < , < );
613 Merge4Case(3, 1, 0, 2, < , < , < );
614 Merge4Case(3, 1, 2, 0, < , < , < );
615 Merge4Case(3, 2, 0, 1, < , < , < );
616 Merge4Case(3, 2, 1, 0, < , < , < );
624 seqs_begin
[0].first
= seq0
;
625 seqs_begin
[1].first
= seq1
;
626 seqs_begin
[2].first
= seq2
;
627 seqs_begin
[3].first
= seq3
;
632 template<typename RandomAccessIteratorIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
633 RandomAccessIterator3
634 multiway_merge_4_combined(RandomAccessIteratorIterator seqs_begin
, RandomAccessIteratorIterator seqs_end
, RandomAccessIterator3 target
, Comparator comp
, _DifferenceTp length
, bool stable
)
636 _GLIBCXX_CALL(length
);
637 typedef _DifferenceTp difference_type
;
639 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
640 RandomAccessIterator1
;
641 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
645 RandomAccessIterator3 target_end
;
648 difference_type overhang
= prepare_unguarded(seqs_begin
, seqs_end
, comp
, min_seq
, true);
650 difference_type total_length
= 0;
651 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; ++s
)
652 total_length
+= LENGTH(*s
);
656 difference_type unguarded_length
= std::min(length
, total_length
- overhang
);
657 target_end
= multiway_merge_4_variant
<unguarded_iterator
>
658 (seqs_begin
, seqs_end
, target
, comp
, unguarded_length
, stable
);
659 overhang
= length
- unguarded_length
;
663 // Empty sequence found.
668 #if _GLIBCXX_ASSERTIONS
669 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
- overhang
);
670 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
673 std::vector
<std::pair
<RandomAccessIterator1
, RandomAccessIterator1
> > one_missing(seqs_begin
, seqs_end
);
674 one_missing
.erase(one_missing
.begin() + min_seq
); //remove
676 target_end
= multiway_merge_3_variant
<guarded_iterator
>(one_missing
.begin(), one_missing
.end(), target_end
, comp
, overhang
, stable
);
678 // Insert back again.
679 one_missing
.insert(one_missing
.begin() + min_seq
, seqs_begin
[min_seq
]);
680 // Write back modified iterators.
681 copy(one_missing
.begin(), one_missing
.end(), seqs_begin
);
683 #if _GLIBCXX_ASSERTIONS
684 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
);
685 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
691 /** @brief Basic multi-way merging procedure.
693 * The head elements are kept in a sorted array, new heads are
695 * @param seqs_begin Begin iterator of iterator pair input sequence.
696 * @param seqs_end End iterator of iterator pair input sequence.
697 * @param target Begin iterator out output sequence.
698 * @param comp Comparator.
699 * @param length Maximum length to merge.
700 * @param stable Stable merging incurs a performance penalty.
701 * @return End iterator of output sequence.
703 template<typename RandomAccessIteratorIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
704 RandomAccessIterator3
705 multiway_merge_bubble(RandomAccessIteratorIterator seqs_begin
, RandomAccessIteratorIterator seqs_end
, RandomAccessIterator3 target
, Comparator comp
, _DifferenceTp length
, bool stable
)
707 _GLIBCXX_CALL(length
)
709 typedef _DifferenceTp difference_type
;
710 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
711 RandomAccessIterator1
;
712 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
715 // Num remaining pieces.
716 int k
= static_cast<int>(seqs_end
- seqs_begin
), nrp
;
718 value_type
* pl
= new value_type
[k
];
719 int* source
= new int[k
];
720 difference_type total_length
= 0;
722 #define POS(i) seqs_begin[(i)].first
723 #define STOPS(i) seqs_begin[(i)].second
725 // Write entries into queue.
727 for (int pi
= 0; pi
< k
; pi
++)
729 if (STOPS(pi
) != POS(pi
))
731 pl
[nrp
] = *(POS(pi
));
734 total_length
+= LENGTH(seqs_begin
[pi
]);
740 for (int k
= 0; k
< nrp
- 1; k
++)
741 for (int pi
= nrp
- 1; pi
> k
; pi
--)
742 if (comp(pl
[pi
], pl
[pi
- 1]) ||
743 (!comp(pl
[pi
- 1], pl
[pi
]) && source
[pi
] < source
[pi
- 1]))
745 std::swap(pl
[pi
- 1], pl
[pi
]);
746 std::swap(source
[pi
- 1], source
[pi
]);
751 for (int k
= 0; k
< nrp
- 1; k
++)
752 for (int pi
= nrp
- 1; pi
> k
; pi
--)
753 if (comp(pl
[pi
], pl
[pi
-1]))
755 std::swap(pl
[pi
-1], pl
[pi
]);
756 std::swap(source
[pi
-1], source
[pi
]);
764 while (nrp
> 0 && length
> 0)
766 if (source
[0] < source
[1])
769 while ((nrp
== 1 || !(comp(pl
[1], pl
[0]))) && length
> 0)
775 if (POS(source
[0]) == STOPS(source
[0]))
777 // Move everything to the left.
778 for (int s
= 0; s
< nrp
- 1; s
++)
781 source
[s
] = source
[s
+ 1];
787 pl
[0] = *(POS(source
[0]));
793 while ((nrp
== 1 || comp(pl
[0], pl
[1])) && length
> 0)
799 if (POS(source
[0]) == STOPS(source
[0]))
801 for (int s
= 0; s
< nrp
- 1; s
++)
804 source
[s
] = source
[s
+ 1];
810 pl
[0] = *(POS(source
[0]));
816 while ((j
< nrp
) && (comp(pl
[j
], pl
[j
- 1]) ||
817 (!comp(pl
[j
- 1], pl
[j
]) && (source
[j
] < source
[j
- 1]))))
819 std::swap(pl
[j
- 1], pl
[j
]);
820 std::swap(source
[j
- 1], source
[j
]);
828 while (nrp
> 0 && length
> 0)
831 while (nrp
== 1 || (!comp(pl
[1], pl
[0])) && length
> 0)
837 if (POS(source
[0]) == STOPS(source
[0]))
839 for (int s
= 0; s
< (nrp
- 1); s
++)
842 source
[s
] = source
[s
+ 1];
848 pl
[0] = *(POS(source
[0]));
853 while ((j
< nrp
) && comp(pl
[j
], pl
[j
- 1]))
855 std::swap(pl
[j
- 1], pl
[j
]);
856 std::swap(source
[j
- 1], source
[j
]);
868 /** @brief Multi-way merging procedure for a high branching factor,
871 * The head elements are kept in a loser tree.
872 * @param seqs_begin Begin iterator of iterator pair input sequence.
873 * @param seqs_end End iterator of iterator pair input sequence.
874 * @param target Begin iterator out output sequence.
875 * @param comp Comparator.
876 * @param length Maximum length to merge.
877 * @param stable Stable merging incurs a performance penalty.
878 * @return End iterator of output sequence.
880 template<typename LT
, typename RandomAccessIteratorIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
881 RandomAccessIterator3
882 multiway_merge_loser_tree(RandomAccessIteratorIterator seqs_begin
, RandomAccessIteratorIterator seqs_end
, RandomAccessIterator3 target
, Comparator comp
, _DifferenceTp length
, bool stable
)
884 _GLIBCXX_CALL(length
)
886 typedef _DifferenceTp difference_type
;
887 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
888 RandomAccessIterator1
;
889 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
892 int k
= static_cast<int>(seqs_end
- seqs_begin
);
896 difference_type total_length
= 0;
898 for (int t
= 0; t
< k
; t
++)
902 if (seqs_begin
[t
].first
== seqs_begin
[t
].second
)
903 lt
.insert_start_stable(value_type(), t
, true);
905 lt
.insert_start_stable(*seqs_begin
[t
].first
, t
, false);
909 if (seqs_begin
[t
].first
== seqs_begin
[t
].second
)
910 lt
.insert_start(value_type(), t
, true);
912 lt
.insert_start(*seqs_begin
[t
].first
, t
, false);
915 total_length
+= LENGTH(seqs_begin
[t
]);
923 total_length
= std::min(total_length
, length
);
929 for (difference_type i
= 0; i
< total_length
; i
++)
932 source
= lt
.get_min_source();
934 *(target
++) = *(seqs_begin
[source
].first
++);
937 if (seqs_begin
[source
].first
== seqs_begin
[source
].second
)
938 lt
.delete_min_insert_stable(value_type(), true);
940 // Replace from same source.
941 lt
.delete_min_insert_stable(*seqs_begin
[source
].first
, false);
947 for (difference_type i
= 0; i
< total_length
; i
++)
950 source
= lt
.get_min_source();
952 *(target
++) = *(seqs_begin
[source
].first
++);
955 if (seqs_begin
[source
].first
== seqs_begin
[source
].second
)
956 lt
.delete_min_insert(value_type(), true);
958 // Replace from same source.
959 lt
.delete_min_insert(*seqs_begin
[source
].first
, false);
966 /** @brief Multi-way merging procedure for a high branching factor,
969 * The head elements are kept in a loser tree.
970 * @param seqs_begin Begin iterator of iterator pair input sequence.
971 * @param seqs_end End iterator of iterator pair input sequence.
972 * @param target Begin iterator out output sequence.
973 * @param comp Comparator.
974 * @param length Maximum length to merge.
975 * @param stable Stable merging incurs a performance penalty.
976 * @return End iterator of output sequence.
977 * @pre No input will run out of elements during the merge.
979 template<typename LT
, typename RandomAccessIteratorIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
980 RandomAccessIterator3
981 multiway_merge_loser_tree_unguarded(RandomAccessIteratorIterator seqs_begin
, RandomAccessIteratorIterator seqs_end
, RandomAccessIterator3 target
, Comparator comp
, _DifferenceTp length
, bool stable
)
983 _GLIBCXX_CALL(length
)
984 typedef _DifferenceTp difference_type
;
986 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
987 RandomAccessIterator1
;
988 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
991 int k
= seqs_end
- seqs_begin
;
995 difference_type total_length
= 0;
997 for (int t
= 0; t
< k
; t
++)
999 #if _GLIBCXX_ASSERTIONS
1000 _GLIBCXX_PARALLEL_ASSERT(seqs_begin
[t
].first
!= seqs_begin
[t
].second
);
1003 lt
.insert_start_stable(*seqs_begin
[t
].first
, t
, false);
1005 lt
.insert_start(*seqs_begin
[t
].first
, t
, false);
1007 total_length
+= LENGTH(seqs_begin
[t
]);
1015 // Do not go past end.
1016 length
= std::min(total_length
, length
);
1020 #if _GLIBCXX_ASSERTIONS
1021 difference_type i
= 0;
1026 RandomAccessIterator3 target_end
= target
+ length
;
1027 while (target
< target_end
)
1030 source
= lt
.get_min_source();
1032 #if _GLIBCXX_ASSERTIONS
1033 _GLIBCXX_PARALLEL_ASSERT(i
== 0 || !comp(*(seqs_begin
[source
].first
), *(target
- 1)));
1036 *(target
++) = *(seqs_begin
[source
].first
++);
1038 #if _GLIBCXX_ASSERTIONS
1039 _GLIBCXX_PARALLEL_ASSERT((seqs_begin
[source
].first
!= seqs_begin
[source
].second
) || (i
== length
- 1));
1043 // Replace from same source.
1044 lt
.delete_min_insert_stable(*seqs_begin
[source
].first
, false);
1050 RandomAccessIterator3 target_end
= target
+ length
;
1051 while (target
< target_end
)
1054 source
= lt
.get_min_source();
1056 #if _GLIBCXX_ASSERTIONS
1057 if (i
> 0 && comp(*(seqs_begin
[source
].first
), *(target
- 1)))
1058 printf(" %i %i %i\n", length
, i
, source
);
1059 _GLIBCXX_PARALLEL_ASSERT(i
== 0 || !comp(*(seqs_begin
[source
].first
), *(target
- 1)));
1062 *(target
++) = *(seqs_begin
[source
].first
++);
1064 #if _GLIBCXX_ASSERTIONS
1065 if (!((seqs_begin
[source
].first
!= seqs_begin
[source
].second
) || (i
>= length
- 1)))
1066 printf(" %i %i %i\n", length
, i
, source
);
1067 _GLIBCXX_PARALLEL_ASSERT((seqs_begin
[source
].first
!= seqs_begin
[source
].second
) || (i
>= length
- 1));
1071 // Replace from same source.
1072 lt
.delete_min_insert(*seqs_begin
[source
].first
, false);
1079 template<typename _ValueTp
, class Comparator
>
1080 struct loser_tree_traits
1082 typedef LoserTree
/*Pointer*/<_ValueTp
, Comparator
> LT
;
1086 /*#define NO_POINTER(T) \
1087 template<typename Comparator> \
1088 struct loser_tree_traits<T, Comparator> \
1090 typedef LoserTreePointer<T, Comparator> LT; \
1093 // NO_POINTER(unsigned char)
1095 // NO_POINTER(unsigned short)
1096 // NO_POINTER(short)
1097 // NO_POINTER(unsigned int)
1099 // NO_POINTER(unsigned long)
1101 // NO_POINTER(unsigned long long)
1102 // NO_POINTER(long long)
1104 // #undef NO_POINTER
1106 template<typename _ValueTp
, class Comparator
>
1107 struct loser_tree_traits_unguarded
1109 typedef LoserTreeUnguarded
<_ValueTp
, Comparator
> LT
;
1112 /*#define NO_POINTER_UNGUARDED(T) \
1113 template<typename Comparator> \
1114 struct loser_tree_traits_unguarded<T, Comparator> \
1116 typedef LoserTreePointerUnguarded<T, Comparator> LT; \
1119 // NO_POINTER_UNGUARDED(unsigned char)
1120 // NO_POINTER_UNGUARDED(char)
1121 // NO_POINTER_UNGUARDED(unsigned short)
1122 // NO_POINTER_UNGUARDED(short)
1123 // NO_POINTER_UNGUARDED(unsigned int)
1124 // NO_POINTER_UNGUARDED(int)
1125 // NO_POINTER_UNGUARDED(unsigned long)
1126 // NO_POINTER_UNGUARDED(long)
1127 // NO_POINTER_UNGUARDED(unsigned long long)
1128 // NO_POINTER_UNGUARDED(long long)
1130 // #undef NO_POINTER_UNGUARDED
1132 template<typename RandomAccessIteratorIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
1133 RandomAccessIterator3
1134 multiway_merge_loser_tree_combined(RandomAccessIteratorIterator seqs_begin
, RandomAccessIteratorIterator seqs_end
, RandomAccessIterator3 target
, Comparator comp
, _DifferenceTp length
, bool stable
)
1136 _GLIBCXX_CALL(length
)
1138 typedef _DifferenceTp difference_type
;
1140 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
1141 RandomAccessIterator1
;
1142 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
1146 RandomAccessIterator3 target_end
;
1147 difference_type overhang
= prepare_unguarded(seqs_begin
, seqs_end
,
1148 comp
, min_seq
, stable
);
1150 difference_type total_length
= 0;
1151 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; s
++)
1152 total_length
+= LENGTH(*s
);
1156 difference_type unguarded_length
= std::min(length
, total_length
- overhang
);
1157 target_end
= multiway_merge_loser_tree_unguarded
1158 <typename loser_tree_traits_unguarded
<value_type
, Comparator
>::LT
>
1159 (seqs_begin
, seqs_end
, target
, comp
, unguarded_length
, stable
);
1160 overhang
= length
- unguarded_length
;
1164 // Empty sequence found.
1166 target_end
= target
;
1169 #if _GLIBCXX_ASSERTIONS
1170 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
- overhang
);
1171 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
1174 target_end
= multiway_merge_loser_tree
1175 <typename loser_tree_traits
<value_type
, Comparator
>::LT
>
1176 (seqs_begin
, seqs_end
, target_end
, comp
, overhang
, stable
);
1178 #if _GLIBCXX_ASSERTIONS
1179 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
);
1180 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
1186 template<typename RandomAccessIteratorIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
1187 RandomAccessIterator3
1188 multiway_merge_loser_tree_sentinel(RandomAccessIteratorIterator seqs_begin
, RandomAccessIteratorIterator seqs_end
, RandomAccessIterator3 target
, Comparator comp
, _DifferenceTp length
, bool stable
)
1190 _GLIBCXX_CALL(length
)
1192 typedef _DifferenceTp difference_type
;
1193 typedef std::iterator_traits
<RandomAccessIteratorIterator
> traits_type
;
1194 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
1195 RandomAccessIterator1
;
1196 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
1198 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
1199 RandomAccessIterator1
;
1201 RandomAccessIterator3 target_end
;
1202 difference_type overhang
= prepare_unguarded_sentinel(seqs_begin
, seqs_end
, comp
);
1204 difference_type total_length
= 0;
1205 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; s
++)
1207 total_length
+= LENGTH(*s
);
1213 difference_type unguarded_length
= std::min(length
, total_length
- overhang
);
1214 target_end
= multiway_merge_loser_tree_unguarded
1215 <typename loser_tree_traits_unguarded
<value_type
, Comparator
>::LT
>
1216 (seqs_begin
, seqs_end
, target
, comp
, unguarded_length
, stable
);
1217 overhang
= length
- unguarded_length
;
1219 #if _GLIBCXX_ASSERTIONS
1220 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
- overhang
);
1221 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
1224 // Copy rest stable.
1225 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
&& overhang
> 0; s
++)
1229 difference_type local_length
= std::min((difference_type
)overhang
, (difference_type
)LENGTH(*s
));
1230 target_end
= std::copy((*s
).first
, (*s
).first
+ local_length
, target_end
);
1231 (*s
).first
+= local_length
;
1232 overhang
-= local_length
;
1235 #if _GLIBCXX_ASSERTIONS
1236 _GLIBCXX_PARALLEL_ASSERT(overhang
== 0);
1237 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
);
1238 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
1244 /** @brief Sequential multi-way merging switch.
1246 * The decision if based on the branching factor and runtime settings.
1247 * @param seqs_begin Begin iterator of iterator pair input sequence.
1248 * @param seqs_end End iterator of iterator pair input sequence.
1249 * @param target Begin iterator out output sequence.
1250 * @param comp Comparator.
1251 * @param length Maximum length to merge.
1252 * @param stable Stable merging incurs a performance penalty.
1253 * @param sentinel The sequences have a sentinel element.
1254 * @return End iterator of output sequence. */
1255 template<typename RandomAccessIteratorIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
1256 RandomAccessIterator3
1257 multiway_merge(RandomAccessIteratorIterator seqs_begin
, RandomAccessIteratorIterator seqs_end
, RandomAccessIterator3 target
, Comparator comp
, _DifferenceTp length
, bool stable
, bool sentinel
, sequential_tag
)
1259 _GLIBCXX_CALL(length
)
1261 typedef _DifferenceTp difference_type
;
1262 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
1263 RandomAccessIterator1
;
1264 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
1267 #if _GLIBCXX_ASSERTIONS
1268 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; s
++)
1269 _GLIBCXX_PARALLEL_ASSERT(is_sorted((*s
).first
, (*s
).second
, comp
));
1272 RandomAccessIterator3 return_target
= target
;
1273 int k
= static_cast<int>(seqs_end
- seqs_begin
);
1275 Settings::MultiwayMergeAlgorithm mwma
= Settings::multiway_merge_algorithm
;
1277 if (!sentinel
&& mwma
== Settings::LOSER_TREE_SENTINEL
)
1278 mwma
= Settings::LOSER_TREE_COMBINED
;
1285 return_target
= std::copy(seqs_begin
[0].first
, seqs_begin
[0].first
+ length
, target
);
1286 seqs_begin
[0].first
+= length
;
1289 return_target
= merge_advance(seqs_begin
[0].first
, seqs_begin
[0].second
, seqs_begin
[1].first
, seqs_begin
[1].second
, target
, length
, comp
);
1294 case Settings::LOSER_TREE_COMBINED
:
1295 return_target
= multiway_merge_3_combined(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1297 case Settings::LOSER_TREE_SENTINEL
:
1298 return_target
= multiway_merge_3_variant
<unguarded_iterator
>(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1301 return_target
= multiway_merge_3_variant
<guarded_iterator
>(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1308 case Settings::LOSER_TREE_COMBINED
:
1309 return_target
= multiway_merge_4_combined(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1311 case Settings::LOSER_TREE_SENTINEL
:
1312 return_target
= multiway_merge_4_variant
<unguarded_iterator
>(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1315 return_target
= multiway_merge_4_variant
<guarded_iterator
>(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1323 case Settings::BUBBLE
:
1324 return_target
= multiway_merge_bubble(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1326 #if _GLIBCXX_LOSER_TREE_EXPLICIT
1327 case Settings::LOSER_TREE_EXPLICIT
:
1328 return_target
= multiway_merge_loser_tree
<LoserTreeExplicit
<value_type
, Comparator
> >(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1331 #if _GLIBCXX_LOSER_TREE
1332 case Settings::LOSER_TREE
:
1333 return_target
= multiway_merge_loser_tree
<LoserTree
<value_type
, Comparator
> >(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1336 #if _GLIBCXX_LOSER_TREE_COMBINED
1337 case Settings::LOSER_TREE_COMBINED
:
1338 return_target
= multiway_merge_loser_tree_combined(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1341 #if _GLIBCXX_LOSER_TREE_SENTINEL
1342 case Settings::LOSER_TREE_SENTINEL
:
1343 return_target
= multiway_merge_loser_tree_sentinel(seqs_begin
, seqs_end
, target
, comp
, length
, stable
);
1347 // multiway_merge algorithm not implemented.
1348 _GLIBCXX_PARALLEL_ASSERT(0);
1353 #if _GLIBCXX_ASSERTIONS
1354 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target
+ length
, comp
));
1357 return return_target
;
1360 /** @brief Parallel multi-way merge routine.
1362 * The decision if based on the branching factor and runtime settings.
1363 * @param seqs_begin Begin iterator of iterator pair input sequence.
1364 * @param seqs_end End iterator of iterator pair input sequence.
1365 * @param target Begin iterator out output sequence.
1366 * @param comp Comparator.
1367 * @param length Maximum length to merge.
1368 * @param stable Stable merging incurs a performance penalty.
1369 * @param sentinel Ignored.
1370 * @return End iterator of output sequence.
1372 template<typename RandomAccessIteratorIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
1373 RandomAccessIterator3
1374 parallel_multiway_merge(RandomAccessIteratorIterator seqs_begin
, RandomAccessIteratorIterator seqs_end
, RandomAccessIterator3 target
, Comparator comp
, _DifferenceTp length
, bool stable
, bool sentinel
)
1376 _GLIBCXX_CALL(length
)
1378 typedef _DifferenceTp difference_type
;
1379 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>::value_type::first_type
1380 RandomAccessIterator1
;
1381 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
1384 #if _GLIBCXX_ASSERTIONS
1385 for (RandomAccessIteratorIterator rii
= seqs_begin
; rii
!= seqs_end
; rii
++)
1386 _GLIBCXX_PARALLEL_ASSERT(is_sorted((*rii
).first
, (*rii
).second
, comp
));
1390 int k
= static_cast<int>(seqs_end
- seqs_begin
);
1392 difference_type total_length
= 0;
1393 for (RandomAccessIteratorIterator raii
= seqs_begin
; raii
!= seqs_end
; raii
++)
1394 total_length
+= LENGTH(*raii
);
1396 _GLIBCXX_CALL(total_length
)
1398 if (total_length
== 0 || k
== 0)
1401 thread_index_t num_threads
= static_cast<thread_index_t
>(std::min(static_cast<difference_type
>(get_max_threads()), total_length
));
1403 Timing
<sequential_tag
>* t
= new Timing
<sequential_tag
>[num_threads
];
1405 for (int pr
= 0; pr
< num_threads
; pr
++)
1408 bool tight
= (total_length
== length
);
1410 // Thread t will have to merge pieces[iam][0..k - 1]
1411 std::vector
<std::pair
<difference_type
, difference_type
> >* pieces
= new std::vector
<std::pair
<difference_type
, difference_type
> >[num_threads
];
1412 for (int s
= 0; s
< num_threads
; s
++)
1413 pieces
[s
].resize(k
);
1415 difference_type num_samples
= Settings::merge_oversampling
* num_threads
;
1417 if (Settings::multiway_merge_splitting
== Settings::SAMPLING
)
1419 value_type
* samples
= new value_type
[k
* num_samples
];
1421 for (int s
= 0; s
< k
; s
++)
1422 for (int i
= 0; (difference_type
)i
< num_samples
; i
++)
1424 difference_type sample_index
= static_cast<difference_type
>(LENGTH(seqs_begin
[s
]) * (double(i
+ 1) / (num_samples
+ 1)) * (double(length
) / total_length
));
1425 samples
[s
* num_samples
+ i
] = seqs_begin
[s
].first
[sample_index
];
1429 __gnu_sequential::stable_sort(samples
, samples
+ (num_samples
* k
), comp
);
1431 __gnu_sequential::sort(samples
, samples
+ (num_samples
* k
), comp
);
1433 for (int slab
= 0; slab
< num_threads
; slab
++)
1434 // For each slab / processor.
1435 for (int seq
= 0; seq
< k
; seq
++)
1437 // For each sequence.
1439 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
;
1442 // Absolute beginning.
1443 pieces
[slab
][seq
].first
= 0;
1445 if ((slab
+ 1) < num_threads
)
1446 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
;
1448 pieces
[slab
][seq
].second
= LENGTH(seqs_begin
[seq
]); //absolute ending
1454 // (Settings::multiway_merge_splitting == Settings::EXACT).
1455 std::vector
<RandomAccessIterator1
>* offsets
= new std::vector
<RandomAccessIterator1
>[num_threads
];
1456 std::vector
<std::pair
<RandomAccessIterator1
, RandomAccessIterator1
> > se(k
);
1458 copy(seqs_begin
, seqs_end
, se
.begin());
1460 difference_type borders
[num_threads
+ 1];
1461 equally_split(length
, num_threads
, borders
);
1463 for (int s
= 0; s
< (num_threads
- 1); s
++)
1465 offsets
[s
].resize(k
);
1466 multiseq_partition(se
.begin(), se
.end(), borders
[s
+ 1],
1467 offsets
[s
].begin(), comp
);
1469 // Last one also needed and available.
1472 offsets
[num_threads
- 1].resize(k
);
1473 multiseq_partition(se
.begin(), se
.end(), (difference_type
)length
,
1474 offsets
[num_threads
- 1].begin(), comp
);
1479 for (int slab
= 0; slab
< num_threads
; slab
++)
1481 // For each slab / processor.
1482 for (int seq
= 0; seq
< k
; seq
++)
1484 // For each sequence.
1487 // Absolute beginning.
1488 pieces
[slab
][seq
].first
= 0;
1491 pieces
[slab
][seq
].first
= pieces
[slab
- 1][seq
].second
;
1492 if (!tight
|| slab
< (num_threads
- 1))
1493 pieces
[slab
][seq
].second
= offsets
[slab
][seq
] - seqs_begin
[seq
].first
;
1496 // slab == num_threads - 1
1497 pieces
[slab
][seq
].second
= LENGTH(seqs_begin
[seq
]);
1504 for (int pr
= 0; pr
< num_threads
; pr
++)
1507 # pragma omp parallel num_threads(num_threads)
1509 thread_index_t iam
= omp_get_thread_num();
1513 difference_type target_position
= 0;
1515 for (int c
= 0; c
< k
; c
++)
1516 target_position
+= pieces
[iam
][c
].first
;
1520 std::pair
<RandomAccessIterator1
, RandomAccessIterator1
>* chunks
= new std::pair
<RandomAccessIterator1
, RandomAccessIterator1
>[k
];
1522 difference_type local_length
= 0;
1523 for (int s
= 0; s
< k
; s
++)
1525 chunks
[s
] = std::make_pair(seqs_begin
[s
].first
+ pieces
[iam
][s
].first
, seqs_begin
[s
].first
+ pieces
[iam
][s
].second
);
1526 local_length
+= LENGTH(chunks
[s
]);
1529 multiway_merge(chunks
, chunks
+ k
, target
+ target_position
, comp
,
1530 std::min(local_length
, length
- target_position
),
1531 stable
, false, sequential_tag());
1537 RandomAccessIterator1 begin0
= seqs_begin
[0].first
+ pieces
[iam
][0].first
, begin1
= seqs_begin
[1].first
+ pieces
[iam
][1].first
;
1538 merge_advance(begin0
,
1539 seqs_begin
[0].first
+ pieces
[iam
][0].second
,
1541 seqs_begin
[1].first
+ pieces
[iam
][1].second
,
1542 target
+ target_position
,
1543 (pieces
[iam
][0].second
- pieces
[iam
][0].first
) + (pieces
[iam
][1].second
- pieces
[iam
][1].first
),
1551 for (int pr
= 0; pr
< num_threads
; pr
++)
1554 #if _GLIBCXX_ASSERTIONS
1555 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target
+ length
, comp
));
1558 // Update ends of sequences.
1559 for (int s
= 0; s
< k
; s
++)
1560 seqs_begin
[s
].first
+= pieces
[num_threads
- 1][s
].second
;
1564 for (int pr
= 0; pr
< num_threads
; pr
++)
1566 for (int pr
= 0; pr
< num_threads
; pr
++)
1570 return target
+ length
;
1574 * @brief Multi-way merging front-end.
1575 * @param seqs_begin Begin iterator of iterator pair input sequence.
1576 * @param seqs_end End iterator of iterator pair input sequence.
1577 * @param target Begin iterator out output sequence.
1578 * @param comp Comparator.
1579 * @param length Maximum length to merge.
1580 * @param stable Stable merging incurs a performance penalty.
1581 * @return End iterator of output sequence.
1583 template<typename RandomAccessIteratorPairIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
1584 RandomAccessIterator3
1585 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
,
1586 RandomAccessIteratorPairIterator seqs_end
,
1587 RandomAccessIterator3 target
, Comparator comp
,
1588 _DifferenceTp length
, bool stable
)
1590 typedef _DifferenceTp difference_type
;
1591 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1593 if (seqs_begin
== seqs_end
)
1596 RandomAccessIterator3 target_end
;
1597 if (_GLIBCXX_PARALLEL_CONDITION(((seqs_end
- seqs_begin
) >= Settings::multiway_merge_minimal_k
) && ((sequence_index_t
)length
>= Settings::multiway_merge_minimal_n
)))
1598 target_end
= parallel_multiway_merge(seqs_begin
, seqs_end
, target
, comp
, (difference_type
)length
, stable
, false);
1600 target_end
= multiway_merge(seqs_begin
, seqs_end
, target
, comp
, length
, stable
, false, sequential_tag());
1605 /** @brief Multi-way merging front-end.
1606 * @param seqs_begin Begin iterator of iterator pair input sequence.
1607 * @param seqs_end End iterator of iterator pair input sequence.
1608 * @param target Begin iterator out output sequence.
1609 * @param comp Comparator.
1610 * @param length Maximum length to merge.
1611 * @param stable Stable merging incurs a performance penalty.
1612 * @return End iterator of output sequence.
1613 * @pre For each @c i, @c seqs_begin[i].second must be the end
1614 * marker of the sequence, but also reference the one more sentinel
1616 template<typename RandomAccessIteratorPairIterator
, typename RandomAccessIterator3
, typename _DifferenceTp
, typename Comparator
>
1617 RandomAccessIterator3
1618 multiway_merge_sentinel(RandomAccessIteratorPairIterator seqs_begin
,
1619 RandomAccessIteratorPairIterator seqs_end
,
1620 RandomAccessIterator3 target
,
1622 _DifferenceTp length
,
1625 typedef _DifferenceTp difference_type
;
1627 if (seqs_begin
== seqs_end
)
1630 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1632 if (_GLIBCXX_PARALLEL_CONDITION(((seqs_end
- seqs_begin
) >= Settings::multiway_merge_minimal_k
) && ((sequence_index_t
)length
>= Settings::multiway_merge_minimal_n
)))
1633 return parallel_multiway_merge(seqs_begin
, seqs_end
, target
, comp
, (typename
std::iterator_traits
<RandomAccessIterator3
>::difference_type
)length
, stable
, true);
1635 return multiway_merge(seqs_begin
, seqs_end
, target
, comp
, length
, stable
, true, sequential_tag());