cds/intrusive/vyukov_mpmc_cycle_queue.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_INTRUSIVE_VYUKOV_MPMC_CYCLE_QUEUE_H
   4 #define __CDS_INTRUSIVE_VYUKOV_MPMC_CYCLE_QUEUE_H
   5
   6 #include <cds/intrusive/base.h>
   7 #include <cds/container/vyukov_mpmc_cycle_queue.h>
   8
   9 namespace cds { namespace intrusive {
  10
  11     /// Vyukov's MPMC bounded queue
  12     /** @ingroup cds_intrusive_queue
  13         This algorithm is developed by Dmitry Vyukov (see http://www.1024cores.net)
  14
  15         Implementation of intrusive version is based on non-intrusive class container::VyukovMPMCCycleQueue.
  16
  17         Template parameters:
  18         - \p T - type stored in queue.
  19         - \p Options - queue's options
  20
  21         Options \p Options are:
  22         - opt::buffer - buffer to store items. Mandatory option, see option description for full list of possible types.
  23         - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter
  24         - opt::disposer - the functor used for dispose removed items. Default is opt::v::empty_disposer. This option is used
  25             only in \ref clear function.
  26         - opt::alignment - the alignment for internal queue data. Default is opt::cache_line_alignment
  27         - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
  28             or opt::v::sequential_consistent (sequentially consisnent memory model).
  29
  30
  31         Instead of saving copy of enqueued data, the intrusive implementation stores pointer to passed data.
  32
  33         \par Examples:
  34         \code
  35         #include <cds/intrusive/vyukov_mpmc_cycle_queue.h>
  36
  37         struct Foo {
  38             ...
  39         };
  40
  41         // Queue of Foo pointers, capacity is 1024, statically allocated buffer:
  42         typedef cds::intrusive::VyukovMPMCCycleQueue<
  43             Foo
  44             ,cds::opt::buffer< cds::opt::v::static_buffer< Foo, 1024 > >
  45         > static_queue;
  46         static_queue    stQueue;
  47
  48         // Queue of Foo pointers, capacity is 1024, dynamically allocated buffer:
  49         typedef cds::intrusive::VyukovMPMCCycleQueue<
  50             Foo
  51             ,cds::opt::buffer< cds::opt::v::dynamic_buffer< Foo > >
  52         > dynamic_queue;
  53         dynamic_queue    dynQueue( 1024 );
  54
  55         \endcode
  56     */
  57     template <typename T, CDS_DECL_OPTIONS6>
  58     class VyukovMPMCCycleQueue
  59         : private container::VyukovMPMCCycleQueue< T *, CDS_OPTIONS6 >
  60     {
  61         //@cond
  62         typedef container::VyukovMPMCCycleQueue< T *, CDS_OPTIONS6 > base_class;
  63         //@endcond
  64     public:
  65         typedef T value_type    ;   ///< type of data stored in the queue
  66         typedef typename base_class::item_counter   item_counter    ;   ///< Item counter type
  67         typedef typename base_class::memory_model   memory_model    ;   ///< Memory ordering. See cds::opt::memory_model option
  68         typedef typename base_class::options::disposer disposer     ;   ///< Item disposer
  69
  70         //@cond
  71         typedef typename base_class::options    options;
  72         //@endcond
  73
  74     public:
  75         /// Rebind template arguments
  76         template <typename T2, CDS_DECL_OTHER_OPTIONS6>
  77         struct rebind {
  78             typedef VyukovMPMCCycleQueue< T2, CDS_OTHER_OPTIONS6> other   ;   ///< Rebinding result
  79         };
  80
  81     public:
  82         /// Constructs the queue of capacity \p nCapacity
  83         /**
  84             For cds::opt::v::static_buffer the \p nCapacity parameter is ignored.
  85         */
  86         VyukovMPMCCycleQueue( size_t nCapacity = 0 )
  87             : base_class( nCapacity )
  88         {}
  89
  90         /// Enqueues \p data to queue
  91         /**
  92             Note that the intrusive queue stores pointer to \p data passed, not the copy of data.
  93         */
  94         bool enqueue( value_type& data )
  95         {
  96             return base_class::enqueue( &data );
  97         }
  98
  99         /// Dequeues an item from queue
 100         /**
 101             If queue is empty, returns \p NULL.
 102         */
 103         value_type * dequeue()
 104         {
 105             value_type * p = nullptr;
 106             return base_class::dequeue( p ) ? p : nullptr;
 107         }
 108
 109         /// Synonym of \ref enqueue
 110         bool push( value_type& data )
 111         {
 112             return enqueue( data );
 113         }
 114
 115         /// Synonym of \ref dequeue
 116         value_type * pop()
 117         {
 118             return dequeue();
 119         }
 120
 121         /// Clears queue in lock-free manner.
 122         /**
 123             \p f parameter is a functor to dispose removed items.
 124             The interface of \p DISPOSER is:
 125             \code
 126             struct myDisposer {
 127                 void operator ()( T * val );
 128             };
 129             \endcode
 130             You can pass \p disposer by reference using \p boost::ref.
 131             The disposer will be called immediately for each item.
 132         */
 133         template <typename Disposer>
 134         void clear( Disposer f )
 135         {
 136             value_type * pv;
 137             while ( (pv = pop()) != nullptr ) {
 138                 unref(f)( pv );
 139             }
 140         }
 141
 142         /// Clears the queue
 143         /**
 144             This function uses the disposer that is specified in \p Options.
 145         */
 146         void clear()
 147         {
 148             clear( disposer() );
 149         }
 150
 151         /// Checks if the queue is empty
 152         bool empty() const
 153         {
 154             return base_class::empty();
 155         }
 156
 157
 158         /// Returns queue's item count
 159         /**
 160             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 161             this function always returns 0.
 162         */
 163         size_t size() const
 164         {
 165             return base_class::size();
 166         }
 167
 168         /// Returns capacity of cyclic buffer
 169         size_t capacity() const
 170         {
 171             return base_class::capacity();
 172         }
 173     };
 174 }}  // namespace cds::intrusive
 175
 176 #endif // #ifndef __CDS_INTRUSIVE_VYUKOV_MPMC_CYCLE_QUEUE_H