multiway_merge.h File Reference

#include <vector>
#include <iterator>
#include <algorithm>
#include <stxxl/bits/verbose.h>
#include <stxxl/bits/common/is_sorted.h>
#include <stxxl/bits/common/utils.h>
#include <stxxl/bits/parallel/merge.h>
#include <stxxl/bits/parallel/losertree.h>
#include <stxxl/bits/parallel/settings.h>
#include <stxxl/bits/parallel/equally_split.h>
#include <stxxl/bits/parallel/multiseq_selection.h>
#include <stxxl/bits/parallel/timing.h>
#include <stxxl/bits/parallel/tags.h>

Go to the source code of this file.

Classes
class	stxxl::parallel::guarded_iterator< RandomAccessIterator, Comparator >
	Iterator wrapper supporting an implicit supremum at the end of the sequence, dominating all comparisons. More...
struct	stxxl::parallel::loser_tree_traits< Stable, ValueType, Comparator >
struct	stxxl::parallel::loser_tree_traits< Stable, char, Comparator >
struct	stxxl::parallel::loser_tree_traits< Stable, int, Comparator >
struct	stxxl::parallel::loser_tree_traits< Stable, long long, Comparator >
struct	stxxl::parallel::loser_tree_traits< Stable, long, Comparator >
struct	stxxl::parallel::loser_tree_traits< Stable, short, Comparator >
struct	stxxl::parallel::loser_tree_traits< Stable, unsigned char, Comparator >
struct	stxxl::parallel::loser_tree_traits< Stable, unsigned int, Comparator >
struct	stxxl::parallel::loser_tree_traits< Stable, unsigned long long, Comparator >
struct	stxxl::parallel::loser_tree_traits< Stable, unsigned long, Comparator >
struct	stxxl::parallel::loser_tree_traits< Stable, unsigned short, Comparator >
class	stxxl::parallel::loser_tree_traits_unguarded< Stable, ValueType, Comparator >
struct	stxxl::parallel::loser_tree_traits_unguarded< Stable, char, Comparator >
struct	stxxl::parallel::loser_tree_traits_unguarded< Stable, int, Comparator >
struct	stxxl::parallel::loser_tree_traits_unguarded< Stable, long long, Comparator >
struct	stxxl::parallel::loser_tree_traits_unguarded< Stable, long, Comparator >
struct	stxxl::parallel::loser_tree_traits_unguarded< Stable, short, Comparator >
struct	stxxl::parallel::loser_tree_traits_unguarded< Stable, unsigned char, Comparator >
struct	stxxl::parallel::loser_tree_traits_unguarded< Stable, unsigned int, Comparator >
struct	stxxl::parallel::loser_tree_traits_unguarded< Stable, unsigned long long, Comparator >
struct	stxxl::parallel::loser_tree_traits_unguarded< Stable, unsigned long, Comparator >
struct	stxxl::parallel::loser_tree_traits_unguarded< Stable, unsigned short, Comparator >
class	stxxl::parallel::unguarded_iterator< RandomAccessIterator, Comparator >

Namespaces
	stxxl
	STXXL library namespace
	stxxl::parallel

Macros
#define	POS(i)   seqs_begin[(i)].first
#define	STOPS(i)   seqs_begin[(i)].second
#define	STXXL_DECISION(a, b, c, d)
#define	STXXL_MERGE3CASE(a, b, c, c0, c1)
#define	STXXL_MERGE4CASE(a, b, c, d, c0, c1, c2)
#define	STXXL_NO_POINTER(T)
#define	STXXL_NO_POINTER_UNGUARDED(T)

Functions
template<typename RandomAccessIteratorPair >
std::iterator_traits< typename RandomAccessIteratorPair::first_type > ::difference_type	stxxl::parallel::iterpair_size (const RandomAccessIteratorPair &p)
	Length of a sequence described by a pair of iterators. More...
template<typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename DiffType , typename Comparator >
RandomAccessIterator3	stxxl::parallel::multiway_merge_3_combined (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, DiffType length, Comparator comp)
template<template< typename RAI, typename C > class Iterator, typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename DiffType , typename Comparator >
RandomAccessIterator3	stxxl::parallel::multiway_merge_3_variant (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, DiffType length, Comparator comp)
	Highly efficient 3-way merging procedure. More...
template<typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename DiffType , typename Comparator >
RandomAccessIterator3	stxxl::parallel::multiway_merge_4_combined (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, DiffType length, Comparator comp)
template<template< typename RAI, typename C > class iterator, typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename DiffType , typename Comparator >
RandomAccessIterator3	stxxl::parallel::multiway_merge_4_variant (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, DiffType length, Comparator comp)
	Highly efficient 4-way merging procedure. More...
