17 #ifndef __TBB_concurrent_priority_queue_H 18 #define __TBB_concurrent_priority_queue_H 20 #define __TBB_concurrent_priority_queue_H_include_area 34 #include __TBB_STD_SWAP_HEADER 36 #if __TBB_INITIALIZER_LISTS_PRESENT 37 #include <initializer_list> 40 #if __TBB_CPP11_IS_COPY_CONSTRUCTIBLE_PRESENT 41 #include <type_traits> 45 namespace interface5 {
47 #if __TBB_CPP11_IS_COPY_CONSTRUCTIBLE_PRESENT 49 struct use_element_copy_constructor {
53 struct use_element_copy_constructor <T,false> {
67 template <
typename T,
typename Compare=std::less<T>,
typename A=cache_aligned_allocator<T> >
91 my_aggregator.initialize_handler(my_functor_t(
this));
97 my_aggregator.initialize_handler(my_functor_t(
this));
102 mark(0), my_size(0), compare(),
data(a)
104 data.reserve(init_capacity);
105 my_aggregator.initialize_handler(my_functor_t(
this));
110 mark(0), my_size(0), compare(c),
data(a)
112 data.reserve(init_capacity);
113 my_aggregator.initialize_handler(my_functor_t(
this));
117 template<
typename InputIterator>
119 mark(0), compare(),
data(begin, end, a)
121 my_aggregator.initialize_handler(my_functor_t(
this));
123 my_size =
data.size();
127 template<
typename InputIterator>
129 mark(0), compare(c),
data(begin, end, a)
131 my_aggregator.initialize_handler(my_functor_t(
this));
133 my_size =
data.size();
136 #if __TBB_INITIALIZER_LISTS_PRESENT 139 mark(0), compare(),
data(init_list.begin(), init_list.end(), a)
141 my_aggregator.initialize_handler(my_functor_t(
this));
143 my_size =
data.size();
148 mark(0), compare(c),
data(init_list.begin(), init_list.end(), a)
150 my_aggregator.initialize_handler(my_functor_t(
this));
152 my_size =
data.size();
154 #endif //# __TBB_INITIALIZER_LISTS_PRESENT 159 my_size(src.my_size),
data(src.
data.begin(), src.
data.end(), src.
data.get_allocator())
161 my_aggregator.initialize_handler(my_functor_t(
this));
168 my_size(src.my_size),
data(src.
data.begin(), src.
data.end(), a)
170 my_aggregator.initialize_handler(my_functor_t(
this));
185 #if __TBB_CPP11_RVALUE_REF_PRESENT 191 my_aggregator.initialize_handler(my_functor_t(
this));
197 my_size(src.my_size),
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()));
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);
234 #endif //__TBB_CPP11_RVALUE_REF_PRESENT 237 template<
typename InputIterator>
238 void assign(InputIterator begin, InputIterator end) {
241 my_size =
data.size();
245 #if __TBB_INITIALIZER_LISTS_PRESENT 246 void assign(std::initializer_list<T> il) { this->assign(il.begin(), il.end()); }
251 this->assign(il.begin(), il.end());
254 #endif //# __TBB_INITIALIZER_LISTS_PRESENT 268 void push(const_reference elem) {
269 #if __TBB_CPP11_IS_COPY_CONSTRUCTIBLE_PRESENT 272 cpq_operation op_data(elem, PUSH_OP);
273 my_aggregator.execute(&op_data);
274 if (op_data.status ==
FAILED)
278 #if __TBB_CPP11_RVALUE_REF_PRESENT 282 cpq_operation op_data(elem, PUSH_RVALUE_OP);
283 my_aggregator.execute(&op_data);
284 if (op_data.status ==
FAILED)
288 #if __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT 291 template<
typename... Args>
293 push(value_type(std::forward<Args>(args)...));
303 cpq_operation op_data(POP_OP);
304 op_data.elem = &elem;
305 my_aggregator.execute(&op_data);
343 type(t), elem(const_cast<value_type*>(&e)) {}
385 typedef std::vector<value_type, allocator_type>
vector_t;
389 cpq_operation *tmp, *pop_list=NULL;
406 if (tmp->type == POP_OP) {
407 if (mark < data.size() &&
408 compare(data[0], data[data.size()-1])) {
422 __TBB_ASSERT(tmp->type == PUSH_OP || tmp->type == PUSH_RVALUE_OP,
"Unknown operation" );
424 if (tmp->type == PUSH_OP) {
447 if (mark < data.size() &&
448 compare(data[0], data[data.size()-1])) {
467 if (mark<data.size()) heapify();
473 if (!mark && data.size()>0) mark = 1;
474 for (; mark<data.size(); ++mark) {
476 size_type cur_pos = mark;
479 size_type
parent = (cur_pos-1)>>1;
480 if (!compare(data[parent], to_place))
break;
491 size_type cur_pos=0, child=1;
493 while (child < mark) {
494 size_type target = child;
495 if (child+1 < mark && compare(data[child], data[child+1]))
498 if (compare(data[target], data[data.size()-1]))
break;
501 child = (cur_pos<<1)+1;
503 if (cur_pos != data.size()-1)
506 if (mark > data.size()) mark = data.size();
514 __TBB_ASSERT(
false,
"The type is not copy constructible. Copying push operation is impossible." );
518 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT 521 template<
typename T,
typename... Args>
524 std::conditional_t< (
sizeof...(Args)>0) && !is_allocator_v< pack_element_t<0, Args...> >,
525 pack_element_t<0, Args...>, std::less<T> >,
526 std::conditional_t< (
sizeof...(Args)>0) && is_allocator_v< pack_element_t<
sizeof...(Args)-1, Args...> >,
532 template<
typename InputIterator,
533 typename T =
typename std::iterator_traits<InputIterator>::value_type,
536 -> internal::priority_queue_t<T, Args...>;
538 template<
typename T,
typename CompareOrAllocalor>
540 -> internal::priority_queue_t<T, CompareOrAllocalor>;
550 #undef __TBB_concurrent_priority_queue_H_include_area cpq_operation(operation_type t)
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
ptrdiff_t difference_type
Difference type for iterator.
const T & const_reference
Const reference type.
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
void reheap()
Re-heapify after an extraction.
void __TBB_store_with_release(volatile T &location, V value)
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.
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 begin
size_type mark
The point at which unsorted elements begin.
void heapify()
Merge unsorted elements into heap.
concurrent_priority_queue(InputIterator begin, InputIterator end, const Compare &c, const allocator_type &a=allocator_type())
[begin,end) constructor
void emplace(Args &&... args)
Constructs a new element using args as the arguments for its construction and pushes it onto the queu...
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 call_itt_notify(notify_type, void *)
concurrent_priority_queue(concurrent_priority_queue &&src, const allocator_type &a)
Move constructor with specific allocator.
T & reference
Reference 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.
concurrent_priority_queue(size_type init_capacity, 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(const concurrent_priority_queue &src, const allocator_type &a)
Copy constructor with specific allocator.
concurrent_priority_queue & operator=(const concurrent_priority_queue &src)
Assignment operator.
void swap(concurrent_hash_map< Key, T, HashCompare, A > &a, concurrent_hash_map< Key, T, HashCompare, A > &b)
void push(const_reference elem)
Pushes elem onto the queue, increasing capacity of queue if necessary.
void swap(concurrent_priority_queue &q)
Swap this queue with another; not thread-safe.
T itt_hide_load_word(const T &src)
#define __TBB_STATIC_ASSERT(condition, msg)
concurrent_priority_queue & operator=(std::initializer_list< T > il)
Assign from std::initializer_list, not thread-safe.
#define __TBB_ALLOCATOR_TRAITS_PRESENT
void assign(InputIterator begin, InputIterator end)
Assign the queue from [begin,end) range, not thread-safe.
T __TBB_load_with_acquire(const volatile T &location)
void swap(atomic< T > &lhs, atomic< T > &rhs)
my_functor_t(concurrent_priority_queue< T, Compare, A > *cpq_)
void move(tbb_thread &t1, tbb_thread &t2)
void itt_hide_store_word(T &dst, T src)
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 __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
bool try_pop(reference elem)
Gets a reference to and removes highest priority element.
tbb::internal::true_type type
size_t size_type
Integral type for representing size of the queue.
void clear()
Clear the queue; not thread-safe.
concurrent_priority_queue< T, Compare, A > * cpq
concurrent_priority_queue & operator=(concurrent_priority_queue &&src)
Move assignment operator.
Meets "allocator" requirements of ISO C++ Standard, Section 20.1.5.
tbb::internal::aggregator< my_functor_t, cpq_operation > aggregator_t
void throw_exception(exception_id eid)
Versionless convenience wrapper for throw_exception_v4()
void push_back_helper(const T &t, tbb::internal::true_type)
aggregator_t my_aggregator
concurrent_priority_queue(const concurrent_priority_queue &src)
Copy constructor.
const size_t NFS_MaxLineSize
Compile-time constant that is upper bound on cache line/sector size.
void operator()(cpq_operation *op_list)
cpq_operation(const_reference e, operation_type t)
void push_back_helper(const T &, tbb::internal::false_type)
__TBB_atomic size_type my_size
concurrent_priority_queue(const Compare &c, const allocator_type &a=allocator_type())
Constructs a new concurrent_priority_queue with default capacity.
aggregated_operation base class
void handle_operations(cpq_operation *op_list)
concurrent_priority_queue(InputIterator begin, InputIterator end, const allocator_type &a=allocator_type())
[begin,end) constructor
allocator_type get_allocator() const
Return allocator object.
A allocator_type
Allocator type.
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
bool empty() const
Returns true if empty, false otherwise.
size_type size() const
Returns the current number of elements contained in the queue.
std::vector< value_type, allocator_type > vector_t
Storage for the heap of elements in queue, plus unheapified elements.
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
T value_type
Element type in the queue.
void itt_store_word_with_release(tbb::atomic< T > &dst, U src)
Concurrent priority queue.