replace struct internal_disposer with lambda
[libcds.git] / cds / intrusive / msqueue.h
1 //$$CDS-header$$
2
3 #ifndef __CDS_INTRUSIVE_MSQUEUE_H
4 #define __CDS_INTRUSIVE_MSQUEUE_H
5
6 #include <type_traits>
7 #include <cds/intrusive/details/single_link_struct.h>
8 #include <cds/cxx11_atomic.h>
9
10 namespace cds { namespace intrusive {
11
12     /// MSQueue related definitions
13     /** @ingroup cds_intrusive_helper
14     */
15     namespace msqueue {
16
17         /// Queue node
18         /**
19             Template parameters:
20             - GC - garbage collector used
21             - Tag - a \ref cds_intrusive_hook_tag "tag"
22         */
23         template <class GC, typename Tag = opt::none >
24         using node = cds::intrusive::single_link::node< GC, Tag > ;
25
26         /// Base hook
27         /**
28             \p Options are:
29             - opt::gc - garbage collector used.
30             - opt::tag - a \ref cds_intrusive_hook_tag "tag"
31         */
32         template < typename... Options >
33         using base_hook = cds::intrusive::single_link::base_hook< Options...>;
34
35         /// Member hook
36         /**
37             \p MemberOffset specifies offset in bytes of \ref node member into your structure.
38             Use \p offsetof macro to define \p MemberOffset
39
40             \p Options are:
41             - opt::gc - garbage collector used.
42             - opt::tag - a \ref cds_intrusive_hook_tag "tag"
43         */
44         template < size_t MemberOffset, typename... Options >
45         using member_hook = cds::intrusive::single_link::member_hook< MemberOffset, Options... >;
46
47         /// Traits hook
48         /**
49             \p NodeTraits defines type traits for node.
50             See \ref node_traits for \p NodeTraits interface description
51
52             \p Options are:
53             - opt::gc - garbage collector used.
54             - opt::tag - a \ref cds_intrusive_hook_tag "tag"
55         */
56         template <typename NodeTraits, typename... Options >
57         using traits_hook = cds::intrusive::single_link::traits_hook< NodeTraits, Options... >;
58
59         /// Queue internal statistics. May be used for debugging or profiling
60         /**
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.
66         */
67         template <typename Counter = cds::atomicity::event_counter >
68         struct stat
69         {
70             typedef Counter     counter_type    ;   ///< Counter type
71
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"
78
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; }
91
92             //@cond
93             void reset()
94             {
95                 m_EnqueueCount.reset();
96                 m_DequeueCount.reset();
97                 m_EnqueueRace.reset();
98                 m_DequeueRace.reset();
99                 m_AdvanceTailError.reset();
100                 m_BadTail.reset();
101             }
102
103             stat& operator +=( stat const& s )
104             {
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();
111
112                 return *this;
113             }
114             //@endcond
115         };
116
117         /// Dummy queue statistics - no counting is performed, no overhead. Support interface like \p msqueue::stat
118         /** @ingroup cds_intrusive_helper
119         */
120         struct empty_stat
121         {
122             //@cond
123             void onEnqueue()                {}
124             void onDequeue()                {}
125             void onEnqueueRace()            {}
126             void onDequeueRace()            {}
127             void onAdvanceTailFailed()      {}
128             void onBadTail()                {}
129
130             void reset() {}
131             empty_stat& operator +=( empty_stat const& s )
132             {
133                 return *this;
134             }
135             //@endcond
136         };
137
138         /// MSQueue default type traits
139         struct traits
140         {
141             /// Back-off strategy
142             typedef cds::backoff::empty         back_off;
143
144             /// Hook, possible types are \p msqueue::base_hook, \p msqueue::member_hook, \p msqueue::traits_hook
145             typedef msqueue::base_hook<>        hook;
146
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;
149
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;
152
153             /// Internal statistics (by default, disabled)
154             /**
155                 Possible option value are: \p msqueue::stat, \p msqueue::empty_stat (the default),
156                 user-provided class that supports \p %msqueue::stat interface.
157             */
158             typedef msqueue::empty_stat         stat;
159
160             /// C++ memory ordering model
161             /** 
162                 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
163                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
164             */
165             typedef opt::v::relaxed_ordering    memory_model;
166
167             /// Link checking, see \p cds::opt::link_checker
168             static const opt::link_check_type link_checker = opt::debug_check_link;
169
170             /// Alignment of internal queue data. Default is \p opt::cache_line_alignment
171             enum { alignment = opt::cache_line_alignment };
172         };
173
174         /// Metafunction converting option list to \p msqueue::traits
175         /**
176             This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
177             Supported \p Options are:
178
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
183                 when dequeuing.
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).
193
194             Example: declare \p %MSQueue with item counting and internal statistics
195             \code
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<> >
200                 >::type
201             > myQueue;
202             \endcode
203         */
204         template <typename... Options>
205         struct make_traits {
206 #   ifdef CDS_DOXYGEN_INVOKED
207             typedef implementation_defined type;   ///< Metafunction result
208 #   else
209             typedef typename cds::opt::make_options<
210                 typename cds::opt::find_type_traits< traits, Options... >::type
211                 , Options...
212             >::type type;
213 #   endif
214         };
215
216
217     } // namespace msqueue
218
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"
223
224         Template arguments:
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:
231             \code
232             struct myTraits: public cds::intrusive::queue::traits {
233                 typedef cds::intrusive::msqueue::stat<> stat;
234                 typedef cds::atomicity::item_counter    item_counter;
235             };
236             typedef cds::intrusive::MSQueue< cds::gc::HP, Foo, myTraits > myQueue;
237
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 >
243                 >::type
244             > myQueue;
245             \endcode
246
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.
250
251         \par Examples
252         \code
253         #include <cds/intrusive/msqueue.h>
254         #include <cds/gc/hp.h>
255
256         namespace ci = cds::inrtusive;
257         typedef cds::gc::HP hp_gc;
258
259         // MSQueue with Hazard Pointer garbage collector, base hook + item disposer:
260         struct Foo: public ci::msqueue::node< hp_gc >
261         {
262             // Your data
263             ...
264         };
265
266         // Disposer for Foo struct just deletes the object passed in
267         struct fooDisposer {
268             void operator()( Foo * p )
269             {
270                 delete p;
271             }
272         };
273
274         // Declare traits for the queue
275         struct myTraits: public ci::msqueue::traits {
276             ,ci::opt::hook<
277                 ci::msqueue::base_hook< ci::opt::gc<hp_gc> >
278             >
279             ,ci::opt::disposer< fooDisposer >
280         };
281
282         // At least, declare the queue type
283         typedef ci::MSQueue< hp_gc, Foo, myTraits > fooQueue;
284
285         // Example 2:
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
290         struct Bar
291         {
292             // Your data
293             ...
294             ci::msqueue::node< hp_gc > hMember;
295         };
296
297         typedef ci::MSQueue< hp_gc,
298             Foo,
299             typename ci::msqueue::make_traits<
300                 ci::opt::hook<
301                     ci::msqueue::member_hook<
302                         offsetof(Bar, hMember)
303                         ,ci::opt::gc<hp_gc>
304                     >
305                 >
306                 ,ci::opt::disposer< fooDisposer >
307                 ,cds::opt::item_counter< cds::atomicity::item_counter >
308                 ,cds::opt::alignment< cds::opt::no_special_alignment >
309             >::type
310         > barQueue;
311         \endcode
312     */
313     template <typename GC, typename T, typename Traits>
314     class MSQueue
315     {
316     public:
317         typedef GC gc;          ///< Garbage collector
318         typedef T  value_type;  ///< type of value stored in the queue
319         typedef Traits traits;  ///< Queue traits
320
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
326
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
331
332         /// Rebind template arguments
333         template <typename GC2, typename T2, typename Traits2>
334         struct rebind {
335             typedef MSQueue< GC2, T2, Traits2 > other;   ///< Rebinding result
336         };
337
338     protected:
339         //@cond
340
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");
343
344         typedef intrusive::node_to_value<MSQueue> node_to_value;
345         typedef typename opt::details::alignment_setter< typename node_type::atomic_node_ptr, traits::alignment >::type aligned_node_ptr;
346
347         typedef typename opt::details::alignment_setter< node_type, traits::alignment >::type dummy_node_type;
348
349         aligned_node_ptr    m_pHead ;           ///< Queue's head pointer (cache-line aligned)
350         aligned_node_ptr    m_pTail ;           ///< Queue's tail pointer (cache-line aligned)
351         dummy_node_type     m_Dummy ;           ///< dummy node
352         item_counter        m_ItemCounter   ;   ///< Item counter
353         stat                m_Stat  ;           ///< Internal statistics
354         //@endcond
355
356         //@cond
357         struct dequeue_result {
358             typename gc::template GuardArray<2>  guards;
359
360             node_type * pHead;
361             node_type * pNext;
362         };
363
364         bool do_dequeue( dequeue_result& res )
365         {
366             node_type * pNext;
367             back_off bkoff;
368
369             node_type * h;
370             while ( true ) {
371                 h = res.guards.protect( 0, m_pHead, node_to_value() );
372                 pNext = h->m_pNext.load( memory_model::memory_order_relaxed );
373                 res.guards.assign( 1, node_to_value()( pNext ));
374                 if ( m_pHead.load(memory_model::memory_order_acquire) != h )
375                     continue;
376
377                 if ( pNext == nullptr )
378                     return false ;    // empty queue
379
380                 node_type * t = m_pTail.load(memory_model::memory_order_acquire);
381                 if ( h == t ) {
382                     // It is needed to help enqueue
383                     m_pTail.compare_exchange_strong( t, pNext, memory_model::memory_order_release, atomics::memory_order_relaxed );
384                     m_Stat.onBadTail();
385                     continue;
386                 }
387
388                 if ( m_pHead.compare_exchange_strong( h, pNext, memory_model::memory_order_release, atomics::memory_order_relaxed ))
389                     break;
390
391                 m_Stat.onDequeueRace();
392                 bkoff();
393             }
394
395             --m_ItemCounter;
396             m_Stat.onDequeue();
397
398             res.pHead = h;
399             res.pNext = pNext;
400             return true;
401         }
402
403         static void clear_links( node_type * pNode )
404         {
405             pNode->m_pNext.store( nullptr, memory_model::memory_order_release );
406         }
407
408         void dispose_result( dequeue_result& res )
409         {
410             dispose_node( res.pHead );
411         }
412
413         void dispose_node( node_type * p )
414         {
415             // Note for he dummy node:
416             // We cannot clear m_Dummy here since it leads to ABA.
417             // On the other hand, we cannot use deferred clear_links( &m_Dummy ) call via
418             // HP retiring cycle since m_Dummy is member of MSQueue and may be destroyed
419             // before HP retiring cycle invocation.
420             // So, we will never clear m_Dummy
421             if ( p != &m_Dummy ) {
422                 gc::retire( node_traits::to_value_ptr(p),
423                     []( value_type * ptr ) {
424                         assert( ptr != nullptr );
425                         MSQueue::clear_links( node_traits::to_node_ptr( ptr ) );
426                         disposer()(ptr);
427                     }
428                 );
429             }
430         }
431         //@endcond
432
433     public:
434         /// Initializes empty queue
435         MSQueue()
436             : m_pHead( &m_Dummy )
437             , m_pTail( &m_Dummy )
438         {}
439
440         /// Destructor clears the queue
441         /**
442             Since the Michael & Scott queue contains at least one item even
443             if the queue is empty, the destructor may call item disposer.
444         */
445         ~MSQueue()
446         {
447             clear();
448
449             node_type * pHead = m_pHead.load(memory_model::memory_order_relaxed);
450
451             assert( pHead != nullptr );
452             assert( pHead == m_pTail.load(memory_model::memory_order_relaxed) );
453
454             m_pHead.store( nullptr, memory_model::memory_order_relaxed );
455             m_pTail.store( nullptr, memory_model::memory_order_relaxed );
456
457             dispose_node( pHead );
458         }
459
460         /// Returns queue's item count
461         /**
462             The value returned depends on \p msqueue::traits::item_counter. For \p atomicity::empty_item_counter,
463             this function always returns 0.
464
465             @note Even if you use real item counter and it returns 0, this fact is not mean that the queue
466             is empty. To check queue emptyness use \p empty() method.
467         */
468         size_t size() const
469         {
470             return m_ItemCounter.value();
471         }
472
473         /// Returns reference to internal statistics
474         stat const& statistics() const
475         {
476             return m_Stat;
477         }
478
479         /// Enqueues \p val value into the queue.
480         /** @anchor cds_intrusive_MSQueue_enqueue
481             The function always returns \p true.
482         */
483         bool enqueue( value_type& val )
484         {
485             node_type * pNew = node_traits::to_node_ptr( val );
486             link_checker::is_empty( pNew );
487
488             typename gc::Guard guard;
489             back_off bkoff;
490
491             node_type * t;
492             while ( true ) {
493                 t = guard.protect( m_pTail, node_to_value() );
494
495                 node_type * pNext = t->m_pNext.load(memory_model::memory_order_acquire);
496                 if ( pNext != nullptr ) {
497                     // Tail is misplaced, advance it
498                     m_pTail.compare_exchange_weak( t, pNext, memory_model::memory_order_release, atomics::memory_order_relaxed );
499                     m_Stat.onBadTail();
500                     continue;
501                 }
502
503                 node_type * tmp = nullptr;
504                 if ( t->m_pNext.compare_exchange_strong( tmp, pNew, memory_model::memory_order_release, atomics::memory_order_relaxed ))
505                     break;
506
507                 m_Stat.onEnqueueRace();
508                 bkoff();
509             }
510             ++m_ItemCounter;
511             m_Stat.onEnqueue();
512
513             if ( !m_pTail.compare_exchange_strong( t, pNew, memory_model::memory_order_acq_rel, atomics::memory_order_relaxed ))
514                 m_Stat.onAdvanceTailFailed();
515             return true;
516         }
517
518         /// Dequeues a value from the queue
519         /** @anchor cds_intrusive_MSQueue_dequeue
520             If the queue is empty the function returns \p nullptr.
521
522             \par Warning
523             The queue algorithm has following feature: when \p %dequeue() is called,
524             the item returning is still queue's top, and previous top is disposed:
525
526             \code
527             before dequeuing         Dequeue               after dequeuing
528             +------------------+                           +------------------+
529       Top ->|      Item 1      |  -> Dispose Item 1        |      Item 2      | <- Top
530             +------------------+                           +------------------+
531             |      Item 2      |  -> Return Item 2         |       ...        |
532             +------------------+
533             |       ...        |
534             \endcode
535
536             \p %dequeue() function returns Item 2, that becomes new top of queue, and calls
537             the disposer for Item 1, that was queue's top on function entry.
538             Thus, you cannot manually delete item returned because it is still included in
539             item sequence and it has valuable link field that must not be zeroed.
540             The item should be deleted only in garbage collector retire cycle using the disposer.
541         */
542         value_type * dequeue()
543         {
544             dequeue_result res;
545
546             if ( do_dequeue( res )) {
547                 dispose_result( res );
548
549                 return node_traits::to_value_ptr( *res.pNext );
550             }
551             return nullptr;
552         }
553
554         /// Synonym for \ref cds_intrusive_MSQueue_enqueue "enqueue()" function
555         bool push( value_type& val )
556         {
557             return enqueue( val );
558         }
559
560         /// Synonym for \ref cds_intrusive_MSQueue_dequeue "dequeue()" function
561         value_type * pop()
562         {
563             return dequeue();
564         }
565
566         /// Checks if the queue is empty
567         bool empty() const
568         {
569             typename gc::Guard guard;
570             return guard.protect( m_pHead, node_to_value() )->m_pNext.load( memory_model::memory_order_relaxed ) == nullptr;
571         }
572
573         /// Clear the queue
574         /**
575             The function repeatedly calls \p dequeue() until it returns \p nullptr.
576             The disposer defined in template \p Traits is called for each item
577             that can be safely disposed.
578         */
579         void clear()
580         {
581             while ( dequeue() );
582         }
583     };
584
585 }} // namespace cds::intrusive
586
587 #endif // #ifndef __CDS_INTRUSIVE_MSQUEUE_H