libstdc++
multiway_merge.h
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2007-2020 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>
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 
56 namespace __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>
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. */
99  {
100  ++_M_current;
101  return *this;
102  }
103 
104  /** @brief Dereference operator.
105  * @return Referenced element. */
108  { return *_M_current; }
109 
110  /** @brief Convert to wrapped iterator.
111  * @return Wrapped iterator. */
112  operator _RAIter()
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
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
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. */
177  operator*()
178  { return *_M_current; }
179 
180  /** @brief Convert to wrapped iterator.
181  * @return Wrapped iterator. */
182  operator _RAIter()
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<(_UnguardedIterator<_RAIter, _Compare>& __bi1,
191  _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<=(_UnguardedIterator<_RAIter, _Compare>& __bi1,
203  _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 
251  ::value_type::first_type
252  _RAIter1;
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 
369  ::value_type::first_type
370  _RAIter1;
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;
500  ::difference_type _SeqNumber;
502  ::value_type::first_type
503  _RAIter1;
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 
587  ::difference_type _SeqNumber;
589  ::value_type::first_type
590  _RAIter1;
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;
676  ::value_type::first_type
677  _RAIter1;
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>
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>
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>
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>
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  {
849  ::value_type::first_type
850  _RAIter1;
852  _ValueType;
853 
855  typename __gnu_cxx::__conditional_type<
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>
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  {
887  ::value_type::first_type
888  _RAIter1;
890  _ValueType;
891 
893  typename __gnu_cxx::__conditional_type<
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;
932  ::difference_type _SeqNumber;
934  ::value_type::first_type
935  _RAIter1;
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:
978  <__sentinels, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare>()
979  (__seqs_begin, __seqs_end, __target, __length, __comp);
980  break;
981  case 4:
983  <__sentinels, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare>()
984  (__seqs_begin, __seqs_end, __target, __length, __comp);
985  break;
986  default:
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>
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,
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;
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 =
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".
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,
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];
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
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 
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<
1287  for (_ThreadIndex __s = 0; __s < __num_threads; ++__s)
1288  __pieces[__s].resize(__k);
1289 
1290  _DifferenceType __num_samples =
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,
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*.
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,
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)
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)))
1467  </* __stable = */ false, /* __sentinels = */ false>
1468  (__seqs_begin, __seqs_end, __target,
1469  multiway_merge_exact_splitting</* __stable = */ false,
1471  ::value_type*, _Compare, _DifferenceTp>,
1472  static_cast<_DifferenceType>(__length), __comp,
1473  __tag.__get_num_threads());
1474  else
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,
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)
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)))
1510  </* __stable = */ false, /* __sentinels = */ false>
1511  (__seqs_begin, __seqs_end, __target,
1512  multiway_merge_exact_splitting</* __stable = */ false,
1514  ::value_type*, _Compare, _DifferenceTp>,
1515  static_cast<_DifferenceType>(__length), __comp,
1516  __tag.__get_num_threads());
1517  else
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,
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*.
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,
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)
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)))
1608  </* __stable = */ true, /* __sentinels = */ false>
1609  (__seqs_begin, __seqs_end, __target,
1610  multiway_merge_exact_splitting</* __stable = */ true,
1612  ::value_type*, _Compare, _DifferenceTp>,
1613  static_cast<_DifferenceType>(__length), __comp,
1614  __tag.__get_num_threads());
1615  else
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)
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)))
1651  </* __stable = */ true, /* __sentinels = */ false>
1652  (__seqs_begin, __seqs_end, __target,
1653  multiway_merge_sampling_splitting</* __stable = */ true,
1655  ::value_type*, _Compare, _DifferenceTp>,
1656  static_cast<_DifferenceType>(__length), __comp,
1657  __tag.__get_num_threads());
1658  else
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,
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*.
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,
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)
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)))
1831  </* __stable = */ false, /* __sentinels = */ true>
1832  (__seqs_begin, __seqs_end, __target,
1833  multiway_merge_exact_splitting</* __stable = */ false,
1835  ::value_type*, _Compare, _DifferenceTp>,
1836  static_cast<_DifferenceType>(__length), __comp,
1837  __tag.__get_num_threads());
1838  else
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)
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)))
1874  </* __stable = */ false, /* __sentinels = */ true>
1875  (__seqs_begin, __seqs_end, __target,
1876  multiway_merge_sampling_splitting</* __stable = */ false,
1878  ::value_type*, _Compare, _DifferenceTp>,
1879  static_cast<_DifferenceType>(__length), __comp,
1880  __tag.__get_num_threads());
1881  else
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  {
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  {
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,
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*.
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,
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)
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)))
1978  </* __stable = */ true, /* __sentinels = */ true>
1979  (__seqs_begin, __seqs_end, __target,
1980  multiway_merge_exact_splitting</* __stable = */ true,
1982  ::value_type*, _Compare, _DifferenceTp>,
1983  static_cast<_DifferenceType>(__length), __comp,
1984  __tag.__get_num_threads());
1985  else
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)
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)))
2022  </* __stable = */ true, /* __sentinels = */ true>
2023  (__seqs_begin, __seqs_end, __target,
2024  multiway_merge_sampling_splitting</* __stable = */ true,
2026  ::value_type*, _Compare, _DifferenceTp>,
2027  static_cast<_DifferenceType>(__length), __comp,
2028  __tag.__get_num_threads());
2029  else
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 */
Routines for checking the correctness of algorithm results. This file is a GNU parallel extension to ...
#define _GLIBCXX_CALL(__n)
Macro to produce log message when entering a function.
Defines on whether to include algorithm variants.
Many generic loser tree variants. This file is a GNU parallel extension to the Standard C++ Library.
Functions to find elements of a certain global __rank in multiple sorted sequences....
#define _GLIBCXX_PARALLEL_LENGTH(__s)
Length of a sequence described by a pair of iterators.
End-user include file. Provides advanced settings and tuning options. This file is a GNU parallel ext...
#define _GLIBCXX_PARALLEL_CONDITION(__c)
Determine at compile(?)-time if the parallel variant of an algorithm should be called.
Definition: settings.h:94
constexpr complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
Definition: complex:391
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
Definition: valarray:1214
GNU parallel code for public use.
_OutputIterator __merge_advance(_RAIter1 &__begin1, _RAIter1 __end1, _RAIter2 &__begin2, _RAIter2 __end2, _OutputIterator __target, _DifferenceTp __max_length, _Compare __comp)
Merge routine being able to merge only the __max_length smallest elements.
Definition: merge.h:171
uint16_t _ThreadIndex
Unsigned integer to index a thread number. The maximum thread number (for each processor) must fit in...
Definition: types.h:123
void multiway_merge_sampling_splitting(_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _DifferenceType __length, _DifferenceType __total_length, _Compare __comp, std::vector< std::pair< _DifferenceType, _DifferenceType > > *__pieces)
Sampling based splitting for parallel multiway-merge routine.
_RAIter3 parallel_multiway_merge(_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, _Splitter __splitter, _DifferenceTp __length, _Compare __comp, _ThreadIndex __num_threads)
Parallel multi-way merge routine.
_RAIter3 multiway_merge_loser_tree(_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, _DifferenceTp __length, _Compare __comp)
Multi-way merging procedure for a high branching factor, guarded case.
uint64_t _SequenceIndex
Unsigned integer to index __elements. The total number of elements for each algorithm must fit into t...
Definition: types.h:117
_RAIterOut multiway_merge(_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sequential_tag)
Multiway Merge Frontend.
bool __is_sorted(_IIter __begin, _IIter __end, _Compare __comp)
Check whether [__begin, __end) is sorted according to __comp.
Definition: checkers.h:51
_RAIter3 multiway_merge_loser_tree_unguarded(_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, const typename std::iterator_traits< typename std::iterator_traits< _RAIterIterator >::value_type::first_type >::value_type &__sentinel, _DifferenceTp __length, _Compare __comp)
Multi-way merging procedure for a high branching factor, unguarded case.
_RAIterOut multiway_merge_sentinels(_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sequential_tag)
Multiway Merge Frontend.
void multiway_merge_exact_splitting(_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _DifferenceType __length, _DifferenceType __total_length, _Compare __comp, std::vector< std::pair< _DifferenceType, _DifferenceType > > *__pieces)
Exact splitting for parallel multiway-merge routine.
_RAIter3 __sequential_multiway_merge(_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, const typename std::iterator_traits< typename std::iterator_traits< _RAIterIterator >::value_type::first_type >::value_type &__sentinel, _DifferenceTp __length, _Compare __comp)
Sequential multi-way merging switch.
_RAIter3 multiway_merge_loser_tree_sentinel(_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, const typename std::iterator_traits< typename std::iterator_traits< _RAIterIterator >::value_type::first_type >::value_type &__sentinel, _DifferenceTp __length, _Compare __comp)
Multi-way merging procedure for a high branching factor, requiring sentinels to exist.
_RAIter3 multiway_merge_3_variant(_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, _DifferenceTp __length, _Compare __comp)
Highly efficient 3-way merging procedure.
_RAIter3 multiway_merge_4_variant(_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, _DifferenceTp __length, _Compare __comp)
Highly efficient 4-way merging procedure.
_OutputIterator __equally_split(_DifferenceType __n, _ThreadIndex __num_threads, _OutputIterator __s)
function to split a sequence into parts of almost equal size.
Definition: equally_split.h:48
void multiseq_partition(_RanSeqs __begin_seqs, _RanSeqs __end_seqs, _RankType __rank, _RankIterator __begin_offsets, _Compare __comp=std::less< typename std::iterator_traits< typename std::iterator_traits< _RanSeqs >::value_type::first_type >::value_type >())
Splits several sorted sequences at a certain global __rank, resulting in a splitting point for each s...
Traits class for iterators.
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:213
A standard container which offers fixed time access to individual elements in any order.
Definition: stl_vector.h:390
void resize(size_type __new_size)
Resizes the vector to the specified number of elements.
Definition: stl_vector.h:937
iterator begin() noexcept
Definition: stl_vector.h:811
iterator end() noexcept
Definition: stl_vector.h:829
Stable _LoserTree variant.
Definition: losertree.h:171
Stable _LoserTree implementation.
Definition: losertree.h:411
Stable implementation of unguarded _LoserTree.
Definition: losertree.h:648
Stable unguarded _LoserTree variant storing pointers.
Definition: losertree.h:893
_Iterator wrapper supporting an implicit supremum at the end of the sequence, dominating all comparis...
friend bool operator<(_GuardedIterator< _RAIter, _Compare > &__bi1, _GuardedIterator< _RAIter, _Compare > &__bi2)
Compare two elements referenced by guarded iterators.
friend bool operator<=(_GuardedIterator< _RAIter, _Compare > &__bi1, _GuardedIterator< _RAIter, _Compare > &__bi2)
Compare two elements referenced by guarded iterators.
std::iterator_traits< _RAIter >::value_type & operator*()
Dereference operator.
_GuardedIterator< _RAIter, _Compare > & operator++()
Pre-increment operator.
_GuardedIterator(_RAIter __begin, _RAIter __end, _Compare &__comp)
Constructor. Sets iterator to beginning of sequence.
Traits for determining whether the loser tree should use pointers or copies.
static const bool _M_use_pointer
True iff to use pointers instead of values in loser trees.
Switch for 3-way merging with __sentinels turned off.
Switch for 4-way merging with __sentinels turned off.
Switch for k-way merging with __sentinels turned on.
Stable sorting functor.
unsigned int merge_oversampling
Oversampling factor for merge.
Definition: settings.h:174
static const _Settings & get()
Get the global settings.
Forces sequential execution at compile time.
Definition: tags.h:42
_ThreadIndex __get_num_threads()
Find out desired number of threads.
Definition: tags.h:63
Forces parallel merging with exact splitting, at compile time.
Definition: tags.h:110
Forces parallel merging with exact splitting, at compile time.
Definition: tags.h:119