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

#include <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 CompareType_	cmp_type
typedef ValueType_	value_type
typedef typed_block < BlockSize_, value_type >	block_type
typedef sort_helper::trigger_entry < block_type >	trigger_entry_type
typedef sorted_runs < trigger_entry_type, cmp_type >	sorted_runs_data_type
typedef counting_ptr < sorted_runs_data_type >	sorted_runs_type
typedef sorted_runs_type	result_type
Public Member Functions
	runs_creator (CompareType_ cmp, unsigned_type memory_to_use)
	Creates the object.
	~runs_creator ()
void	clear ()
	Clear current state and remove all items.
void	allocate ()
	Allocates input buffers and clears result.
void	deallocate ()
	Deallocates input buffers but not the current result.
void	push (const value_type &val)
	Adds new element to the sorter.
sorted_runs_type &	result ()
	Returns the sorted runs object.
unsigned_type	size () const
	number of items currently inserted.
const cmp_type &	cmp () const
	return comparator object
unsigned_type	memory_used () const
	return memory size used (in bytes)
Protected Member Functions
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
void	sort_run (block_type *run, unsigned_type elements)
	Sort a specific run, contained in a sequences of blocks.
void	compute_result ()
Private Types
typedef sorted_runs_data_type::run_type	run_type
Private Attributes
CompareType_	m_cmp
	comparator object to sort runs
sorted_runs_type	m_result
	stores the result (sorted runs) in a reference counted object
const unsigned_type	m_memory_to_use
	memory size in bytes to use
const unsigned_type	m_memsize
	memory size in numberr of blocks for internal use
const unsigned_type	m_m2
	m_memsize / 2
bool	m_result_computed
	true after the result() method was called for the first time
const unsigned_type	m_el_in_run
	total number of elements in a run
unsigned_type	m_cur_el
	current number of elements in the run m_blocks1
block_type *	m_blocks1
	accumulation buffer of size m_m2 blocks, half the available memory size
block_type *	m_blocks2
	accumulation buffer that is currently being written to disk
request_ptr *	m_write_reqs
	reference to write requests transporting the last accumulation buffer to disk
run_type	run
	run object containing block ids of the run being written to disk

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 404 of file sort_stream.h.

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 414 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 412 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 418 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 424 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 416 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 417 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 415 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 413 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:

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

Definition at line 532 of file sort_stream.h.

References 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 550 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 575 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 557 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 667 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 ( ) [inline, protected]

Definition at line 484 of file sort_stream.h.

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

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 589 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
	)		`[inline, protected]`

fill the rest of the block with max values

Definition at line 461 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 673 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 605 of file sort_stream.h.

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

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 647 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 661 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
	)		`[inline, protected]`

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

Definition at line 476 of file sort_stream.h.

References 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 448 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 451 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 422 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 445 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 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_m2 [private]

m_memsize / 2

Definition at line 436 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 430 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 433 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 427 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 439 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 454 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 457 of file sort_stream.h.

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

include/stxxl/bits/stream/sort_stream.h

Public Types

Public Member Functions

Protected Member Functions

Private Types

Private Attributes

Detailed Description

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

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