concurrent_priority_queue.h
Go to the documentation of this file.
/*
Copyright (c) 2005-2020 Intel Corporation
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/
#ifndef __TBB_concurrent_priority_queue_H
#define __TBB_concurrent_priority_queue_H
#define __TBB_concurrent_priority_queue_H_include_area
#include "internal/_warning_suppress_enable_notice.h"
#include "atomic.h"
#include "cache_aligned_allocator.h"
#include "tbb_exception.h"
#include "tbb_stddef.h"
#include "tbb_profiling.h"
#include "internal/_aggregator_impl.h"
#include "internal/_template_helpers.h"
#include "internal/_allocator_traits.h"
#include <vector>
#include <iterator>
#include <functional>
#include __TBB_STD_SWAP_HEADER
#if __TBB_INITIALIZER_LISTS_PRESENT
#include <initializer_list>
#endif
#if __TBB_CPP11_IS_COPY_CONSTRUCTIBLE_PRESENT
#include <type_traits>
#endif
namespace tbb {
namespace interface5 {
namespace internal {
#if __TBB_CPP11_IS_COPY_CONSTRUCTIBLE_PRESENT
template<typename T, bool C = std::is_copy_constructible<T>::value>
struct use_element_copy_constructor {
typedef tbb::internal::true_type type;
};
template<typename T>
struct use_element_copy_constructor <T,false> {
typedef tbb::internal::false_type type;
};
#else
template<typename>
struct use_element_copy_constructor {
typedef tbb::internal::true_type type;
};
#endif
} // namespace internal
using namespace tbb::internal;
template <typename T, typename Compare=std::less<T>, typename A=cache_aligned_allocator<T> >
class concurrent_priority_queue {
public:
typedef T value_type;
typedef T& reference;
typedef const T& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef A allocator_type;
explicit concurrent_priority_queue(const allocator_type& a = allocator_type()) : mark(0), my_size(0), compare(), data(a)
{
my_aggregator.initialize_handler(my_functor_t(this));
}
explicit concurrent_priority_queue(const Compare& c, const allocator_type& a = allocator_type()) : mark(0), my_size(0), compare(c), data(a)
{
my_aggregator.initialize_handler(my_functor_t(this));
}
explicit concurrent_priority_queue(size_type init_capacity, const allocator_type& a = allocator_type()) :
mark(0), my_size(0), compare(), data(a)
{
data.reserve(init_capacity);
my_aggregator.initialize_handler(my_functor_t(this));
}
explicit concurrent_priority_queue(size_type init_capacity, const Compare& c, const allocator_type& a = allocator_type()) :
mark(0), my_size(0), compare(c), data(a)
{
data.reserve(init_capacity);
my_aggregator.initialize_handler(my_functor_t(this));
}
template<typename InputIterator>
concurrent_priority_queue(InputIterator begin, InputIterator end, const allocator_type& a = allocator_type()) :
mark(0), compare(), data(begin, end, a)
{
my_aggregator.initialize_handler(my_functor_t(this));
heapify();
my_size = data.size();
}
template<typename InputIterator>
concurrent_priority_queue(InputIterator begin, InputIterator end, const Compare& c, const allocator_type& a = allocator_type()) :
mark(0), compare(c), data(begin, end, a)
{
my_aggregator.initialize_handler(my_functor_t(this));
heapify();
my_size = data.size();
}
#if __TBB_INITIALIZER_LISTS_PRESENT
concurrent_priority_queue(std::initializer_list<T> init_list, const allocator_type &a = allocator_type()) :
mark(0), compare(), data(init_list.begin(), init_list.end(), a)
{
my_aggregator.initialize_handler(my_functor_t(this));
heapify();
my_size = data.size();
}
concurrent_priority_queue(std::initializer_list<T> init_list, const Compare& c, const allocator_type &a = allocator_type()) :
mark(0), compare(c), data(init_list.begin(), init_list.end(), a)
{
my_aggregator.initialize_handler(my_functor_t(this));
heapify();
my_size = data.size();
}
#endif //# __TBB_INITIALIZER_LISTS_PRESENT
concurrent_priority_queue(const concurrent_priority_queue& src) : mark(src.mark),
my_size(src.my_size), data(src.data.begin(), src.data.end(), src.data.get_allocator())
{
my_aggregator.initialize_handler(my_functor_t(this));
heapify();
}
concurrent_priority_queue(const concurrent_priority_queue& src, const allocator_type& a) : mark(src.mark),
my_size(src.my_size), data(src.data.begin(), src.data.end(), a)
{
my_aggregator.initialize_handler(my_functor_t(this));
heapify();
}
concurrent_priority_queue& operator=(const concurrent_priority_queue& src) {
if (this != &src) {
vector_t(src.data.begin(), src.data.end(), src.data.get_allocator()).swap(data);
mark = src.mark;
my_size = src.my_size;
}
return *this;
}
#if __TBB_CPP11_RVALUE_REF_PRESENT
concurrent_priority_queue(concurrent_priority_queue&& src) : mark(src.mark),
my_size(src.my_size), data(std::move(src.data))
{
my_aggregator.initialize_handler(my_functor_t(this));
}
concurrent_priority_queue(concurrent_priority_queue&& src, const allocator_type& a) : mark(src.mark),
my_size(src.my_size),
#if __TBB_ALLOCATOR_TRAITS_PRESENT
data(std::move(src.data), a)
#else
// Some early version of C++11 STL vector does not have a constructor of vector(vector&& , allocator).
// It seems that the reason is absence of support of allocator_traits (stateful allocators).
data(a)
#endif //__TBB_ALLOCATOR_TRAITS_PRESENT
{
my_aggregator.initialize_handler(my_functor_t(this));
#if !__TBB_ALLOCATOR_TRAITS_PRESENT
if (a != src.data.get_allocator()){
data.reserve(src.data.size());
data.assign(std::make_move_iterator(src.data.begin()), std::make_move_iterator(src.data.end()));
}else{
data = std::move(src.data);
}
#endif
}
concurrent_priority_queue& operator=( concurrent_priority_queue&& src) {
if (this != &src) {
mark = src.mark;
my_size = src.my_size;
#if !__TBB_ALLOCATOR_TRAITS_PRESENT
if (data.get_allocator() != src.data.get_allocator()){
vector_t(std::make_move_iterator(src.data.begin()), std::make_move_iterator(src.data.end()), data.get_allocator()).swap(data);
}else
#endif
{
data = std::move(src.data);
}
}
return *this;
}
#endif //__TBB_CPP11_RVALUE_REF_PRESENT
template<typename InputIterator>
void assign(InputIterator begin, InputIterator end) {
vector_t(begin, end, data.get_allocator()).swap(data);
mark = 0;
my_size = data.size();
heapify();
}
#if __TBB_INITIALIZER_LISTS_PRESENT
void assign(std::initializer_list<T> il) { this->assign(il.begin(), il.end()); }
concurrent_priority_queue& operator=(std::initializer_list<T> il) {
this->assign(il.begin(), il.end());
return *this;
}
#endif //# __TBB_INITIALIZER_LISTS_PRESENT
bool empty() const { return size()==0; }
size_type size() const { return __TBB_load_with_acquire(my_size); }
void push(const_reference elem) {
#if __TBB_CPP11_IS_COPY_CONSTRUCTIBLE_PRESENT
__TBB_STATIC_ASSERT( std::is_copy_constructible<value_type>::value, "The type is not copy constructible. Copying push operation is impossible." );
#endif
cpq_operation op_data(elem, PUSH_OP);
my_aggregator.execute(&op_data);
if (op_data.status == FAILED) // exception thrown
throw_exception(eid_bad_alloc);
}
#if __TBB_CPP11_RVALUE_REF_PRESENT
void push(value_type &&elem) {
cpq_operation op_data(elem, PUSH_RVALUE_OP);
my_aggregator.execute(&op_data);
if (op_data.status == FAILED) // exception thrown
throw_exception(eid_bad_alloc);
}
#if __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT
template<typename... Args>
void emplace(Args&&... args) {
push(value_type(std::forward<Args>(args)...));
}
#endif /* __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT */
#endif /* __TBB_CPP11_RVALUE_REF_PRESENT */
bool try_pop(reference elem) {
cpq_operation op_data(POP_OP);
op_data.elem = &elem;
my_aggregator.execute(&op_data);
return op_data.status==SUCCEEDED;
}
void clear() {
data.clear();
mark = 0;
my_size = 0;
}
void swap(concurrent_priority_queue& q) {
using std::swap;
data.swap(q.data);
swap(mark, q.mark);
swap(my_size, q.my_size);
}
allocator_type get_allocator() const { return data.get_allocator(); }
private:
enum operation_type {INVALID_OP, PUSH_OP, POP_OP, PUSH_RVALUE_OP};
enum operation_status { WAIT=0, SUCCEEDED, FAILED };
class cpq_operation : public aggregated_operation<cpq_operation> {
public:
operation_type type;
union {
value_type *elem;
size_type sz;
};
cpq_operation(const_reference e, operation_type t) :
type(t), elem(const_cast<value_type*>(&e)) {}
cpq_operation(operation_type t) : type(t) {}
};
class my_functor_t {
concurrent_priority_queue<T, Compare, A> *cpq;
public:
my_functor_t() {}
my_functor_t(concurrent_priority_queue<T, Compare, A> *cpq_) : cpq(cpq_) {}
void operator()(cpq_operation* op_list) {
cpq->handle_operations(op_list);
}
};
typedef tbb::internal::aggregator< my_functor_t, cpq_operation > aggregator_t;
aggregator_t my_aggregator;
char padding1[NFS_MaxLineSize - sizeof(aggregator_t)];
size_type mark;
__TBB_atomic size_type my_size;
Compare compare;
char padding2[NFS_MaxLineSize - (2*sizeof(size_type)) - sizeof(Compare)];
typedef std::vector<value_type, allocator_type> vector_t;
vector_t data;
void handle_operations(cpq_operation *op_list) {
cpq_operation *tmp, *pop_list=NULL;
__TBB_ASSERT(mark == data.size(), NULL);
// First pass processes all constant (amortized; reallocation may happen) time pushes and pops.
while (op_list) {
// ITT note: &(op_list->status) tag is used to cover accesses to op_list
// node. This thread is going to handle the operation, and so will acquire it
// and perform the associated operation w/o triggering a race condition; the
// thread that created the operation is waiting on the status field, so when
// this thread is done with the operation, it will perform a
// store_with_release to give control back to the waiting thread in
// aggregator::insert_operation.
call_itt_notify(acquired, &(op_list->status));
__TBB_ASSERT(op_list->type != INVALID_OP, NULL);
tmp = op_list;
op_list = itt_hide_load_word(op_list->next);
if (tmp->type == POP_OP) {
if (mark < data.size() &&
compare(data[0], data[data.size()-1])) {
// there are newly pushed elems and the last one
// is higher than top
*(tmp->elem) = tbb::internal::move(data[data.size()-1]);
__TBB_store_with_release(my_size, my_size-1);
itt_store_word_with_release(tmp->status, uintptr_t(SUCCEEDED));
data.pop_back();
__TBB_ASSERT(mark<=data.size(), NULL);
}
else { // no convenient item to pop; postpone
itt_hide_store_word(tmp->next, pop_list);
pop_list = tmp;
}
} else { // PUSH_OP or PUSH_RVALUE_OP
__TBB_ASSERT(tmp->type == PUSH_OP || tmp->type == PUSH_RVALUE_OP, "Unknown operation" );
__TBB_TRY{
if (tmp->type == PUSH_OP) {
push_back_helper(*(tmp->elem), typename internal::use_element_copy_constructor<value_type>::type());
} else {
data.push_back(tbb::internal::move(*(tmp->elem)));
}
__TBB_store_with_release(my_size, my_size + 1);
itt_store_word_with_release(tmp->status, uintptr_t(SUCCEEDED));
} __TBB_CATCH(...) {
itt_store_word_with_release(tmp->status, uintptr_t(FAILED));
}
}
}
// second pass processes pop operations
while (pop_list) {
tmp = pop_list;
pop_list = itt_hide_load_word(pop_list->next);
__TBB_ASSERT(tmp->type == POP_OP, NULL);
if (data.empty()) {
itt_store_word_with_release(tmp->status, uintptr_t(FAILED));
}
else {
__TBB_ASSERT(mark<=data.size(), NULL);
if (mark < data.size() &&
compare(data[0], data[data.size()-1])) {
// there are newly pushed elems and the last one is
// higher than top
*(tmp->elem) = tbb::internal::move(data[data.size()-1]);
__TBB_store_with_release(my_size, my_size-1);
itt_store_word_with_release(tmp->status, uintptr_t(SUCCEEDED));
data.pop_back();
}
else { // extract top and push last element down heap
*(tmp->elem) = tbb::internal::move(data[0]);
__TBB_store_with_release(my_size, my_size-1);
itt_store_word_with_release(tmp->status, uintptr_t(SUCCEEDED));
reheap();
}
}
}
// heapify any leftover pushed elements before doing the next
// batch of operations
if (mark<data.size()) heapify();
__TBB_ASSERT(mark == data.size(), NULL);
}
void heapify() {
if (!mark && data.size()>0) mark = 1;
for (; mark<data.size(); ++mark) {
// for each unheapified element under size
size_type cur_pos = mark;
value_type to_place = tbb::internal::move(data[mark]);
do { // push to_place up the heap
size_type parent = (cur_pos-1)>>1;
if (!compare(data[parent], to_place)) break;
data[cur_pos] = tbb::internal::move(data[parent]);
cur_pos = parent;
} while( cur_pos );
data[cur_pos] = tbb::internal::move(to_place);
}
}
void reheap() {
size_type cur_pos=0, child=1;
while (child < mark) {
size_type target = child;
if (child+1 < mark && compare(data[child], data[child+1]))
++target;
// target now has the higher priority child
if (compare(data[target], data[data.size()-1])) break;
data[cur_pos] = tbb::internal::move(data[target]);
cur_pos = target;
child = (cur_pos<<1)+1;
}
if (cur_pos != data.size()-1)
data[cur_pos] = tbb::internal::move(data[data.size()-1]);
data.pop_back();
if (mark > data.size()) mark = data.size();
}
void push_back_helper(const T& t, tbb::internal::true_type) {
data.push_back(t);
}
void push_back_helper(const T&, tbb::internal::false_type) {
__TBB_ASSERT( false, "The type is not copy constructible. Copying push operation is impossible." );
}
};
#if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
namespace internal {
template<typename T, typename... Args>
using priority_queue_t = concurrent_priority_queue<
T,
std::conditional_t< (sizeof...(Args)>0) && !is_allocator_v< pack_element_t<0, Args...> >,
pack_element_t<0, Args...>, std::less<T> >,
std::conditional_t< (sizeof...(Args)>0) && is_allocator_v< pack_element_t<sizeof...(Args)-1, Args...> >,
pack_element_t<sizeof...(Args)-1, Args...>, cache_aligned_allocator<T> >
>;
}
// Deduction guide for the constructor from two iterators
template<typename InputIterator,
typename T = typename std::iterator_traits<InputIterator>::value_type,
typename... Args
> concurrent_priority_queue(InputIterator, InputIterator, Args...)
-> internal::priority_queue_t<T, Args...>;
template<typename T, typename CompareOrAllocalor>
concurrent_priority_queue(std::initializer_list<T> init_list, CompareOrAllocalor)
-> internal::priority_queue_t<T, CompareOrAllocalor>;
#endif /* __TBB_CPP17_DEDUCTION_GUIDES_PRESENT */
} // namespace interface5
using interface5::concurrent_priority_queue;
} // namespace tbb
#include "internal/_warning_suppress_disable_notice.h"
#undef __TBB_concurrent_priority_queue_H_include_area
#endif /* __TBB_concurrent_priority_queue_H */
atomic.h
cache_aligned_allocator.h
_aggregator_impl.h
_allocator_traits.h
_template_helpers.h
_warning_suppress_disable_notice.h
_warning_suppress_enable_notice.h
__TBB_ALLOCATOR_TRAITS_PRESENT
#define __TBB_ALLOCATOR_TRAITS_PRESENT
Definition: tbb_config.h:336
tbb_exception.h
tbb_profiling.h
tbb_stddef.h
__TBB_CATCH
#define __TBB_CATCH(e)
Definition: tbb_stddef.h:284
__TBB_atomic
#define __TBB_atomic
Definition: tbb_stddef.h:237
__TBB_TRY
#define __TBB_TRY
Definition: tbb_stddef.h:283
__TBB_ASSERT
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
__TBB_STATIC_ASSERT
#define __TBB_STATIC_ASSERT(condition, msg)
Definition: tbb_stddef.h:553
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 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
Definition: ittnotify_static.h:198
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 __itt_timestamp end
Definition: ittnotify_static.h:182
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 __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp begin
Definition: ittnotify_static.h:182
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 parent
Definition: ittnotify_static.h:176
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 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
Definition: ittnotify_static.h:192
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 size
Definition: ittnotify_static.h:109
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_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle __itt_metadata_type type
Definition: ittnotify_static.h:198
tbb::internal::NFS_MaxLineSize
const size_t NFS_MaxLineSize
Compile-time constant that is upper bound on cache line/sector size.
Definition: tbb_stddef.h:216
tbb
The graph class.
Definition: serial/tbb/parallel_for.h:46
tbb::swap
void swap(concurrent_hash_map< Key, T, HashCompare, A > &a, concurrent_hash_map< Key, T, HashCompare, A > &b)
Definition: concurrent_hash_map.h:1638
tbb::move
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:319
tbb::internal
Identifiers declared inside namespace internal should never be used directly by client code.
Definition: atomic.h:65
tbb::internal::acquired
@ acquired
Definition: tbb_profiling.h:129
tbb::internal::__TBB_load_with_acquire
T __TBB_load_with_acquire(const volatile T &location)
Definition: tbb_machine.h:712
tbb::internal::swap
void swap(atomic< T > &lhs, atomic< T > &rhs)
Definition: atomic.h:564
tbb::internal::throw_exception
void throw_exception(exception_id eid)
Versionless convenience wrapper for throw_exception_v4()
Definition: tbb_exception.h:105
tbb::internal::itt_hide_store_word
void itt_hide_store_word(T &dst, T src)
Definition: tbb_profiling.h:210
tbb::internal::itt_store_word_with_release
void itt_store_word_with_release(tbb::atomic< T > &dst, U src)
Definition: tbb_profiling.h:157
tbb::internal::eid_bad_alloc
@ eid_bad_alloc
Definition: tbb_exception.h:68
tbb::internal::itt_hide_load_word
T itt_hide_load_word(const T &src)
Definition: tbb_profiling.h:222
tbb::internal::call_itt_notify
void call_itt_notify(notify_type, void *)
Definition: tbb_profiling.h:276
tbb::internal::__TBB_store_with_release
void __TBB_store_with_release(volatile T &location, V value)
Definition: tbb_machine.h:716
internal
Definition: _flow_graph_async_msg_impl.h:24
internal::WAIT
@ WAIT
Definition: _flow_graph_types_impl.h:719
internal::FAILED
@ FAILED
Definition: _flow_graph_types_impl.h:719
internal::SUCCEEDED
@ SUCCEEDED
Definition: _flow_graph_types_impl.h:719
tbb::cache_aligned_allocator
Meets "allocator" requirements of ISO C++ Standard, Section 20.1.5.
Definition: cache_aligned_allocator.h:60
tbb::interface5::internal::use_element_copy_constructor
Definition: concurrent_priority_queue.h:58
tbb::interface5::internal::use_element_copy_constructor::type
tbb::internal::true_type type
Definition: concurrent_priority_queue.h:59
tbb::interface5::concurrent_priority_queue
Concurrent priority queue.
Definition: concurrent_priority_queue.h:68
tbb::interface5::concurrent_priority_queue::concurrent_priority_queue
concurrent_priority_queue(InputIterator begin, InputIterator end, const Compare &c, const allocator_type &a=allocator_type())
[begin,end) constructor
Definition: concurrent_priority_queue.h:128
tbb::interface5::concurrent_priority_queue::const_reference
const T & const_reference
Const reference type.
Definition: concurrent_priority_queue.h:77
tbb::interface5::concurrent_priority_queue::concurrent_priority_queue
concurrent_priority_queue(InputIterator begin, InputIterator end, const allocator_type &a=allocator_type())
[begin,end) constructor
Definition: concurrent_priority_queue.h:118
tbb::interface5::concurrent_priority_queue::concurrent_priority_queue
concurrent_priority_queue(concurrent_priority_queue &&src, const allocator_type &a)
Move constructor with specific allocator.
Definition: concurrent_priority_queue.h:196
tbb::interface5::concurrent_priority_queue::push
void push(const_reference elem)
Pushes elem onto the queue, increasing capacity of queue if necessary.
Definition: concurrent_priority_queue.h:268
tbb::interface5::concurrent_priority_queue::allocator_type
A allocator_type
Allocator type.
Definition: concurrent_priority_queue.h:86
tbb::interface5::concurrent_priority_queue::clear
void clear()
Clear the queue; not thread-safe.
Definition: concurrent_priority_queue.h:313
tbb::interface5::concurrent_priority_queue::push_back_helper
void push_back_helper(const T &, tbb::internal::false_type)
Definition: concurrent_priority_queue.h:513
tbb::interface5::concurrent_priority_queue::value_type
T value_type
Element type in the queue.
Definition: concurrent_priority_queue.h:71
tbb::interface5::concurrent_priority_queue::concurrent_priority_queue
concurrent_priority_queue(const concurrent_priority_queue &src)
Copy constructor.
Definition: concurrent_priority_queue.h:158
tbb::interface5::concurrent_priority_queue::compare
Compare compare
Definition: concurrent_priority_queue.h:364
tbb::interface5::concurrent_priority_queue::concurrent_priority_queue
concurrent_priority_queue(const allocator_type &a=allocator_type())
Constructs a new concurrent_priority_queue with default capacity.
Definition: concurrent_priority_queue.h:89
tbb::interface5::concurrent_priority_queue::concurrent_priority_queue
concurrent_priority_queue(size_type init_capacity, const allocator_type &a=allocator_type())
Constructs a new concurrent_priority_queue with init_sz capacity.
Definition: concurrent_priority_queue.h:101
tbb::interface5::concurrent_priority_queue::push
void push(value_type &&elem)
Pushes elem onto the queue, increasing capacity of queue if necessary.
Definition: concurrent_priority_queue.h:281
tbb::interface5::concurrent_priority_queue::aggregator_t
tbb::internal::aggregator< my_functor_t, cpq_operation > aggregator_t
Definition: concurrent_priority_queue.h:357
tbb::interface5::concurrent_priority_queue::size
size_type size() const
Returns the current number of elements contained in the queue.
Definition: concurrent_priority_queue.h:264
tbb::interface5::concurrent_priority_queue::size_type
size_t size_type
Integral type for representing size of the queue.
Definition: concurrent_priority_queue.h:80
tbb::interface5::concurrent_priority_queue::operator=
concurrent_priority_queue & operator=(std::initializer_list< T > il)
Assign from std::initializer_list, not thread-safe.
Definition: concurrent_priority_queue.h:250
tbb::interface5::concurrent_priority_queue::concurrent_priority_queue
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.
Definition: concurrent_priority_queue.h:109
tbb::interface5::concurrent_priority_queue::operation_type
operation_type
Definition: concurrent_priority_queue.h:332
tbb::interface5::concurrent_priority_queue::INVALID_OP
@ INVALID_OP
Definition: concurrent_priority_queue.h:332
tbb::interface5::concurrent_priority_queue::my_size
__TBB_atomic size_type my_size
Definition: concurrent_priority_queue.h:363
tbb::interface5::concurrent_priority_queue::try_pop
bool try_pop(reference elem)
Gets a reference to and removes highest priority element.
Definition: concurrent_priority_queue.h:302
tbb::interface5::concurrent_priority_queue::operator=
concurrent_priority_queue & operator=(concurrent_priority_queue &&src)
Move assignment operator.
Definition: concurrent_priority_queue.h:219
tbb::interface5::concurrent_priority_queue::concurrent_priority_queue
concurrent_priority_queue(std::initializer_list< T > init_list, const Compare &c, const allocator_type &a=allocator_type())
Constructor from std::initializer_list.
Definition: concurrent_priority_queue.h:147
tbb::interface5::concurrent_priority_queue::concurrent_priority_queue
concurrent_priority_queue(const concurrent_priority_queue &src, const allocator_type &a)
Copy constructor with specific allocator.
Definition: concurrent_priority_queue.h:167
tbb::interface5::concurrent_priority_queue::my_aggregator
aggregator_t my_aggregator
Definition: concurrent_priority_queue.h:358
tbb::interface5::concurrent_priority_queue::swap
void swap(concurrent_priority_queue &q)
Swap this queue with another; not thread-safe.
Definition: concurrent_priority_queue.h:321
tbb::interface5::concurrent_priority_queue::concurrent_priority_queue
concurrent_priority_queue(std::initializer_list< T > init_list, const allocator_type &a=allocator_type())
Constructor from std::initializer_list.
Definition: concurrent_priority_queue.h:138
tbb::interface5::concurrent_priority_queue::data
vector_t data
Definition: concurrent_priority_queue.h:386
tbb::interface5::concurrent_priority_queue::reheap
void reheap()
Re-heapify after an extraction.
Definition: concurrent_priority_queue.h:490
tbb::interface5::concurrent_priority_queue::operator=
concurrent_priority_queue & operator=(const concurrent_priority_queue &src)
Assignment operator.
Definition: concurrent_priority_queue.h:176
tbb::interface5::concurrent_priority_queue::assign
void assign(std::initializer_list< T > il)
Assign the queue from std::initializer_list, not thread-safe.
Definition: concurrent_priority_queue.h:247
tbb::interface5::concurrent_priority_queue::heapify
void heapify()
Merge unsorted elements into heap.
Definition: concurrent_priority_queue.h:472
tbb::interface5::concurrent_priority_queue::assign
void assign(InputIterator begin, InputIterator end)
Assign the queue from [begin,end) range, not thread-safe.
Definition: concurrent_priority_queue.h:238
tbb::interface5::concurrent_priority_queue::operation_status
operation_status
Definition: concurrent_priority_queue.h:333
tbb::interface5::concurrent_priority_queue::mark
size_type mark
The point at which unsorted elements begin.
Definition: concurrent_priority_queue.h:362
tbb::interface5::concurrent_priority_queue::empty
bool empty() const
Returns true if empty, false otherwise.
Definition: concurrent_priority_queue.h:259
tbb::interface5::concurrent_priority_queue::vector_t
std::vector< value_type, allocator_type > vector_t
Storage for the heap of elements in queue, plus unheapified elements.
Definition: concurrent_priority_queue.h:385
tbb::interface5::concurrent_priority_queue::concurrent_priority_queue
concurrent_priority_queue(const Compare &c, const allocator_type &a=allocator_type())
Constructs a new concurrent_priority_queue with default capacity.
Definition: concurrent_priority_queue.h:95
tbb::interface5::concurrent_priority_queue::difference_type
ptrdiff_t difference_type
Difference type for iterator.
Definition: concurrent_priority_queue.h:83
tbb::interface5::concurrent_priority_queue::reference
T & reference
Reference type.
Definition: concurrent_priority_queue.h:74
tbb::interface5::concurrent_priority_queue::concurrent_priority_queue
concurrent_priority_queue(concurrent_priority_queue &&src)
Move constructor.
Definition: concurrent_priority_queue.h:188
tbb::interface5::concurrent_priority_queue::emplace
void emplace(Args &&... args)
Constructs a new element using args as the arguments for its construction and pushes it onto the queu...
Definition: concurrent_priority_queue.h:292
tbb::interface5::concurrent_priority_queue::handle_operations
void handle_operations(cpq_operation *op_list)
Definition: concurrent_priority_queue.h:388
tbb::interface5::concurrent_priority_queue::push_back_helper
void push_back_helper(const T &t, tbb::internal::true_type)
Definition: concurrent_priority_queue.h:509
tbb::interface5::concurrent_priority_queue::get_allocator
allocator_type get_allocator() const
Return allocator object.
Definition: concurrent_priority_queue.h:329
tbb::interface5::concurrent_priority_queue::cpq_operation
Definition: concurrent_priority_queue.h:335
tbb::interface5::concurrent_priority_queue::cpq_operation::elem
value_type * elem
Definition: concurrent_priority_queue.h:339
tbb::interface5::concurrent_priority_queue::cpq_operation::type
operation_type type
Definition: concurrent_priority_queue.h:337
tbb::interface5::concurrent_priority_queue::cpq_operation::cpq_operation
cpq_operation(operation_type t)
Definition: concurrent_priority_queue.h:344
tbb::interface5::concurrent_priority_queue::cpq_operation::cpq_operation
cpq_operation(const_reference e, operation_type t)
Definition: concurrent_priority_queue.h:342
tbb::interface5::concurrent_priority_queue::cpq_operation::sz
size_type sz
Definition: concurrent_priority_queue.h:340
tbb::interface5::concurrent_priority_queue::my_functor_t
Definition: concurrent_priority_queue.h:347
tbb::interface5::concurrent_priority_queue::my_functor_t::my_functor_t
my_functor_t(concurrent_priority_queue< T, Compare, A > *cpq_)
Definition: concurrent_priority_queue.h:351
tbb::interface5::concurrent_priority_queue::my_functor_t::cpq
concurrent_priority_queue< T, Compare, A > * cpq
Definition: concurrent_priority_queue.h:348
tbb::interface5::concurrent_priority_queue::my_functor_t::operator()
void operator()(cpq_operation *op_list)
Definition: concurrent_priority_queue.h:352
tbb::interface5::concurrent_priority_queue::my_functor_t::my_functor_t
my_functor_t()
Definition: concurrent_priority_queue.h:350
tbb::interface6::internal::aggregated_operation
aggregated_operation base class
Definition: _aggregator_impl.h:33
tbb::interface6::internal::aggregated_operation::next
Derived * next
Definition: _aggregator_impl.h:38
tbb::interface6::internal::aggregated_operation::status
uintptr_t status
Zero value means "wait" status, all other values are "user" specified values and are defined into the...
Definition: _aggregator_impl.h:36
tbb::interface6::internal::aggregator
Definition: _aggregator_impl.h:144
tbb::internal::bool_constant
Definition: tbb_stddef.h:486

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.