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

Arity maximum 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_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 ()

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

Definition at line 191 of file pq_ext_merger.h.

References stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::initialize().

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

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.

Member Function Documentation

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

template<class Merger >

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

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().

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

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.

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 >::init ( )

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.

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

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 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.

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

Definition at line 439 of file pq_ext_merger.h.

References stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::multi_merge().

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

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.

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

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().

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

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().

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:

include/stxxl/bits/containers/pq_ext_merger.h

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 >

Classes

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Additional Inherited Members

Member Typedef Documentation

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

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