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 912 of file 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 AllocStr_	alloc_strategy

typedef sorted_runs_data_type::block_type	block_type

typedef stxxl::int64	diff_type

typedef loser_tree < run_cursor_type, run_cursor2_cmp_type >	loser_tree_type

typedef block_type	out_block_type

typedef block_prefetcher < block_type, typename run_type::iterator >	prefetcher_type

typedef sort_helper::run_cursor2_cmp < block_type, prefetcher_type, value_cmp >	run_cursor2_cmp_type

typedef run_cursor2 < block_type, prefetcher_type >	run_cursor_type

typedef sorted_runs_data_type::run_type	run_type

typedef std::vector< sequence > ::size_type	seqs_size_type

typedef std::pair< typename block_type::iterator, typename block_type::iterator >	sequence

typedef sorted_runs_data_type::size_type	size_type

typedef sorted_runs_type::element_type	sorted_runs_data_type

typedef RunsType_	sorted_runs_type

typedef run_type::value_type	trigger_entry_type

typedef CompareType_	value_cmp

typedef sorted_runs_data_type::value_type	value_type
	Standard stream typedef. More...

Public Member Functions
	basic_runs_merger (value_cmp c, unsigned_type memory_to_use)
	Creates a runs merger object. More...

virtual	~basic_runs_merger ()
	Destructor. More...

void	deallocate ()
	Deallocate temporary structures freeing memory prior to next initialize(). More...

bool	empty () const
	Standard stream method. More...

void	initialize (const sorted_runs_type &sruns)
	Initialize the runs merger object with a new round of sorted_runs. More...

const value_type &	operator* () const
	Standard stream method. More...

basic_runs_merger &	operator++ ()
	Standard stream method. More...

const value_type *	operator-> () const
	Standard stream method. More...

void	set_memory_to_use (unsigned_type memory_to_use)
	Set memory amount to use for the merger in bytes. More...

size_type	size () const
	Standard size method. More...

Private Member Functions
void	deallocate_prefetcher ()

void	fill_buffer_block ()

void	merge_recursively ()

Private Member Functions inherited from stxxl::noncopyable
	noncopyable ()

Private Attributes
out_block_type *	m_buffer_block
	memory buffer for merging from external streams More...

value_cmp	m_cmp
	comparator object to sort runs More...

run_type	m_consume_seq
	sequence of block needed for merging More...

const value_type *	m_current_end
	pointer into current memory buffer: end after range of current values More...

const value_type *	m_current_ptr
	pointer into current memory buffer: this is either m_buffer_block or the small_runs vector More...

size_type	m_elements_remaining
	items remaining in input More...

loser_tree_type *	m_losers
	loser tree used for native merging More...

unsigned_type	m_memory_to_use
	memory size in bytes to use More...

int_type *	m_prefetch_seq
	precalculated order of blocks in which they are prefetched More...

prefetcher_type *	m_prefetcher
	prefetcher object More...

sorted_runs_type	m_sruns
	smart pointer to sorted_runs object More...

Member Typedef Documentation

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef AllocStr_ stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::alloc_strategy

Definition at line 917 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef sorted_runs_data_type::block_type stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::block_type

Definition at line 922 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef stxxl::int64 stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::diff_type

Definition at line 929 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef loser_tree<run_cursor_type, run_cursor2_cmp_type> stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::loser_tree_type

Definition at line 928 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef block_type stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::out_block_type

Definition at line 923 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef block_prefetcher<block_type, typename run_type::iterator> stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::prefetcher_type

Definition at line 925 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef sort_helper::run_cursor2_cmp<block_type, prefetcher_type, value_cmp> stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::run_cursor2_cmp_type

Definition at line 927 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef run_cursor2<block_type, prefetcher_type> stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::run_cursor_type

Definition at line 926 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef sorted_runs_data_type::run_type stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::run_type

Definition at line 921 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef std::vector<sequence>::size_type stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::seqs_size_type

Definition at line 931 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef std::pair<typename block_type::iterator, typename block_type::iterator> stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::sequence

Definition at line 930 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef sorted_runs_data_type::size_type stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::size_type

Definition at line 920 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef sorted_runs_type::element_type stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::sorted_runs_data_type

Definition at line 919 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef RunsType_ stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::sorted_runs_type

Definition at line 915 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef run_type::value_type stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::trigger_entry_type

Definition at line 924 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef CompareType_ stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::value_cmp

Definition at line 916 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef sorted_runs_data_type::value_type stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::value_type

Standard stream typedef.

Definition at line 935 of file sort_stream.h.

Constructor & Destructor Documentation

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::basic_runs_merger	(	value_cmp	c,
		unsigned_type	memory_to_use
	)

inline

Creates a runs merger object.

Parameters

c	comparison object
memory_to_use	amount of memory available for the merger in bytes

Definition at line 1077 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

virtual stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::~basic_runs_merger ( )

inlinevirtual

Destructor.

Remarks: Deallocates blocks of the input sorted runs object

Definition at line 1300 of file sort_stream.h.

Member Function Documentation

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

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

inline

Deallocate temporary structures freeing memory prior to next initialize().

Definition at line 1237 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

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

inlineprivate

Definition at line 986 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

bool stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::empty ( ) const

inline

Standard stream method.

Definition at line 1245 of file sort_stream.h.

Referenced by stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::merge_recursively().

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

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

inlineprivate

Definition at line 1001 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

void stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::initialize ( const sorted_runs_type & sruns )

inline

Initialize the runs merger object with a new round of sorted_runs.

Definition at line 1103 of file sort_stream.h.

Referenced by stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::merge_recursively().

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

const value_type& stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::operator* ( ) const

inline

Standard stream method.

Definition at line 1257 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

basic_runs_merger& stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::operator++ ( )

inline

Standard stream method.

Definition at line 1270 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

const value_type* stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::operator-> ( ) const

inline

Standard stream method.

Definition at line 1264 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

void stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::set_memory_to_use ( unsigned_type memory_to_use )

inline

Set memory amount to use for the merger in bytes.

Definition at line 1097 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

size_type stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::size ( ) const

inline

Standard size method.

Definition at line 1251 of file sort_stream.h.

Member Data Documentation

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

out_block_type* stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::m_buffer_block

private

memory buffer for merging from external streams

Definition at line 951 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

value_cmp stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::m_cmp

private

comparator object to sort runs

Definition at line 939 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

run_type stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::m_consume_seq

private

sequence of block needed for merging

Definition at line 960 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

const value_type* stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::m_current_end

private

pointer into current memory buffer: end after range of current values

Definition at line 957 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

const value_type* stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::m_current_ptr

private

pointer into current memory buffer: this is either m_buffer_block or the small_runs vector

Definition at line 954 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

size_type stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::m_elements_remaining

private

items remaining in input

Definition at line 948 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

loser_tree_type* stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::m_losers

private

loser tree used for native merging

Definition at line 969 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

unsigned_type stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::m_memory_to_use

private

memory size in bytes to use

Definition at line 942 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

int_type* stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::m_prefetch_seq

private

precalculated order of blocks in which they are prefetched

Definition at line 963 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

prefetcher_type* stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::m_prefetcher

private

prefetcher object

Definition at line 966 of file sort_stream.h.

template<class RunsType_, class CompareType_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

sorted_runs_type stxxl::stream::basic_runs_merger< RunsType_, CompareType_, AllocStr_ >::m_sruns

private

smart pointer to sorted_runs object

Definition at line 945 of file sort_stream.h.

The documentation for this class was generated from the following file:

include/stxxl/bits/stream/sort_stream.h

Detailed Description

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

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

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