cds::intrusive::MoirQueue< GC, T, Traits > 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, Traits >:

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, Traits >
	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.

Additional Inherited Members
Public Types inherited from cds::intrusive::MSQueue< GC, T, Traits >
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.
Static Public Attributes inherited from cds::intrusive::MSQueue< GC, T, Traits >
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 = cds::intrusive::msqueue::traits>
class cds::intrusive::MoirQueue< GC, T, Traits >

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'."

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::msqueue::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
    typename ci::msqueue::make_traits<
        ,ci::opt::hook<
            ci::msqueue::base_hook< ci::opt::gc<hp_gc> >
        >
        ,ci::opt::disposer< fooDisposer >
    >::type
> fooQueue;

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

struct barQueueTraits: public ci::msqueue::traits
{
    typedef ci::msqueue::member_hook< offsetof(Bar, hMember), ,ci::opt::gc<hp_gc> > hook;
    typedef fooDisposer disposer;
    typedef cds::atomicity::item_counter item_counter;
    enum { padding = cds::opt::no_special_padding };
};
typedef ci::MoirQueue< hp_gc, Bar, barQueueTraits > barQueue;

Member Function Documentation

dequeue()

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

value_type* cds::intrusive::MoirQueue< GC, T, Traits >::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