cds::container::MSPriorityQueue< T, Traits > Class Template Reference

Michael & Scott array-based lock-based concurrent priority queue heap. More...

#include <cds/container/mspriority_queue.h>

Inheritance diagram for cds::container::MSPriorityQueue< T, Traits >:

Public Types
typedef T	value_type
	Value type stored in the queue.
typedef Traits	traits
	Traits template parameter.
typedef base_class::key_comparator	key_comparator
	priority comparing functor based on opt::compare and opt::less option setter.
typedef base_class::lock_type	lock_type
	heap's size lock type
typedef base_class::back_off	back_off
	Back-off strategy.
typedef traits::stat	stat
	internal statistics type, see intrusive::mspriority_queue::traits::stat
typedef base_class::item_counter	item_counter
	Item counter type.
typedef traits::allocator::template rebind< value_type >::other	allocator_type
	Value allocator.
typedef traits::move_policy	move_policy
	Move policy for type T.

Public Member Functions
	MSPriorityQueue (size_t nCapacity)
	Constructs empty priority queue. More...
	~MSPriorityQueue ()
	Clears priority queue and destructs the object.
bool	push (value_type const &val)
	Inserts an item into priority queue. More...
template<typename Func >
bool	push_with (Func f)
	Inserts an item into the queue using a functor. More...
template<typename... Args>
bool	emplace (Args &&... args)
	Inserts a item into priority queue. More...
bool	pop (value_type &dest)
	Extracts item with high priority. More...
template<typename Func >
bool	pop_with (Func f)
	Extracts an item with high priority. More...
void	clear ()
	Clears the queue (not atomic) More...
template<typename Func >
void	clear_with (Func f)
	Clears the queue (not atomic) More...
bool	empty () const
	Checks is the priority queue is empty.
bool	full () const
	Checks if the priority queue is full.
size_t	size () const
	Returns current size of priority queue.
size_t	capacity () const
	Return capacity of the priority queue.
stat const &	statistics () const
	Returns const reference to internal statistics.

Additional Inherited Members
Protected Types inherited from cds::intrusive::MSPriorityQueue< T, Traits >
typedef T	value_type
	Value type stored in the queue.
typedef Traits	traits
	Traits template parameter.
typedef implementation_defined	key_comparator
	priority comparing functor based on opt::compare and opt::less option setter.
typedef traits::lock_type	lock_type
	heap's size lock type
typedef traits::back_off	back_off
	Back-off strategy.
typedef traits::stat	stat
	internal statistics type, see mspriority_queue::traits::stat
typedef cds::bitop::bit_reverse_counter	item_counter
	Item counter type.
typedef traits::buffer::template rebind< node >::other	buffer_type
	Heap array buffer type.
Protected Member Functions inherited from cds::intrusive::MSPriorityQueue< T, Traits >
	MSPriorityQueue (size_t nCapacity)
	Constructs empty priority queue. More...
	~MSPriorityQueue ()
	Clears priority queue and destructs the object.
bool	push (value_type &val)
	Inserts a item into priority queue. More...
value_type *	pop ()
	Extracts item with high priority. More...
void	clear ()
	Clears the queue (not atomic) More...
template<typename Func >
void	clear_with (Func f)
	Clears the queue (not atomic) More...
bool	empty () const
	Checks is the priority queue is empty.
bool	full () const
	Checks if the priority queue is full.
size_t	size () const
	Returns current size of priority queue.
size_t	capacity () const
	Return capacity of the priority queue.
stat const &	statistics () const
	Returns const reference to internal statistics.
Protected Attributes inherited from cds::intrusive::MSPriorityQueue< T, Traits >
item_counter	m_ItemCounter
	Item counter.
lock_type	m_Lock
	Heap's size lock.
buffer_type	m_Heap
	Heap array.
stat	m_Stat
	internal statistics accumulator

Detailed Description

template<typename T, class Traits = mspriority_queue::traits>
class cds::container::MSPriorityQueue< T, Traits >

Michael & Scott array-based lock-based concurrent priority queue heap.

Source:

• [1996] G.Hunt, M.Michael, S. Parthasarathy, M.Scott "An efficient algorithm for concurrent priority queue heaps"

