Intel(R) Threading Building Blocks Doxygen Documentation version 4.2.3
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 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_queueoperator= (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_queueoperator= (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_queueoperator= (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_operationaggregator_t
 
typedef std::vector< value_type, allocator_typevector_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.

◆ const_reference

template<typename T , typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>
typedef const T& tbb::interface5::concurrent_priority_queue< T, Compare, A >::const_reference

Const reference type.

Definition at line 77 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

◆ 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

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())
inlineexplicit

◆ 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() 
)
inlineexplicit

Constructs a new concurrent_priority_queue with default capacity.

Definition at line 95 of file concurrent_priority_queue.h.

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

References tbb::interface6::internal::aggregator< handler_type, operation_type >::initialize_handler(), and tbb::interface5::concurrent_priority_queue< T, Compare, A >::my_aggregator.

Here is the call graph for this function:

◆ 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() 
)
inlineexplicit

Constructs a new concurrent_priority_queue with init_sz capacity.

Definition at line 101 of file concurrent_priority_queue.h.

101 :
102 mark(0), my_size(0), compare(), data(a)
103 {
104 data.reserve(init_capacity);
105 my_aggregator.initialize_handler(my_functor_t(this));
106 }

References tbb::interface5::concurrent_priority_queue< T, Compare, A >::data, tbb::interface6::internal::aggregator< handler_type, operation_type >::initialize_handler(), and tbb::interface5::concurrent_priority_queue< T, Compare, A >::my_aggregator.

Here is the call graph for this function:

◆ 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() 
)
inlineexplicit

Constructs a new concurrent_priority_queue with init_sz capacity.

Definition at line 109 of file concurrent_priority_queue.h.

109 :
110 mark(0), my_size(0), compare(c), data(a)
111 {
112 data.reserve(init_capacity);
113 my_aggregator.initialize_handler(my_functor_t(this));
114 }

References tbb::interface5::concurrent_priority_queue< T, Compare, A >::data, tbb::interface6::internal::aggregator< handler_type, operation_type >::initialize_handler(), and tbb::interface5::concurrent_priority_queue< T, Compare, A >::my_aggregator.

Here is the call graph for this function:

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

118 :
119 mark(0), compare(), data(begin, end, a)
120 {
121 my_aggregator.initialize_handler(my_functor_t(this));
122 heapify();
123 my_size = data.size();
124 }
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
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
void heapify()
Merge unsorted elements into heap.

References tbb::interface5::concurrent_priority_queue< T, Compare, A >::data, tbb::interface5::concurrent_priority_queue< T, Compare, A >::heapify(), tbb::interface6::internal::aggregator< handler_type, operation_type >::initialize_handler(), tbb::interface5::concurrent_priority_queue< T, Compare, A >::my_aggregator, and tbb::interface5::concurrent_priority_queue< T, Compare, A >::my_size.

Here is the call graph for this function:

◆ 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

◆ 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

◆ 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

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

158 : mark(src.mark),
159 my_size(src.my_size), data(src.data.begin(), src.data.end(), src.data.get_allocator())
160 {
161 my_aggregator.initialize_handler(my_functor_t(this));
162 heapify();
163 }

References tbb::interface5::concurrent_priority_queue< T, Compare, A >::heapify(), tbb::interface6::internal::aggregator< handler_type, operation_type >::initialize_handler(), and tbb::interface5::concurrent_priority_queue< T, Compare, A >::my_aggregator.

Here is the call graph for this function:

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

167 : mark(src.mark),
168 my_size(src.my_size), data(src.data.begin(), src.data.end(), a)
169 {
170 my_aggregator.initialize_handler(my_functor_t(this));
171 heapify();
172 }

References tbb::interface5::concurrent_priority_queue< T, Compare, A >::heapify(), tbb::interface6::internal::aggregator< handler_type, operation_type >::initialize_handler(), and tbb::interface5::concurrent_priority_queue< T, Compare, A >::my_aggregator.

Here is the call graph for this function:

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

188 : mark(src.mark),
189 my_size(src.my_size), data(std::move(src.data))
190 {
191 my_aggregator.initialize_handler(my_functor_t(this));
192 }
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:319

References tbb::interface6::internal::aggregator< handler_type, operation_type >::initialize_handler(), and tbb::interface5::concurrent_priority_queue< T, Compare, A >::my_aggregator.

Here is the call graph for this function:

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

196 : mark(src.mark),
197 my_size(src.my_size),
198#if __TBB_ALLOCATOR_TRAITS_PRESENT
199 data(std::move(src.data), a)
200#else
201 // Some early version of C++11 STL vector does not have a constructor of vector(vector&& , allocator).
202 // It seems that the reason is absence of support of allocator_traits (stateful allocators).
203 data(a)
204#endif //__TBB_ALLOCATOR_TRAITS_PRESENT
205 {
206 my_aggregator.initialize_handler(my_functor_t(this));
207#if !__TBB_ALLOCATOR_TRAITS_PRESENT
208 if (a != src.data.get_allocator()){
209 data.reserve(src.data.size());
210 data.assign(std::make_move_iterator(src.data.begin()), std::make_move_iterator(src.data.end()));
211 }else{
212 data = std::move(src.data);
213 }
214#endif
215 }

References tbb::interface5::concurrent_priority_queue< T, Compare, A >::data, tbb::interface6::internal::aggregator< handler_type, operation_type >::initialize_handler(), tbb::move(), and tbb::interface5::concurrent_priority_queue< T, Compare, A >::my_aggregator.

Here is the call graph for this function:

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.

238 {
239 vector_t(begin, end, data.get_allocator()).swap(data);
240 mark = 0;
241 my_size = data.size();
242 heapify();
243 }
std::vector< value_type, allocator_type > vector_t
Storage for the heap of elements in queue, plus unheapified elements.

References begin, tbb::interface5::concurrent_priority_queue< T, Compare, A >::data, end, tbb::interface5::concurrent_priority_queue< T, Compare, A >::heapify(), tbb::interface5::concurrent_priority_queue< T, Compare, A >::mark, and tbb::interface5::concurrent_priority_queue< T, Compare, A >::my_size.

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

Here is the call graph for this function:
Here is the caller graph for this function:

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

247{ this->assign(il.begin(), il.end()); }
void assign(InputIterator begin, InputIterator end)
Assign the queue from [begin,end) range, not thread-safe.

References tbb::interface5::concurrent_priority_queue< T, Compare, A >::assign().

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

Here is the call graph for this function:
Here is the caller graph for this function:

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

313 {
314 data.clear();
315 mark = 0;
316 my_size = 0;
317 }

References tbb::interface5::concurrent_priority_queue< T, Compare, A >::data, tbb::interface5::concurrent_priority_queue< T, Compare, A >::mark, and tbb::interface5::concurrent_priority_queue< T, Compare, A >::my_size.

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

292 {
293 push(value_type(std::forward<Args>(args)...));
294 }
void push(const_reference elem)
Pushes elem onto the queue, increasing capacity of queue if necessary.

References tbb::interface5::concurrent_priority_queue< T, Compare, A >::push().

Here is the call graph for this function:

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

259{ return size()==0; }
size_type size() const
Returns the current number of elements contained in the queue.

References tbb::interface5::concurrent_priority_queue< T, Compare, A >::size().

Here is the call graph for this function:

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

329{ return data.get_allocator(); }

References tbb::interface5::concurrent_priority_queue< T, Compare, A >::data.

◆ 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)
inlineprivate

Definition at line 388 of file concurrent_priority_queue.h.

388 {
389 cpq_operation *tmp, *pop_list=NULL;
390
391 __TBB_ASSERT(mark == data.size(), NULL);
392
393 // First pass processes all constant (amortized; reallocation may happen) time pushes and pops.
394 while (op_list) {
395 // ITT note: &(op_list->status) tag is used to cover accesses to op_list
396 // node. This thread is going to handle the operation, and so will acquire it
397 // and perform the associated operation w/o triggering a race condition; the
398 // thread that created the operation is waiting on the status field, so when
399 // this thread is done with the operation, it will perform a
400 // store_with_release to give control back to the waiting thread in
401 // aggregator::insert_operation.
402 call_itt_notify(acquired, &(op_list->status));
403 __TBB_ASSERT(op_list->type != INVALID_OP, NULL);
404 tmp = op_list;
405 op_list = itt_hide_load_word(op_list->next);
406 if (tmp->type == POP_OP) {
407 if (mark < data.size() &&
408 compare(data[0], data[data.size()-1])) {
409 // there are newly pushed elems and the last one
410 // is higher than top
411 *(tmp->elem) = tbb::internal::move(data[data.size()-1]);
413 itt_store_word_with_release(tmp->status, uintptr_t(SUCCEEDED));
414 data.pop_back();
415 __TBB_ASSERT(mark<=data.size(), NULL);
416 }
417 else { // no convenient item to pop; postpone
418 itt_hide_store_word(tmp->next, pop_list);
419 pop_list = tmp;
420 }
421 } else { // PUSH_OP or PUSH_RVALUE_OP
422 __TBB_ASSERT(tmp->type == PUSH_OP || tmp->type == PUSH_RVALUE_OP, "Unknown operation" );
423 __TBB_TRY{
424 if (tmp->type == PUSH_OP) {
426 } else {
427 data.push_back(tbb::internal::move(*(tmp->elem)));
428 }
430 itt_store_word_with_release(tmp->status, uintptr_t(SUCCEEDED));
431 } __TBB_CATCH(...) {
432 itt_store_word_with_release(tmp->status, uintptr_t(FAILED));
433 }
434 }
435 }
436
437 // second pass processes pop operations
438 while (pop_list) {
439 tmp = pop_list;
440 pop_list = itt_hide_load_word(pop_list->next);
441 __TBB_ASSERT(tmp->type == POP_OP, NULL);
442 if (data.empty()) {
443 itt_store_word_with_release(tmp->status, uintptr_t(FAILED));
444 }
445 else {
446 __TBB_ASSERT(mark<=data.size(), NULL);
447 if (mark < data.size() &&
448 compare(data[0], data[data.size()-1])) {
449 // there are newly pushed elems and the last one is
450 // higher than top
451 *(tmp->elem) = tbb::internal::move(data[data.size()-1]);
453 itt_store_word_with_release(tmp->status, uintptr_t(SUCCEEDED));
454 data.pop_back();
455 }
456 else { // extract top and push last element down heap
457 *(tmp->elem) = tbb::internal::move(data[0]);
459 itt_store_word_with_release(tmp->status, uintptr_t(SUCCEEDED));
460 reheap();
461 }
462 }
463 }
464
465 // heapify any leftover pushed elements before doing the next
466 // batch of operations
467 if (mark<data.size()) heapify();
468 __TBB_ASSERT(mark == data.size(), NULL);
469 }
#define __TBB_CATCH(e)
Definition: tbb_stddef.h:284
#define __TBB_TRY
Definition: tbb_stddef.h:283
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
void itt_hide_store_word(T &dst, T src)
void itt_store_word_with_release(tbb::atomic< T > &dst, U src)
T itt_hide_load_word(const T &src)
void call_itt_notify(notify_type, void *)
void __TBB_store_with_release(volatile T &location, V value)
Definition: tbb_machine.h:713
void reheap()
Re-heapify after an extraction.
void push_back_helper(const T &t, tbb::internal::true_type)

References __TBB_ASSERT, __TBB_CATCH, tbb::internal::__TBB_store_with_release(), __TBB_TRY, tbb::internal::acquired, tbb::internal::call_itt_notify(), tbb::interface5::concurrent_priority_queue< T, Compare, A >::compare, tbb::interface5::concurrent_priority_queue< T, Compare, A >::data, tbb::interface5::concurrent_priority_queue< T, Compare, A >::cpq_operation::elem, tbb::interface5::concurrent_priority_queue< T, Compare, A >::FAILED, tbb::interface5::concurrent_priority_queue< T, Compare, A >::heapify(), tbb::interface5::concurrent_priority_queue< T, Compare, A >::INVALID_OP, tbb::internal::itt_hide_load_word(), tbb::internal::itt_hide_store_word(), tbb::internal::itt_store_word_with_release(), tbb::interface5::concurrent_priority_queue< T, Compare, A >::mark, tbb::move(), tbb::interface5::concurrent_priority_queue< T, Compare, A >::my_size, tbb::interface6::internal::aggregated_operation< Derived >::next, tbb::interface5::concurrent_priority_queue< T, Compare, A >::POP_OP, tbb::interface5::concurrent_priority_queue< T, Compare, A >::push_back_helper(), tbb::interface5::concurrent_priority_queue< T, Compare, A >::PUSH_OP, tbb::interface5::concurrent_priority_queue< T, Compare, A >::PUSH_RVALUE_OP, tbb::interface5::concurrent_priority_queue< T, Compare, A >::reheap(), tbb::interface6::internal::aggregated_operation< Derived >::status, tbb::interface5::concurrent_priority_queue< T, Compare, A >::SUCCEEDED, and tbb::interface5::concurrent_priority_queue< T, Compare, A >::cpq_operation::type.

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

Here is the call graph for this function:
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 ( )
inlineprivate

Merge unsorted elements into heap.

Definition at line 472 of file concurrent_priority_queue.h.

472 {
473 if (!mark && data.size()>0) mark = 1;
474 for (; mark<data.size(); ++mark) {
475 // for each unheapified element under size
476 size_type cur_pos = mark;
478 do { // push to_place up the heap
479 size_type parent = (cur_pos-1)>>1;
480 if (!compare(data[parent], to_place)) break;
481 data[cur_pos] = tbb::internal::move(data[parent]);
482 cur_pos = parent;
483 } while( cur_pos );
484 data[cur_pos] = tbb::internal::move(to_place);
485 }
486 }
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
size_t size_type
Integral type for representing size of the queue.

References tbb::interface5::concurrent_priority_queue< T, Compare, A >::compare, tbb::interface5::concurrent_priority_queue< T, Compare, A >::data, tbb::interface5::concurrent_priority_queue< T, Compare, A >::mark, tbb::move(), and parent.

Referenced by tbb::interface5::concurrent_priority_queue< T, Compare, A >::assign(), tbb::interface5::concurrent_priority_queue< T, Compare, A >::concurrent_priority_queue(), and tbb::interface5::concurrent_priority_queue< T, Compare, A >::handle_operations().

Here is the call graph for this function:
Here is the caller graph for this function:

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

219 {
220 if (this != &src) {
221 mark = src.mark;
222 my_size = src.my_size;
223#if !__TBB_ALLOCATOR_TRAITS_PRESENT
224 if (data.get_allocator() != src.data.get_allocator()){
225 vector_t(std::make_move_iterator(src.data.begin()), std::make_move_iterator(src.data.end()), data.get_allocator()).swap(data);
226 }else
227#endif
228 {
229 data = std::move(src.data);
230 }
231 }
232 return *this;
233 }

References tbb::interface5::concurrent_priority_queue< T, Compare, A >::data, tbb::interface5::concurrent_priority_queue< T, Compare, A >::mark, tbb::move(), and tbb::interface5::concurrent_priority_queue< T, Compare, A >::my_size.

Here is the call graph for this function:

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

176 {
177 if (this != &src) {
178 vector_t(src.data.begin(), src.data.end(), src.data.get_allocator()).swap(data);
179 mark = src.mark;
180 my_size = src.my_size;
181 }
182 return *this;
183 }

References tbb::interface5::concurrent_priority_queue< T, Compare, A >::data, tbb::interface5::concurrent_priority_queue< T, Compare, A >::mark, and tbb::interface5::concurrent_priority_queue< T, Compare, A >::my_size.

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

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

References tbb::interface5::concurrent_priority_queue< T, Compare, A >::assign().

Here is the call graph for this function:

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

268 {
269#if __TBB_CPP11_IS_COPY_CONSTRUCTIBLE_PRESENT
270 __TBB_STATIC_ASSERT( std::is_copy_constructible<value_type>::value, "The type is not copy constructible. Copying push operation is impossible." );
271#endif
272 cpq_operation op_data(elem, PUSH_OP);
273 my_aggregator.execute(&op_data);
274 if (op_data.status == FAILED) // exception thrown
276 }
#define __TBB_STATIC_ASSERT(condition, msg)
Definition: tbb_stddef.h:553
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
void throw_exception(exception_id eid)
Versionless convenience wrapper for throw_exception_v4()

References __TBB_STATIC_ASSERT, tbb::internal::eid_bad_alloc, tbb::interface6::internal::aggregator< handler_type, operation_type >::execute(), tbb::interface5::concurrent_priority_queue< T, Compare, A >::FAILED, tbb::interface5::concurrent_priority_queue< T, Compare, A >::my_aggregator, tbb::interface5::concurrent_priority_queue< T, Compare, A >::PUSH_OP, tbb::interface6::internal::aggregated_operation< Derived >::status, tbb::internal::throw_exception(), and value.

