cds/intrusive/moir_queue.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_INTRUSIVE_MOIR_QUEUE_H
   4 #define __CDS_INTRUSIVE_MOIR_QUEUE_H
   5
   6 #include <cds/intrusive/msqueue.h>
   7
   8 namespace cds { namespace intrusive {
   9
  10     /// A variation of Michael & Scott's lock-free queue (intrusive variant)
  11     /** @ingroup cds_intrusive_queue
  12         This is slightly optimized Michael & Scott's queue algorithm that overloads \ref dequeue function.
  13
  14         Source:
  15             \li [2000] Simon Doherty, Lindsay Groves, Victor Luchangco, Mark Moir
  16                 "Formal Verification of a practical lock-free queue algorithm"
  17
  18         Cite from this work about difference from Michael & Scott algo:
  19         "Our algorithm differs from Michael and Scott\92s [MS98] in that we test whether \p Tail points to the header
  20         node only <b>after</b> \p Head has been updated, so a dequeuing process reads \p Tail only once. The dequeue in
  21         [MS98] performs this test before checking whether the next pointer in the dummy node is null, which
  22         means that it reads \p Tail every time a dequeuing process loops. Under high load, when operations retry
  23         frequently, our modification will reduce the number of accesses to global memory. This modification, however,
  24         introduces the possibility of \p Head and \p Tail \93crossing\94."
  25
  26         Type of node: \ref single_link::node
  27
  28         Explanation of template arguments see intrusive::MSQueue.
  29
  30         \par Examples
  31         \code
  32         #include <cds/intrusive/moir_queue.h>
  33         #include <cds/gc/hp.h>
  34
  35         namespace ci = cds::inrtusive;
  36         typedef cds::gc::HP hp_gc;
  37
  38         // MoirQueue with Hazard Pointer garbage collector, base hook + item disposer:
  39         struct Foo: public ci::single_link::node< hp_gc >
  40         {
  41             // Your data
  42             ...
  43         };
  44
  45         // Disposer for Foo struct just deletes the object passed in
  46         struct fooDisposer {
  47             void operator()( Foo * p )
  48             {
  49                 delete p;
  50             }
  51         };
  52
  53         typedef ci::MoirQueue<
  54             hp_gc
  55             ,Foo
  56             ,ci::opt::hook<
  57                 ci::single_link::base_hook< ci::opt::gc<hp_gc> >
  58             >
  59             ,ci::opt::disposer< fooDisposer >
  60         > fooQueue;
  61
  62         // MoirQueue with Hazard Pointer garbage collector,
  63         // member hook + item disposer + item counter,
  64         // without alignment of internal queue data:
  65         struct Bar
  66         {
  67             // Your data
  68             ...
  69             ci::single_link::node< hp_gc > hMember;
  70         };
  71
  72         typedef ci::MoirQueue<
  73             hp_gc
  74             ,Foo
  75             ,ci::opt::hook<
  76                 ci::single_link::member_hook<
  77                     offsetof(Bar, hMember)
  78                     ,ci::opt::gc<hp_gc>
  79                 >
  80             >
  81             ,ci::opt::disposer< fooDisposer >
  82             ,cds::opt::item_counter< cds::atomicity::item_counter >
  83             ,cds::opt::alignment< cds::opt::no_special_alignment >
  84         > barQueue;
  85
  86         \endcode
  87     */
  88     template <typename GC, typename T, typename... Options>
  89     class MoirQueue: public MSQueue< GC, T, Options... >
  90     {
  91         //@cond
  92         typedef MSQueue< GC, T, Options... > base_class;
  93         typedef typename base_class::node_type node_type;
  94         //@endcond
  95
  96     public:
  97         //@cond
  98         typedef typename base_class::value_type value_type;
  99         typedef typename base_class::back_off   back_off;
 100         typedef typename base_class::gc         gc;
 101         typedef typename base_class::node_traits node_traits;
 102         typedef typename base_class::memory_model   memory_model;
 103         //@endcond
 104
 105         /// Rebind template arguments
 106         template <typename GC2, typename T2, typename... Options2>
 107         struct rebind {
 108             typedef MoirQueue< GC2, T2, Options2...> other   ;   ///< Rebinding result
 109         };
 110
 111     protected:
 112         //@cond
 113         typedef typename base_class::dequeue_result dequeue_result;
 114         typedef typename base_class::node_to_value node_to_value;
 115
 116         bool do_dequeue( dequeue_result& res )
 117         {
 118             back_off bkoff;
 119
 120             node_type * pNext;
 121             node_type * h;
 122             while ( true ) {
 123                 h = res.guards.protect( 0, base_class::m_pHead, node_to_value() );
 124                 pNext = res.guards.protect( 1, h->m_pNext, node_to_value() );
 125
 126                 if ( pNext == nullptr )
 127                     return false    ;    // queue is empty
 128
 129                 if ( base_class::m_pHead.compare_exchange_strong( h, pNext, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
 130                     node_type * t = base_class::m_pTail.load(memory_model::memory_order_acquire);
 131                     if ( h == t )
 132                         base_class::m_pTail.compare_exchange_strong( t, pNext, memory_model::memory_order_release, atomics::memory_order_relaxed );
 133                     break;
 134                 }
 135
 136                 base_class::m_Stat.onDequeueRace();
 137                 bkoff();
 138             }
 139
 140             --base_class::m_ItemCounter;
 141             base_class::m_Stat.onDequeue();
 142
 143             res.pHead = h;
 144             res.pNext = pNext;
 145             return true;
 146         }
 147         //@endcond
 148
 149     public:
 150         /// Dequeues a value from the queue
 151         /** @anchor cds_intrusive_MoirQueue_dequeue
 152             See warning about item disposing in \ref MSQueue::dequeue.
 153         */
 154         value_type * dequeue()
 155         {
 156             dequeue_result res;
 157             if ( do_dequeue( res )) {
 158                 base_class::dispose_result( res );
 159                 return node_traits::to_value_ptr( *res.pNext );
 160             }
 161             return nullptr;
 162         }
 163
 164         /// Synonym for \ref cds_intrusive_MoirQueue_dequeue "dequeue" function
 165         value_type * pop()
 166         {
 167             return dequeue();
 168         }
 169     };
 170
 171 }} // namespace cds::intrusive
 172
 173 #endif // #ifndef __CDS_INTRUSIVE_MOIR_QUEUE_H