OpenCores
URL https://opencores.org/ocsvn/altor32/altor32/trunk

Subversion Repositories altor32

[/] [altor32/] [trunk/] [gcc-x64/] [or1knd-elf/] [or1knd-elf/] [include/] [c++/] [4.8.0/] [parallel/] [multiway_merge.h] - Blame information for rev 35

Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.