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> >
102 mark(0), my_size(0), compare(),
data(a)
104 data.reserve(init_capacity);
110 mark(0), my_size(0), compare(c),
data(a)
112 data.reserve(init_capacity);
117 template<
typename InputIterator>
123 my_size =
data.size();
127 template<
typename InputIterator>
133 my_size =
data.size();
136 #if __TBB_INITIALIZER_LISTS_PRESENT
139 mark(0), compare(),
data(init_list.
begin(), init_list.
end(), a)
143 my_size =
data.size();
148 mark(0), compare(c),
data(init_list.
begin(), init_list.
end(), a)
152 my_size =
data.size();
185 #if __TBB_CPP11_RVALUE_REF_PRESENT
197 my_size(src.my_size),
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);
237 template<
typename InputIterator>
241 my_size =
data.size();
245 #if __TBB_INITIALIZER_LISTS_PRESENT
247 void assign(std::initializer_list<T> il) { this->
assign(il.begin(), il.end()); }
251 this->assign(il.begin(), il.end());
269 #if __TBB_CPP11_IS_COPY_CONSTRUCTIBLE_PRESENT
273 my_aggregator.execute(&op_data);
278 #if __TBB_CPP11_RVALUE_REF_PRESENT
283 my_aggregator.execute(&op_data);
288 #if __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT
291 template<
typename... Args>
293 push(
value_type(std::forward<Args>(args)...));
304 op_data.
elem = &elem;
305 my_aggregator.execute(&op_data);
385 typedef std::vector<value_type, allocator_type>
vector_t;
406 if (tmp->
type == POP_OP) {
407 if (mark <
data.size() &&
424 if (tmp->
type == PUSH_OP) {
447 if (mark <
data.size() &&
467 if (mark<
data.size()) heapify();
473 if (!mark &&
data.size()>0) mark = 1;
474 for (; mark<
data.size(); ++mark) {
493 while (child < mark) {
495 if (child+1 < mark && compare(
data[child],
data[child+1]))
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,
535 > concurrent_priority_queue(InputIterator, InputIterator, Args...)
536 -> internal::priority_queue_t<T, Args...>;
538 template<
typename T,
typename CompareOrAllocalor>
539 concurrent_priority_queue(std::initializer_list<T> init_list, CompareOrAllocalor)
540 -> internal::priority_queue_t<T, CompareOrAllocalor>;
545 using interface5::concurrent_priority_queue;
550 #undef __TBB_concurrent_priority_queue_H_include_area
#define __TBB_ALLOCATOR_TRAITS_PRESENT
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
#define __TBB_STATIC_ASSERT(condition, msg)
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_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle __itt_metadata_type size_t void * data
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 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 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 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
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_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle __itt_metadata_type type
const size_t NFS_MaxLineSize
Compile-time constant that is upper bound on cache line/sector size.
void swap(concurrent_hash_map< Key, T, HashCompare, A > &a, concurrent_hash_map< Key, T, HashCompare, A > &b)
void move(tbb_thread &t1, tbb_thread &t2)
Identifiers declared inside namespace internal should never be used directly by client code.
T __TBB_load_with_acquire(const volatile T &location)
void swap(atomic< T > &lhs, atomic< T > &rhs)
void throw_exception(exception_id eid)
Versionless convenience wrapper for throw_exception_v4()
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)
Meets "allocator" requirements of ISO C++ Standard, Section 20.1.5.
tbb::internal::true_type type
Concurrent priority queue.
concurrent_priority_queue(InputIterator begin, InputIterator end, const Compare &c, const allocator_type &a=allocator_type())
[begin,end) constructor
const T & const_reference
Const reference 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 push(const_reference elem)
Pushes elem onto the queue, increasing capacity of queue if necessary.
A allocator_type
Allocator type.
void clear()
Clear the queue; not thread-safe.
void push_back_helper(const T &, tbb::internal::false_type)
T value_type
Element type in the queue.
concurrent_priority_queue(const concurrent_priority_queue &src)
Copy constructor.
concurrent_priority_queue(const allocator_type &a=allocator_type())
Constructs a new concurrent_priority_queue with default capacity.
concurrent_priority_queue(size_type init_capacity, const allocator_type &a=allocator_type())
Constructs a new concurrent_priority_queue with init_sz capacity.
void push(value_type &&elem)
Pushes elem onto the queue, increasing capacity of queue if necessary.
tbb::internal::aggregator< my_functor_t, cpq_operation > aggregator_t
size_type size() const
Returns the current number of elements contained in the queue.
size_t size_type
Integral type for representing size of the queue.
concurrent_priority_queue & operator=(std::initializer_list< T > il)
Assign from std::initializer_list, not thread-safe.
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.
__TBB_atomic size_type my_size
bool try_pop(reference elem)
Gets a reference to and removes highest priority element.
concurrent_priority_queue & operator=(concurrent_priority_queue &&src)
Move assignment operator.
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 concurrent_priority_queue &src, const allocator_type &a)
Copy constructor with specific allocator.
aggregator_t my_aggregator
void swap(concurrent_priority_queue &q)
Swap this queue with another; not thread-safe.
concurrent_priority_queue(std::initializer_list< T > init_list, const allocator_type &a=allocator_type())
Constructor from std::initializer_list.
void reheap()
Re-heapify after an extraction.
concurrent_priority_queue & operator=(const concurrent_priority_queue &src)
Assignment operator.
void assign(std::initializer_list< T > il)
Assign the queue from std::initializer_list, not thread-safe.
void heapify()
Merge unsorted elements into heap.
void assign(InputIterator begin, InputIterator end)
Assign the queue from [begin,end) range, not thread-safe.
size_type mark
The point at which unsorted elements begin.
bool empty() const
Returns true if empty, false otherwise.
std::vector< value_type, allocator_type > vector_t
Storage for the heap of elements in queue, plus unheapified elements.
concurrent_priority_queue(const Compare &c, const allocator_type &a=allocator_type())
Constructs a new concurrent_priority_queue with default capacity.
ptrdiff_t difference_type
Difference type for iterator.
T & reference
Reference type.
concurrent_priority_queue(concurrent_priority_queue &&src)
Move constructor.
void emplace(Args &&... args)
Constructs a new element using args as the arguments for its construction and pushes it onto the queu...
void handle_operations(cpq_operation *op_list)
void push_back_helper(const T &t, tbb::internal::true_type)
allocator_type get_allocator() const
Return allocator object.
cpq_operation(operation_type t)
cpq_operation(const_reference e, operation_type t)
my_functor_t(concurrent_priority_queue< T, Compare, A > *cpq_)
concurrent_priority_queue< T, Compare, A > * cpq
void operator()(cpq_operation *op_list)
aggregated_operation base class
uintptr_t status
Zero value means "wait" status, all other values are "user" specified values and are defined into the...