cds/intrusive/vyukov_mpmc_cycle_queue.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_INTRUSIVE_VYUKOV_MPMC_CYCLE_QUEUE_H
  32 #define CDSLIB_INTRUSIVE_VYUKOV_MPMC_CYCLE_QUEUE_H
  33
  34 #include <cds/intrusive/details/base.h>
  35 #include <cds/container/vyukov_mpmc_cycle_queue.h>
  36
  37 namespace cds { namespace intrusive {
  38
  39     /// VyukovMPMCCycleQueue related definitions
  40     /** @ingroup cds_intrusive_helper
  41     */
  42     namespace vyukov_queue {
  43
  44         /// VyukovMPMCCycleQueue traits
  45         struct traits : public cds::container::vyukov_queue::traits
  46         {
  47             /// The functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used only in \p clear()
  48             typedef opt::v::empty_disposer  disposer;
  49         };
  50
  51         /// Metafunction converting option list to \p vyukov_queue::traits
  52         /**
  53             Supported \p Options are:
  54             - \p opt::buffer - an uninitialized buffer type for internal cyclic array. Possible types are:
  55                 \p opt::v::uninitialized_dynamic_buffer (the default), \p opt::v::uninitialized_static_buffer. The type of
  56                 element in the buffer is not important: it will be changed via \p rebind metafunction.
  57             - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer.
  58                 This option is used only in \p clear() member function.
  59             - \p opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter (item counting disabled)
  60                 To enable item counting use \p cds::atomicity::item_counter
  61             - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
  62             - \p opt::padding - padding for internal critical atomic data. Default is \p opt::cache_line_padding
  63             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
  64                 or \p opt::v::sequential_consistent (sequentially consistent memory model).
  65
  66             Example: declare \p %VyukovMPMCCycleQueue with item counting and static internal buffer of size 1024:
  67             \code
  68             typedef cds::intrusive::VyukovMPMCCycleQueue< Foo,
  69                 typename cds::intrusive::vyukov_queue::make_traits<
  70                     cds::opt::buffer< cds::opt::v::uninitialized_static_buffer< void *, 1024 >,
  71                     cds::opt::item_counter< cds::atomicity::item_counter >
  72                 >::type
  73             > myQueue;
  74             \endcode
  75         */
  76         template <typename... Options>
  77         struct make_traits {
  78 #   ifdef CDS_DOXYGEN_INVOKED
  79             typedef implementation_defined type;   ///< Metafunction result
  80 #   else
  81             typedef typename cds::opt::make_options<
  82                 typename cds::opt::find_type_traits< traits, Options... >::type
  83                 , Options...
  84             >::type type;
  85 #   endif
  86         };
  87
  88     } // namespace vyukov_queue
  89
  90     /// Vyukov's MPMC bounded queue
  91     /** @ingroup cds_intrusive_queue
  92         This algorithm is developed by Dmitry Vyukov (see http://www.1024cores.net)
  93
  94         Implementation of intrusive version is based on container::VyukovMPMCCycleQueue.
  95
  96         Template parameters:
  97         - \p T - type stored in queue.
  98         - \p Traits - queue traits, default is \p vyukov_queue::traits. You can use \p vyukov_queue::make_traits
  99             metafunction to make your traits or just derive your traits from \p %vyukov_queue::traits:
 100             \code
 101             struct myTraits: public cds::intrusive::vyukov_queue::traits {
 102                 typedef cds::atomicity::item_counter    item_counter;
 103             };
 104             typedef cds::intrusive::VyukovMPMCCycleQueue< Foo, myTraits > myQueue;
 105
 106             // Equivalent make_traits example:
 107             typedef cds::intrusive::VyukovMPMCCycleQueue< cds::gc::HP, Foo,
 108                 typename cds::intrusive::vyukov_queue::make_traits<
 109                     cds::opt::item_counter< cds::atomicity::item_counter >
 110                 >::type
 111             > myQueue;
 112             \endcode
 113
 114         Instead of saving copy of enqueued data, the intrusive implementation stores pointer to passed data.
 115
 116         \par Examples:
 117         \code
 118         #include <cds/intrusive/vyukov_mpmc_cycle_queue.h>
 119
 120         struct Foo {
 121             ...
 122         };
 123
 124         // Queue of Foo pointers, capacity is 1024, statically allocated buffer:
 125         typedef cds::intrusive::VyukovMPMCCycleQueue< Foo,
 126             typename cds::intrusive::vyukov_queue::make_traits<
 127                 cds::opt::buffer< cds::opt::v::uninitialized_static_buffer< Foo, 1024 > >
 128             >::type
 129         > static_queue;
 130         static_queue    stQueue;
 131
 132         // Queue of Foo pointers, capacity is 1024, dynamically allocated buffer:
 133         struct queue_traits: public cds::intrusive::vyukov_queue::traits
 134         {
 135             typedef cds::opt::v::uninitialized_dynamic_buffer< Foo > buffer;
 136         };
 137         typedef cds::intrusive::VyukovMPMCCycleQueue< Foo, queue_traits > dynamic_queue;
 138         dynamic_queue    dynQueue( 1024 );
 139         \endcode
 140     */
 141     template <typename T, typename Traits = vyukov_queue::traits >
 142     class VyukovMPMCCycleQueue
 143         : private container::VyukovMPMCCycleQueue< T*, Traits >
 144     {
 145         //@cond
 146         typedef container::VyukovMPMCCycleQueue< T*, Traits > base_class;
 147         //@endcond
 148     public:
 149         typedef T value_type;   ///< type of data to be stored in the queue
 150         typedef Traits traits;  ///< Queue traits
 151         typedef typename traits::item_counter item_counter; ///< Item counter type
 152         typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
 153         typedef typename traits::disposer     disposer;     ///< Item disposer
 154         typedef typename traits::back_off     back_off;     ///< back-off strategy
 155
 156     public:
 157         /// Rebind template arguments
 158         template <typename T2, typename Traits2>
 159         struct rebind {
 160             typedef VyukovMPMCCycleQueue< T2, Traits2> other   ;   ///< Rebinding result
 161         };
 162
 163     public:
 164         /// Constructs the queue of capacity \p nCapacity
 165         /**
 166             For \p cds::opt::v::uninitialized_static_buffer the \p nCapacity parameter is ignored.
 167         */
 168         VyukovMPMCCycleQueue( size_t nCapacity = 0 )
 169             : base_class( nCapacity )
 170         {}
 171
 172         /// Enqueues \p data to queue
 173         /**
 174             @note The intrusive queue stores pointer to \p data passed, not the copy of \p data.
 175         */
 176         bool enqueue( value_type& data )
 177         {
 178             return base_class::enqueue( &data );
 179         }
 180
 181         /// Dequeues an item from queue
 182         /**
 183             \p Traits::disposer is not called. You may manually delete the returned pointer.
 184
 185             If queue is empty, returns \p nullptr.
 186         */
 187         value_type * dequeue()
 188         {
 189             value_type * p = nullptr;
 190             return base_class::dequeue( p ) ? p : nullptr;
 191         }
 192
 193         /// Synonym for \p enqueue()
 194         bool push( value_type& data )
 195         {
 196             return enqueue( data );
 197         }
 198
 199         /// Synonym for \p dequeue()
 200         value_type * pop()
 201         {
 202             return dequeue();
 203         }
 204
 205         /// Clears queue in lock-free manner.
 206         /**
 207             \p f parameter is a functor to dispose removed items.
 208             The interface of \p Disposer is:
 209             \code
 210             struct myDisposer {
 211                 void operator ()( T * val );
 212             };
 213             \endcode
 214             The disposer will be called immediately for each item.
 215         */
 216         template <typename Disposer>
 217         void clear( Disposer f )
 218         {
 219             value_type * pv;
 220             while ( (pv = pop()) != nullptr ) {
 221                 f( pv );
 222             }
 223         }
 224
 225         /// Clears the queue
 226         /**
 227             This function uses the disposer that is specified in \p Traits.
 228         */
 229         void clear()
 230         {
 231             clear( disposer() );
 232         }
 233
 234         /// Checks if the queue is empty
 235         bool empty() const
 236         {
 237             return base_class::empty();
 238         }
 239
 240         /// Returns queue's item count
 241         /**
 242             The value returned depends on \p vyukov_queue::traits::item_counter option.
 243             For \p atomicity::empty_item_counter, this function always returns 0.
 244         */
 245         size_t size() const
 246         {
 247             return base_class::size();
 248         }
 249
 250         /// Returns capacity of the queue
 251         size_t capacity() const
 252         {
 253             return base_class::capacity();
 254         }
 255     };
 256 }}  // namespace cds::intrusive
 257
 258 #endif // #ifndef CDSLIB_INTRUSIVE_VYUKOV_MPMC_CYCLE_QUEUE_H