STXXL  1.4.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
stxxl::stream::runs_creator< use_push< ValueType >, CompareType, BlockSize, AllocStr > Class Template Reference

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
ValueTypetype of values (parameter for use_push strategy)
CompareTypetype of comparison object used for sorting the runs
BlockSizesize of blocks used to store the runs
AllocStrfunctor 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_typecmp () 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_typeresult ()
 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_typem_blocks1
 accumulation buffer of size m_m2 blocks, half the available memory size More...
 
block_typem_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_ptrm_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
cmpcomparator object
memory_to_usememory 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
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 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
valvalue 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: