multiway_merge.h File Reference

Implementation of sequential and parallel multiway merge. More...

#include <vector>
#include <bits/stl_algo.h>
#include <parallel/features.h>
#include <parallel/parallel.h>
#include <parallel/losertree.h>
#include <parallel/multiseq_selection.h>

Include dependency graph for multiway_merge.h:

This graph shows which files directly or indirectly include this file:

Classes
struct	__gnu_parallel::__multiway_merge_3_variant_sentinel_switch< __sentinels, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare >
	Switch for 3-way merging with __sentinels turned off. More...
struct	__gnu_parallel::__multiway_merge_3_variant_sentinel_switch< true, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare >
	Switch for 3-way merging with __sentinels turned on. More...
struct	__gnu_parallel::__multiway_merge_4_variant_sentinel_switch< __sentinels, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare >
	Switch for 4-way merging with __sentinels turned off. More...
struct	__gnu_parallel::__multiway_merge_4_variant_sentinel_switch< true, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare >
	Switch for 4-way merging with __sentinels turned on. More...
struct	__gnu_parallel::__multiway_merge_k_variant_sentinel_switch< __sentinels, __stable, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare >
	Switch for k-way merging with __sentinels turned on. More...
struct	__gnu_parallel::__multiway_merge_k_variant_sentinel_switch< false, __stable, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare >
	Switch for k-way merging with __sentinels turned off. More...
class	__gnu_parallel::_GuardedIterator< _RAIter, _Compare >
	_Iterator wrapper supporting an implicit supremum at the end of the sequence, dominating all comparisons. More...
struct	__gnu_parallel::_LoserTreeTraits< _Tp >
	Traits for determining whether the loser tree should use pointers or copies. More...
struct	__gnu_parallel::_SamplingSorter< __stable, _RAIter, _StrictWeakOrdering >
	Stable sorting functor. More...
struct	__gnu_parallel::_SamplingSorter< false, _RAIter, _StrictWeakOrdering >
	Non-__stable sorting functor. More...
class	__gnu_parallel::_UnguardedIterator< _RAIter, _Compare >

Namespaces
	__gnu_parallel
	GNU parallel code for public use.

Macros
#define	_GLIBCXX_PARALLEL_DECISION(__a, __b, __c, __d)
#define	_GLIBCXX_PARALLEL_LENGTH(__s)   ((__s).second - (__s).first)
	Length of a sequence described by a pair of iterators. More...
#define	_GLIBCXX_PARALLEL_MERGE_3_CASE(__a, __b, __c, __c0, __c1)
#define	_GLIBCXX_PARALLEL_MERGE_4_CASE(__a, __b, __c, __d, __c0, __c1, __c2)

Functions
template<typename _RAIter1 , typename _RAIter2 , typename _OutputIterator , typename _DifferenceTp , typename _Compare >
_OutputIterator	__gnu_parallel::__merge_advance (_RAIter1 &__begin1, _RAIter1 __end1, _RAIter2 &__begin2, _RAIter2 __end2, _OutputIterator __target, _DifferenceTp __max_length, _Compare __comp)
	Merge routine being able to merge only the __max_length smallest elements. More...
template<bool __stable, bool __sentinels, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare >
_RAIter3	__gnu_parallel::__sequential_multiway_merge (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, const typename std::iterator_traits< typename std::iterator_traits< _RAIterIterator >::value_type::first_type >::value_type &__sentinel, _DifferenceTp __length, _Compare __comp)
	Sequential multi-way merging switch. More...
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	__gnu_parallel::multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sequential_tag)
	Multiway Merge Frontend. More...
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	__gnu_parallel::multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::exact_tag __tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	__gnu_parallel::multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sampling_tag __tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	__gnu_parallel::multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, parallel_tag __tag=parallel_tag(0))
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	__gnu_parallel::multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, default_parallel_tag __tag)
template<template< typename RAI, typename C > class iterator, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare >
_RAIter3	__gnu_parallel::multiway_merge_3_variant (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, _DifferenceTp __length, _Compare __comp)
	Highly efficient 3-way merging procedure. More...
template<template< typename RAI, typename C > class iterator, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare >
_RAIter3	__gnu_parallel::multiway_merge_4_variant (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, _DifferenceTp __length, _Compare __comp)
	Highly efficient 4-way merging procedure. More...
template<bool __stable, typename _RAIterIterator , typename _Compare , typename _DifferenceType >
void	__gnu_parallel::multiway_merge_exact_splitting (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _DifferenceType __length, _DifferenceType __total_length, _Compare __comp, std::vector< std::pair< _DifferenceType, _DifferenceType > > *__pieces)
	Exact splitting for parallel multiway-merge routine. More...
template<typename _LT , typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare >
_RAIter3	__gnu_parallel::multiway_merge_loser_tree (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, _DifferenceTp __length, _Compare __comp)
	Multi-way merging procedure for a high branching factor, guarded case. More...
template<typename UnguardedLoserTree , typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare >
_RAIter3	__gnu_parallel::multiway_merge_loser_tree_sentinel (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, const typename std::iterator_traits< typename std::iterator_traits< _RAIterIterator >::value_type::first_type >::value_type &__sentinel, _DifferenceTp __length, _Compare __comp)
	Multi-way merging procedure for a high branching factor, requiring sentinels to exist. More...
