tbb::interface5::concurrent_priority_queue< T, Compare, A > Class Template Reference

Concurrent priority queue. More...

`#include <concurrent_priority_queue.h>`

Inheritance diagram for tbb::interface5::concurrent_priority_queue< T, Compare, A >:
Collaboration diagram for tbb::interface5::concurrent_priority_queue< T, Compare, A >:

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

## Public Attributes

const typedef T & | const_reference
| Const reference type. 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

## Detailed Description

### template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>
class tbb::interface5::concurrent_priority_queue< T, Compare, A >

Concurrent priority queue.

Definition at line 68 of file concurrent_priority_queue.h.

## Member Typedef Documentation

## aggregator_t

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

typedef tbb::internal::aggregator< my_functor_t, cpq_operation > tbb::interface5::concurrent_priority_queue< T, Compare, A >::aggregator_t

private

Definition at line 357 of file concurrent_priority_queue.h.

## allocator_type

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

typedef A tbb::interface5::concurrent_priority_queue< T, Compare, A >::allocator_type

Allocator type.

Definition at line 86 of file concurrent_priority_queue.h.

## difference_type

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

typedef ptrdiff_t tbb::interface5::concurrent_priority_queue< T, Compare, A >::difference_type

Difference type for iterator.

Definition at line 83 of file concurrent_priority_queue.h.

## reference

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

typedef T& tbb::interface5::concurrent_priority_queue< T, Compare, A >::reference

Reference type.

Definition at line 74 of file concurrent_priority_queue.h.

## size_type

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

typedef size_t tbb::interface5::concurrent_priority_queue< T, Compare, A >::size_type

Integral type for representing size of the queue.

Definition at line 80 of file concurrent_priority_queue.h.

## value_type

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

typedef T tbb::interface5::concurrent_priority_queue< T, Compare, A >::value_type

Element type in the queue.

Definition at line 71 of file concurrent_priority_queue.h.

## vector_t

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

typedef std::vector<value_type, allocator_type> tbb::interface5::concurrent_priority_queue< T, Compare, A >::vector_t

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 385 of file concurrent_priority_queue.h.

## Member Enumeration Documentation

## operation_status

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

enum tbb::interface5::concurrent_priority_queue::operation_status

private

Enumerator
WAIT |
SUCCEEDED |
FAILED |

Definition at line 333 of file concurrent_priority_queue.h.

{ WAIT=0, SUCCEEDED, FAILED };

## operation_type

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

enum tbb::interface5::concurrent_priority_queue::operation_type

private

Enumerator
INVALID_OP |
PUSH_OP |
POP_OP |
PUSH_RVALUE_OP |

Definition at line 332 of file concurrent_priority_queue.h.

{INVALID_OP, PUSH_OP, POP_OP, PUSH_RVALUE_OP};

## Constructor & Destructor Documentation

## concurrent_priority_queue() [1/12]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

tbb::interface5::concurrent_priority_queue< T, Compare, A >::concurrent_priority_queue | ( | const allocator_type & | a = `allocator_type()` | ) |

inline explicit

Constructs a new concurrent_priority_queue with default capacity.

Definition at line 89 of file concurrent_priority_queue.h.

: mark(0), my_size(0), compare(), data(a)
{
my_aggregator.initialize_handler(my_functor_t(this));
}

## concurrent_priority_queue() [2/12]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

tbb::interface5::concurrent_priority_queue< T, Compare, A >::concurrent_priority_queue | ( | const Compare & | c,
|  | const allocator_type & | a = `allocator_type()`
| ) |  |

inline explicit

Constructs a new concurrent_priority_queue with default capacity.

Definition at line 95 of file concurrent_priority_queue.h.

: mark(0), my_size(0), compare(c), data(a)
{
my_aggregator.initialize_handler(my_functor_t(this));
}

## concurrent_priority_queue() [3/12]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

tbb::interface5::concurrent_priority_queue< T, Compare, A >::concurrent_priority_queue | ( | size_type | init_capacity,
|  | const allocator_type & | a = `allocator_type()`
| ) |  |

inline explicit

Constructs a new concurrent_priority_queue with init_sz capacity.

Definition at line 101 of file concurrent_priority_queue.h.

:
mark(0), my_size(0), compare(), data(a)
{
data.reserve(init_capacity);
my_aggregator.initialize_handler(my_functor_t(this));
}

## concurrent_priority_queue() [4/12]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

tbb::interface5::concurrent_priority_queue< T, Compare, A >::concurrent_priority_queue | ( | size_type | init_capacity,
|  | const Compare & | c,
|  | const allocator_type & | a = `allocator_type()`
| ) |  |

inline explicit

Constructs a new concurrent_priority_queue with init_sz capacity.

Definition at line 109 of file concurrent_priority_queue.h.

:
mark(0), my_size(0), compare(c), data(a)
{
data.reserve(init_capacity);
my_aggregator.initialize_handler(my_functor_t(this));
}

## concurrent_priority_queue() [5/12]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>
template<typename InputIterator >

tbb::interface5::concurrent_priority_queue< T, Compare, A >::concurrent_priority_queue | ( | InputIterator | begin,
|  | InputIterator | end,
|  | const allocator_type & | a = `allocator_type()`
| ) |  |

inline

[begin,end) constructor

Definition at line 118 of file concurrent_priority_queue.h.

:
mark(0), compare(), data(begin, end, a)
{
my_aggregator.initialize_handler(my_functor_t(this));
heapify();
my_size = data.size();
}

## concurrent_priority_queue() [6/12]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>
template<typename InputIterator >

tbb::interface5::concurrent_priority_queue< T, Compare, A >::concurrent_priority_queue | ( | InputIterator | begin,
|  | InputIterator | end,
|  | const Compare & | c,
|  | const allocator_type & | a = `allocator_type()`
| ) |  |

inline

[begin,end) constructor

Definition at line 128 of file concurrent_priority_queue.h.

:
mark(0), compare(c), data(begin, end, a)
{
my_aggregator.initialize_handler(my_functor_t(this));
heapify();
my_size = data.size();
}

## concurrent_priority_queue() [7/12]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

tbb::interface5::concurrent_priority_queue< T, Compare, A >::concurrent_priority_queue | ( | std::initializer_list< T > | init_list,
|  | const allocator_type & | a = `allocator_type()`
| ) |  |

inline

Constructor from std::initializer_list.

Definition at line 138 of file concurrent_priority_queue.h.

:
mark(0), compare(), data(init_list.begin(), init_list.end(), a)
{
my_aggregator.initialize_handler(my_functor_t(this));
heapify();
my_size = data.size();
}

## concurrent_priority_queue() [8/12]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

tbb::interface5::concurrent_priority_queue< T, Compare, A >::concurrent_priority_queue | ( | std::initializer_list< T > | init_list,
|  | const Compare & | c,
|  | const allocator_type & | a = `allocator_type()`
| ) |  |

inline

Constructor from std::initializer_list.

Definition at line 147 of file concurrent_priority_queue.h.

:
mark(0), compare(c), data(init_list.begin(), init_list.end(), a)
{
my_aggregator.initialize_handler(my_functor_t(this));
heapify();
my_size = data.size();
}

## concurrent_priority_queue() [9/12]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

tbb::interface5::concurrent_priority_queue< T, Compare, A >::concurrent_priority_queue | ( | const concurrent_priority_queue< T, Compare, A > & | src | ) |

inline

Copy constructor.

This operation is unsafe if there are pending concurrent operations on the src queue.

Definition at line 158 of file concurrent_priority_queue.h.

: mark(src.mark),
my_size(src.my_size), data(src.data.begin(), src.data.end(), src.data.get_allocator())
{
my_aggregator.initialize_handler(my_functor_t(this));
heapify();
}

## concurrent_priority_queue() [10/12]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

tbb::interface5::concurrent_priority_queue< T, Compare, A >::concurrent_priority_queue | ( | const concurrent_priority_queue< T, Compare, A > & | src,
|  | const allocator_type & | a
| ) |  |

inline

Copy constructor with specific allocator.

This operation is unsafe if there are pending concurrent operations on the src queue.

Definition at line 167 of file concurrent_priority_queue.h.

: mark(src.mark),
my_size(src.my_size), data(src.data.begin(), src.data.end(), a)
{
my_aggregator.initialize_handler(my_functor_t(this));
heapify();
}

## concurrent_priority_queue() [11/12]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

tbb::interface5::concurrent_priority_queue< T, Compare, A >::concurrent_priority_queue | ( | concurrent_priority_queue< T, Compare, A > && | src | ) |

inline

Move constructor.

This operation is unsafe if there are pending concurrent operations on the src queue.

Definition at line 188 of file concurrent_priority_queue.h.

: mark(src.mark),
my_size(src.my_size), data(std::move(src.data))
{
my_aggregator.initialize_handler(my_functor_t(this));
}

## concurrent_priority_queue() [12/12]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

tbb::interface5::concurrent_priority_queue< T, Compare, A >::concurrent_priority_queue | ( | concurrent_priority_queue< T, Compare, A > && | src,
|  | const allocator_type & | a
| ) |  |

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 196 of file concurrent_priority_queue.h.

: mark(src.mark),
my_size(src.my_size),
#if __TBB_ALLOCATOR_TRAITS_PRESENT
data(std::move(src.data), a)
#else
// Some early version of C++11 STL vector does not have a constructor of vector(vector&& , allocator).
// It seems that the reason is absence of support of allocator_traits (stateful allocators).
data(a)
#endif //__TBB_ALLOCATOR_TRAITS_PRESENT
{
my_aggregator.initialize_handler(my_functor_t(this));
#if !__TBB_ALLOCATOR_TRAITS_PRESENT
if (a != src.data.get_allocator()){
data.reserve(src.data.size());
data.assign(std::make_move_iterator(src.data.begin()), std::make_move_iterator(src.data.end()));
}else{
data = std::move(src.data);
}
#endif
}

## Member Function Documentation

## assign() [1/2]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>
template<typename InputIterator >

void tbb::interface5::concurrent_priority_queue< T, Compare, A >::assign | ( | InputIterator | begin,
|  | InputIterator | end
| ) |  |

inline

Assign the queue from [begin,end) range, not thread-safe.

Definition at line 238 of file concurrent_priority_queue.h.

{
vector_t(begin, end, data.get_allocator()).swap(data);
mark = 0;
my_size = data.size();
heapify();
}

## assign() [2/2]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

void tbb::interface5::concurrent_priority_queue< T, Compare, A >::assign | ( | std::initializer_list< T > | il | ) |

inline

Assign the queue from std::initializer_list, not thread-safe.

Definition at line 247 of file concurrent_priority_queue.h.

{ this->assign(il.begin(), il.end()); }

## clear()

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

void tbb::interface5::concurrent_priority_queue< T, Compare, A >::clear | ( |  | ) |

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 313 of file concurrent_priority_queue.h.

{
data.clear();
mark = 0;
my_size = 0;
}

## emplace()

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>
template<typename... Args>

void tbb::interface5::concurrent_priority_queue< T, Compare, A >::emplace | ( | Args &&... | args | ) |

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 292 of file concurrent_priority_queue.h.

{
push(value_type(std::forward<Args>(args)...));
}

## empty()

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

bool tbb::interface5::concurrent_priority_queue< T, Compare, A >::empty | ( |  | ) | const

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 259 of file concurrent_priority_queue.h.

{ return size()==0; }

## get_allocator()

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

allocator_type tbb::interface5::concurrent_priority_queue< T, Compare, A >::get_allocator | ( |  | ) | const

inline

Return allocator object.

Definition at line 329 of file concurrent_priority_queue.h.

{ return data.get_allocator(); }

## handle_operations()

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

void tbb::interface5::concurrent_priority_queue< T, Compare, A >::handle_operations | ( | cpq_operation * | op_list | ) |

inline private

Definition at line 388 of file concurrent_priority_queue.h.

{
cpq_operation *tmp, *pop_list=NULL;
__TBB_ASSERT(mark == data.size(), NULL);
// First pass processes all constant (amortized; reallocation may happen) time pushes and pops.
while (op_list) {
// ITT note: &(op_list->status) tag is used to cover accesses to op_list
// node. This thread is going to handle the operation, and so will acquire it
// and perform the associated operation w/o triggering a race condition; the
// thread that created the operation is waiting on the status field, so when
// this thread is done with the operation, it will perform a
// store_with_release to give control back to the waiting thread in
// aggregator::insert_operation.
call_itt_notify(acquired, &(op_list->status));
__TBB_ASSERT(op_list->type != INVALID_OP, NULL);
tmp = op_list;
op_list = itt_hide_load_word(op_list->next);
if (tmp->type == POP_OP) {
if (mark < data.size() &&
compare(data[0], data[data.size()-1])) {
// there are newly pushed elems and the last one
// is higher than top
*(tmp->elem) = tbb::internal::move(data[data.size()-1]);
__TBB_store_with_release(my_size, my_size-1);
itt_store_word_with_release(tmp->status, uintptr_t(SUCCEEDED));
data.pop_back();
__TBB_ASSERT(mark<=data.size(), NULL);
}
else { // no convenient item to pop; postpone
itt_hide_store_word(tmp->next, pop_list);
pop_list = tmp;
}
} else { // PUSH_OP or PUSH_RVALUE_OP
__TBB_ASSERT(tmp->type == PUSH_OP || tmp->type == PUSH_RVALUE_OP, "Unknown operation" );
__TBB_TRY{
if (tmp->type == PUSH_OP) {
push_back_helper(*(tmp->elem), typename internal::use_element_copy_constructor<value_type>::type());
} else {
data.push_back(tbb::internal::move(*(tmp->elem)));
}
__TBB_store_with_release(my_size, my_size + 1);
itt_store_word_with_release(tmp->status, uintptr_t(SUCCEEDED));
} __TBB_CATCH(...) {
itt_store_word_with_release(tmp->status, uintptr_t(FAILED));
}
}
}
// second pass processes pop operations
while (pop_list) {
tmp = pop_list;
pop_list = itt_hide_load_word(pop_list->next);
__TBB_ASSERT(tmp->type == POP_OP, NULL);
if (data.empty()) {
itt_store_word_with_release(tmp->status, uintptr_t(FAILED));
}
else {
__TBB_ASSERT(mark<=data.size(), NULL);
if (mark < data.size() &&
compare(data[0], data[data.size()-1])) {
// there are newly pushed elems and the last one is
// higher than top
*(tmp->elem) = tbb::internal::move(data[data.size()-1]);
__TBB_store_with_release(my_size, my_size-1);
itt_store_word_with_release(tmp->status, uintptr_t(SUCCEEDED));
data.pop_back();
}
else { // extract top and push last element down heap
*(tmp->elem) = tbb::internal::move(data[0]);
__TBB_store_with_release(my_size, my_size-1);
itt_store_word_with_release(tmp->status, uintptr_t(SUCCEEDED));
reheap();
}
}
}
// heapify any leftover pushed elements before doing the next
// batch of operations
if (mark<data.size()) heapify();
__TBB_ASSERT(mark == data.size(), NULL);
}

Referenced by tbb::interface5::concurrent_priority_queue< T, Compare, A >::my_functor_t::operator()().

Here is the caller graph for this function:

## heapify()

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

void tbb::interface5::concurrent_priority_queue< T, Compare, A >::heapify | ( |  | ) |

inline private

Merge unsorted elements into heap.

Definition at line 472 of file concurrent_priority_queue.h.

{
if (!mark && data.size()>0) mark = 1;
for (; mark<data.size(); ++mark) {
// for each unheapified element under size
size_type cur_pos = mark;
value_type to_place = tbb::internal::move(data[mark]);
do { // push to_place up the heap
size_type parent = (cur_pos-1)>>1;
if (!compare(data[parent], to_place)) break;
data[cur_pos] = tbb::internal::move(data[parent]);
cur_pos = parent;
} while( cur_pos );
data[cur_pos] = tbb::internal::move(to_place);
}
}

## operator=() [1/3]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

concurrent_priority_queue& tbb::interface5::concurrent_priority_queue< T, Compare, A >::operator= | ( | concurrent_priority_queue< T, Compare, A > && | src | ) |

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 219 of file concurrent_priority_queue.h.

{
if (this != &src) {
mark = src.mark;
my_size = src.my_size;
#if !__TBB_ALLOCATOR_TRAITS_PRESENT
if (data.get_allocator() != src.data.get_allocator()){
vector_t(std::make_move_iterator(src.data.begin()), std::make_move_iterator(src.data.end()), data.get_allocator()).swap(data);
}else
#endif
{
data = std::move(src.data);
}
}
return *this;
}

## operator=() [2/3]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

concurrent_priority_queue& tbb::interface5::concurrent_priority_queue< T, Compare, A >::operator= | ( | const concurrent_priority_queue< T, Compare, A > & | src | ) |

inline

Assignment operator.

This operation is unsafe if there are pending concurrent operations on the src queue.

Definition at line 176 of file concurrent_priority_queue.h.

{
if (this != &src) {
vector_t(src.data.begin(), src.data.end(), src.data.get_allocator()).swap(data);
mark = src.mark;
my_size = src.my_size;
}
return *this;
}

## operator=() [3/3]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

concurrent_priority_queue& tbb::interface5::concurrent_priority_queue< T, Compare, A >::operator= | ( | std::initializer_list< T > | il | ) |

inline

Assign from std::initializer_list, not thread-safe.

Definition at line 250 of file concurrent_priority_queue.h.

{
this->assign(il.begin(), il.end());
return *this;
}

## push() [1/2]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

void tbb::interface5::concurrent_priority_queue< T, Compare, A >::push | ( | const_reference | elem | ) |

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 268 of file concurrent_priority_queue.h.

{
#if __TBB_CPP11_IS_COPY_CONSTRUCTIBLE_PRESENT
__TBB_STATIC_ASSERT( std::is_copy_constructible<value_type>::value, "The type is not copy constructible. Copying push operation is impossible." );
#endif
cpq_operation op_data(elem, PUSH_OP);
my_aggregator.execute(&op_data);
if (op_data.status == FAILED) // exception thrown
throw_exception(eid_bad_alloc);
}

Referenced by tbb::flow::interface11::internal::prioritize_task().

Here is the caller graph for this function:

## push() [2/2]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

void tbb::interface5::concurrent_priority_queue< T, Compare, A >::push | ( | value_type && | elem | ) |

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 281 of file concurrent_priority_queue.h.

{
cpq_operation op_data(elem, PUSH_RVALUE_OP);
my_aggregator.execute(&op_data);
if (op_data.status == FAILED) // exception thrown
throw_exception(eid_bad_alloc);
}

## push_back_helper() [1/2]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

void tbb::interface5::concurrent_priority_queue< T, Compare, A >::push_back_helper | ( | const T & | ,
|  | tbb::internal::false_type |
| ) |  |

inline private

Definition at line 513 of file concurrent_priority_queue.h.

{
__TBB_ASSERT( false, "The type is not copy constructible. Copying push operation is impossible." );
}

## push_back_helper() [2/2]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

void tbb::interface5::concurrent_priority_queue< T, Compare, A >::push_back_helper | ( | const T & | t,
|  | tbb::internal::true_type |
| ) |  |

inline private

Definition at line 509 of file concurrent_priority_queue.h.

{
data.push_back(t);
}

## reheap()

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

void tbb::interface5::concurrent_priority_queue< T, Compare, A >::reheap | ( |  | ) |

inline private

Re-heapify after an extraction.

Re-heapify by pushing last element down the heap from the root.

Definition at line 490 of file concurrent_priority_queue.h.

{
size_type cur_pos=0, child=1;
while (child < mark) {
size_type target = child;
if (child+1 < mark && compare(data[child], data[child+1]))
++target;
// target now has the higher priority child
if (compare(data[target], data[data.size()-1])) break;
data[cur_pos] = tbb::internal::move(data[target]);
cur_pos = target;
child = (cur_pos<<1)+1;
}
if (cur_pos != data.size()-1)
data[cur_pos] = tbb::internal::move(data[data.size()-1]);
data.pop_back();
if (mark > data.size()) mark = data.size();
}

## size()

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

size_type tbb::interface5::concurrent_priority_queue< T, Compare, A >::size | ( |  | ) | const

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 264 of file concurrent_priority_queue.h.

{ return __TBB_load_with_acquire(my_size); }

## swap()

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

void tbb::interface5::concurrent_priority_queue< T, Compare, A >::swap | ( | concurrent_priority_queue< T, Compare, A > & | q | ) |

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 321 of file concurrent_priority_queue.h.

{
using std::swap;
data.swap(q.data);
swap(mark, q.mark);
swap(my_size, q.my_size);
}

## try_pop()

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

bool tbb::interface5::concurrent_priority_queue< T, Compare, A >::try_pop | ( | reference | elem | ) |

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 302 of file concurrent_priority_queue.h.

{
cpq_operation op_data(POP_OP);
op_data.elem = &elem;
my_aggregator.execute(&op_data);
return op_data.status==SUCCEEDED;
}

Referenced by tbb::flow::interface11::internal::priority_task_selector::execute().

Here is the caller graph for this function:

## Member Data Documentation

## compare

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

Compare tbb::interface5::concurrent_priority_queue< T, Compare, A >::compare

private

Definition at line 364 of file concurrent_priority_queue.h.

## const_reference

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

const typedef T& tbb::interface5::concurrent_priority_queue< T, Compare, A >::const_reference

Const reference type.

Definition at line 77 of file concurrent_priority_queue.h.

## data

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

vector_t tbb::interface5::concurrent_priority_queue< T, Compare, A >::data

private

Definition at line 386 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().

## mark

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

size_type tbb::interface5::concurrent_priority_queue< T, Compare, A >::mark

private

The point at which unsorted elements begin.

Definition at line 362 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().

## my_aggregator

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

aggregator_t tbb::interface5::concurrent_priority_queue< T, Compare, A >::my_aggregator

private

Definition at line 358 of file concurrent_priority_queue.h.

## my_size

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

__TBB_atomic size_type tbb::interface5::concurrent_priority_queue< T, Compare, A >::my_size

private

Definition at line 363 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().

## padding1

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

char tbb::interface5::concurrent_priority_queue< T, Compare, A >::padding1[NFS_MaxLineSize - sizeof(aggregator_t)]

private

Padding added to avoid false sharing.

Definition at line 360 of file concurrent_priority_queue.h.

## padding2

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

char tbb::interface5::concurrent_priority_queue< T, Compare, A >::padding2[NFS_MaxLineSize -(2 *sizeof(size_type)) - sizeof(Compare)]

private

Padding added to avoid false sharing.

Definition at line 366 of file concurrent_priority_queue.h.

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

- concurrent_priority_queue.h

tbb::internal::__TBB_load_with_acquire
T __TBB_load_with_acquire(const volatile T &location)
Definition: tbb_machine.h:712
tbb::interface5::concurrent_priority_queue::compare
Compare compare
Definition: concurrent_priority_queue.h:364
tbb::interface5::concurrent_priority_queue::WAIT
Definition: concurrent_priority_queue.h:333
end
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp end
Definition: ittnotify_static.h:182
__TBB_ASSERT
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
tbb::internal::itt_store_word_with_release
void itt_store_word_with_release(tbb::atomic< T > &dst, U src)
Definition: tbb_profiling.h:157
tbb::internal::throw_exception
void throw_exception(exception_id eid)
Versionless convenience wrapper for throw_exception_v4()
Definition: tbb_exception.h:105
tbb::interface5::concurrent_priority_queue::assign
void assign(InputIterator begin, InputIterator end)
Assign the queue from [begin,end) range, not thread-safe.
Definition: concurrent_priority_queue.h:238
tbb::internal::swap
void swap(atomic< T > &lhs, atomic< T > &rhs)
Definition: atomic.h:564
tbb::interface6::internal::aggregator::execute
void execute(operation_type *op)
Definition: _aggregator_impl.h:152
tbb::interface5::concurrent_priority_queue::PUSH_OP
Definition: concurrent_priority_queue.h:332
begin
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp begin
Definition: ittnotify_static.h:182
tbb::interface5::concurrent_priority_queue::reheap
void reheap()
Re-heapify after an extraction.
Definition: concurrent_priority_queue.h:490
tbb::interface5::internal::use_element_copy_constructor::type
tbb::internal::true_type type
Definition: concurrent_priority_queue.h:59
tbb::interface5::concurrent_priority_queue::size_type
size_t size_type
Integral type for representing size of the queue.
Definition: concurrent_priority_queue.h:80
tbb::interface5::concurrent_priority_queue::swap
void swap(concurrent_priority_queue &q)
Swap this queue with another; not thread-safe.
Definition: concurrent_priority_queue.h:321
tbb::interface5::concurrent_priority_queue::PUSH_RVALUE_OP
Definition: concurrent_priority_queue.h:332
tbb::interface5::concurrent_priority_queue::my_size
__TBB_atomic size_type my_size
Definition: concurrent_priority_queue.h:363
tbb::internal::acquired
Definition: tbb_profiling.h:129
tbb::interface5::concurrent_priority_queue::vector_t
std::vector< value_type, allocator_type > vector_t
Storage for the heap of elements in queue, plus unheapified elements.
Definition: concurrent_priority_queue.h:385
tbb::interface6::internal::aggregator::initialize_handler
void initialize_handler(handler_type h)
Definition: _aggregator_impl.h:150
tbb::interface5::concurrent_priority_queue::heapify
void heapify()
Merge unsorted elements into heap.
Definition: concurrent_priority_queue.h:472
__TBB_STATIC_ASSERT
#define __TBB_STATIC_ASSERT(condition, msg)
Definition: tbb_stddef.h:553
tbb::interface5::concurrent_priority_queue::value_type
T value_type
Element type in the queue.
Definition: concurrent_priority_queue.h:71
tbb::move
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:319
tbb::internal::__TBB_store_with_release
void __TBB_store_with_release(volatile T &location, V value)
Definition: tbb_machine.h:716
tbb::interface5::concurrent_priority_queue::push_back_helper
void push_back_helper(const T &t, tbb::internal::true_type)
Definition: concurrent_priority_queue.h:509
parent
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id parent
Definition: ittnotify_static.h:176
tbb::interface5::concurrent_priority_queue::SUCCEEDED
Definition: concurrent_priority_queue.h:333
__TBB_TRY
#define __TBB_TRY
Definition: tbb_stddef.h:283
tbb::interface5::concurrent_priority_queue::POP_OP
Definition: concurrent_priority_queue.h:332
tbb::internal::itt_hide_store_word
void itt_hide_store_word(T &dst, T src)
Definition: tbb_profiling.h:210
tbb::interface5::concurrent_priority_queue::data
vector_t data
Definition: concurrent_priority_queue.h:386
tbb::internal::eid_bad_alloc
Definition: tbb_exception.h:68
tbb::interface5::concurrent_priority_queue::mark
size_type mark
The point at which unsorted elements begin.
Definition: concurrent_priority_queue.h:362
value
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long value
Definition: ittnotify_static.h:192
tbb::interface5::concurrent_priority_queue::my_aggregator
aggregator_t my_aggregator
Definition: concurrent_priority_queue.h:358
tbb::interface5::concurrent_priority_queue::size
size_type size() const
Returns the current number of elements contained in the queue.
Definition: concurrent_priority_queue.h:264
__TBB_CATCH
#define __TBB_CATCH(e)
Definition: tbb_stddef.h:284
tbb::internal::itt_hide_load_word
T itt_hide_load_word(const T &src)
Definition: tbb_profiling.h:222
tbb::internal::call_itt_notify
void call_itt_notify(notify_type, void *)
Definition: tbb_profiling.h:276
tbb::interface5::concurrent_priority_queue::FAILED
Definition: concurrent_priority_queue.h:333
tbb::interface5::concurrent_priority_queue::push
void push(const_reference elem)
Pushes elem onto the queue, increasing capacity of queue if necessary.
Definition: concurrent_priority_queue.h:268
tbb::interface5::concurrent_priority_queue::INVALID_OP
Definition: concurrent_priority_queue.h:332

Copyright © 2005-2020 Intel Corporation. All Rights Reserved.

Intel, Pentium, Intel Xeon, Itanium, Intel XScale and VTune are registered trademarks or trademarks of Intel Corporation or its subsidiaries in the United States and other countries.

* Other names and brands may be claimed as the property of others.