External priority queue data structure. More...

#include <priority_queue.h>

Inheritance diagram for stxxl::priority_queue< Config_ >:

Collaboration diagram for stxxl::priority_queue< Config_ >:

Public Types
enum	{ delete_buffer_size = Config::delete_buffer_size, N = Config::N, IntKMAX = Config::IntKMAX, num_int_groups = Config::num_int_groups, num_ext_groups = Config::num_ext_groups, total_num_groups = Config::num_int_groups + Config::num_ext_groups, BlockSize = Config::BlockSize, ExtKMAX = Config::ExtKMAX }
typedef Config_	Config
typedef Config::value_type	value_type
	The type of object stored in the priority_queue.
typedef Config::comparator_type	comparator_type
	Comparison object.
typedef Config::alloc_strategy_type	alloc_strategy_type
typedef stxxl::uint64	size_type
	An unsigned integral type (64 bit)
typedef typed_block< BlockSize, value_type >	block_type
typedef read_write_pool < block_type >	pool_type
Public Member Functions
	priority_queue (pool_type &pool_)
	Constructs external priority queue object.
	_STXXL_DEPRECATED (priority_queue(prefetch_pool< block_type > &p_pool_, write_pool< block_type > &w_pool_))
	Constructs external priority queue object.
	priority_queue (unsigned_type p_pool_mem, unsigned_type w_pool_mem)
	Constructs external priority queue object.
virtual	~priority_queue ()
size_type	size () const
	Returns number of elements contained.
bool	empty () const
	Returns true if queue has no elements.
const value_type &	top () const
	Returns "largest" element.
void	pop ()
	Removes the element at the top.
void	push (const value_type &obj)
	Inserts x into the priority_queue.
unsigned_type	mem_cons () const
	Returns number of bytes consumed by the priority_queue.
void	dump_sizes () const
void	dump_params () const
Protected Types
typedef priority_queue_local::internal_priority_queue < value_type, std::vector < value_type > , comparator_type >	insert_heap_type
typedef priority_queue_local::loser_tree < value_type, comparator_type, IntKMAX >	int_merger_type
typedef priority_queue_local::ext_merger < block_type, comparator_type, ExtKMAX, alloc_strategy_type >	ext_merger_type
Protected Attributes
int_merger_type	int_mergers [num_int_groups]
pool_type *	pool
bool	pool_owned
ext_merger_type **	ext_mergers
value_type	group_buffers [total_num_groups][N+1]
value_type *	group_buffer_current_mins [total_num_groups]
value_type	delete_buffer [delete_buffer_size+1]
value_type *	delete_buffer_current_min
value_type *	delete_buffer_end
comparator_type	cmp
insert_heap_type	insert_heap
unsigned_type	num_active_groups
size_type	size_
Private Member Functions
void	init ()
void	refill_delete_buffer ()
unsigned_type	refill_group_buffer (unsigned_type k)
unsigned_type	make_space_available (unsigned_type level)
void	empty_insert_heap ()
value_type	get_supremum () const
unsigned_type	current_delete_buffer_size () const
unsigned_type	current_group_buffer_size (unsigned_type i) const

Detailed Description

template<class Config_>
class stxxl::priority_queue< Config_ >

External priority queue data structure.

Definition at line 142 of file priority_queue.h.

Member Typedef Documentation

template<class Config_>

typedef Config::alloc_strategy_type stxxl::priority_queue< Config_ >::alloc_strategy_type

Definition at line 162 of file priority_queue.h.

template<class Config_>

typedef typed_block<BlockSize, value_type> stxxl::priority_queue< Config_ >::block_type

Definition at line 165 of file priority_queue.h.

template<class Config_>

typedef Config::comparator_type stxxl::priority_queue< Config_ >::comparator_type

Comparison object.

Definition at line 161 of file priority_queue.h.

template<class Config_>

typedef Config_ stxxl::priority_queue< Config_ >::Config

Definition at line 145 of file priority_queue.h.

template<class Config_>

typedef priority_queue_local::ext_merger< block_type, comparator_type, ExtKMAX, alloc_strategy_type> stxxl::priority_queue< Config_ >::ext_merger_type [protected]

