STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems > Class Template Reference

Detailed Description

template<class ValueType, class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
class stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >

Parallelized External Memory Priority Queue.

Template Parameters
ValueTypeType of the contained objects (POD with no references to internal memory).
CompareTypeThe comparator type used to determine whether one element is smaller than another element.
DefaultMemSizeMaximum memory consumption by the queue. Can be overwritten by the constructor. Default = 1 GiB.
MaxItemsMaximum number of elements the queue contains at one time. Default = 0 = unlimited. This is no hard limit and only used for optimization. Can be overwritten by the constructor.
BlockSizeExternal block size. Default = STXXL_DEFAULT_BLOCK_SIZE(ValueType).
AllocStrategyAllocation strategy for the external memory. Default = STXXL_DEFAULT_ALLOC_STRATEGY.

Definition at line 1867 of file parallel_priority_queue.h.

+ Inheritance diagram for stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >:
+ Collaboration diagram for stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >:

Classes

struct  empty_external_array_eraser
 Unary operator which returns true if the external array has run empty. More...
 
struct  empty_internal_array_eraser
 Unary operator which returns true if the internal array has run empty. More...
 
struct  external_min_comparator
 Compares the largest accessible value of two external arrays. More...
 
struct  hint_comparator
 Compares the largest value of the block hinted the latest of two external arrays. More...
 
struct  inv_compare_type
 Inverse comparison functor. More...
 
struct  ProcessorData
 A struct containing the local insertion heap and other information local to a processor. More...
 
struct  s_min_tree_comparator
 
struct  stats_type
 Struct of all statistical counters and timers. Turn on/off statistics using the stats_counter and stats_timer typedefs. More...
 

Public Member Functions

void flush_ia_ea_until_memory_free (internal_size_type mem_free)
 Free up memory by flushing internal arrays and combining external arrays until enough bytes are free. More...
 
void hint_external_arrays ()
 Hints EA blocks which will be needed soon. Hints at most m_num_prefetchers blocks globally. More...
 
void merge_external_arrays ()
 Merges all external arrays and all internal arrays into one external array. More...
 
void print_stats () const
 Print statistics. More...
 
void rebuild_hint_tree ()
 Rebuild hint tree completely as the hint sequence may have changed, and re-hint the correct block sequence. More...
 
void resize_read_pool ()
 Automatically resize the read/prefetch buffer pool depending on number of external arrays. More...
 
void update_external_min_tree (size_t ea_index)
 Updates the external min tree afer a remove() or a wait_next_blocks() call. More...
 
void update_hint_tree (size_t ea_index)
 Updates the prefetch prediction tree afer a remove_items(), which frees up blocks. More...
 
Bulk Operations
void bulk_push_begin (size_type bulk_size)
 Start a sequence of push operations. More...
 
void bulk_push (const value_type &element, const unsigned_type p)
 Push an element inside a sequence of pushes. More...
 
void bulk_push (const value_type &element)
 Push an element inside a bulk sequence of pushes. More...
 
void bulk_push_end ()
 Ends a sequence of push operations. More...
 
void bulk_pop (std::vector< value_type > &out, size_t max_size)
 Extract up to max_size values at once. More...
 
bool bulk_pop_limit (std::vector< value_type > &out, const value_type &limit, size_t max_size=std::numeric_limits< size_t >::max())
 Extracts all elements which are greater or equal to a given limit. More...
 
Aggregation Operations
void aggregate_push (const value_type &element)
 Aggregate pushes. More...
 
std::priority_queue compliant operations
void push (const value_type &element, unsigned_type p=0)
 Insert new element. More...
 
const value_typetop ()
 Access the minimum element. More...
 
void pop ()
 Remove the minimum element. More...
 

Protected Member Functions

void add_as_internal_array (std::vector< value_type > &values, unsigned_type used=0, unsigned_type level=0)
 Add new internal array, which requires that values are sorted! automatically decreases m_mem_left! also merges internal arrays if there are too many internal arrays on the same level. More...
 
void advance_arrays (std::vector< iterator_pair_type > &sequences, std::vector< size_type > &sizes, size_t eas, size_t ias)
 
size_t calculate_merge_sequences (std::vector< size_type > &sizes, std::vector< iterator_pair_type > &sequences, bool reuse_previous_lower_bounds=false)
 Calculates the sequences vector needed by the multiway merger, considering inaccessible data from external arrays. The sizes vector stores the size of each sequence. More...
 
void check_external_level (unsigned_type level, bool force_merge_all=false)
 Merges external arrays if there are too many external arrays on the same level. More...
 
void cleanup_external_arrays ()
 Clean up empty external arrays, free their memory and capacity. More...
 
void cleanup_internal_arrays ()
 Clean up empty internal arrays, free their memory and capacity. More...
 
void convert_eb_into_ia (bool do_not_flush=false)
 Convert extract buffer into a new internal array. More...
 
void flush_array_internal (std::vector< value_type > &values)
 Sorts the values from values and writes them into an internal array. More...
 
void flush_insertion_heap (unsigned_type p)
 Flushes the insertions heap p into an internal array. More...
 
void flush_insertion_heaps ()
 Flushes all insertions heaps into an internal array. More...
 
void flush_insertion_heaps_with_limit (const value_type &limit)
 Flushes all elements of the insertion heaps which are greater or equal to a given limit. More...
 
void flush_internal_arrays ()
 Flushes the internal arrays into an external array. More...
 
void refill_extract_buffer (size_t minimum_size=0, size_t maximum_size=0)
 Refills the extract buffer from the external arrays. More...
 
void wait_next_ea_blocks (unsigned_type ea_index)
 Requests more EM data from a given EA and updates the winner trees and hints accordingly. More...
 

Static Protected Member Functions

template<typename RandomAccessIterator , typename HeapCompareType >
static unsigned_type push_heap (RandomAccessIterator first, RandomAccessIterator last, HeapCompareType comp)
 SiftUp a new element from the last position in the heap, reestablishing the heap invariant. More...
 

Protected Attributes

unsigned_type m_bulk_first_delayed_external_array
 First index in m_external_arrays that was not re-hinted during a bulk_push sequence. More...
 
size_type m_extract_buffer_index
 Index of the currently smallest element in the extract buffer. More...
 
bool m_in_bulk_push
 Flag if inside a bulk_push sequence. More...
 
bool m_is_very_large_bulk
 If the bulk currently being inserted is very large, this boolean is set and bulk_push just accumulate the elements for eventual sorting. More...
 
stats_type m_stats
 
Number of elements currently in the data structures
size_type m_heaps_size
 Number of elements int the insertion heaps. More...
 
size_type m_extract_buffer_size
 Number of elements in the extract buffer. More...
 
size_type m_internal_size
 Number of elements in the internal arrays. More...
 
size_type m_external_size
 Number of elements in the external arrays. More...
 

Static Protected Attributes

Compile-Time Parameters
static const bool c_merge_sorted_heaps = true
 Merge sorted heaps when flushing into an internal array. Pro: Reduces the risk of a large winner tree Con: Flush insertion heaps becomes slower. More...
 
static const unsigned c_num_write_buffer_blocks = 14
 Default number of write buffer block for a new external array being filled. More...
 
static const unsigned c_num_reserved_external_arrays = 10
 Defines for how much external arrays memory should be reserved in the constructor. More...
 
static const size_type c_default_single_heap_ram = 1L * 1024L * 1024L
 Size of a single insertion heap in Byte, if not defined otherwise in the constructor. Default: 1 MiB. More...
 
static const double c_default_extract_buffer_ram_part = 0.05
 Default limit of the extract buffer ram consumption as share of total ram. More...
 
static const bool c_limit_extract_buffer = true
 Limit the size of the extract buffer to an absolute value. More...
 
static const unsigned c_single_insert_limit = 100
 For bulks of size up to c_single_insert_limit sequential single insert is faster than bulk_push. More...
 

Types

typedef ValueType value_type
 
typedef CompareType compare_type
 
typedef AllocStrategy alloc_strategy
 
typedef uint64 size_type
 
typedef typed_block
< block_size, value_type
block_type
 
typedef std::vector< BID
< block_size > > 
bid_vector
 
typedef bid_vector bids_container_type
 
typedef read_write_pool
< block_type
pool_type
 
typedef
ppq_local::internal_array
< value_type
internal_array_type
 
typedef
ppq_local::external_array
< value_type, block_size,
AllocStrategy > 
external_array_type
 
typedef
external_array_type::writer_type 
external_array_writer_type
 
typedef std::vector
< value_type >::iterator 
value_iterator
 
typedef
internal_array_type::iterator 
iterator
 
typedef std::pair< iterator,
iterator
iterator_pair_type
 
typedef std::vector< value_typeheap_type
 type of insertion heap itself More...
 
typedef stxxl::swap_vector
< internal_array_type
internal_arrays_type
 type of internal arrays vector More...
 
typedef stxxl::swap_vector
< external_array_type
external_arrays_type
 type of external arrays vector More...
 
typedef ppq_local::minima_tree
< parallel_priority_queue
< value_type, compare_type,
alloc_strategy, block_size,
DefaultMemSize, MaxItems > > 
minima_type
 type of minima tree combining the structures More...
 
typedef
dummy_custom_stats_counter
< uint64
stats_counter
 Defines if statistics are gathered: dummy_custom_stats_counter or custom_stats_counter. More...
 
typedef fake_timer stats_timer
 Defines if statistics are gathered: fake_timer or timer. More...
 
static const uint64 block_size = BlockSize
 
static const bool debug = false
 
unsigned_type c_max_internal_level_size
 currently global public tuning parameter: More...
 
unsigned_type c_max_external_level_size
 currently global public tuning parameter: More...
 
compare_type m_compare
 <-Comparator for value_type More...
 
inv_compare_type m_inv_compare
 >-Comparator for value_type More...
 

Parameters and Sizes for Memory Allocation Policy

const long m_num_insertion_heaps
 Number of insertion heaps. Usually equal to the number of CPUs. More...
 
const unsigned m_insertion_heap_capacity
 Capacity of one inserion heap. More...
 
const size_type m_mem_total
 Total amount of internal memory. More...
 
size_type m_extract_buffer_limit
 Maximum size of extract buffer in number of elements Only relevant if c_limit_extract_buffer==true. More...
 
const size_type m_mem_for_heaps
 Size of all insertion heaps together in bytes. More...
 
const float m_num_read_blocks_per_ea
 Number of read/prefetch blocks per external array. More...
 
unsigned_type m_num_read_blocks
 Total number of read/prefetch buffer blocks. More...
 
unsigned_type m_num_hinted_blocks
 number of currently hinted prefetch blocks More...
 
unsigned_type m_num_used_read_blocks
 number of currently loaded blocks More...
 
size_type m_mem_left
 Free memory in bytes. More...
 
size_type insertion_heap_int_memory () const
 Return size of insertion heap reservation in bytes. More...
 

Data Holding Structures

typedef std::vector
< ProcessorData * > 
proc_vector_type
 
proc_vector_type m_proc
 Array of processor local data structures, including the insertion heaps. More...
 
pool_type m_pool
 Prefetch and write buffer pool for external arrays (has to be in front of m_external_arrays) More...
 
std::vector< value_typem_extract_buffer
 The extract buffer where external (and internal) arrays are merged into for extracting. More...
 
internal_arrays_type m_internal_arrays
 The sorted arrays in internal memory. More...
 
external_arrays_type m_external_arrays
 The sorted arrays in external memory. More...
 
std::vector< value_typem_aggregated_pushes
 The aggregated pushes. They cannot be extracted yet. More...
 
unsigned_type m_internal_levels [c_max_internal_levels]
 The number of internal arrays on each level, we use plain array. More...
 
unsigned_type m_external_levels [c_max_external_levels]
 The number of external arrays on each level, we use plain array. More...
 
minima_type m_minima
 The winner tree containing the smallest values of all sources where the globally smallest element could come from. More...
 
struct
stxxl::parallel_priority_queue::external_min_comparator 
m_external_min_comparator
 
winner_tree
< external_min_comparator
m_external_min_tree
 Tracks the largest accessible values of the external arrays if there is unaccessible data in EM. The winning array is the first one that needs to fetch further data from EM. Used in calculate_merge_sequences. More...
 
struct
stxxl::parallel_priority_queue::hint_comparator 
m_hint_comparator
 
winner_tree< hint_comparatorm_hint_tree
 Tracks the largest values of the block hinted the latest of the external arrays if there is unaccessible data in EM. The winning array is the first one that needs to fetch further data from EM. Used for prefetch hints. More...
 
random_number32_r m_rng
 Random number generator for randomly selecting a heap in sequential push() More...
 
static const unsigned_type c_max_internal_levels = 8
 The maximum number of internal array levels. More...
 
static const unsigned_type c_max_external_levels = 8
 The maximum number of external array levels. More...
 

Initialization

void check_invariants () const
 Assert many invariants of the data structures. More...
 
 parallel_priority_queue (const compare_type &compare=compare_type(), size_type total_ram=DefaultMemSize, float num_read_blocks_per_ea=1.5f, unsigned_type num_write_buffer_blocks=c_num_write_buffer_blocks, unsigned_type num_insertion_heaps=0, size_type single_heap_ram=c_default_single_heap_ram, size_type extract_buffer_ram=0)
 Constructor. More...
 
 ~parallel_priority_queue ()
 Destructor. More...
 

Properties

bool extract_buffer_empty () const
 Returns if the extract buffer is empty. More...
 
size_type size () const
 The number of elements in the queue. More...
 
bool empty () const
 Returns if the queue is empty. More...
 
size_type memory_consumption () const
 The memory consumption in Bytes. More...
 

Bulk-Limit Operations

value_type m_limit_element
 current limit element More...
 
bool m_limit_extract
 flag if inside a bulk limit extract session More...
 
bool m_limit_has_full_range
 flag if the extract buffer contains the full limit range More...
 
void limit_begin (const value_type &limit, size_type bulk_size)
 Begin bulk-limit extraction session with limit element. More...
 
void limit_push (const value_type &element, const unsigned_type p=0)
 Push new item >= bulk-limit element into insertion heap p. More...
 
const value_typelimit_top ()
 Access the minimum element, which can only be in the extract buffer. More...
 
void limit_pop ()
 Remove the minimum element, only works correctly while elements < L. More...
 
void limit_end ()
 Finish bulk-limit extraction session. More...
 

Additional Inherited Members

- Private Member Functions inherited from stxxl::noncopyable
 noncopyable ()
 

Member Typedef Documentation

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
typedef AllocStrategy stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::alloc_strategy

Definition at line 1875 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
typedef std::vector<BID<block_size> > stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::bid_vector

Definition at line 1880 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
typedef bid_vector stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::bids_container_type

Definition at line 1881 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
typedef typed_block<block_size, value_type> stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::block_type

Definition at line 1879 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
typedef CompareType stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::compare_type

Definition at line 1874 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
typedef ppq_local::external_array<value_type, block_size, AllocStrategy> stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::external_array_type

Definition at line 1884 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
typedef external_array_type::writer_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::external_array_writer_type

Definition at line 1885 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
typedef stxxl::swap_vector<external_array_type> stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::external_arrays_type
protected

type of external arrays vector

Definition at line 1905 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
typedef std::vector<value_type> stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::heap_type
protected

type of insertion heap itself

Definition at line 1900 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
typedef ppq_local::internal_array<value_type> stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::internal_array_type

Definition at line 1883 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
typedef stxxl::swap_vector<internal_array_type> stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::internal_arrays_type
protected

type of internal arrays vector

Definition at line 1903 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
typedef internal_array_type::iterator stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::iterator

Definition at line 1887 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
typedef std::pair<iterator, iterator> stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::iterator_pair_type

Definition at line 1888 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
typedef ppq_local::minima_tree< parallel_priority_queue<value_type, compare_type, alloc_strategy, block_size, DefaultMemSize, MaxItems> > stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::minima_type
protected

type of minima tree combining the structures

Definition at line 1909 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
typedef read_write_pool<block_type> stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::pool_type

Definition at line 1882 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
typedef std::vector<ProcessorData*> stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::proc_vector_type
protected

Definition at line 2079 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
typedef uint64 stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::size_type

Definition at line 1877 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
typedef dummy_custom_stats_counter<uint64> stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::stats_counter
protected

Defines if statistics are gathered: dummy_custom_stats_counter or custom_stats_counter.

Definition at line 1938 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
typedef fake_timer stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::stats_timer
protected

Defines if statistics are gathered: fake_timer or timer.

Definition at line 1941 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
typedef std::vector<value_type>::iterator stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::value_iterator

Definition at line 1886 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
typedef ValueType stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::value_type

Definition at line 1873 of file parallel_priority_queue.h.

Constructor & Destructor Documentation

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::parallel_priority_queue ( const compare_type compare = compare_type(),
size_type  total_ram = DefaultMemSize,
float  num_read_blocks_per_ea = 1.5f,
unsigned_type  num_write_buffer_blocks = c_num_write_buffer_blocks,
unsigned_type  num_insertion_heaps = 0,
size_type  single_heap_ram = c_default_single_heap_ram,
size_type  extract_buffer_ram = 0 
)
inline

Constructor.

Parameters
compareComparator for priority queue, which is a Max-PQ.
total_ramMaximum RAM usage. 0 = Default = Use the template value DefaultMemSize.
num_read_blocks_per_eaNumber of read blocks per external array. Default = 1.5f
num_write_buffer_blocksNumber of write buffer blocks for a new external array being filled. 0 = Default = c_num_write_buffer_blocks
num_insertion_heapsNumber of insertion heaps. 0 = Default = Determine by omp_get_max_threads().
single_heap_ramMemory usage for a single insertion heap. Default = c_single_heap_ram.
extract_buffer_ramMemory usage for the extract buffer. Only relevant if c_limit_extract_buffer==true. 0 = Default = total_ram * c_default_extract_buffer_ram_part.

Definition at line 2325 of file parallel_priority_queue.h.

References stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::ProcessorData::insertion_heap, and STXXL_ERRMSG.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::~parallel_priority_queue ( )
inline

Destructor.

Definition at line 2447 of file parallel_priority_queue.h.

Member Function Documentation

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::add_as_internal_array ( std::vector< value_type > &  values,
unsigned_type  used = 0,
unsigned_type  level = 0 
)
inlineprotected

Add new internal array, which requires that values are sorted! automatically decreases m_mem_left! also merges internal arrays if there are too many internal arrays on the same level.

Definition at line 4403 of file parallel_priority_queue.h.

References stxxl::ppq_local::internal_array< ValueType >::int_memory(), stxxl::potentially_parallel::multiway_merge(), STXXL_ASSERT, STXXL_CHECK, and STXXL_DEBUG.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::advance_arrays ( std::vector< iterator_pair_type > &  sequences,
std::vector< size_type > &  sizes,
size_t  eas,
size_t  ias 
)
inlineprotected

Definition at line 3868 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::aggregate_push ( const value_type element)
inline

Aggregate pushes.

Use flush_aggregated_pushes() to finally push them. extract_min is allowed is allowed in between the aggregation of pushes if you can assure, that the extracted value is smaller than all of the aggregated values.

Parameters
elementThe element to push.

Definition at line 2984 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::bulk_pop ( std::vector< value_type > &  out,
size_t  max_size 
)
inline

Extract up to max_size values at once.

Definition at line 2812 of file parallel_priority_queue.h.

References STXXL_DEBUG.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
bool stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::bulk_pop_limit ( std::vector< value_type > &  out,
const value_type limit,
size_t  max_size = std::numeric_limits<size_t>::max() 
)
inline

Extracts all elements which are greater or equal to a given limit.

Parameters
outresult vector
limitlimit value
max_sizemaximum number of items to extract
Returns
true if the buffer contains all items < limit, false it was too small.

Definition at line 2842 of file parallel_priority_queue.h.

References stxxl::potentially_parallel::multiway_merge(), STXXL_ASSERT, and STXXL_DEBUG.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::bulk_push ( const value_type element,
const unsigned_type  p 
)
inline

Push an element inside a sequence of pushes.

Run bulk_push_begin() before using this method.

Parameters
elementThe element to push.
pThe id of the insertion heap to use (usually the thread id).

Definition at line 2634 of file parallel_priority_queue.h.

References UNLIKELY.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::bulk_push ( const value_type element)
inline

Push an element inside a bulk sequence of pushes.

Run bulk_push_begin() before using this method. This function uses the insertion heap id = omp_get_thread_num().

Parameters
elementThe element to push.

Definition at line 2708 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::bulk_push_begin ( size_type  bulk_size)
inline

Start a sequence of push operations.

Parameters
bulk_sizeExact number of elements to push before the next pop.

Definition at line 2599 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::bulk_push_end ( )
inline

Ends a sequence of push operations.

Run bulk_push_begin() and some bulk_push() before this.

Definition at line 2722 of file parallel_priority_queue.h.

References STXXL_DEBUG.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
size_t stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::calculate_merge_sequences ( std::vector< size_type > &  sizes,
std::vector< iterator_pair_type > &  sequences,
bool  reuse_previous_lower_bounds = false 
)
inlineprotected

Calculates the sequences vector needed by the multiway merger, considering inaccessible data from external arrays. The sizes vector stores the size of each sequence.

Parameters
reuse_previous_lower_boundsReuse upper bounds from previous runs. sequences[i].second must be valid upper bound iterator from a previous run!
Returns
the index of the external array which is limiting factor or m_external_arrays.size() if not limited.

Definition at line 3598 of file parallel_priority_queue.h.

References STXXL_ASSERT, and STXXL_DEBUG.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::check_external_level ( unsigned_type  level,
bool  force_merge_all = false 
)
inlineprotected
template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::check_invariants ( ) const
inlineprotected

Assert many invariants of the data structures.

Definition at line 2459 of file parallel_priority_queue.h.

References stxxl::is_heap(), STXXL_CHECK, and STXXL_CHECK_EQUAL.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::cleanup_external_arrays ( )
inlineprotected

Clean up empty external arrays, free their memory and capacity.

Definition at line 2207 of file parallel_priority_queue.h.

References STXXL_DEBUG.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::cleanup_internal_arrays ( )
inlineprotected

Clean up empty internal arrays, free their memory and capacity.

Definition at line 2184 of file parallel_priority_queue.h.

References STXXL_DEBUG0, and stxxl::swap_remove_if().

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::convert_eb_into_ia ( bool  do_not_flush = false)
inlineprotected

Convert extract buffer into a new internal array.

Definition at line 3716 of file parallel_priority_queue.h.

References STXXL_DEBUG.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
bool stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::empty ( ) const
inline

Returns if the queue is empty.

Definition at line 2570 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
bool stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::extract_buffer_empty ( ) const
inlineprotected

Returns if the extract buffer is empty.

Definition at line 2584 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::flush_array_internal ( std::vector< value_type > &  values)
inlineprotected

Sorts the values from values and writes them into an internal array.

Don't use the value vector afterwards!

Parameters
valuesthe vector to sort and store

Definition at line 4498 of file parallel_priority_queue.h.

References stxxl::sort().

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::flush_ia_ea_until_memory_free ( internal_size_type  mem_free)
inline

Free up memory by flushing internal arrays and combining external arrays until enough bytes are free.

Definition at line 3377 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::flush_insertion_heap ( unsigned_type  p)
inlineprotected

Flushes the insertions heap p into an internal array.

Definition at line 3914 of file parallel_priority_queue.h.

References stxxl::sort(), and STXXL_DEBUG0.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::flush_insertion_heaps ( )
inlineprotected

Flushes all insertions heaps into an internal array.

Definition at line 3965 of file parallel_priority_queue.h.

References stxxl::potentially_parallel::multiway_merge(), and stxxl::sort().

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::flush_insertion_heaps_with_limit ( const value_type limit)
inlineprotected

Flushes all elements of the insertion heaps which are greater or equal to a given limit.

Parameters
limitlimit value

Definition at line 3279 of file parallel_priority_queue.h.

References stxxl::sort(), and STXXL_DEBUG.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::flush_internal_arrays ( )
inlineprotected

Flushes the internal arrays into an external array.

Definition at line 4048 of file parallel_priority_queue.h.

References stxxl::ppq_local::external_array_writer< ExternalArrayType >::begin(), stxxl::potentially_parallel::multiway_merge(), and STXXL_DEBUG.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::hint_external_arrays ( )
inline

Hints EA blocks which will be needed soon. Hints at most m_num_prefetchers blocks globally.

Definition at line 3534 of file parallel_priority_queue.h.

References STXXL_DEBUG.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
size_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::insertion_heap_int_memory ( ) const
inlineprotected

Return size of insertion heap reservation in bytes.

Definition at line 2003 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::limit_begin ( const value_type limit,
size_type  bulk_size 
)
inline

Begin bulk-limit extraction session with limit element.

Definition at line 3175 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::limit_end ( )
inline

Finish bulk-limit extraction session.

Definition at line 3264 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::limit_pop ( )
inline

Remove the minimum element, only works correctly while elements < L.

Definition at line 3236 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::limit_push ( const value_type element,
const unsigned_type  p = 0 
)
inline

Push new item >= bulk-limit element into insertion heap p.

Definition at line 3196 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
const value_type& stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::limit_top ( )
inline

Access the minimum element, which can only be in the extract buffer.

Definition at line 3205 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
size_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::memory_consumption ( ) const
inline

The memory consumption in Bytes.

Definition at line 2576 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::merge_external_arrays ( )
inline

Merges all external arrays and all internal arrays into one external array.

Public for benchmark purposes.

Definition at line 3357 of file parallel_priority_queue.h.

References STXXL_DEBUG, and STXXL_ERRMSG.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::pop ( )
inline

Remove the minimum element.

Definition at line 3084 of file parallel_priority_queue.h.

References min(), and STXXL_ERRMSG.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::print_stats ( ) const
inline

Print statistics.

Definition at line 3563 of file parallel_priority_queue.h.

References STXXL_MEMDUMP, STXXL_MSG, and STXXL_VARDUMP.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::push ( const value_type element,
unsigned_type  p = 0 
)
inline

Insert new element.

Parameters
elementthe element to insert.
pnumber of insertion heap to insert item into

Definition at line 3025 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
template<typename RandomAccessIterator , typename HeapCompareType >
static unsigned_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::push_heap ( RandomAccessIterator  first,
RandomAccessIterator  last,
HeapCompareType  comp 
)
inlinestaticprotected

SiftUp a new element from the last position in the heap, reestablishing the heap invariant.

This is identical to std::push_heap, except that it returns the last element modified by siftUp. Thus we can identify if the minimum may have changed.

Definition at line 2275 of file parallel_priority_queue.h.

References STXXL_MOVE.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::rebuild_hint_tree ( )
inline

