Classes
class	active_tag

class	binary_negate
	Alternative to std::not2, typedefs first_argument_type and second_argument_type not needed. More...

class	equal_from_less
	Constructs predicate for equality from strict weak ordering predicate. More...

struct	equal_to

class	guarded_iterator
	Iterator wrapper supporting an implicit supremum at the end of the sequence, dominating all comparisons. More...

class	inactive_tag

struct	less

class	lexicographic
	Compare a pair of types lexcigraphically, ascending. More...

class	lexicographic_rev
	Compare a pair of types lexcigraphically, descending. More...

struct	loser_tree_traits

struct	loser_tree_traits< Stable, char, Comparator >

struct	loser_tree_traits< Stable, int, Comparator >

struct	loser_tree_traits< Stable, long long, Comparator >

struct	loser_tree_traits< Stable, long, Comparator >

struct	loser_tree_traits< Stable, short, Comparator >

struct	loser_tree_traits< Stable, unsigned char, Comparator >

struct	loser_tree_traits< Stable, unsigned int, Comparator >

struct	loser_tree_traits< Stable, unsigned long long, Comparator >

struct	loser_tree_traits< Stable, unsigned long, Comparator >

struct	loser_tree_traits< Stable, unsigned short, Comparator >

class	loser_tree_traits_unguarded

struct	loser_tree_traits_unguarded< Stable, char, Comparator >

struct	loser_tree_traits_unguarded< Stable, int, Comparator >

struct	loser_tree_traits_unguarded< Stable, long long, Comparator >

struct	loser_tree_traits_unguarded< Stable, long, Comparator >

struct	loser_tree_traits_unguarded< Stable, short, Comparator >

struct	loser_tree_traits_unguarded< Stable, unsigned char, Comparator >

struct	loser_tree_traits_unguarded< Stable, unsigned int, Comparator >

struct	loser_tree_traits_unguarded< Stable, unsigned long long, Comparator >

struct	loser_tree_traits_unguarded< Stable, unsigned long, Comparator >

struct	loser_tree_traits_unguarded< Stable, unsigned short, Comparator >

class	LoserTreeCopy

class	LoserTreeCopy< true, ValueType, Comparator >

class	LoserTreeCopyBase

class	LoserTreeCopyUnguarded

class	LoserTreeCopyUnguarded< true, ValueType, Comparator >

class	LoserTreeCopyUnguardedBase

class	LoserTreePointer

class	LoserTreePointer< true, ValueType, Comparator >

class	LoserTreePointerBase

class	LoserTreePointerUnguarded

class	LoserTreePointerUnguarded< true, ValueType, Comparator >

class	LoserTreePointerUnguardedBase

class	LoserTreeReference

class	NumberOfThreads

struct	Settings

class	Timing

class	Timing< inactive_tag, must_be_int >

class	unguarded_iterator

Typedefs
typedef int64	lcas_t

typedef double	point_in_time

typedef uint64	sequence_index_t

typedef Settings	SETTINGS

typedef int	thread_index_t

Functions
static void	decode2 (lcas_t x, int &a, int &b)
	Decode two integers from one mcstl::lcas_t. More...

static lcas_t	encode2 (int a, int b)
	Encode two integers into one mcstl::lcas_t. More...

template<typename DiffType , typename DiffTypeOutputIterator >
DiffTypeOutputIterator	equally_split (DiffType n, thread_index_t p, DiffTypeOutputIterator s)
	Split a sequence into parts of almost equal size. More...

template<typename RandomAccessIteratorPair >
std::iterator_traits< typename RandomAccessIteratorPair::first_type > ::difference_type	iterpair_size (const RandomAccessIteratorPair &p)
	Length of a sequence described by a pair of iterators. More...

template<typename RandomAccessIterator , typename Comparator >
RandomAccessIterator	median_of_three_iterators (RandomAccessIterator a, RandomAccessIterator b, RandomAccessIterator c, Comparator &comp)
	Compute the median of three referenced elements, according to `comp`. More...

template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename OutputIterator , typename DiffType , typename Comparator >
OutputIterator	merge_advance (RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, OutputIterator target, DiffType max_length, Comparator comp)
	Merge routine being able to merge only the `max_length` smallest elements. More...

