Stream Package

Package that enables pipelining of consequent sorts and scans of the external data avoiding the saving the intermediate results on the disk, e.g. the output of a sort can be directly fed into a scan procedure without the need to save it on a disk. All components of the package are contained in the stxxl::stream namespace. More...

Classes
class	stxxl::stream::basic_runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >
	Forms sorted runs of data from a stream. More...
class	stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >
	Merges sorted runs. More...
class	stxxl::stream::compute_sorted_runs_type< ValueType_, BlockSize_ >
	Computes sorted runs type from value type and block size. More...
struct	stxxl::stream::from_sorted_sequences< ValueType_ >
	Input strategy for runs_creator class. More...
class	stxxl::stream::generator2stream< Generator_, T >
	A model of stream that outputs data from an adaptable generator functor. For convenience use streamify function instead of direct instantiation of generator2stream . More...
class	stxxl::stream::iterator2stream< InputIterator_ >
	A model of stream that retrieves the data from an input iterator. For convenience use streamify function instead of direct instantiation of iterator2stream . More...
class	stxxl::stream::make_tuple< Input1_, Input2_, Input3_, Input4_, Input5_, Input6_ >
	Creates stream of 6-tuples from 6 input streams. More...
class	stxxl::stream::make_tuple< Input1_, Input2_, Input3_, Input4_, Input5_, Stopper >
	Creates stream of 5-tuples from 5 input streams. More...
class	stxxl::stream::make_tuple< Input1_, Input2_, Input3_, Input4_, Stopper, Stopper >
	Creates stream of 4-tuples from 4 input streams. More...
class	stxxl::stream::make_tuple< Input1_, Input2_, Input3_, Stopper, Stopper, Stopper >
	Creates stream of 3-tuples from 3 input streams. More...
class	stxxl::stream::make_tuple< Input1_, Input2_, Stopper, Stopper, Stopper, Stopper >
	Creates stream of 2-tuples (pairs) from 2 input streams. More...
class	stxxl::stream::runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >
	Forms sorted runs of data from a stream. More...
class	stxxl::stream::runs_creator< from_sorted_sequences< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >
	Forms sorted runs of data taking elements in sorted order (element by element). More...
class	stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >
	Forms sorted runs of elements passed in push() method. More...
class	stxxl::stream::runs_merger< RunsType_, CompareType_, AllocStr_ >
	Merges sorted runs. More...
class	stxxl::stream::sort< Input_, CompareType_, BlockSize_, AllocStr_, runs_creator_type >
	Produces sorted stream from input stream. More...
struct	stxxl::stream::sorted_runs< TriggerEntryType, CompareType >
	All sorted runs of a sort operation. More...
struct	stxxl::stream::Stopper
struct	stxxl::stream::streamify_traits< InputIterator_ >
	Traits class of streamify function. More...
struct	stxxl::stream::streamify_traits< stxxl::const_vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > >
struct	stxxl::stream::streamify_traits< stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > >
class	stxxl::stream::transform< Operation_, Input1_, Input2_, Input3_, Input4_, Input5_, Input6_ >
	Processes (up to) 6 input streams using given operation functor. More...
class	stxxl::stream::transform< Operation_, Input1_, Input2_, Input3_, Input4_, Input5_, Stopper >
	Processes 5 input streams using given operation functor. More...
class	stxxl::stream::transform< Operation_, Input1_, Input2_, Input3_, Input4_, Stopper, Stopper >
	Processes 4 input streams using given operation functor. More...
class	stxxl::stream::transform< Operation_, Input1_, Input2_, Input3_, Stopper, Stopper, Stopper >
	Processes 3 input streams using given operation functor. More...
class	stxxl::stream::transform< Operation_, Input1_, Input2_, Stopper, Stopper, Stopper, Stopper >
	Processes 2 input streams using given operation functor. More...
class	stxxl::stream::transform< Operation_, Input1_, Stopper, Stopper, Stopper, Stopper, Stopper >
	Processes an input stream using given operation functor. More...
struct	stxxl::stream::use_push< ValueType_ >
	Input strategy for runs_creator class. More...
class	stxxl::stream::vector_iterator2stream< InputIterator_ >
	A model of stream that retrieves data from an external stxxl::vector iterator. It is more efficient than generic iterator2stream thanks to use of overlapping For convenience use streamify function instead of direct instantiation of vector_iterator2stream . More...
class	stxxl::stream::vector_iterator2stream_sr< InputIterator_ >
	Version of iterator2stream. Switches between vector_iterator2stream and iterator2stream . More...

Functions
template<class RunsType_ , class CompareType_ >
bool	stxxl::stream::check_sorted_runs (const RunsType_ &sruns, CompareType_ cmp)
	Checker for the sorted runs object created by the runs_creator . More...
