cds/intrusive/vyukov_mpmc_cycle_queue.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_INTRUSIVE_VYUKOV_MPMC_CYCLE_QUEUE_H
   4 #define CDSLIB_INTRUSIVE_VYUKOV_MPMC_CYCLE_QUEUE_H
   5
   6 #include <cds/intrusive/details/base.h>
   7 #include <cds/container/vyukov_mpmc_cycle_queue.h>
   8
   9 namespace cds { namespace intrusive {
  10
  11     /// VyukovMPMCCycleQueue related definitions
  12     /** @ingroup cds_intrusive_helper
  13     */
  14     namespace vyukov_queue {
  15
  16         /// VyukovMPMCCycleQueue traits
  17         struct traits : public cds::container::vyukov_queue::traits
  18         {
  19             /// The functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used only in \p clear()
  20             typedef opt::v::empty_disposer  disposer;
  21         };
  22
  23         /// Metafunction converting option list to \p vyukov_queue::traits
  24         /**
  25             Supported \p Options are:
  26             - \p opt::buffer - the buffer type for internal cyclic array. Possible types are:
  27                 \p opt::v::dynamic_buffer (the default), \p opt::v::static_buffer. The type of
  28                 element in the buffer is not important: it will be changed via \p rebind metafunction.
  29             - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer.
  30                 This option is used only in \p clear() member function.
  31             - \p opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter (item counting disabled)
  32                 To enable item counting use \p cds::atomicity::item_counter
  33             - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
  34             - \p opt::padding - padding for internal critical atomic data. Default is \p opt::cache_line_padding
  35             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
  36                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
  37
  38             Example: declare \p %VyukovMPMCCycleQueue with item counting and static iternal buffer of size 1024:
  39             \code
  40             typedef cds::intrusive::VyukovMPMCCycleQueue< Foo,
  41                 typename cds::intrusive::vyukov_queue::make_traits<
  42                     cds::opt::buffer< cds::opt::v::static_buffer< void *, 1024 >,
  43                     cds::opt::item_counter< cds::atomicity::item_counter >
  44                 >::type
  45             > myQueue;
  46             \endcode
  47         */
  48         template <typename... Options>
  49         struct make_traits {
  50 #   ifdef CDS_DOXYGEN_INVOKED
  51             typedef implementation_defined type;   ///< Metafunction result
  52 #   else
  53             typedef typename cds::opt::make_options<
  54                 typename cds::opt::find_type_traits< traits, Options... >::type
  55                 , Options...
  56             >::type type;
  57 #   endif
  58         };
  59
  60     } // namespace vyukov_queue
  61
  62     /// Vyukov's MPMC bounded queue
  63     /** @ingroup cds_intrusive_queue
  64         This algorithm is developed by Dmitry Vyukov (see http://www.1024cores.net)
  65
  66         Implementation of intrusive version is based on container::VyukovMPMCCycleQueue.
  67
  68         Template parameters:
  69         - \p T - type stored in queue.
  70         - \p Traits - queue traits, default is \p vykov_queue::traits. You can use \p vykov_queue::make_traits
  71             metafunction to make your traits or just derive your traits from \p %vykov_queue::traits:
  72             \code
  73             struct myTraits: public cds::intrusive::vykov_queue::traits {
  74                 typedef cds::atomicity::item_counter    item_counter;
  75             };
  76             typedef cds::intrusive::VyukovMPMCCycleQueue< Foo, myTraits > myQueue;
  77
  78             // Equivalent make_traits example:
  79             typedef cds::intrusive::VyukovMPMCCycleQueue< cds::gc::HP, Foo,
  80                 typename cds::intrusive::vykov_queue::make_traits<
  81                     cds::opt::item_counter< cds::atomicity::item_counter >
  82                 >::type
  83             > myQueue;
  84             \endcode
  85
  86         Instead of saving copy of enqueued data, the intrusive implementation stores pointer to passed data.
  87
  88         \par Examples:
  89         \code
  90         #include <cds/intrusive/vyukov_mpmc_cycle_queue.h>
  91
  92         struct Foo {
  93             ...
  94         };
  95
  96         // Queue of Foo pointers, capacity is 1024, statically allocated buffer:
  97         typedef cds::intrusive::VyukovMPMCCycleQueue< Foo,
  98             typename cds::intrusive::vyukov_queue::make_traits<
  99                 cds::opt::buffer< cds::opt::v::static_buffer< Foo, 1024 > >
 100             >::type
 101         > static_queue;
 102         static_queue    stQueue;
 103
 104         // Queue of Foo pointers, capacity is 1024, dynamically allocated buffer:
 105         struct queue_traits: public cds::intrusive::vyukov_queue::traits
 106         {
 107             typedef cds::opt::v::dynamic_buffer< Foo > buffer;
 108         };
 109         typedef cds::intrusive::VyukovMPMCCycleQueue< Foo, queue_traits > dynamic_queue;
 110         dynamic_queue    dynQueue( 1024 );
 111         \endcode
 112     */
 113     template <typename T, typename Traits = vyukov_queue::traits >
 114     class VyukovMPMCCycleQueue
 115         : private container::VyukovMPMCCycleQueue< T*, Traits >
 116     {
 117         //@cond
 118         typedef container::VyukovMPMCCycleQueue< T*, Traits > base_class;
 119         //@endcond
 120     public:
 121         typedef T value_type;   ///< type of data to be stored in the queue
 122         typedef Traits traits;  ///< Queue traits
 123         typedef typename traits::item_counter item_counter; ///< Item counter type
 124         typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
 125         typedef typename traits::disposer     disposer;     ///< Item disposer
 126         typedef typename traits::back_off     back_off;     ///< back-off strategy
 127
 128     public:
 129         /// Rebind template arguments
 130         template <typename T2, typename Traits2>
 131         struct rebind {
 132             typedef VyukovMPMCCycleQueue< T2, Traits2> other   ;   ///< Rebinding result
 133         };
 134
 135     public:
 136         /// Constructs the queue of capacity \p nCapacity
 137         /**
 138             For \p cds::opt::v::static_buffer the \p nCapacity parameter is ignored.
 139         */
 140         VyukovMPMCCycleQueue( size_t nCapacity = 0 )
 141             : base_class( nCapacity )
 142         {}
 143
 144         /// Enqueues \p data to queue
 145         /**
 146             @note The intrusive queue stores pointer to \p data passed, not the copy of \p data.
 147         */
 148         bool enqueue( value_type& data )
 149         {
 150             return base_class::enqueue( &data );
 151         }
 152
 153         /// Dequeues an item from queue
 154         /**
 155             \p Traits::disposer is not called. You may manually delete the returned pointer.
 156
 157             If queue is empty, returns \p nullptr.
 158         */
 159         value_type * dequeue()
 160         {
 161             value_type * p = nullptr;
 162             return base_class::dequeue( p ) ? p : nullptr;
 163         }
 164
 165         /// Synonym for \p enqueue()
 166         bool push( value_type& data )
 167         {
 168             return enqueue( data );
 169         }
 170
 171         /// Synonym for \p dequeue()
 172         value_type * pop()
 173         {
 174             return dequeue();
 175         }
 176
 177         /// Clears queue in lock-free manner.
 178         /**
 179             \p f parameter is a functor to dispose removed items.
 180             The interface of \p Disposer is:
 181             \code
 182             struct myDisposer {
 183                 void operator ()( T * val );
 184             };
 185             \endcode
 186             The disposer will be called immediately for each item.
 187         */
 188         template <typename Disposer>
 189         void clear( Disposer f )
 190         {
 191             value_type * pv;
 192             while ( (pv = pop()) != nullptr ) {
 193                 f( pv );
 194             }
 195         }
 196
 197         /// Clears the queue
 198         /**
 199             This function uses the disposer that is specified in \p Traits.
 200         */
 201         void clear()
 202         {
 203             clear( disposer() );
 204         }
 205
 206         /// Checks if the queue is empty
 207         bool empty() const
 208         {
 209             return base_class::empty();
 210         }
 211
 212         /// Returns queue's item count
 213         /**
 214             The value returned depends on \p vyukov_queue::traits::item_counter option.
 215             For \p atomicity::empty_item_counter, this function always returns 0.
 216         */
 217         size_t size() const
 218         {
 219             return base_class::size();
 220         }
 221
 222         /// Returns capacity of the queue
 223         size_t capacity() const
 224         {
 225             return base_class::capacity();
 226         }
 227     };
 228 }}  // namespace cds::intrusive
 229
 230 #endif // #ifndef CDSLIB_INTRUSIVE_VYUKOV_MPMC_CYCLE_QUEUE_H