Detailed Description

template<class ValueType_, class CompareType_, unsigned BlockSize_, class AllocStr_>
class stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >

Forms sorted runs of elements passed in push() method.

A specialization of runs_creator that allows to create sorted runs data structure usable for runs_merger from elements passed in sorted push() method.

Template Parameters

ValueType_	type of values (parameter for `use_push` strategy)
CompareType_	type of comparison object used for sorting the runs
BlockSize_	size of blocks used to store the runs
AllocStr_	functor that defines allocation strategy for the runs

Definition at line 400 of file sort_stream.h.

Inheritance diagram for stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >:

Collaboration diagram for stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >:

Public Types
typedef typed_block < BlockSize_, value_type >	block_type

typedef CompareType_	cmp_type

typedef sorted_runs_type	result_type

typedef sorted_runs < trigger_entry_type, cmp_type >	sorted_runs_data_type

typedef counting_ptr < sorted_runs_data_type >	sorted_runs_type

typedef sort_helper::trigger_entry < block_type >	trigger_entry_type

typedef ValueType_	value_type

Public Member Functions
	runs_creator (CompareType_ cmp, unsigned_type memory_to_use)
	Creates the object. More...

	~runs_creator ()

void	allocate ()
	Allocates input buffers and clears result. More...

void	clear ()
	Clear current state and remove all items. More...

const cmp_type &	cmp () const
	return comparator object. More...

void	deallocate ()
	Deallocates input buffers but not the current result. More...

unsigned_type	memory_used () const
	return memory size used (in bytes). More...

void	push (const value_type &val)
	Adds new element to the sorter. More...

sorted_runs_type &	result ()
	Returns the sorted runs object. More...

unsigned_type	size () const
	number of items currently inserted. More...

Protected Member Functions
void	compute_result ()

void	fill_with_max_value (block_type *blocks, unsigned_type num_blocks, unsigned_type first_idx)
	fill the rest of the block with max values More...

void	sort_run (block_type *run, unsigned_type elements)
	Sort a specific run, contained in a sequences of blocks. More...

Private Types
typedef sorted_runs_data_type::run_type	run_type

Private Attributes
block_type *	m_blocks1
	accumulation buffer of size m_m2 blocks, half the available memory size More...

block_type *	m_blocks2
	accumulation buffer that is currently being written to disk More...

CompareType_	m_cmp
	comparator object to sort runs More...

unsigned_type	m_cur_el
	current number of elements in the run m_blocks1 More...

const unsigned_type	m_el_in_run
	total number of elements in a run More...

const unsigned_type	m_m2
	m_memsize / 2 More...

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

const unsigned_type	m_memsize
	memory size in numberr of blocks for internal use More...

sorted_runs_type	m_result
	stores the result (sorted runs) in a reference counted object More...

bool	m_result_computed
	true after the result() method was called for the first time More...

request_ptr *	m_write_reqs
	reference to write requests transporting the last accumulation buffer to disk More...

run_type	run
	run object containing block ids of the run being written to disk More...

Additional Inherited Members
Private Member Functions inherited from stxxl::noncopyable
	noncopyable ()

Member Typedef Documentation

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

typedef typed_block<BlockSize_, value_type> stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::block_type

Definition at line 410 of file sort_stream.h.

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

typedef CompareType_ stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::cmp_type

Definition at line 408 of file sort_stream.h.

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

typedef sorted_runs_type stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::result_type

Definition at line 414 of file sort_stream.h.

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

typedef sorted_runs_data_type::run_type stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::run_type

private

Definition at line 420 of file sort_stream.h.

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

typedef sorted_runs<trigger_entry_type, cmp_type> stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::sorted_runs_data_type

Definition at line 412 of file sort_stream.h.

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

typedef counting_ptr<sorted_runs_data_type> stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::sorted_runs_type

Definition at line 413 of file sort_stream.h.

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

typedef sort_helper::trigger_entry<block_type> stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::trigger_entry_type

Definition at line 411 of file sort_stream.h.

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

typedef ValueType_ stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::value_type

Definition at line 409 of file sort_stream.h.

Constructor & Destructor Documentation

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::runs_creator	(	CompareType_	cmp,
		unsigned_type	memory_to_use
	)

inline

Creates the object.

Parameters

cmp	comparator object
memory_to_use	memory amount that is allowed to used by the sorter in bytes

Definition at line 528 of file sort_stream.h.

References stxxl::sort_memory_usage_factor(), and stxxl::sort_helper::verify_sentinel_strict_weak_ordering().

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::~runs_creator ( )

