cds  2.2.0
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 >:
cds::intrusive::MSPriorityQueue< T, Traits > cds::bounded_container

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

Bar bar;
myQueue.push_with( [&bar]( Foo& dest ) { dest = bar; } );

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:40 by Doxygen 1.8.12