MSPriorityQueue augments the standard array-based heap data structure with a mutual-exclusion lock on the heap's size and locks on each node in the heap. Each node also has a tag that indicates whether it is empty, valid, or in a transient state due to an update to the heap by an inserting thread. The algorithm allows concurrent insertions and deletions in opposite directions, without risking deadlock and without the need for special server threads. It also uses a "bit-reversal" technique to scatter accesses across the fringe of the tree to reduce contention. On large heaps the algorithm achieves significant performance improvements over serialized single-lock algorithm, for various insertion/deletion workloads. For small heaps it still performs well, but not as well as single-lock algorithm.

Template parameters:

• T - type to be stored in the list. The priority is a part of T type.
• Traits - the traits. See mspriority_queue::traits for explanation. It is possible to declare option-based queue with mspriority_queue::make_traits metafunction instead of Traits template argument.

Constructor & Destructor Documentation

MSPriorityQueue()

template<typename T , class Traits = mspriority_queue::traits>

cds::container::MSPriorityQueue< T, Traits >::MSPriorityQueue ( size_t  nCapacity )

inline

Constructs empty priority queue.

For cds::opt::v::initialized_static_buffer the nCapacity parameter is ignored.

Member Function Documentation

clear()

template<typename T , class Traits = mspriority_queue::traits>

void cds::container::MSPriorityQueue< T, Traits >::clear ( )

inline

Clears the queue (not atomic)

This function is not atomic, but thread-safe

clear_with()

template<typename T , class Traits = mspriority_queue::traits>

template<typename Func >

void cds::container::MSPriorityQueue< T, Traits >::clear_with ( Func  f )

inline

Clears the queue (not atomic)

This function is not atomic, but thread-safe.

For each item removed the functor f is called. Func interface is:

struct clear_functor
{
    void operator()( value_type& item );
};

emplace()

template<typename T , class Traits = mspriority_queue::traits>

template<typename... Args>

bool cds::container::MSPriorityQueue< T, Traits >::emplace ( Args &&...  args )

inline

Inserts a item into priority queue.

If the priority queue is full, the function returns false, no item has been added. Otherwise, the function inserts a new item created from args arguments into the heap and returns true.

pop()

template<typename T , class Traits = mspriority_queue::traits>

bool cds::container::MSPriorityQueue< T, Traits >::pop ( value_type &  dest )

inline

Extracts item with high priority.

If the priority queue is empty, the function returns false. Otherwise, it returns true and dest contains the copy of extracted item. The item is deleted from the heap.

The function uses move_policy to move extracted value from the heap's top to dest.

The function is equivalent of such call:

pop_with( dest, [&dest]( value_type& src ) { move_policy()(dest, src); } );

pop_with()

template<typename T , class Traits = mspriority_queue::traits>

template<typename Func >

bool cds::container::MSPriorityQueue< T, Traits >::pop_with ( Func  f )

inline

Extracts an item with high priority.

If the priority queue is empty, the function returns false. Otherwise, it returns true and dest contains the copy of extracted item. The item is deleted from the heap.

Func is a functor called to copy popped value. The functor takes one argument - a reference to removed node:

cds:container::MSPriorityQueue< Foo > myQueue;
Bar bar;
myQueue.pop_with( [&bar]( Foo& src ) { bar = std::move( src );});

push()

template<typename T , class Traits = mspriority_queue::traits>

bool cds::container::MSPriorityQueue< T, Traits >::push ( value_type const &  val )

inline

Inserts an item into priority queue.

If the priority queue is full, the function returns false, no item has been added. Otherwise, the function inserts the copy of val into the heap and returns true.

The function use copy constructor to create new heap item from val.

push_with()

template<typename T , class Traits = mspriority_queue::traits>

template<typename Func >

bool cds::container::MSPriorityQueue< T, Traits >::push_with ( Func  f )

inline

Inserts an item into the queue using a functor.

Func is a functor called to create node. The functor f takes one argument - a reference to a new node of type value_type :

cds::container::MSPriorityQueue< Foo > myQueue;
Bar bar;
myQueue.push_with( [&bar]( Foo& dest ) { dest = bar; } );

---

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

• cds/container/mspriority_queue.h