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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [libstdc++-v3/] [include/] [parallel/] [multiway_merge.h] - Blame information for rev 826

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 424 jeremybenn 
// -*- 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 
      mutable _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 = NULL;
506 
 
507 
      for (_SeqNumber __t = 0; __t < __k; ++__t)
508 
        {
509 
          if(__arbitrary_element == NULL
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 
      _SeqNumber __k = static_cast<_SeqNumber>(__seqs_end - __seqs_begin);
1049 
 
1050 
      _ThreadIndex __num_threads = omp_get_num_threads();
1051 
 
1052 
      _DifferenceType __num_samples =
1053 
        __gnu_parallel::_Settings::get().merge_oversampling * __num_threads;
1054 
 
1055 
      _ValueType* __samples = static_cast<_ValueType*>
1056 
        (::operator new(sizeof(_ValueType) * __k * __num_samples));
1057 
      // Sample.
1058 
      for (_SeqNumber __s = 0; __s < __k; ++__s)
1059 
        for (_DifferenceType __i = 0; __i < __num_samples; ++__i)
1060 
          {
1061 
            _DifferenceType sample_index = static_cast<_DifferenceType>
1062 
              (_GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__s])
1063 
               * (double(__i + 1) / (__num_samples + 1))
1064 
               * (double(__length) / __total_length));
1065 
            new(&(__samples[__s * __num_samples + __i]))
1066 
              _ValueType(__seqs_begin[__s].first[sample_index]);
1067 
          }
1068 
 
1069 
      // Sort stable or non-stable, depending on value of template parameter
1070 
      // "__stable".
1071 
      _SamplingSorter<__stable, _ValueType*, _Compare>()
1072 
        (__samples, __samples + (__num_samples * __k), __comp);
1073 
 
1074 
      for (_ThreadIndex __slab = 0; __slab < __num_threads; ++__slab)
1075 
        // For each slab / processor.
1076 
        for (_SeqNumber __seq = 0; __seq < __k; ++__seq)
1077 
          {
1078 
            // For each sequence.
1079 
            if (__slab > 0)
1080 
              __pieces[__slab][__seq].first = std::upper_bound
1081 
                (__seqs_begin[__seq].first, __seqs_begin[__seq].second,
1082 
                 __samples[__num_samples * __k * __slab / __num_threads],
1083 
                 __comp)
1084 
                - __seqs_begin[__seq].first;
1085 
            else
1086 
              // Absolute beginning.
1087 
              __pieces[__slab][__seq].first = 0;
1088 
            if ((__slab + 1) < __num_threads)
1089 
              __pieces[__slab][__seq].second = std::upper_bound
1090 
                (__seqs_begin[__seq].first, __seqs_begin[__seq].second,
1091 
                 __samples[__num_samples * __k * (__slab + 1) / __num_threads],
1092 
                 __comp)
1093 
                - __seqs_begin[__seq].first;
1094 
            else
1095 
              // Absolute end.
1096 
              __pieces[__slab][__seq].second =
1097 
                _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__seq]);
1098 
          }
1099 
      ::operator delete(__samples);
1100 
    }
1101 
 
1102 
  /**
1103 
   * @brief Exact splitting for parallel multiway-merge routine.
1104 
   *
1105 
   * None of the passed sequences may be empty.
1106 
   */
1107 
  template<bool __stable,
1108 
           typename _RAIterIterator,
1109 
           typename _Compare,
1110 
           typename _DifferenceType>
1111 
    void
1112 
    multiway_merge_exact_splitting(_RAIterIterator __seqs_begin,
1113 
                                   _RAIterIterator __seqs_end,
1114 
                                   _DifferenceType __length,
1115 
                                   _DifferenceType __total_length,
1116 
                                   _Compare __comp,
1117 
       std::vector<std::pair<_DifferenceType, _DifferenceType> > *__pieces)
1118 
    {
1119 
      typedef typename std::iterator_traits<_RAIterIterator>
1120 
        ::difference_type _SeqNumber;
1121 
      typedef typename std::iterator_traits<_RAIterIterator>
1122 
        ::value_type::first_type
1123 
        _RAIter1;
1124 
 
1125 
      const bool __tight = (__total_length == __length);
1126 
 
1127 
      // __k sequences.
1128 
      const _SeqNumber __k = __seqs_end - __seqs_begin;
1129 
 
1130 
      const _ThreadIndex __num_threads = omp_get_num_threads();
1131 
 
1132 
      // (Settings::multiway_merge_splitting
1133 
      //  == __gnu_parallel::_Settings::EXACT).
1134 
      std::vector<_RAIter1>* __offsets =
1135 
        new std::vector<_RAIter1>[__num_threads];
1136 
      std::vector<std::pair<_RAIter1, _RAIter1> > __se(__k);
1137 
 
1138 
      copy(__seqs_begin, __seqs_end, __se.begin());
1139 
 
1140 
      _DifferenceType* __borders =
1141 
        new _DifferenceType[__num_threads + 1];
1142 
      equally_split(__length, __num_threads, __borders);
1143 
 
1144 
      for (_ThreadIndex __s = 0; __s < (__num_threads - 1); ++__s)
1145 
        {
1146 
          __offsets[__s].resize(__k);
1147 
          multiseq_partition(__se.begin(), __se.end(), __borders[__s + 1],
1148 
                             __offsets[__s].begin(), __comp);
1149 
 
1150 
          // Last one also needed and available.
1151 
          if (!__tight)
1152 
            {
1153 
              __offsets[__num_threads - 1].resize(__k);
1154 
              multiseq_partition(__se.begin(), __se.end(),
1155 
                                 _DifferenceType(__length),
1156 
                                 __offsets[__num_threads - 1].begin(),
1157 
                                 __comp);
1158 
            }
1159 
        }
1160 
      delete[] __borders;
1161 
 
1162 
      for (_ThreadIndex __slab = 0; __slab < __num_threads; ++__slab)
1163 
        {
1164 
          // For each slab / processor.
1165 
          for (_SeqNumber __seq = 0; __seq < __k; ++__seq)
1166 
            {
1167 
              // For each sequence.
1168 
              if (__slab == 0)
1169 
                {
1170 
                  // Absolute beginning.
1171 
                  __pieces[__slab][__seq].first = 0;
1172 
                }
1173 
              else
1174 
                __pieces[__slab][__seq].first =
1175 
                  __pieces[__slab - 1][__seq].second;
1176 
              if (!__tight || __slab < (__num_threads - 1))
1177 
                __pieces[__slab][__seq].second =
1178 
                  __offsets[__slab][__seq] - __seqs_begin[__seq].first;
1179 
              else
1180 
                {
1181 
                  // __slab == __num_threads - 1
1182 
                  __pieces[__slab][__seq].second =
1183 
                    _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__seq]);
1184 
                }
1185 
            }