template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename OutputIterator , typename DiffType , typename Comparator >
OutputIterator	merge_advance_movc (RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, OutputIterator target, DiffType max_length, Comparator comp)
	Merge routine being able to merge only the `max_length` smallest elements. More...

template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename OutputIterator , typename DiffType , typename Comparator >
OutputIterator	merge_advance_usual (RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, OutputIterator target, DiffType max_length, Comparator comp)
	Merge routine being able to merge only the `max_length` smallest elements. More...

template<typename RanSeqs , typename RankType , typename RankIterator , typename Comparator >
void	multiseq_partition (const RanSeqs &begin_seqs, const RanSeqs &end_seqs, const RankType &rank, RankIterator begin_offsets, Comparator comp=std::less< typename std::iterator_traits< typename std::iterator_traits< RanSeqs >::value_type::first_type >::value_type >())
	Splits several sorted sequences at a certain global rank, resulting in a splitting point for each sequence. More...

template<typename ValueType , typename RanSeqs , typename RankType , typename Comparator >
ValueType	multiseq_selection (const RanSeqs &begin_seqs, const RanSeqs &end_seqs, const RankType &rank, RankType &offset, Comparator comp=std::less< ValueType >())
	Selects the element at a certain global rank from several sorted sequences. More...

template<typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename DiffType , typename Comparator >
RandomAccessIterator3	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	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	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	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	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	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	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	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	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<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename RandomAccessIterator3 , typename Comparator >
RandomAccessIterator3	parallel_merge_advance (RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, RandomAccessIterator3 target, typename std::iterator_traits< RandomAccessIterator1 >::difference_type max_length, Comparator comp)
	Merge routine fallback to sequential in case the iterators of the two input sequences are of different type. More...

template<typename RandomAccessIterator1 , typename RandomAccessIterator3 , typename Comparator >
RandomAccessIterator3	parallel_merge_advance (RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator1 &begin2, RandomAccessIterator1 end2, RandomAccessIterator3 target, typename std::iterator_traits< RandomAccessIterator1 >::difference_type max_length, Comparator comp)
	Parallel merge routine being able to merge only the `max_length` smallest elements. More...

template<bool Stable, typename RandomAccessIteratorIterator , typename DiffType , typename Comparator >
void	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	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	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	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	sequential_multiway_merge (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, DiffType length, Comparator comp)
	Sequential multi-way merging switch. More...

Variables
static const size_t	lcas_t_bits = sizeof(lcas_t) * 8

static const lcas_t	lcas_t_mask = (((lcas_t)1 << (lcas_t_bits / 2)) - 1)

Typedef Documentation

typedef int64 stxxl::parallel::lcas_t

Longest compare-and-swappable integer type on this platform.

Definition at line 41 of file types.h.

typedef double stxxl::parallel::point_in_time

Type of of point in time, used for the Timing classes.

Definition at line 36 of file timing.h.

typedef uint64 stxxl::parallel::sequence_index_t

Unsigned integer to index elements. The total number of elements for each algorithm must fit into this type.

Definition at line 32 of file types.h.

typedef Settings stxxl::parallel::SETTINGS

Convenience typedef to avoid to have write Settings<>.

Definition at line 137 of file settings.h.

typedef int stxxl::parallel::thread_index_t

Unsigned integer to index a thread number. The maximum thread number must fit into this type.

Definition at line 37 of file types.h.

Function Documentation

static void stxxl::parallel::decode2	(	lcas_t	x,
		int &	a,
		int &	b
	)

inlinestatic

Decode two integers from one mcstl::lcas_t.

Parameters

x	mcstl::lcas_t to decode integers from.
a	First integer, to be decoded from the most-significant `lcas_t_bits/2` bits of `x`.
b	Second integer, to be encoded in the least-significant `lcas_t_bits/2` bits of `x`.

See Also: encode2

Definition at line 73 of file base.h.

References lcas_t_bits, and lcas_t_mask.

static lcas_t stxxl::parallel::encode2	(	int	a,
		int	b
	)

inlinestatic

Encode two integers into one mcstl::lcas_t.

Parameters

a	First integer, to be encoded in the most-significant `lcas_t_bits/2` bits.
b	Second integer, to be encoded in the least-significant `lcas_t_bits/2` bits.

Returns: mcstl::lcas_t value encoding a and b.

See Also: decode2

Definition at line 60 of file base.h.

References lcas_t_bits.

template<typename DiffType , typename DiffTypeOutputIterator >

DiffTypeOutputIterator stxxl::parallel::equally_split	(	DiffType	n,
		thread_index_t	p,
		DiffTypeOutputIterator	s
	)

Split a sequence into parts of almost equal size.

The resulting sequence s of length p+1 contains the splitting positions when splitting the range [0,n) into parts of almost equal size (plus minus 1). The first entry is 0, the last one n. There may result empty parts.

Parameters

n	Number of elements
p	Number of parts
s	Splitters

Returns: End of splitter sequence, i. e. s+p+1

Definition at line 41 of file equally_split.h.

References stxxl::split().

Referenced by parallel_multiway_merge_exact_splitting().

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.

Definition at line 49 of file multiway_merge.h.

Referenced by multiway_merge_3_combined(), multiway_merge_4_combined(), multiway_merge_bubble(), multiway_merge_loser_tree(), multiway_merge_loser_tree_combined(), multiway_merge_loser_tree_unguarded(), and parallel_multiway_merge_sampling_splitting().

template<typename RandomAccessIterator , typename Comparator >

RandomAccessIterator stxxl::parallel::median_of_three_iterators	(	RandomAccessIterator	a,
		RandomAccessIterator	b,
		RandomAccessIterator	c,
		Comparator &	comp
	)

Compute the median of three referenced elements, according to comp.

Parameters

a	First iterator.
b	Second iterator.
c	Third iterator.
comp	Comparator.

Definition at line 108 of file base.h.

template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename OutputIterator , typename DiffType , typename Comparator >

OutputIterator stxxl::parallel::merge_advance	(	RandomAccessIterator1 &	begin1,
		RandomAccessIterator1	end1,
		RandomAccessIterator2 &	begin2,
		RandomAccessIterator2	end2,
		OutputIterator	target,
		DiffType	max_length,
		Comparator	comp
	)

Merge routine being able to merge only the max_length smallest elements.

The begin iterators are advanced accordingly, they might not reach end, in contrast to the usual variant. Static switch on whether to use the conditional-move variant.

Parameters

begin1	Begin iterator of first sequence.
end1	End iterator of first sequence.
begin2	Begin iterator of second sequence.
end2	End iterator of second sequence.
target	Target begin iterator.
max_length	Maximum number of elements to merge.
comp	Comparator.

Returns: Output end iterator.

Definition at line 161 of file merge.h.

References merge_advance_movc(), and STXXL_PARALLEL_PCALL.

Referenced by multiway_merge_3_combined(), parallel_merge_advance(), and sequential_multiway_merge().

template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename OutputIterator , typename DiffType , typename Comparator >

OutputIterator stxxl::parallel::merge_advance_movc	(	RandomAccessIterator1 &	begin1,
		RandomAccessIterator1	end1,
		RandomAccessIterator2 &	begin2,
		RandomAccessIterator2	end2,
		OutputIterator	target,
		DiffType	max_length,
		Comparator	comp
	)

Merge routine being able to merge only the max_length smallest elements.

The begin iterators are advanced accordingly, they might not reach end, in contrast to the usual variant. Specially designed code should allow the compiler to generate conditional moves instead of branches.

Parameters

begin1	Begin iterator of first sequence.
end1	End iterator of first sequence.
begin2	Begin iterator of second sequence.
end2	End iterator of second sequence.
target	Target begin iterator.
max_length	Maximum number of elements to merge.
comp	Comparator.

Returns: Output end iterator.

Definition at line 96 of file merge.h.

Referenced by merge_advance().

template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename OutputIterator , typename DiffType , typename Comparator >

