stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr > Class Template Reference

Detailed Description

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>
class stxxl::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

Definition at line 127 of file pq_ext_merger.h.

Inheritance diagram for stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >:

Collaboration diagram for stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >:

Classes
struct	sequence_state

Public Types
enum	{ arity = Arity, arity_bound = 1UL << (LOG2<Arity>::ceil) }
typedef AllocStr	alloc_strategy
typedef block_type::bid_type	bid_type
typedef BlockType	block_type
typedef Cmp	comparator_type
typedef read_write_pool < block_type >	pool_type
typedef stxxl::uint64	size_type
typedef block_type::value_type	value_type

Public Member Functions
	ext_merger ()
	ext_merger (pool_type *pool_)
virtual	~ext_merger ()
template<class Merger >
void	insert_segment (Merger &another_merger, size_type segment_size)
bool	is_space_available () const
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

Protected Member Functions
void	deallocate_segment (unsigned_type slot)
void	insert_segment (std::list< bid_type > *bidlist, block_type *first_block, unsigned_type first_size, unsigned_type slot)
bool	is_segment_allocated (unsigned_type slot) const
bool	is_segment_empty (unsigned_type slot) const
bool	is_sentinel (const value_type &a) const
bool	not_sentinel (const value_type &a) const

Protected Attributes
comparator_type	cmp
internal_bounded_stack < unsigned_type, arity >	free_segments
unsigned_type	k
unsigned_type	log_k
pool_type *	pool
block_type *	sentinel_block
size_type	size_
sequence_state	states [arity_bound]

Private Member Functions
void	compact_tree ()
void	double_k ()
void	init ()
void	rebuild_loser_tree ()
Private Member Functions inherited from stxxl::noncopyable
	noncopyable ()

Member Typedef Documentation

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef AllocStr stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::alloc_strategy

Definition at line 135 of file pq_ext_merger.h.

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef block_type::bid_type stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::bid_type

Definition at line 132 of file pq_ext_merger.h.

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef BlockType stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::block_type

Definition at line 131 of file pq_ext_merger.h.

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef Cmp stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::comparator_type

Definition at line 134 of file pq_ext_merger.h.

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef read_write_pool<block_type> stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::pool_type

Definition at line 136 of file pq_ext_merger.h.

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef stxxl::uint64 stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::size_type

Definition at line 130 of file pq_ext_merger.h.

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef block_type::value_type stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::value_type

Definition at line 133 of file pq_ext_merger.h.

Member Enumeration Documentation

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

anonymous enum

Enumerator
arity
arity_bound

Definition at line 139 of file pq_ext_merger.h.

Constructor & Destructor Documentation

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::ext_merger ( )

inline

Definition at line 290 of file pq_ext_merger.h.

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::ext_merger ( pool_type *  pool_ )

inline

Definition at line 296 of file pq_ext_merger.h.

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

virtual stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::~ext_merger ( )

inlinevirtual

Definition at line 303 of file pq_ext_merger.h.

References stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::sequence_state::block, and STXXL_VERBOSE1.

Member Function Documentation

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

void stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::compact_tree ( )

inlineprivate

Definition at line 489 of file pq_ext_merger.h.

References stxxl::priority_queue_local::internal_bounded_stack< ValueType, MaxSize >::clear(), stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::sequence_state::make_inf(), stxxl::priority_queue_local::internal_bounded_stack< ValueType, MaxSize >::push(), stxxl::priority_queue_local::internal_bounded_stack< ValueType, MaxSize >::size(), STXXL_VERBOSE1, and stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::sequence_state::swap().

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

void stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::deallocate_segment ( unsigned_type  slot )

inlineprotected

Definition at line 1079 of file pq_ext_merger.h.

References stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::sequence_state::allocated, stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::sequence_state::make_inf(), stxxl::priority_queue_local::internal_bounded_stack< ValueType, MaxSize >::push(), and STXXL_VERBOSE1.

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

void stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::double_k ( )

inlineprivate

Definition at line 460 of file pq_ext_merger.h.

References stxxl::priority_queue_local::internal_bounded_stack< ValueType, MaxSize >::empty(), stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::sequence_state::make_inf(), stxxl::priority_queue_local::internal_bounded_stack< ValueType, MaxSize >::push(), stxxl::priority_queue_local::internal_bounded_stack< ValueType, MaxSize >::size(), and STXXL_VERBOSE1.

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

void stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::init ( )

inlineprivate

Definition at line 319 of file pq_ext_merger.h.

References stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::sequence_state::block, stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::sequence_state::make_inf(), stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::sequence_state::merger, stxxl::priority_queue_local::internal_bounded_stack< ValueType, MaxSize >::push(), STXXL_ERRMSG, and STXXL_VERBOSE2.

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