1186 
        }
1187 
      delete[] __offsets;
1188 
    }
1189 
 
1190 
  /** @brief Parallel multi-way merge routine.
1191 
   *
1192 
   * The _GLIBCXX_PARALLEL_DECISION is based on the branching factor
1193 
   * and runtime settings.
1194 
   *
1195 
   * Must not be called if the number of sequences is 1.
1196 
   *
1197 
   * @param _Splitter functor to split input (either __exact or sampling based)
1198 
   *
1199 
   * @param __seqs_begin Begin iterator of iterator pair input sequence.
1200 
   * @param __seqs_end End iterator of iterator pair input sequence.
1201 
   * @param __target Begin iterator of output sequence.
1202 
   * @param __comp Comparator.
1203 
   * @param __length Maximum length to merge, possibly larger than the
1204 
   * number of elements available.
1205 
   * @param __stable Stable merging incurs a performance penalty.
1206 
   * @param __sentinel Ignored.
1207 
   * @return End iterator of output sequence.
1208 
   */
1209 
  template<bool __stable,
1210 
           bool __sentinels,
1211 
           typename _RAIterIterator,
1212 
           typename _RAIter3,
1213 
           typename _DifferenceTp,
1214 
           typename _Splitter,
1215 
           typename _Compare>
1216 
    _RAIter3
1217 
    parallel_multiway_merge(_RAIterIterator __seqs_begin,
1218 
                            _RAIterIterator __seqs_end,
1219 
                            _RAIter3 __target,
1220 
                            _Splitter __splitter,
1221 
                            _DifferenceTp __length,
1222 
                            _Compare __comp,
1223 
                            _ThreadIndex __num_threads)
1224 
      {
1225 
#if _GLIBCXX_ASSERTIONS
1226 
        _GLIBCXX_PARALLEL_ASSERT(__seqs_end - __seqs_begin > 1);
1227 
#endif
1228 
 
1229 
        _GLIBCXX_CALL(__length)
1230 
 
1231 
        typedef _DifferenceTp _DifferenceType;
1232 
        typedef typename std::iterator_traits<_RAIterIterator>
1233 
          ::difference_type _SeqNumber;
1234 
        typedef typename std::iterator_traits<_RAIterIterator>
1235 
          ::value_type::first_type
1236 
          _RAIter1;
1237 
        typedef typename
1238 
          std::iterator_traits<_RAIter1>::value_type _ValueType;
1239 
 
1240 
        // Leave only non-empty sequences.
1241 
        typedef std::pair<_RAIter1, _RAIter1> seq_type;
1242 
        seq_type* __ne_seqs = new seq_type[__seqs_end - __seqs_begin];
1243 
        _SeqNumber __k = 0;
1244 
        _DifferenceType __total_length = 0;
1245 
        for (_RAIterIterator __raii = __seqs_begin;
1246 
             __raii != __seqs_end; ++__raii)
1247 
          {
1248 
            _DifferenceTp __seq_length = _GLIBCXX_PARALLEL_LENGTH(*__raii);
1249 
            if(__seq_length > 0)
1250 
              {
1251 
                __total_length += __seq_length;
1252 
                __ne_seqs[__k++] = *__raii;
1253 
              }
1254 
          }
1255 
 
1256 
        _GLIBCXX_CALL(__total_length)
1257 
 
1258 
        __length = std::min<_DifferenceTp>(__length, __total_length);
1259 
 
1260 
        if (__total_length == 0 || __k == 0)
1261 
        {
1262 
          delete[] __ne_seqs;
1263 
          return __target;
1264 
        }
1265 
 
1266 
        std::vector<std::pair<_DifferenceType, _DifferenceType> >* __pieces;
1267 
 
1268 
        __num_threads = static_cast<_ThreadIndex>
1269 
          (std::min<_DifferenceType>(__num_threads, __total_length));
1270 
 
1271 
#       pragma omp parallel num_threads (__num_threads)
1272 
        {
1273 
#         pragma omp single
1274 
          {
1275 
            __num_threads = omp_get_num_threads();
1276 
            // Thread __t will have to merge pieces[__iam][0..__k - 1]
1277 
            __pieces = new std::vector<
1278 
            std::pair<_DifferenceType, _DifferenceType> >[__num_threads];
1279 
            for (_ThreadIndex __s = 0; __s < __num_threads; ++__s)
1280 
              __pieces[__s].resize(__k);
1281 
 
1282 
            _DifferenceType __num_samples =
1283 
              __gnu_parallel::_Settings::get().merge_oversampling
1284 
              * __num_threads;
1285 
 
1286 
            __splitter(__ne_seqs, __ne_seqs + __k, __length, __total_length,
1287 
                       __comp, __pieces);
1288 
          } //single
1289 
 
1290 
          _ThreadIndex __iam = omp_get_thread_num();
1291 
 
1292 
          _DifferenceType __target_position = 0;
1293 
 
1294 
          for (_SeqNumber __c = 0; __c < __k; ++__c)
1295 
            __target_position += __pieces[__iam][__c].first;
1296 
 
1297 
          seq_type* __chunks = new seq_type[__k];
1298 
 
1299 
          for (_SeqNumber __s = 0; __s < __k; ++__s)
1300 
            __chunks[__s] = std::make_pair(__ne_seqs[__s].first
1301 
                                           + __pieces[__iam][__s].first,
1302 
                                           __ne_seqs[__s].first
1303 
                                           + __pieces[__iam][__s].second);
1304 
 
1305 
          if(__length > __target_position)
1306 
            __sequential_multiway_merge<__stable, __sentinels>
1307 
              (__chunks, __chunks + __k, __target + __target_position,
1308 
               *(__seqs_begin->second), __length - __target_position, __comp);
1309 
 
1310 
          delete[] __chunks;
1311 
        } // parallel
1312 
 
1313 
#if _GLIBCXX_ASSERTIONS
1314 
        _GLIBCXX_PARALLEL_ASSERT(
1315 
          __is_sorted(__target, __target + __length, __comp));
1316 
#endif
1317 
 
1318 
        __k = 0;
1319 
        // Update ends of sequences.
1320 
        for (_RAIterIterator __raii = __seqs_begin;
1321 
             __raii != __seqs_end; ++__raii)
1322 
          {
1323 
            _DifferenceTp __length = _GLIBCXX_PARALLEL_LENGTH(*__raii);
1324 
            if(__length > 0)
1325 
              (*__raii).first += __pieces[__num_threads - 1][__k++].second;
1326 
          }
1327 
 
1328 
        delete[] __pieces;
1329 
        delete[] __ne_seqs;
1330 
 
1331 
        return __target + __length;
1332 
      }
