cds  2.3.1
cds::intrusive::MSQueue< GC, T, Traits > Class Template Reference

Michael & Scott's intrusive lock-free queue. More...

#include <cds/intrusive/msqueue.h>

Inheritance diagram for cds::intrusive::MSQueue< GC, T, Traits >:
cds::intrusive::MoirQueue< GC, T, Traits >

Data Structures

struct  rebind
 Rebind template arguments. More...
 

Public Types

typedef GC gc
 Garbage collector.
 
typedef T value_type
 type of value to be stored in the queue
 
typedef Traits traits
 Queue traits.
 
typedef traits::hook hook
 hook type
 
typedef hook::node_type node_type
 node type
 
typedef traits::disposer disposer
 disposer used
 
typedef get_node_traits< value_type, node_type, hook >::type node_traits
 node traits
 
typedef single_link::get_link_checker< node_type, traits::link_checker >::type link_checker
 link checker
 
typedef traits::back_off back_off
 back-off strategy
 
typedef traits::item_counter item_counter
 Item counter class.
 
typedef traits::stat stat
 Internal statistics.
 
typedef traits::memory_model memory_model
 Memory ordering. See cds::opt::memory_model option.
 

Public Member Functions

 MSQueue ()
 Initializes empty queue.
 
 ~MSQueue ()
 Destructor clears the queue. More...
 
bool enqueue (value_type &val)
 Enqueues val value into the queue. More...
 
value_typedequeue ()
 Dequeues a value from the queue. More...
 
bool push (value_type &val)
 Synonym for enqueue() function.
 
value_typepop ()
 Synonym for dequeue() function.
 
bool empty () const
 Checks if the queue is empty.
 
void clear ()
 Clear the queue. More...
 
size_t size () const
 Returns queue's item count. More...
 
stat const & statistics () const
 Returns reference to internal statistics.
 

Static Public Attributes

static constexpr const size_t c_nHazardPtrCount = 2
 Count of hazard pointer required for the algorithm.
 

Detailed Description

template<typename GC, typename T, typename Traits = msqueue::traits>
class cds::intrusive::MSQueue< GC, T, Traits >

Michael & Scott's intrusive lock-free queue.

Implementation of well-known Michael & Scott's queue algorithm:

  • [1998] Maged Michael, Michael Scott "Simple, fast, and practical non-blocking and blocking concurrent queue algorithms"

Template arguments:

About item disposing
The Michael & Scott's queue algo has a key feature: even if the queue is empty it contains one item that is "dummy" one from the standpoint of the algo. See dequeue() function for explanation.
Examples
#include <cds/intrusive/msqueue.h>
#include <cds/gc/hp.h>
namespace ci = cds::inrtusive;
typedef cds::gc::HP hp_gc;
// MSQueue with Hazard Pointer garbage collector, base hook + item disposer:
struct Foo: public ci::msqueue::node< hp_gc >
{
// Your data
...
};
// Disposer for Foo struct just deletes the object passed in
struct fooDisposer {
void operator()( Foo * p )
{
delete p;
}
};
// Declare traits for the queue
struct myTraits: public ci::msqueue::traits {
,ci::opt::hook<
ci::msqueue::base_hook< ci::opt::gc<hp_gc> >
>
,ci::opt::disposer< fooDisposer >
};
// At least, declare the queue type
typedef ci::MSQueue< hp_gc, Foo, myTraits > fooQueue;
// Example 2:
// MSQueue with Hazard Pointer garbage collector,
// member hook + item disposer + item counter,
// without padding of internal queue data
// Use msqueue::make_traits
struct Bar
{
// Your data
...
ci::msqueue::node< hp_gc > hMember;
};
typedef ci::MSQueue< hp_gc,
Foo,
typename ci::msqueue::make_traits<
ci::opt::hook<
ci::msqueue::member_hook<
offsetof(Bar, hMember)
,ci::opt::gc<hp_gc>
>
>
,ci::opt::disposer< fooDisposer >
>::type
> barQueue;

Constructor & Destructor Documentation

◆ ~MSQueue()

template<typename GC, typename T, typename Traits = msqueue::traits>
cds::intrusive::MSQueue< GC, T, Traits >::~MSQueue ( )
inline

Destructor clears the queue.

Since the Michael & Scott queue contains at least one item even if the queue is empty, the destructor may call item disposer.

Member Function Documentation

◆ clear()

template<typename GC, typename T, typename Traits = msqueue::traits>
void cds::intrusive::MSQueue< GC, T, Traits >::clear ( )
inline

Clear the queue.

The function repeatedly calls dequeue() until it returns nullptr. The disposer defined in template Traits is called for each item that can be safely disposed.

◆ dequeue()

template<typename GC, typename T, typename Traits = msqueue::traits>
value_type* cds::intrusive::MSQueue< GC, T, Traits >::dequeue ( )
inline

Dequeues a value from the queue.

If the queue is empty the function returns nullptr.

Warning
The queue algorithm has following feature: when dequeue() is called, the item returning is still queue's top, and previous top is disposed:
before dequeuing Dequeue after dequeuing
+------------------+ +------------------+
Top ->| Item 1 | -> Dispose Item 1 | Item 2 | <- Top
+------------------+ +------------------+
| Item 2 | -> Return Item 2 | ... |
+------------------+
| ... |

dequeue() function returns Item 2, that becomes new top of queue, and calls the disposer for Item 1, that was queue's top on function entry. Thus, you cannot manually delete item returned because it is still included in item sequence and it has valuable link field that must not be zeroed. The item should be deleted only in garbage collector retire cycle using the disposer.

◆ enqueue()

template<typename GC, typename T, typename Traits = msqueue::traits>
bool cds::intrusive::MSQueue< GC, T, Traits >::enqueue ( value_type val)
inline

Enqueues val value into the queue.

The function always returns true.

◆ size()

template<typename GC, typename T, typename Traits = msqueue::traits>
size_t cds::intrusive::MSQueue< GC, T, Traits >::size ( ) const
inline

Returns queue's item count.

The value returned depends on msqueue::traits::item_counter. For atomicity::empty_item_counter, this function always returns 0.

Note
Even if you use real item counter and it returns 0, this fact is not mean that the queue is empty. To check queue emptyness use empty() method.

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

cds 2.3.1 Developed by Maxim Khizhinsky aka khizmax 2007 - 2017
Autogenerated Fri Sep 1 2017 08:47:22 by Doxygen 1.8.13