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 65 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 354 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 83 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 74 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 80 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 71 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 77 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 68 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 382 of file concurrent_priority_queue.h.

Member Enumeration Documentation

◆ operation_status

◆ operation_type

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

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

98  :
99  mark(0), my_size(0), compare(), data(a)
100  {
101  data.reserve(init_capacity);
102  my_aggregator.initialize_handler(my_functor_t(this));
103  }
size_type mark
The point at which unsorted elements begin.

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

106  :
107  mark(0), my_size(0), compare(c), data(a)
108  {
109  data.reserve(init_capacity);
110  my_aggregator.initialize_handler(my_functor_t(this));
111  }
size_type mark
The point at which unsorted elements begin.

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

115  :
116  mark(0), compare(), data(begin, end, a)
117  {
118  my_aggregator.initialize_handler(my_functor_t(this));
119  heapify();
120  my_size = data.size();
121  }
void heapify()
Merge unsorted elements into heap.
size_type mark
The point at which unsorted elements 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 __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

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

125  :
126  mark(0), compare(c), data(begin, end, a)
127  {
128  my_aggregator.initialize_handler(my_functor_t(this));
129  heapify();
130  my_size = data.size();
131  }
void heapify()
Merge unsorted elements into heap.
size_type mark
The point at which unsorted elements 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 __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

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

135  :
136  mark(0), compare(), data(init_list.begin(), init_list.end(), a)
137  {
138  my_aggregator.initialize_handler(my_functor_t(this));
139  heapify();
140  my_size = data.size();
141  }
void heapify()
Merge unsorted elements into heap.
size_type mark
The point at which unsorted elements begin.

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

144  :
145  mark(0), compare(c), data(init_list.begin(), init_list.end(), a)
146  {
147  my_aggregator.initialize_handler(my_functor_t(this));
148  heapify();
149  my_size = data.size();
150  }
void heapify()
Merge unsorted elements into heap.
size_type mark
The point at which unsorted elements begin.

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

155  : mark(src.mark),
156  my_size(src.my_size), data(src.data.begin(), src.data.end(), src.data.get_allocator())
157  {
158  my_aggregator.initialize_handler(my_functor_t(this));
159  heapify();
160  }
void heapify()
Merge unsorted elements into heap.
size_type mark
The point at which unsorted elements begin.

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

164  : mark(src.mark),
165  my_size(src.my_size), data(src.data.begin(), src.data.end(), a)
166  {
167  my_aggregator.initialize_handler(my_functor_t(this));
168  heapify();
169  }
void heapify()
Merge unsorted elements into heap.
size_type mark
The point at which unsorted elements begin.

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

185  : mark(src.mark),
186  my_size(src.my_size), data(std::move(src.data))
187  {
188  my_aggregator.initialize_handler(my_functor_t(this));
189  }
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:305
size_type mark
The point at which unsorted elements begin.

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

193  : mark(src.mark),
194  my_size(src.my_size),
195 #if __TBB_ALLOCATOR_TRAITS_PRESENT
196  data(std::move(src.data), a)
197 #else
198  // Some early version of C++11 STL vector does not have a constructor of vector(vector&& , allocator).
199  // It seems that the reason is absence of support of allocator_traits (stateful allocators).
200  data(a)
201 #endif //__TBB_ALLOCATOR_TRAITS_PRESENT
202  {
203  my_aggregator.initialize_handler(my_functor_t(this));
204 #if !__TBB_ALLOCATOR_TRAITS_PRESENT
205  if (a != src.data.get_allocator()){
206  data.reserve(src.data.size());
207  data.assign(std::make_move_iterator(src.data.begin()), std::make_move_iterator(src.data.end()));
208  }else{
209  data = std::move(src.data);
210  }
211 #endif
212  }
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:305
size_type mark
The point at which unsorted elements begin.

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

235  {
236  vector_t(begin, end, data.get_allocator()).swap(data);
237  mark = 0;
238  my_size = data.size();
239  heapify();
240  }
void heapify()
Merge unsorted elements into heap.
size_type mark
The point at which unsorted elements 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 __itt_timestamp end
void swap(concurrent_priority_queue &q)
Swap this queue with another; not thread-safe.
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
std::vector< value_type, allocator_type > vector_t
Storage for the heap of elements in queue, plus unheapified elements.

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

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

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

310  {
311  data.clear();
312  mark = 0;
313  my_size = 0;
314  }
size_type mark
The point at which unsorted elements begin.

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

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

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

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

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

326 { 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)
inlineprivate

Definition at line 385 of file concurrent_priority_queue.h.

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

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

Merge unsorted elements into heap.

Definition at line 469 of file concurrent_priority_queue.h.