Rebuild hint tree completely as the hint sequence may have changed, and re-hint the correct block sequence.

Definition at line 3445 of file parallel_priority_queue.h.

References STXXL_DEBUG.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::refill_extract_buffer ( size_t  minimum_size = 0,
size_t  maximum_size = 0 
)
inlineprotected

Refills the extract buffer from the external arrays.

Parameters
minimum_sizerequested minimum size of the resulting extract buffer. Prints a warning if there is not enough data to reach this size.
maximum_sizemaximum size of the extract buffer. Using m_extract_buffer_limit if set to 0.

Definition at line 3751 of file parallel_priority_queue.h.

References stxxl::potentially_parallel::multiway_merge(), STXXL_DEBUG, and STXXL_MSG.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::resize_read_pool ( )
inline

Automatically resize the read/prefetch buffer pool depending on number of external arrays.

Definition at line 3393 of file parallel_priority_queue.h.

References STXXL_ASSERT, STXXL_DEBUG, and STXXL_ERRMSG.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
size_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::size ( ) const
inline

The number of elements in the queue.

Definition at line 2564 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
const value_type& stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::top ( )
inline

Access the minimum element.

Definition at line 3046 of file parallel_priority_queue.h.

References min(), STXXL_DEBUG, and STXXL_ERRMSG.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::update_external_min_tree ( size_t  ea_index)
inline

Updates the external min tree afer a remove() or a wait_next_blocks() call.

Parameters
ea_indexindex of the external array in question

Definition at line 3522 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::update_hint_tree ( size_t  ea_index)
inline

Updates the prefetch prediction tree afer a remove_items(), which frees up blocks.

Parameters
ea_indexindex of the external array in question

Definition at line 3507 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
void stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::wait_next_ea_blocks ( unsigned_type  ea_index)
inlineprotected

Requests more EM data from a given EA and updates the winner trees and hints accordingly.

Definition at line 3856 of file parallel_priority_queue.h.

Member Data Documentation

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
const uint64 stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::block_size = BlockSize
static

Definition at line 1876 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
const double stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::c_default_extract_buffer_ram_part = 0.05
staticprotected

Default limit of the extract buffer ram consumption as share of total ram.

Definition at line 1970 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
const size_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::c_default_single_heap_ram = 1L * 1024L * 1024L
staticprotected

Size of a single insertion heap in Byte, if not defined otherwise in the constructor. Default: 1 MiB.

Definition at line 1963 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
const bool stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::c_limit_extract_buffer = true
staticprotected

Limit the size of the extract buffer to an absolute value.

The actual size can be set using the extract_buffer_ram parameter of the constructor. If this parameter is not set, the value is calculated by (total_ram*c_default_extract_buffer_ram_part)

If c_limit_extract_buffer==false, the memory consumption of the extract buffer is only limited by the number of external and internal arrays. This is considered in memory management using the ram_per_external_array and ram_per_internal_array values. Attention: Each internal array reserves space for the extract buffer in the size of all heaps together.

Definition at line 1986 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
unsigned_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::c_max_external_level_size

currently global public tuning parameter:

Definition at line 1896 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
const unsigned_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::c_max_external_levels = 8
staticprotected

The maximum number of external array levels.

Definition at line 2108 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
unsigned_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::c_max_internal_level_size

currently global public tuning parameter:

Definition at line 1893 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
const unsigned_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::c_max_internal_levels = 8
staticprotected

The maximum number of internal array levels.

Definition at line 2102 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
const bool stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::c_merge_sorted_heaps = true
staticprotected

Merge sorted heaps when flushing into an internal array. Pro: Reduces the risk of a large winner tree Con: Flush insertion heaps becomes slower.

Definition at line 1951 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
const unsigned stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::c_num_reserved_external_arrays = 10
staticprotected

Defines for how much external arrays memory should be reserved in the constructor.

Definition at line 1959 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
const unsigned stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::c_num_write_buffer_blocks = 14
staticprotected

Default number of write buffer block for a new external array being filled.

Definition at line 1955 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
const unsigned stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::c_single_insert_limit = 100
staticprotected

For bulks of size up to c_single_insert_limit sequential single insert is faster than bulk_push.

Definition at line 1990 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
const bool stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::debug = false
static

Definition at line 1890 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
std::vector<value_type> stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_aggregated_pushes
protected

The aggregated pushes. They cannot be extracted yet.

Definition at line 2099 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
unsigned_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_bulk_first_delayed_external_array
protected

First index in m_external_arrays that was not re-hinted during a bulk_push sequence.

Definition at line 2042 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
compare_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_compare
protected