OutputIterator stxxl::parallel::merge_advance_usual	(	RandomAccessIterator1 &	begin1,
		RandomAccessIterator1	end1,
		RandomAccessIterator2 &	begin2,
		RandomAccessIterator2	end2,
		OutputIterator	target,
		DiffType	max_length,
		Comparator	comp
	)

Merge routine being able to merge only the max_length smallest elements.

The begin iterators are advanced accordingly, they might not reach end, in contrast to the usual variant.

Parameters

begin1	Begin iterator of first sequence.
end1	End iterator of first sequence.
begin2	Begin iterator of second sequence.
end2	End iterator of second sequence.
target	Target begin iterator.
max_length	Maximum number of elements to merge.
comp	Comparator.

Returns: Output end iterator.

Definition at line 48 of file merge.h.

template<typename RanSeqs , typename RankType , typename RankIterator , typename Comparator >

void stxxl::parallel::multiseq_partition	(	const RanSeqs &	begin_seqs,
		const RanSeqs &	end_seqs,
		const RankType &	rank,
		RankIterator	begin_offsets,
		Comparator	comp = `std::less< typename std::iterator_traits<typename std::iterator_traits<RanSeqs> ::value_type::first_type>::value_type >()`
	)

Splits several sorted sequences at a certain global rank, resulting in a splitting point for each sequence.

The sequences are passed via a sequence of random-access iterator pairs, none of the sequences may be empty. If there are several equal elements across the split, the ones on the left side will be chosen from sequences with smaller number.

Parameters

begin_seqs	Begin of the sequence of iterator pairs.
end_seqs	End of the sequence of iterator pairs.
rank	The global rank to partition at.
begin_offsets	A random-access sequence begin where the result will be stored in. Each element of the sequence is an iterator that points to the first element on the greater part of the respective sequence.
comp	The ordering functor, defaults to std::less<T>.

Definition at line 102 of file multiseq_selection.h.

References max(), min(), stxxl::round_up_to_power_of_two(), S, stxxl::sort(), and STXXL_PARALLEL_PCALL.

Referenced by parallel_multiway_merge_exact_splitting().

template<typename ValueType , typename RanSeqs , typename RankType , typename Comparator >

ValueType stxxl::parallel::multiseq_selection	(	const RanSeqs &	begin_seqs,
		const RanSeqs &	end_seqs,
		const RankType &	rank,
		RankType &	offset,
		Comparator	comp = `std::less<ValueType>()`
	)

Selects the element at a certain global rank from several sorted sequences.

The sequences are passed via a sequence of random-access iterator pairs, none of the sequences may be empty.

Parameters

begin_seqs	Begin of the sequence of iterator pairs.
end_seqs	End of the sequence of iterator pairs.
rank	The global rank to partition at.
offset	The rank of the selected element in the global subsequence of elements equal to the selected element. If the selected element is unique, this number is 0.
comp	The ordering functor, defaults to std::less.

Definition at line 347 of file multiseq_selection.h.

References max(), min(), stxxl::round_up_to_power_of_two(), S, stxxl::sort(), and STXXL_PARALLEL_PCALL.

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
	)

Definition at line 470 of file multiway_merge.h.

References stxxl::is_sorted(), iterpair_size(), merge_advance(), min(), STXXL_ASSERT, STXXL_DEBUG_ASSERT, and STXXL_PARALLEL_PCALL.

Referenced by sequential_multiway_merge().

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.

Merging is done with the algorithm implementation described by Peter Sanders. Basically, the idea is to minimize the number of necessary comparison after merging an element. The implementation trick that makes this fast is that the order of the sequences is stored in the instruction pointer (translated into labels in C++).

This works well for merging up to 4 sequences.

Note that making the merging stable does not come at a performance hit.

Whether the merging is done guarded or unguarded is selected by the used iterator class.

Parameters

seqs_begin	Begin iterator of iterator pair input sequence.
seqs_end	End iterator of iterator pair input sequence.
target	Begin iterator out output sequence.
length	Maximum length to merge.
comp	Comparator.

Returns: End iterator of output sequence.

Definition at line 384 of file multiway_merge.h.

References STXXL_ASSERT, STXXL_CHECK_EQUAL, STXXL_MERGE3CASE, and STXXL_PARALLEL_PCALL.

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
	)

