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

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

List of all members.

Classes
struct	sequence_state
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 ()
	ext_merger (pool_type *pool_)
virtual	~ext_merger ()
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
Private Member Functions
void	init ()
void	rebuild_loser_tree ()
void	double_k ()
void	compact_tree ()

---

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.

---

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 288 of file pq_ext_merger.h.

References init().

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 294 of file pq_ext_merger.h.

References init().

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

(

)

[inline, virtual]

Definition at line 301 of file pq_ext_merger.h.

References stxxl::priority_queue_local::ext_merger< BlockType_, Cmp_, Arity_, AllocStr_ >::sequence_state::block.

---

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

(

)

[inline, private]

Definition at line 487 of file pq_ext_merger.h.

References stxxl::priority_queue_local::internal_bounded_stack< Tp_, max_size_ >::clear(), stxxl::priority_queue_local::ext_merger< BlockType_, Cmp_, Arity_, AllocStr_ >::sequence_state::make_inf(), stxxl::priority_queue_local::internal_bounded_stack< Tp_, max_size_ >::push(), stxxl::priority_queue_local::internal_bounded_stack< Tp_, max_size_ >::size(), 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

)

[inline, protected]

Definition at line 1080 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(), and stxxl::priority_queue_local::internal_bounded_stack< Tp_, max_size_ >::push().

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

(

)

[inline, private]

Definition at line 458 of file pq_ext_merger.h.

References stxxl::priority_queue_local::internal_bounded_stack< Tp_, max_size_ >::empty(), stxxl::priority_queue_local::ext_merger< BlockType_, Cmp_, Arity_, AllocStr_ >::sequence_state::make_inf(), stxxl::priority_queue_local::internal_bounded_stack< Tp_, max_size_ >::push(), and stxxl::priority_queue_local::internal_bounded_stack< Tp_, max_size_ >::size().

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

(

)

[inline, private]

Definition at line 317 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, and stxxl::priority_queue_local::internal_bounded_stack< Tp_, max_size_ >::push().

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 972 of file pq_ext_merger.h.

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

Referenced by main(), and stxxl::priority_queue< Config_ >::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
	)		[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

Definition at line 1058 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 std::swap().

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 [inline, protected]

Definition at line 1099 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 [inline, protected]

Definition at line 1092 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 [inline, protected]

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< Tp_, max_size_ >::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 550 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 561 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< Tp_, max_size_ >::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< Tp_, max_size_ >::size(), stxxl::STXXL_MIN(), and stxxl::request_interface::wait().

Referenced by main().

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 [inline, protected]

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

(

)

[inline, private]

Definition at line 355 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 311 of file pq_ext_merger.h.

Referenced by stxxl::priority_queue< Config_ >::init(), and stxxl::priority_queue< Config_ >::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 1050 of file pq_ext_merger.h.

Referenced by main().

---

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 270 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 264 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 263 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 283 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 285 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 262 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 281 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