Stxxl  1.4.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Public Types | Public Member Functions | Protected Types | Protected Attributes | Private Member Functions
stxxl::priority_queue< Config_ > Class Template Reference

External priority queue data structure. More...

#include <priority_queue.h>

Inheritance diagram for stxxl::priority_queue< Config_ >:
Inheritance graph
[legend]
Collaboration diagram for stxxl::priority_queue< Config_ >:
Collaboration graph
[legend]

List of all members.

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_typetop () 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_typepool
bool pool_owned
ext_merger_type ** ext_mergers
value_type group_buffers [total_num_groups][N+1]
value_typegroup_buffer_current_mins [total_num_groups]
value_type delete_buffer [delete_buffer_size+1]
value_typedelete_buffer_current_min
value_typedelete_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.

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_memmemory (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_memmemory (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]
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]
template<class Config_ >
unsigned_type stxxl::priority_queue< Config_ >::make_space_available ( unsigned_type  level) [private]
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]
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().


Member Data Documentation

template<class Config_>
comparator_type stxxl::priority_queue< Config_ >::cmp [protected]

Definition at line 198 of file priority_queue.h.

template<class Config_>
value_type stxxl::priority_queue< Config_ >::delete_buffer[delete_buffer_size+1] [protected]

Definition at line 194 of file priority_queue.h.

template<class Config_>
value_type* stxxl::priority_queue< Config_ >::delete_buffer_current_min [protected]

Definition at line 195 of file priority_queue.h.

template<class Config_>
value_type* stxxl::priority_queue< Config_ >::delete_buffer_end [protected]

Definition at line 196 of file priority_queue.h.

template<class Config_>
ext_merger_type** stxxl::priority_queue< Config_ >::ext_mergers [protected]

Definition at line 187 of file priority_queue.h.

template<class Config_>
value_type* stxxl::priority_queue< Config_ >::group_buffer_current_mins[total_num_groups] [protected]

Definition at line 191 of file priority_queue.h.

template<class Config_>
value_type stxxl::priority_queue< Config_ >::group_buffers[total_num_groups][N+1] [protected]

Definition at line 190 of file priority_queue.h.

template<class Config_>
insert_heap_type stxxl::priority_queue< Config_ >::insert_heap [protected]

Definition at line 201 of file priority_queue.h.

template<class Config_>
int_merger_type stxxl::priority_queue< Config_ >::int_mergers[num_int_groups] [protected]

Definition at line 184 of file priority_queue.h.

template<class Config_>
unsigned_type stxxl::priority_queue< Config_ >::num_active_groups [protected]

Definition at line 204 of file priority_queue.h.

template<class Config_>
pool_type* stxxl::priority_queue< Config_ >::pool [protected]

Definition at line 185 of file priority_queue.h.

template<class Config_>
bool stxxl::priority_queue< Config_ >::pool_owned [protected]

Definition at line 186 of file priority_queue.h.

template<class Config_>
size_type stxxl::priority_queue< Config_ >::size_ [protected]

Definition at line 207 of file priority_queue.h.


The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines