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

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
RunsTypetype of the sorted runs, available as runs_creator::sorted_runs_type ,
CompareTypetype of comparison object used for merging
AllocStrallocation strategy used to allocate the blocks for storing intermediate results if several merge passes are required

Definition at line 934 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_typeoperator* () const
 Standard stream method. More...
 
basic_runs_mergeroperator++ ()
 Standard stream method. More...
 
const value_typeoperator-> () 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_typem_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_typem_current_end
 pointer into current memory buffer: end after range of current values More...
 
const value_typem_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_typem_losers
 loser tree used for native merging More...
 
unsigned_type m_memory_to_use
 memory size in bytes to use More...
 
int_typem_prefetch_seq
 precalculated order of blocks in which they are prefetched More...
 
prefetcher_typem_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 939 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 944 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 951 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 950 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 945 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 947 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 949 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 948 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 943 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 953 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 952 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 942 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 941 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 937 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 946 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 938 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 957 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
ccomparison object
memory_to_useamount of memory available for the merger in bytes

Definition at line 1099 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 1325 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 1262 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 1008 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 1270 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 1023 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 1125 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 1282 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 1295 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 1289 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 1119 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 1276 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 973 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 961 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 982 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 979 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 976 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 970 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 991 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 964 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 985 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 988 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 967 of file sort_stream.h.


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