Classes
class	stxxl::stream::basic_runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >
	Forms sorted runs of data from a stream. More...
class	stxxl::stream::runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >
	Forms sorted runs of data from a stream. More...
struct	stxxl::stream::use_push< ValueType_ >
	Input strategy for `runs_creator` class. More...
class	stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >
	Forms sorted runs of elements passed in push() method. More...
struct	stxxl::stream::from_sorted_sequences< ValueType_ >
	Input strategy for `runs_creator` class. 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::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >
	Merges sorted runs. 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...
class	stxxl::stream::compute_sorted_runs_type< ValueType_, BlockSize_ >
	Computes sorted runs type from value type and block size. More...
struct	stxxl::stream::sorted_runs< TriggerEntryType, CompareType_ >
	All sorted runs of a sort operation. 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...
struct	stxxl::stream::streamify_traits< InputIterator_ >
	Traits class of `streamify` function. 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...
struct	stxxl::stream::streamify_traits< stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > >
struct	stxxl::stream::streamify_traits< stxxl::const_vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > >
class	stxxl::stream::vector_iterator2stream_sr< InputIterator_ >
	Version of `iterator2stream`. Switches between `vector_iterator2stream` and `iterator2stream` . 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...
struct	stxxl::stream::Stopper
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_, Stopper, Stopper, Stopper, Stopper, Stopper >
	Processes an input stream 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_, Input2_, Input3_, Stopper, Stopper, Stopper >
	Processes 3 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_, Input4_, Input5_, Stopper >
	Processes 5 input streams using given operation functor. 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_, Stopper, Stopper, Stopper, Stopper >
	Creates stream of 2-tuples (pairs) from 2 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_, Input3_, Input4_, Stopper, Stopper >
	Creates stream of 4-tuples from 4 input streams. More...
class	stxxl::stream::make_tuple< Input1_, Input2_, Input3_, Input4_, Input5_, Stopper >
	Creates stream of 5-tuples from 5 input streams. 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` .
template<class InputIterator_ >
iterator2stream< InputIterator_ >	stxxl::stream::streamify (InputIterator_ begin, InputIterator_ end)
	Input iterator range to stream converter.
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.
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.
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.
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.
template<class OutputIterator_ , class StreamAlgorithm_ >
OutputIterator_	stxxl::stream::materialize (StreamAlgorithm_ &in, OutputIterator_ out)
	Stores consecutively stream content to an output iterator.
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.
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.
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.
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.
template<class Generator_ >
generator2stream< Generator_ >	stxxl::stream::streamify (Generator_ gen_)
	Adaptable generator to stream converter.
void	stxxl::stream::basic_runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >::compute_result ()
	Finish the results, i. e. create all runs.
void	stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::merge_recursively ()

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

=

Examples:: stream/test_push_sort.cpp.

Definition at line 855 of file sort_stream.h.

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

Referenced by main().

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 161 of file sort_stream.h.

References stxxl::element_block< T, Size_ >::begin(), stxxl::block_manager::delete_blocks(), stxxl::div_ceil(), stxxl::make_bid_iterator(), stxxl::block_manager::new_blocks(), run(), stxxl::sort(), std::swap(), stxxl::request_interface::wait(), stxxl::wait_all(), and stxxl::typed_block< RawSize_, T_, NRef_, InfoType_ >::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 604 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:: algo/copy_and_sort_file.cpp, algo/test_parallel_sort.cpp, containers/berkeley_db_benchmark.cpp, stream/test_naive_transpose.cpp, and stream/test_stream.cpp.

Definition at line 395 of file stream.h.

References STXXL_PRETTY_FUNCTION_NAME, and STXXL_VERBOSE_MATERIALIZE.

Referenced by linear_sort_streamed(), main(), run_bdb_btree_big(), run_stxxl_map_big(), and 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 418 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 445 of file stream.h.

References stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >::bid(), stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >::block_externally_updated(), stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >::block_offset(), 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 525 of file stream.h.

References stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >::bid(), stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >::block_externally_updated(), stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >::block_offset(), 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 1312 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(), STXXL_MSG, and std::swap().

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:: algo/copy_and_sort_file.cpp, algo/test_parallel_sort.cpp, stream/test_naive_transpose.cpp, and stream/test_stream.cpp.

Definition at line 115 of file stream.h.

Referenced by linear_sort_streamed(), main(), 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 223 of file stream.h.

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 251 of file stream.h.

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 667 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 359 of file stream.h.

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 373 of file stream.h.

Classes

Functions

Detailed Description

Function Documentation