template<typename _LT , typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare >
_RAIter3	__gnu_parallel::multiway_merge_loser_tree_unguarded (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, const typename std::iterator_traits< typename std::iterator_traits< _RAIterIterator >::value_type::first_type >::value_type &__sentinel, _DifferenceTp __length, _Compare __comp)
	Multi-way merging procedure for a high branching factor, unguarded case. More...
template<bool __stable, typename _RAIterIterator , typename _Compare , typename _DifferenceType >
void	__gnu_parallel::multiway_merge_sampling_splitting (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _DifferenceType __length, _DifferenceType __total_length, _Compare __comp, std::vector< std::pair< _DifferenceType, _DifferenceType > > *__pieces)
	Sampling based splitting for parallel multiway-merge routine. More...
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	__gnu_parallel::multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sequential_tag)
	Multiway Merge Frontend. More...
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	__gnu_parallel::multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::exact_tag __tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	__gnu_parallel::multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, sampling_tag __tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	__gnu_parallel::multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, parallel_tag __tag=parallel_tag(0))
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	__gnu_parallel::multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, default_parallel_tag __tag)
template<bool __stable, bool __sentinels, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Splitter , typename _Compare >
_RAIter3	__gnu_parallel::parallel_multiway_merge (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, _Splitter __splitter, _DifferenceTp __length, _Compare __comp, _ThreadIndex __num_threads)
	Parallel multi-way merge routine. More...
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	__gnu_parallel::stable_multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sequential_tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	__gnu_parallel::stable_multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::exact_tag __tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	__gnu_parallel::stable_multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, sampling_tag __tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	__gnu_parallel::stable_multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, parallel_tag __tag=parallel_tag(0))
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	__gnu_parallel::stable_multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, default_parallel_tag __tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	__gnu_parallel::stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sequential_tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	__gnu_parallel::stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::exact_tag __tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	__gnu_parallel::stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, sampling_tag __tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	__gnu_parallel::stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, parallel_tag __tag=parallel_tag(0))
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	__gnu_parallel::stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, default_parallel_tag __tag)

Detailed Description

Implementation of sequential and parallel multiway merge.

Explanations on the high-speed merging routines in the appendix of

P. Sanders. Fast priority queues for cached memory. ACM Journal of Experimental Algorithmics, 5, 2000.

This file is a GNU parallel extension to the Standard C++ Library.

Macro Definition Documentation

#define _GLIBCXX_PARALLEL_DECISION	(		__a,
			__b,
			__c,
			__d
	)

Value:

{  \
    if (__seq ## __d < __seq ## __a)          \
      goto __s ## __d ## __a ## __b ## __c;       \
    if (__seq ## __d < __seq ## __b)          \
      goto __s ## __a ## __d ## __b ## __c;       \
    if (__seq ## __d < __seq ## __c)          \
      goto __s ## __a ## __b ## __d ## __c;       \
    goto __s ## __a ## __b ## __c ## __d;  }

Referenced by __gnu_parallel::multiway_merge_4_variant().

#define _GLIBCXX_PARALLEL_LENGTH

(

__s

)

((__s).second - (__s).first)

Length of a sequence described by a pair of iterators.

Referenced by __gnu_parallel::__sequential_multiway_merge(), __gnu_parallel::multiway_merge_exact_splitting(), __gnu_parallel::multiway_merge_loser_tree(), __gnu_parallel::multiway_merge_sampling_splitting(), and __gnu_parallel::parallel_multiway_merge().

#define _GLIBCXX_PARALLEL_MERGE_3_CASE	(		__a,
			__b,
			__c,
			__c0,
			__c1
	)

Value:

__s ## __a ## __b ## __c :                            \
    *__target = *__seq ## __a;                          \
    ++__target;                                         \
    --__length;                                         \
    ++__seq ## __a;                                     \
    if (__length == 0) goto __finish;                   \
    if (__seq ## __a __c0 __seq ## __b) goto __s ## __a ## __b ## __c; \
    if (__seq ## __a __c1 __seq ## __c) goto __s ## __b ## __a ## __c; \
    goto __s ## __b ## __c ## __a;

Referenced by __gnu_parallel::multiway_merge_3_variant().

#define _GLIBCXX_PARALLEL_MERGE_4_CASE	(		__a,
			__b,
			__c,
			__d,
			__c0,
			__c1,
			__c2
	)

Value:

__s ## __a ## __b ## __c ## __d:                      \
      if (__length == 0) goto __finish;                     \
      *__target = *__seq ## __a;                            \
      ++__target;                                           \
      --__length;                                           \
      ++__seq ## __a;                                       \
      if (__seq ## __a __c0 __seq ## __b)      \
    goto __s ## __a ## __b ## __c ## __d;  \
      if (__seq ## __a __c1 __seq ## __c)      \
    goto __s ## __b ## __a ## __c ## __d;  \
      if (__seq ## __a __c2 __seq ## __d)      \
    goto __s ## __b ## __c ## __a ## __d;  \
      goto __s ## __b ## __c ## __d ## __a;

Referenced by __gnu_parallel::multiway_merge_4_variant().