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

Data Structures

struct  rebind
 Rebind template arguments. More...
 

Public Member Functions

value_typedequeue ()
 Dequeues a value from the queue. More...
 
value_typepop ()
 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_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.
 

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;
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 2.3.1 Developed by Maxim Khizhinsky aka khizmax 2007 - 2017
Autogenerated Fri Sep 1 2017 08:47:22 by Doxygen 1.8.13