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

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_type *	dequeue ()
	Dequeues a value from the queue. More...
bool	push (value_type &val)
	Synonym for enqueue() function.
value_type *	pop ()
	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:

• GC - garbage collector type: gc::HP, gc::DHP
• T - type of value to be stored in the queue. A value of type T must be derived from msqueue::node for msqueue::base_hook, or it should have a member of type msqueue::node for msqueue::member_hook, or it should be convertible to msqueue::node for msqueue::traits_hook.
• Traits - queue traits, default is msqueue::traits. You can use msqueue::make_traits metafunction to make your traits or just derive your traits from msqueue::traits:

  struct myTraits: public cds::intrusive::msqueue::traits {
      typedef cds::intrusive::msqueue::stat<> stat;
      typedef cds::atomicity::item_counter    item_counter;
  };
  typedef cds::intrusive::MSQueue< cds::gc::HP, Foo, myTraits > myQueue;
  
  // Equivalent make_traits example:
  typedef cds::intrusive::MSQueue< cds::gc::HP, Foo,
      typename cds::intrusive::msqueue::make_traits<
          cds::opt::stat< cds::intrusive::msqueue::stat<> >,
          cds::opt::item_counter< cds::atomicity::item_counter >
      >::type
  > myQueue;

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 >
        ,cds::opt::item_counter< cds::atomicity::item_counter >
        ,cds::opt::padding< cds::opt::no_special_padding >
    >::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/intrusive/msqueue.h