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(concurrent_priority_queue &&src)
Move constructor.
concurrent_priority_queue & operator=(std::initializer_list< T > il)
Assign from std::initializer_list, not thread-safe.
T & reference
Reference type.
T __TBB_load_with_acquire(const volatile T &location)
concurrent_priority_queue & operator=(concurrent_priority_queue &&src)
Move assignment operator.
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
concurrent_priority_queue< T, Compare, A > * cpq
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
void emplace(Args &&... args)
Constructs a new element using args as the arguments for its construction and pushes it onto the queu...
void itt_store_word_with_release(tbb::atomic< T > &dst, U src)
const typedef T & const_reference
Const reference type.
void throw_exception(exception_id eid)
Versionless convenience wrapper for throw_exception_v4()
cpq_operation(operation_type t)
aggregated_operation base class
void assign(InputIterator begin, InputIterator end)
Assign the queue from [begin,end) range, not thread-safe.
tbb::internal::aggregator< my_functor_t, cpq_operation > aggregator_t
concurrent_priority_queue(size_type init_capacity, const allocator_type &a=allocator_type())
Constructs a new concurrent_priority_queue with init_sz capacity.
void swap(atomic< T > &lhs, atomic< T > &rhs)
Meets "allocator" requirements of ISO C++ Standard, Section 20.1.5.
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 size
concurrent_priority_queue(const concurrent_priority_queue &src)
Copy constructor.
void reheap()
Re-heapify after an extraction.
#define __TBB_ALLOCATOR_TRAITS_PRESENT
concurrent_priority_queue(std::initializer_list< T > init_list, const Compare &c, const allocator_type &a=allocator_type())
Constructor from std::initializer_list.
tbb::internal::true_type type
allocator_type get_allocator() const
Return allocator object.
size_t size_type
Integral type for representing size of the queue.
void swap(concurrent_priority_queue &q)
Swap this queue with another; not thread-safe.
concurrent_priority_queue(InputIterator begin, InputIterator end, const allocator_type &a=allocator_type())
[begin,end) constructor
__TBB_atomic size_type my_size
my_functor_t(concurrent_priority_queue< T, Compare, A > *cpq_)
std::vector< value_type, allocator_type > vector_t
Storage for the heap of elements in queue, plus unheapified elements.
void heapify()
Merge unsorted elements into heap.
#define __TBB_STATIC_ASSERT(condition, msg)
T value_type
Element type in the queue.
void handle_operations(cpq_operation *op_list)
void move(tbb_thread &t1, tbb_thread &t2)
cpq_operation(const_reference e, operation_type t)
concurrent_priority_queue(const allocator_type &a=allocator_type())
Constructs a new concurrent_priority_queue with default capacity.
void __TBB_store_with_release(volatile T &location, V value)
void push_back_helper(const T &t, tbb::internal::true_type)
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 parent
void push_back_helper(const T &, tbb::internal::false_type)
ptrdiff_t difference_type
Difference type for iterator.
void itt_hide_store_word(T &dst, T src)
concurrent_priority_queue(const concurrent_priority_queue &src, const allocator_type &a)
Copy constructor with specific allocator.
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(const Compare &c, const allocator_type &a=allocator_type())
Constructs a new concurrent_priority_queue with default capacity.
Concurrent priority queue.
size_type mark
The point at which unsorted elements begin.
void operator()(cpq_operation *op_list)
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
aggregator_t my_aggregator
size_type size() const
Returns the current number of elements contained in the queue.
A allocator_type
Allocator type.
Identifiers declared inside namespace internal should never be used directly by client code.
bool empty() const
Returns true if empty, false otherwise.
T itt_hide_load_word(const T &src)
void call_itt_notify(notify_type, void *)
concurrent_priority_queue & operator=(const concurrent_priority_queue &src)
Assignment operator.
bool try_pop(reference elem)
Gets a reference to and removes highest priority element.
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 clear()
Clear the queue; not thread-safe.
void swap(concurrent_hash_map< Key, T, HashCompare, A > &a, concurrent_hash_map< Key, T, HashCompare, A > &b)
Class for determining type of std::allocator<T>::value_type.
void push(const_reference 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 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
concurrent_priority_queue(InputIterator begin, InputIterator end, const Compare &c, 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.
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.