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