source: Daodan/MSYS2/mingw32/include/c++/11.2.0/parallel/multiway_merge.h@ 1170

Last change on this file since 1170 was 1166, checked in by rossy, 3 years ago

Daodan: Replace MinGW build env with an up-to-date MSYS2 env
File size: 69.0 KB
RevLine 
[1166]1// -*- C++ -*-
2
3// Copyright (C) 2007-2021 Free Software Foundation, Inc.
4//
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 3, or (at your option) any later
9// version.
10
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.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/** @file parallel/multiway_merge.h
26* @brief Implementation of sequential and parallel multiway merge.
27*
28* Explanations on the high-speed merging routines in the appendix of
29*
30* P. Sanders.
31* Fast priority queues for cached memory.
32* ACM Journal of Experimental Algorithmics, 5, 2000.
33*
34* This file is a GNU parallel extension to the Standard C++ Library.
35*/
36
37// Written by Johannes Singler and Manuel Holtgrewe.
38
39#ifndef _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H
40#define _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H
41
42#include <vector>
43
44#include <bits/stl_algo.h>
45#include <parallel/features.h>
46#include <parallel/parallel.h>
47#include <parallel/losertree.h>
48#include <parallel/multiseq_selection.h>
49#if _GLIBCXX_PARALLEL_ASSERTIONS
50#include <parallel/checkers.h>
51#endif
52
53/** @brief Length of a sequence described by a pair of iterators. */
54#define _GLIBCXX_PARALLEL_LENGTH(__s) ((__s).second - (__s).first)
55
56namespace __gnu_parallel
57{
58 template<typename _RAIter1, typename _RAIter2, typename _OutputIterator,
59 typename _DifferenceTp, typename _Compare>
60 _OutputIterator
61 __merge_advance(_RAIter1&, _RAIter1, _RAIter2&, _RAIter2,
62 _OutputIterator, _DifferenceTp, _Compare);
63
64 /** @brief _Iterator wrapper supporting an implicit supremum at the end
65 * of the sequence, dominating all comparisons.
66 *
67 * The implicit supremum comes with a performance cost.
68 *
69 * Deriving from _RAIter is not possible since
70 * _RAIter need not be a class.
71 */
72 template<typename _RAIter, typename _Compare>
73 class _GuardedIterator
74 {
75 private:
76 /** @brief Current iterator __position. */
77 _RAIter _M_current;
78
79 /** @brief End iterator of the sequence. */
80 _RAIter _M_end;
81
82 /** @brief _Compare. */
83 _Compare& __comp;
84
85 public:
86 /** @brief Constructor. Sets iterator to beginning of sequence.
87 * @param __begin Begin iterator of sequence.
88 * @param __end End iterator of sequence.
89 * @param __comp Comparator provided for associated overloaded
90 * compare operators. */
91 _GuardedIterator(_RAIter __begin, _RAIter __end, _Compare& __comp)
92 : _M_current(__begin), _M_end(__end), __comp(__comp)
93 { }
94
95 /** @brief Pre-increment operator.
96 * @return This. */
97 _GuardedIterator<_RAIter, _Compare>&
98 operator++()
99 {
100 ++_M_current;
101 return *this;
102 }
103
104 /** @brief Dereference operator.
105 * @return Referenced element. */
106 typename std::iterator_traits<_RAIter>::value_type&
107 operator*() const
108 { return *_M_current; }
109
110 /** @brief Convert to wrapped iterator.
111 * @return Wrapped iterator. */
112 operator _RAIter() const
113 { return _M_current; }
114
115 /** @brief Compare two elements referenced by guarded iterators.
116 * @param __bi1 First iterator.
117 * @param __bi2 Second iterator.
118 * @return @c true if less. */
119 friend bool
120 operator<(const _GuardedIterator<_RAIter, _Compare>& __bi1,
121 const _GuardedIterator<_RAIter, _Compare>& __bi2)
122 {
123 if (__bi1._M_current == __bi1._M_end) // __bi1 is sup
124 return __bi2._M_current == __bi2._M_end; // __bi2 is not sup
125 if (__bi2._M_current == __bi2._M_end) // __bi2 is sup
126 return true;
127 return (__bi1.__comp)(*__bi1, *__bi2); // normal compare
128 }
129
130 /** @brief Compare two elements referenced by guarded iterators.
131 * @param __bi1 First iterator.
132 * @param __bi2 Second iterator.
133 * @return @c True if less equal. */
134 friend bool
135 operator<=(const _GuardedIterator<_RAIter, _Compare>& __bi1,
136 const _GuardedIterator<_RAIter, _Compare>& __bi2)
137 {
138 if (__bi2._M_current == __bi2._M_end) // __bi1 is sup
139 return __bi1._M_current != __bi1._M_end; // __bi2 is not sup
140 if (__bi1._M_current == __bi1._M_end) // __bi2 is sup
141 return false;
142 return !(__bi1.__comp)(*__bi2, *__bi1); // normal compare
143 }
144 };
145
146 template<typename _RAIter, typename _Compare>
147 class _UnguardedIterator
148 {
149 private:
150 /** @brief Current iterator __position. */
151 _RAIter _M_current;
152 /** @brief _Compare. */
153 _Compare& __comp;
154
155 public:
156 /** @brief Constructor. Sets iterator to beginning of sequence.
157 * @param __begin Begin iterator of sequence.
158 * @param __end Unused, only for compatibility.
159 * @param __comp Unused, only for compatibility. */
160 _UnguardedIterator(_RAIter __begin,
161 _RAIter /* __end */, _Compare& __comp)
162 : _M_current(__begin), __comp(__comp)
163 { }
164
165 /** @brief Pre-increment operator.
166 * @return This. */
167 _UnguardedIterator<_RAIter, _Compare>&
168 operator++()
169 {
170 ++_M_current;
171 return *this;
172 }
173
174 /** @brief Dereference operator.
175 * @return Referenced element. */
176 typename std::iterator_traits<_RAIter>::value_type&
177 operator*() const
178 { return *_M_current; }
179
180 /** @brief Convert to wrapped iterator.
181 * @return Wrapped iterator. */
182 operator _RAIter() const
183 { return _M_current; }
184
185 /** @brief Compare two elements referenced by unguarded iterators.
186 * @param __bi1 First iterator.
187 * @param __bi2 Second iterator.
188 * @return @c true if less. */
189 friend bool
190 operator<(const _UnguardedIterator<_RAIter, _Compare>& __bi1,
191 const _UnguardedIterator<_RAIter, _Compare>& __bi2)
192 {
193 // Normal compare.
194 return (__bi1.__comp)(*__bi1, *__bi2);
195 }
196
197 /** @brief Compare two elements referenced by unguarded iterators.
198 * @param __bi1 First iterator.
199 * @param __bi2 Second iterator.
200 * @return @c True if less equal. */
201 friend bool
202 operator<=(const _UnguardedIterator<_RAIter, _Compare>& __bi1,
203 const _UnguardedIterator<_RAIter, _Compare>& __bi2)
204 {
205 // Normal compare.
206 return !(__bi1.__comp)(*__bi2, *__bi1);
207 }
208 };
209
210 /** @brief Highly efficient 3-way merging procedure.
211 *
212 * Merging is done with the algorithm implementation described by Peter
213 * Sanders. Basically, the idea is to minimize the number of necessary
214 * comparison after merging an element. The implementation trick
215 * that makes this fast is that the order of the sequences is stored
216 * in the instruction pointer (translated into labels in C++).
217 *
218 * This works well for merging up to 4 sequences.
219 *
220 * Note that making the merging stable does @a not come at a
221 * performance hit.
222 *
223 * Whether the merging is done guarded or unguarded is selected by the
224 * used iterator class.
225 *
226 * @param __seqs_begin Begin iterator of iterator pair input sequence.
227 * @param __seqs_end End iterator of iterator pair input sequence.
228 * @param __target Begin iterator of output sequence.
229 * @param __comp Comparator.
230 * @param __length Maximum length to merge, less equal than the
231 * total number of elements available.
232 *
233 * @return End iterator of output sequence.
234 */
235 template<template<typename _RAI, typename _Cp> class iterator,
236 typename _RAIterIterator,
237 typename _RAIter3,
238 typename _DifferenceTp,
239 typename _Compare>
240 _RAIter3
241 multiway_merge_3_variant(_RAIterIterator __seqs_begin,
242 _RAIterIterator __seqs_end,
243 _RAIter3 __target,
244 _DifferenceTp __length, _Compare __comp)
245 {
246 _GLIBCXX_CALL(__length);
247
248 typedef _DifferenceTp _DifferenceType;
249
250 typedef typename std::iterator_traits<_RAIterIterator>
251 ::value_type::first_type
252 _RAIter1;
253 typedef typename std::iterator_traits<_RAIter1>::value_type
254 _ValueType;
255
256 if (__length == 0)
257 return __target;
258
259#if _GLIBCXX_PARALLEL_ASSERTIONS
260 _DifferenceTp __orig_length = __length;
261#endif
262
263 iterator<_RAIter1, _Compare>
264 __seq0(__seqs_begin[0].first, __seqs_begin[0].second, __comp),
265 __seq1(__seqs_begin[1].first, __seqs_begin[1].second, __comp),
266 __seq2(__seqs_begin[2].first, __seqs_begin[2].second, __comp);
267
268 if (__seq0 <= __seq1)
269 {
270 if (__seq1 <= __seq2)
271 goto __s012;
272 else
273 if (__seq2 < __seq0)
274 goto __s201;
275 else
276 goto __s021;
277 }
278 else
279 {
280 if (__seq1 <= __seq2)
281 {
282 if (__seq0 <= __seq2)
283 goto __s102;
284 else
285 goto __s120;
286 }
287 else
288 goto __s210;
289 }
290#define _GLIBCXX_PARALLEL_MERGE_3_CASE(__a, __b, __c, __c0, __c1) \
291 __s ## __a ## __b ## __c : \
292 *__target = *__seq ## __a; \
293 ++__target; \
294 --__length; \
295 ++__seq ## __a; \
296 if (__length == 0) goto __finish; \
297 if (__seq ## __a __c0 __seq ## __b) goto __s ## __a ## __b ## __c; \
298 if (__seq ## __a __c1 __seq ## __c) goto __s ## __b ## __a ## __c; \
299 goto __s ## __b ## __c ## __a;
300
301 _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 1, 2, <=, <=);
302 _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 2, 0, <=, < );
303 _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 0, 1, < , < );
304 _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 0, 2, < , <=);
305 _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 2, 1, <=, <=);
306 _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 1, 0, < , < );
307
308#undef _GLIBCXX_PARALLEL_MERGE_3_CASE
309
310 __finish:
311 ;
312
313#if _GLIBCXX_PARALLEL_ASSERTIONS
314 _GLIBCXX_PARALLEL_ASSERT(
315 ((_RAIter1)__seq0 - __seqs_begin[0].first) +
316 ((_RAIter1)__seq1 - __seqs_begin[1].first) +
317 ((_RAIter1)__seq2 - __seqs_begin[2].first)
318 == __orig_length);
319#endif
320
321 __seqs_begin[0].first = __seq0;
322 __seqs_begin[1].first = __seq1;
323 __seqs_begin[2].first = __seq2;
324
325 return __target;
326 }
327
328 /**
329 * @brief Highly efficient 4-way merging procedure.
330 *
331 * Merging is done with the algorithm implementation described by Peter
332 * Sanders. Basically, the idea is to minimize the number of necessary
333 * comparison after merging an element. The implementation trick
334 * that makes this fast is that the order of the sequences is stored
335 * in the instruction pointer (translated into goto labels in C++).
336 *
337 * This works well for merging up to 4 sequences.
338 *
339 * Note that making the merging stable does @a not come at a
340 * performance hit.
341 *
342 * Whether the merging is done guarded or unguarded is selected by the
343 * used iterator class.
344 *
345 * @param __seqs_begin Begin iterator of iterator pair input sequence.
346 * @param __seqs_end End iterator of iterator pair input sequence.
347 * @param __target Begin iterator of output sequence.
348 * @param __comp Comparator.
349 * @param __length Maximum length to merge, less equal than the
350 * total number of elements available.
351 *
352 * @return End iterator of output sequence.
353 */
354 template<template<typename _RAI, typename _Cp> class iterator,
355 typename _RAIterIterator,
356 typename _RAIter3,
357 typename _DifferenceTp,
358 typename _Compare>
359 _RAIter3
360 multiway_merge_4_variant(_RAIterIterator __seqs_begin,
361 _RAIterIterator __seqs_end,
362 _RAIter3 __target,
363 _DifferenceTp __length, _Compare __comp)
364 {
365 _GLIBCXX_CALL(__length);
366 typedef _DifferenceTp _DifferenceType;
367
368 typedef typename std::iterator_traits<_RAIterIterator>
369 ::value_type::first_type
370 _RAIter1;
371 typedef typename std::iterator_traits<_RAIter1>::value_type
372 _ValueType;
373
374 iterator<_RAIter1, _Compare>
375 __seq0(__seqs_begin[0].first, __seqs_begin[0].second, __comp),
376 __seq1(__seqs_begin[1].first, __seqs_begin[1].second, __comp),
377 __seq2(__seqs_begin[2].first, __seqs_begin[2].second, __comp),
378 __seq3(__seqs_begin[3].first, __seqs_begin[3].second, __comp);
379
380#define _GLIBCXX_PARALLEL_DECISION(__a, __b, __c, __d) { \
381 if (__seq ## __d < __seq ## __a) \
382 goto __s ## __d ## __a ## __b ## __c; \
383 if (__seq ## __d < __seq ## __b) \
384 goto __s ## __a ## __d ## __b ## __c; \
385 if (__seq ## __d < __seq ## __c) \
386 goto __s ## __a ## __b ## __d ## __c; \
387 goto __s ## __a ## __b ## __c ## __d; }
388
389 if (__seq0 <= __seq1)
390 {
391 if (__seq1 <= __seq2)
392 _GLIBCXX_PARALLEL_DECISION(0,1,2,3)
393 else
394 if (__seq2 < __seq0)
395 _GLIBCXX_PARALLEL_DECISION(2,0,1,3)
396 else
397 _GLIBCXX_PARALLEL_DECISION(0,2,1,3)
398 }
399 else
400 {
401 if (__seq1 <= __seq2)
402 {
403 if (__seq0 <= __seq2)
404 _GLIBCXX_PARALLEL_DECISION(1,0,2,3)
405 else
406 _GLIBCXX_PARALLEL_DECISION(1,2,0,3)
407 }
408 else
409 _GLIBCXX_PARALLEL_DECISION(2,1,0,3)
410 }
411
412#define _GLIBCXX_PARALLEL_MERGE_4_CASE(__a, __b, __c, __d, \
413 __c0, __c1, __c2) \
414 __s ## __a ## __b ## __c ## __d: \
415 if (__length == 0) goto __finish; \
416 *__target = *__seq ## __a; \
417 ++__target; \
418 --__length; \
419 ++__seq ## __a; \
420 if (__seq ## __a __c0 __seq ## __b) \
421 goto __s ## __a ## __b ## __c ## __d; \
422 if (__seq ## __a __c1 __seq ## __c) \
423 goto __s ## __b ## __a ## __c ## __d; \
424 if (__seq ## __a __c2 __seq ## __d) \
425 goto __s ## __b ## __c ## __a ## __d; \
426 goto __s ## __b ## __c ## __d ## __a;
427
428 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 2, 3, <=, <=, <=);
429 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 3, 2, <=, <=, <=);
430 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 1, 3, <=, <=, <=);
431 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 3, 1, <=, <=, <=);
432 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 1, 2, <=, <=, <=);
433 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 2, 1, <=, <=, <=);
434 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 2, 3, < , <=, <=);
435 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 3, 2, < , <=, <=);
436 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 0, 3, <=, < , <=);
437 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 3, 0, <=, <=, < );
438 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 0, 2, <=, < , <=);
439 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 2, 0, <=, <=, < );
440 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 1, 3, < , < , <=);
441 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 3, 1, < , <=, < );
442 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 0, 3, < , < , <=);
443 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 3, 0, < , <=, < );
444 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 0, 1, <=, < , < );
445 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 1, 0, <=, < , < );
446 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 1, 2, < , < , < );
447 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 2, 1, < , < , < );
448 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 0, 2, < , < , < );
449 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 2, 0, < , < , < );
450 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 0, 1, < , < , < );
451 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 1, 0, < , < , < );
452
453#undef _GLIBCXX_PARALLEL_MERGE_4_CASE
454#undef _GLIBCXX_PARALLEL_DECISION
455
456 __finish:
457 ;
458
459 __seqs_begin[0].first = __seq0;
460 __seqs_begin[1].first = __seq1;
461 __seqs_begin[2].first = __seq2;
462 __seqs_begin[3].first = __seq3;
463
464 return __target;
465 }
466
467 /** @brief Multi-way merging procedure for a high branching factor,
468 * guarded case.
469 *
470 * This merging variant uses a LoserTree class as selected by <tt>_LT</tt>.
471 *
472 * Stability is selected through the used LoserTree class <tt>_LT</tt>.
473 *
474 * At least one non-empty sequence is required.
475 *
476 * @param __seqs_begin Begin iterator of iterator pair input sequence.
477 * @param __seqs_end End iterator of iterator pair input sequence.
478 * @param __target Begin iterator of output sequence.
479 * @param __comp Comparator.
480 * @param __length Maximum length to merge, less equal than the
481 * total number of elements available.
482 *
483 * @return End iterator of output sequence.
484 */
485 template<typename _LT,
486 typename _RAIterIterator,
487 typename _RAIter3,
488 typename _DifferenceTp,
489 typename _Compare>
490 _RAIter3
491 multiway_merge_loser_tree(_RAIterIterator __seqs_begin,
492 _RAIterIterator __seqs_end,
493 _RAIter3 __target,
494 _DifferenceTp __length, _Compare __comp)
495 {
496 _GLIBCXX_CALL(__length)
497
498 typedef _DifferenceTp _DifferenceType;
499 typedef typename std::iterator_traits<_RAIterIterator>
500 ::difference_type _SeqNumber;
501 typedef typename std::iterator_traits<_RAIterIterator>
502 ::value_type::first_type
503 _RAIter1;
504 typedef typename std::iterator_traits<_RAIter1>::value_type
505 _ValueType;
506
507 _SeqNumber __k = static_cast<_SeqNumber>(__seqs_end - __seqs_begin);
508
509 _LT __lt(__k, __comp);
510
511 // Default value for potentially non-default-constructible types.
512 _ValueType* __arbitrary_element = 0;
513
514 for (_SeqNumber __t = 0; __t < __k; ++__t)
515 {
516 if(!__arbitrary_element
517 && _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__t]) > 0)
518 __arbitrary_element = &(*__seqs_begin[__t].first);
519 }
520
521 for (_SeqNumber __t = 0; __t < __k; ++__t)
522 {
523 if (__seqs_begin[__t].first == __seqs_begin[__t].second)
524 __lt.__insert_start(*__arbitrary_element, __t, true);
525 else
526 __lt.__insert_start(*__seqs_begin[__t].first, __t, false);
527 }
528
529 __lt.__init();
530
531 _SeqNumber __source;
532
533 for (_DifferenceType __i = 0; __i < __length; ++__i)
534 {
535 //take out
536 __source = __lt.__get_min_source();
537
538 *(__target++) = *(__seqs_begin[__source].first++);
539
540 // Feed.
541 if (__seqs_begin[__source].first == __seqs_begin[__source].second)
542 __lt.__delete_min_insert(*__arbitrary_element, true);
543 else
544 // Replace from same __source.
545 __lt.__delete_min_insert(*__seqs_begin[__source].first, false);
546 }
547
548 return __target;
549 }
550
551 /** @brief Multi-way merging procedure for a high branching factor,
552 * unguarded case.
553 *
554 * Merging is done using the LoserTree class <tt>_LT</tt>.
555 *
556 * Stability is selected by the used LoserTrees.
557 *
558 * @pre No input will run out of elements during the merge.
559 *
560 * @param __seqs_begin Begin iterator of iterator pair input sequence.
561 * @param __seqs_end End iterator of iterator pair input sequence.
562 * @param __target Begin iterator of output sequence.
563 * @param __comp Comparator.
564 * @param __length Maximum length to merge, less equal than the
565 * total number of elements available.
566 *
567 * @return End iterator of output sequence.
568 */
569 template<typename _LT,
570 typename _RAIterIterator,
571 typename _RAIter3,
572 typename _DifferenceTp, typename _Compare>
573 _RAIter3
574 multiway_merge_loser_tree_unguarded(_RAIterIterator __seqs_begin,
575 _RAIterIterator __seqs_end,
576 _RAIter3 __target,
577 const typename std::iterator_traits<typename std::iterator_traits<
578 _RAIterIterator>::value_type::first_type>::value_type&
579 __sentinel,
580 _DifferenceTp __length,
581 _Compare __comp)
582 {
583 _GLIBCXX_CALL(__length)
584 typedef _DifferenceTp _DifferenceType;
585
586 typedef typename std::iterator_traits<_RAIterIterator>
587 ::difference_type _SeqNumber;
588 typedef typename std::iterator_traits<_RAIterIterator>
589 ::value_type::first_type
590 _RAIter1;
591 typedef typename std::iterator_traits<_RAIter1>::value_type
592 _ValueType;
593
594 _SeqNumber __k = __seqs_end - __seqs_begin;
595
596 _LT __lt(__k, __sentinel, __comp);
597
598 for (_SeqNumber __t = 0; __t < __k; ++__t)
599 {
600#if _GLIBCXX_PARALLEL_ASSERTIONS
601 _GLIBCXX_PARALLEL_ASSERT(__seqs_begin[__t].first
602 != __seqs_begin[__t].second);
603#endif
604 __lt.__insert_start(*__seqs_begin[__t].first, __t, false);
605 }
606
607 __lt.__init();
608
609 _SeqNumber __source;
610
611#if _GLIBCXX_PARALLEL_ASSERTIONS
612 _DifferenceType __i = 0;
613#endif
614
615 _RAIter3 __target_end = __target + __length;
616 while (__target < __target_end)
617 {
618 // Take out.
619 __source = __lt.__get_min_source();
620
621#if _GLIBCXX_PARALLEL_ASSERTIONS
622 _GLIBCXX_PARALLEL_ASSERT(0 <= __source && __source < __k);
623 _GLIBCXX_PARALLEL_ASSERT(__i == 0
624 || !__comp(*(__seqs_begin[__source].first), *(__target - 1)));
625#endif
626
627 // Feed.
628 *(__target++) = *(__seqs_begin[__source].first++);
629
630#if _GLIBCXX_PARALLEL_ASSERTIONS
631 ++__i;
632#endif
633 // Replace from same __source.
634 __lt.__delete_min_insert(*__seqs_begin[__source].first, false);
635 }
636
637 return __target;
638 }
639
640
641 /** @brief Multi-way merging procedure for a high branching factor,
642 * requiring sentinels to exist.
643 *
644 * @tparam _UnguardedLoserTree Loser Tree variant to use for the unguarded
645 * merging.
646 *
647 * @param __seqs_begin Begin iterator of iterator pair input sequence.
648 * @param __seqs_end End iterator of iterator pair input sequence.
649 * @param __target Begin iterator of output sequence.
650 * @param __comp Comparator.
651 * @param __length Maximum length to merge, less equal than the
652 * total number of elements available.
653 *
654 * @return End iterator of output sequence.
655 */
656 template<typename _UnguardedLoserTree,
657 typename _RAIterIterator,
658 typename _RAIter3,
659 typename _DifferenceTp,
660 typename _Compare>
661 _RAIter3
662 multiway_merge_loser_tree_sentinel(_RAIterIterator __seqs_begin,
663 _RAIterIterator __seqs_end,
664 _RAIter3 __target,
665 const typename std::iterator_traits<typename std::iterator_traits<
666 _RAIterIterator>::value_type::first_type>::value_type&
667 __sentinel,
668 _DifferenceTp __length,
669 _Compare __comp)
670 {
671 _GLIBCXX_CALL(__length)
672
673 typedef _DifferenceTp _DifferenceType;
674 typedef std::iterator_traits<_RAIterIterator> _TraitsType;
675 typedef typename std::iterator_traits<_RAIterIterator>
676 ::value_type::first_type
677 _RAIter1;
678 typedef typename std::iterator_traits<_RAIter1>::value_type
679 _ValueType;
680
681 _RAIter3 __target_end;
682
683 for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
684 // Move the sequence ends to the sentinel. This has the
685 // effect that the sentinel appears to be within the sequence. Then,
686 // we can use the unguarded variant if we merge out as many
687 // non-sentinel elements as we have.
688 ++((*__s).second);
689
690 __target_end = multiway_merge_loser_tree_unguarded<_UnguardedLoserTree>
691 (__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp);
692
693#if _GLIBCXX_PARALLEL_ASSERTIONS
694 _GLIBCXX_PARALLEL_ASSERT(__target_end == __target + __length);
695 _GLIBCXX_PARALLEL_ASSERT(__is_sorted(__target, __target_end, __comp));
696#endif
697
698 // Restore the sequence ends so the sentinels are not contained in the
699 // sequence any more (see comment in loop above).
700 for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
701 --((*__s).second);
702
703 return __target_end;
704 }
705
706 /**
707 * @brief Traits for determining whether the loser tree should
708 * use pointers or copies.
709 *
710 * The field "_M_use_pointer" is used to determine whether to use pointers
711 * in he loser trees or whether to copy the values into the loser tree.
712 *
713 * The default behavior is to use pointers if the data type is 4 times as
714 * big as the pointer to it.
715 *
716 * Specialize for your data type to customize the behavior.
717 *
718 * Example:
719 *
720 * template<>
721 * struct _LoserTreeTraits<int>
722 * { static const bool _M_use_pointer = false; };
723 *
724 * template<>
725 * struct _LoserTreeTraits<heavyweight_type>
726 * { static const bool _M_use_pointer = true; };
727 *
728 * @param _Tp type to give the loser tree traits for.
729 */
730 template <typename _Tp>
731 struct _LoserTreeTraits
732 {
733 /**
734 * @brief True iff to use pointers instead of values in loser trees.
735 *
736 * The default behavior is to use pointers if the data type is four
737 * times as big as the pointer to it.
738 */
739 static const bool _M_use_pointer = (sizeof(_Tp) > 4 * sizeof(_Tp*));
740 };
741
742 /**
743 * @brief Switch for 3-way merging with __sentinels turned off.
744 *
745 * Note that 3-way merging is always stable!
746 */
747 template<bool __sentinels /*default == false*/,
748 typename _RAIterIterator,
749 typename _RAIter3,
750 typename _DifferenceTp,
751 typename _Compare>
752 struct __multiway_merge_3_variant_sentinel_switch
753 {
754 _RAIter3
755 operator()(_RAIterIterator __seqs_begin,
756 _RAIterIterator __seqs_end,
757 _RAIter3 __target,
758 _DifferenceTp __length, _Compare __comp)
759 { return multiway_merge_3_variant<_GuardedIterator>
760 (__seqs_begin, __seqs_end, __target, __length, __comp); }
761 };
762
763 /**
764 * @brief Switch for 3-way merging with __sentinels turned on.
765 *
766 * Note that 3-way merging is always stable!
767 */
768 template<typename _RAIterIterator,
769 typename _RAIter3,
770 typename _DifferenceTp,
771 typename _Compare>
772 struct __multiway_merge_3_variant_sentinel_switch<true, _RAIterIterator,
773 _RAIter3, _DifferenceTp,
774 _Compare>
775 {
776 _RAIter3
777 operator()(_RAIterIterator __seqs_begin,
778 _RAIterIterator __seqs_end,
779 _RAIter3 __target,
780 _DifferenceTp __length, _Compare __comp)
781 { return multiway_merge_3_variant<_UnguardedIterator>
782 (__seqs_begin, __seqs_end, __target, __length, __comp); }
783 };
784
785 /**
786 * @brief Switch for 4-way merging with __sentinels turned off.
787 *
788 * Note that 4-way merging is always stable!
789 */
790 template<bool __sentinels /*default == false*/,
791 typename _RAIterIterator,
792 typename _RAIter3,
793 typename _DifferenceTp,
794 typename _Compare>
795 struct __multiway_merge_4_variant_sentinel_switch
796 {
797 _RAIter3
798 operator()(_RAIterIterator __seqs_begin,
799 _RAIterIterator __seqs_end,
800 _RAIter3 __target,
801 _DifferenceTp __length, _Compare __comp)
802 { return multiway_merge_4_variant<_GuardedIterator>
803 (__seqs_begin, __seqs_end, __target, __length, __comp); }
804 };
805
806 /**
807 * @brief Switch for 4-way merging with __sentinels turned on.
808 *
809 * Note that 4-way merging is always stable!
810 */
811 template<typename _RAIterIterator,
812 typename _RAIter3,
813 typename _DifferenceTp,
814 typename _Compare>
815 struct __multiway_merge_4_variant_sentinel_switch<true, _RAIterIterator,
816 _RAIter3, _DifferenceTp,
817 _Compare>
818 {
819 _RAIter3
820 operator()(_RAIterIterator __seqs_begin,
821 _RAIterIterator __seqs_end,
822 _RAIter3 __target,
823 _DifferenceTp __length, _Compare __comp)
824 { return multiway_merge_4_variant<_UnguardedIterator>
825 (__seqs_begin, __seqs_end, __target, __length, __comp); }
826 };
827
828 /**
829 * @brief Switch for k-way merging with __sentinels turned on.
830 */
831 template<bool __sentinels,
832 bool __stable,
833 typename _RAIterIterator,
834 typename _RAIter3,
835 typename _DifferenceTp,
836 typename _Compare>
837 struct __multiway_merge_k_variant_sentinel_switch
838 {
839 _RAIter3
840 operator()(_RAIterIterator __seqs_begin,
841 _RAIterIterator __seqs_end,
842 _RAIter3 __target,
843 const typename std::iterator_traits<typename std::iterator_traits<
844 _RAIterIterator>::value_type::first_type>::value_type&
845 __sentinel,
846 _DifferenceTp __length, _Compare __comp)
847 {
848 typedef typename std::iterator_traits<_RAIterIterator>
849 ::value_type::first_type
850 _RAIter1;
851 typedef typename std::iterator_traits<_RAIter1>::value_type
852 _ValueType;
853
854 return multiway_merge_loser_tree_sentinel<
855 typename __gnu_cxx::__conditional_type<
856 _LoserTreeTraits<_ValueType>::_M_use_pointer,
857 _LoserTreePointerUnguarded<__stable, _ValueType, _Compare>,
858 _LoserTreeUnguarded<__stable, _ValueType, _Compare>
859 >::__type>
860 (__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp);
861 }
862 };
863
864 /**
865 * @brief Switch for k-way merging with __sentinels turned off.
866 */
867 template<bool __stable,
868 typename _RAIterIterator,
869 typename _RAIter3,
870 typename _DifferenceTp,
871 typename _Compare>
872 struct __multiway_merge_k_variant_sentinel_switch<false, __stable,
873 _RAIterIterator,
874 _RAIter3, _DifferenceTp,
875 _Compare>
876 {
877 _RAIter3
878 operator()(_RAIterIterator __seqs_begin,
879 _RAIterIterator __seqs_end,
880 _RAIter3 __target,
881 const typename std::iterator_traits<typename std::iterator_traits<
882 _RAIterIterator>::value_type::first_type>::value_type&
883 __sentinel,
884 _DifferenceTp __length, _Compare __comp)
885 {
886 typedef typename std::iterator_traits<_RAIterIterator>
887 ::value_type::first_type
888 _RAIter1;
889 typedef typename std::iterator_traits<_RAIter1>::value_type
890 _ValueType;
891
892 return multiway_merge_loser_tree<
893 typename __gnu_cxx::__conditional_type<
894 _LoserTreeTraits<_ValueType>::_M_use_pointer,
895 _LoserTreePointer<__stable, _ValueType, _Compare>,
896 _LoserTree<__stable, _ValueType, _Compare>
897 >::__type >(__seqs_begin, __seqs_end, __target, __length, __comp);
898 }
899 };
900
901 /** @brief Sequential multi-way merging switch.
902 *
903 * The _GLIBCXX_PARALLEL_DECISION is based on the branching factor and
904 * runtime settings.
905 * @param __seqs_begin Begin iterator of iterator pair input sequence.
906 * @param __seqs_end End iterator of iterator pair input sequence.
907 * @param __target Begin iterator of output sequence.
908 * @param __comp Comparator.
909 * @param __length Maximum length to merge, possibly larger than the
910 * number of elements available.
911 * @param __sentinel The sequences have __a __sentinel element.
912 * @return End iterator of output sequence. */
913 template<bool __stable,
914 bool __sentinels,
915 typename _RAIterIterator,
916 typename _RAIter3,
917 typename _DifferenceTp,
918 typename _Compare>
919 _RAIter3
920 __sequential_multiway_merge(_RAIterIterator __seqs_begin,
921 _RAIterIterator __seqs_end,
922 _RAIter3 __target,
923 const typename std::iterator_traits<typename std::iterator_traits<
924 _RAIterIterator>::value_type::first_type>::value_type&
925 __sentinel,
926 _DifferenceTp __length, _Compare __comp)
927 {
928 _GLIBCXX_CALL(__length)
929
930 typedef _DifferenceTp _DifferenceType;
931 typedef typename std::iterator_traits<_RAIterIterator>
932 ::difference_type _SeqNumber;
933 typedef typename std::iterator_traits<_RAIterIterator>
934 ::value_type::first_type
935 _RAIter1;
936 typedef typename std::iterator_traits<_RAIter1>::value_type
937 _ValueType;
938
939#if _GLIBCXX_PARALLEL_ASSERTIONS
940 for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
941 {
942 _GLIBCXX_PARALLEL_ASSERT(__is_sorted((*__s).first,
943 (*__s).second, __comp));
944 }
945#endif
946
947 _DifferenceTp __total_length = 0;
948 for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
949 __total_length += _GLIBCXX_PARALLEL_LENGTH(*__s);
950
951 __length = std::min<_DifferenceTp>(__length, __total_length);
952
953 if(__length == 0)
954 return __target;
955
956 _RAIter3 __return_target = __target;
957 _SeqNumber __k = static_cast<_SeqNumber>(__seqs_end - __seqs_begin);
958
959 switch (__k)
960 {
961 case 0:
962 break;
963 case 1:
964 __return_target = std::copy(__seqs_begin[0].first,
965 __seqs_begin[0].first + __length,
966 __target);
967 __seqs_begin[0].first += __length;
968 break;
969 case 2:
970 __return_target = __merge_advance(__seqs_begin[0].first,
971 __seqs_begin[0].second,
972 __seqs_begin[1].first,
973 __seqs_begin[1].second,
974 __target, __length, __comp);
975 break;
976 case 3:
977 __return_target = __multiway_merge_3_variant_sentinel_switch
978 <__sentinels, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare>()
979 (__seqs_begin, __seqs_end, __target, __length, __comp);
980 break;
981 case 4:
982 __return_target = __multiway_merge_4_variant_sentinel_switch
983 <__sentinels, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare>()
984 (__seqs_begin, __seqs_end, __target, __length, __comp);
985 break;
986 default:
987 __return_target = __multiway_merge_k_variant_sentinel_switch
988 <__sentinels, __stable, _RAIterIterator, _RAIter3, _DifferenceTp,
989 _Compare>()
990 (__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp);
991 break;
992 }
993#if _GLIBCXX_PARALLEL_ASSERTIONS
994 _GLIBCXX_PARALLEL_ASSERT(
995 __is_sorted(__target, __target + __length, __comp));
996#endif
997
998 return __return_target;
999 }
1000
1001 /**
1002 * @brief Stable sorting functor.
1003 *
1004 * Used to reduce code instanciation in multiway_merge_sampling_splitting.
1005 */
1006 template<bool __stable, class _RAIter, class _StrictWeakOrdering>
1007 struct _SamplingSorter
1008 {
1009 void
1010 operator()(_RAIter __first, _RAIter __last, _StrictWeakOrdering __comp)
1011 { __gnu_sequential::stable_sort(__first, __last, __comp); }
1012 };
1013
1014 /**
1015 * @brief Non-__stable sorting functor.
1016 *
1017 * Used to reduce code instantiation in multiway_merge_sampling_splitting.
1018 */
1019 template<class _RAIter, class _StrictWeakOrdering>
1020 struct _SamplingSorter<false, _RAIter, _StrictWeakOrdering>
1021 {
1022 void
1023 operator()(_RAIter __first, _RAIter __last, _StrictWeakOrdering __comp)
1024 { __gnu_sequential::sort(__first, __last, __comp); }
1025 };
1026
1027 /**
1028 * @brief Sampling based splitting for parallel multiway-merge routine.
1029 */
1030 template<bool __stable,
1031 typename _RAIterIterator,
1032 typename _Compare,
1033 typename _DifferenceType>
1034 void
1035 multiway_merge_sampling_splitting(_RAIterIterator __seqs_begin,
1036 _RAIterIterator __seqs_end,
1037 _DifferenceType __length,
1038 _DifferenceType __total_length,
1039 _Compare __comp,
1040 std::vector<std::pair<_DifferenceType, _DifferenceType> > *__pieces)
1041 {
1042 typedef typename std::iterator_traits<_RAIterIterator>
1043 ::difference_type _SeqNumber;
1044 typedef typename std::iterator_traits<_RAIterIterator>
1045 ::value_type::first_type
1046 _RAIter1;
1047 typedef typename std::iterator_traits<_RAIter1>::value_type
1048 _ValueType;
1049
1050 // __k sequences.
1051 const _SeqNumber __k
1052 = static_cast<_SeqNumber>(__seqs_end - __seqs_begin);
1053
1054 const _ThreadIndex __num_threads = omp_get_num_threads();
1055
1056 const _DifferenceType __num_samples =
1057 __gnu_parallel::_Settings::get().merge_oversampling * __num_threads;
1058
1059 _ValueType* __samples = static_cast<_ValueType*>
1060 (::operator new(sizeof(_ValueType) * __k * __num_samples));
1061 // Sample.
1062 for (_SeqNumber __s = 0; __s < __k; ++__s)
1063 for (_DifferenceType __i = 0; __i < __num_samples; ++__i)
1064 {
1065 _DifferenceType sample_index = static_cast<_DifferenceType>
1066 (_GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__s])
1067 * (double(__i + 1) / (__num_samples + 1))
1068 * (double(__length) / __total_length));
1069 new(&(__samples[__s * __num_samples + __i]))
1070 _ValueType(__seqs_begin[__s].first[sample_index]);
1071 }
1072
1073 // Sort stable or non-stable, depending on value of template parameter
1074 // "__stable".
1075 _SamplingSorter<__stable, _ValueType*, _Compare>()
1076 (__samples, __samples + (__num_samples * __k), __comp);
1077
1078 for (_ThreadIndex __slab = 0; __slab < __num_threads; ++__slab)
1079 // For each slab / processor.
1080 for (_SeqNumber __seq = 0; __seq < __k; ++__seq)
1081 {
1082 // For each sequence.
1083 if (__slab > 0)
1084 __pieces[__slab][__seq].first = std::upper_bound
1085 (__seqs_begin[__seq].first, __seqs_begin[__seq].second,
1086 __samples[__num_samples * __k * __slab / __num_threads],
1087 __comp)
1088 - __seqs_begin[__seq].first;
1089 else
1090 // Absolute beginning.
1091 __pieces[__slab][__seq].first = 0;
1092 if ((__slab + 1) < __num_threads)
1093 __pieces[__slab][__seq].second = std::upper_bound
1094 (__seqs_begin[__seq].first, __seqs_begin[__seq].second,
1095 __samples[__num_samples * __k * (__slab + 1) / __num_threads],
1096 __comp)
1097 - __seqs_begin[__seq].first;
1098 else
1099 // Absolute end.
1100 __pieces[__slab][__seq].second =
1101 _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__seq]);
1102 }
1103
1104 for (_SeqNumber __s = 0; __s < __k; ++__s)
1105 for (_DifferenceType __i = 0; __i < __num_samples; ++__i)
1106 __samples[__s * __num_samples + __i].~_ValueType();
1107 ::operator delete(__samples);
1108 }
1109
1110 /**
1111 * @brief Exact splitting for parallel multiway-merge routine.
1112 *
1113 * None of the passed sequences may be empty.
1114 */
1115 template<bool __stable,
1116 typename _RAIterIterator,
1117 typename _Compare,
1118 typename _DifferenceType>
1119 void
1120 multiway_merge_exact_splitting(_RAIterIterator __seqs_begin,
1121 _RAIterIterator __seqs_end,
1122 _DifferenceType __length,
1123 _DifferenceType __total_length,
1124 _Compare __comp,
1125 std::vector<std::pair<_DifferenceType, _DifferenceType> > *__pieces)
1126 {
1127 typedef typename std::iterator_traits<_RAIterIterator>
1128 ::difference_type _SeqNumber;
1129 typedef typename std::iterator_traits<_RAIterIterator>
1130 ::value_type::first_type
1131 _RAIter1;
1132
1133 const bool __tight = (__total_length == __length);
1134
1135 // __k sequences.
1136 const _SeqNumber __k = __seqs_end - __seqs_begin;
1137
1138 const _ThreadIndex __num_threads = omp_get_num_threads();
1139
1140 // (Settings::multiway_merge_splitting
1141 // == __gnu_parallel::_Settings::EXACT).
1142 std::vector<_RAIter1>* __offsets =
1143 new std::vector<_RAIter1>[__num_threads];
1144 std::vector<std::pair<_RAIter1, _RAIter1> > __se(__k);
1145
1146 copy(__seqs_begin, __seqs_end, __se.begin());
1147
1148 _DifferenceType* __borders =
1149 new _DifferenceType[__num_threads + 1];
1150 __equally_split(__length, __num_threads, __borders);
1151
1152 for (_ThreadIndex __s = 0; __s < (__num_threads - 1); ++__s)
1153 {
1154 __offsets[__s].resize(__k);
1155 multiseq_partition(__se.begin(), __se.end(), __borders[__s + 1],
1156 __offsets[__s].begin(), __comp);
1157
1158 // Last one also needed and available.
1159 if (!__tight)
1160 {
1161 __offsets[__num_threads - 1].resize(__k);
1162 multiseq_partition(__se.begin(), __se.end(),
1163 _DifferenceType(__length),
1164 __offsets[__num_threads - 1].begin(),
1165 __comp);
1166 }
1167 }
1168 delete[] __borders;
1169
1170 for (_ThreadIndex __slab = 0; __slab < __num_threads; ++__slab)
1171 {
1172 // For each slab / processor.
1173 for (_SeqNumber __seq = 0; __seq < __k; ++__seq)
1174 {
1175 // For each sequence.
1176 if (__slab == 0)
1177 {
1178 // Absolute beginning.
1179 __pieces[__slab][__seq].first = 0;
1180 }
1181 else
1182 __pieces[__slab][__seq].first =
1183 __pieces[__slab - 1][__seq].second;
1184 if (!__tight || __slab < (__num_threads - 1))
1185 __pieces[__slab][__seq].second =
1186 __offsets[__slab][__seq] - __seqs_begin[__seq].first;
1187 else
1188 {
1189 // __slab == __num_threads - 1
1190 __pieces[__slab][__seq].second =
1191 _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__seq]);
1192 }
1193 }
1194 }
1195 delete[] __offsets;
1196 }
1197
1198 /** @brief Parallel multi-way merge routine.
1199 *
1200 * The _GLIBCXX_PARALLEL_DECISION is based on the branching factor
1201 * and runtime settings.
1202 *
1203 * Must not be called if the number of sequences is 1.
1204 *
1205 * @tparam _Splitter functor to split input (either __exact or sampling based)
1206 * @tparam __stable Stable merging incurs a performance penalty.
1207 * @tparam __sentinel Ignored.
1208 *
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 of output sequence.
1212 * @param __comp Comparator.
1213 * @param __length Maximum length to merge, possibly larger than the
1214 * number of elements available.
1215 * @return End iterator of output sequence.
1216 */
1217 template<bool __stable,
1218 bool __sentinels,
1219 typename _RAIterIterator,
1220 typename _RAIter3,
1221 typename _DifferenceTp,
1222 typename _Splitter,
1223 typename _Compare>
1224 _RAIter3
1225 parallel_multiway_merge(_RAIterIterator __seqs_begin,
1226 _RAIterIterator __seqs_end,
1227 _RAIter3 __target,
1228 _Splitter __splitter,
1229 _DifferenceTp __length,
1230 _Compare __comp,
1231 _ThreadIndex __num_threads)
1232 {
1233#if _GLIBCXX_PARALLEL_ASSERTIONS
1234 _GLIBCXX_PARALLEL_ASSERT(__seqs_end - __seqs_begin > 1);
1235#endif
1236
1237 _GLIBCXX_CALL(__length)
1238
1239 typedef _DifferenceTp _DifferenceType;
1240 typedef typename std::iterator_traits<_RAIterIterator>
1241 ::difference_type _SeqNumber;
1242 typedef typename std::iterator_traits<_RAIterIterator>
1243 ::value_type::first_type
1244 _RAIter1;
1245 typedef typename
1246 std::iterator_traits<_RAIter1>::value_type _ValueType;
1247
1248 // Leave only non-empty sequences.
1249 typedef std::pair<_RAIter1, _RAIter1> seq_type;
1250 seq_type* __ne_seqs = new seq_type[__seqs_end - __seqs_begin];
1251 _SeqNumber __k = 0;
1252 _DifferenceType __total_length = 0;
1253 for (_RAIterIterator __raii = __seqs_begin;
1254 __raii != __seqs_end; ++__raii)
1255 {
1256 _DifferenceTp __seq_length = _GLIBCXX_PARALLEL_LENGTH(*__raii);
1257 if(__seq_length > 0)
1258 {
1259 __total_length += __seq_length;
1260 __ne_seqs[__k++] = *__raii;
1261 }
1262 }
1263
1264 _GLIBCXX_CALL(__total_length)
1265
1266 __length = std::min<_DifferenceTp>(__length, __total_length);
1267
1268 if (__total_length == 0 || __k == 0)
1269 {
1270 delete[] __ne_seqs;
1271 return __target;
1272 }
1273
1274 std::vector<std::pair<_DifferenceType, _DifferenceType> >* __pieces;
1275
1276 __num_threads = static_cast<_ThreadIndex>
1277 (std::min<_DifferenceType>(__num_threads, __total_length));
1278
1279# pragma omp parallel num_threads (__num_threads)
1280 {
1281# pragma omp single
1282 {
1283 __num_threads = omp_get_num_threads();
1284 // Thread __t will have to merge pieces[__iam][0..__k - 1]
1285 __pieces = new std::vector<
1286 std::pair<_DifferenceType, _DifferenceType> >[__num_threads];
1287 for (_ThreadIndex __s = 0; __s < __num_threads; ++__s)
1288 __pieces[__s].resize(__k);
1289
1290 _DifferenceType __num_samples =
1291 __gnu_parallel::_Settings::get().merge_oversampling
1292 * __num_threads;
1293
1294 __splitter(__ne_seqs, __ne_seqs + __k, __length, __total_length,
1295 __comp, __pieces);
1296 } //single
1297
1298 _ThreadIndex __iam = omp_get_thread_num();
1299
1300 _DifferenceType __target_position = 0;
1301
1302 for (_SeqNumber __c = 0; __c < __k; ++__c)
1303 __target_position += __pieces[__iam][__c].first;
1304
1305 seq_type* __chunks = new seq_type[__k];
1306
1307 for (_SeqNumber __s = 0; __s < __k; ++__s)
1308 __chunks[__s] = std::make_pair(__ne_seqs[__s].first
1309 + __pieces[__iam][__s].first,
1310 __ne_seqs[__s].first
1311 + __pieces[__iam][__s].second);
1312
1313 if(__length > __target_position)
1314 __sequential_multiway_merge<__stable, __sentinels>
1315 (__chunks, __chunks + __k, __target + __target_position,
1316 *(__seqs_begin->second), __length - __target_position, __comp);
1317
1318 delete[] __chunks;
1319 } // parallel
1320
1321#if _GLIBCXX_PARALLEL_ASSERTIONS
1322 _GLIBCXX_PARALLEL_ASSERT(
1323 __is_sorted(__target, __target + __length, __comp));
1324#endif
1325
1326 __k = 0;
1327 // Update ends of sequences.
1328 for (_RAIterIterator __raii = __seqs_begin;
1329 __raii != __seqs_end; ++__raii)
1330 {
1331 _DifferenceTp __length = _GLIBCXX_PARALLEL_LENGTH(*__raii);
1332 if(__length > 0)
1333 (*__raii).first += __pieces[__num_threads - 1][__k++].second;
1334 }
1335
1336 delete[] __pieces;
1337 delete[] __ne_seqs;
1338
1339 return __target + __length;
1340 }
1341
1342 /**
1343 * @brief Multiway Merge Frontend.
1344 *
1345 * Merge the sequences specified by seqs_begin and __seqs_end into
1346 * __target. __seqs_begin and __seqs_end must point to a sequence of
1347 * pairs. These pairs must contain an iterator to the beginning
1348 * of a sequence in their first entry and an iterator the _M_end of
1349 * the same sequence in their second entry.
1350 *
1351 * Ties are broken arbitrarily. See stable_multiway_merge for a variant
1352 * that breaks ties by sequence number but is slower.
1353 *
1354 * The first entries of the pairs (i.e. the begin iterators) will be moved
1355 * forward.
1356 *
1357 * The output sequence has to provide enough space for all elements
1358 * that are written to it.
1359 *
1360 * This function will merge the input sequences:
1361 *
1362 * - not stable
1363 * - parallel, depending on the input size and Settings
1364 * - using sampling for splitting
1365 * - not using sentinels
1366 *
1367 * Example:
1368 *
1369 * <pre>
1370 * int sequences[10][10];
1371 * for (int __i = 0; __i < 10; ++__i)
1372 * for (int __j = 0; __i < 10; ++__j)
1373 * sequences[__i][__j] = __j;
1374 *
1375 * int __out[33];
1376 * std::vector<std::pair<int*> > seqs;
1377 * for (int __i = 0; __i < 10; ++__i)
1378 * { seqs.push(std::make_pair<int*>(sequences[__i],
1379 * sequences[__i] + 10)) }
1380 *
1381 * multiway_merge(seqs.begin(), seqs.end(), __target, std::less<int>(), 33);
1382 * </pre>
1383 *
1384 * @see stable_multiway_merge
1385 *
1386 * @pre All input sequences must be sorted.
1387 * @pre Target must provide enough space to merge out length elements or
1388 * the number of elements in all sequences, whichever is smaller.
1389 *
1390 * @post [__target, return __value) contains merged __elements from the
1391 * input sequences.
1392 * @post return __value - __target = min(__length, number of elements in all
1393 * sequences).
1394 *
1395 * @tparam _RAIterPairIterator iterator over sequence
1396 * of pairs of iterators
1397 * @tparam _RAIterOut iterator over target sequence
1398 * @tparam _DifferenceTp difference type for the sequence
1399 * @tparam _Compare strict weak ordering type to compare elements
1400 * in sequences
1401 *
1402 * @param __seqs_begin __begin of sequence __sequence
1403 * @param __seqs_end _M_end of sequence __sequence
1404 * @param __target target sequence to merge to.
1405 * @param __comp strict weak ordering to use for element comparison.
1406 * @param __length Maximum length to merge, possibly larger than the
1407 * number of elements available.
1408 *
1409 * @return _M_end iterator of output sequence
1410 */
1411 // multiway_merge
1412 // public interface
1413 template<typename _RAIterPairIterator,
1414 typename _RAIterOut,
1415 typename _DifferenceTp,
1416 typename _Compare>
1417 _RAIterOut
1418 multiway_merge(_RAIterPairIterator __seqs_begin,
1419 _RAIterPairIterator __seqs_end,
1420 _RAIterOut __target,
1421 _DifferenceTp __length, _Compare __comp,
1422 __gnu_parallel::sequential_tag)
1423 {
1424 typedef _DifferenceTp _DifferenceType;
1425 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1426
1427 // catch special case: no sequences
1428 if (__seqs_begin == __seqs_end)
1429 return __target;
1430
1431 // Execute multiway merge *sequentially*.
1432 return __sequential_multiway_merge
1433 </* __stable = */ false, /* __sentinels = */ false>
1434 (__seqs_begin, __seqs_end, __target,
1435 *(__seqs_begin->second), __length, __comp);
1436 }
1437
1438 // public interface
1439 template<typename _RAIterPairIterator,
1440 typename _RAIterOut,
1441 typename _DifferenceTp,
1442 typename _Compare>
1443 _RAIterOut
1444 multiway_merge(_RAIterPairIterator __seqs_begin,
1445 _RAIterPairIterator __seqs_end,
1446 _RAIterOut __target,
1447 _DifferenceTp __length, _Compare __comp,
1448 __gnu_parallel::exact_tag __tag)
1449 {
1450 typedef _DifferenceTp _DifferenceType;
1451 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1452
1453 // catch special case: no sequences
1454 if (__seqs_begin == __seqs_end)
1455 return __target;
1456
1457 // Execute merge; maybe parallel, depending on the number of merged
1458 // elements and the number of sequences and global thresholds in
1459 // Settings.
1460 if ((__seqs_end - __seqs_begin > 1)
1461 && _GLIBCXX_PARALLEL_CONDITION(
1462 ((__seqs_end - __seqs_begin) >=
1463 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1464 && ((_SequenceIndex)__length >=
1465 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1466 return parallel_multiway_merge
1467 </* __stable = */ false, /* __sentinels = */ false>
1468 (__seqs_begin, __seqs_end, __target,
1469 multiway_merge_exact_splitting</* __stable = */ false,
1470 typename std::iterator_traits<_RAIterPairIterator>
1471 ::value_type*, _Compare, _DifferenceTp>,
1472 static_cast<_DifferenceType>(__length), __comp,
1473 __tag.__get_num_threads());
1474 else
1475 return __sequential_multiway_merge
1476 </* __stable = */ false, /* __sentinels = */ false>
1477 (__seqs_begin, __seqs_end, __target,
1478 *(__seqs_begin->second), __length, __comp);
1479 }
1480
1481 // public interface
1482 template<typename _RAIterPairIterator,
1483 typename _RAIterOut,
1484 typename _DifferenceTp,
1485 typename _Compare>
1486 _RAIterOut
1487 multiway_merge(_RAIterPairIterator __seqs_begin,
1488 _RAIterPairIterator __seqs_end,
1489 _RAIterOut __target,
1490 _DifferenceTp __length, _Compare __comp,
1491 __gnu_parallel::sampling_tag __tag)
1492 {
1493 typedef _DifferenceTp _DifferenceType;
1494 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1495
1496 // catch special case: no sequences
1497 if (__seqs_begin == __seqs_end)
1498 return __target;
1499
1500 // Execute merge; maybe parallel, depending on the number of merged
1501 // elements and the number of sequences and global thresholds in
1502 // Settings.
1503 if ((__seqs_end - __seqs_begin > 1)
1504 && _GLIBCXX_PARALLEL_CONDITION(
1505 ((__seqs_end - __seqs_begin) >=
1506 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1507 && ((_SequenceIndex)__length >=
1508 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1509 return parallel_multiway_merge
1510 </* __stable = */ false, /* __sentinels = */ false>
1511 (__seqs_begin, __seqs_end, __target,
1512 multiway_merge_exact_splitting</* __stable = */ false,
1513 typename std::iterator_traits<_RAIterPairIterator>
1514 ::value_type*, _Compare, _DifferenceTp>,
1515 static_cast<_DifferenceType>(__length), __comp,
1516 __tag.__get_num_threads());
1517 else
1518 return __sequential_multiway_merge
1519 </* __stable = */ false, /* __sentinels = */ false>
1520 (__seqs_begin, __seqs_end, __target,
1521 *(__seqs_begin->second), __length, __comp);
1522 }
1523
1524 // public interface
1525 template<typename _RAIterPairIterator,
1526 typename _RAIterOut,
1527 typename _DifferenceTp,
1528 typename _Compare>
1529 _RAIterOut
1530 multiway_merge(_RAIterPairIterator __seqs_begin,
1531 _RAIterPairIterator __seqs_end,
1532 _RAIterOut __target,
1533 _DifferenceTp __length, _Compare __comp,
1534 parallel_tag __tag = parallel_tag(0))
1535 { return multiway_merge(__seqs_begin, __seqs_end, __target, __length,
1536 __comp, exact_tag(__tag.__get_num_threads())); }
1537
1538 // public interface
1539 template<typename _RAIterPairIterator,
1540 typename _RAIterOut,
1541 typename _DifferenceTp,
1542 typename _Compare>
1543 _RAIterOut
1544 multiway_merge(_RAIterPairIterator __seqs_begin,
1545 _RAIterPairIterator __seqs_end,
1546 _RAIterOut __target,
1547 _DifferenceTp __length, _Compare __comp,
1548 default_parallel_tag __tag)
1549 { return multiway_merge(__seqs_begin, __seqs_end, __target, __length,
1550 __comp, exact_tag(__tag.__get_num_threads())); }
1551
1552 // stable_multiway_merge
1553 // public interface
1554 template<typename _RAIterPairIterator,
1555 typename _RAIterOut,
1556 typename _DifferenceTp,
1557 typename _Compare>
1558 _RAIterOut
1559 stable_multiway_merge(_RAIterPairIterator __seqs_begin,
1560 _RAIterPairIterator __seqs_end,
1561 _RAIterOut __target,
1562 _DifferenceTp __length, _Compare __comp,
1563 __gnu_parallel::sequential_tag)
1564 {
1565 typedef _DifferenceTp _DifferenceType;
1566 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1567
1568 // catch special case: no sequences
1569 if (__seqs_begin == __seqs_end)
1570 return __target;
1571
1572 // Execute multiway merge *sequentially*.
1573 return __sequential_multiway_merge
1574 </* __stable = */ true, /* __sentinels = */ false>
1575 (__seqs_begin, __seqs_end, __target,
1576 *(__seqs_begin->second), __length, __comp);
1577 }
1578
1579 // public interface
1580 template<typename _RAIterPairIterator,
1581 typename _RAIterOut,
1582 typename _DifferenceTp,
1583 typename _Compare>
1584 _RAIterOut
1585 stable_multiway_merge(_RAIterPairIterator __seqs_begin,
1586 _RAIterPairIterator __seqs_end,
1587 _RAIterOut __target,
1588 _DifferenceTp __length, _Compare __comp,
1589 __gnu_parallel::exact_tag __tag)
1590 {
1591 typedef _DifferenceTp _DifferenceType;
1592 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1593
1594 // catch special case: no sequences
1595 if (__seqs_begin == __seqs_end)
1596 return __target;
1597
1598 // Execute merge; maybe parallel, depending on the number of merged
1599 // elements and the number of sequences and global thresholds in
1600 // Settings.
1601 if ((__seqs_end - __seqs_begin > 1)
1602 && _GLIBCXX_PARALLEL_CONDITION(
1603 ((__seqs_end - __seqs_begin) >=
1604 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1605 && ((_SequenceIndex)__length >=
1606 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1607 return parallel_multiway_merge
1608 </* __stable = */ true, /* __sentinels = */ false>
1609 (__seqs_begin, __seqs_end, __target,
1610 multiway_merge_exact_splitting</* __stable = */ true,
1611 typename std::iterator_traits<_RAIterPairIterator>
1612 ::value_type*, _Compare, _DifferenceTp>,
1613 static_cast<_DifferenceType>(__length), __comp,
1614 __tag.__get_num_threads());
1615 else
1616 return __sequential_multiway_merge
1617 </* __stable = */ true, /* __sentinels = */ false>
1618 (__seqs_begin, __seqs_end, __target,
1619 *(__seqs_begin->second), __length, __comp);
1620 }
1621
1622 // public interface
1623 template<typename _RAIterPairIterator,
1624 typename _RAIterOut,
1625 typename _DifferenceTp,
1626 typename _Compare>
1627 _RAIterOut
1628 stable_multiway_merge(_RAIterPairIterator __seqs_begin,
1629 _RAIterPairIterator __seqs_end,
1630 _RAIterOut __target,
1631 _DifferenceTp __length, _Compare __comp,
1632 sampling_tag __tag)
1633 {
1634 typedef _DifferenceTp _DifferenceType;
1635 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1636
1637 // catch special case: no sequences
1638 if (__seqs_begin == __seqs_end)
1639 return __target;
1640
1641 // Execute merge; maybe parallel, depending on the number of merged
1642 // elements and the number of sequences and global thresholds in
1643 // Settings.
1644 if ((__seqs_end - __seqs_begin > 1)
1645 && _GLIBCXX_PARALLEL_CONDITION(
1646 ((__seqs_end - __seqs_begin) >=
1647 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1648 && ((_SequenceIndex)__length >=
1649 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1650 return parallel_multiway_merge
1651 </* __stable = */ true, /* __sentinels = */ false>
1652 (__seqs_begin, __seqs_end, __target,
1653 multiway_merge_sampling_splitting</* __stable = */ true,
1654 typename std::iterator_traits<_RAIterPairIterator>
1655 ::value_type*, _Compare, _DifferenceTp>,
1656 static_cast<_DifferenceType>(__length), __comp,
1657 __tag.__get_num_threads());
1658 else
1659 return __sequential_multiway_merge
1660 </* __stable = */ true, /* __sentinels = */ false>
1661 (__seqs_begin, __seqs_end, __target,
1662 *(__seqs_begin->second), __length, __comp);
1663 }
1664
1665 // public interface
1666 template<typename _RAIterPairIterator,
1667 typename _RAIterOut,
1668 typename _DifferenceTp,
1669 typename _Compare>
1670 _RAIterOut
1671 stable_multiway_merge(_RAIterPairIterator __seqs_begin,
1672 _RAIterPairIterator __seqs_end,
1673 _RAIterOut __target,
1674 _DifferenceTp __length, _Compare __comp,
1675 parallel_tag __tag = parallel_tag(0))
1676 {
1677 return stable_multiway_merge
1678 (__seqs_begin, __seqs_end, __target, __length, __comp,
1679 exact_tag(__tag.__get_num_threads()));
1680 }
1681
1682 // public interface
1683 template<typename _RAIterPairIterator,
1684 typename _RAIterOut,
1685 typename _DifferenceTp,
1686 typename _Compare>
1687 _RAIterOut
1688 stable_multiway_merge(_RAIterPairIterator __seqs_begin,
1689 _RAIterPairIterator __seqs_end,
1690 _RAIterOut __target,
1691 _DifferenceTp __length, _Compare __comp,
1692 default_parallel_tag __tag)
1693 {
1694 return stable_multiway_merge
1695 (__seqs_begin, __seqs_end, __target, __length, __comp,
1696 exact_tag(__tag.__get_num_threads()));
1697 }
1698
1699 /**
1700 * @brief Multiway Merge Frontend.
1701 *
1702 * Merge the sequences specified by seqs_begin and __seqs_end into
1703 * __target. __seqs_begin and __seqs_end must point to a sequence of
1704 * pairs. These pairs must contain an iterator to the beginning
1705 * of a sequence in their first entry and an iterator the _M_end of
1706 * the same sequence in their second entry.
1707 *
1708 * Ties are broken arbitrarily. See stable_multiway_merge for a variant
1709 * that breaks ties by sequence number but is slower.
1710 *
1711 * The first entries of the pairs (i.e. the begin iterators) will be moved
1712 * forward accordingly.
1713 *
1714 * The output sequence has to provide enough space for all elements
1715 * that are written to it.
1716 *
1717 * This function will merge the input sequences:
1718 *
1719 * - not stable
1720 * - parallel, depending on the input size and Settings
1721 * - using sampling for splitting
1722 * - using sentinels
1723 *
1724 * You have to take care that the element the _M_end iterator points to is
1725 * readable and contains a value that is greater than any other non-sentinel
1726 * value in all sequences.
1727 *
1728 * Example:
1729 *
1730 * <pre>
1731 * int sequences[10][11];
1732 * for (int __i = 0; __i < 10; ++__i)
1733 * for (int __j = 0; __i < 11; ++__j)
1734 * sequences[__i][__j] = __j; // __last one is sentinel!
1735 *
1736 * int __out[33];
1737 * std::vector<std::pair<int*> > seqs;
1738 * for (int __i = 0; __i < 10; ++__i)
1739 * { seqs.push(std::make_pair<int*>(sequences[__i],
1740 * sequences[__i] + 10)) }
1741 *
1742 * multiway_merge(seqs.begin(), seqs.end(), __target, std::less<int>(), 33);
1743 * </pre>
1744 *
1745 * @pre All input sequences must be sorted.
1746 * @pre Target must provide enough space to merge out length elements or
1747 * the number of elements in all sequences, whichever is smaller.
1748 * @pre For each @c __i, @c __seqs_begin[__i].second must be the end
1749 * marker of the sequence, but also reference the one more __sentinel
1750 * element.
1751 *
1752 * @post [__target, return __value) contains merged __elements from the
1753 * input sequences.
1754 * @post return __value - __target = min(__length, number of elements in all
1755 * sequences).
1756 *
1757 * @see stable_multiway_merge_sentinels
1758 *
1759 * @tparam _RAIterPairIterator iterator over sequence
1760 * of pairs of iterators
1761 * @tparam _RAIterOut iterator over target sequence
1762 * @tparam _DifferenceTp difference type for the sequence
1763 * @tparam _Compare strict weak ordering type to compare elements
1764 * in sequences
1765 *
1766 * @param __seqs_begin __begin of sequence __sequence
1767 * @param __seqs_end _M_end of sequence __sequence
1768 * @param __target target sequence to merge to.
1769 * @param __comp strict weak ordering to use for element comparison.
1770 * @param __length Maximum length to merge, possibly larger than the
1771 * number of elements available.
1772 *
1773 * @return _M_end iterator of output sequence
1774 */
1775 // multiway_merge_sentinels
1776 // public interface
1777 template<typename _RAIterPairIterator,
1778 typename _RAIterOut,
1779 typename _DifferenceTp,
1780 typename _Compare>
1781 _RAIterOut
1782 multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1783 _RAIterPairIterator __seqs_end,
1784 _RAIterOut __target,
1785 _DifferenceTp __length, _Compare __comp,
1786 __gnu_parallel::sequential_tag)
1787 {
1788 typedef _DifferenceTp _DifferenceType;
1789 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1790
1791 // catch special case: no sequences
1792 if (__seqs_begin == __seqs_end)
1793 return __target;
1794
1795 // Execute multiway merge *sequentially*.
1796 return __sequential_multiway_merge
1797 </* __stable = */ false, /* __sentinels = */ true>
1798 (__seqs_begin, __seqs_end,
1799 __target, *(__seqs_begin->second), __length, __comp);
1800 }
1801
1802 // public interface
1803 template<typename _RAIterPairIterator,
1804 typename _RAIterOut,
1805 typename _DifferenceTp,
1806 typename _Compare>
1807 _RAIterOut
1808 multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1809 _RAIterPairIterator __seqs_end,
1810 _RAIterOut __target,
1811 _DifferenceTp __length, _Compare __comp,
1812 __gnu_parallel::exact_tag __tag)
1813 {
1814 typedef _DifferenceTp _DifferenceType;
1815 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1816
1817 // catch special case: no sequences
1818 if (__seqs_begin == __seqs_end)
1819 return __target;
1820
1821 // Execute merge; maybe parallel, depending on the number of merged
1822 // elements and the number of sequences and global thresholds in
1823 // Settings.
1824 if ((__seqs_end - __seqs_begin > 1)
1825 && _GLIBCXX_PARALLEL_CONDITION(
1826 ((__seqs_end - __seqs_begin) >=
1827 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1828 && ((_SequenceIndex)__length >=
1829 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1830 return parallel_multiway_merge
1831 </* __stable = */ false, /* __sentinels = */ true>
1832 (__seqs_begin, __seqs_end, __target,
1833 multiway_merge_exact_splitting</* __stable = */ false,
1834 typename std::iterator_traits<_RAIterPairIterator>
1835 ::value_type*, _Compare, _DifferenceTp>,
1836 static_cast<_DifferenceType>(__length), __comp,
1837 __tag.__get_num_threads());
1838 else
1839 return __sequential_multiway_merge
1840 </* __stable = */ false, /* __sentinels = */ true>
1841 (__seqs_begin, __seqs_end, __target,
1842 *(__seqs_begin->second), __length, __comp);
1843 }
1844
1845 // public interface
1846 template<typename _RAIterPairIterator,
1847 typename _RAIterOut,
1848 typename _DifferenceTp,
1849 typename _Compare>
1850 _RAIterOut
1851 multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1852 _RAIterPairIterator __seqs_end,
1853 _RAIterOut __target,
1854 _DifferenceTp __length, _Compare __comp,
1855 sampling_tag __tag)
1856 {
1857 typedef _DifferenceTp _DifferenceType;
1858 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1859
1860 // catch special case: no sequences
1861 if (__seqs_begin == __seqs_end)
1862 return __target;
1863
1864 // Execute merge; maybe parallel, depending on the number of merged
1865 // elements and the number of sequences and global thresholds in
1866 // Settings.
1867 if ((__seqs_end - __seqs_begin > 1)
1868 && _GLIBCXX_PARALLEL_CONDITION(
1869 ((__seqs_end - __seqs_begin) >=
1870 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1871 && ((_SequenceIndex)__length >=
1872 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1873 return parallel_multiway_merge
1874 </* __stable = */ false, /* __sentinels = */ true>
1875 (__seqs_begin, __seqs_end, __target,
1876 multiway_merge_sampling_splitting</* __stable = */ false,
1877 typename std::iterator_traits<_RAIterPairIterator>
1878 ::value_type*, _Compare, _DifferenceTp>,
1879 static_cast<_DifferenceType>(__length), __comp,
1880 __tag.__get_num_threads());
1881 else
1882 return __sequential_multiway_merge
1883 </* __stable = */false, /* __sentinels = */ true>(
1884 __seqs_begin, __seqs_end, __target,
1885 *(__seqs_begin->second), __length, __comp);
1886 }
1887
1888 // public interface
1889 template<typename _RAIterPairIterator,
1890 typename _RAIterOut,
1891 typename _DifferenceTp,
1892 typename _Compare>
1893 _RAIterOut
1894 multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1895 _RAIterPairIterator __seqs_end,
1896 _RAIterOut __target,
1897 _DifferenceTp __length, _Compare __comp,
1898 parallel_tag __tag = parallel_tag(0))
1899 {
1900 return multiway_merge_sentinels
1901 (__seqs_begin, __seqs_end, __target, __length, __comp,
1902 exact_tag(__tag.__get_num_threads()));
1903 }
1904
1905 // public interface
1906 template<typename _RAIterPairIterator,
1907 typename _RAIterOut,
1908 typename _DifferenceTp,
1909 typename _Compare>
1910 _RAIterOut
1911 multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1912 _RAIterPairIterator __seqs_end,
1913 _RAIterOut __target,
1914 _DifferenceTp __length, _Compare __comp,
1915 default_parallel_tag __tag)
1916 {
1917 return multiway_merge_sentinels
1918 (__seqs_begin, __seqs_end, __target, __length, __comp,
1919 exact_tag(__tag.__get_num_threads()));
1920 }
1921
1922 // stable_multiway_merge_sentinels
1923 // public interface
1924 template<typename _RAIterPairIterator,
1925 typename _RAIterOut,
1926 typename _DifferenceTp,
1927 typename _Compare>
1928 _RAIterOut
1929 stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1930 _RAIterPairIterator __seqs_end,
1931 _RAIterOut __target,
1932 _DifferenceTp __length, _Compare __comp,
1933 __gnu_parallel::sequential_tag)
1934 {
1935 typedef _DifferenceTp _DifferenceType;
1936 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1937
1938 // catch special case: no sequences
1939 if (__seqs_begin == __seqs_end)
1940 return __target;
1941
1942 // Execute multiway merge *sequentially*.
1943 return __sequential_multiway_merge
1944 </* __stable = */ true, /* __sentinels = */ true>
1945 (__seqs_begin, __seqs_end, __target,
1946 *(__seqs_begin->second), __length, __comp);
1947 }
1948
1949 // public interface
1950 template<typename _RAIterPairIterator,
1951 typename _RAIterOut,
1952 typename _DifferenceTp,
1953 typename _Compare>
1954 _RAIterOut
1955 stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1956 _RAIterPairIterator __seqs_end,
1957 _RAIterOut __target,
1958 _DifferenceTp __length, _Compare __comp,
1959 __gnu_parallel::exact_tag __tag)
1960 {
1961 typedef _DifferenceTp _DifferenceType;
1962 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1963
1964 // catch special case: no sequences
1965 if (__seqs_begin == __seqs_end)
1966 return __target;
1967
1968 // Execute merge; maybe parallel, depending on the number of merged
1969 // elements and the number of sequences and global thresholds in
1970 // Settings.
1971 if ((__seqs_end - __seqs_begin > 1)
1972 && _GLIBCXX_PARALLEL_CONDITION(
1973 ((__seqs_end - __seqs_begin) >=
1974 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1975 && ((_SequenceIndex)__length >=
1976 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1977 return parallel_multiway_merge
1978 </* __stable = */ true, /* __sentinels = */ true>
1979 (__seqs_begin, __seqs_end, __target,
1980 multiway_merge_exact_splitting</* __stable = */ true,
1981 typename std::iterator_traits<_RAIterPairIterator>
1982 ::value_type*, _Compare, _DifferenceTp>,
1983 static_cast<_DifferenceType>(__length), __comp,
1984 __tag.__get_num_threads());
1985 else
1986 return __sequential_multiway_merge
1987 </* __stable = */ true, /* __sentinels = */ true>
1988 (__seqs_begin, __seqs_end, __target,
1989 *(__seqs_begin->second), __length, __comp);
1990 }
1991
1992 // public interface
1993 template<typename _RAIterPairIterator,
1994 typename _RAIterOut,
1995 typename _DifferenceTp,
1996 typename _Compare>
1997 _RAIterOut
1998 stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1999 _RAIterPairIterator __seqs_end,
2000 _RAIterOut __target,
2001 _DifferenceTp __length,
2002 _Compare __comp,
2003 sampling_tag __tag)
2004 {
2005 typedef _DifferenceTp _DifferenceType;
2006 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
2007
2008 // catch special case: no sequences
2009 if (__seqs_begin == __seqs_end)
2010 return __target;
2011
2012 // Execute merge; maybe parallel, depending on the number of merged
2013 // elements and the number of sequences and global thresholds in
2014 // Settings.
2015 if ((__seqs_end - __seqs_begin > 1)
2016 && _GLIBCXX_PARALLEL_CONDITION(
2017 ((__seqs_end - __seqs_begin) >=
2018 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
2019 && ((_SequenceIndex)__length >=
2020 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
2021 return parallel_multiway_merge
2022 </* __stable = */ true, /* __sentinels = */ true>
2023 (__seqs_begin, __seqs_end, __target,
2024 multiway_merge_sampling_splitting</* __stable = */ true,
2025 typename std::iterator_traits<_RAIterPairIterator>
2026 ::value_type*, _Compare, _DifferenceTp>,
2027 static_cast<_DifferenceType>(__length), __comp,
2028 __tag.__get_num_threads());
2029 else
2030 return __sequential_multiway_merge
2031 </* __stable = */ true, /* __sentinels = */ true>
2032 (__seqs_begin, __seqs_end, __target,
2033 *(__seqs_begin->second), __length, __comp);
2034 }
2035
2036 // public interface
2037 template<typename _RAIterPairIterator,
2038 typename _RAIterOut,
2039 typename _DifferenceTp,
2040 typename _Compare>
2041 _RAIterOut
2042 stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
2043 _RAIterPairIterator __seqs_end,
2044 _RAIterOut __target,
2045 _DifferenceTp __length,
2046 _Compare __comp,
2047 parallel_tag __tag = parallel_tag(0))
2048 {
2049 return stable_multiway_merge_sentinels
2050 (__seqs_begin, __seqs_end, __target, __length, __comp,
2051 exact_tag(__tag.__get_num_threads()));
2052 }
2053
2054 // public interface
2055 template<typename _RAIterPairIterator,
2056 typename _RAIterOut,
2057 typename _DifferenceTp,
2058 typename _Compare>
2059 _RAIterOut
2060 stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
2061 _RAIterPairIterator __seqs_end,
2062 _RAIterOut __target,
2063 _DifferenceTp __length, _Compare __comp,
2064 default_parallel_tag __tag)
2065 {
2066 return stable_multiway_merge_sentinels
2067 (__seqs_begin, __seqs_end, __target, __length, __comp,
2068 exact_tag(__tag.__get_num_threads()));
2069 }
2070}; // namespace __gnu_parallel
2071
2072#endif /* _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H */
Note: See TracBrowser for help on using the repository browser.