template<class Merger >

void stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::insert_segment ( Merger &  another_merger, size_type  segment_size  )

inline

Definition at line 971 of file pq_ext_merger.h.

References stxxl::priority_queue_local::internal_bounded_stack< ValueType, MaxSize >::empty(), stxxl::block_manager::new_blocks(), stxxl::priority_queue_local::internal_bounded_stack< ValueType, MaxSize >::pop(), stxxl::read_write_pool< BlockType >::size_write(), stxxl::read_write_pool< BlockType >::steal(), STXXL_VERBOSE1, stxxl::priority_queue_local::internal_bounded_stack< ValueType, MaxSize >::top(), and stxxl::read_write_pool< BlockType >::write().

Referenced by stxxl::priority_queue< ConfigType >::make_space_available().

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

void stxxl::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  )

inlineprotected

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

Definition at line 1057 of file pq_ext_merger.h.

References stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::sequence_state::allocated, stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::sequence_state::bids, stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::sequence_state::block, stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::sequence_state::current, and STXXL_VERBOSE1.

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

bool stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::is_segment_allocated ( unsigned_type  slot ) const

inlineprotected

Definition at line 1098 of file pq_ext_merger.h.

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

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

bool stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::is_segment_empty ( unsigned_type  slot ) const

inlineprotected

Definition at line 1091 of file pq_ext_merger.h.

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

bool stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::is_sentinel ( const value_type &  a ) const

inlineprotected

Definition at line 144 of file pq_ext_merger.h.

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

bool stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::is_space_available ( ) const

inline

Definition at line 963 of file pq_ext_merger.h.

References stxxl::priority_queue_local::internal_bounded_stack< ValueType, MaxSize >::empty().

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

unsigned_type stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::mem_cons ( ) const

inline

Definition at line 551 of file pq_ext_merger.h.

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

template<class OutputIterator >

void stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::multi_merge ( OutputIterator  begin, OutputIterator  end  )

inline

Definition at line 562 of file pq_ext_merger.h.

References stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::sequence_state::bids, stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::sequence_state::block, stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::sequence_state::current, stxxl::priority_queue_local::internal_bounded_stack< ValueType, MaxSize >::empty(), stxxl::read_write_pool< BlockType >::hint(), stxxl::is_sorted(), stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::sequence_state::make_inf(), stxxl::priority_queue_local::merge3_iterator(), stxxl::priority_queue_local::merge4_iterator(), stxxl::priority_queue_local::merge_iterator(), stxxl::read_write_pool< BlockType >::read(), stxxl::priority_queue_local::internal_bounded_stack< ValueType, MaxSize >::size(), stxxl::STXXL_MIN(), STXXL_VERBOSE1, STXXL_VERBOSE2, STXXL_VERBOSE3, and stxxl::request_interface::wait().

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

bool stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::not_sentinel ( const value_type &  a ) const

inlineprotected

Definition at line 149 of file pq_ext_merger.h.

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

void stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::rebuild_loser_tree ( )

inlineprivate

Definition at line 357 of file pq_ext_merger.h.

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

void stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::set_pool ( pool_type *  pool_ )

inline

Definition at line 313 of file pq_ext_merger.h.

Referenced by stxxl::priority_queue< ConfigType >::init(), and stxxl::priority_queue< ConfigType >::make_space_available().

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

size_type stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::size ( ) const

inline

Definition at line 1048 of file pq_ext_merger.h.

Member Data Documentation

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

comparator_type stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::cmp

protected

Definition at line 142 of file pq_ext_merger.h.

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

internal_bounded_stack<unsigned_type, arity> stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::free_segments

protected

Definition at line 272 of file pq_ext_merger.h.

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

unsigned_type stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::k

protected

Definition at line 266 of file pq_ext_merger.h.

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

unsigned_type stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::log_k

protected

Definition at line 265 of file pq_ext_merger.h.

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

pool_type* stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::pool

protected

Definition at line 285 of file pq_ext_merger.h.

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

block_type* stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::sentinel_block

protected

Definition at line 287 of file pq_ext_merger.h.

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

size_type stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::size_

protected

Definition at line 264 of file pq_ext_merger.h.

template<class BlockType, class Cmp, unsigned Arity, class AllocStr = STXXL_DEFAULT_ALLOC_STRATEGY>

sequence_state stxxl::priority_queue_local::ext_merger< BlockType, Cmp, Arity, AllocStr >::states[arity_bound]

protected

Definition at line 283 of file pq_ext_merger.h.

---

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

• include/stxxl/bits/containers/pq_ext_merger.h