cds/container/moir_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-2017
   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_CONTAINER_MOIR_QUEUE_H
  32 #define CDSLIB_CONTAINER_MOIR_QUEUE_H
  33
  34 #include <memory>
  35 #include <cds/container/msqueue.h>
  36 #include <cds/intrusive/moir_queue.h>
  37
  38 namespace cds { namespace container {
  39
  40     //@cond
  41     namespace details {
  42         template <typename GC, typename T, typename Traits>
  43         struct make_moir_queue: public cds::container::details::make_msqueue< GC, T, Traits >
  44         {
  45             typedef cds::container::details::make_msqueue< GC, T, Traits > base_class;
  46             typedef cds::intrusive::MoirQueue< GC, typename base_class::node_type, typename base_class::intrusive_traits > type;
  47         };
  48     }
  49     //@endcond
  50
  51     /// A variation of Michael & Scott's lock-free queue
  52     /** @ingroup cds_nonintrusive_queue
  53         It is non-intrusive version of \p cds::intrusive::MoirQueue.
  54
  55         Template arguments:
  56         - \p GC - garbage collector type: \p gc::HP, \p gc::DHP
  57         - \p T - a type stored in the queue.
  58         - \p Traits - queue traits, default is \p msqueue::traits. You can use \p msqueue::make_traits
  59             metafunction to make your traits or just derive your traits from \p %msqueue::traits:
  60             \code
  61             struct myTraits: public cds::container::msqueue::traits {
  62                 typedef cds::intrusive::msqueue::stat<> stat;
  63                 typedef cds::atomicity::item_counter    item_counter;
  64             };
  65             typedef cds::container::MoirQueue< cds::gc::HP, Foo, myTraits > myQueue;
  66
  67             // Equivalent make_traits example:
  68             typedef cds::container::MoirQueue< cds::gc::HP, Foo,
  69                 typename cds::container::msqueue::make_traits<
  70                     cds::opt::stat< cds::container::msqueue::stat<> >,
  71                     cds::opt::item_counter< cds::atomicity::item_counter >
  72                 >::type
  73             > myQueue;
  74             \endcode
  75     */
  76     template <typename GC, typename T, typename Traits = cds::container::msqueue::traits >
  77     class MoirQueue:
  78 #ifdef CDS_DOXYGEN_INVOKED
  79         private intrusive::MoirQueue< GC, intrusive::msqueue::node< T >, Traits >
  80 #else
  81         private details::make_moir_queue< GC, T, Traits >::type
  82 #endif
  83     {
  84         //@cond
  85         typedef details::make_moir_queue< GC, T, Traits > maker;
  86         typedef typename maker::type base_class;
  87         //@endcond
  88
  89     public:
  90         /// Rebind template arguments
  91         template <typename GC2, typename T2, typename Traits2>
  92         struct rebind {
  93             typedef MoirQueue< GC2, T2, Traits2 > other   ;   ///< Rebinding result
  94         };
  95
  96         static CDS_CONSTEXPR const size_t c_nHazardPtrCount = base_class::c_nHazardPtrCount; ///< Count of hazard pointer required for the algorithm
  97
  98     public:
  99         typedef T value_type ; ///< Value type stored in the queue
 100         typedef typename base_class::gc                 gc;             ///< Garbage collector
 101         typedef typename base_class::back_off           back_off;       ///< Back-off strategy
 102         typedef typename maker::allocator_type          allocator_type; ///< Allocator type used for allocate/deallocate the nodes
 103         typedef typename base_class::item_counter       item_counter;   ///< Item counting policy used
 104         typedef typename base_class::stat               stat;           ///< Internal statistics policy used
 105         typedef typename base_class::memory_model       memory_model;   ///< Memory ordering. See cds::opt::memory_model option
 106
 107     protected:
 108         //@cond
 109         typedef typename maker::node_type  node_type;   ///< queue node type (derived from intrusive::msqueue::node)
 110
 111         typedef typename maker::cxx_allocator     cxx_allocator;
 112         typedef typename maker::node_deallocator  node_deallocator;   // deallocate node
 113         typedef typename base_class::node_traits  node_traits;
 114         //@endcond
 115
 116     protected:
 117         ///@cond
 118         static node_type * alloc_node()
 119         {
 120             return cxx_allocator().New();
 121         }
 122         static node_type * alloc_node( const value_type& val )
 123         {
 124             return cxx_allocator().New( val );
 125         }
 126         template <typename... Args>
 127         static node_type * alloc_node_move( Args&&... args )
 128         {
 129             return cxx_allocator().MoveNew( std::forward<Args>( args )... );
 130         }
 131         static void free_node( node_type * p )
 132         {
 133             node_deallocator()( p );
 134         }
 135
 136         struct node_disposer {
 137             void operator()( node_type * pNode )
 138             {
 139                 free_node( pNode );
 140             }
 141         };
 142         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
 143         //@endcond
 144
 145     public:
 146         /// Initializes empty queue
 147         MoirQueue()
 148         {}
 149
 150         /// Destructor clears the queue
 151         ~MoirQueue()
 152         {}
 153
 154         /// Enqueues \p val value into the queue.
 155         /**
 156             The function makes queue node in dynamic memory calling copy constructor for \p val
 157             and then it calls \p intrusive::MoirQueue::enqueue.
 158             Returns \p true if success, \p false otherwise.
 159         */
 160         bool enqueue( value_type const& val )
 161         {
 162             scoped_node_ptr p( alloc_node(val));
 163             if ( base_class::enqueue( *p )) {
 164                 p.release();
 165                 return true;
 166             }
 167             return false;
 168         }
 169
 170         /// Enqueues \p val value into the queue, move semantics
 171         bool enqueue( value_type&& val )
 172         {
 173             scoped_node_ptr p( alloc_node_move( std::move( val )));
 174             if ( base_class::enqueue( *p )) {
 175                 p.release();
 176                 return true;
 177             }
 178             return false;
 179         }
 180
 181         /// Enqueues \p data to queue using a functor
 182         /**
 183             \p Func is a functor calling to create a new node.
 184             The functor should initialize creating node
 185             and it takes one argument - a reference to a new node of type \ref value_type :
 186             \code
 187             cds:container::MoirQueue< cds::gc::HP, Foo > myQueue;
 188             Bar bar;
 189             myQueue.enqueue_with( [&bar]( Foo& dest ) { dest = bar; } );
 190             \endcode
 191         */
 192         template <typename Func>
 193         bool enqueue_with( Func f )
 194         {
 195             scoped_node_ptr p( alloc_node());
 196             f( p->m_value );
 197             if ( base_class::enqueue( *p )) {
 198                 p.release();
 199                 return true;
 200             }
 201             return false;
 202         }
 203
 204         /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 205         template <typename... Args>
 206         bool emplace( Args&&... args )
 207         {
 208             scoped_node_ptr p( alloc_node_move( std::forward<Args>( args )... ));
 209             if ( base_class::enqueue( *p )) {
 210                 p.release();
 211                 return true;
 212             }
 213             return false;
 214         }
 215
 216         /// Synonym for \p enqueue() function
 217         bool push( value_type const& val )
 218         {
 219             return enqueue( val );
 220         }
 221
 222         /// Synonym for \p enqueue() function, move semantics
 223         bool push( value_type&& val )
 224         {
 225             return enqueue( std::move( val ));
 226         }
 227
 228         /// Synonym for \p enqueue_with() function
 229         template <typename Func>
 230         bool push_with( Func f )
 231         {
 232             return enqueue_with( f );
 233         }
 234
 235         /// Dequeues a value from the queue
 236         /**
 237             If queue is not empty, the function returns \p true, \p dest contains copy of
 238             dequeued value. The assignment operator for type \ref value_type is invoked.
 239             If queue is empty, the function returns \p false, \p dest is unchanged.
 240         */
 241         bool dequeue( value_type& dest )
 242         {
 243             return dequeue_with( [&dest]( value_type& src ) {
 244                 // TSan finds a race between this read of \p src and node_type constructor
 245                 // I think, it is wrong
 246                 CDS_TSAN_ANNOTATE_IGNORE_READS_BEGIN;
 247                 dest = std::move( src );
 248                 CDS_TSAN_ANNOTATE_IGNORE_READS_END;
 249             });
 250         }
 251
 252         /// Dequeues a value using a functor
 253         /**
 254             \p Func is a functor called to copy dequeued value.
 255             The functor takes one argument - a reference to removed node:
 256             \code
 257             cds:container::MoirQueue< cds::gc::HP, Foo > myQueue;
 258             Bar bar;
 259             myQueue.dequeue_with( [&bar]( Foo& src ) { bar = std::move( src );});
 260             \endcode
 261             The functor is called only if the queue is not empty.
 262         */
 263         template <typename Func>
 264         bool dequeue_with( Func f )
 265         {
 266             typename base_class::dequeue_result res;
 267             if ( base_class::do_dequeue( res )) {
 268                 f( node_traits::to_value_ptr( *res.pNext )->m_value );
 269                 base_class::dispose_result( res );
 270                 return true;
 271             }
 272             return false;
 273         }
 274
 275         /// Synonym for \p dequeue() function
 276         bool pop( value_type& dest )
 277         {
 278             return dequeue( dest );
 279         }
 280
 281         /// Synonym for \p dequeue_with() function
 282         template <typename Func>
 283         bool pop_with( Func f )
 284         {
 285             return dequeue_with( f );
 286         }
 287
 288         /// Clear the queue
 289         /**
 290             The function repeatedly calls \ref dequeue until it returns \p nullptr.
 291             The disposer defined in template \p Traits is called for each item
 292             that can be safely disposed.
 293         */
 294         void clear()
 295         {
 296             base_class::clear();
 297         }
 298
 299         /// Checks if the queue is empty
 300         bool empty() const
 301         {
 302             return base_class::empty();
 303         }
 304
 305         /// Returns queue's item count (see \ref intrusive::MSQueue::size for explanation)
 306         size_t size() const
 307         {
 308             return base_class::size();
 309         }
 310
 311         /// Returns refernce to internal statistics
 312         const stat& statistics() const
 313         {
 314             return base_class::statistics();
 315         }
 316
 317     };
 318
 319 }}  // namespace cds::container
 320
 321 #endif  // #ifndef CDSLIB_CONTAINER_MOIR_QUEUE_H
 322
 323