17 #ifndef __TBB_concurrent_priority_queue_H 18 #define __TBB_concurrent_priority_queue_H 31 #include __TBB_STD_SWAP_HEADER 33 #if __TBB_INITIALIZER_LISTS_PRESENT 34 #include <initializer_list> 37 #if __TBB_CPP11_IS_COPY_CONSTRUCTIBLE_PRESENT 38 #include <type_traits> 42 namespace interface5 {
44 #if __TBB_CPP11_IS_COPY_CONSTRUCTIBLE_PRESENT 46 struct use_element_copy_constructor {
50 struct use_element_copy_constructor <T,false> {
64 template <
typename T,
typename Compare=std::less<T>,
typename A=cache_aligned_allocator<T> >
88 my_aggregator.initialize_handler(my_functor_t(
this));
94 my_aggregator.initialize_handler(my_functor_t(
this));
99 mark(0), my_size(0), compare(),
data(a)
101 data.reserve(init_capacity);
102 my_aggregator.initialize_handler(my_functor_t(
this));
107 mark(0), my_size(0), compare(c),
data(a)
109 data.reserve(init_capacity);
110 my_aggregator.initialize_handler(my_functor_t(
this));
114 template<
typename InputIterator>
118 my_aggregator.initialize_handler(my_functor_t(
this));
120 my_size =
data.size();
124 template<
typename InputIterator>
128 my_aggregator.initialize_handler(my_functor_t(
this));
130 my_size =
data.size();
133 #if __TBB_INITIALIZER_LISTS_PRESENT 136 mark(0), compare(),
data(init_list.
begin(), init_list.
end(), a)
138 my_aggregator.initialize_handler(my_functor_t(
this));
140 my_size =
data.size();
145 mark(0), compare(c),
data(init_list.
begin(), init_list.
end(), a)
147 my_aggregator.initialize_handler(my_functor_t(
this));
149 my_size =
data.size();
151 #endif //# __TBB_INITIALIZER_LISTS_PRESENT 158 my_aggregator.initialize_handler(my_functor_t(
this));
167 my_aggregator.initialize_handler(my_functor_t(
this));
182 #if __TBB_CPP11_RVALUE_REF_PRESENT 188 my_aggregator.initialize_handler(my_functor_t(
this));
194 my_size(src.my_size),
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()));
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);
231 #endif //__TBB_CPP11_RVALUE_REF_PRESENT 234 template<
typename InputIterator>
238 my_size =
data.size();
242 #if __TBB_INITIALIZER_LISTS_PRESENT 243 void assign(std::initializer_list<T> il) { this->assign(il.begin(), il.end()); }
248 this->assign(il.begin(), il.end());
251 #endif //# __TBB_INITIALIZER_LISTS_PRESENT 266 #if __TBB_CPP11_IS_COPY_CONSTRUCTIBLE_PRESENT 269 cpq_operation op_data(elem, PUSH_OP);
270 my_aggregator.execute(&op_data);
271 if (op_data.status ==
FAILED)
275 #if __TBB_CPP11_RVALUE_REF_PRESENT 279 cpq_operation op_data(elem, PUSH_RVALUE_OP);
280 my_aggregator.execute(&op_data);
281 if (op_data.status ==
FAILED)
285 #if __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT 288 template<
typename... Args>
290 push(
value_type(std::forward<Args>(args)...));
300 cpq_operation op_data(POP_OP);
301 op_data.elem = &elem;
302 my_aggregator.execute(&op_data);
382 typedef std::vector<value_type, allocator_type>
vector_t;
386 cpq_operation *tmp, *pop_list=NULL;
403 if (tmp->type == POP_OP) {
404 if (mark <
data.size() &&
419 __TBB_ASSERT(tmp->type == PUSH_OP || tmp->type == PUSH_RVALUE_OP,
"Unknown operation" );
421 if (tmp->type == PUSH_OP) {
444 if (mark <
data.size() &&
464 if (mark<
data.size()) heapify();
470 if (!mark &&
data.size()>0) mark = 1;
471 for (; mark<
data.size(); ++mark) {
490 while (child < mark) {
492 if (child+1 < mark && compare(
data[child],
data[child+1]))
498 child = (cur_pos<<1)+1;
500 if (cur_pos !=
data.size()-1)
503 if (mark >
data.size()) mark =
data.size();
511 __TBB_ASSERT(
false,
"The type is not copy constructible. Copying push operation is impossible." );
515 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT 518 template<
typename T,
typename... Args>
521 std::conditional_t< (
sizeof...(Args)>0) && !is_allocator_v< pack_element_t<0, Args...> >,
522 pack_element_t<0, Args...>, std::less<T> >,
523 std::conditional_t< (
sizeof...(Args)>0) && is_allocator_v< pack_element_t<
sizeof...(Args)-1, Args...> >,
529 template<
typename InputIterator,
530 typename T =
typename std::iterator_traits<InputIterator>::value_type,
532 > concurrent_priority_queue(InputIterator, InputIterator, Args...)
533 -> internal::priority_queue_t<T, Args...>;
535 template<
typename T,
typename CompareOrAllocalor>
536 concurrent_priority_queue(std::initializer_list<T> init_list, CompareOrAllocalor)
537 -> internal::priority_queue_t<T, CompareOrAllocalor>;
542 using interface5::concurrent_priority_queue;
concurrent_priority_queue(InputIterator begin, InputIterator end, const Compare &c, const allocator_type &a=allocator_type())
[begin,end) constructor
bool try_pop(reference elem)
Gets a reference to and removes highest priority element.
Class for determining type of std::allocator<T>::value_type.
void itt_hide_store_word(T &dst, T src)
void assign(InputIterator begin, InputIterator end)
Assign the queue from [begin,end) range, not thread-safe.
size_type size() const
Returns the current number of elements contained in the queue.
ptrdiff_t difference_type
Difference type for iterator.
concurrent_priority_queue(const Compare &c, const allocator_type &a=allocator_type())
Constructs a new concurrent_priority_queue with default capacity.
tbb::internal::aggregator< my_functor_t, cpq_operation > aggregator_t
void clear()
Clear the queue; not thread-safe.
T value_type
Element type in the queue.
aggregated_operation base class
void push_back_helper(const T &t, tbb::internal::true_type)
T & reference
Reference type.
#define __TBB_STATIC_ASSERT(condition, msg)
Concurrent priority queue.
void emplace(Args &&... args)
Constructs a new element using args as the arguments for its construction and pushes it onto the queu...
std::vector< value_type, allocator_type > vector_t
Storage for the heap of elements in queue, plus unheapified elements.
concurrent_priority_queue< T, Compare, A > * cpq
concurrent_priority_queue(const concurrent_priority_queue &src, const allocator_type &a)
Copy constructor with specific allocator.
void reheap()
Re-heapify after an extraction.
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 handle_operations(cpq_operation *op_list)
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 ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle __itt_metadata_type size_t void * data
concurrent_priority_queue(std::initializer_list< T > init_list, const Compare &c, const allocator_type &a=allocator_type())
Constructor from std::initializer_list.
concurrent_priority_queue(const allocator_type &a=allocator_type())
Constructs a new concurrent_priority_queue with default capacity.
void itt_store_word_with_release(tbb::atomic< T > &dst, U src)
void swap(concurrent_priority_queue &q)
Swap this queue with another; not thread-safe.
T itt_hide_load_word(const T &src)
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_type mark
The point at which unsorted elements begin.
void heapify()
Merge unsorted elements into heap.
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
allocator_type get_allocator() const
Return allocator object.
void move(tbb_thread &t1, tbb_thread &t2)
cpq_operation(const_reference e, operation_type t)
size_t size_type
Integral type for representing size of the queue.
const T & const_reference
Const reference type.
void __TBB_store_with_release(volatile T &location, V value)
concurrent_priority_queue & operator=(const concurrent_priority_queue &src)
Assignment operator.
Meets "allocator" requirements of ISO C++ Standard, Section 20.1.5.
void operator()(cpq_operation *op_list)
tbb::internal::true_type type
A allocator_type
Allocator type.
void push(const_reference elem)
Pushes elem onto the queue, increasing capacity of queue if necessary.
T __TBB_load_with_acquire(const volatile T &location)
#define __TBB_ALLOCATOR_TRAITS_PRESENT
void call_itt_notify(notify_type, void *)
void push_back_helper(const T &, tbb::internal::false_type)
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.
Identifiers declared inside namespace internal should never be used directly by client code.
concurrent_priority_queue & operator=(std::initializer_list< T > il)
Assign from std::initializer_list, not thread-safe.
void push(value_type &&elem)
Pushes elem onto the queue, increasing capacity of queue if necessary.
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(concurrent_priority_queue &&src)
Move constructor.
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
aggregator_t my_aggregator
bool empty() const
Returns true if empty, false otherwise.
void swap(concurrent_hash_map< Key, T, HashCompare, A > &a, concurrent_hash_map< Key, T, HashCompare, A > &b)
concurrent_priority_queue(size_type init_capacity, const allocator_type &a=allocator_type())
Constructs a new concurrent_priority_queue with init_sz capacity.
void throw_exception(exception_id eid)
Versionless convenience wrapper for throw_exception_v4()
my_functor_t(concurrent_priority_queue< T, Compare, A > *cpq_)
const size_t NFS_MaxLineSize
Compile-time constant that is upper bound on cache line/sector size.
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 ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle __itt_metadata_type type
concurrent_priority_queue(InputIterator begin, InputIterator end, const allocator_type &a=allocator_type())
[begin,end) constructor
concurrent_priority_queue(concurrent_priority_queue &&src, const allocator_type &a)
Move constructor with specific allocator.
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 size
cpq_operation(operation_type t)
concurrent_priority_queue(const concurrent_priority_queue &src)
Copy constructor.
__TBB_atomic size_type my_size
concurrent_priority_queue & operator=(concurrent_priority_queue &&src)
Move assignment operator.
void swap(atomic< T > &lhs, atomic< T > &rhs)