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

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

#include <cds/intrusive/moir_queue.h>

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

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

Public Member Functions
value_type *	dequeue ()
	Dequeues a value from the queue. More...
value_type *	pop ()
	Synonym for dequeue function.
Public Member Functions inherited from cds::intrusive::MSQueue< GC, T, Options... >
	MSQueue ()
	Initializes empty queue.
	~MSQueue ()
	Destructor clears the queue. More...
size_t	size () const
	Returns queue's item count. More...
const stat &	statistics () const
	Returns reference to internal statistics.
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...

Additional Inherited Members
Public Types inherited from cds::intrusive::MSQueue< GC, T, Options... >
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.

Detailed Description

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

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

This is slightly optimized Michael & Scott's queue algorithm that overloads dequeue function.

Source:

• [2000] Simon Doherty, Lindsay Groves, Victor Luchangco, Mark Moir "Formal Verification of a practical lock-free queue algorithm"

Cite from this work about difference from Michael & Scott algo: "Our algorithm differs from Michael and Scott’s [MS98] in that we test whether Tail points to the header node only after Head has been updated, so a dequeuing process reads Tail only once. The dequeue in [MS98] performs this test before checking whether the next pointer in the dummy node is null, which means that it reads Tail every time a dequeuing process loops. Under high load, when operations retry frequently, our modification will reduce the number of accesses to global memory. This modification, however, introduces the possibility of Head and Tail “crossing”."

Type of node: single_link::node

Explanation of template arguments see intrusive::MSQueue.

Examples

#include <cds/intrusive/moir_queue.h>
#include <cds/gc/hp.h>

namespace ci = cds::inrtusive ;
typedef cds::gc::HP hp_gc;

// MoirQueue 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::MoirQueue<
    hp_gc
    ,Foo
    ,ci::opt::hook<
        ci::single_link::base_hook< ci::opt::gc<hp_gc> >
    >
    ,ci::opt::disposer< fooDisposer >
> fooQueue  ;

// MoirQueue 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::MoirQueue<
    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  ;

Member Function Documentation

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

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

inline

Dequeues a value from the queue.

See warning about item disposing in MSQueue::dequeue.

---

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

• cds/intrusive/moir_queue.h