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 414 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 element_iterator_traits < block_type, external_size_type > ::element_iterator	element_iterator

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...

external_size_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...

internal_size_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 424 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 422 of file sort_stream.h.

template<class ValueType , class CompareType , unsigned BlockSize, class AllocStr >

typedef element_iterator_traits<block_type, external_size_type>::element_iterator stxxl::stream::runs_creator< use_push< ValueType >, CompareType, BlockSize, AllocStr >::element_iterator

Definition at line 430 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 428 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 436 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 426 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 427 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 425 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 423 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 545 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 565 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 590 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 572 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 682 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 497 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 604 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 474 of file sort_stream.h.

References curr, and 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 688 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 620 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 662 of file sort_stream.h.

References STXXL_MSG.

template<class ValueType , class CompareType , unsigned BlockSize, class AllocStr >

external_size_type stxxl::stream::runs_creator< use_push< ValueType >, CompareType, BlockSize, AllocStr >::size ( ) const

inline

number of items currently inserted.

Definition at line 676 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 489 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 460 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 463 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 434 of file sort_stream.h.

template<class ValueType , class CompareType , unsigned BlockSize, class AllocStr >

internal_size_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 457 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 454 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 448 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 442 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 445 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 439 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 451 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 467 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 470 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 >