inline

Definition at line 546 of file sort_stream.h.

Member Function Documentation

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

void stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::allocate ( )

inline

Allocates input buffers and clears result.

Definition at line 571 of file sort_stream.h.

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

void stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::clear ( )

inline

Clear current state and remove all items.

Definition at line 553 of file sort_stream.h.

References stxxl::stream::sorted_runs< TriggerEntryType, CompareType >::clear().

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

const cmp_type& stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::cmp ( ) const

inline

return comparator object.

Definition at line 663 of file sort_stream.h.

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

void stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::compute_result ( )

inlineprotected

Definition at line 480 of file sort_stream.h.

References stxxl::div_ceil(), stxxl::make_bid_iterator(), stxxl::block_manager::new_blocks(), and STXXL_VERBOSE1.

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

void stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::deallocate ( )

inline

Deallocates input buffers but not the current result.

Definition at line 585 of file sort_stream.h.

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

void stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::fill_with_max_value	(	block_type *	blocks,
		unsigned_type	num_blocks,
		unsigned_type	first_idx
	)

inlineprotected

fill the rest of the block with max values

Definition at line 457 of file sort_stream.h.

References stxxl::make_element_iterator().

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

unsigned_type stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::memory_used ( ) const

inline

return memory size used (in bytes).

Definition at line 669 of file sort_stream.h.

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

void stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::push ( const value_type & val )

inline

Adds new element to the sorter.

Parameters

val	value to be added

Definition at line 601 of file sort_stream.h.

References stxxl::div_ceil(), LIKELY, stxxl::make_bid_iterator(), and stxxl::block_manager::new_blocks().

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

sorted_runs_type& stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::result ( )

inline

Returns the sorted runs object.

Returns: Sorted runs object.

Remarks: Returned object is intended to be used by runs_merger object as input

Definition at line 643 of file sort_stream.h.

References STXXL_MSG.

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

unsigned_type stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::size ( ) const

inline

number of items currently inserted.

Definition at line 657 of file sort_stream.h.

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

void stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::sort_run	(	block_type *	run,
		unsigned_type	elements
	)

inlineprotected

Sort a specific run, contained in a sequences of blocks.

Definition at line 472 of file sort_stream.h.

References stxxl::check_sort_settings(), stxxl::make_element_iterator(), and stxxl::sort().

Member Data Documentation

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

block_type* stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::m_blocks1

private

accumulation buffer of size m_m2 blocks, half the available memory size

Definition at line 444 of file sort_stream.h.

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

block_type* stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::m_blocks2

private

accumulation buffer that is currently being written to disk

Definition at line 447 of file sort_stream.h.

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

CompareType_ stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::m_cmp

private

comparator object to sort runs

Definition at line 418 of file sort_stream.h.

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

unsigned_type stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::m_cur_el

private

current number of elements in the run m_blocks1

Definition at line 441 of file sort_stream.h.

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

const unsigned_type stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::m_el_in_run

private

total number of elements in a run

Definition at line 438 of file sort_stream.h.

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

const unsigned_type stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::m_m2

private

m_memsize / 2

Definition at line 432 of file sort_stream.h.

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

const unsigned_type stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::m_memory_to_use

private

memory size in bytes to use

Definition at line 426 of file sort_stream.h.

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

const unsigned_type stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::m_memsize

private

memory size in numberr of blocks for internal use

Definition at line 429 of file sort_stream.h.

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

sorted_runs_type stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::m_result

private

stores the result (sorted runs) in a reference counted object

Definition at line 423 of file sort_stream.h.

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

bool stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::m_result_computed

private

true after the result() method was called for the first time

Definition at line 435 of file sort_stream.h.

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

request_ptr* stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::m_write_reqs

private

reference to write requests transporting the last accumulation buffer to disk

Definition at line 450 of file sort_stream.h.

template<class ValueType_ , class CompareType_ , unsigned BlockSize_, class AllocStr_ >

run_type stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >::run

private

run object containing block ids of the run being written to disk

Definition at line 453 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 ValueType_, class CompareType_, unsigned BlockSize_, class AllocStr_> class stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >

Public Types

Public Member Functions

Protected Member Functions

Private Types

Private Attributes

Additional Inherited Members

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class ValueType_, class CompareType_, unsigned BlockSize_, class AllocStr_>
class stxxl::stream::runs_creator< use_push< ValueType_ >, CompareType_, BlockSize_, AllocStr_ >