Definition at line 181 of file priority_queue.h.

template<class Config_>

typedef priority_queue_local::internal_priority_queue<value_type, std::vector<value_type>, comparator_type> stxxl::priority_queue< Config_ >::insert_heap_type [protected]

Definition at line 170 of file priority_queue.h.

template<class Config_>

typedef priority_queue_local::loser_tree< value_type, comparator_type, IntKMAX> stxxl::priority_queue< Config_ >::int_merger_type [protected]

Definition at line 175 of file priority_queue.h.

template<class Config_>

typedef read_write_pool<block_type> stxxl::priority_queue< Config_ >::pool_type

Definition at line 166 of file priority_queue.h.

template<class Config_>

typedef stxxl::uint64 stxxl::priority_queue< Config_ >::size_type

An unsigned integral type (64 bit)

Definition at line 164 of file priority_queue.h.

template<class Config_>

typedef Config::value_type stxxl::priority_queue< Config_ >::value_type

The type of object stored in the priority_queue.

Definition at line 159 of file priority_queue.h.

Member Enumeration Documentation

template<class Config_>

anonymous enum

Enumerator:

delete_buffer_size
N
IntKMAX
num_int_groups
num_ext_groups
total_num_groups
BlockSize
ExtKMAX

Definition at line 146 of file priority_queue.h.

Constructor & Destructor Documentation

template<class Config_ >

stxxl::priority_queue< Config_ >::priority_queue ( pool_type & pool_ )

Constructs external priority queue object.

Parameters:

pool_ pool of blocks that will be used for data writing and prefetching for the disk<->memory transfers happening in the priority queue. Larger pool size helps to speed up operations.

Definition at line 401 of file priority_queue.h.

References stxxl::priority_queue< Config_ >::init(), and STXXL_VERBOSE_PQ.

template<class Config_ >

stxxl::priority_queue< Config_ >::priority_queue	(	unsigned_type	p_pool_mem,
		unsigned_type	w_pool_mem
	)

Constructs external priority queue object.

Parameters:

p_pool_mem	memory (in bytes) for prefetch pool that will be used for data prefetching for the disk<->memory transfers happening in the priority queue. Larger pool size helps to speed up operations.
w_pool_mem	memory (in bytes) for buffered write pool that will be used for writing data for the memory<->disk transfers happening in the priority queue. Larger pool size helps to speed up operations.

Definition at line 426 of file priority_queue.h.

References stxxl::priority_queue< Config_ >::init(), and STXXL_VERBOSE_PQ.

template<class Config_ >

stxxl::priority_queue< Config_ >::~priority_queue ( ) [virtual]

Definition at line 460 of file priority_queue.h.

References STXXL_VERBOSE_PQ.

Member Function Documentation

template<class Config_>

stxxl::priority_queue< Config_ >::_STXXL_DEPRECATED ( priority_queue< Config_ >(prefetch_pool< block_type > &p_pool_, write_pool< block_type > &w_pool_) )

Constructs external priority queue object.

Parameters:

p_pool_	pool of blocks that will be used for data prefetching for the disk<->memory transfers happening in the priority queue. Larger pool size helps to speed up operations.
w_pool_	pool of blocks that will be used for writing data for the memory<->disk transfers happening in the priority queue. Larger pool size helps to speed up operations.

template<class Config_>

unsigned_type stxxl::priority_queue< Config_ >::current_delete_buffer_size ( ) const [inline, private]

Definition at line 219 of file priority_queue.h.

template<class Config_>

unsigned_type stxxl::priority_queue< Config_ >::current_group_buffer_size ( unsigned_type i ) const [inline, private]

Definition at line 220 of file priority_queue.h.

template<class Config_ >

void stxxl::priority_queue< Config_ >::dump_params ( ) const

Definition at line 858 of file priority_queue.h.

References STXXL_MSG.

template<class Config_ >

void stxxl::priority_queue< Config_ >::dump_sizes ( ) const

Definition at line 834 of file priority_queue.h.

References STXXL_MSG.

template<class Config_>

bool stxxl::priority_queue< Config_ >::empty ( ) const [inline]

Returns true if queue has no elements.

