cds  2.2.0
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 >:
cds::bounded_container cds::container::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_typepop ()
 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:

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 2.2.0 Developed by Maxim Khizhinsky aka khizmax 2007 - 2017
Autogenerated Wed Jan 4 2017 08:49:51 by Doxygen 1.8.12