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

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

#include <cds/intrusive/mspriority_queue.h>

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

Public Types
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.

Public Member Functions
	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
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::intrusive::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 queue. The priority is a part of T type.
• Traits - type traits. See mspriority_queue::traits for explanation. It is possible to declare option-based queue with cds::container::mspriority_queue::make_traits metafunction instead of Traits template argument.

Constructor & Destructor Documentation

MSPriorityQueue()

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

cds::intrusive::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::intrusive::MSPriorityQueue< T, Traits >::clear ( )

inline

Clears the queue (not atomic)

This function is no atomic, but thread-safe

clear_with()

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

template<typename Func >

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

inline

Clears the queue (not atomic)

This function is no atomic, but thread-safe.

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

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

A lambda function or a function pointer can be used as f.

pop()

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

value_type* cds::intrusive::MSPriorityQueue< T, Traits >::pop ( )

inline

Extracts item with high priority.

If the priority queue is empty, the function returns nullptr. Otherwise, it returns the item extracted.

push()

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

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

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 the pointer to val into the heap and returns true.

The function does not make a copy of val.

---

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

• cds/intrusive/mspriority_queue.h