3 #ifndef __CDS_INTRUSIVE_MSQUEUE_H
4 #define __CDS_INTRUSIVE_MSQUEUE_H
7 #include <cds/intrusive/details/single_link_struct.h>
8 #include <cds/cxx11_atomic.h>
10 namespace cds { namespace intrusive {
12 /// MSQueue related definitions
13 /** @ingroup cds_intrusive_helper
20 - GC - garbage collector used
21 - Tag - a \ref cds_intrusive_hook_tag "tag"
23 template <class GC, typename Tag = opt::none >
24 using node = cds::intrusive::single_link::node< GC, Tag > ;
29 - opt::gc - garbage collector used.
30 - opt::tag - a \ref cds_intrusive_hook_tag "tag"
32 template < typename... Options >
33 using base_hook = cds::intrusive::single_link::base_hook< Options...>;
37 \p MemberOffset specifies offset in bytes of \ref node member into your structure.
38 Use \p offsetof macro to define \p MemberOffset
41 - opt::gc - garbage collector used.
42 - opt::tag - a \ref cds_intrusive_hook_tag "tag"
44 template < size_t MemberOffset, typename... Options >
45 using member_hook = cds::intrusive::single_link::member_hook< MemberOffset, Options... >;
49 \p NodeTraits defines type traits for node.
50 See \ref node_traits for \p NodeTraits interface description
53 - opt::gc - garbage collector used.
54 - opt::tag - a \ref cds_intrusive_hook_tag "tag"
56 template <typename NodeTraits, typename... Options >
57 using traits_hook = cds::intrusive::single_link::traits_hook< NodeTraits, Options... >;
59 /// Queue internal statistics. May be used for debugging or profiling
61 Template argument \p Counter defines type of counter.
62 Default is \p cds::atomicity::event_counter, that is weak, i.e. it is not guaranteed
63 strict event counting.
64 You may use stronger type of counter like as \p cds::atomicity::item_counter,
65 or even integral type, for example, \p int.
67 template <typename Counter = cds::atomicity::event_counter >
70 typedef Counter counter_type ; ///< Counter type
72 counter_type m_EnqueueCount ; ///< Enqueue call count
73 counter_type m_DequeueCount ; ///< Dequeue call count
74 counter_type m_EnqueueRace ; ///< Count of enqueue race conditions encountered
75 counter_type m_DequeueRace ; ///< Count of dequeue race conditions encountered
76 counter_type m_AdvanceTailError ; ///< Count of "advance tail failed" events
77 counter_type m_BadTail ; ///< Count of events "Tail is not pointed to the last item in the queue"
79 /// Register enqueue call
80 void onEnqueue() { ++m_EnqueueCount; }
81 /// Register dequeue call
82 void onDequeue() { ++m_DequeueCount; }
83 /// Register enqueue race event
84 void onEnqueueRace() { ++m_EnqueueRace; }
85 /// Register dequeue race event
86 void onDequeueRace() { ++m_DequeueRace; }
87 /// Register "advance tail failed" event
88 void onAdvanceTailFailed() { ++m_AdvanceTailError; }
89 /// Register event "Tail is not pointed to last item in the queue"
90 void onBadTail() { ++m_BadTail; }
95 m_EnqueueCount.reset();
96 m_DequeueCount.reset();
97 m_EnqueueRace.reset();
98 m_DequeueRace.reset();
99 m_AdvanceTailError.reset();
103 stat& operator +=( stat const& s )
105 m_EnqueueCount += s.m_EnqueueCount.get();
106 m_DequeueCount += s.m_DequeueCount.get();
107 m_EnqueueRace += s.m_EnqueueRace.get();
108 m_DequeueRace += s.m_DequeueRace.get();
109 m_AdvanceTailError += s.m_AdvanceTailError.get();
110 m_BadTail += s.m_BadTail.get();
117 /// Dummy queue statistics - no counting is performed, no overhead. Support interface like \p msqueue::stat
118 /** @ingroup cds_intrusive_helper
125 void onEnqueueRace() {}
126 void onDequeueRace() {}
127 void onAdvanceTailFailed() {}
131 empty_stat& operator +=( empty_stat const& s )
138 /// MSQueue default type traits
141 /// Back-off strategy
142 typedef cds::backoff::empty back_off;
144 /// Hook, possible types are \p msqueue::base_hook, \p msqueue::member_hook, \p msqueue::traits_hook
145 typedef msqueue::base_hook<> hook;
147 /// The functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used for dequeuing
148 typedef opt::v::empty_disposer disposer;
150 /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
151 typedef atomicity::empty_item_counter item_counter;
153 /// Internal statistics (by default, disabled)
155 Possible option value are: \p msqueue::stat, \p msqueue::empty_stat (the default),
156 user-provided class that supports \p %msqueue::stat interface.
158 typedef msqueue::empty_stat stat;
160 /// C++ memory ordering model
162 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
163 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
165 typedef opt::v::relaxed_ordering memory_model;
167 /// Link checking, see \p cds::opt::link_checker
168 static const opt::link_check_type link_checker = opt::debug_check_link;
170 /// Alignment of internal queue data. Default is \p opt::cache_line_alignment
171 enum { alignment = opt::cache_line_alignment };
174 /// Metafunction converting option list to \p msqueue::traits
176 This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
177 Supported \p Options are:
179 - opt::hook - hook used. Possible hooks are: \p msqueue::base_hook, \p msqueue::member_hook, \p msqueue::traits_hook.
180 If the option is not specified, \p %msqueue::base_hook<> is used.
181 - opt::back_off - back-off strategy used, default is \p cds::backoff::empty.
182 - opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used
184 - opt::link_checker - the type of node's link fields checking. Default is \p opt::debug_check_link
185 - opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter (item counting disabled)
186 To enable item counting use \p cds::atomicity::item_counter
187 - opt::stat - the type to gather internal statistics.
188 Possible statistics types are: \p msqueue::stat, \p msqueue::empty_stat, user-provided class that supports \p %msqueue::stat interface.
189 Default is \p msqueue::empty_stat.
190 - opt::alignment - the alignment for internal queue data. Default is \p opt::cache_line_alignment
191 - opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
192 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
194 Example: declare \p %MSQueue with item counting and internal statistics
196 typedef cds::intrusive::MSQueue< cds::gc::HP, Foo,
197 typename cds::intrusive::msqueue::make_traits<
198 cds::opt::item_counte< cds::atomicity::item_counter >,
199 cds::opt::stat< cds::intrusive::msqueue::stat<> >
204 template <typename... Options>
206 # ifdef CDS_DOXYGEN_INVOKED
207 typedef implementation_defined type; ///< Metafunction result
209 typedef typename cds::opt::make_options<
210 typename cds::opt::find_type_traits< traits, Options... >::type
217 } // namespace msqueue
219 /// Michael & Scott's intrusive lock-free queue
220 /** @ingroup cds_intrusive_queue
221 Implementation of well-known Michael & Scott's queue algorithm:
222 - [1998] Maged Michael, Michael Scott "Simple, fast, and practical non-blocking and blocking concurrent queue algorithms"
225 - \p GC - garbage collector type: \p gc::HP, \p gc::DHP
226 - \p T - type to be stored in the queue. A value of type \p T must be derived from \p msqueue::node for \p msqueue::base_hook,
227 or it should have a member of type \p %msqueue::node for \p msqueue::member_hook,
228 or it should be convertible to \p %msqueue::node for \p msqueue::traits_hook.
229 - \p Traits - queue traits, default is \p queue::traits. You can use \p queue::make_traits
230 metafunction to make your traits or just derive your traits from \p %queue::traits:
232 struct myTraits: public cds::intrusive::queue::traits {
233 typedef cds::intrusive::msqueue::stat<> stat;
234 typedef cds::atomicity::item_counter item_counter;
236 typedef cds::intrusive::MSQueue< cds::gc::HP, Foo, myTraits > myQueue;
238 // Equivalent make_traits example:
239 typedef cds::intrusive::MSQueue< cds::gc::HP, Foo,
240 typename cds::intrusive::msqueue::make_traits<
241 cds::opt::stat< cds::intrusive::msqueue::stat<> >,
242 cds::opt::item_counter< cds::atomicity::item_counter >
247 \par About item disposing
248 The Michael & Scott's queue algo has a key feature: even if the queue is empty it contains one item that is "dummy" one from
249 the standpoint of the algo. See \p dequeue() function for explanation.
253 #include <cds/intrusive/msqueue.h>
254 #include <cds/gc/hp.h>
256 namespace ci = cds::inrtusive;
257 typedef cds::gc::HP hp_gc;
259 // MSQueue with Hazard Pointer garbage collector, base hook + item disposer:
260 struct Foo: public ci::msqueue::node< hp_gc >
266 // Disposer for Foo struct just deletes the object passed in
268 void operator()( Foo * p )
274 // Declare traits for the queue
275 struct myTraits: public ci::msqueue::traits {
277 ci::msqueue::base_hook< ci::opt::gc<hp_gc> >
279 ,ci::opt::disposer< fooDisposer >
282 // At least, declare the queue type
283 typedef ci::MSQueue< hp_gc, Foo, myTraits > fooQueue;
286 // MSQueue with Hazard Pointer garbage collector,
287 // member hook + item disposer + item counter,
288 // without alignment of internal queue data
289 // Use msqueue::make_traits
294 ci::msqueue::node< hp_gc > hMember;
297 typedef ci::MSQueue< hp_gc,
299 typename ci::msqueue::make_traits<
301 ci::msqueue::member_hook<
302 offsetof(Bar, hMember)
306 ,ci::opt::disposer< fooDisposer >
307 ,cds::opt::item_counter< cds::atomicity::item_counter >
308 ,cds::opt::alignment< cds::opt::no_special_alignment >
313 template <typename GC, typename T, typename Traits>
317 typedef GC gc; ///< Garbage collector
318 typedef T value_type; ///< type of value stored in the queue
319 typedef Traits traits; ///< Queue traits
321 typedef typename traits::hook hook; ///< hook type
322 typedef typename hook::node_type node_type; ///< node type
323 typedef typename traits::disposer disposer; ///< disposer used
324 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
325 typedef typename single_link::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
327 typedef typename traits::back_off back_off; ///< back-off strategy
328 typedef typename traits::item_counter item_counter; ///< Item counter class
329 typedef typename traits::stat stat; ///< Internal statistics
330 typedef typename traits::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option
332 /// Rebind template arguments
333 template <typename GC2, typename T2, typename Traits2>
335 typedef MSQueue< GC2, T2, Traits2 > other; ///< Rebinding result
341 // GC and node_type::gc must be the same
342 static_assert((std::is_same<gc, typename node_type::gc>::value), "GC and node_type::gc must be the same");
344 struct internal_disposer
346 void operator()( value_type * p )
348 assert( p != nullptr );
350 MSQueue::clear_links( node_traits::to_node_ptr(p) );
355 typedef intrusive::node_to_value<MSQueue> node_to_value;
356 typedef typename opt::details::alignment_setter< typename node_type::atomic_node_ptr, traits::alignment >::type aligned_node_ptr;
358 typedef typename opt::details::alignment_setter< node_type, traits::alignment >::type dummy_node_type;
360 aligned_node_ptr m_pHead ; ///< Queue's head pointer (cache-line aligned)
361 aligned_node_ptr m_pTail ; ///< Queue's tail pointer (cache-line aligned)
362 dummy_node_type m_Dummy ; ///< dummy node
363 item_counter m_ItemCounter ; ///< Item counter
364 stat m_Stat ; ///< Internal statistics
368 struct dequeue_result {
369 typename gc::template GuardArray<2> guards;
375 bool do_dequeue( dequeue_result& res )
382 h = res.guards.protect( 0, m_pHead, node_to_value() );
383 pNext = h->m_pNext.load( memory_model::memory_order_relaxed );
384 res.guards.assign( 1, node_to_value()( pNext ));
385 if ( m_pHead.load(memory_model::memory_order_acquire) != h )
388 if ( pNext == nullptr )
389 return false ; // empty queue
391 node_type * t = m_pTail.load(memory_model::memory_order_acquire);
393 // It is needed to help enqueue
394 m_pTail.compare_exchange_strong( t, pNext, memory_model::memory_order_release, atomics::memory_order_relaxed );
399 if ( m_pHead.compare_exchange_strong( h, pNext, memory_model::memory_order_release, atomics::memory_order_relaxed ))
402 m_Stat.onDequeueRace();
414 static void clear_links( node_type * pNode )
416 pNode->m_pNext.store( nullptr, memory_model::memory_order_release );
419 void dispose_result( dequeue_result& res )
421 dispose_node( res.pHead );
424 void dispose_node( node_type * p )
426 // Note for he dummy node:
427 // We cannot clear m_Dummy here since it leads to ABA.
428 // On the other hand, we cannot use deferred clear_links( &m_Dummy ) call via
429 // HP retiring cycle since m_Dummy is member of MSQueue and may be destroyed
430 // before HP retiring cycle invocation.
431 // So, we will never clear m_Dummy
432 if ( p != &m_Dummy ) {
433 gc::template retire<internal_disposer>( node_traits::to_value_ptr(p) );
439 /// Initializes empty queue
441 : m_pHead( &m_Dummy )
442 , m_pTail( &m_Dummy )
445 /// Destructor clears the queue
447 Since the Michael & Scott queue contains at least one item even
448 if the queue is empty, the destructor may call item disposer.
454 node_type * pHead = m_pHead.load(memory_model::memory_order_relaxed);
456 assert( pHead != nullptr );
457 assert( pHead == m_pTail.load(memory_model::memory_order_relaxed) );
459 m_pHead.store( nullptr, memory_model::memory_order_relaxed );
460 m_pTail.store( nullptr, memory_model::memory_order_relaxed );
462 dispose_node( pHead );
465 /// Returns queue's item count
467 The value returned depends on \p msqueue::traits::item_counter. For \p atomicity::empty_item_counter,
468 this function always returns 0.
470 @note Even if you use real item counter and it returns 0, this fact is not mean that the queue
471 is empty. To check queue emptyness use \p empty() method.
475 return m_ItemCounter.value();
478 /// Returns reference to internal statistics
479 stat const& statistics() const
484 /// Enqueues \p val value into the queue.
485 /** @anchor cds_intrusive_MSQueue_enqueue
486 The function always returns \p true.
488 bool enqueue( value_type& val )
490 node_type * pNew = node_traits::to_node_ptr( val );
491 link_checker::is_empty( pNew );
493 typename gc::Guard guard;
498 t = guard.protect( m_pTail, node_to_value() );
500 node_type * pNext = t->m_pNext.load(memory_model::memory_order_acquire);
501 if ( pNext != nullptr ) {
502 // Tail is misplaced, advance it
503 m_pTail.compare_exchange_weak( t, pNext, memory_model::memory_order_release, atomics::memory_order_relaxed );
508 node_type * tmp = nullptr;
509 if ( t->m_pNext.compare_exchange_strong( tmp, pNew, memory_model::memory_order_release, atomics::memory_order_relaxed ))
512 m_Stat.onEnqueueRace();
518 if ( !m_pTail.compare_exchange_strong( t, pNew, memory_model::memory_order_acq_rel, atomics::memory_order_relaxed ))
519 m_Stat.onAdvanceTailFailed();
523 /// Dequeues a value from the queue
524 /** @anchor cds_intrusive_MSQueue_dequeue
525 If the queue is empty the function returns \p nullptr.
528 The queue algorithm has following feature: when \p %dequeue() is called,
529 the item returning is still queue's top, and previous top is disposed:
532 before dequeuing Dequeue after dequeuing
533 +------------------+ +------------------+
534 Top ->| Item 1 | -> Dispose Item 1 | Item 2 | <- Top
535 +------------------+ +------------------+
536 | Item 2 | -> Return Item 2 | ... |
541 \p %dequeue() function returns Item 2, that becomes new top of queue, and calls
542 the disposer for Item 1, that was queue's top on function entry.
543 Thus, you cannot manually delete item returned because it is still included in
544 item sequence and it has valuable link field that must not be zeroed.
545 The item should be deleted only in garbage collector retire cycle using the disposer.
547 value_type * dequeue()
551 if ( do_dequeue( res )) {
552 dispose_result( res );
554 return node_traits::to_value_ptr( *res.pNext );
559 /// Synonym for \ref cds_intrusive_MSQueue_enqueue "enqueue()" function
560 bool push( value_type& val )
562 return enqueue( val );
565 /// Synonym for \ref cds_intrusive_MSQueue_dequeue "dequeue()" function
571 /// Checks if the queue is empty
574 typename gc::Guard guard;
575 return guard.protect( m_pHead, node_to_value() )->m_pNext.load( memory_model::memory_order_relaxed ) == nullptr;
580 The function repeatedly calls \p dequeue() until it returns \p nullptr.
581 The disposer defined in template \p Traits is called for each item
582 that can be safely disposed.
590 }} // namespace cds::intrusive
592 #endif // #ifndef __CDS_INTRUSIVE_MSQUEUE_H