stxxl::priority_queue< ConfigType > Class Template Reference

Detailed Description

template<class ConfigType>
class stxxl::priority_queue< ConfigType >

External priority queue data structure
Introduction to priority queue container: see STXXL Priority Queue tutorial.
Design and Internals of priority queue container: see Priority Queue.

Examples:

examples/containers/pqueue1.cpp, and examples/containers/pqueue2.cpp.

Definition at line 98 of file priority_queue.h.

Inheritance diagram for stxxl::priority_queue< ConfigType >:

Collaboration diagram for stxxl::priority_queue< ConfigType >:

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::alloc_strategy_type	alloc_strategy_type
typedef typed_block< BlockSize, value_type >	block_type
	Type of the block used in disk-memory transfers. More...
typedef Config::comparator_type	comparator_type
	Comparison object. More...
typedef ConfigType	Config
typedef read_write_pool < block_type >	pool_type
typedef stxxl::uint64	size_type
	An unsigned integral type (64 bit). More...
typedef Config::value_type	value_type
	The type of object stored in the priority_queue. More...

Public Member Functions
Constructors/Destructors
	priority_queue (pool_type &pool_)
	Constructs external priority queue object. More...
	priority_queue (prefetch_pool< block_type > &p_pool_, write_pool< block_type > &w_pool_)
	Constructs external priority queue object. More...
	priority_queue (unsigned_type p_pool_mem, unsigned_type w_pool_mem)
	Constructs external priority queue object. More...
virtual	~priority_queue ()
Capacity
size_type	size () const
	Returns number of elements contained. More...
bool	empty () const
	Returns true if queue has no elements. More...
Operators
const value_type &	top () const
	Returns "largest" element. More...
Modifiers
void	pop ()
	Removes the element at the top. More...
void	push (const value_type &obj)
	Inserts x into the priority_queue. More...
Miscellaneous
unsigned_type	mem_cons () const
	Number of bytes consumed by the priority_queue from the internal memory not including pools (see the constructor) More...
void	dump_sizes () const
void	dump_params () const

Protected Types
typedef priority_queue_local::ext_merger < block_type, comparator_type, ExtKMAX, alloc_strategy_type >	ext_merger_type
typedef priority_queue_local::internal_priority_queue < value_type, std::vector < value_type > , comparator_type >	insert_heap_type
typedef priority_queue_local::int_merger < value_type, comparator_type, IntKMAX >	int_merger_type

Protected Attributes
comparator_type	cmp
value_type	delete_buffer [delete_buffer_size+1]
value_type *	delete_buffer_current_min
value_type *	delete_buffer_end
ext_merger_type **	ext_mergers
value_type *	group_buffer_current_mins [total_num_groups]
value_type	group_buffers [total_num_groups][N+1]
insert_heap_type	insert_heap
int_merger_type	int_mergers [num_int_groups]
unsigned_type	num_active_groups
pool_type *	pool
bool	pool_owned
size_type	size_

Private Member Functions
unsigned_type	current_delete_buffer_size () const
unsigned_type	current_group_buffer_size (unsigned_type i) const
void	empty_insert_heap ()
value_type	get_supremum () const
void	init ()
unsigned_type	make_space_available (unsigned_type level)
void	refill_delete_buffer ()
size_type	refill_group_buffer (unsigned_type k)
Private Member Functions inherited from stxxl::noncopyable
	noncopyable ()

Member Typedef Documentation

template<class ConfigType>

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

Definition at line 118 of file priority_queue.h.

template<class ConfigType>

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

Type of the block used in disk-memory transfers.

Definition at line 122 of file priority_queue.h.

template<class ConfigType>

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

Comparison object.

Definition at line 117 of file priority_queue.h.

template<class ConfigType>

typedef ConfigType stxxl::priority_queue< ConfigType >::Config

Definition at line 101 of file priority_queue.h.

template<class ConfigType>

typedef priority_queue_local::ext_merger< block_type, comparator_type, ExtKMAX, alloc_strategy_type> stxxl::priority_queue< ConfigType >::ext_merger_type

protected

Definition at line 138 of file priority_queue.h.

template<class ConfigType>

typedef priority_queue_local::internal_priority_queue<value_type, std::vector<value_type>, comparator_type> stxxl::priority_queue< ConfigType >::insert_heap_type

protected

Definition at line 127 of file priority_queue.h.

template<class ConfigType>

typedef priority_queue_local::int_merger< value_type, comparator_type, IntKMAX> stxxl::priority_queue< ConfigType >::int_merger_type

protected

Definition at line 132 of file priority_queue.h.

template<class ConfigType>

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

Definition at line 123 of file priority_queue.h.

template<class ConfigType>

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

An unsigned integral type (64 bit).

Definition at line 120 of file priority_queue.h.

template<class ConfigType>

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

The type of object stored in the priority_queue.

Definition at line 115 of file priority_queue.h.

Member Enumeration Documentation

template<class ConfigType>

anonymous enum

Enumerator
delete_buffer_size
N
IntKMAX
num_int_groups
num_ext_groups
total_num_groups
BlockSize
ExtKMAX

Definition at line 102 of file priority_queue.h.

Constructor & Destructor Documentation

template<class ConfigType >

stxxl::priority_queue< ConfigType >::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 377 of file priority_queue.h.

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

template<class ConfigType >

