Intel(R) Threading Building Blocks Doxygen Documentation
version 4.2.3
|
Concurrent priority queue. More...
#include <concurrent_priority_queue.h>
Classes | |
class | cpq_operation |
class | my_functor_t |
Public Types | |
typedef T | value_type |
Element type in the queue. More... | |
typedef T & | reference |
Reference type. More... | |
typedef const T & | const_reference |
Const reference type. More... | |
typedef size_t | size_type |
Integral type for representing size of the queue. More... | |
typedef ptrdiff_t | difference_type |
Difference type for iterator. More... | |
typedef A | allocator_type |
Allocator type. More... | |
Public Member Functions | |
concurrent_priority_queue (const allocator_type &a=allocator_type()) | |
Constructs a new concurrent_priority_queue with default capacity. More... | |
concurrent_priority_queue (const Compare &c, const allocator_type &a=allocator_type()) | |
Constructs a new concurrent_priority_queue with default capacity. More... | |
concurrent_priority_queue (size_type init_capacity, const allocator_type &a=allocator_type()) | |
Constructs a new concurrent_priority_queue with init_sz capacity. More... | |
concurrent_priority_queue (size_type init_capacity, const Compare &c, const allocator_type &a=allocator_type()) | |
Constructs a new concurrent_priority_queue with init_sz capacity. More... | |
template<typename InputIterator > | |
concurrent_priority_queue (InputIterator begin, InputIterator end, const allocator_type &a=allocator_type()) | |
[begin,end) constructor More... | |
template<typename InputIterator > | |
concurrent_priority_queue (InputIterator begin, InputIterator end, const Compare &c, const allocator_type &a=allocator_type()) | |
[begin,end) constructor More... | |
concurrent_priority_queue (std::initializer_list< T > init_list, const allocator_type &a=allocator_type()) | |
Constructor from std::initializer_list. More... | |
concurrent_priority_queue (std::initializer_list< T > init_list, const Compare &c, const allocator_type &a=allocator_type()) | |
Constructor from std::initializer_list. More... | |
concurrent_priority_queue (const concurrent_priority_queue &src) | |
Copy constructor. More... | |
concurrent_priority_queue (const concurrent_priority_queue &src, const allocator_type &a) | |
Copy constructor with specific allocator. More... | |
concurrent_priority_queue & | operator= (const concurrent_priority_queue &src) |
Assignment operator. More... | |
concurrent_priority_queue (concurrent_priority_queue &&src) | |
Move constructor. More... | |
concurrent_priority_queue (concurrent_priority_queue &&src, const allocator_type &a) | |
Move constructor with specific allocator. More... | |
concurrent_priority_queue & | operator= (concurrent_priority_queue &&src) |
Move assignment operator. More... | |
template<typename InputIterator > | |
void | assign (InputIterator begin, InputIterator end) |
Assign the queue from [begin,end) range, not thread-safe. More... | |
void | assign (std::initializer_list< T > il) |
Assign the queue from std::initializer_list, not thread-safe. More... | |
concurrent_priority_queue & | operator= (std::initializer_list< T > il) |
Assign from std::initializer_list, not thread-safe. More... | |
bool | empty () const |
Returns true if empty, false otherwise. More... | |
size_type | size () const |
Returns the current number of elements contained in the queue. More... | |
void | push (const_reference elem) |
Pushes elem onto the queue, increasing capacity of queue if necessary. More... | |
void | push (value_type &&elem) |
Pushes elem onto the queue, increasing capacity of queue if necessary. More... | |
template<typename... Args> | |
void | emplace (Args &&... args) |
Constructs a new element using args as the arguments for its construction and pushes it onto the queue */. More... | |
bool | try_pop (reference elem) |
Gets a reference to and removes highest priority element. More... | |
void | clear () |
Clear the queue; not thread-safe. More... | |
void | swap (concurrent_priority_queue &q) |
Swap this queue with another; not thread-safe. More... | |
allocator_type | get_allocator () const |
Return allocator object. More... | |
Private Types | |
enum | operation_type { INVALID_OP, PUSH_OP, POP_OP, PUSH_RVALUE_OP } |
enum | operation_status { WAIT =0, SUCCEEDED, FAILED } |
typedef tbb::internal::aggregator< my_functor_t, cpq_operation > | aggregator_t |
typedef std::vector< value_type, allocator_type > | vector_t |
Storage for the heap of elements in queue, plus unheapified elements. More... | |
Private Member Functions | |
void | handle_operations (cpq_operation *op_list) |
void | heapify () |
Merge unsorted elements into heap. More... | |
void | reheap () |
Re-heapify after an extraction. More... | |
void | push_back_helper (const T &t, tbb::internal::true_type) |
void | push_back_helper (const T &, tbb::internal::false_type) |
Private Attributes | |
aggregator_t | my_aggregator |
char | padding1 [NFS_MaxLineSize - sizeof(aggregator_t)] |
Padding added to avoid false sharing. More... | |
size_type | mark |
The point at which unsorted elements begin. More... | |
__TBB_atomic size_type | my_size |
Compare | compare |
char | padding2 [NFS_MaxLineSize -(2 *sizeof(size_type)) - sizeof(Compare)] |
Padding added to avoid false sharing. More... | |
vector_t | data |
Concurrent priority queue.
Definition at line 65 of file concurrent_priority_queue.h.
|
private |
Definition at line 354 of file concurrent_priority_queue.h.
typedef A tbb::interface5::concurrent_priority_queue< T, Compare, A >::allocator_type |
Allocator type.
Definition at line 83 of file concurrent_priority_queue.h.
typedef const T& tbb::interface5::concurrent_priority_queue< T, Compare, A >::const_reference |
Const reference type.
Definition at line 74 of file concurrent_priority_queue.h.
typedef ptrdiff_t tbb::interface5::concurrent_priority_queue< T, Compare, A >::difference_type |
Difference type for iterator.
Definition at line 80 of file concurrent_priority_queue.h.
typedef T& tbb::interface5::concurrent_priority_queue< T, Compare, A >::reference |
Reference type.
Definition at line 71 of file concurrent_priority_queue.h.
typedef size_t tbb::interface5::concurrent_priority_queue< T, Compare, A >::size_type |
Integral type for representing size of the queue.
Definition at line 77 of file concurrent_priority_queue.h.
typedef T tbb::interface5::concurrent_priority_queue< T, Compare, A >::value_type |
Element type in the queue.
Definition at line 68 of file concurrent_priority_queue.h.
|
private |
Storage for the heap of elements in queue, plus unheapified elements.
data has the following structure:
binary unheapified heap elements ____|_______|____ | | | v v v [_|...|_|_|...|_| |...| ] 0 ^ ^ ^ | | |__capacity | |__my_size |__mark
Thus, data stores the binary heap starting at position 0 through mark-1 (it may be empty). Then there are 0 or more elements that have not yet been inserted into the heap, in positions mark through my_size-1.
Definition at line 382 of file concurrent_priority_queue.h.
|
private |
|
private |
Enumerator | |
---|---|
INVALID_OP | |
PUSH_OP | |
POP_OP | |
PUSH_RVALUE_OP |
Definition at line 329 of file concurrent_priority_queue.h.
|
inlineexplicit |
Constructs a new concurrent_priority_queue with default capacity.
Definition at line 86 of file concurrent_priority_queue.h.
|
inlineexplicit |
Constructs a new concurrent_priority_queue with default capacity.
Definition at line 92 of file concurrent_priority_queue.h.
|
inlineexplicit |
Constructs a new concurrent_priority_queue with init_sz capacity.
Definition at line 98 of file concurrent_priority_queue.h.
|
inlineexplicit |
Constructs a new concurrent_priority_queue with init_sz capacity.
Definition at line 106 of file concurrent_priority_queue.h.
|
inline |
[begin,end) constructor
Definition at line 115 of file concurrent_priority_queue.h.
|
inline |
[begin,end) constructor
Definition at line 125 of file concurrent_priority_queue.h.
|
inline |
Constructor from std::initializer_list.
Definition at line 135 of file concurrent_priority_queue.h.
|
inline |
Constructor from std::initializer_list.
Definition at line 144 of file concurrent_priority_queue.h.
|
inline |
Copy constructor.
This operation is unsafe if there are pending concurrent operations on the src queue.
Definition at line 155 of file concurrent_priority_queue.h.
|
inline |
Copy constructor with specific allocator.
This operation is unsafe if there are pending concurrent operations on the src queue.
Definition at line 164 of file concurrent_priority_queue.h.
|
inline |
Move constructor.
This operation is unsafe if there are pending concurrent operations on the src queue.
Definition at line 185 of file concurrent_priority_queue.h.
|
inline |
Move constructor with specific allocator.
This operation is unsafe if there are pending concurrent operations on the src queue.
__TBB_ALLOCATOR_TRAITS_PRESENT
Definition at line 193 of file concurrent_priority_queue.h.
|
inline |
Assign the queue from [begin,end) range, not thread-safe.
Definition at line 235 of file concurrent_priority_queue.h.
|
inline |
Assign the queue from std::initializer_list, not thread-safe.
Definition at line 244 of file concurrent_priority_queue.h.
|
inline |
Clear the queue; not thread-safe.
This operation is unsafe if there are pending concurrent operations on the queue. Resets size, effectively emptying queue; does not free space. May not clear elements added in pending operations.
Definition at line 310 of file concurrent_priority_queue.h.
|
inline |
Constructs a new element using args as the arguments for its construction and pushes it onto the queue */.
This operation can be safely used concurrently with other push, try_pop or emplace operations.
Definition at line 289 of file concurrent_priority_queue.h.
|
inline |
Returns true if empty, false otherwise.
Returned value may not reflect results of pending operations. This operation reads shared data and will trigger a race condition.
Definition at line 256 of file concurrent_priority_queue.h.
|
inline |
Return allocator object.
Definition at line 326 of file concurrent_priority_queue.h.
|
inlineprivate |
Definition at line 385 of file concurrent_priority_queue.h.
Referenced by tbb::interface5::concurrent_priority_queue< T, Compare, A >::my_functor_t::operator()().
|
inlineprivate |
Merge unsorted elements into heap.
Definition at line 469 of file concurrent_priority_queue.h.
|
inline |
Assignment operator.
This operation is unsafe if there are pending concurrent operations on the src queue.
Definition at line 173 of file concurrent_priority_queue.h.
|
inline |
Move assignment operator.
This operation is unsafe if there are pending concurrent operations on the src queue.
__TBB_ALLOCATOR_TRAITS_PRESENT
Definition at line 216 of file concurrent_priority_queue.h.
|
inline |
Assign from std::initializer_list, not thread-safe.
Definition at line 247 of file concurrent_priority_queue.h.
|
inline |
Pushes elem onto the queue, increasing capacity of queue if necessary.
This operation can be safely used concurrently with other push, try_pop or emplace operations.
Definition at line 265 of file concurrent_priority_queue.h.
Referenced by tbb::flow::interface10::internal::prioritize_task().
|
inline |
Pushes elem onto the queue, increasing capacity of queue if necessary.
This operation can be safely used concurrently with other push, try_pop or emplace operations.
Definition at line 278 of file concurrent_priority_queue.h.
|
inlineprivate |
Definition at line 506 of file concurrent_priority_queue.h.
|
inlineprivate |
Definition at line 510 of file concurrent_priority_queue.h.
|
inlineprivate |
Re-heapify after an extraction.
Re-heapify by pushing last element down the heap from the root.
Definition at line 487 of file concurrent_priority_queue.h.
|
inline |
Returns the current number of elements contained in the queue.
Returned value may not reflect results of pending operations. This operation reads shared data and will trigger a race condition.
Definition at line 261 of file concurrent_priority_queue.h.
|
inline |
Swap this queue with another; not thread-safe.
This operation is unsafe if there are pending concurrent operations on the queue.
Definition at line 318 of file concurrent_priority_queue.h.
|
inline |
Gets a reference to and removes highest priority element.
If a highest priority element was found, sets elem and returns true, otherwise returns false. This operation can be safely used concurrently with other push, try_pop or emplace operations.
Definition at line 299 of file concurrent_priority_queue.h.
Referenced by tbb::flow::interface10::internal::priority_task_selector::execute().
|
private |
Definition at line 361 of file concurrent_priority_queue.h.
|
private |
|
private |
The point at which unsorted elements begin.
Definition at line 359 of file concurrent_priority_queue.h.
Referenced by tbb::interface5::concurrent_priority_queue< graph_task *, graph_task_comparator >::operator=(), and tbb::interface5::concurrent_priority_queue< graph_task *, graph_task_comparator >::swap().
|
private |
Definition at line 355 of file concurrent_priority_queue.h.
|
private |
|
private |
Padding added to avoid false sharing.
Definition at line 357 of file concurrent_priority_queue.h.
|
private |
Padding added to avoid false sharing.
Definition at line 363 of file concurrent_priority_queue.h.