tbb::interface5::concurrent_priority_queue< T, Compare, A > Class Template Reference

Concurrent priority queue. More...

#include <concurrent_priority_queue.h>

Inheritance diagram for tbb::interface5::concurrent_priority_queue< T, Compare, A >:

Collaboration diagram for tbb::interface5::concurrent_priority_queue< T, Compare, A >:

Classes
class	cpq_operation
class	my_functor_t

Public Types
typedef T	value_type
	Element type in the queue. More...
typedef T &	reference
	Reference type. More...
typedef const T &	const_reference
	Const reference type. More...
typedef size_t	size_type
	Integral type for representing size of the queue. More...
typedef ptrdiff_t	difference_type
	Difference type for iterator. More...
typedef A	allocator_type
	Allocator type. More...

Public Member Functions
	concurrent_priority_queue (const allocator_type &a=allocator_type())
	Constructs a new concurrent_priority_queue with default capacity. More...
	concurrent_priority_queue (size_type init_capacity, const allocator_type &a=allocator_type())
	Constructs a new concurrent_priority_queue with init_sz capacity. More...
template<typename InputIterator >
	concurrent_priority_queue (InputIterator begin, InputIterator end, const allocator_type &a=allocator_type())
	[begin,end) constructor More...
	concurrent_priority_queue (std::initializer_list< T > init_list, const allocator_type &a=allocator_type())
	Constructor from std::initializer_list. More...
	concurrent_priority_queue (const concurrent_priority_queue &src)
	Copy constructor. More...
	concurrent_priority_queue (const concurrent_priority_queue &src, const allocator_type &a)
	Copy constructor with specific allocator. More...
concurrent_priority_queue &	operator= (const concurrent_priority_queue &src)
	Assignment operator. More...
	concurrent_priority_queue (concurrent_priority_queue &&src)
	Move constructor. More...
	concurrent_priority_queue (concurrent_priority_queue &&src, const allocator_type &a)
	Move constructor with specific allocator. More...
concurrent_priority_queue &	operator= (concurrent_priority_queue &&src)
	Move assignment operator. More...
template<typename InputIterator >
void	assign (InputIterator begin, InputIterator end)
	Assign the queue from [begin,end) range, not thread-safe. More...
void	assign (std::initializer_list< T > il)
	Assign the queue from std::initializer_list, not thread-safe. More...
concurrent_priority_queue &	operator= (std::initializer_list< T > il)
	Assign from std::initializer_list, not thread-safe. More...
bool	empty () const
	Returns true if empty, false otherwise. More...
size_type	size () const
	Returns the current number of elements contained in the queue. More...
void	push (const_reference elem)
	Pushes elem onto the queue, increasing capacity of queue if necessary. More...
void	push (value_type &&elem)
	Pushes elem onto the queue, increasing capacity of queue if necessary. More...
template<typename... Args>
void	emplace (Args &&... args)
	Constructs a new element using args as the arguments for its construction and pushes it onto the queue */. More...
bool	try_pop (reference elem)
	Gets a reference to and removes highest priority element. More...
void	clear ()
	Clear the queue; not thread-safe. More...
void	swap (concurrent_priority_queue &q)
	Swap this queue with another; not thread-safe. More...
allocator_type	get_allocator () const
	Return allocator object. More...

Private Types
enum	operation_type { INVALID_OP, PUSH_OP, POP_OP, PUSH_RVALUE_OP }
enum	operation_status { WAIT =0, SUCCEEDED, FAILED }
typedef tbb::internal::aggregator< my_functor_t, cpq_operation >	aggregator_t
typedef std::vector< value_type, allocator_type >	vector_t
	Storage for the heap of elements in queue, plus unheapified elements. More...

Private Member Functions
void	handle_operations (cpq_operation *op_list)
void	heapify ()
	Merge unsorted elements into heap. More...
void	reheap ()
	Re-heapify after an extraction. More...
void	push_back_helper (const T &t, tbb::internal::true_type)
void	push_back_helper (const T &, tbb::internal::false_type)

Private Attributes
aggregator_t	my_aggregator
char	padding1 [NFS_MaxLineSize - sizeof(aggregator_t)]
	Padding added to avoid false sharing. More...
