priority_queue_local::ext_merger< BlockType_, Cmp_, Arity_, AllocStr_ > Class Template Reference

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_ >:

List of all members.

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:

• pq_ext_merger.h