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 - \p GC - garbage collector
22 - \p Tag - a \ref cds_intrusive_hook_tag "tag"
24 template <class GC, typename Tag = opt::none>
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 );
123 /// Metafunction for selecting appropriate link checking policy
124 template < typename Node, opt::link_check_type LinkType >
125 struct get_link_checker
128 typedef intrusive::opt::v::empty_link_checker<Node> type;
133 template < typename Node >
134 struct get_link_checker< Node, opt::always_check_link >
136 typedef link_checker<Node> type;
138 template < typename Node >
139 struct get_link_checker< Node, opt::debug_check_link >
142 typedef link_checker<Node> type;
144 typedef intrusive::opt::v::empty_link_checker<Node> type;
149 /// OptimisticQueue internal statistics. May be used for debugging or profiling
151 Template argument \p Counter defines type of counter.
152 Default is \p cds::atomicity::event_counter, that is weak, i.e. it is not guaranteed
153 strict event counting.
154 You may use stronger type of counter like as \p cds::atomicity::item_counter,
155 or even integral type, for example, \p int.
157 template <typename Counter = cds::atomicity::event_counter >
160 typedef Counter counter_type; ///< Counter type
162 counter_type m_EnqueueCount; ///< Enqueue call count
163 counter_type m_DequeueCount; ///< Dequeue call count
164 counter_type m_EnqueueRace; ///< Count of enqueue race conditions encountered
165 counter_type m_DequeueRace; ///< Count of dequeue race conditions encountered
166 counter_type m_AdvanceTailError; ///< Count of "advance tail failed" events
167 counter_type m_BadTail; ///< Count of events "Tail is not pointed to the last item in the queue"
168 counter_type m_FixListCount; ///< Count of fix list event
170 /// Register enqueue call
171 void onEnqueue() { ++m_EnqueueCount; }
172 /// Register dequeue call
173 void onDequeue() { ++m_DequeueCount; }
174 /// Register enqueue race event
175 void onEnqueueRace() { ++m_EnqueueRace; }
176 /// Register dequeue race event
177 void onDequeueRace() { ++m_DequeueRace; }
178 /// Register "advance tail failed" event
179 void onAdvanceTailFailed() { ++m_AdvanceTailError; }
180 /// Register event "Tail is not pointed to last item in the queue"
181 void onBadTail() { ++m_BadTail; }
182 /// Register fix list event
183 void onFixList() { ++m_FixListCount; }
188 m_EnqueueCount.reset();
189 m_DequeueCount.reset();
190 m_EnqueueRace.reset();
191 m_DequeueRace.reset();
192 m_AdvanceTailError.reset();
194 m_FixListCount.reset();
197 stat& operator +=( stat const& s )
199 m_EnqueueCount += s.m_EnqueueCount.get();
200 m_DequeueCount += s.m_DequeueCount.get();
201 m_EnqueueRace += s.m_EnqueueRace.get();
202 m_DequeueRace += s.m_DequeueRace.get();
203 m_AdvanceTailError += s.m_AdvanceTailError.get();
204 m_BadTail += s.m_BadTail.get();
205 m_FixListCount += s.m_FixListCount.get();
211 /// Dummy OptimisticQueue statistics - no counting is performed. Support interface like \ref optimistic_queue::stat
217 void onEnqueueRace() {}
218 void onDequeueRace() {}
219 void onAdvanceTailFailed() {}
224 empty_stat& operator +=( empty_stat const& )
231 /// OptimisticQueue default type traits
234 /// Back-off strategy
235 typedef cds::backoff::empty back_off;
237 /// Hook, possible types are \p optimistic_queue::base_hook, \p optimistic_queue::member_hook, \p optimistic_queue::traits_hook
238 typedef optimistic_queue::base_hook<> hook;
240 /// The functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used for dequeuing
241 typedef opt::v::empty_disposer disposer;
243 /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
244 typedef cds::atomicity::empty_item_counter item_counter;
246 /// C++ memory ordering model
248 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
249 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
251 typedef opt::v::relaxed_ordering memory_model;
253 /// Internal statistics (by default, disabled)
255 Possible option value are: \p optimistic_queue::stat, \p optimistic_queue::empty_stat (the default),
256 user-provided class that supports \p %optimistic_queue::stat interface.
258 typedef optimistic_queue::empty_stat stat;
260 /// Link checking, see \p cds::opt::link_checker
261 static CDS_CONSTEXPR const opt::link_check_type link_checker = opt::debug_check_link;
263 /// Alignment for internal queue data. Default is \p opt::cache_line_alignment
264 enum { alignment = opt::cache_line_alignment };
267 /// Metafunction converting option list to \p optimistic_queue::traits
269 Supported \p Options are:
271 - opt::hook - hook used. Possible hooks are: \p optimistic_queue::base_hook, \p optimistic_queue::member_hook, \p optimistic_queue::traits_hook.
272 If the option is not specified, \p %optimistic_queue::base_hook<> is used.
273 - opt::back_off - back-off strategy used, default is \p cds::backoff::empty.
274 - opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used
276 - opt::link_checker - the type of node's link fields checking. Default is \p opt::debug_check_link
277 - opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter (item counting disabled)
278 To enable item counting use \p cds::atomicity::item_counter
279 - opt::stat - the type to gather internal statistics.
280 Possible statistics types are: \p optimistic_queue::stat, \p optimistic_queue::empty_stat,
281 user-provided class that supports \p %optimistic_queue::stat interface.
282 Default is \p %optimistic_queue::empty_stat (internal statistics disabled).
283 - opt::alignment - the alignment for internal queue data. Default is \p opt::cache_line_alignment
284 - opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
285 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
287 Example: declare \p %OptimisticQueue with item counting and internal statistics
289 typedef cds::intrusive::OptimisticQueue< cds::gc::HP, Foo,
290 typename cds::intrusive::optimistic_queue::make_traits<
291 cds::intrusive::opt:hook< cds::intrusive::optimistic_queue::base_hook< cds::opt::gc<cds:gc::HP> >>,
292 cds::opt::item_counte< cds::atomicity::item_counter >,
293 cds::opt::stat< cds::intrusive::optimistic_queue::stat<> >
298 template <typename... Options>
300 # ifdef CDS_DOXYGEN_INVOKED
301 typedef implementation_defined type; ///< Metafunction result
303 typedef typename cds::opt::make_options<
304 typename cds::opt::find_type_traits< traits, Options... >::type
309 } // namespace optimistic_queue
311 /// Optimistic intruive lock-free queue
312 /** @ingroup cds_intrusive_queue
313 Implementation of Ladan-Mozes & Shavit optimistic queue algorithm.
314 [2008] Edya Ladan-Mozes, Nir Shavit "An Optimistic Approach to Lock-Free FIFO Queues"
317 - \p GC - garbage collector type: \p gc::HP, \p gc::DHP
318 - \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,
319 or it should have a member of type \p %optimistic_queue::node for \p optimistic_queue::member_hook,
320 or it should be convertible to \p %optimistic_queue::node for \p optimistic_queue::traits_hook.
321 - \p Traits - queue traits, default is \p optimistic_queue::traits. You can use \p optimistic_queue::make_traits
322 metafunction to make your traits or just derive your traits from \p %optimistic_queue::traits:
324 struct myTraits: public cds::intrusive::optimistic_queue::traits {
325 typedef cds::intrusive::optimistic_queue::stat<> stat;
326 typedef cds::atomicity::item_counter item_counter;
328 typedef cds::intrusive::OptimisticQueue< cds::gc::HP, Foo, myTraits > myQueue;
330 // Equivalent make_traits example:
331 typedef cds::intrusive::OptimisticQueue< cds::gc::HP, Foo,
332 typename cds::intrusive::optimistic_queue::make_traits<
333 cds::opt::stat< cds::intrusive::optimistic_queue::stat<> >,
334 cds::opt::item_counter< cds::atomicity::item_counter >
339 Garbage collecting schema \p GC must be consistent with the optimistic_queue::node GC.
341 \par About item disposing
342 The optimistic queue algo has a key feature: even if the queue is empty it contains one item that is "dummy" one from
343 the standpoint of the algo. See \p dequeue() function for explanation.
347 #include <cds/gc/hp.h>
348 #include <cds/intrusive/optimistic_queue.h>
350 namespace ci = cds::inrtusive;
351 typedef cds::gc::HP hp_gc;
353 // Optimistic queue with Hazard Pointer garbage collector, base hook + item counter:
354 struct Foo: public ci::optimistic_queue::node< hp_gc >
360 typedef ci::OptimisticQueue< hp_gc,
362 typename ci::optimistic_queue::make_traits<
364 ci::optimistic_queue::base_hook< ci::opt::gc< hp_gc > >
366 ,cds::opt::item_counter< cds::atomicity::item_counter >
370 // Optimistic queue with Hazard Pointer garbage collector, member hook, no item counter:
375 ci::optimistic_queue::node< hp_gc > hMember;
378 typedef ci::OptimisticQueue< hp_gc,
380 typename ci::optimistic_queue::make_traits<
382 ci::optimistic_queue::member_hook<
383 offsetof(Bar, hMember)
384 ,ci::opt::gc< hp_gc >
391 template <typename GC, typename T, typename Traits = optimistic_queue::traits >
392 class OptimisticQueue
395 typedef GC gc; ///< Garbage collector
396 typedef T value_type; ///< type of value to be stored in the queue
397 typedef Traits traits; ///< Queue traits
399 typedef typename traits::hook hook; ///< hook type
400 typedef typename hook::node_type node_type; ///< node type
401 typedef typename traits::disposer disposer; ///< disposer used
402 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
403 typedef typename optimistic_queue::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
404 typedef typename traits::back_off back_off; ///< back-off strategy
405 typedef typename traits::item_counter item_counter; ///< Item counting policy used
406 typedef typename traits::memory_model memory_model;///< Memory ordering. See cds::opt::memory_model option
407 typedef typename traits::stat stat; ///< Internal statistics policy used
409 /// Rebind template arguments
410 template <typename GC2, typename T2, typename Traits2>
412 typedef OptimisticQueue< GC2, T2, Traits2 > other ; ///< Rebinding result
417 typedef intrusive::node_to_value<OptimisticQueue> node_to_value;
418 typedef typename opt::details::alignment_setter< typename node_type::atomic_node_ptr, traits::alignment >::type aligned_node_ptr;
420 // GC and node_type::gc must be the same
421 static_assert((std::is_same<gc, typename node_type::gc>::value), "GC and node_type::gc must be the same");
425 aligned_node_ptr m_pTail ; ///< Pointer to tail node
426 aligned_node_ptr m_pHead ; ///< Pointer to head node
427 node_type m_Dummy ; ///< dummy node
428 item_counter m_ItemCounter ; ///< Item counter
429 stat m_Stat ; ///< Internal statistics
431 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 5 ; ///< Count of hazard pointer required for the algorithm
435 static void clear_links( node_type * pNode )
437 pNode->m_pNext.store( nullptr, memory_model::memory_order_release );
438 pNode->m_pPrev.store( nullptr, memory_model::memory_order_release );
441 struct dequeue_result {
442 typename gc::template GuardArray<3> guards;
448 bool do_dequeue( dequeue_result& res )
452 node_type * pFirstNodePrev;
455 while ( true ) { // Try till success or empty
456 pHead = res.guards.protect( 0, m_pHead, node_to_value() );
457 pTail = res.guards.protect( 1, m_pTail, node_to_value() );
458 assert( pHead != nullptr );
459 pFirstNodePrev = res.guards.protect( 2, pHead->m_pPrev, node_to_value() );
461 if ( pHead == m_pHead.load(memory_model::memory_order_relaxed)) {
462 if ( pTail != pHead ) {
463 if ( pFirstNodePrev == nullptr
464 || pFirstNodePrev->m_pNext.load(memory_model::memory_order_relaxed) != pHead )
466 fix_list( pTail, pHead );
469 if ( m_pHead.compare_exchange_weak( pHead, pFirstNodePrev, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
475 // the queue is empty
480 m_Stat.onDequeueRace();
488 res.pNext = pFirstNodePrev;
493 /// Helper function for optimistic queue. Corrects \p prev pointer of queue's nodes if it is needed
494 void fix_list( node_type * pTail, node_type * pHead )
496 // pTail and pHead are already guarded
498 node_type * pCurNode;
499 node_type * pCurNodeNext;
501 typename gc::template GuardArray<2> guards;
504 while ( pCurNode != pHead ) { // While not at head
505 pCurNodeNext = guards.protect(0, pCurNode->m_pNext, node_to_value() );
506 if ( pHead != m_pHead.load(memory_model::memory_order_relaxed) )
508 pCurNodeNext->m_pPrev.store( pCurNode, memory_model::memory_order_release );
509 guards.assign( 1, node_traits::to_value_ptr( pCurNode = pCurNodeNext ));
515 void dispose_result( dequeue_result& res )
517 dispose_node( res.pHead );
520 void dispose_node( node_type * p )
522 assert( p != nullptr );
524 if ( p != &m_Dummy ) {
525 struct internal_disposer
527 void operator ()( value_type * p )
529 assert( p != nullptr );
531 OptimisticQueue::clear_links( node_traits::to_node_ptr( *p ) );
535 gc::template retire<internal_disposer>( node_traits::to_value_ptr(p) );
542 /// Constructor creates empty queue
544 : m_pTail( &m_Dummy )
545 , m_pHead( &m_Dummy )
551 node_type * pHead = m_pHead.load(memory_model::memory_order_relaxed);
552 CDS_DEBUG_ONLY( node_type * pTail = m_pTail.load(memory_model::memory_order_relaxed); )
553 CDS_DEBUG_ONLY( assert( pHead == pTail ); )
554 assert( pHead != nullptr );
556 m_pHead.store( nullptr, memory_model::memory_order_relaxed );
557 m_pTail.store( nullptr, memory_model::memory_order_relaxed );
559 dispose_node( pHead );
562 /// @anchor cds_intrusive_OptimisticQueue_enqueue Enqueues \p data in lock-free manner. Always return \a true
563 bool enqueue( value_type& val )
565 node_type * pNew = node_traits::to_node_ptr( val );
566 link_checker::is_empty( pNew );
568 typename gc::template GuardArray<2> guards;
571 guards.assign( 1, &val );
572 node_type * pTail = guards.protect( 0, m_pTail, node_to_value() ) ; // Read the tail
574 pNew->m_pNext.store( pTail, memory_model::memory_order_release );
575 if ( m_pTail.compare_exchange_strong( pTail, pNew, memory_model::memory_order_release, atomics::memory_order_relaxed ) ) { // Try to CAS the tail
576 pTail->m_pPrev.store( pNew, memory_model::memory_order_release ) ; // Success, write prev
579 break ; // Enqueue done!
581 guards.assign( 0, node_traits::to_value_ptr( pTail ) ) ; // pTail has been changed by CAS above
582 m_Stat.onEnqueueRace();
588 /// Dequeues a value from the queue
589 /** @anchor cds_intrusive_OptimisticQueue_dequeue
590 If the queue is empty the function returns \p nullptr
593 The queue algorithm has following feature: when \p dequeue is called,
594 the item returning is still queue's top, and previous top is disposed:
597 before dequeuing Dequeue after dequeuing
598 +------------------+ +------------------+
599 Top ->| Item 1 | -> Dispose Item 1 | Item 2 | <- Top
600 +------------------+ +------------------+
601 | Item 2 | -> Return Item 2 | ... |
606 \p dequeue function returns Item 2, that becomes new top of queue, and calls
607 the disposer for Item 1, that was queue's top on function entry.
608 Thus, you cannot manually delete item returned because it is still included in
609 item sequence and it has valuable link field that must not be zeroed.
610 The item may be deleted only in disposer call.
612 value_type * dequeue()
615 if ( do_dequeue( res )) {
616 dispose_result( res );
618 return node_traits::to_value_ptr( *res.pNext );
623 /// Synonym for \p enqueue()
624 bool push( value_type& val )
626 return enqueue( val );
629 /// Synonym for \p dequeue()
635 /// Checks if the queue is empty
638 return m_pTail.load(memory_model::memory_order_relaxed) == m_pHead.load(memory_model::memory_order_relaxed);
643 The function repeatedly calls \ref dequeue until it returns \p nullptr.
644 The disposer defined in template \p Traits is called for each item
645 that can be safely disposed.
650 while ( (pv = dequeue()) != nullptr );
653 /// Returns queue's item count
655 The value returned depends on \p optimistic_queue::traits::item_counter.
656 For \p atomicity::empty_item_counter, this function always returns 0.
658 @note Even if you use real item counter and it returns 0, this fact is not mean that the queue
659 is empty. To check queue emptyness use \p empty() method.
663 return m_ItemCounter.value();
666 /// Returns refernce to internal statistics
667 const stat& statistics() const
673 }} // namespace cds::intrusive
675 #endif // #ifndef __CDS_INTRUSIVE_OPTIMISTIC_QUEUE_H