STXXL
1.4-dev
|
Merges sorted runs.
RunsType | type of the sorted runs, available as runs_creator::sorted_runs_type , |
CompareType | type of comparison object used for merging |
AllocStr | allocation 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.
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_type & | operator* () const |
Standard stream method. More... | |
basic_runs_merger & | operator++ () |
Standard stream method. More... | |
const value_type * | operator-> () 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 () |
![]() | |
noncopyable () | |
Private Attributes | |
out_block_type * | m_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_type * | m_current_end |
pointer into current memory buffer: end after range of current values More... | |
const value_type * | m_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_type * | m_losers |
loser tree used for native merging More... | |
unsigned_type | m_memory_to_use |
memory size in bytes to use More... | |
int_type * | m_prefetch_seq |
precalculated order of blocks in which they are prefetched More... | |
prefetcher_type * | m_prefetcher |
prefetcher object More... | |
sorted_runs_type | m_sruns |
smart pointer to sorted_runs object More... | |
typedef AllocStr stxxl::stream::basic_runs_merger< RunsType, CompareType, AllocStr >::alloc_strategy |
Definition at line 939 of file sort_stream.h.
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.
typedef stxxl::int64 stxxl::stream::basic_runs_merger< RunsType, CompareType, AllocStr >::diff_type |
Definition at line 951 of file sort_stream.h.
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.
typedef block_type stxxl::stream::basic_runs_merger< RunsType, CompareType, AllocStr >::out_block_type |
Definition at line 945 of file sort_stream.h.
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.
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.
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.
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.
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.
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.
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.
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.
typedef RunsType stxxl::stream::basic_runs_merger< RunsType, CompareType, AllocStr >::sorted_runs_type |
Definition at line 937 of file sort_stream.h.
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.
typedef CompareType stxxl::stream::basic_runs_merger< RunsType, CompareType, AllocStr >::value_cmp |
Definition at line 938 of file sort_stream.h.
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.
|
inline |
Creates a runs merger object.
c | comparison object |
memory_to_use | amount of memory available for the merger in bytes |
Definition at line 1101 of file sort_stream.h.
|
inlinevirtual |
Destructor.
Definition at line 1327 of file sort_stream.h.
|
inline |
Deallocate temporary structures freeing memory prior to next initialize().
Definition at line 1264 of file sort_stream.h.
|
inlineprivate |
Definition at line 1008 of file sort_stream.h.
|
inline |
Standard stream method.
Definition at line 1272 of file sort_stream.h.
Referenced by stxxl::stream::basic_runs_merger< RunsType, CompareType, AllocStr >::merge_recursively().
|
inlineprivate |
Definition at line 1023 of file sort_stream.h.
|
inline |
Initialize the runs merger object with a new round of sorted_runs.
Definition at line 1127 of file sort_stream.h.
Referenced by stxxl::stream::basic_runs_merger< RunsType, CompareType, AllocStr >::merge_recursively().
|
inline |
Standard stream method.
Definition at line 1284 of file sort_stream.h.
|
inline |
Standard stream method.
Definition at line 1297 of file sort_stream.h.
|
inline |
Standard stream method.
Definition at line 1291 of file sort_stream.h.
|
inline |
Set memory amount to use for the merger in bytes.
Definition at line 1121 of file sort_stream.h.
|
inline |
Standard size method.
Definition at line 1278 of file sort_stream.h.
|
private |
memory buffer for merging from external streams
Definition at line 973 of file sort_stream.h.
|
private |
comparator object to sort runs
Definition at line 961 of file sort_stream.h.
|
private |
sequence of block needed for merging
Definition at line 982 of file sort_stream.h.
|
private |
pointer into current memory buffer: end after range of current values
Definition at line 979 of file sort_stream.h.
|
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.
|
private |
items remaining in input
Definition at line 970 of file sort_stream.h.
|
private |
loser tree used for native merging
Definition at line 991 of file sort_stream.h.
|
private |
memory size in bytes to use
Definition at line 964 of file sort_stream.h.
|
private |
precalculated order of blocks in which they are prefetched
Definition at line 985 of file sort_stream.h.
|
private |
prefetcher object
Definition at line 988 of file sort_stream.h.
|
private |
smart pointer to sorted_runs object
Definition at line 967 of file sort_stream.h.