2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_INTRUSIVE_MOIR_QUEUE_H
32 #define CDSLIB_INTRUSIVE_MOIR_QUEUE_H
34 #include <cds/intrusive/msqueue.h>
36 namespace cds { namespace intrusive {
38 /// A variation of Michael & Scott's lock-free queue (intrusive variant)
39 /** @ingroup cds_intrusive_queue
40 This is slightly optimized Michael & Scott's queue algorithm that overloads \ref dequeue function.
43 - [2000] Simon Doherty, Lindsay Groves, Victor Luchangco, Mark Moir
44 "Formal Verification of a practical lock-free queue algorithm"
46 Cite from this work about difference from Michael & Scott algo:
47 "Our algorithm differs from Michael and Scott's [MS98] in that we test whether \p Tail points to the header
48 node only <b>after</b> \p Head has been updated, so a dequeuing process reads \p Tail only once. The dequeue in
49 [MS98] performs this test before checking whether the next pointer in the dummy node is null, which
50 means that it reads \p Tail every time a dequeuing process loops. Under high load, when operations retry
51 frequently, our modification will reduce the number of accesses to global memory. This modification, however,
52 introduces the possibility of \p Head and \p Tail 'crossing'."
54 Explanation of template arguments see \p intrusive::MSQueue.
58 #include <cds/intrusive/moir_queue.h>
59 #include <cds/gc/hp.h>
61 namespace ci = cds::inrtusive;
62 typedef cds::gc::HP hp_gc;
64 // MoirQueue with Hazard Pointer garbage collector, base hook + item disposer:
65 struct Foo: public ci::msqueue::node< hp_gc >
71 // Disposer for Foo struct just deletes the object passed in
73 void operator()( Foo * p )
79 typedef ci::MoirQueue<
82 typename ci::msqueue::make_traits<
84 ci::msqueue::base_hook< ci::opt::gc<hp_gc> >
86 ,ci::opt::disposer< fooDisposer >
90 // MoirQueue with Hazard Pointer garbage collector,
91 // member hook + item disposer + item counter,
92 // without padding of internal queue data:
97 ci::msqueue::node< hp_gc > hMember;
100 struct barQueueTraits: public ci::msqueue::traits
102 typedef ci::msqueue::member_hook< offsetof(Bar, hMember), ,ci::opt::gc<hp_gc> > hook;
103 typedef fooDisposer disposer;
104 typedef cds::atomicity::item_counter item_counter;
105 enum { padding = cds::opt::no_special_padding };
107 typedef ci::MoirQueue< hp_gc, Bar, barQueueTraits > barQueue;
110 template <typename GC, typename T, typename Traits = cds::intrusive::msqueue::traits>
111 class MoirQueue: public MSQueue< GC, T, Traits >
114 typedef MSQueue< GC, T, Traits > base_class;
115 typedef typename base_class::node_type node_type;
120 typedef typename base_class::value_type value_type;
121 typedef typename base_class::back_off back_off;
122 typedef typename base_class::gc gc;
123 typedef typename base_class::node_traits node_traits;
124 typedef typename base_class::memory_model memory_model;
127 /// Rebind template arguments
128 template < typename GC2, typename T2, typename Traits2 >
130 typedef MoirQueue< GC2, T2, Traits2> other ; ///< Rebinding result
135 typedef typename base_class::dequeue_result dequeue_result;
137 bool do_dequeue( dequeue_result& res )
144 h = res.guards.protect( 0, base_class::m_pHead, []( node_type * p ) -> value_type * { return node_traits::to_value_ptr( p );});
145 pNext = res.guards.protect( 1, h->m_pNext, []( node_type * p ) -> value_type * { return node_traits::to_value_ptr( p );});
147 if ( pNext == nullptr ) {
148 base_class::m_Stat.onEmptyDequeue();
149 return false; // queue is empty
152 if ( base_class::m_pHead.compare_exchange_strong( h, pNext, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
153 node_type * t = base_class::m_pTail.load(memory_model::memory_order_acquire);
155 base_class::m_pTail.compare_exchange_strong( t, pNext, memory_model::memory_order_release, atomics::memory_order_relaxed );
159 base_class::m_Stat.onDequeueRace();
163 --base_class::m_ItemCounter;
164 base_class::m_Stat.onDequeue();
173 /// Dequeues a value from the queue
174 /** @anchor cds_intrusive_MoirQueue_dequeue
175 See warning about item disposing in \p MSQueue::dequeue.
177 value_type * dequeue()
180 if ( do_dequeue( res )) {
181 base_class::dispose_result( res );
182 return node_traits::to_value_ptr( *res.pNext );
187 /// Synonym for \ref cds_intrusive_MoirQueue_dequeue "dequeue" function
194 }} // namespace cds::intrusive
196 #endif // #ifndef CDSLIB_INTRUSIVE_MOIR_QUEUE_H