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

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

#include <cds/intrusive/msqueue.h>

Data Structures
struct	rebind
	Rebind template arguments. More...

Public Types
typedef T	value_type
	type of value stored in the queue
typedef options::hook	hook
	hook type
typedef hook::node_type	node_type
	node type
typedef options::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, options::link_checker >::type	link_checker
	link checker
typedef GC	gc
	Garbage collector.
typedef options::back_off	back_off
	back-off strategy
typedef options::item_counter	item_counter
	Item counting policy used.
typedef options::stat	stat
	Internal statistics policy used.
typedef options::memory_model	memory_model
	Memory ordering. See cds::opt::memory_model option.

Public Member Functions
	MSQueue ()
	Initializes empty queue.
	~MSQueue ()
	Destructor clears the queue.
size_t	size () const
	Returns queue's item count.
const stat &	statistics () const
	Returns reference to internal statistics.
bool	enqueue (value_type &val)
	Enqueues val value into the queue.
value_type *	dequeue ()
	Dequeues a value from the queue.
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.

Detailed Description

template<typename GC, typename T, typename... Options>
class cds::intrusive::MSQueue< GC, T, Options >

Michael & Scott's lock-free queue (intrusive variant)

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

Source:

[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::HRC, gc::PTB
• T - type to be stored in the queue, should be convertible to single_link::node
• Options - options

Type of node: single_link::node

Options are:

• opt::hook - hook used. Possible values are: single_link::base_hook, single_link::member_hook, single_link::traits_hook. If the option is not specified, single_link::base_hook<> is used. For Gidenstam's gc::HRC, only single_link::base_hook is supported.
• opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used.
• opt::disposer - the functor used for dispose removed items. Default is opt::v::empty_disposer. This option is used in dequeue function.
• opt::link_checker - the type of node's link fields checking. Default is opt::debug_check_link Note: for gc::HRC garbage collector, link checking policy is always selected as opt::always_check_link.
• opt::item_counter - the type of item counting feature. Default is atomicity::empty_item_counter (no item counting feature)
• opt::stat - the type to gather internal statistics. Possible option value are: queue_stat, queue_dummy_stat, user-provided class that supports queue_stat interface. Default is queue_dummy_stat.
• opt::alignment - the alignment for internal queue data. Default is opt::cache_line_alignment
• opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default) or opt::v::sequential_consistent (sequentially consisnent memory model).

Garbage collecting schema GC must be consistent with the single_link::node GC.

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 doc 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::single_link::node< hp_gc >
{
    // Your data
    ...
};

// Disposer for Foo struct just deletes the object passed in
struct fooDisposer {
    void operator()( Foo * p )
    {
        delete p    ;
    }
};

typedef ci::MSQueue< hp_gc,
    Foo
    ,ci::opt::hook<
        ci::single_link::base_hook< ci::opt::gc<hp_gc> >
    >
    ,ci::opt::disposer< fooDisposer >
> fooQueue  ;

// MSQueue with Hazard Pointer garbage collector,
// member hook + item disposer + item counter,
// without alignment of internal queue data:
struct Bar
{
    // Your data
    ...
    ci::single_link::node< hp_gc > hMember ;
};

typedef ci::MSQueue< hp_gc,
    Foo
    ,ci::opt::hook<
        ci::single_link::member_hook<
            offsetof(Bar, hMember)
            ,ci::opt::gc<hp_gc>
        >
    >
    ,ci::opt::disposer< fooDisposer >
    ,cds::opt::item_counter< cds::atomicity::item_counter >
    ,cds::opt::alignment< cds::opt::no_special_alignment >
> barQueue  ;

Constructor & Destructor Documentation

template<typename GC, typename T, typename... Options>

cds::intrusive::MSQueue< GC, T, Options >::~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

template<typename GC, typename T, typename... Options>

void cds::intrusive::MSQueue< GC, T, Options >::clear ( )

inline

Clear the queue.

The function repeatedly calls dequeue until it returns NULL. The disposer defined in template Options is called for each item that can be safely disposed.

template<typename GC, typename T, typename... Options>

value_type* cds::intrusive::MSQueue< GC, T, Options >::dequeue ( )

inline

Dequeues a value from the queue.

If the queue is empty the function returns NULL.

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 may be deleted only in disposer call.

template<typename GC, typename T, typename... Options>

bool cds::intrusive::MSQueue< GC, T, Options >::enqueue ( value_type &  val )

inline

Enqueues val value into the queue.

The function always returns true.

template<typename GC, typename T, typename... Options>

size_t cds::intrusive::MSQueue< GC, T, Options >::size ( ) const

inline

Returns queue's item count.

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

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