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
123 void onEnqueueRace() {}
124 void onDequeueRace() {}
125 void onAdvanceTailFailed() {}
129 empty_stat& operator +=( empty_stat const& s )
136 /// MSQueue default traits
139 /// Back-off strategy
140 typedef cds::backoff::empty back_off;
142 /// Hook, possible types are \p msqueue::base_hook, \p msqueue::member_hook, \p msqueue::traits_hook
143 typedef msqueue::base_hook<> hook;
145 /// The functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used for dequeuing
146 typedef opt::v::empty_disposer disposer;
148 /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
149 typedef atomicity::empty_item_counter item_counter;
151 /// Internal statistics (by default, disabled)
153 Possible option value are: \p msqueue::stat, \p msqueue::empty_stat (the default),
154 user-provided class that supports \p %msqueue::stat interface.
156 typedef msqueue::empty_stat stat;
158 /// C++ memory ordering model
160 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
161 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
163 typedef opt::v::relaxed_ordering memory_model;
165 /// Link checking, see \p cds::opt::link_checker
166 static CDS_CONSTEXPR const opt::link_check_type link_checker = opt::debug_check_link;
168 /// Alignment for internal queue data. Default is \p opt::cache_line_alignment
169 enum { alignment = opt::cache_line_alignment };
172 /// Metafunction converting option list to \p msqueue::traits
174 Supported \p Options are:
176 - \p opt::hook - hook used. Possible hooks are: \p msqueue::base_hook, \p msqueue::member_hook, \p msqueue::traits_hook.
177 If the option is not specified, \p %msqueue::base_hook<> is used.
178 - \p opt::back_off - back-off strategy used, default is \p cds::backoff::empty.
179 - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used
181 - \p opt::link_checker - the type of node's link fields checking. Default is \p opt::debug_check_link
182 - \p opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter (item counting disabled)
183 To enable item counting use \p cds::atomicity::item_counter
184 - \p opt::stat - the type to gather internal statistics.
185 Possible statistics types are: \p msqueue::stat, \p msqueue::empty_stat, user-provided class that supports \p %msqueue::stat interface.
186 Default is \p %msqueue::empty_stat (internal statistics disabled).
187 - \p opt::alignment - the alignment for internal queue data. Default is \p opt::cache_line_alignment
188 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
189 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
191 Example: declare \p %MSQueue with item counting and internal statistics
193 typedef cds::intrusive::MSQueue< cds::gc::HP, Foo,
194 typename cds::intrusive::msqueue::make_traits<
195 cds::intrusive::opt:hook< cds::intrusive::msqueue::base_hook< cds::opt::gc<cds:gc::HP> >>,
196 cds::opt::item_counte< cds::atomicity::item_counter >,
197 cds::opt::stat< cds::intrusive::msqueue::stat<> >
202 template <typename... Options>
204 # ifdef CDS_DOXYGEN_INVOKED
205 typedef implementation_defined type; ///< Metafunction result
207 typedef typename cds::opt::make_options<
208 typename cds::opt::find_type_traits< traits, Options... >::type
213 } // namespace msqueue
215 /// Michael & Scott's intrusive lock-free queue
216 /** @ingroup cds_intrusive_queue
217 Implementation of well-known Michael & Scott's queue algorithm:
218 - [1998] Maged Michael, Michael Scott "Simple, fast, and practical non-blocking and blocking concurrent queue algorithms"
221 - \p GC - garbage collector type: \p gc::HP, \p gc::DHP
222 - \p T - type of value to be stored in the queue. A value of type \p T must be derived from \p msqueue::node for \p msqueue::base_hook,
223 or it should have a member of type \p %msqueue::node for \p msqueue::member_hook,
224 or it should be convertible to \p %msqueue::node for \p msqueue::traits_hook.
225 - \p Traits - queue traits, default is \p msqueue::traits. You can use \p msqueue::make_traits
226 metafunction to make your traits or just derive your traits from \p %msqueue::traits:
228 struct myTraits: public cds::intrusive::msqueue::traits {
229 typedef cds::intrusive::msqueue::stat<> stat;
230 typedef cds::atomicity::item_counter item_counter;
232 typedef cds::intrusive::MSQueue< cds::gc::HP, Foo, myTraits > myQueue;
234 // Equivalent make_traits example:
235 typedef cds::intrusive::MSQueue< cds::gc::HP, Foo,
236 typename cds::intrusive::msqueue::make_traits<
237 cds::opt::stat< cds::intrusive::msqueue::stat<> >,
238 cds::opt::item_counter< cds::atomicity::item_counter >
243 \par About item disposing
244 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
245 the standpoint of the algo. See \p dequeue() function for explanation.
249 #include <cds/intrusive/msqueue.h>
250 #include <cds/gc/hp.h>
252 namespace ci = cds::inrtusive;
253 typedef cds::gc::HP hp_gc;
255 // MSQueue with Hazard Pointer garbage collector, base hook + item disposer:
256 struct Foo: public ci::msqueue::node< hp_gc >
262 // Disposer for Foo struct just deletes the object passed in
264 void operator()( Foo * p )
270 // Declare traits for the queue
271 struct myTraits: public ci::msqueue::traits {
273 ci::msqueue::base_hook< ci::opt::gc<hp_gc> >
275 ,ci::opt::disposer< fooDisposer >
278 // At least, declare the queue type
279 typedef ci::MSQueue< hp_gc, Foo, myTraits > fooQueue;
282 // MSQueue with Hazard Pointer garbage collector,
283 // member hook + item disposer + item counter,
284 // without alignment of internal queue data
285 // Use msqueue::make_traits
290 ci::msqueue::node< hp_gc > hMember;
293 typedef ci::MSQueue< hp_gc,
295 typename ci::msqueue::make_traits<
297 ci::msqueue::member_hook<
298 offsetof(Bar, hMember)
302 ,ci::opt::disposer< fooDisposer >
303 ,cds::opt::item_counter< cds::atomicity::item_counter >
304 ,cds::opt::alignment< cds::opt::no_special_alignment >
309 template <typename GC, typename T, typename Traits>
313 typedef GC gc; ///< Garbage collector
314 typedef T value_type; ///< type of value to be stored in the queue
315 typedef Traits traits; ///< Queue traits
317 typedef typename traits::hook hook; ///< hook type
318 typedef typename hook::node_type node_type; ///< node type
319 typedef typename traits::disposer disposer; ///< disposer used
320 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
321 typedef typename single_link::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
323 typedef typename traits::back_off back_off; ///< back-off strategy
324 typedef typename traits::item_counter item_counter; ///< Item counter class
325 typedef typename traits::stat stat; ///< Internal statistics
326 typedef typename traits::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option
328 /// Rebind template arguments
329 template <typename GC2, typename T2, typename Traits2>
331 typedef MSQueue< GC2, T2, Traits2 > other; ///< Rebinding result
334 static CDS_CONSTEXPR const size_t m_nHazardPtrCount = 2; ///< Count of hazard pointer required for the algorithm
339 // GC and node_type::gc must be the same
340 static_assert((std::is_same<gc, typename node_type::gc>::value), "GC and node_type::gc must be the same");
342 typedef intrusive::node_to_value<MSQueue> node_to_value;
343 typedef typename opt::details::alignment_setter< typename node_type::atomic_node_ptr, traits::alignment >::type aligned_node_ptr;
344 typedef typename opt::details::alignment_setter< node_type, traits::alignment >::type dummy_node_type;
346 aligned_node_ptr m_pHead ; ///< Queue's head pointer
347 aligned_node_ptr m_pTail ; ///< Queue's tail pointer
348 dummy_node_type m_Dummy ; ///< dummy node
349 item_counter m_ItemCounter ; ///< Item counter
350 stat m_Stat ; ///< Internal statistics
354 struct dequeue_result {
355 typename gc::template GuardArray<2> guards;
361 bool do_dequeue( dequeue_result& res )
368 h = res.guards.protect( 0, m_pHead, node_to_value() );
369 pNext = h->m_pNext.load( memory_model::memory_order_relaxed );
370 res.guards.assign( 1, node_to_value()( pNext ));
371 if ( m_pHead.load(memory_model::memory_order_acquire) != h )
374 if ( pNext == nullptr )
375 return false ; // empty queue
377 node_type * t = m_pTail.load(memory_model::memory_order_acquire);
379 // It is needed to help enqueue
380 m_pTail.compare_exchange_strong( t, pNext, memory_model::memory_order_release, atomics::memory_order_relaxed );
385 if ( m_pHead.compare_exchange_strong( h, pNext, memory_model::memory_order_release, atomics::memory_order_relaxed ))
388 m_Stat.onDequeueRace();
400 static void clear_links( node_type * pNode )
402 pNode->m_pNext.store( nullptr, memory_model::memory_order_release );
405 void dispose_result( dequeue_result& res )
407 dispose_node( res.pHead );
410 void dispose_node( node_type * p )
412 // Note about the dummy node:
413 // We cannot clear m_Dummy here since it leads to ABA.
414 // On the other hand, we cannot use deferred clear_links( &m_Dummy ) call via
415 // HP retiring cycle since m_Dummy is member of MSQueue and may be destroyed
416 // before HP retiring cycle invocation.
417 // So, we will never clear m_Dummy
419 struct disposer_thunk {
420 void operator()( value_type * p ) const
422 assert( p != nullptr );
423 MSQueue::clear_links( node_traits::to_node_ptr( p ) );
429 gc::template retire<disposer_thunk>( node_traits::to_value_ptr( p ) );
434 /// Initializes empty queue
436 : m_pHead( &m_Dummy )
437 , m_pTail( &m_Dummy )
440 /// Destructor clears the queue
442 Since the Michael & Scott queue contains at least one item even
443 if the queue is empty, the destructor may call item disposer.
449 node_type * pHead = m_pHead.load(memory_model::memory_order_relaxed);
451 assert( pHead != nullptr );
452 assert( pHead == m_pTail.load(memory_model::memory_order_relaxed) );
454 m_pHead.store( nullptr, memory_model::memory_order_relaxed );
455 m_pTail.store( nullptr, memory_model::memory_order_relaxed );
457 dispose_node( pHead );
460 /// Enqueues \p val value into the queue.
461 /** @anchor cds_intrusive_MSQueue_enqueue
462 The function always returns \p true.
464 bool enqueue( value_type& val )
466 node_type * pNew = node_traits::to_node_ptr( val );
467 link_checker::is_empty( pNew );
469 typename gc::Guard guard;
474 t = guard.protect( m_pTail, node_to_value() );
476 node_type * pNext = t->m_pNext.load(memory_model::memory_order_acquire);
477 if ( pNext != nullptr ) {
478 // Tail is misplaced, advance it
479 m_pTail.compare_exchange_weak( t, pNext, memory_model::memory_order_release, atomics::memory_order_relaxed );
484 node_type * tmp = nullptr;
485 if ( t->m_pNext.compare_exchange_strong( tmp, pNew, memory_model::memory_order_release, atomics::memory_order_relaxed ))
488 m_Stat.onEnqueueRace();
494 if ( !m_pTail.compare_exchange_strong( t, pNew, memory_model::memory_order_acq_rel, atomics::memory_order_relaxed ))
495 m_Stat.onAdvanceTailFailed();
499 /// Dequeues a value from the queue
500 /** @anchor cds_intrusive_MSQueue_dequeue
501 If the queue is empty the function returns \p nullptr.
504 The queue algorithm has following feature: when \p %dequeue() is called,
505 the item returning is still queue's top, and previous top is disposed:
508 before dequeuing Dequeue after dequeuing
509 +------------------+ +------------------+
510 Top ->| Item 1 | -> Dispose Item 1 | Item 2 | <- Top
511 +------------------+ +------------------+
512 | Item 2 | -> Return Item 2 | ... |
517 \p %dequeue() function returns Item 2, that becomes new top of queue, and calls
518 the disposer for Item 1, that was queue's top on function entry.
519 Thus, you cannot manually delete item returned because it is still included in
520 item sequence and it has valuable link field that must not be zeroed.
521 The item should be deleted only in garbage collector retire cycle using the disposer.
523 value_type * dequeue()
527 if ( do_dequeue( res )) {
528 dispose_result( res );
530 return node_traits::to_value_ptr( *res.pNext );
535 /// Synonym for \ref cds_intrusive_MSQueue_enqueue "enqueue()" function
536 bool push( value_type& val )
538 return enqueue( val );
541 /// Synonym for \ref cds_intrusive_MSQueue_dequeue "dequeue()" function
547 /// Checks if the queue is empty
550 typename gc::Guard guard;
551 return guard.protect( m_pHead, node_to_value() )->m_pNext.load( memory_model::memory_order_relaxed ) == nullptr;
556 The function repeatedly calls \p dequeue() until it returns \p nullptr.
557 The disposer defined in template \p Traits is called for each item
558 that can be safely disposed.
565 /// Returns queue's item count
567 The value returned depends on \p msqueue::traits::item_counter. For \p atomicity::empty_item_counter,
568 this function always returns 0.
570 @note Even if you use real item counter and it returns 0, this fact is not mean that the queue
571 is empty. To check queue emptyness use \p empty() method.
575 return m_ItemCounter.value();
578 /// Returns reference to internal statistics
579 stat const& statistics() const
585 }} // namespace cds::intrusive
587 #endif // #ifndef __CDS_INTRUSIVE_MSQUEUE_H