STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr > Class Template Reference

Detailed Description

template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
class stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >

External merger, based on the loser tree data structure.

Parameters
Aritymaximum arity of merger, does not need to be a power of 2

Definition at line 38 of file pq_ext_merger.h.

+ Inheritance diagram for stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >:
+ Collaboration diagram for stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >:

Classes

struct  sequence_state
 

Public Types

enum  { arity = Arity, max_arity = 1UL << (LOG2<Arity>::ceil) }
 
typedef AllocStr alloc_strategy
 
typedef std::deque< bid_typebid_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_typeget_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_typepool
 read and writer block pool More...
 
block_typesentinel_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 ()
 

Member Typedef Documentation

template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
typedef AllocStr stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::alloc_strategy

Definition at line 48 of file pq_ext_merger.h.

template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
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.

template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
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.

template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
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.

template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
typedef CompareType stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::compare_type

Definition at line 43 of file pq_ext_merger.h.

template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
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.

template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
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.

template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
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.

template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
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.

template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
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.

template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
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.

Member Enumeration Documentation

template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
anonymous enum
Enumerator
arity 
max_arity 

Definition at line 46 of file pq_ext_merger.h.

Constructor & Destructor Documentation

template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::ext_merger ( const compare_type c = compare_type())
inline
template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
virtual stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::~ext_merger ( )
inlinevirtual

Member Function Documentation

template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
void stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::free_array ( unsigned_type  slot)
inline
template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
sequence_type& stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::get_array ( unsigned_type  slot)
inline

Return the item sequence of the given slot.

Definition at line 234 of file pq_ext_merger.h.

template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
void stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::insert_segment ( bid_container_type bidlist,
block_type first_block,
unsigned_type  first_size,
unsigned_type  slot 
)
inline
template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
bool stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::is_array_allocated ( unsigned_type  slot) const
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.

References stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::sequence_state::allocated.

template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
bool stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::is_array_empty ( unsigned_type  slot) const
inline

is this segment empty ?

Definition at line 221 of file pq_ext_merger.h.

template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
bool stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::is_sentinel ( const value_type a) const
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().

template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
bool stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::is_space_available ( ) const
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().

template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
void stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::make_array_sentinel ( unsigned_type  a)
inline

Set a usually empty array to the sentinel.

Definition at line 246 of file pq_ext_merger.h.

References stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::sequence_state::make_inf().

template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
unsigned_type stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::mem_cons ( ) const
inline

Definition at line 319 of file pq_ext_merger.h.

template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
template<class OutputIterator >
void stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::multi_merge ( OutputIterator  begin,
OutputIterator  end 
)
inline
template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
void stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::prefetch_arrays ( )
inline
template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
void stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::set_pool ( pool_type pool_)
inline
template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
size_type stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::size ( ) const
inline

Return the number of items in the arrays.

Definition at line 337 of file pq_ext_merger.h.

template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
void stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::swap_arrays ( unsigned_type  a,
unsigned_type  b 
)
inline

Member Data Documentation

template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
size_type stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::m_size
protected

total number of elements stored

Definition at line 188 of file pq_ext_merger.h.

template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
pool_type* stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::pool
protected

read and writer block pool

Definition at line 182 of file pq_ext_merger.h.

template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
block_type* stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::sentinel_block
protected

a memory block filled with sentinel values

Definition at line 185 of file pq_ext_merger.h.

template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
sequence_state stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::states[max_arity]
protected

sequence including current position, dereference gives current element

Definition at line 179 of file pq_ext_merger.h.

template<class BlockType, class CompareType, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
tree_type stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::tree
protected

loser tree instance

Definition at line 176 of file pq_ext_merger.h.


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