Referenced by tbb::interface5::concurrent_priority_queue< T, Compare, A >::emplace(), and tbb::flow::interface11::internal::prioritize_task().

Here is the call graph for this function:
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.

281 {
282 cpq_operation op_data(elem, PUSH_RVALUE_OP);
283 my_aggregator.execute(&op_data);
284 if (op_data.status == FAILED) // exception thrown
286 }

References tbb::internal::eid_bad_alloc, tbb::interface6::internal::aggregator< handler_type, operation_type >::execute(), tbb::interface5::concurrent_priority_queue< T, Compare, A >::FAILED, tbb::interface5::concurrent_priority_queue< T, Compare, A >::my_aggregator, tbb::interface5::concurrent_priority_queue< T, Compare, A >::PUSH_RVALUE_OP, tbb::interface6::internal::aggregated_operation< Derived >::status, and tbb::internal::throw_exception().

Here is the call graph for this function:

◆ 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   
)
inlineprivate

Definition at line 513 of file concurrent_priority_queue.h.

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

References __TBB_ASSERT.

◆ 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   
)
inlineprivate

Definition at line 509 of file concurrent_priority_queue.h.

509 {
510 data.push_back(t);
511 }

References tbb::interface5::concurrent_priority_queue< T, Compare, A >::data.

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

Here is the caller graph for this function:

◆ 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 ( )
inlineprivate

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.

490 {
491 size_type cur_pos=0, child=1;
492
493 while (child < mark) {
494 size_type target = child;
495 if (child+1 < mark && compare(data[child], data[child+1]))
496 ++target;
497 // target now has the higher priority child
498 if (compare(data[target], data[data.size()-1])) break;
499 data[cur_pos] = tbb::internal::move(data[target]);
500 cur_pos = target;
501 child = (cur_pos<<1)+1;
502 }
503 if (cur_pos != data.size()-1)
504 data[cur_pos] = tbb::internal::move(data[data.size()-1]);
505 data.pop_back();
506 if (mark > data.size()) mark = data.size();
507 }

References tbb::interface5::concurrent_priority_queue< T, Compare, A >::compare, tbb::interface5::concurrent_priority_queue< T, Compare, A >::data, tbb::interface5::concurrent_priority_queue< T, Compare, A >::mark, and tbb::move().

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

Here is the call graph for this function:
Here is the caller graph for this function:

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

T __TBB_load_with_acquire(const volatile T &location)
Definition: tbb_machine.h:709

References tbb::internal::__TBB_load_with_acquire(), and tbb::interface5::concurrent_priority_queue< T, Compare, A >::my_size.

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

Here is the call graph for this function:
Here is the caller graph for this function:

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

321 {
322 using std::swap;
323 data.swap(q.data);
324 swap(mark, q.mark);
325 swap(my_size, q.my_size);
326 }
void swap(atomic< T > &lhs, atomic< T > &rhs)
Definition: atomic.h:564
void swap(concurrent_priority_queue &q)
Swap this queue with another; not thread-safe.

References tbb::interface5::concurrent_priority_queue< T, Compare, A >::data, tbb::interface5::concurrent_priority_queue< T, Compare, A >::mark, tbb::interface5::concurrent_priority_queue< T, Compare, A >::my_size, tbb::internal::swap(), and tbb::interface5::concurrent_priority_queue< T, Compare, A >::swap().

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

Here is the call graph for this function:
Here is the caller graph for this function:

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

302 {
303 cpq_operation op_data(POP_OP);
304 op_data.elem = &elem;
305 my_aggregator.execute(&op_data);
306 return op_data.status==SUCCEEDED;
307 }

References tbb::interface5::concurrent_priority_queue< T, Compare, A >::cpq_operation::elem, tbb::interface6::internal::aggregator< handler_type, operation_type >::execute(), tbb::interface5::concurrent_priority_queue< T, Compare, A >::my_aggregator, tbb::interface5::concurrent_priority_queue< T, Compare, A >::POP_OP, tbb::interface6::internal::aggregated_operation< Derived >::status, and tbb::interface5::concurrent_priority_queue< T, Compare, A >::SUCCEEDED.

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

Here is the call graph for this function:
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

◆ data

◆ mark

◆ my_aggregator

◆ my_size

◆ 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:

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.