STXXL
1.4-dev
|
External merger, based on the loser tree data structure.
Arity | maximum arity of merger, does not need to be a power of 2 |
Definition at line 38 of file pq_ext_merger.h.
Classes | |
struct | sequence_state |
Public Types | |
enum | { arity = Arity, max_arity = 1UL << (LOG2<Arity>::ceil) } |
typedef AllocStr | alloc_strategy |
typedef std::deque< bid_type > | bid_container_type |
typedef block_type::bid_type | bid_type |
typedef BlockType | block_type |
class is parameterized by the block of the external arrays More... | |
typedef CompareType | compare_type |
typedef read_write_pool < block_type > | pool_type |
typedef ext_merger< BlockType, CompareType, Arity, AllocStr > | self_type |
our type More... | |
typedef sequence_state | sequence_type |
type of sequences in which the values are stored: external arrays More... | |
typedef external_size_type | size_type |
size type of total number of item in merger More... | |
typedef loser_tree< self_type, CompareType, Arity > | tree_type |
type of embedded loser tree More... | |
typedef block_type::value_type | value_type |
Public Member Functions | |
ext_merger (const compare_type &c=compare_type()) | |
virtual | ~ext_merger () |
template<class Merger > | |
void | append_merger (Merger &another_merger, size_type segment_size) |
Merge all items from another merger and insert the resulting external array into the merger. Requires: is_space_available() == 1. More... | |
void | insert_segment (bid_container_type &bidlist, block_type *first_block, unsigned_type first_size, unsigned_type slot) |
bool | is_sentinel (const value_type &a) const |
True if a is the sentinel value. More... | |
bool | is_space_available () const |
Whether there is still space for new array. More... | |
unsigned_type | mem_cons () const |
template<class OutputIterator > | |
void | multi_merge (OutputIterator begin, OutputIterator end) |
void | set_pool (pool_type *pool_) |
size_type | size () const |
Return the number of items in the arrays. More... | |
Interface for loser_tree | |
bool | is_array_empty (unsigned_type slot) const |
is this segment empty ? More... | |
bool | is_array_allocated (unsigned_type slot) const |
Is this segment allocated? Otherwise it's empty, already on the stack of free segment indices and can be reused. More... | |
sequence_type & | get_array (unsigned_type slot) |
Return the item sequence of the given slot. More... | |
void | swap_arrays (unsigned_type a, unsigned_type b) |
Swap contents of arrays a and b. More... | |
void | make_array_sentinel (unsigned_type a) |
Set a usually empty array to the sentinel. More... | |
void | free_array (unsigned_type slot) |
free an empty segment. More... | |
void | prefetch_arrays () |
Hint (prefetch) first non-internal (actually second) block of each sequence. More... | |
Protected Member Functions | |
void | init () |
Protected Attributes | |
size_type | m_size |
total number of elements stored More... | |
pool_type * | pool |
read and writer block pool More... | |
block_type * | sentinel_block |
a memory block filled with sentinel values More... | |
sequence_state | states [max_arity] |
sequence including current position, dereference gives current element More... | |
tree_type | tree |
loser tree instance More... | |
Additional Inherited Members | |
Private Member Functions inherited from stxxl::noncopyable | |
noncopyable () | |
typedef AllocStr stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::alloc_strategy |
Definition at line 48 of file pq_ext_merger.h.
typedef std::deque<bid_type> stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::bid_container_type |
Definition at line 53 of file pq_ext_merger.h.
typedef block_type::bid_type stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::bid_type |
Definition at line 50 of file pq_ext_merger.h.
typedef BlockType stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::block_type |
class is parameterized by the block of the external arrays
Definition at line 42 of file pq_ext_merger.h.
typedef CompareType stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::compare_type |
Definition at line 43 of file pq_ext_merger.h.
typedef read_write_pool<block_type> stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::pool_type |
Definition at line 55 of file pq_ext_merger.h.
typedef ext_merger<BlockType, CompareType, Arity, AllocStr> stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::self_type |
our type
Definition at line 58 of file pq_ext_merger.h.
typedef sequence_state stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::sequence_type |
type of sequences in which the values are stored: external arrays
Definition at line 172 of file pq_ext_merger.h.
typedef external_size_type stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::size_type |
size type of total number of item in merger
Definition at line 69 of file pq_ext_merger.h.
typedef loser_tree<self_type, CompareType, Arity> stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::tree_type |
type of embedded loser tree
Definition at line 65 of file pq_ext_merger.h.
typedef block_type::value_type stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::value_type |
Definition at line 51 of file pq_ext_merger.h.
anonymous enum |
Enumerator | |
---|---|
arity | |
max_arity |
Definition at line 46 of file pq_ext_merger.h.
|
inline |
Definition at line 191 of file pq_ext_merger.h.
References stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::initialize().
|
inlinevirtual |
Definition at line 201 of file pq_ext_merger.h.
References stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::sequence_state::block, and STXXL_VERBOSE1.
|
inline |
Merge all items from another merger and insert the resulting external array into the merger. Requires: is_space_available() == 1.
Definition at line 367 of file pq_ext_merger.h.
References stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::cmp, stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::k, stxxl::block_manager::new_blocks(), stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::new_player(), stxxl::read_write_pool< BlockType >::size_write(), stxxl::read_write_pool< BlockType >::steal(), STXXL_VERBOSE1, stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::update_on_insert(), and stxxl::read_write_pool< BlockType >::write().
Referenced by stxxl::priority_queue< ConfigType >::make_space_available().
|
inline |
free an empty segment.
Definition at line 252 of file pq_ext_merger.h.
References stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::sequence_state::allocated, stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::free_player(), stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::sequence_state::make_inf(), and STXXL_VERBOSE1.
|
inline |
Return the item sequence of the given slot.
Definition at line 234 of file pq_ext_merger.h.
|
inlineprotected |
Definition at line 277 of file pq_ext_merger.h.
References stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::sequence_state::block, stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::cmp, stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::sequence_state::make_inf(), stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::sequence_state::merger, STXXL_ERRMSG, and STXXL_VERBOSE2.
|
inline |
bidlist | list of blocks to insert |
first_block | the first block of the sequence, before bidlist |
first_size | number of elements in the first block |
slot | slot to insert into |
Definition at line 348 of file pq_ext_merger.h.
References stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::sequence_state::allocated, stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::sequence_state::bids, stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::sequence_state::block, stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::sequence_state::current, and STXXL_VERBOSE1.
|
inline |
Is this segment allocated? Otherwise it's empty, already on the stack of free segment indices and can be reused.
Definition at line 228 of file pq_ext_merger.h.
|
inline |
is this segment empty ?
Definition at line 221 of file pq_ext_merger.h.
|
inline |
True if a is the sentinel value.
Definition at line 331 of file pq_ext_merger.h.
References stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::is_sentinel().
|
inline |
Whether there is still space for new array.
Definition at line 325 of file pq_ext_merger.h.
References stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::is_space_available().
|
inline |
Set a usually empty array to the sentinel.
Definition at line 246 of file pq_ext_merger.h.
|
inline |
Definition at line 319 of file pq_ext_merger.h.
|
inline |
Definition at line 439 of file pq_ext_merger.h.
References stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::multi_merge().
|
inline |
Hint (prefetch) first non-internal (actually second) block of each sequence.
Definition at line 265 of file pq_ext_merger.h.
References stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::sequence_state::bids, stxxl::read_write_pool< BlockType >::hint(), and stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::k.
|
inline |
Definition at line 211 of file pq_ext_merger.h.
Referenced by stxxl::priority_queue< ConfigType >::init(), and stxxl::priority_queue< ConfigType >::make_space_available().
|
inline |
Return the number of items in the arrays.
Definition at line 337 of file pq_ext_merger.h.
|
inline |
Swap contents of arrays a and b.
Definition at line 240 of file pq_ext_merger.h.
References stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::sequence_state::swap().
|
protected |
total number of elements stored
Definition at line 188 of file pq_ext_merger.h.
|
protected |
read and writer block pool
Definition at line 182 of file pq_ext_merger.h.
|
protected |
a memory block filled with sentinel values
Definition at line 185 of file pq_ext_merger.h.
|
protected |
sequence including current position, dereference gives current element
Definition at line 179 of file pq_ext_merger.h.
|
protected |
loser tree instance
Definition at line 176 of file pq_ext_merger.h.