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