External merger, based on the loser tree data structure. ! More...
#include <pq_ext_merger.h>
Inherits noncopyable.
Collaboration diagram for priority_queue_local::ext_merger< BlockType_, Cmp_, Arity_, AllocStr_ >:
Public Types | |
| enum | { arity = Arity_, arity_bound = 1UL << (LOG2<Arity_>::ceil) } |
| typedef stxxl::uint64 | size_type |
| typedef BlockType_ | block_type |
| typedef block_type::bid_type | bid_type |
| typedef block_type::value_type | value_type |
| typedef Cmp_ | comparator_type |
| typedef AllocStr_ | alloc_strategy |
|
typedef read_write_pool < block_type > | pool_type |
Public Member Functions | |
| ext_merger (pool_type *pool_) | |
| void | set_pool (pool_type *pool_) |
| unsigned_type | mem_cons () const |
| template<class OutputIterator > | |
| void | multi_merge (OutputIterator begin, OutputIterator end) |
| bool | is_space_available () const |
| template<class Merger > | |
| void | insert_segment (Merger &another_merger, size_type segment_size) |
| size_type | size () const |
Protected Member Functions | |
| bool | is_sentinel (const value_type &a) const |
| bool | not_sentinel (const value_type &a) const |
| void | insert_segment (std::list< bid_type > *bidlist, block_type *first_block, unsigned_type first_size, unsigned_type slot) |
| void | deallocate_segment (unsigned_type slot) |
| bool | is_segment_empty (unsigned_type slot) const |
| bool | is_segment_allocated (unsigned_type slot) const |
Protected Attributes | |
| comparator_type | cmp |
| size_type | size_ |
| unsigned_type | log_k |
| unsigned_type | k |
|
internal_bounded_stack < unsigned_type, arity > | free_segments |
| sequence_state | states [arity_bound] |
| pool_type * | pool |
| block_type * | sentinel_block |
Detailed Description
template<class BlockType_, class Cmp_, unsigned Arity_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>
class priority_queue_local::ext_merger< BlockType_, Cmp_, Arity_, AllocStr_ >
External merger, based on the loser tree data structure. !
!
- Parameters:
-
Arity_ maximum arity of merger, does not need to be a power of 2
Member Function Documentation
template<class BlockType_ , class Cmp_ , unsigned Arity_, class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>
| void priority_queue_local::ext_merger< BlockType_, Cmp_, Arity_, AllocStr_ >::insert_segment | ( | std::list< bid_type > * | bidlist, | |
| block_type * | first_block, | |||
| unsigned_type | first_size, | |||
| unsigned_type | slot | |||
| ) | [inline, protected] |
- Parameters:
-
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
The documentation for this class was generated from the following file:
