cds/container/moir_queue.h

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