469  {
470  if (!mark && data.size()>0) mark = 1;
471  for (; mark<data.size(); ++mark) {
472  // for each unheapified element under size
473  size_type cur_pos = mark;
475  do { // push to_place up the heap
476  size_type parent = (cur_pos-1)>>1;
477  if (!compare(data[parent], to_place)) break;
478  data[cur_pos] = tbb::internal::move(data[parent]);
479  cur_pos = parent;
480  } while( cur_pos );
481  data[cur_pos] = tbb::internal::move(to_place);
482  }
483  }
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
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:305
size_t size_type
Integral type for representing size of the queue.
size_type mark
The point at which unsorted elements begin.

◆ 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= ( 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 173 of file concurrent_priority_queue.h.

173  {
174  if (this != &src) {
175  vector_t(src.data.begin(), src.data.end(), src.data.get_allocator()).swap(data);
176  mark = src.mark;
177  my_size = src.my_size;
178  }
179  return *this;
180  }
size_type mark
The point at which unsorted elements begin.
void swap(concurrent_priority_queue &q)
Swap this queue with another; not thread-safe.
std::vector< value_type, allocator_type > vector_t
Storage for the heap of elements in queue, plus unheapified elements.

◆ 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= ( 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 216 of file concurrent_priority_queue.h.

216  {
217  if (this != &src) {
218  mark = src.mark;
219  my_size = src.my_size;
220 #if !__TBB_ALLOCATOR_TRAITS_PRESENT
221  if (data.get_allocator() != src.data.get_allocator()){
222  vector_t(std::make_move_iterator(src.data.begin()), std::make_move_iterator(src.data.end()), data.get_allocator()).swap(data);
223  }else
224 #endif
225  {
226  data = std::move(src.data);
227  }
228  }
229  return *this;
230  }
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:305
size_type mark
The point at which unsorted elements begin.
void swap(concurrent_priority_queue &q)
Swap this queue with another; not thread-safe.
std::vector< value_type, allocator_type > vector_t
Storage for the heap of elements in queue, plus unheapified elements.

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

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

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

265  {
266 #if __TBB_CPP11_IS_COPY_CONSTRUCTIBLE_PRESENT
267  __TBB_STATIC_ASSERT( std::is_copy_constructible<value_type>::value, "The type is not copy constructible. Copying push operation is impossible." );
268 #endif
269  cpq_operation op_data(elem, PUSH_OP);
270  my_aggregator.execute(&op_data);
271  if (op_data.status == FAILED) // exception thrown
273  }
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()
#define __TBB_STATIC_ASSERT(condition, msg)
Definition: tbb_stddef.h:532

Referenced by tbb::flow::interface10::internal::spawn_in_graph_arena().

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

278  {
279  cpq_operation op_data(elem, PUSH_RVALUE_OP);
280  my_aggregator.execute(&op_data);
281  if (op_data.status == FAILED) // exception thrown
283  }
void throw_exception(exception_id eid)
Versionless convenience wrapper for throw_exception_v4()

◆ 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 &  t,
tbb::internal::true_type   
)
inlineprivate

Definition at line 506 of file concurrent_priority_queue.h.

506  {
507  data.push_back(t);
508  }

◆ 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 &  ,
tbb::internal::false_type   
)
inlineprivate

Definition at line 510 of file concurrent_priority_queue.h.

510  {
511  __TBB_ASSERT( false, "The type is not copy constructible. Copying push operation is impossible." );
512  }
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165

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

487  {
488  size_type cur_pos=0, child=1;
489 
490  while (child < mark) {
491  size_type target = child;
492  if (child+1 < mark && compare(data[child], data[child+1]))
493  ++target;
494  // target now has the higher priority child
495  if (compare(data[target], data[data.size()-1])) break;
496  data[cur_pos] = tbb::internal::move(data[target]);
497  cur_pos = target;
498  child = (cur_pos<<1)+1;
499  }
500  if (cur_pos != data.size()-1)
501  data[cur_pos] = tbb::internal::move(data[data.size()-1]);
502  data.pop_back();
503  if (mark > data.size()) mark = data.size();
504  }
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:305
size_t size_type
Integral type for representing size of the queue.
size_type mark
The point at which unsorted elements begin.

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

261 { return __TBB_load_with_acquire(my_size); }
T __TBB_load_with_acquire(const volatile T &location)
Definition: tbb_machine.h:709

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

318  {
319  using std::swap;
320  data.swap(q.data);
321  swap(mark, q.mark);
322  swap(my_size, q.my_size);
323  }
size_type mark
The point at which unsorted elements begin.
void swap(concurrent_priority_queue &q)
Swap this queue with another; not thread-safe.
void swap(atomic< T > &lhs, atomic< T > &rhs)
Definition: atomic.h:535

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

Referenced by tbb::flow::interface10::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 361 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

◆ 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

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

◆ 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 357 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 363 of file concurrent_priority_queue.h.


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

Copyright © 2005-2019 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.