Returns:: true if queue has no elements, false otherwise

Definition at line 290 of file priority_queue.h.

template<class Config_ >

void stxxl::priority_queue< Config_ >::empty_insert_heap ( ) [private]

Definition at line 753 of file priority_queue.h.

References stxxl::priority_queue_local::merge_iterator(), and STXXL_VERBOSE_PQ.

template<class Config_>

value_type stxxl::priority_queue< Config_ >::get_supremum ( ) const [inline, private]

Definition at line 218 of file priority_queue.h.

template<class Config_ >

void stxxl::priority_queue< Config_ >::init ( ) [private]

Definition at line 438 of file priority_queue.h.

References stxxl::priority_queue_local::ext_merger< BlockType_, Cmp_, Arity_, AllocStr_ >::set_pool().

Referenced by stxxl::priority_queue< Config_ >::priority_queue().

template<class Config_ >

unsigned_type stxxl::priority_queue< Config_ >::make_space_available ( unsigned_type level ) [private]

Definition at line 676 of file priority_queue.h.

References stxxl::priority_queue_local::ext_merger< BlockType_, Cmp_, Arity_, AllocStr_ >::insert_segment(), stxxl::priority_queue_local::ext_merger< BlockType_, Cmp_, Arity_, AllocStr_ >::set_pool(), STXXL_VERBOSE_PQ, and std::swap().

template<class Config_>

unsigned_type stxxl::priority_queue< Config_ >::mem_cons ( ) const [inline]

Returns number of bytes consumed by the priority_queue.

number of bytes consumed by the priority_queue from the internal memory not including pools (see the constructor)

Definition at line 323 of file priority_queue.h.

template<class Config_ >

void stxxl::priority_queue< Config_ >::pop ( ) [inline]

Removes the element at the top.

Removes the element at the top of the priority_queue, that is, the largest element in the priority_queue. Precondition: empty() is false. Postcondition: size() will be decremented by 1.

Definition at line 367 of file priority_queue.h.

template<class Config_ >

void stxxl::priority_queue< Config_ >::push ( const value_type & obj ) [inline]

Inserts x into the priority_queue.

Inserts x into the priority_queue. Postcondition: size() will be incremented by 1.

Definition at line 384 of file priority_queue.h.

References stxxl::priority_queue< Config_ >::push().

Referenced by stxxl::priority_queue< Config_ >::push().

template<class Config_ >

void stxxl::priority_queue< Config_ >::refill_delete_buffer ( ) [private]

Definition at line 534 of file priority_queue.h.

References stxxl::is_sorted(), stxxl::priority_queue_local::merge3_iterator(), stxxl::priority_queue_local::merge4_iterator(), stxxl::priority_queue_local::merge_iterator(), STXXL_MSG, STXXL_THROW, and STXXL_VERBOSE_PQ.

template<class Config_ >

unsigned_type stxxl::priority_queue< Config_ >::refill_group_buffer ( unsigned_type k ) [private]

Definition at line 475 of file priority_queue.h.

References stxxl::is_sorted(), STXXL_MSG, and STXXL_VERBOSE_PQ.

template<class Config_ >

priority_queue< Config_ >::size_type stxxl::priority_queue< Config_ >::size ( ) const [inline]

Returns number of elements contained.

Returns:: number of elements contained

Definition at line 346 of file priority_queue.h.

References stxxl::priority_queue< Config_ >::size().

Referenced by stxxl::priority_queue< Config_ >::size().

template<class Config_ >

const priority_queue< Config_ >::value_type & stxxl::priority_queue< Config_ >::top ( ) const [inline]

Returns "largest" element.

Returns a const reference to the element at the top of the priority_queue. The element at the top is guaranteed to be the largest element in the priority queue, as determined by the comparison function Config_::comparator_type (the same as the second parameter of PRIORITY_QUEUE_GENERATOR utility class). That is, for every other element x in the priority_queue, Config_::comparator_type(Q.top(), x) is false. Precondition: empty() is false.

Definition at line 355 of file priority_queue.h.

References stxxl::priority_queue< Config_ >::top().

Referenced by stxxl::priority_queue< Config_ >::top().