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