stxxl::priority_queue< ConfigType >::priority_queue	(	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.

Definition at line 390 of file priority_queue.h.

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

template<class ConfigType >

stxxl::priority_queue< ConfigType >::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 402 of file priority_queue.h.

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

template<class ConfigType >

stxxl::priority_queue< ConfigType >::~priority_queue ( )

virtual

Definition at line 436 of file priority_queue.h.

References STXXL_VERBOSE_PQ.

Member Function Documentation

template<class ConfigType>

unsigned_type stxxl::priority_queue< ConfigType >::current_delete_buffer_size ( ) const

inlineprivate

Definition at line 175 of file priority_queue.h.

template<class ConfigType>

unsigned_type stxxl::priority_queue< ConfigType >::current_group_buffer_size ( unsigned_type  i ) const

inlineprivate

Definition at line 176 of file priority_queue.h.

template<class ConfigType >

void stxxl::priority_queue< ConfigType >::dump_params

(

)

const

Definition at line 854 of file priority_queue.h.

References STXXL_MSG.

template<class ConfigType >

void stxxl::priority_queue< ConfigType >::dump_sizes

(

)

const

Definition at line 828 of file priority_queue.h.

References STXXL_MSG.

template<class ConfigType>

bool stxxl::priority_queue< ConfigType >::empty ( ) const

inline

Returns true if queue has no elements.

Returns

true if queue has no elements, false otherwise

Definition at line 257 of file priority_queue.h.

template<class ConfigType >

void stxxl::priority_queue< ConfigType >::empty_insert_heap ( )

private

Definition at line 742 of file priority_queue.h.

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

template<class ConfigType>

value_type stxxl::priority_queue< ConfigType >::get_supremum ( ) const

inlineprivate

Definition at line 174 of file priority_queue.h.

template<class ConfigType >

void stxxl::priority_queue< ConfigType >::init ( )

private

Definition at line 414 of file priority_queue.h.

References sentinel, and stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::set_pool().

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

template<class ConfigType >

unsigned_type stxxl::priority_queue< ConfigType >::make_space_available ( unsigned_type  level )

private

Definition at line 666 of file priority_queue.h.

References stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::append_merger(), stxxl::priority_queue_local::ext_merger< BlockType, CompareType, Arity, AllocStr >::set_pool(), STXXL_ERRMSG, STXXL_VERBOSE1, and STXXL_VERBOSE_PQ.

template<class ConfigType>

unsigned_type stxxl::priority_queue< ConfigType >::mem_cons ( ) const

inline

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

Definition at line 300 of file priority_queue.h.

template<class ConfigType >

void stxxl::priority_queue< ConfigType >::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 345 of file priority_queue.h.

template<class ConfigType >

void stxxl::priority_queue< ConfigType >::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 362 of file priority_queue.h.

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

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

template<class ConfigType >

void stxxl::priority_queue< ConfigType >::refill_delete_buffer ( )

private

Definition at line 511 of file priority_queue.h.

References stxxl::is_sorted(), stxxl::priority_queue_local::merge2_iterator(), stxxl::priority_queue_local::merge3_iterator(), stxxl::priority_queue_local::merge4_iterator(), stxxl::potentially_parallel::multiway_merge_sentinels(), STXXL_MSG, STXXL_THROW2, and STXXL_VERBOSE_PQ.

template<class ConfigType >

priority_queue< ConfigType >::size_type stxxl::priority_queue< ConfigType >::refill_group_buffer ( unsigned_type  k )

private

Definition at line 452 of file priority_queue.h.

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

template<class ConfigType >

priority_queue< ConfigType >::size_type stxxl::priority_queue< ConfigType >::size ( ) const

inline

Returns number of elements contained.

Returns

number of elements contained

Definition at line 324 of file priority_queue.h.

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

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

template<class ConfigType >

const priority_queue< ConfigType >::value_type & stxxl::priority_queue< ConfigType >::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 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, comparator_type(Q.top(), x) is false. Precondition: empty() is false.

Definition at line 333 of file priority_queue.h.

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

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

Member Data Documentation

template<class ConfigType>

comparator_type stxxl::priority_queue< ConfigType >::cmp

protected

Definition at line 154 of file priority_queue.h.

template<class ConfigType>

value_type stxxl::priority_queue< ConfigType >::delete_buffer[delete_buffer_size+1]

protected

Definition at line 150 of file priority_queue.h.

template<class ConfigType>

value_type* stxxl::priority_queue< ConfigType >::delete_buffer_current_min

protected

Definition at line 151 of file priority_queue.h.

template<class ConfigType>

value_type* stxxl::priority_queue< ConfigType >::delete_buffer_end

protected

Definition at line 152 of file priority_queue.h.

template<class ConfigType>

ext_merger_type** stxxl::priority_queue< ConfigType >::ext_mergers

protected

Definition at line 143 of file priority_queue.h.

template<class ConfigType>

value_type* stxxl::priority_queue< ConfigType >::group_buffer_current_mins[total_num_groups]

protected

Definition at line 147 of file priority_queue.h.

template<class ConfigType>

value_type stxxl::priority_queue< ConfigType >::group_buffers[total_num_groups][N+1]

protected

Definition at line 146 of file priority_queue.h.

template<class ConfigType>

insert_heap_type stxxl::priority_queue< ConfigType >::insert_heap

protected

Definition at line 157 of file priority_queue.h.

template<class ConfigType>

int_merger_type stxxl::priority_queue< ConfigType >::int_mergers[num_int_groups]

protected

Definition at line 140 of file priority_queue.h.

template<class ConfigType>

unsigned_type stxxl::priority_queue< ConfigType >::num_active_groups

protected

Definition at line 160 of file priority_queue.h.

template<class ConfigType>

pool_type* stxxl::priority_queue< ConfigType >::pool

protected

Definition at line 141 of file priority_queue.h.

template<class ConfigType>

bool stxxl::priority_queue< ConfigType >::pool_owned

protected

Definition at line 142 of file priority_queue.h.

template<class ConfigType>

size_type stxxl::priority_queue< ConfigType >::size_

protected

Definition at line 163 of file priority_queue.h.

---

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

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