void	stxxl::stream::basic_runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >::compute_result ()
	Finish the results, i. e. create all runs. More...
template<class StreamAlgorithm_ >
void	stxxl::stream::discard (StreamAlgorithm_ &in)
	Reads stream content and discards it. Useful where you do not need the processed stream anymore, but are just interested in side effects, or just for debugging. More...
template<class OutputIterator_ , class StreamAlgorithm_ >
OutputIterator_	stxxl::stream::materialize (StreamAlgorithm_ &in, OutputIterator_ out)
	Stores consecutively stream content to an output iterator. More...
template<class OutputIterator_ , class StreamAlgorithm_ >
OutputIterator_	stxxl::stream::materialize (StreamAlgorithm_ &in, OutputIterator_ outbegin, OutputIterator_ outend)
	Stores consecutively stream content to an output iterator range until end of the stream or end of the iterator range is reached. More...
template<typename Tp_ , typename AllocStr_ , typename SzTp_ , typename DiffTp_ , unsigned BlkSize_, typename PgTp_ , unsigned PgSz_, class StreamAlgorithm_ >
stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >	stxxl::stream::materialize (StreamAlgorithm_ &in, stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > outbegin, stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > outend, unsigned_type nbuffers=0)
	Stores consecutively stream content to an output stxxl::vector iterator until end of the stream or end of the iterator range is reached. More...
template<typename Tp_ , typename AllocStr_ , typename SzTp_ , typename DiffTp_ , unsigned BlkSize_, typename PgTp_ , unsigned PgSz_, class StreamAlgorithm_ >
stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >	stxxl::stream::materialize (StreamAlgorithm_ &in, stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > out, unsigned_type nbuffers=0)
	Stores consecutively stream content to an output stxxl::vector iterator. More...
void	stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::merge_recursively ()
template<class InputIterator_ >
iterator2stream< InputIterator_ >	stxxl::stream::streamify (InputIterator_ begin, InputIterator_ end)
	Input iterator range to stream converter. More...
template<typename Tp_ , typename AllocStr_ , typename SzTp_ , typename DiffTp_ , unsigned BlkSize_, typename PgTp_ , unsigned PgSz_>
vector_iterator2stream < stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > >	stxxl::stream::streamify (stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > begin, stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > end, unsigned_type nbuffers=0)
	Input external stxxl::vector iterator range to stream converter. It is more efficient than generic input iterator streamify thanks to use of overlapping. More...
template<typename Tp_ , typename AllocStr_ , typename SzTp_ , typename DiffTp_ , unsigned BlkSize_, typename PgTp_ , unsigned PgSz_>
vector_iterator2stream < stxxl::const_vector_iterator < Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > >	stxxl::stream::streamify (stxxl::const_vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > begin, stxxl::const_vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > end, unsigned_type nbuffers=0)
	Input external stxxl::vector const iterator range to stream converter. It is more efficient than generic input iterator streamify thanks to use of overlapping. More...
template<class Generator_ >
generator2stream< Generator_ >	stxxl::stream::streamify (Generator_ gen_)
	Adaptable generator to stream converter. More...
template<typename Tp_ , typename AllocStr_ , typename SzTp_ , typename DiffTp_ , unsigned BlkSize_, typename PgTp_ , unsigned PgSz_>
vector_iterator2stream_sr < stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > >	stxxl::stream::streamify_sr (stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > begin, stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > end, unsigned_type nbuffers=0)
	Version of streamify. Switches from vector_iterator2stream to iterator2stream for small ranges. More...
template<typename Tp_ , typename AllocStr_ , typename SzTp_ , typename DiffTp_ , unsigned BlkSize_, typename PgTp_ , unsigned PgSz_>
vector_iterator2stream_sr < stxxl::const_vector_iterator < Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > >	stxxl::stream::streamify_sr (stxxl::const_vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > begin, stxxl::const_vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > end, unsigned_type nbuffers=0)
	Version of streamify. Switches from vector_iterator2stream to iterator2stream for small ranges. More...

Detailed Description

Package that enables pipelining of consequent sorts and scans of the external data avoiding the saving the intermediate results on the disk, e.g. the output of a sort can be directly fed into a scan procedure without the need to save it on a disk. All components of the package are contained in the stxxl::stream namespace.

STREAM ALGORITHM CONCEPT (Do not confuse with C++ input/output streams)

   struct stream_algorithm // stream, pipe, whatever
   {
     typedef some_type value_type;

     const value_type & operator * () const; // return current element of the stream
     stream_algorithm & operator ++ ();      // go to next element. precondition: empty() == false
     bool empty() const;                     // return true if end of stream is reached

   };

Function Documentation

template<class RunsType_ , class CompareType_ >