1333 
 
1334 
  /**
1335 
   * @brief Multiway Merge Frontend.
1336 
   *
1337 
   * Merge the sequences specified by seqs_begin and __seqs_end into
1338 
   * __target.  __seqs_begin and __seqs_end must point to a sequence of
1339 
   * pairs.  These pairs must contain an iterator to the beginning
1340 
   * of a sequence in their first entry and an iterator the _M_end of
1341 
   * the same sequence in their second entry.
1342 
   *
1343 
   * Ties are broken arbitrarily.  See stable_multiway_merge for a variant
1344 
   * that breaks ties by sequence number but is slower.
1345 
   *
1346 
   * The first entries of the pairs (i.e. the begin iterators) will be moved
1347 
   * forward.
1348 
   *
1349 
   * The output sequence has to provide enough space for all elements
1350 
   * that are written to it.
1351 
   *
1352 
   * This function will merge the input sequences:
1353 
   *
1354 
   * - not stable
1355 
   * - parallel, depending on the input size and Settings
1356 
   * - using sampling for splitting
1357 
   * - not using sentinels
1358 
   *
1359 
   * Example:
1360 
   *
1361 
   * <pre>
1362 
   *   int sequences[10][10];
1363 
   *   for (int __i = 0; __i < 10; ++__i)
1364 
   *     for (int __j = 0; __i < 10; ++__j)
1365 
   *       sequences[__i][__j] = __j;
1366 
   *
1367 
   *   int __out[33];
1368 
   *   std::vector<std::pair<int*> > seqs;
1369 
   *   for (int __i = 0; __i < 10; ++__i)
1370 
   *     { seqs.push(std::make_pair<int*>(sequences[__i],
1371 
   *                                      sequences[__i] + 10)) }
1372 
   *
1373 
   *   multiway_merge(seqs.begin(), seqs.end(), __target, std::less<int>(), 33);
1374 
   * </pre>
1375 
   *
1376 
   * @see stable_multiway_merge
1377 
   *
1378 
   * @pre All input sequences must be sorted.
1379 
   * @pre Target must provide enough space to merge out length elements or
1380 
   *    the number of elements in all sequences, whichever is smaller.
1381 
   *
1382 
   * @post [__target, return __value) contains merged __elements from the
1383 
   *    input sequences.
1384 
   * @post return __value - __target = min(__length, number of elements in all
1385 
   *    sequences).
1386 
   *
1387 
   * @param _RAIterPairIterator iterator over sequence
1388 
   *    of pairs of iterators
1389 
   * @param _RAIterOut iterator over target sequence
1390 
   * @param _DifferenceTp difference type for the sequence
1391 
   * @param _Compare strict weak ordering type to compare elements
1392 
   *    in sequences
1393 
   *
1394 
   * @param __seqs_begin  __begin of sequence __sequence
1395 
   * @param __seqs_end    _M_end of sequence __sequence
1396 
   * @param __target      target sequence to merge to.
1397 
   * @param __comp        strict weak ordering to use for element comparison.
1398 
   * @param __length Maximum length to merge, possibly larger than the
1399 
   * number of elements available.
1400 
   *
1401 
   * @return _M_end iterator of output sequence
1402 
   */
1403 
  // multiway_merge
1404 
  // public interface
1405 
  template<typename _RAIterPairIterator,
1406 
           typename _RAIterOut,
1407 
           typename _DifferenceTp,
1408 
           typename _Compare>
1409 
    _RAIterOut
1410 
    multiway_merge(_RAIterPairIterator __seqs_begin,
1411 
                   _RAIterPairIterator __seqs_end,
1412 
                   _RAIterOut __target,
1413 
                   _DifferenceTp __length, _Compare __comp,
1414 
                   __gnu_parallel::sequential_tag)