Definition at line 679 of file multiway_merge.h.

References stxxl::is_sorted(), iterpair_size(), min(), STXXL_ASSERT, STXXL_DEBUG_ASSERT, and STXXL_PARALLEL_PCALL.

Referenced by sequential_multiway_merge().

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.

Merging is done with the algorithm implementation described by Peter Sanders. Basically, the idea is to minimize the number of necessary comparison after merging an element. The implementation trick that makes this fast is that the order of the sequences is stored in the instruction pointer (translated into goto labels in C++).

This works well for merging up to 4 sequences.

Note that making the merging stable does not come at a performance hit.

Whether the merging is done guarded or unguarded is selected by the used iterator class.

Parameters

seqs_begin	Begin iterator of iterator pair input sequence.
seqs_end	End iterator of iterator pair input sequence.
target	Begin iterator out output sequence.
length	Maximum length to merge.
comp	Comparator.

Returns: End iterator of output sequence.

Definition at line 562 of file multiway_merge.h.

References STXXL_ASSERT, STXXL_CHECK_EQUAL, STXXL_DECISION, STXXL_MERGE4CASE, and STXXL_PARALLEL_PCALL.

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.

The head elements are kept in a sorted array, new heads are inserted linearly.

Parameters

seqs_begin	Begin iterator of iterator pair input sequence.
seqs_end	End iterator of iterator pair input sequence.
target	Begin iterator out output sequence.
length	Maximum length to merge.
comp	Comparator.

Template Parameters

Stable Stable merging incurs a performance penalty.

Returns: End iterator of output sequence.

Definition at line 748 of file multiway_merge.h.

References iterpair_size(), POS, STOPS, and STXXL_PARALLEL_PCALL.

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.

The head elements are kept in a loser tree.

Parameters

seqs_begin	Begin iterator of iterator pair input sequence.
seqs_end	End iterator of iterator pair input sequence.
target	Begin iterator out output sequence.
length	Maximum length to merge.
comp	Comparator.

Template Parameters

Stable Stable merging incurs a performance penalty.

Returns: End iterator of output sequence.

Definition at line 930 of file multiway_merge.h.

References iterpair_size(), min(), STXXL_PARALLEL_PCALL, and UNLIKELY.

Referenced by multiway_merge_loser_tree_combined(), and sequential_multiway_merge().

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
	)

Definition at line 1131 of file multiway_merge.h.

References stxxl::is_sorted(), iterpair_size(), min(), multiway_merge_loser_tree(), multiway_merge_loser_tree_unguarded(), STXXL_DEBUG_ASSERT, and STXXL_PARALLEL_PCALL.

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
	)

Definition at line 1185 of file multiway_merge.h.

References stxxl::is_sorted(), multiway_merge_loser_tree_unguarded(), STXXL_DEBUG_ASSERT, and STXXL_PARALLEL_PCALL.

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.

The head elements are kept in a loser tree.

Parameters

seqs_begin	Begin iterator of iterator pair input sequence.
seqs_end	End iterator of iterator pair input sequence.
target	Begin iterator out output sequence.
length	Maximum length to merge.
comp	Comparator.

Template Parameters

Stable Stable merging incurs a performance penalty.

Returns: End iterator of output sequence.

Precondition: No input will run out of elements during the merge.

Definition at line 1011 of file multiway_merge.h.

References iterpair_size(), min(), and STXXL_PARALLEL_PCALL.

Referenced by multiway_merge_loser_tree_combined(), and multiway_merge_loser_tree_sentinel().

template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename RandomAccessIterator3 , typename Comparator >

RandomAccessIterator3 stxxl::parallel::parallel_merge_advance	(	RandomAccessIterator1 &	begin1,
		RandomAccessIterator1	end1,
		RandomAccessIterator2 &	begin2,
		RandomAccessIterator2	end2,
		RandomAccessIterator3	target,
		typename std::iterator_traits< RandomAccessIterator1 >::difference_type	max_length,
		Comparator	comp
	)

Merge routine fallback to sequential in case the iterators of the two input sequences are of different type.

Parameters