<-Comparator for value_type

Definition at line 1931 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
external_arrays_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_external_arrays
protected

The sorted arrays in external memory.

Definition at line 2096 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
unsigned_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_external_levels[c_max_external_levels]
protected

The number of external arrays on each level, we use plain array.

Definition at line 2111 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
struct stxxl::parallel_priority_queue::external_min_comparator stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_external_min_comparator
protected
template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
winner_tree<external_min_comparator> stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_external_min_tree
protected

Tracks the largest accessible values of the external arrays if there is unaccessible data in EM. The winning array is the first one that needs to fetch further data from EM. Used in calculate_merge_sequences.

Definition at line 2136 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
size_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_external_size
protected

Number of elements in the external arrays.

Definition at line 2060 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
std::vector<value_type> stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_extract_buffer
protected

The extract buffer where external (and internal) arrays are merged into for extracting.

Definition at line 2090 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
size_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_extract_buffer_index
protected

Index of the currently smallest element in the extract buffer.

Definition at line 2045 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
size_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_extract_buffer_limit
protected

Maximum size of extract buffer in number of elements Only relevant if c_limit_extract_buffer==true.

Definition at line 2013 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
size_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_extract_buffer_size
protected

Number of elements in the extract buffer.

Definition at line 2054 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
size_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_heaps_size
protected

Number of elements int the insertion heaps.

Definition at line 2051 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
struct stxxl::parallel_priority_queue::hint_comparator stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_hint_comparator
protected
template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
winner_tree<hint_comparator> stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_hint_tree
protected

Tracks the largest values of the block hinted the latest of the external arrays if there is unaccessible data in EM. The winning array is the first one that needs to fetch further data from EM. Used for prefetch hints.

Definition at line 2159 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
bool stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_in_bulk_push
protected

Flag if inside a bulk_push sequence.

Definition at line 2034 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
const unsigned stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_insertion_heap_capacity
protected

Capacity of one inserion heap.

Definition at line 2000 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
internal_arrays_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_internal_arrays
protected

The sorted arrays in internal memory.

Definition at line 2093 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
unsigned_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_internal_levels[c_max_internal_levels]
protected

The number of internal arrays on each level, we use plain array.

Definition at line 2105 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
size_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_internal_size
protected

Number of elements in the internal arrays.

Definition at line 2057 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
inv_compare_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_inv_compare
protected

>-Comparator for value_type

Definition at line 1934 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
bool stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_is_very_large_bulk
protected

If the bulk currently being inserted is very large, this boolean is set and bulk_push just accumulate the elements for eventual sorting.

Definition at line 2038 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
value_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_limit_element
protected

current limit element

Definition at line 3165 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
bool stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_limit_extract
protected

flag if inside a bulk limit extract session

Definition at line 3168 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
bool stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_limit_has_full_range
protected

flag if the extract buffer contains the full limit range

Definition at line 3171 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
const size_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_mem_for_heaps
protected

Size of all insertion heaps together in bytes.

Definition at line 2016 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
size_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_mem_left
protected

Free memory in bytes.

Definition at line 2029 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
const size_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_mem_total
protected

Total amount of internal memory.

Definition at line 2009 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
minima_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_minima
protected

The winner tree containing the smallest values of all sources where the globally smallest element could come from.

Definition at line 2115 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
unsigned_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_num_hinted_blocks
protected

number of currently hinted prefetch blocks

Definition at line 2024 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
const long stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_num_insertion_heaps
protected

Number of insertion heaps. Usually equal to the number of CPUs.

Definition at line 1997 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
unsigned_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_num_read_blocks
protected

Total number of read/prefetch buffer blocks.

Definition at line 2022 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
const float stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_num_read_blocks_per_ea
protected

Number of read/prefetch blocks per external array.

Definition at line 2019 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
unsigned_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_num_used_read_blocks
protected

number of currently loaded blocks

Definition at line 2026 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
pool_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_pool
protected

Prefetch and write buffer pool for external arrays (has to be in front of m_external_arrays)

Definition at line 2086 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
proc_vector_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_proc
protected

Array of processor local data structures, including the insertion heaps.

Definition at line 2082 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
random_number32_r stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_rng
protected

Random number generator for randomly selecting a heap in sequential push()

Definition at line 2163 of file parallel_priority_queue.h.

template<class ValueType , class CompareType = std::less<ValueType>, class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY, uint64 BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), uint64 DefaultMemSize = 1* 1024L* 1024L* 1024L, uint64 MaxItems = 0>
stats_type stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::m_stats
protected

Definition at line 4658 of file parallel_priority_queue.h.


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