1415 
    {
1416 
      typedef _DifferenceTp _DifferenceType;
1417 
      _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1418 
 
1419 
      // catch special case: no sequences
1420 
      if (__seqs_begin == __seqs_end)
1421 
        return __target;
1422 
 
1423 
      // Execute multiway merge *sequentially*.
1424 
      return __sequential_multiway_merge
1425 
        </* __stable = */ false, /* __sentinels = */ false>
1426 
        (__seqs_begin, __seqs_end, __target,
1427 
         *(__seqs_begin->second), __length, __comp);
1428 
    }
1429 
 
1430 
  // public interface
1431 
  template<typename _RAIterPairIterator,
1432 
           typename _RAIterOut,
1433 
           typename _DifferenceTp,
1434 
           typename _Compare>
1435 
    _RAIterOut
1436 
    multiway_merge(_RAIterPairIterator __seqs_begin,
1437 
                   _RAIterPairIterator __seqs_end,
1438 
                   _RAIterOut __target,
1439 
                   _DifferenceTp __length, _Compare __comp,
1440 
                   __gnu_parallel::exact_tag __tag)
1441 
    {
1442 
      typedef _DifferenceTp _DifferenceType;
1443 
      _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1444 
 
1445 
      // catch special case: no sequences
1446 
      if (__seqs_begin == __seqs_end)
1447 
        return __target;
1448 
 
1449 
      // Execute merge; maybe parallel, depending on the number of merged
1450 
      // elements and the number of sequences and global thresholds in
1451 
      // Settings.
1452 
      if ((__seqs_end - __seqs_begin > 1)
1453 
          && _GLIBCXX_PARALLEL_CONDITION(
1454 
            ((__seqs_end - __seqs_begin) >=
1455 
               __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1456 
            && ((_SequenceIndex)__length >=
1457 
              __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1458 
        return parallel_multiway_merge
1459 
          </* __stable = */ false, /* __sentinels = */ false>
1460 
          (__seqs_begin, __seqs_end, __target,
1461 
           multiway_merge_exact_splitting</* __stable = */ false,
1462 
           typename std::iterator_traits<_RAIterPairIterator>
1463 
           ::value_type*, _Compare, _DifferenceTp>,
1464 
           static_cast<_DifferenceType>(__length), __comp,
1465 
           __tag.__get_num_threads());
1466 
      else
1467 
        return __sequential_multiway_merge
1468 
          </* __stable = */ false, /* __sentinels = */ false>
1469 
          (__seqs_begin, __seqs_end, __target,
1470 
           *(__seqs_begin->second), __length, __comp);
1471 
    }
1472 
 
1473 
  // public interface
1474 
  template<typename _RAIterPairIterator,
1475 
           typename _RAIterOut,
1476 
           typename _DifferenceTp,
1477 
           typename _Compare>
1478 
    _RAIterOut
1479 
    multiway_merge(_RAIterPairIterator __seqs_begin,
1480 
                   _RAIterPairIterator __seqs_end,
1481 
                   _RAIterOut __target,
1482 
                   _DifferenceTp __length, _Compare __comp,
1483 
                   __gnu_parallel::sampling_tag __tag)
1484 
    {
1485 
      typedef _DifferenceTp _DifferenceType;
1486 
      _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1487 
 
1488 
      // catch special case: no sequences
1489 
      if (__seqs_begin == __seqs_end)
1490 
        return __target;
1491 
 
1492 
      // Execute merge; maybe parallel, depending on the number of merged
1493 
      // elements and the number of sequences and global thresholds in
1494 
      // Settings.
1495 
      if ((__seqs_end - __seqs_begin > 1)
1496 
          && _GLIBCXX_PARALLEL_CONDITION(
1497 
            ((__seqs_end - __seqs_begin) >=
1498 
               __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1499 
            && ((_SequenceIndex)__length >=
1500 
              __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1501 
        return parallel_multiway_merge
1502 
          </* __stable = */ false, /* __sentinels = */ false>
1503 
          (__seqs_begin, __seqs_end, __target,
1504 
           multiway_merge_exact_splitting</* __stable = */ false,
1505 
           typename std::iterator_traits<_RAIterPairIterator>
1506 
           ::value_type*, _Compare, _DifferenceTp>,
1507 
           static_cast<_DifferenceType>(__length), __comp,
1508 
           __tag.__get_num_threads());
1509 
      else
1510 
        return __sequential_multiway_merge
1511 
          </* __stable = */ false, /* __sentinels = */ false>
1512 
          (__seqs_begin, __seqs_end, __target,
1513 
           *(__seqs_begin->second), __length, __comp);
1514 
    }
1515 
 
1516 
  // public interface
1517 
  template<typename _RAIterPairIterator,
1518 
           typename _RAIterOut,
1519 
           typename _DifferenceTp,
1520 
           typename _Compare>
1521 
    _RAIterOut
1522 
    multiway_merge(_RAIterPairIterator __seqs_begin,
1523 
                   _RAIterPairIterator __seqs_end,
1524 
                   _RAIterOut __target,
1525 
                   _DifferenceTp __length, _Compare __comp,
1526 
                   parallel_tag __tag = parallel_tag(0))
1527 
    { return multiway_merge(__seqs_begin, __seqs_end, __target, __length,
1528 
                            __comp, exact_tag(__tag.__get_num_threads())); }
1529 
 
1530 
  // public interface
1531 
  template<typename _RAIterPairIterator,
1532 
           typename _RAIterOut,
1533 
           typename _DifferenceTp,
1534 
           typename _Compare>
1535 
    _RAIterOut
1536 
    multiway_merge(_RAIterPairIterator __seqs_begin,
1537 
                   _RAIterPairIterator __seqs_end,
1538 
                   _RAIterOut __target,
1539 
                   _DifferenceTp __length, _Compare __comp,
1540 
                   default_parallel_tag __tag)
1541 
    { return multiway_merge(__seqs_begin, __seqs_end, __target, __length,
1542 
                            __comp, exact_tag(__tag.__get_num_threads())); }
1543 
 
1544 
  // stable_multiway_merge
1545 
  // public interface
1546 
  template<typename _RAIterPairIterator,
1547 
           typename _RAIterOut,
1548 
           typename _DifferenceTp,
1549 
           typename _Compare>
1550 
    _RAIterOut
1551 
    stable_multiway_merge(_RAIterPairIterator __seqs_begin,
1552 
                          _RAIterPairIterator __seqs_end,
1553 
                          _RAIterOut __target,
1554 
                          _DifferenceTp __length, _Compare __comp,
1555 
                          __gnu_parallel::sequential_tag)
1556 
    {
1557 
      typedef _DifferenceTp _DifferenceType;
1558 
      _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1559 
 
1560 
      // catch special case: no sequences
1561 
      if (__seqs_begin == __seqs_end)
1562 
        return __target;
1563 
 
1564 
      // Execute multiway merge *sequentially*.
1565 
      return __sequential_multiway_merge
1566 
        </* __stable = */ true, /* __sentinels = */ false>
1567 
          (__seqs_begin, __seqs_end, __target,
1568 
           *(__seqs_begin->second), __length, __comp);
1569 
    }
1570 
 
1571 
  // public interface
1572 
  template<typename _RAIterPairIterator,
1573 
           typename _RAIterOut,
1574 
           typename _DifferenceTp,
1575 
           typename _Compare>
1576 
    _RAIterOut
1577 
    stable_multiway_merge(_RAIterPairIterator __seqs_begin,
1578 
                          _RAIterPairIterator __seqs_end,
1579 
                          _RAIterOut __target,
1580 
                          _DifferenceTp __length, _Compare __comp,
1581 
                          __gnu_parallel::exact_tag __tag)
1582 
    {
1583 
      typedef _DifferenceTp _DifferenceType;
1584 
      _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1585 
 
1586 
      // catch special case: no sequences
1587 
      if (__seqs_begin == __seqs_end)
1588 
        return __target;
1589 
 
1590 
      // Execute merge; maybe parallel, depending on the number of merged
1591 
      // elements and the number of sequences and global thresholds in
1592 
      // Settings.
1593 
      if ((__seqs_end - __seqs_begin > 1)
1594 
          && _GLIBCXX_PARALLEL_CONDITION(
1595 
            ((__seqs_end - __seqs_begin) >=
1596 
              __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1597 
            && ((_SequenceIndex)__length >=
1598 
              __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1599 
        return parallel_multiway_merge
1600 
          </* __stable = */ true, /* __sentinels = */ false>
1601 
          (__seqs_begin, __seqs_end, __target,
1602 
           multiway_merge_exact_splitting</* __stable = */ true,
1603 
           typename std::iterator_traits<_RAIterPairIterator>
1604 
           ::value_type*, _Compare, _DifferenceTp>,
1605 
           static_cast<_DifferenceType>(__length), __comp,
1606 
           __tag.__get_num_threads());
1607 
      else
1608 
        return __sequential_multiway_merge
1609 
          </* __stable = */ true, /* __sentinels = */ false>
1610 
          (__seqs_begin, __seqs_end, __target,
1611 
           *(__seqs_begin->second), __length, __comp);
1612 
    }
1613 
 
1614 
  // public interface
1615 
  template<typename _RAIterPairIterator,
1616 
           typename _RAIterOut,
1617 
           typename _DifferenceTp,
1618 
           typename _Compare>
1619 
    _RAIterOut
1620 
    stable_multiway_merge(_RAIterPairIterator __seqs_begin,
1621 
                          _RAIterPairIterator __seqs_end,
1622 
                          _RAIterOut __target,
1623 
                          _DifferenceTp __length, _Compare __comp,
1624 
                          sampling_tag __tag)
1625 
    {
1626 
      typedef _DifferenceTp _DifferenceType;
1627 
      _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1628 
 
1629 
      // catch special case: no sequences
1630 
      if (__seqs_begin == __seqs_end)
1631 
        return __target;
1632 
 
1633 
      // Execute merge; maybe parallel, depending on the number of merged
1634 
      // elements and the number of sequences and global thresholds in
1635 
      // Settings.
1636 
      if ((__seqs_end - __seqs_begin > 1)
1637 
          && _GLIBCXX_PARALLEL_CONDITION(
1638 
            ((__seqs_end - __seqs_begin) >=
1639 
              __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1640 
            && ((_SequenceIndex)__length >=
1641 
              __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1642 
        return parallel_multiway_merge
1643 
          </* __stable = */ true, /* __sentinels = */ false>
1644 
          (__seqs_begin, __seqs_end, __target,
1645 
           multiway_merge_sampling_splitting</* __stable = */ true,
1646 
           typename std::iterator_traits<_RAIterPairIterator>
1647 
           ::value_type*, _Compare, _DifferenceTp>,
1648 
           static_cast<_DifferenceType>(__length), __comp,
1649 
           __tag.__get_num_threads());
1650 
      else
1651 
        return __sequential_multiway_merge
1652 
          </* __stable = */ true, /* __sentinels = */ false>
1653 
          (__seqs_begin, __seqs_end, __target,
1654 
           *(__seqs_begin->second), __length, __comp);
1655 
    }
1656 
 
1657 
  // public interface
1658 
  template<typename _RAIterPairIterator,
1659 
           typename _RAIterOut,
1660 
           typename _DifferenceTp,
1661 
           typename _Compare>
1662 
    _RAIterOut
1663 
    stable_multiway_merge(_RAIterPairIterator __seqs_begin,
1664 
                          _RAIterPairIterator __seqs_end,
1665 
                          _RAIterOut __target,
1666 
                          _DifferenceTp __length, _Compare __comp,
1667 
                          parallel_tag __tag = parallel_tag(0))
1668 
    {
1669 
      return stable_multiway_merge
1670 
        (__seqs_begin, __seqs_end, __target, __length, __comp,
1671 
         exact_tag(__tag.__get_num_threads()));
1672 
    }
1673 
 
1674 
  // public interface
1675 
  template<typename _RAIterPairIterator,
1676 
           typename _RAIterOut,
1677 
           typename _DifferenceTp,
1678 
           typename _Compare>
1679 
    _RAIterOut
1680 
    stable_multiway_merge(_RAIterPairIterator __seqs_begin,
1681 
                          _RAIterPairIterator __seqs_end,
1682 
                          _RAIterOut __target,
1683 
                          _DifferenceTp __length, _Compare __comp,
1684 
                          default_parallel_tag __tag)
1685 
    {
1686 
      return stable_multiway_merge
1687 
        (__seqs_begin, __seqs_end, __target, __length, __comp,
1688 
         exact_tag(__tag.__get_num_threads()));
1689 
    }
1690 
 
1691 
  /**
1692 
   * @brief Multiway Merge Frontend.
1693 
   *
1694 
   * Merge the sequences specified by seqs_begin and __seqs_end into
1695 
   * __target.  __seqs_begin and __seqs_end must point to a sequence of
1696 
   * pairs.  These pairs must contain an iterator to the beginning
1697 
   * of a sequence in their first entry and an iterator the _M_end of
1698 
   * the same sequence in their second entry.
1699 
   *
1700 
   * Ties are broken arbitrarily.  See stable_multiway_merge for a variant
1701 
   * that breaks ties by sequence number but is slower.
1702 
   *
1703 
   * The first entries of the pairs (i.e. the begin iterators) will be moved
1704 
   * forward accordingly.
1705 
   *
1706 
   * The output sequence has to provide enough space for all elements
1707 
   * that are written to it.
1708 
   *
1709 
   * This function will merge the input sequences:
1710 
   *
1711 
   * - not stable
1712 
   * - parallel, depending on the input size and Settings
1713 
   * - using sampling for splitting
1714 
   * - using sentinels
1715 
   *
1716 
   * You have to take care that the element the _M_end iterator points to is
1717 
   * readable and contains a value that is greater than any other non-sentinel
1718 
   * value in all sequences.
1719 
   *
1720 
   * Example:
1721 
   *
1722 
   * <pre>
1723 
   *   int sequences[10][11];
1724 
   *   for (int __i = 0; __i < 10; ++__i)
1725 
   *     for (int __j = 0; __i < 11; ++__j)
1726 
   *       sequences[__i][__j] = __j; // __last one is sentinel!
1727 
   *
1728 
   *   int __out[33];
1729 
   *   std::vector<std::pair<int*> > seqs;
1730 
   *   for (int __i = 0; __i < 10; ++__i)
1731 
   *     { seqs.push(std::make_pair<int*>(sequences[__i],
1732 
   *                                      sequences[__i] + 10)) }
1733 
   *
1734 
   *   multiway_merge(seqs.begin(), seqs.end(), __target, std::less<int>(), 33);
1735 
   * </pre>
1736 
   *
1737 
   * @pre All input sequences must be sorted.
1738 
   * @pre Target must provide enough space to merge out length elements or
1739 
   *    the number of elements in all sequences, whichever is smaller.
1740 
   * @pre For each @c __i, @c __seqs_begin[__i].second must be the end
1741 
   *    marker of the sequence, but also reference the one more __sentinel
1742 
   *    element.
1743 
   *
1744 
   * @post [__target, return __value) contains merged __elements from the
1745 
   *    input sequences.
1746 
   * @post return __value - __target = min(__length, number of elements in all
1747 
   *    sequences).
1748 
   *
1749 
   * @see stable_multiway_merge_sentinels
1750 
   *
1751 
   * @param _RAIterPairIterator iterator over sequence
1752 
   *    of pairs of iterators
1753 
   * @param _RAIterOut iterator over target sequence
1754 
   * @param _DifferenceTp difference type for the sequence
1755 
   * @param _Compare strict weak ordering type to compare elements
1756 
   *    in sequences
1757 
   *
1758 
   * @param __seqs_begin  __begin of sequence __sequence
1759 
   * @param __seqs_end    _M_end of sequence __sequence
1760 
   * @param __target      target sequence to merge to.
1761 
   * @param __comp        strict weak ordering to use for element comparison.
1762 
   * @param __length Maximum length to merge, possibly larger than the
1763 
   * number of elements available.
1764 
   *
1765 
   * @return _M_end iterator of output sequence
1766 
   */
1767 
  // multiway_merge_sentinels
1768 
  // public interface
1769 
  template<typename _RAIterPairIterator,
1770 
           typename _RAIterOut,
1771 
           typename _DifferenceTp,
1772 
           typename _Compare>
1773 
    _RAIterOut
1774 
    multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1775 
                             _RAIterPairIterator __seqs_end,
1776 
                             _RAIterOut __target,
1777 
                             _DifferenceTp __length, _Compare __comp,
1778 
                             __gnu_parallel::sequential_tag)
1779 
    {
1780 
      typedef _DifferenceTp _DifferenceType;
1781 
      _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1782 
 
1783 
      // catch special case: no sequences
1784 
      if (__seqs_begin == __seqs_end)
1785 
        return __target;
1786 
 
1787 
      // Execute multiway merge *sequentially*.
1788 
      return __sequential_multiway_merge
1789 
        </* __stable = */ false, /* __sentinels = */ true>
1790 
          (__seqs_begin, __seqs_end,
1791 
           __target, *(__seqs_begin->second), __length, __comp);
1792 
    }
1793 
 
1794 
  // public interface
1795 
  template<typename _RAIterPairIterator,
1796 
           typename _RAIterOut,
1797 
           typename _DifferenceTp,
1798 
           typename _Compare>
1799 
    _RAIterOut
1800 
    multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1801 
                             _RAIterPairIterator __seqs_end,
1802 
                             _RAIterOut __target,
1803 
                             _DifferenceTp __length, _Compare __comp,
1804 
                             __gnu_parallel::exact_tag __tag)
1805 
    {
1806 
      typedef _DifferenceTp _DifferenceType;
1807 
      _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1808 
 
1809 
      // catch special case: no sequences
1810 
      if (__seqs_begin == __seqs_end)
1811 
        return __target;
1812 
 
1813 
      // Execute merge; maybe parallel, depending on the number of merged
1814 
      // elements and the number of sequences and global thresholds in
1815 
      // Settings.
1816 
      if ((__seqs_end - __seqs_begin > 1)
1817 
          && _GLIBCXX_PARALLEL_CONDITION(
1818 
            ((__seqs_end - __seqs_begin) >=
1819 
              __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1820 
            && ((_SequenceIndex)__length >=
1821 
              __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1822 
        return parallel_multiway_merge
1823 
          </* __stable = */ false, /* __sentinels = */ true>
1824 
          (__seqs_begin, __seqs_end, __target,
1825 
           multiway_merge_exact_splitting</* __stable = */ false,
1826 
           typename std::iterator_traits<_RAIterPairIterator>
1827 
           ::value_type*, _Compare, _DifferenceTp>,
1828 
           static_cast<_DifferenceType>(__length), __comp,
1829 
           __tag.__get_num_threads());
1830 
      else
1831 
        return __sequential_multiway_merge
1832 
          </* __stable = */ false, /* __sentinels = */ true>
1833 
          (__seqs_begin, __seqs_end, __target,
1834 
           *(__seqs_begin->second), __length, __comp);
1835 
    }
1836 
 
1837 
  // public interface
1838 
  template<typename _RAIterPairIterator,
1839 
           typename _RAIterOut,
1840 
           typename _DifferenceTp,
1841 
           typename _Compare>
1842 
    _RAIterOut
1843 
    multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1844 
                             _RAIterPairIterator __seqs_end,
1845 
                             _RAIterOut __target,
1846 
                             _DifferenceTp __length, _Compare __comp,
1847 
                             sampling_tag __tag)
1848 
    {
1849 
      typedef _DifferenceTp _DifferenceType;
1850 
      _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1851 
 
1852 
      // catch special case: no sequences
1853 
      if (__seqs_begin == __seqs_end)
1854 
        return __target;
1855 
 
1856 
      // Execute merge; maybe parallel, depending on the number of merged
1857 
      // elements and the number of sequences and global thresholds in
1858 
      // Settings.
1859 
      if ((__seqs_end - __seqs_begin > 1)
1860 
          && _GLIBCXX_PARALLEL_CONDITION(
1861 
            ((__seqs_end - __seqs_begin) >=
1862 
              __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1863 
            && ((_SequenceIndex)__length >=
1864 
              __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1865 
        return parallel_multiway_merge
1866 
          </* __stable = */ false, /* __sentinels = */ true>
1867 
          (__seqs_begin, __seqs_end, __target,
1868 
           multiway_merge_sampling_splitting</* __stable = */ false,
1869 
           typename std::iterator_traits<_RAIterPairIterator>
1870 
           ::value_type*, _Compare, _DifferenceTp>,
1871 
           static_cast<_DifferenceType>(__length), __comp,
1872 
           __tag.__get_num_threads());
1873 
      else
1874 
        return __sequential_multiway_merge
1875 
          </* __stable = */false, /* __sentinels = */ true>(
1876 
            __seqs_begin, __seqs_end, __target,
1877 
            *(__seqs_begin->second), __length, __comp);
1878 
    }
1879 
 
1880 
  // public interface
1881 
  template<typename _RAIterPairIterator,
1882 
           typename _RAIterOut,
1883 
           typename _DifferenceTp,
1884 
           typename _Compare>
1885 
    _RAIterOut
1886 
    multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1887 
                             _RAIterPairIterator __seqs_end,
1888 
                             _RAIterOut __target,
1889 
                             _DifferenceTp __length, _Compare __comp,
1890 
                             parallel_tag __tag = parallel_tag(0))
1891 
    {
1892 
      return multiway_merge_sentinels
1893 
        (__seqs_begin, __seqs_end, __target, __length, __comp,
1894 
         exact_tag(__tag.__get_num_threads()));
1895 
    }
1896 
 
1897 
  // public interface
1898 
  template<typename _RAIterPairIterator,
1899 
           typename _RAIterOut,
1900 
           typename _DifferenceTp,
1901 
           typename _Compare>
1902 
    _RAIterOut
1903 
    multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1904 
                             _RAIterPairIterator __seqs_end,
1905 
                             _RAIterOut __target,
1906 
                             _DifferenceTp __length, _Compare __comp,
1907 
                             default_parallel_tag __tag)
1908 
    {
1909 
      return multiway_merge_sentinels
1910 
        (__seqs_begin, __seqs_end, __target, __length, __comp,
1911 
         exact_tag(__tag.__get_num_threads()));
1912 
    }
1913 
 
1914 
  // stable_multiway_merge_sentinels
1915 
  // public interface
1916 
  template<typename _RAIterPairIterator,
1917 
           typename _RAIterOut,
1918 
           typename _DifferenceTp,
1919 
           typename _Compare>
1920 
    _RAIterOut
1921 
    stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1922 
                                    _RAIterPairIterator __seqs_end,
1923 
                                    _RAIterOut __target,
1924 
                                    _DifferenceTp __length, _Compare __comp,
1925 
                                    __gnu_parallel::sequential_tag)
1926 
    {
1927 
      typedef _DifferenceTp _DifferenceType;
1928 
      _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1929 
 
1930 
      // catch special case: no sequences
1931 
      if (__seqs_begin == __seqs_end)
1932 
        return __target;
1933 
 
1934 
      // Execute multiway merge *sequentially*.
1935 
      return __sequential_multiway_merge
1936 
        </* __stable = */ true, /* __sentinels = */ true>
1937 
        (__seqs_begin, __seqs_end, __target,
1938 
         *(__seqs_begin->second), __length, __comp);
1939 
    }
1940 
 
1941 
  // public interface
1942 
  template<typename _RAIterPairIterator,
1943 
           typename _RAIterOut,
1944 
           typename _DifferenceTp,
1945 
           typename _Compare>
1946 
    _RAIterOut
1947 
    stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1948 
                                    _RAIterPairIterator __seqs_end,
1949 
                                    _RAIterOut __target,
1950 
                                    _DifferenceTp __length, _Compare __comp,
1951 
                                    __gnu_parallel::exact_tag __tag)
1952 
    {
1953 
      typedef _DifferenceTp _DifferenceType;
1954 
      _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1955 
 
1956 
      // catch special case: no sequences
1957 
      if (__seqs_begin == __seqs_end)
1958 
        return __target;
1959 
 
1960 
      // Execute merge; maybe parallel, depending on the number of merged
1961 
      // elements and the number of sequences and global thresholds in
1962 
      // Settings.
1963 
      if ((__seqs_end - __seqs_begin > 1)
1964 
          && _GLIBCXX_PARALLEL_CONDITION(
1965 
            ((__seqs_end - __seqs_begin) >=
1966 
            __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1967 
            && ((_SequenceIndex)__length >=
1968 
            __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1969 
        return parallel_multiway_merge
1970 
          </* __stable = */ true, /* __sentinels = */ true>
1971 
          (__seqs_begin, __seqs_end, __target,
1972 
           multiway_merge_exact_splitting</* __stable = */ true,
1973 
           typename std::iterator_traits<_RAIterPairIterator>
1974 
           ::value_type*, _Compare, _DifferenceTp>,
1975 
           static_cast<_DifferenceType>(__length), __comp,
1976 
           __tag.__get_num_threads());
1977 
      else
1978 
        return __sequential_multiway_merge
1979 
          </* __stable = */ true, /* __sentinels = */ true>
1980 
          (__seqs_begin, __seqs_end, __target,
1981 
           *(__seqs_begin->second), __length, __comp);
1982 
    }
1983 
 
1984 
  // public interface
1985 
  template<typename _RAIterPairIterator,
1986 
           typename _RAIterOut,
1987 
           typename _DifferenceTp,
1988 
           typename _Compare>
1989 
    _RAIterOut
1990 
    stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1991 
                                    _RAIterPairIterator __seqs_end,
1992 
                                    _RAIterOut __target,
1993 
                                    _DifferenceTp __length,
1994 
                                    _Compare __comp,
1995 
                                    sampling_tag __tag)
1996 
    {
1997 
      typedef _DifferenceTp _DifferenceType;
1998 
      _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1999 
 
2000 
      // catch special case: no sequences
2001 
      if (__seqs_begin == __seqs_end)
2002 
        return __target;
2003 
 
2004 
      // Execute merge; maybe parallel, depending on the number of merged
2005 
      // elements and the number of sequences and global thresholds in
2006 
      // Settings.
2007 
      if ((__seqs_end - __seqs_begin > 1)
2008 
          && _GLIBCXX_PARALLEL_CONDITION(
2009 
            ((__seqs_end - __seqs_begin) >=
2010 
              __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
2011 
            && ((_SequenceIndex)__length >=
2012 
              __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
2013 
        return parallel_multiway_merge
2014 
          </* __stable = */ true, /* __sentinels = */ true>
2015 
          (__seqs_begin, __seqs_end, __target,
2016 
           multiway_merge_sampling_splitting</* __stable = */ true,
2017 
           typename std::iterator_traits<_RAIterPairIterator>
2018 
           ::value_type*, _Compare, _DifferenceTp>,
2019 
           static_cast<_DifferenceType>(__length), __comp,
2020 
           __tag.__get_num_threads());
2021 
      else
2022 
        return __sequential_multiway_merge
2023 
          </* __stable = */ true, /* __sentinels = */ true>
2024 
          (__seqs_begin, __seqs_end, __target,
2025 
           *(__seqs_begin->second), __length, __comp);
2026 
    }
2027 
 
2028 
  // public interface
2029 
  template<typename _RAIterPairIterator,
2030 
           typename _RAIterOut,
2031 
           typename _DifferenceTp,
2032 
           typename _Compare>
2033 
    _RAIterOut
2034 
    stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
2035 
                                    _RAIterPairIterator __seqs_end,
2036 
                                    _RAIterOut __target,
2037 
                                    _DifferenceTp __length,
2038 
                                    _Compare __comp,
2039 
                                    parallel_tag __tag = parallel_tag(0))
2040 
    {
2041 
      return stable_multiway_merge_sentinels
2042 
        (__seqs_begin, __seqs_end, __target, __length, __comp,
2043 
         exact_tag(__tag.__get_num_threads()));
2044 
    }
2045 
 
2046 
  // public interface
2047 
  template<typename _RAIterPairIterator,
2048 
           typename _RAIterOut,
2049 
           typename _DifferenceTp,
2050 
           typename _Compare>
2051 
    _RAIterOut
2052 
    stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
2053 
                                    _RAIterPairIterator __seqs_end,
2054 
                                    _RAIterOut __target,
2055 
                                    _DifferenceTp __length, _Compare __comp,
2056 
                                    default_parallel_tag __tag)
2057 
    {
2058 
      return stable_multiway_merge_sentinels
2059 
        (__seqs_begin, __seqs_end, __target, __length, __comp,
2060 
         exact_tag(__tag.__get_num_threads()));
2061 
    }
2062 
}; // namespace __gnu_parallel
2063 
 
2064 
#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.