bool stxxl::stream::check_sorted_runs	(	const RunsType_ &	sruns,
		CompareType_	cmp
	)

Checker for the sorted runs object created by the runs_creator .

Parameters

sruns	sorted runs object
cmp	comparison object used for checking the order of elements in runs

Returns

true if runs are sorted, false otherwise

=

Definition at line 851 of file sort_stream.h.

References stxxl::is_sorted(), stxxl::make_element_iterator(), STXXL_ERRMSG, STXXL_MSG, STXXL_VERBOSE2, stxxl::sort_helper::verify_sentinel_strict_weak_ordering(), and stxxl::wait_all().

template<class Input_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

void stxxl::stream::basic_runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >::compute_result ( )

private

Finish the results, i. e. create all runs.

This is the main routine of this class.

Definition at line 157 of file sort_stream.h.

References stxxl::mng_local::element_block< Type, Size >::begin(), stxxl::check_sort_settings(), stxxl::block_manager::delete_blocks(), stxxl::div_ceil(), stxxl::make_bid_iterator(), stxxl::block_manager::new_blocks(), stxxl::sort(), STXXL_VERBOSE1, stxxl::request_interface::wait(), stxxl::wait_all(), and stxxl::typed_block< RawSize, Type, NRef, MetaInfoType >::write().

template<class StreamAlgorithm_ >

void stxxl::stream::discard

(

StreamAlgorithm_ &

in

)

Reads stream content and discards it. Useful where you do not need the processed stream anymore, but are just interested in side effects, or just for debugging.

Parameters

in	input stream

Definition at line 606 of file stream.h.

template<class OutputIterator_ , class StreamAlgorithm_ >

OutputIterator_ stxxl::stream::materialize	(	StreamAlgorithm_ &	in,
		OutputIterator_	out
	)

Stores consecutively stream content to an output iterator.

Parameters

in	stream to be stored used as source
out	output iterator used as destination

Returns

value of the output iterator after all increments, i.e. points to the first unwritten value

Precondition

Output (range) is large enough to hold the all elements in the input stream

Examples:

examples/algo/copy_and_sort_file.cpp, examples/applications/skew3.cpp, examples/containers/copy_file.cpp, and examples/stream/stream1.cpp.

Definition at line 396 of file stream.h.

References STXXL_PRETTY_FUNCTION_NAME, and STXXL_VERBOSE_MATERIALIZE.

Referenced by stxxl::sort().

template<class OutputIterator_ , class StreamAlgorithm_ >

OutputIterator_ stxxl::stream::materialize	(	StreamAlgorithm_ &	in,
		OutputIterator_	outbegin,
		OutputIterator_	outend
	)

Stores consecutively stream content to an output iterator range until end of the stream or end of the iterator range is reached.

Parameters

in	stream to be stored used as source
outbegin	output iterator used as destination
outend	output end iterator, pointing beyond the output range

Returns

value of the output iterator after all increments, i.e. points to the first unwritten value

Precondition

Output range is large enough to hold the all elements in the input stream

This function is useful when you do not know the length of the stream beforehand.

Definition at line 419 of file stream.h.

References STXXL_PRETTY_FUNCTION_NAME, and STXXL_VERBOSE_MATERIALIZE.

template<typename Tp_ , typename AllocStr_ , typename SzTp_ , typename DiffTp_ , unsigned BlkSize_, typename PgTp_ , unsigned PgSz_, class StreamAlgorithm_ >

stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> stxxl::stream::materialize	(	StreamAlgorithm_ &	in,
		stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >	outbegin,
		stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >	outend,
		unsigned_type	nbuffers = 0
	)

Stores consecutively stream content to an output stxxl::vector iterator until end of the stream or end of the iterator range is reached.

Parameters

