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. 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, RunsCreatorType >
	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< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize > >
struct	stxxl::stream::streamify_traits< stxxl::vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize > >
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 ValueType , typename AllocStr , typename SizeType , typename DiffType , unsigned BlockSize, typename PagerType , unsigned PageSize, class StreamAlgorithm >
stxxl::vector_iterator < ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize >	stxxl::stream::materialize (StreamAlgorithm &in, stxxl::vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize > outbegin, stxxl::vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize > 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 ValueType , typename AllocStr , typename SizeType , typename DiffType , unsigned BlockSize, typename PagerType , unsigned PageSize, class StreamAlgorithm >
stxxl::vector_iterator < ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize >	stxxl::stream::materialize (StreamAlgorithm &in, stxxl::vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize > 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 ValueType , typename AllocStr , typename SizeType , typename DiffType , unsigned BlockSize, typename PagerType , unsigned PageSize>
vector_iterator2stream < stxxl::vector_iterator < ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize > >	stxxl::stream::streamify (stxxl::vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize > begin, stxxl::vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize > 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 ValueType , typename AllocStr , typename SizeType , typename DiffType , unsigned BlockSize, typename PagerType , unsigned PageSize>
vector_iterator2stream < stxxl::const_vector_iterator < ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize > >	stxxl::stream::streamify (stxxl::const_vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize > begin, stxxl::const_vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize > 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 ValueType , typename AllocStr , typename SizeType , typename DiffType , unsigned BlockSize, typename PagerType , unsigned PageSize>
vector_iterator2stream_sr < stxxl::vector_iterator < ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize > >	stxxl::stream::streamify_sr (stxxl::vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize > begin, stxxl::vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize > end, unsigned_type nbuffers=0)
	Version of streamify. Switches from vector_iterator2stream to iterator2stream for small ranges. More...
template<typename ValueType , typename AllocStr , typename SizeType , typename DiffType , unsigned BlockSize, typename PagerType , unsigned PageSize>
vector_iterator2stream_sr < stxxl::const_vector_iterator < ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize > >	stxxl::stream::streamify_sr (stxxl::const_vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize > begin, stxxl::const_vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize > 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 873 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 168 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 640 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 428 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 450 of file stream.h.

References STXXL_PRETTY_FUNCTION_NAME, and STXXL_VERBOSE_MATERIALIZE.

template<typename ValueType , typename AllocStr , typename SizeType , typename DiffType , unsigned BlockSize, typename PagerType , unsigned PageSize, class StreamAlgorithm >

stxxl::vector_iterator<ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize> stxxl::stream::materialize	(	StreamAlgorithm &	in,
		stxxl::vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize >	outbegin,
		stxxl::vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize >	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 479 of file stream.h.

References stxxl::buf_ostream< BlockType, BidIteratorType >::flush(), STXXL_PRETTY_FUNCTION_NAME, and STXXL_VERBOSE_MATERIALIZE.

template<typename ValueType , typename AllocStr , typename SizeType , typename DiffType , unsigned BlockSize, typename PagerType , unsigned PageSize, class StreamAlgorithm >

stxxl::vector_iterator<ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize> stxxl::stream::materialize	(	StreamAlgorithm &	in,
		stxxl::vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize >	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 561 of file stream.h.

References stxxl::buf_ostream< BlockType, BidIteratorType >::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 1334 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 93 of file stream.h.

Referenced by stxxl::hash_map::hash_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::insert(), and stxxl::random_shuffle().

template<typename ValueType , typename AllocStr , typename SizeType , typename DiffType , unsigned BlockSize, typename PagerType , unsigned PageSize>

vector_iterator2stream< stxxl::vector_iterator<ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize> > stxxl::stream::streamify	(	stxxl::vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize >	begin,
		stxxl::vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize >	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 212 of file stream.h.

References STXXL_VERBOSE1.

template<typename ValueType , typename AllocStr , typename SizeType , typename DiffType , unsigned BlockSize, typename PagerType , unsigned PageSize>

vector_iterator2stream< stxxl::const_vector_iterator<ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize> > stxxl::stream::streamify	(	stxxl::const_vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize >	begin,
		stxxl::const_vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize >	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 255 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 703 of file stream.h.

template<typename ValueType , typename AllocStr , typename SizeType , typename DiffType , unsigned BlockSize, typename PagerType , unsigned PageSize>

vector_iterator2stream_sr< stxxl::vector_iterator<ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize> > stxxl::stream::streamify_sr	(	stxxl::vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize >	begin,
		stxxl::vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize >	end,
		unsigned_type	nbuffers = 0
	)

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

Definition at line 380 of file stream.h.

References STXXL_VERBOSE1.

template<typename ValueType , typename AllocStr , typename SizeType , typename DiffType , unsigned BlockSize, typename PagerType , unsigned PageSize>

vector_iterator2stream_sr< stxxl::const_vector_iterator<ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize> > stxxl::stream::streamify_sr	(	stxxl::const_vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize >	begin,
		stxxl::const_vector_iterator< ValueType, AllocStr, SizeType, DiffType, BlockSize, PagerType, PageSize >	end,
		unsigned_type	nbuffers = 0
	)

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

Definition at line 403 of file stream.h.

References STXXL_VERBOSE1.