Intel(R) Threading Building Blocks Doxygen Documentation
version 4.2.3
|
Go to the documentation of this file.
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>
121 my_aggregator.initialize_handler(my_functor_t(
this));
123 my_size =
data.size();
127 template<
typename InputIterator>
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
161 my_aggregator.initialize_handler(my_functor_t(
this));
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>
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);
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() &&
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() &&
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
concurrent_priority_queue(const concurrent_priority_queue &src)
Copy constructor.
tbb::internal::aggregator< my_functor_t, cpq_operation > aggregator_t
T __TBB_load_with_acquire(const volatile T &location)
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 end
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
void itt_store_word_with_release(tbb::atomic< T > &dst, U src)
void throw_exception(exception_id eid)
Versionless convenience wrapper for throw_exception_v4()
bool try_pop(reference elem)
Gets a reference to and removes highest priority element.
T value_type
Element type in the queue.
aggregated_operation base class
Meets "allocator" requirements of ISO C++ Standard, Section 20.1.5.
void swap(atomic< T > &lhs, atomic< T > &rhs)
T & reference
Reference type.
size_type mark
The point at which unsorted elements begin.
bool empty() const
Returns true if empty, false otherwise.
Class for determining type of std::allocator<T>::value_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 begin
concurrent_priority_queue(const Compare &c, const allocator_type &a=allocator_type())
Constructs a new concurrent_priority_queue with default capacity.
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
concurrent_priority_queue(const allocator_type &a=allocator_type())
Constructs a new concurrent_priority_queue with default capacity.
#define __TBB_ALLOCATOR_TRAITS_PRESENT
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::internal::true_type type
concurrent_priority_queue(const concurrent_priority_queue &src, const allocator_type &a)
Copy constructor with specific allocator.
cpq_operation(const_reference e, operation_type t)
void clear()
Clear the queue; not thread-safe.
cpq_operation(operation_type t)
concurrent_priority_queue< T, Compare, A > * cpq
void emplace(Args &&... args)
Constructs a new element using args as the arguments for its construction and pushes it onto the queu...
size_type size() const
Returns the current number of elements contained in the queue.
void push_back_helper(const T &, tbb::internal::false_type)
#define __TBB_STATIC_ASSERT(condition, msg)
void move(tbb_thread &t1, tbb_thread &t2)
void __TBB_store_with_release(volatile T &location, V value)
void reheap()
Re-heapify after an extraction.
concurrent_priority_queue & operator=(const concurrent_priority_queue &src)
Assignment operator.
concurrent_priority_queue(concurrent_priority_queue &&src, const allocator_type &a)
Move constructor with specific allocator.
void heapify()
Merge unsorted elements into heap.
const size_t NFS_MaxLineSize
Compile-time constant that is upper bound on cache line/sector size.
concurrent_priority_queue & operator=(concurrent_priority_queue &&src)
Move assignment operator.
void push(const_reference elem)
Pushes elem onto the queue, increasing capacity of queue if necessary.
Concurrent priority queue.
concurrent_priority_queue(InputIterator begin, InputIterator end, const Compare &c, const allocator_type &a=allocator_type())
[begin,end) 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 parent
const typedef 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)
Move constructor.
aggregator_t my_aggregator
void itt_hide_store_word(T &dst, T src)
concurrent_priority_queue(std::initializer_list< T > init_list, const Compare &c, const allocator_type &a=allocator_type())
Constructor from std::initializer_list.
allocator_type get_allocator() const
Return allocator object.
void push_back_helper(const T &t, tbb::internal::true_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 value
Identifiers declared inside namespace internal should never be used directly by client code.
std::vector< value_type, allocator_type > vector_t
Storage for the heap of elements in queue, plus unheapified elements.
T itt_hide_load_word(const T &src)
size_t size_type
Integral type for representing size of the queue.
void call_itt_notify(notify_type, void *)
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.
void assign(InputIterator begin, InputIterator end)
Assign the queue from [begin,end) range, 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 __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 swap(concurrent_hash_map< Key, T, HashCompare, A > &a, concurrent_hash_map< Key, T, HashCompare, A > &b)
my_functor_t(concurrent_priority_queue< T, Compare, A > *cpq_)
void operator()(cpq_operation *op_list)
concurrent_priority_queue & operator=(std::initializer_list< T > il)
Assign from std::initializer_list, 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 __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
void swap(concurrent_priority_queue &q)
Swap this queue with another; not thread-safe.
A allocator_type
Allocator type.
ptrdiff_t difference_type
Difference type for iterator.
__TBB_atomic size_type my_size
Copyright © 2005-2020 Intel Corporation. All Rights Reserved.
Intel, Pentium, Intel Xeon, Itanium, Intel XScale and VTune are
registered trademarks or trademarks of Intel Corporation or its
subsidiaries in the United States and other countries.
* Other names and brands may be claimed as the property of others.