3 #ifndef CDSLIB_INTRUSIVE_OPTIMISTIC_QUEUE_H
4 #define CDSLIB_INTRUSIVE_OPTIMISTIC_QUEUE_H
7 #include <cds/intrusive/details/base.h>
8 #include <cds/algo/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_pNext ; ///< Pointer to next node
33 atomic_node_ptr m_pPrev ; ///< Pointer to previous 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
169 counter_type m_EmptyDequeue; ///< Count of dequeue from empty queue
171 /// Register enqueue call
172 void onEnqueue() { ++m_EnqueueCount; }
173 /// Register dequeue call
174 void onDequeue() { ++m_DequeueCount; }
175 /// Register enqueue race event
176 void onEnqueueRace() { ++m_EnqueueRace; }
177 /// Register dequeue race event
178 void onDequeueRace() { ++m_DequeueRace; }
179 /// Register "advance tail failed" event
180 void onAdvanceTailFailed() { ++m_AdvanceTailError; }
181 /// Register event "Tail is not pointed to last item in the queue"
182 void onBadTail() { ++m_BadTail; }
183 /// Register fix list event
184 void onFixList() { ++m_FixListCount; }
185 /// Register dequeuing from empty queue
186 void onEmptyDequeue() { ++m_EmptyDequeue; }
191 m_EnqueueCount.reset();
192 m_DequeueCount.reset();
193 m_EnqueueRace.reset();
194 m_DequeueRace.reset();
195 m_AdvanceTailError.reset();
197 m_FixListCount.reset();
198 m_EmptyDequeue.reset();
201 stat& operator +=( stat const& s )
203 m_EnqueueCount += s.m_EnqueueCount.get();
204 m_DequeueCount += s.m_DequeueCount.get();
205 m_EnqueueRace += s.m_EnqueueRace.get();
206 m_DequeueRace += s.m_DequeueRace.get();
207 m_AdvanceTailError += s.m_AdvanceTailError.get();
208 m_BadTail += s.m_BadTail.get();
209 m_FixListCount += s.m_FixListCount.get();
210 m_EmptyDequeue += s.m_EmptyDequeue.get();
217 /// Dummy OptimisticQueue statistics - no counting is performed. Support interface like \ref optimistic_queue::stat
221 void onEnqueue() const {}
222 void onDequeue() const {}
223 void onEnqueueRace() const {}
224 void onDequeueRace() const {}
225 void onAdvanceTailFailed() const {}
226 void onBadTail() const {}
227 void onFixList() const {}
228 void onEmptyDequeue() const {}
231 empty_stat& operator +=( empty_stat const& )
238 /// OptimisticQueue default type traits
241 /// Back-off strategy
242 typedef cds::backoff::empty back_off;
244 /// Hook, possible types are \p optimistic_queue::base_hook, \p optimistic_queue::member_hook, \p optimistic_queue::traits_hook
245 typedef optimistic_queue::base_hook<> hook;
247 /// The functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used for dequeuing
248 typedef opt::v::empty_disposer disposer;
250 /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
251 typedef cds::atomicity::empty_item_counter item_counter;
253 /// C++ memory ordering model
255 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
256 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
258 typedef opt::v::relaxed_ordering memory_model;
260 /// Internal statistics (by default, disabled)
262 Possible option value are: \p optimistic_queue::stat, \p optimistic_queue::empty_stat (the default),
263 user-provided class that supports \p %optimistic_queue::stat interface.
265 typedef optimistic_queue::empty_stat stat;
267 /// Link checking, see \p cds::opt::link_checker
268 static CDS_CONSTEXPR const opt::link_check_type link_checker = opt::debug_check_link;
270 /// Padding for internal critical atomic data. Default is \p opt::cache_line_padding
271 enum { padding = opt::cache_line_padding };
274 /// Metafunction converting option list to \p optimistic_queue::traits
276 Supported \p Options are:
278 - \p opt::hook - hook used. Possible hooks are: \p optimistic_queue::base_hook, \p optimistic_queue::member_hook, \p optimistic_queue::traits_hook.
279 If the option is not specified, \p %optimistic_queue::base_hook<> is used.
280 - \p opt::back_off - back-off strategy used, default is \p cds::backoff::empty.
281 - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used
283 - \p opt::link_checker - the type of node's link fields checking. Default is \p opt::debug_check_link
284 - \p opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter (item counting disabled)
285 To enable item counting use \p cds::atomicity::item_counter
286 - \p opt::stat - the type to gather internal statistics.
287 Possible statistics types are: \p optimistic_queue::stat, \p optimistic_queue::empty_stat,
288 user-provided class that supports \p %optimistic_queue::stat interface.
289 Default is \p %optimistic_queue::empty_stat (internal statistics disabled).
290 - \p opt::padding - padding for internal critical atomic data. Default is \p opt::cache_line_padding
291 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
292 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
294 Example: declare \p %OptimisticQueue with item counting and internal statistics
296 typedef cds::intrusive::OptimisticQueue< cds::gc::HP, Foo,
297 typename cds::intrusive::optimistic_queue::make_traits<
298 cds::intrusive::opt:hook< cds::intrusive::optimistic_queue::base_hook< cds::opt::gc<cds:gc::HP> >>,
299 cds::opt::item_counte< cds::atomicity::item_counter >,
300 cds::opt::stat< cds::intrusive::optimistic_queue::stat<> >
305 template <typename... Options>
307 # ifdef CDS_DOXYGEN_INVOKED
308 typedef implementation_defined type; ///< Metafunction result
310 typedef typename cds::opt::make_options<
311 typename cds::opt::find_type_traits< traits, Options... >::type
316 } // namespace optimistic_queue
318 /// Optimistic intruive lock-free queue
319 /** @ingroup cds_intrusive_queue
320 Implementation of Ladan-Mozes & Shavit optimistic queue algorithm.
321 [2008] Edya Ladan-Mozes, Nir Shavit "An Optimistic Approach to Lock-Free FIFO Queues"
324 - \p GC - garbage collector type: \p gc::HP, \p gc::DHP
325 - \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,
326 or it should have a member of type \p %optimistic_queue::node for \p optimistic_queue::member_hook,
327 or it should be convertible to \p %optimistic_queue::node for \p optimistic_queue::traits_hook.
328 - \p Traits - queue traits, default is \p optimistic_queue::traits. You can use \p optimistic_queue::make_traits
329 metafunction to make your traits or just derive your traits from \p %optimistic_queue::traits:
331 struct myTraits: public cds::intrusive::optimistic_queue::traits {
332 typedef cds::intrusive::optimistic_queue::stat<> stat;
333 typedef cds::atomicity::item_counter item_counter;
335 typedef cds::intrusive::OptimisticQueue< cds::gc::HP, Foo, myTraits > myQueue;
337 // Equivalent make_traits example:
338 typedef cds::intrusive::OptimisticQueue< cds::gc::HP, Foo,
339 typename cds::intrusive::optimistic_queue::make_traits<
340 cds::opt::stat< cds::intrusive::optimistic_queue::stat<> >,
341 cds::opt::item_counter< cds::atomicity::item_counter >
346 Garbage collecting schema \p GC must be consistent with the optimistic_queue::node GC.
348 \par About item disposing
349 The optimistic queue algo has a key feature: even if the queue is empty it contains one item that is "dummy" one from
350 the standpoint of the algo. See \p dequeue() function for explanation.
354 #include <cds/gc/hp.h>
355 #include <cds/intrusive/optimistic_queue.h>
357 namespace ci = cds::inrtusive;
358 typedef cds::gc::HP hp_gc;
360 // Optimistic queue with Hazard Pointer garbage collector, base hook + item counter:
361 struct Foo: public ci::optimistic_queue::node< hp_gc >
367 typedef ci::OptimisticQueue< hp_gc,
369 typename ci::optimistic_queue::make_traits<
371 ci::optimistic_queue::base_hook< ci::opt::gc< hp_gc > >
373 ,cds::opt::item_counter< cds::atomicity::item_counter >
377 // Optimistic queue with Hazard Pointer garbage collector, member hook, no item counter:
382 ci::optimistic_queue::node< hp_gc > hMember;
385 typedef ci::OptimisticQueue< hp_gc,
387 typename ci::optimistic_queue::make_traits<
389 ci::optimistic_queue::member_hook<
390 offsetof(Bar, hMember)
391 ,ci::opt::gc< hp_gc >
398 template <typename GC, typename T, typename Traits = optimistic_queue::traits >
399 class OptimisticQueue
402 typedef GC gc; ///< Garbage collector
403 typedef T value_type; ///< type of value to be stored in the queue
404 typedef Traits traits; ///< Queue traits
406 typedef typename traits::hook hook; ///< hook type
407 typedef typename hook::node_type node_type; ///< node type
408 typedef typename traits::disposer disposer; ///< disposer used
409 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
410 typedef typename optimistic_queue::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
411 typedef typename traits::back_off back_off; ///< back-off strategy
412 typedef typename traits::item_counter item_counter; ///< Item counting policy used
413 typedef typename traits::memory_model memory_model;///< Memory ordering. See cds::opt::memory_model option
414 typedef typename traits::stat stat; ///< Internal statistics policy used
416 /// Rebind template arguments
417 template <typename GC2, typename T2, typename Traits2>
419 typedef OptimisticQueue< GC2, T2, Traits2 > other ; ///< Rebinding result
424 typedef typename node_type::atomic_node_ptr atomic_node_ptr;
426 // GC and node_type::gc must be the same
427 static_assert((std::is_same<gc, typename node_type::gc>::value), "GC and node_type::gc must be the same");
430 atomic_node_ptr m_pTail; ///< Pointer to tail node
432 typename opt::details::apply_padding< atomic_node_ptr, traits::padding >::padding_type pad1_;
434 atomic_node_ptr m_pHead; ///< Pointer to head node
436 typename opt::details::apply_padding< atomic_node_ptr, traits::padding >::padding_type pad2_;
438 node_type m_Dummy ; ///< dummy node
440 typename opt::details::apply_padding< atomic_node_ptr, traits::padding >::padding_type pad3_;
442 item_counter m_ItemCounter ; ///< Item counter
443 stat m_Stat ; ///< Internal statistics
445 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 5 ; ///< Count of hazard pointer required for the algorithm
449 static void clear_links( node_type * pNode )
451 pNode->m_pNext.store( nullptr, memory_model::memory_order_release );
452 pNode->m_pPrev.store( nullptr, memory_model::memory_order_release );
455 struct dequeue_result {
456 typename gc::template GuardArray<3> guards;
462 bool do_dequeue( dequeue_result& res )
466 node_type * pFirstNodePrev;
469 while ( true ) { // Try till success or empty
470 pHead = res.guards.protect( 0, m_pHead, [](node_type * p) -> value_type * {return node_traits::to_value_ptr(p);});
471 pTail = res.guards.protect( 1, m_pTail, [](node_type * p) -> value_type * {return node_traits::to_value_ptr(p);});
472 assert( pHead != nullptr );
473 pFirstNodePrev = res.guards.protect( 2, pHead->m_pPrev, [](node_type * p) -> value_type * {return node_traits::to_value_ptr(p);});
475 if ( pHead == m_pHead.load(memory_model::memory_order_acquire)) {
476 if ( pTail != pHead ) {
477 if ( pFirstNodePrev == nullptr
478 || pFirstNodePrev->m_pNext.load(memory_model::memory_order_acquire) != pHead )
480 fix_list( pTail, pHead );
483 if ( m_pHead.compare_exchange_weak( pHead, pFirstNodePrev, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
489 // the queue is empty
490 m_Stat.onEmptyDequeue();
495 m_Stat.onDequeueRace();
503 res.pNext = pFirstNodePrev;
508 /// Helper function for optimistic queue. Corrects \p prev pointer of queue's nodes if it is needed
509 void fix_list( node_type * pTail, node_type * pHead )
511 // pTail and pHead are already guarded
513 node_type * pCurNode;
514 node_type * pCurNodeNext;
516 typename gc::template GuardArray<2> guards;
519 while ( pCurNode != pHead ) { // While not at head
520 pCurNodeNext = guards.protect(0, pCurNode->m_pNext, [](node_type * p) -> value_type * { return node_traits::to_value_ptr(p);});
521 if ( pHead != m_pHead.load(memory_model::memory_order_acquire))
523 pCurNodeNext->m_pPrev.store( pCurNode, memory_model::memory_order_release );
524 guards.assign( 1, node_traits::to_value_ptr( pCurNode = pCurNodeNext ));
530 void dispose_result( dequeue_result& res )
532 dispose_node( res.pHead );
535 void dispose_node( node_type * p )
537 assert( p != nullptr );
539 if ( p != &m_Dummy ) {
540 struct internal_disposer
542 void operator ()( value_type * p )
544 assert( p != nullptr );
546 OptimisticQueue::clear_links( node_traits::to_node_ptr( *p ) );
550 gc::template retire<internal_disposer>( node_traits::to_value_ptr(p) );
557 /// Constructor creates empty queue
559 : m_pTail( &m_Dummy )
560 , m_pHead( &m_Dummy )
566 node_type * pHead = m_pHead.load(memory_model::memory_order_relaxed);
567 CDS_DEBUG_ONLY( node_type * pTail = m_pTail.load(memory_model::memory_order_relaxed); )
568 CDS_DEBUG_ONLY( assert( pHead == pTail ); )
569 assert( pHead != nullptr );
571 m_pHead.store( nullptr, memory_model::memory_order_relaxed );
572 m_pTail.store( nullptr, memory_model::memory_order_relaxed );
574 dispose_node( pHead );
577 /// @anchor cds_intrusive_OptimisticQueue_enqueue Enqueues \p data in lock-free manner. Always return \a true
578 bool enqueue( value_type& val )
580 node_type * pNew = node_traits::to_node_ptr( val );
581 link_checker::is_empty( pNew );
583 typename gc::template GuardArray<2> guards;
586 guards.assign( 1, &val );
587 node_type * pTail = guards.protect( 0, m_pTail, [](node_type * p) -> value_type * {return node_traits::to_value_ptr(p);} ); // Read the tail
589 pNew->m_pNext.store( pTail, memory_model::memory_order_release );
590 if ( m_pTail.compare_exchange_strong( pTail, pNew, memory_model::memory_order_release, atomics::memory_order_relaxed )) { // Try to CAS the tail
591 pTail->m_pPrev.store( pNew, memory_model::memory_order_release ); // Success, write prev
594 break; // Enqueue done!
596 guards.assign( 0, node_traits::to_value_ptr( pTail )); // pTail has been changed by CAS above
597 m_Stat.onEnqueueRace();
603 /// Dequeues a value from the queue
604 /** @anchor cds_intrusive_OptimisticQueue_dequeue
605 If the queue is empty the function returns \p nullptr
608 The queue algorithm has following feature: when \p dequeue is called,
609 the item returning is still queue's top, and previous top is disposed:
612 before dequeuing Dequeue after dequeuing
613 +------------------+ +------------------+
614 Top ->| Item 1 | -> Dispose Item 1 | Item 2 | <- Top
615 +------------------+ +------------------+
616 | Item 2 | -> Return Item 2 | ... |
621 \p dequeue function returns Item 2, that becomes new top of queue, and calls
622 the disposer for Item 1, that was queue's top on function entry.
623 Thus, you cannot manually delete item returned because it is still included in
624 item sequence and it has valuable link field that must not be zeroed.
625 The item may be deleted only in disposer call.
627 value_type * dequeue()
630 if ( do_dequeue( res )) {
631 dispose_result( res );
633 return node_traits::to_value_ptr( *res.pNext );
638 /// Synonym for \p enqueue()
639 bool push( value_type& val )
641 return enqueue( val );
644 /// Synonym for \p dequeue()
650 /// Checks if the queue is empty
653 return m_pTail.load(memory_model::memory_order_relaxed) == m_pHead.load(memory_model::memory_order_relaxed);
658 The function repeatedly calls \ref dequeue until it returns \p nullptr.
659 The disposer defined in template \p Traits is called for each item
660 that can be safely disposed.
665 while ( (pv = dequeue()) != nullptr );
668 /// Returns queue's item count
670 The value returned depends on \p optimistic_queue::traits::item_counter.
671 For \p atomicity::empty_item_counter, this function always returns 0.
673 @note Even if you use real item counter and it returns 0, this fact is not mean that the queue
674 is empty. To check queue emptyness use \p empty() method.
678 return m_ItemCounter.value();
681 /// Returns refernce to internal statistics
682 const stat& statistics() const
688 }} // namespace cds::intrusive
690 #endif // #ifndef CDSLIB_INTRUSIVE_OPTIMISTIC_QUEUE_H