in	stream to be stored used as source
outbegin	output stxxl::vector iterator used as destination
outend	output end iterator, pointing beyond the output range
nbuffers	number of blocks used for overlapped writing (0 is default, which equals to (2 * number_of_disks)

Returns

value of the output iterator after all increments, i.e. points to the first unwritten value

Precondition

Output range is large enough to hold the all elements in the input stream

This function is useful when you do not know the length of the stream beforehand.

Definition at line 446 of file stream.h.

References stxxl::vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize >::bid(), stxxl::vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize >::block_externally_updated(), stxxl::vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize >::block_offset(), stxxl::vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize >::flush(), STXXL_PRETTY_FUNCTION_NAME, and STXXL_VERBOSE_MATERIALIZE.

template<typename Tp_ , typename AllocStr_ , typename SzTp_ , typename DiffTp_ , unsigned BlkSize_, typename PgTp_ , unsigned PgSz_, class StreamAlgorithm_ >

stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> stxxl::stream::materialize	(	StreamAlgorithm_ &	in,
		stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >	out,
		unsigned_type	nbuffers = 0
	)

Stores consecutively stream content to an output stxxl::vector iterator.

Parameters

in	stream to be stored used as source
out	output stxxl::vector iterator used as destination
nbuffers	number of blocks used for overlapped writing (0 is default, which equals to (2 * number_of_disks)

Returns

value of the output iterator after all increments, i.e. points to the first unwritten value

Precondition

Output (range) is large enough to hold the all elements in the input stream

Definition at line 526 of file stream.h.

References stxxl::vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize >::bid(), stxxl::vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize >::block_externally_updated(), stxxl::vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize >::block_offset(), stxxl::vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize >::flush(), STXXL_PRETTY_FUNCTION_NAME, and STXXL_VERBOSE_MATERIALIZE.

template<class RunsType_ , class CompareType_ , class AllocStr_ >

void stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::merge_recursively ( )

private

Definition at line 1310 of file sort_stream.h.

References stxxl::div_ceil(), stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::empty(), stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::initialize(), stxxl::make_bid_iterator(), stxxl::block_manager::new_blocks(), stxxl::optimal_merge_factor(), stxxl::STXXL_MIN(), and STXXL_MSG.

template<class InputIterator_ >

iterator2stream<InputIterator_> stxxl::stream::streamify	(	InputIterator_	begin,
		InputIterator_	end
	)

Input iterator range to stream converter.

Parameters

begin	iterator, pointing to the first value
end	iterator, pointing to the last + 1 position, i.e. beyond the range

Returns

an instance of a stream object

Examples:

examples/algo/copy_and_sort_file.cpp, and examples/applications/skew3.cpp.

Definition at line 116 of file stream.h.

Referenced by stxxl::random_shuffle(), and stxxl::sort().

template<typename Tp_ , typename AllocStr_ , typename SzTp_ , typename DiffTp_ , unsigned BlkSize_, typename PgTp_ , unsigned PgSz_>

vector_iterator2stream<stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> > stxxl::stream::streamify	(	stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >	begin,
		stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >	end,
		unsigned_type	nbuffers = 0
	)

Input external stxxl::vector iterator range to stream converter. It is more efficient than generic input iterator streamify thanks to use of overlapping.

Parameters

begin	iterator, pointing to the first value
end	iterator, pointing to the last + 1 position, i.e. beyond the range
nbuffers	number of blocks used for overlapped reading (0 is default, which equals to (2 * number_of_disks)

Returns

an instance of a stream object

Definition at line 224 of file stream.h.

References STXXL_VERBOSE1.

template<typename Tp_ , typename AllocStr_ , typename SzTp_ , typename DiffTp_ , unsigned BlkSize_, typename PgTp_ , unsigned PgSz_>

vector_iterator2stream<stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> > stxxl::stream::streamify	(	stxxl::const_vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >	begin,
		stxxl::const_vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >	end,
		unsigned_type	nbuffers = 0
	)

Input external stxxl::vector const iterator range to stream converter. It is more efficient than generic input iterator streamify thanks to use of overlapping.

Parameters

begin	const iterator, pointing to the first value
end	const iterator, pointing to the last + 1 position, i.e. beyond the range
nbuffers	number of blocks used for overlapped reading (0 is default, which equals to (2 * number_of_disks)

Returns

an instance of a stream object

Definition at line 252 of file stream.h.

References STXXL_VERBOSE1.

template<class Generator_ >

generator2stream<Generator_> stxxl::stream::streamify

(

Generator_

gen_

)

Adaptable generator to stream converter.

Parameters

gen_	generator object

Returns

an instance of a stream object

Definition at line 669 of file stream.h.

template<typename Tp_ , typename AllocStr_ , typename SzTp_ , typename DiffTp_ , unsigned BlkSize_, typename PgTp_ , unsigned PgSz_>

vector_iterator2stream_sr<stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> > stxxl::stream::streamify_sr	(	stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >	begin,
		stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >	end,
		unsigned_type	nbuffers = 0
	)

Version of streamify. Switches from vector_iterator2stream to iterator2stream for small ranges.

Definition at line 360 of file stream.h.

References STXXL_VERBOSE1.

template<typename Tp_ , typename AllocStr_ , typename SzTp_ , typename DiffTp_ , unsigned BlkSize_, typename PgTp_ , unsigned PgSz_>

vector_iterator2stream_sr<stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> > stxxl::stream::streamify_sr	(	stxxl::const_vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >	begin,
		stxxl::const_vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >	end,
		unsigned_type	nbuffers = 0
	)

Version of streamify. Switches from vector_iterator2stream to iterator2stream for small ranges.

Definition at line 374 of file stream.h.

References STXXL_VERBOSE1.