begin1	Begin iterator of first sequence.
end1	End iterator of first sequence.
begin2	Begin iterator of second sequence.
end2	End iterator of second sequence.
target	Target begin iterator.
max_length	Maximum number of elements to merge.
comp	Comparator.

Returns: Output end iterator.

Definition at line 187 of file merge.h.

References merge_advance().

template<typename RandomAccessIterator1 , typename RandomAccessIterator3 , typename Comparator >

RandomAccessIterator3 stxxl::parallel::parallel_merge_advance	(	RandomAccessIterator1 &	begin1,
		RandomAccessIterator1	end1,
		RandomAccessIterator1 &	begin2,
		RandomAccessIterator1	end2,
		RandomAccessIterator3	target,
		typename std::iterator_traits< RandomAccessIterator1 >::difference_type	max_length,
		Comparator	comp
	)

Parallel merge routine being able to merge only the max_length smallest elements.

The begin iterators are advanced accordingly, they might not reach end, in contrast to the usual variant. The functionality is projected onto parallel_multiway_merge.

Parameters

begin1	Begin iterator of first sequence.
end1	End iterator of first sequence.
begin2	Begin iterator of second sequence.
end2	End iterator of second sequence.
target	Target begin iterator.
max_length	Maximum number of elements to merge.
comp	Comparator.

Returns: Output end iterator.

Definition at line 218 of file merge.h.

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.

Parameters

seqs_begin	Begin iterator of iterator pair input sequence.
seqs_end	End iterator of iterator pair input sequence.
length	Maximum length to merge.
total_length	Total length of all sequences combined.
comp	Comparator.
chunks	Output subsequences for num_threads.
num_threads	Split the sequences into for num_threads.

Template Parameters

Stable Stable merging incurs a performance penalty.

Returns: End iterator of output sequence.

Definition at line 1447 of file multiway_merge.h.

References equally_split(), and multiseq_partition().

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.

Parameters

seqs_begin	Begin iterator of iterator pair input sequence.
seqs_end	End iterator of iterator pair input sequence.
length	Maximum length to merge.
total_length	Total length of all sequences combined.
comp	Comparator.
chunks	Output subsequences for num_threads.
num_threads	Split the sequences into for num_threads.

Template Parameters

Stable Stable merging incurs a performance penalty.

Returns: End iterator of output sequence.

Definition at line 1361 of file multiway_merge.h.

References iterpair_size(), and stxxl::sort().

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.

Parameters

seqs_begin
seqs_end
comp
min_sequence

Template Parameters

Stable

Precondition: (seqs_end - seqs_begin > 0)

Definition at line 243 of file multiway_merge.h.

References min(), stxxl::split(), and STXXL_PARALLEL_PCALL.

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)

Parameters

seqs_begin
seqs_end
comp

Definition at line 321 of file multiway_merge.h.

References stxxl::split(), and STXXL_PARALLEL_PCALL.

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.

The decision if based on the branching factor and runtime settings.

Parameters

seqs_begin	Begin iterator of iterator pair input sequence.
seqs_end	End iterator of iterator pair input sequence.
target	Begin iterator out output sequence.
length	Maximum length to merge.
comp	Comparator.

Template Parameters

Stable	Stable merging incurs a performance penalty.
Sentinels	The sequences have a sentinel element.

Returns: End iterator of output sequence.

Definition at line 1236 of file multiway_merge.h.

References stxxl::is_sorted(), merge_advance(), multiway_merge_3_combined(), multiway_merge_4_combined(), multiway_merge_loser_tree(), STXXL_DEBUG_ASSERT, and STXXL_PARALLEL_PCALL.

Variable Documentation

const size_t stxxl::parallel::lcas_t_bits = sizeof(lcas_t) * 8

static

Number of bits of lcas_t.

Definition at line 45 of file types.h.

Referenced by decode2(), and encode2().

const lcas_t stxxl::parallel::lcas_t_mask = (((lcas_t)1 << (lcas_t_bits / 2)) - 1)

static

lcas_t with the right half of bits set to 1.

Definition at line 49 of file types.h.

Referenced by decode2().

Classes

Typedefs

Functions

Variables

Typedef Documentation

Function Documentation

Variable Documentation