template<bool Stable, typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename DiffType , typename Comparator >
RandomAccessIterator3	stxxl::parallel::multiway_merge_bubble (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, DiffType length, Comparator comp)
	Basic multi-way merging procedure. More...
template<typename LoserTreeType , typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename DiffType , typename Comparator >
RandomAccessIterator3	stxxl::parallel::multiway_merge_loser_tree (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, DiffType length, Comparator comp)
	Multi-way merging procedure for a high branching factor, guarded case. More...
template<bool Stable, typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename DiffType , typename Comparator >
RandomAccessIterator3	stxxl::parallel::multiway_merge_loser_tree_combined (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, DiffType length, Comparator comp)
template<bool Stable, typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename DiffType , typename Comparator >
RandomAccessIterator3	stxxl::parallel::multiway_merge_loser_tree_sentinel (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, DiffType length, Comparator comp)
template<typename LoserTreeType , typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename DiffType , typename Comparator >
RandomAccessIterator3	stxxl::parallel::multiway_merge_loser_tree_unguarded (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, DiffType length, Comparator comp)
	Multi-way merging procedure for a high branching factor, unguarded case. More...
template<bool Stable, typename RandomAccessIteratorIterator , typename DiffType , typename Comparator >
void	stxxl::parallel::parallel_multiway_merge_exact_splitting (const RandomAccessIteratorIterator &seqs_begin, const RandomAccessIteratorIterator &seqs_end, DiffType length, DiffType total_length, Comparator comp, std::vector< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type > *chunks, const thread_index_t num_threads)
	Splitting method for parallel multi-way merge routine: use multisequence selection for exact splitting. More...
template<bool Stable, typename RandomAccessIteratorIterator , typename DiffType , typename Comparator >
void	stxxl::parallel::parallel_multiway_merge_sampling_splitting (const RandomAccessIteratorIterator &seqs_begin, const RandomAccessIteratorIterator &seqs_end, DiffType length, DiffType total_length, Comparator comp, std::vector< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type > *chunks, const thread_index_t num_threads)
	Splitting method for parallel multi-way merge routine: use sampling and binary search for in-exact splitting. More...
template<bool Stable, typename RandomAccessIteratorIterator , typename Comparator >
std::iterator_traits< typename std::iterator_traits < RandomAccessIteratorIterator > ::value_type::first_type > ::difference_type	stxxl::parallel::prepare_unguarded (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, Comparator comp, int &min_sequence)
	Prepare a set of sequences to be merged without a (end) guard. More...
template<typename RandomAccessIteratorIterator , typename Comparator >
std::iterator_traits< typename std::iterator_traits < RandomAccessIteratorIterator > ::value_type::first_type > ::difference_type	stxxl::parallel::prepare_unguarded_sentinel (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, Comparator comp)
	Prepare a set of sequences to be merged with a (end) guard (sentinel) More...
template<bool Stable, bool Sentinels, typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename DiffType , typename Comparator >
RandomAccessIterator3	stxxl::parallel::sequential_multiway_merge (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, DiffType length, Comparator comp)
	Sequential multi-way merging switch. More...

Macro Definition Documentation

#define POS

(

i

)

seqs_begin[(i)].first

Referenced by stxxl::parallel::multiway_merge_bubble().

#define STOPS

(

i

)

seqs_begin[(i)].second

Referenced by stxxl::parallel::multiway_merge_bubble().

#define STXXL_DECISION	(		a,
			b,
			c,
			d
	)

Value:

do { \
 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; \
} \
 while (0)

Referenced by stxxl::parallel::multiway_merge_4_variant().

#define STXXL_MERGE3CASE	(		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 stxxl::parallel::multiway_merge_3_variant().

#define STXXL_MERGE4CASE	(		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 stxxl::parallel::multiway_merge_4_variant().

#define STXXL_NO_POINTER

(

T

)

Value:

template <bool Stable, class Comparator> \
 struct loser_tree_traits<Stable, T, Comparator> \
 { \
 typedef LoserTreeCopy<Stable, T, Comparator> LT; \
 };

Definition at line 1079 of file multiway_merge.h.

#define STXXL_NO_POINTER_UNGUARDED

(

T

)

Value:

template <bool Stable, class Comparator> \
 struct loser_tree_traits_unguarded<Stable, T, Comparator> \
 { \
 typedef LoserTreeCopyUnguarded<Stable, T, Comparator> LT; \
 };

Definition at line 1106 of file multiway_merge.h.