size_type	mark
	The point at which unsorted elements begin. More...
__TBB_atomic size_type	my_size
Compare	compare
char	padding2 [NFS_MaxLineSize -(2 *sizeof(size_type)) - sizeof(Compare)]
	Padding added to avoid false sharing. More...
vector_t	data

Detailed Description

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>
class tbb::interface5::concurrent_priority_queue< T, Compare, A >

Concurrent priority queue.

Definition at line 67 of file concurrent_priority_queue.h.

Member Typedef Documentation

aggregator_t

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

typedef tbb::internal::aggregator< my_functor_t, cpq_operation > tbb::interface5::concurrent_priority_queue< T, Compare, A >::aggregator_t

private

Definition at line 323 of file concurrent_priority_queue.h.

allocator_type

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

typedef A tbb::interface5::concurrent_priority_queue< T, Compare, A >::allocator_type

Allocator type.

Definition at line 85 of file concurrent_priority_queue.h.

const_reference

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

typedef const T& tbb::interface5::concurrent_priority_queue< T, Compare, A >::const_reference

Const reference type.

Definition at line 76 of file concurrent_priority_queue.h.

difference_type

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

typedef ptrdiff_t tbb::interface5::concurrent_priority_queue< T, Compare, A >::difference_type

Difference type for iterator.

Definition at line 82 of file concurrent_priority_queue.h.

reference

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

typedef T& tbb::interface5::concurrent_priority_queue< T, Compare, A >::reference

Reference type.

Definition at line 73 of file concurrent_priority_queue.h.

size_type

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

typedef size_t tbb::interface5::concurrent_priority_queue< T, Compare, A >::size_type

Integral type for representing size of the queue.

Definition at line 79 of file concurrent_priority_queue.h.

value_type

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

typedef T tbb::interface5::concurrent_priority_queue< T, Compare, A >::value_type

Element type in the queue.

Definition at line 70 of file concurrent_priority_queue.h.

vector_t

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

typedef std::vector<value_type, allocator_type> tbb::interface5::concurrent_priority_queue< T, Compare, A >::vector_t

private

Storage for the heap of elements in queue, plus unheapified elements.

data has the following structure:

binary unheapified heap elements ____|_______|____ | | | v v v [_|...|_|_|...|_| |...| ] 0 ^ ^ ^ | | |__capacity | |__my_size |__mark

Thus, data stores the binary heap starting at position 0 through mark-1 (it may be empty). Then there are 0 or more elements that have not yet been inserted into the heap, in positions mark through my_size-1.

Definition at line 351 of file concurrent_priority_queue.h.

Member Enumeration Documentation

operation_status

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

enum tbb::interface5::concurrent_priority_queue::operation_status

private

Enumerator
WAIT
SUCCEEDED
FAILED

Definition at line 299 of file concurrent_priority_queue.h.

{ WAIT=0, SUCCEEDED, FAILED };

operation_type

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

enum tbb::interface5::concurrent_priority_queue::operation_type

private

Enumerator
INVALID_OP
PUSH_OP
POP_OP
PUSH_RVALUE_OP

Definition at line 298 of file concurrent_priority_queue.h.

{INVALID_OP, PUSH_OP, POP_OP, PUSH_RVALUE_OP};

Constructor & Destructor Documentation

concurrent_priority_queue() [1/8]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

tbb::interface5::concurrent_priority_queue< T, Compare, A >::concurrent_priority_queue ( const allocator_type &  a = allocator_type() )

inlineexplicit

Constructs a new concurrent_priority_queue with default capacity.

Definition at line 88 of file concurrent_priority_queue.h.

                                                                                   : mark(0), my_size(0), data(a)
    {
        my_aggregator.initialize_handler(my_functor_t(this));
    }

concurrent_priority_queue() [2/8]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

tbb::interface5::concurrent_priority_queue< T, Compare, A >::concurrent_priority_queue ( size_type  init_capacity, const allocator_type &  a = allocator_type()  )

inlineexplicit

Constructs a new concurrent_priority_queue with init_sz capacity.

Definition at line 94 of file concurrent_priority_queue.h.

                                                                                                            :
        mark(0), my_size(0), data(a)
    {
        data.reserve(init_capacity);
        my_aggregator.initialize_handler(my_functor_t(this));
    }

concurrent_priority_queue() [3/8]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

template<typename InputIterator >

tbb::interface5::concurrent_priority_queue< T, Compare, A >::concurrent_priority_queue ( InputIterator  begin, InputIterator  end, const allocator_type &  a = allocator_type()  )

inline

[begin,end) constructor

Definition at line 103 of file concurrent_priority_queue.h.

                                                                                                                  :
        mark(0), data(begin, end, a)
    {
        my_aggregator.initialize_handler(my_functor_t(this));
        heapify();
        my_size = data.size();
    }

concurrent_priority_queue() [4/8]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

tbb::interface5::concurrent_priority_queue< T, Compare, A >::concurrent_priority_queue ( std::initializer_list< T >  init_list, const allocator_type &  a = allocator_type()  )

inline

Constructor from std::initializer_list.

Definition at line 113 of file concurrent_priority_queue.h.

                                                                                                            :
        mark(0),data(init_list.begin(), init_list.end(), a)
    {
        my_aggregator.initialize_handler(my_functor_t(this));
        heapify();
        my_size = data.size();
    }

concurrent_priority_queue() [5/8]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

tbb::interface5::concurrent_priority_queue< T, Compare, A >::concurrent_priority_queue ( const concurrent_priority_queue< T, Compare, A > &  src )

inline

Copy constructor.

This operation is unsafe if there are pending concurrent operations on the src queue.

Definition at line 124 of file concurrent_priority_queue.h.

                                                                    : 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() [6/8]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

tbb::interface5::concurrent_priority_queue< T, Compare, A >::concurrent_priority_queue ( const concurrent_priority_queue< T, Compare, A > &  src, const allocator_type &  a  )

inline

Copy constructor with specific allocator.

This operation is unsafe if there are pending concurrent operations on the src queue.

Definition at line 133 of file concurrent_priority_queue.h.

                                                                                             : 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() [7/8]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

tbb::interface5::concurrent_priority_queue< T, Compare, A >::concurrent_priority_queue ( concurrent_priority_queue< T, Compare, A > &&  src )

inline

Move constructor.

This operation is unsafe if there are pending concurrent operations on the src queue.

Definition at line 154 of file concurrent_priority_queue.h.

                                                               : mark(src.mark),
        my_size(src.my_size), data(std::move(src.data))
    {
        my_aggregator.initialize_handler(my_functor_t(this));
    }

concurrent_priority_queue() [8/8]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

tbb::interface5::concurrent_priority_queue< T, Compare, A >::concurrent_priority_queue ( concurrent_priority_queue< T, Compare, A > &&  src, const allocator_type &  a  )

inline

Move constructor with specific allocator.

This operation is unsafe if there are pending concurrent operations on the src queue.

__TBB_ALLOCATOR_TRAITS_PRESENT

Definition at line 162 of file concurrent_priority_queue.h.

                                                                                        : 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 
    }

Member Function Documentation

assign() [1/2]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

template<typename InputIterator >

void tbb::interface5::concurrent_priority_queue< T, Compare, A >::assign ( InputIterator  begin, InputIterator  end  )

inline

Assign the queue from [begin,end) range, not thread-safe.

Definition at line 204 of file concurrent_priority_queue.h.

                                                        {
        vector_t(begin, end, data.get_allocator()).swap(data);
        mark = 0;
        my_size = data.size();
        heapify();
    }

assign() [2/2]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

void tbb::interface5::concurrent_priority_queue< T, Compare, A >::assign ( std::initializer_list< T >  il )

inline

Assign the queue from std::initializer_list, not thread-safe.

Definition at line 213 of file concurrent_priority_queue.h.

{ this->assign(il.begin(), il.end()); }

clear()

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

void tbb::interface5::concurrent_priority_queue< T, Compare, A >::clear ( )

inline

Clear the queue; not thread-safe.

This operation is unsafe if there are pending concurrent operations on the queue. Resets size, effectively emptying queue; does not free space. May not clear elements added in pending operations.

Definition at line 279 of file concurrent_priority_queue.h.

                 {
        data.clear();
        mark = 0;
        my_size = 0;
    }

emplace()

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

template<typename... Args>

void tbb::interface5::concurrent_priority_queue< T, Compare, A >::emplace ( Args &&...  args )

inline

Constructs a new element using args as the arguments for its construction and pushes it onto the queue */.

This operation can be safely used concurrently with other push, try_pop or emplace operations.

Definition at line 258 of file concurrent_priority_queue.h.

                                 {
        push(value_type(std::forward<Args>(args)...));
    }

empty()

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

bool tbb::interface5::concurrent_priority_queue< T, Compare, A >::empty ( ) const

inline

Returns true if empty, false otherwise.

Returned value may not reflect results of pending operations. This operation reads shared data and will trigger a race condition.

Definition at line 225 of file concurrent_priority_queue.h.

{ return size()==0; }

get_allocator()

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

allocator_type tbb::interface5::concurrent_priority_queue< T, Compare, A >::get_allocator ( ) const

inline

Return allocator object.

Definition at line 295 of file concurrent_priority_queue.h.

{ return data.get_allocator(); }

handle_operations()

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

void tbb::interface5::concurrent_priority_queue< T, Compare, A >::handle_operations ( cpq_operation *  op_list )

inlineprivate

Definition at line 354 of file concurrent_priority_queue.h.

Referenced by tbb::interface5::concurrent_priority_queue< T, Compare, A >::my_functor_t::operator()().

                                                   {
        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);
    }

Here is the caller graph for this function:

heapify()

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

void tbb::interface5::concurrent_priority_queue< T, Compare, A >::heapify ( )

inlineprivate

Merge unsorted elements into heap.

Definition at line 438 of file concurrent_priority_queue.h.

                   {
        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);
        }
    }

operator=() [1/3]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

concurrent_priority_queue& tbb::interface5::concurrent_priority_queue< T, Compare, A >::operator= ( const concurrent_priority_queue< T, Compare, A > &  src )

inline

Assignment operator.

This operation is unsafe if there are pending concurrent operations on the src queue.

Definition at line 142 of file concurrent_priority_queue.h.

                                                                               {
        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;
    }

operator=() [2/3]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

concurrent_priority_queue& tbb::interface5::concurrent_priority_queue< T, Compare, A >::operator= ( concurrent_priority_queue< T, Compare, A > &&  src )

inline

Move assignment operator.

This operation is unsafe if there are pending concurrent operations on the src queue.

__TBB_ALLOCATOR_TRAITS_PRESENT

Definition at line 185 of file concurrent_priority_queue.h.

                                                                           {
        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;
    }

operator=() [3/3]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

concurrent_priority_queue& tbb::interface5::concurrent_priority_queue< T, Compare, A >::operator= ( std::initializer_list< T >  il )

inline

Assign from std::initializer_list, not thread-safe.

Definition at line 216 of file concurrent_priority_queue.h.

                                                                    {
        this->assign(il.begin(), il.end());
        return *this;
    }

push() [1/2]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

void tbb::interface5::concurrent_priority_queue< T, Compare, A >::push ( const_reference  elem )

inline

Pushes elem onto the queue, increasing capacity of queue if necessary.

This operation can be safely used concurrently with other push, try_pop or emplace operations.

Definition at line 234 of file concurrent_priority_queue.h.

Referenced by tbb::flow::interface10::internal::spawn_in_graph_arena().

                                    {
#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);
    }

Here is the caller graph for this function:

push() [2/2]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

void tbb::interface5::concurrent_priority_queue< T, Compare, A >::push ( value_type &&  elem )

inline

Pushes elem onto the queue, increasing capacity of queue if necessary.

This operation can be safely used concurrently with other push, try_pop or emplace operations.

Definition at line 247 of file concurrent_priority_queue.h.

                                 {
        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);
    }

push_back_helper() [1/2]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

void tbb::interface5::concurrent_priority_queue< T, Compare, A >::push_back_helper ( const T &  t, tbb::internal::true_type    )

inlineprivate

Definition at line 475 of file concurrent_priority_queue.h.

                                                            {
        data.push_back(t);
    }

push_back_helper() [2/2]

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

void tbb::interface5::concurrent_priority_queue< T, Compare, A >::push_back_helper ( const T &  , tbb::internal::false_type    )

inlineprivate

Definition at line 479 of file concurrent_priority_queue.h.

                                                           {
        __TBB_ASSERT( false, "The type is not copy constructible. Copying push operation is impossible." );
    }

reheap()

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

void tbb::interface5::concurrent_priority_queue< T, Compare, A >::reheap ( )

inlineprivate

Re-heapify after an extraction.

Re-heapify by pushing last element down the heap from the root.

Definition at line 456 of file concurrent_priority_queue.h.

                  {
        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();
    }

size()

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

size_type tbb::interface5::concurrent_priority_queue< T, Compare, A >::size ( ) const

inline

Returns the current number of elements contained in the queue.

Returned value may not reflect results of pending operations. This operation reads shared data and will trigger a race condition.

Definition at line 230 of file concurrent_priority_queue.h.

{ return __TBB_load_with_acquire(my_size); }

swap()

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

void tbb::interface5::concurrent_priority_queue< T, Compare, A >::swap ( concurrent_priority_queue< T, Compare, A > &  q )

inline

Swap this queue with another; not thread-safe.

This operation is unsafe if there are pending concurrent operations on the queue.

Definition at line 287 of file concurrent_priority_queue.h.

                                            {
        using std::swap;
        data.swap(q.data);
        swap(mark, q.mark);
        swap(my_size, q.my_size);
    }

try_pop()

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

bool tbb::interface5::concurrent_priority_queue< T, Compare, A >::try_pop ( reference  elem )

inline

Gets a reference to and removes highest priority element.

If a highest priority element was found, sets elem and returns true, otherwise returns false. This operation can be safely used concurrently with other push, try_pop or emplace operations.

Definition at line 268 of file concurrent_priority_queue.h.

                                 {
        cpq_operation op_data(POP_OP);
        op_data.elem = &elem;
        my_aggregator.execute(&op_data);
        return op_data.status==SUCCEEDED;
    }

Member Data Documentation

compare

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

Compare tbb::interface5::concurrent_priority_queue< T, Compare, A >::compare

private

Definition at line 330 of file concurrent_priority_queue.h.

data

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

vector_t tbb::interface5::concurrent_priority_queue< T, Compare, A >::data

private

Definition at line 352 of file concurrent_priority_queue.h.

Referenced by tbb::interface5::concurrent_priority_queue< graph_task *, graph_task_comparator >::operator=(), and tbb::interface5::concurrent_priority_queue< graph_task *, graph_task_comparator >::swap().

mark

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

size_type tbb::interface5::concurrent_priority_queue< T, Compare, A >::mark

private

The point at which unsorted elements begin.

Definition at line 328 of file concurrent_priority_queue.h.

Referenced by tbb::interface5::concurrent_priority_queue< graph_task *, graph_task_comparator >::operator=(), and tbb::interface5::concurrent_priority_queue< graph_task *, graph_task_comparator >::swap().

my_aggregator

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

aggregator_t tbb::interface5::concurrent_priority_queue< T, Compare, A >::my_aggregator

private

Definition at line 324 of file concurrent_priority_queue.h.

my_size

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

__TBB_atomic size_type tbb::interface5::concurrent_priority_queue< T, Compare, A >::my_size

private

Definition at line 329 of file concurrent_priority_queue.h.

Referenced by tbb::interface5::concurrent_priority_queue< graph_task *, graph_task_comparator >::operator=(), and tbb::interface5::concurrent_priority_queue< graph_task *, graph_task_comparator >::swap().

padding1

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

char tbb::interface5::concurrent_priority_queue< T, Compare, A >::padding1[NFS_MaxLineSize - sizeof(aggregator_t)]

private

Padding added to avoid false sharing.

Definition at line 326 of file concurrent_priority_queue.h.

padding2

template<typename T, typename Compare = std::less<T>, typename A = cache_aligned_allocator<T>>

char tbb::interface5::concurrent_priority_queue< T, Compare, A >::padding2[NFS_MaxLineSize -(2 *sizeof(size_type)) - sizeof(Compare)]

private

Padding added to avoid false sharing.

Definition at line 332 of file concurrent_priority_queue.h.

---

The documentation for this class was generated from the following file:

• concurrent_priority_queue.h