STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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
srunssorted runs object
cmpcomparison 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
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
ininput 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
instream to be stored used as source
outoutput 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
instream to be stored used as source
outbeginoutput iterator used as destination
outendoutput 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
instream to be stored used as source
outbeginoutput stxxl::vector iterator used as destination
outendoutput end iterator, pointing beyond the output range
nbuffersnumber 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
instream to be stored used as source
outoutput stxxl::vector iterator used as destination
nbuffersnumber 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 InputIterator >
iterator2stream<InputIterator> stxxl::stream::streamify ( InputIterator  begin,
InputIterator  end 
)

Input iterator range to stream converter.

Parameters
beginiterator, pointing to the first value
enditerator, 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
beginiterator, pointing to the first value
enditerator, pointing to the last + 1 position, i.e. beyond the range
nbuffersnumber 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
beginconst iterator, pointing to the first value
endconst iterator, pointing to the last + 1 position, i.e. beyond the range
nbuffersnumber 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.