3 #ifndef __CDS_INTRUSIVE_OPTIMISTIC_QUEUE_H
4 #define __CDS_INTRUSIVE_OPTIMISTIC_QUEUE_H
7 #include <cds/intrusive/details/base.h>
8 #include <cds/cxx11_atomic.h>
9 #include <cds/gc/default_gc.h>
11 namespace cds { namespace intrusive {
13 /// OptimisticQueue related definitions
14 /** @ingroup cds_intrusive_helper
16 namespace optimistic_queue {
18 /// Optimistic queue node
21 - GC - garbage collector used. gc::HRC is not supported.
22 - Tag - a tag used to distinguish between different implementation
24 template <class GC, typename Tag = opt::none>
25 struct node: public GC::container_node
27 typedef GC gc ; ///< Garbage collector
28 typedef Tag tag ; ///< tag
30 typedef typename gc::template atomic_ref<node> atomic_node_ptr ; ///< atomic pointer
32 atomic_node_ptr m_pPrev ; ///< Pointer to previous node
33 atomic_node_ptr m_pNext ; ///< Pointer to next node
35 CDS_CONSTEXPR node() CDS_NOEXCEPT
43 typedef cds::gc::default_gc gc;
44 typedef opt::none tag;
49 template < typename HookType, typename... Options>
52 typedef typename opt::make_options< default_hook, Options...>::type options;
53 typedef typename options::gc gc;
54 typedef typename options::tag tag;
55 typedef node<gc, tag> node_type;
56 typedef HookType hook_type;
63 - opt::gc - garbage collector used.
64 - opt::tag - a \ref cds_intrusive_hook_tag "tag"
66 template < typename... Options >
67 struct base_hook: public hook< opt::base_hook_tag, Options... >
72 \p MemberOffset specifies offset in bytes of \ref node member into your structure.
73 Use \p offsetof macro to define \p MemberOffset
76 - opt::gc - garbage collector used.
77 - opt::tag - a \ref cds_intrusive_hook_tag "tag"
79 template < size_t MemberOffset, typename... Options >
80 struct member_hook: public hook< opt::member_hook_tag, Options... >
83 static const size_t c_nMemberOffset = MemberOffset;
89 \p NodeTraits defines type traits for node.
90 See \ref node_traits for \p NodeTraits interface description
93 - opt::gc - garbage collector used.
94 - opt::tag - a \ref cds_intrusive_hook_tag "tag"
96 template <typename NodeTraits, typename... Options >
97 struct traits_hook: public hook< opt::traits_hook_tag, Options... >
100 typedef NodeTraits node_traits;
105 template <typename Node>
106 struct link_checker {
108 typedef Node node_type;
111 /// Checks if the link fields of node \p pNode is \p nullptr
113 An asserting is generated if \p pNode link fields is not \p nullptr
115 static void is_empty( const node_type * pNode )
117 assert( pNode->m_pNext.load( atomics::memory_order_relaxed ) == nullptr );
118 assert( pNode->m_pPrev.load( atomics::memory_order_relaxed ) == nullptr );
122 /// Metafunction for selecting appropriate link checking policy
123 template < typename Node, opt::link_check_type LinkType >
124 struct get_link_checker
127 typedef intrusive::opt::v::empty_link_checker<Node> type;
132 template < typename Node >
133 struct get_link_checker< Node, opt::always_check_link >
135 typedef link_checker<Node> type;
137 template < typename Node >
138 struct get_link_checker< Node, opt::debug_check_link >
141 typedef link_checker<Node> type;
143 typedef intrusive::opt::v::empty_link_checker<Node> type;
148 /// OptimisticQueue internal statistics. May be used for debugging or profiling
150 Template argument \p Counter defines type of counter.
151 Default is \p cds::atomicity::event_counter, that is weak, i.e. it is not guaranteed
152 strict event counting.
153 You may use stronger type of counter like as \p cds::atomicity::item_counter,
154 or even integral type, for example, \p int.
156 template <typename Counter = cds::atomicity::event_counter >
159 typedef Counter counter_type; ///< Counter type
161 counter_type m_EnqueueCount; ///< Enqueue call count
162 counter_type m_DequeueCount; ///< Dequeue call count
163 counter_type m_EnqueueRace; ///< Count of enqueue race conditions encountered
164 counter_type m_DequeueRace; ///< Count of dequeue race conditions encountered
165 counter_type m_AdvanceTailError; ///< Count of "advance tail failed" events
166 counter_type m_BadTail; ///< Count of events "Tail is not pointed to the last item in the queue"
167 counter_type m_FixListCount; ///< Count of fix list event
169 /// Register enqueue call
170 void onEnqueue() { ++m_EnqueueCount; }
171 /// Register dequeue call
172 void onDequeue() { ++m_DequeueCount; }
173 /// Register enqueue race event
174 void onEnqueueRace() { ++m_EnqueueRace; }
175 /// Register dequeue race event
176 void onDequeueRace() { ++m_DequeueRace; }
177 /// Register "advance tail failed" event
178 void onAdvanceTailFailed() { ++m_AdvanceTailError; }
179 /// Register event "Tail is not pointed to last item in the queue"
180 void onBadTail() { ++m_BadTail; }
181 /// Register fix list event
182 void onFixList() { ++m_FixListCount; }
187 m_EnqueueCount.reset();
188 m_DequeueCount.reset();
189 m_EnqueueRace.reset();
190 m_DequeueRace.reset();
191 m_AdvanceTailError.reset();
193 m_FixListCount.reset();
196 stat& operator +=( stat const& s )
198 m_EnqueueCount += s.m_EnqueueCount.get();
199 m_DequeueCount += s.m_DequeueCount.get();
200 m_EnqueueRace += s.m_EnqueueRace.get();
201 m_DequeueRace += s.m_DequeueRace.get();
202 m_AdvanceTailError += s.m_AdvanceTailError.get();
203 m_BadTail += s.m_BadTail.get();
204 m_FixListCount += s.m_FixListCount.get();
210 /// Dummy OptimisticQueue statistics - no counting is performed. Support interface like \ref optimistic_queue::stat
216 void onEnqueueRace() {}
217 void onDequeueRace() {}
218 void onAdvanceTailFailed() {}
223 empty_stat& operator +=( empty_stat const& )
230 /// OptimisticQueue default type traits
233 /// Back-off strategy
234 typedef cds::backoff::empty back_off;
236 /// Hook, possible types are \p optimistic_queue::base_hook, \p optimistic_queue::member_hook, \p optimistic_queue::traits_hook
237 typedef optimistic_queue::base_hook<> hook;
239 /// The functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used for dequeuing
240 typedef opt::v::empty_disposer disposer;
242 /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
243 typedef cds::atomicity::empty_item_counter item_counter;
245 /// C++ memory ordering model
247 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
248 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
250 typedef opt::v::relaxed_ordering memory_model;
252 /// Internal statistics (by default, disabled)
254 Possible option value are: \p optimistic_queue::stat, \p optimistic_queue::empty_stat (the default),
255 user-provided class that supports \p %optimistic_queue::stat interface.
257 typedef optimistic_queue::empty_stat stat;
259 /// Link checking, see \p cds::opt::link_checker
260 static CDS_CONSTEXPR const opt::link_check_type link_checker = opt::debug_check_link;
262 /// Alignment for internal queue data. Default is \p opt::cache_line_alignment
263 enum { alignment = opt::cache_line_alignment };
266 /// Metafunction converting option list to \p optimistic_queue::traits
268 Supported \p Options are:
270 - opt::hook - hook used. Possible hooks are: \p optimistic_queue::base_hook, \p optimistic_queue::member_hook, \p optimistic_queue::traits_hook.
271 If the option is not specified, \p %optimistic_queue::base_hook<> is used.
272 - opt::back_off - back-off strategy used, default is \p cds::backoff::empty.
273 - opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used
275 - opt::link_checker - the type of node's link fields checking. Default is \p opt::debug_check_link
276 - opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter (item counting disabled)
277 To enable item counting use \p cds::atomicity::item_counter
278 - opt::stat - the type to gather internal statistics.
279 Possible statistics types are: \p optimistic_queue::stat, \p optimistic_queue::empty_stat,
280 user-provided class that supports \p %optimistic_queue::stat interface.
281 Default is \p %optimistic_queue::empty_stat (internal statistics disabled).
282 - opt::alignment - the alignment for internal queue data. Default is \p opt::cache_line_alignment
283 - opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
284 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
286 Example: declare \p %OptimisticQueue with item counting and internal statistics
288 typedef cds::intrusive::OptimisticQueue< cds::gc::HP, Foo,
289 typename cds::intrusive::optimistic_queue::make_traits<
290 cds::intrusive::opt:hook< cds::intrusive::optimistic_queue::base_hook< cds::opt::gc<cds:gc::HP> >>,
291 cds::opt::item_counte< cds::atomicity::item_counter >,
292 cds::opt::stat< cds::intrusive::optimistic_queue::stat<> >
297 template <typename... Options>
299 # ifdef CDS_DOXYGEN_INVOKED
300 typedef implementation_defined type; ///< Metafunction result
302 typedef typename cds::opt::make_options<
303 typename cds::opt::find_type_traits< traits, Options... >::type
308 } // namespace optimistic_queue
310 /// Optimistic intruive lock-free queue
311 /** @ingroup cds_intrusive_queue
312 Implementation of Ladan-Mozes & Shavit optimistic queue algorithm.
313 [2008] Edya Ladan-Mozes, Nir Shavit "An Optimistic Approach to Lock-Free FIFO Queues"
316 - \p GC - garbage collector type: \p gc::HP, \p gc::DHP
317 - \p T - type of value to be stored in the queue. A value of type \p T must be derived from \p optimistic_queue::node for \p optimistic_queue::base_hook,
318 or it should have a member of type \p %optimistic_queue::node for \p optimistic_queue::member_hook,
319 or it should be convertible to \p %optimistic_queue::node for \p optimistic_queue::traits_hook.
320 - \p Traits - queue traits, default is \p optimistic_queue::traits. You can use \p optimistic_queue::make_traits
321 metafunction to make your traits or just derive your traits from \p %optimistic_queue::traits:
323 struct myTraits: public cds::intrusive::optimistic_queue::traits {
324 typedef cds::intrusive::optimistic_queue::stat<> stat;
325 typedef cds::atomicity::item_counter item_counter;
327 typedef cds::intrusive::OptimisticQueue< cds::gc::HP, Foo, myTraits > myQueue;
329 // Equivalent make_traits example:
330 typedef cds::intrusive::OptimisticQueue< cds::gc::HP, Foo,
331 typename cds::intrusive::optimistic_queue::make_traits<
332 cds::opt::stat< cds::intrusive::optimistic_queue::stat<> >,
333 cds::opt::item_counter< cds::atomicity::item_counter >
338 Garbage collecting schema \p GC must be consistent with the optimistic_queue::node GC.
340 \par About item disposing
341 The optimistic queue algo has a key feature: even if the queue is empty it contains one item that is "dummy" one from
342 the standpoint of the algo. See \p dequeue() function for explanation.
346 #include <cds/gc/hp.h>
347 #include <cds/intrusive/optimistic_queue.h>
349 namespace ci = cds::inrtusive;
350 typedef cds::gc::HP hp_gc;
352 // Optimistic queue with Hazard Pointer garbage collector, base hook + item counter:
353 struct Foo: public ci::optimistic_queue::node< hp_gc >
359 typedef ci::OptimisticQueue< hp_gc,
361 typename ci::optimistic_queue::make_traits<
363 ci::optimistic_queue::base_hook< ci::opt::gc< hp_gc > >
365 ,cds::opt::item_counter< cds::atomicity::item_counter >
369 // Optimistic queue with Hazard Pointer garbage collector, member hook, no item counter:
374 ci::optimistic_queue::node< hp_gc > hMember;
377 typedef ci::OptimisticQueue< hp_gc,
379 typename ci::optimistic_queue::make_traits<
381 ci::optimistic_queue::member_hook<
382 offsetof(Bar, hMember)
383 ,ci::opt::gc< hp_gc >
390 template <typename GC, typename T, typename Traits = optimistic_queue::traits >
391 class OptimisticQueue
394 typedef GC gc; ///< Garbage collector
395 typedef T value_type; ///< type of value to be stored in the queue
396 typedef Traits traits; ///< Queue traits
398 typedef typename traits::hook hook; ///< hook type
399 typedef typename hook::node_type node_type; ///< node type
400 typedef typename traits::disposer disposer; ///< disposer used
401 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
402 typedef typename optimistic_queue::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
403 typedef typename traits::back_off back_off; ///< back-off strategy
404 typedef typename traits::item_counter item_counter; ///< Item counting policy used
405 typedef typename traits::memory_model memory_model;///< Memory ordering. See cds::opt::memory_model option
406 typedef typename traits::stat stat; ///< Internal statistics policy used
408 /// Rebind template arguments
409 template <typename GC2, typename T2, typename Traits2>
411 typedef OptimisticQueue< GC2, T2, Traits2 > other ; ///< Rebinding result
416 typedef intrusive::node_to_value<OptimisticQueue> node_to_value;
417 typedef typename opt::details::alignment_setter< typename node_type::atomic_node_ptr, traits::alignment >::type aligned_node_ptr;
419 // GC and node_type::gc must be the same
420 static_assert((std::is_same<gc, typename node_type::gc>::value), "GC and node_type::gc must be the same");
424 aligned_node_ptr m_pTail ; ///< Pointer to tail node
425 aligned_node_ptr m_pHead ; ///< Pointer to head node
426 node_type m_Dummy ; ///< dummy node
427 item_counter m_ItemCounter ; ///< Item counter
428 stat m_Stat ; ///< Internal statistics
430 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 5 ; ///< Count of hazard pointer required for the algorithm
434 static void clear_links( node_type * pNode )
436 pNode->m_pNext.store( nullptr, memory_model::memory_order_release );
437 pNode->m_pPrev.store( nullptr, memory_model::memory_order_release );
440 struct dequeue_result {
441 typename gc::template GuardArray<3> guards;
447 bool do_dequeue( dequeue_result& res )
451 node_type * pFirstNodePrev;
454 while ( true ) { // Try till success or empty
455 pHead = res.guards.protect( 0, m_pHead, node_to_value() );
456 pTail = res.guards.protect( 1, m_pTail, node_to_value() );
457 assert( pHead != nullptr );
458 pFirstNodePrev = res.guards.protect( 2, pHead->m_pPrev, node_to_value() );
460 if ( pHead == m_pHead.load(memory_model::memory_order_relaxed)) {
461 if ( pTail != pHead ) {
462 if ( pFirstNodePrev == nullptr
463 || pFirstNodePrev->m_pNext.load(memory_model::memory_order_relaxed) != pHead )
465 fix_list( pTail, pHead );
468 if ( m_pHead.compare_exchange_weak( pHead, pFirstNodePrev, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
474 // the queue is empty
479 m_Stat.onDequeueRace();
487 res.pNext = pFirstNodePrev;
492 /// Helper function for optimistic queue. Corrects \p prev pointer of queue's nodes if it is needed
493 void fix_list( node_type * pTail, node_type * pHead )
495 // pTail and pHead are already guarded
497 node_type * pCurNode;
498 node_type * pCurNodeNext;
500 typename gc::template GuardArray<2> guards;
503 while ( pCurNode != pHead ) { // While not at head
504 pCurNodeNext = guards.protect(0, pCurNode->m_pNext, node_to_value() );
505 if ( pHead != m_pHead.load(memory_model::memory_order_relaxed) )
507 pCurNodeNext->m_pPrev.store( pCurNode, memory_model::memory_order_release );
508 guards.assign( 1, node_traits::to_value_ptr( pCurNode = pCurNodeNext ));
514 void dispose_result( dequeue_result& res )
516 dispose_node( res.pHead );
519 void dispose_node( node_type * p )
521 assert( p != nullptr );
523 if ( p != &m_Dummy ) {
524 struct internal_disposer
526 void operator ()( value_type * p )
528 assert( p != nullptr );
530 OptimisticQueue::clear_links( node_traits::to_node_ptr( *p ) );
534 gc::template retire<internal_disposer>( node_traits::to_value_ptr(p) );
541 /// Constructor creates empty queue
543 : m_pTail( &m_Dummy )
544 , m_pHead( &m_Dummy )
550 node_type * pHead = m_pHead.load(memory_model::memory_order_relaxed);
551 CDS_DEBUG_ONLY( node_type * pTail = m_pTail.load(memory_model::memory_order_relaxed); )
552 CDS_DEBUG_ONLY( assert( pHead == pTail ); )
553 assert( pHead != nullptr );
555 m_pHead.store( nullptr, memory_model::memory_order_relaxed );
556 m_pTail.store( nullptr, memory_model::memory_order_relaxed );
558 dispose_node( pHead );
561 /// @anchor cds_intrusive_OptimisticQueue_enqueue Enqueues \p data in lock-free manner. Always return \a true
562 bool enqueue( value_type& val )
564 node_type * pNew = node_traits::to_node_ptr( val );
565 link_checker::is_empty( pNew );
567 typename gc::template GuardArray<2> guards;
570 guards.assign( 1, &val );
571 node_type * pTail = guards.protect( 0, m_pTail, node_to_value() ) ; // Read the tail
573 pNew->m_pNext.store( pTail, memory_model::memory_order_release );
574 if ( m_pTail.compare_exchange_strong( pTail, pNew, memory_model::memory_order_release, atomics::memory_order_relaxed ) ) { // Try to CAS the tail
575 pTail->m_pPrev.store( pNew, memory_model::memory_order_release ) ; // Success, write prev
578 break ; // Enqueue done!
580 guards.assign( 0, node_traits::to_value_ptr( pTail ) ) ; // pTail has been changed by CAS above
581 m_Stat.onEnqueueRace();
587 /// Dequeues a value from the queue
588 /** @anchor cds_intrusive_OptimisticQueue_dequeue
589 If the queue is empty the function returns \p nullptr
592 The queue algorithm has following feature: when \p dequeue is called,
593 the item returning is still queue's top, and previous top is disposed:
596 before dequeuing Dequeue after dequeuing
597 +------------------+ +------------------+
598 Top ->| Item 1 | -> Dispose Item 1 | Item 2 | <- Top
599 +------------------+ +------------------+
600 | Item 2 | -> Return Item 2 | ... |
605 \p dequeue function returns Item 2, that becomes new top of queue, and calls
606 the disposer for Item 1, that was queue's top on function entry.
607 Thus, you cannot manually delete item returned because it is still included in
608 item sequence and it has valuable link field that must not be zeroed.
609 The item may be deleted only in disposer call.
611 value_type * dequeue()
614 if ( do_dequeue( res )) {
615 dispose_result( res );
617 return node_traits::to_value_ptr( *res.pNext );
622 /// Synonym for \p enqueue()
623 bool push( value_type& val )
625 return enqueue( val );
628 /// Synonym for \p dequeue()
634 /// Checks if the queue is empty
637 return m_pTail.load(memory_model::memory_order_relaxed) == m_pHead.load(memory_model::memory_order_relaxed);
642 The function repeatedly calls \ref dequeue until it returns \p nullptr.
643 The disposer defined in template \p Traits is called for each item
644 that can be safely disposed.
649 while ( (pv = dequeue()) != nullptr );
652 /// Returns queue's item count
654 The value returned depends on \p optimistic_queue::traits::item_counter.
655 For \p atomicity::empty_item_counter, this function always returns 0.
657 @note Even if you use real item counter and it returns 0, this fact is not mean that the queue
658 is empty. To check queue emptyness use \p empty() method.
662 return m_ItemCounter.value();
665 /// Returns refernce to internal statistics
666 const stat& statistics() const
672 }} // namespace cds::intrusive
674 #endif // #ifndef __CDS_INTRUSIVE_OPTIMISTIC_QUEUE_H