Merges sorted runs. More...

#include <sort_stream.h>

Inheritance diagram for stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >:

Collaboration diagram for stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >:

Public Types
typedef RunsType_	sorted_runs_type
typedef CompareType_	value_cmp
typedef AllocStr_	alloc_strategy
typedef sorted_runs_type::element_type	sorted_runs_data_type
typedef sorted_runs_data_type::size_type	size_type
typedef sorted_runs_data_type::run_type	run_type
typedef sorted_runs_data_type::block_type	block_type
typedef block_type	out_block_type
typedef run_type::value_type	trigger_entry_type
typedef block_prefetcher < block_type, typename run_type::iterator >	prefetcher_type
typedef run_cursor2 < block_type, prefetcher_type >	run_cursor_type
typedef sort_helper::run_cursor2_cmp < block_type, prefetcher_type, value_cmp >	run_cursor2_cmp_type
typedef loser_tree < run_cursor_type, run_cursor2_cmp_type >	loser_tree_type
typedef stxxl::int64	diff_type
typedef std::pair< typename block_type::iterator, typename block_type::iterator >	sequence
typedef std::vector< sequence > ::size_type	seqs_size_type
typedef sorted_runs_data_type::value_type	value_type
	Standard stream typedef.
Public Member Functions
	basic_runs_merger (value_cmp c, unsigned_type memory_to_use)
	Creates a runs merger object.
void	set_memory_to_use (unsigned_type memory_to_use)
	Set memory amount to use for the merger in bytes.
void	initialize (const sorted_runs_type &sruns)
	Initialize the runs merger object with a new round of sorted_runs.
void	deallocate ()
	Deallocate temporary structures freeing memory prior to next initialize()
bool	empty () const
	Standard stream method.
size_type	size () const
	Standard size method.
const value_type &	operator* () const
	Standard stream method.
const value_type *	operator-> () const
	Standard stream method.
basic_runs_merger &	operator++ ()
	Standard stream method.
virtual	~basic_runs_merger ()
	Destructor.
Private Member Functions
void	merge_recursively ()
void	deallocate_prefetcher ()
void	fill_buffer_block ()
Private Attributes
value_cmp	m_cmp
	comparator object to sort runs
unsigned_type	m_memory_to_use
	memory size in bytes to use
sorted_runs_type	m_sruns
	smart pointer to sorted_runs object
size_type	m_elements_remaining
	items remaining in input
out_block_type *	m_buffer_block
	memory buffer for merging from external streams
const value_type *	m_current_ptr
	pointer into current memory buffer: this is either m_buffer_block or the small_runs vector
const value_type *	m_current_end
	pointer into current memory buffer: end after range of current values
run_type	m_consume_seq
	sequence of block needed for merging
int_type *	m_prefetch_seq
	precalculated order of blocks in which they are prefetched
prefetcher_type *	m_prefetcher
	prefetcher object
loser_tree_type *	m_losers
	loser tree used for native merging

Detailed Description

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>
class stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >

Merges sorted runs.

Template Parameters:

RunsType_	type of the sorted runs, available as `runs_creator::sorted_runs_type` ,
CompareType_	type of comparison object used for merging
AllocStr_	allocation strategy used to allocate the blocks for storing intermediate results if several merge passes are required

Definition at line 914 of file sort_stream.h.