External priority queue data structure. More...

#include <priority_queue.h>

Inherits noncopyable.

Collaboration diagram for 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. More...

typedef Config::comparator_type	comparator_type
	Comparison object. More...

typedef Config::alloc_strategy_type	alloc_strategy_type

typedef stxxl::uint64	size_type
	An unsigned integral type (64 bit) More...

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

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

void	swap (priority_queue &obj)
	swap this priority queue with another one Implementation correctness is questionable. More...

size_type	size () const
	Returns number of elements contained. More...

bool	empty () const
	Returns true if queue has no elements. More...

const value_type &	top () const
	Returns "largest" element. More...

void	pop ()
	Removes the element at the top. More...

void	push (const value_type &obj)
	Inserts x into the priority_queue. More...

unsigned_type	mem_cons () const
	Returns number of bytes consumed by the priority_queue. More...

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_

Detailed Description

template<class Config_>
class priority_queue< Config_ >

External priority queue data structure.

Member Typedef Documentation

template<class Config_ >

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

Comparison object.

template<class Config_ >

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

An unsigned integral type (64 bit)

template<class Config_ >

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

The type of object stored in the priority_queue.

Constructor & Destructor Documentation

template<class Config_ >

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.

template<class Config_ >

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.

Member Function Documentation

template<class Config_ >

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

bool priority_queue< Config_ >::empty ( ) const

inline

Returns true if queue has no elements.

Returns: true if queue has no elements, false otherwise

References priority_queue< Config_ >::size().

template<class Config_ >

unsigned_type 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)

template<class Config_ >

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

template<class Config_ >

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

template<class Config_ >

priority_queue< Config_ >::size_type priority_queue< Config_ >::size ( ) const

inline

Returns number of elements contained.

Returns: number of elements contained

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

template<class Config_ >

void priority_queue< Config_ >::swap ( priority_queue< Config_ > & obj )

inline

swap this priority queue with another one Implementation correctness is questionable.

template<class Config_ >

const priority_queue< Config_ >::value_type & 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.

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

priority_queue.h

Public Types

Public Member Functions

Protected Types

Protected Attributes

Detailed Description

template<class Config_> class priority_queue< Config_ >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

template<class Config_>
class priority_queue< Config_ >