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/intrusive/moir_queue.h>
   8 #include <cds/intrusive/details/queue_stat.h>
   9 #include <cds/container/details/base.h>
  10 #include <cds/ref.h>
  11 #include <cds/details/trivial_assign.h>
  12
  13 namespace cds { namespace container {
  14
  15     //@cond
  16     namespace details {
  17         template <typename GC, typename T, typename... Options>
  18         struct make_moir_queue
  19         {
  20             typedef GC gc;
  21             typedef T value_type;
  22
  23             struct default_options {
  24                 typedef cds::backoff::empty     back_off;
  25                 typedef CDS_DEFAULT_ALLOCATOR   allocator;
  26                 typedef atomicity::empty_item_counter item_counter;
  27                 typedef intrusive::queue_dummy_stat stat;
  28                 typedef opt::v::relaxed_ordering    memory_model;
  29                 enum { alignment = opt::cache_line_alignment };
  30             };
  31
  32             typedef typename opt::make_options<
  33                 typename cds::opt::find_type_traits< default_options, Options... >::type
  34                 ,Options...
  35             >::type   options;
  36
  37             struct node_type: public intrusive::single_link::node< gc >
  38             {
  39                 value_type  m_value;
  40
  41                 node_type( const value_type& val )
  42                     : m_value( val )
  43                 {}
  44
  45                 template <typename... Args>
  46                 node_type( Args&&... args )
  47                     : m_value( std::forward<Args>(args)...)
  48                 {}
  49             };
  50
  51             typedef typename options::allocator::template rebind<node_type>::other allocator_type;
  52             typedef cds::details::Allocator< node_type, allocator_type >           cxx_allocator;
  53
  54             struct node_deallocator
  55             {
  56                 void operator ()( node_type * pNode )
  57                 {
  58                     cxx_allocator().Delete( pNode );
  59                 }
  60             };
  61
  62             typedef intrusive::MoirQueue<
  63                 gc
  64                 ,node_type
  65                 ,intrusive::opt::hook<
  66                     intrusive::single_link::base_hook< opt::gc<gc> >
  67                 >
  68                 ,opt::back_off< typename options::back_off >
  69                 ,intrusive::opt::disposer< node_deallocator >
  70                 ,opt::item_counter< typename options::item_counter >
  71                 ,opt::stat< typename options::stat >
  72                 ,opt::alignment< options::alignment >
  73                 ,opt::memory_model< typename options::memory_model >
  74             >   type;
  75         };
  76     }
  77     //@endcond
  78
  79     /// A variation of Michael & Scott's lock-free queue
  80     /** @ingroup cds_nonintrusive_queue
  81         It is non-intrusive version of intrusive::MoirQueue.
  82
  83         \p T is a type stored in the queue. It should be default-constructible, copy-constructible, assignable type.
  84
  85         \p Options description see MSQueue
  86     */
  87     template <typename GC, typename T, typename... Options>
  88     class MoirQueue:
  89 #ifdef CDS_DOXYGEN_INVOKED
  90         intrusive::MoirQueue< GC, intrusive::single_link::node< T >, Options... >
  91 #else
  92         details::make_moir_queue< GC, T, Options... >::type
  93 #endif
  94     {
  95         //@cond
  96         typedef details::make_moir_queue< GC, T, Options... > options;
  97         typedef typename options::type base_class;
  98         //@endcond
  99
 100     public:
 101         /// Rebind template arguments
 102         template <typename GC2, typename T2, typename... Options2>
 103         struct rebind {
 104             typedef MoirQueue< GC2, T2, Options2...> other   ;   ///< Rebinding result
 105         };
 106
 107     public:
 108         typedef T value_type ; ///< Value type stored in the stack
 109
 110         typedef typename base_class::gc                 gc              ; ///< Garbage collector used
 111         typedef typename base_class::back_off           back_off        ; ///< Back-off strategy used
 112         typedef typename options::allocator_type        allocator_type  ; ///< Allocator type used for allocate/deallocate the nodes
 113         typedef typename options::options::item_counter item_counter    ; ///< Item counting policy used
 114         typedef typename options::options::stat         stat            ; ///< Internal statistics policy used
 115         typedef typename base_class::memory_model       memory_model    ; ///< Memory ordering. See cds::opt::memory_model option
 116
 117     protected:
 118         typedef typename options::node_type  node_type   ;   ///< queue node type (derived from intrusive::single_link::node)
 119
 120         //@cond
 121         typedef typename options::cxx_allocator     cxx_allocator;
 122         typedef typename options::node_deallocator  node_deallocator;   // deallocate node
 123         typedef typename base_class::node_traits    node_traits;
 124         //@endcond
 125
 126     protected:
 127         ///@cond
 128         static node_type * alloc_node()
 129         {
 130             return cxx_allocator().New();
 131         }
 132         static node_type * alloc_node( const value_type& val )
 133         {
 134             return cxx_allocator().New( val );
 135         }
 136         template <typename... Args>
 137         static node_type * alloc_node_move( Args&&... args )
 138         {
 139             return cxx_allocator().MoveNew( std::forward<Args>( args )... );
 140         }
 141         static void free_node( node_type * p )
 142         {
 143             node_deallocator()( p );
 144         }
 145
 146         struct node_disposer {
 147             void operator()( node_type * pNode )
 148             {
 149                 free_node( pNode );
 150             }
 151         };
 152         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
 153         //@endcond
 154
 155     public:
 156         /// Initializes empty queue
 157         MoirQueue()
 158         {}
 159
 160         /// Destructor clears the queue
 161         ~MoirQueue()
 162         {}
 163
 164         /// Returns queue's item count (see \ref intrusive::MSQueue::size for explanation)
 165         size_t size() const
 166         {
 167             return base_class::size();
 168         }
 169
 170         /// Returns refernce to internal statistics
 171         const stat& statistics() const
 172         {
 173             return base_class::statistics();
 174         }
 175
 176         /// Enqueues \p val value into the queue.
 177         /**
 178             The function makes queue node in dynamic memory calling copy constructor for \p val
 179             and then it calls intrusive::MSQueue::enqueue.
 180             Returns \p true if success, \p false otherwise.
 181         */
 182         bool enqueue( value_type const& val )
 183         {
 184             scoped_node_ptr p( alloc_node(val) );
 185             if ( base_class::enqueue( *p )) {
 186                 p.release();
 187                 return true;
 188             }
 189             return false;
 190         }
 191
 192         /// Enqueues \p data to queue using copy functor
 193         /**
 194             \p Func is a functor called to copy value \p data of type \p Type
 195             which may be differ from type \p T stored in the queue.
 196             The functor's interface is:
 197             \code
 198             struct myFunctor {
 199                 void operator()(T& dest, SOURCE const& data)
 200                 {
 201                     // // Code to copy \p data to \p dest
 202                     dest = data;
 203                 }
 204             };
 205             \endcode
 206             You may use \p boost:ref construction to pass functor \p f by reference.
 207
 208             <b>Requirements</b> The functor \p Func should not throw any exception.
 209         */
 210         template <typename Type, typename Func>
 211         bool enqueue( const Type& data, Func f  )
 212         {
 213             scoped_node_ptr p( alloc_node());
 214             unref(f)( node_traits::to_value_ptr( *p )->m_value, data );
 215             if ( base_class::enqueue( *p )) {
 216                 p.release();
 217                 return true;
 218             }
 219             return false;
 220         }
 221
 222         /// Dequeues a value using copy functor
 223         /**
 224             \p Func is a functor called to copy dequeued value to \p dest of type \p Type
 225             which may be differ from type \p T stored in the queue.
 226             The functor's interface is:
 227             \code
 228             struct myFunctor {
 229                 void operator()(Type& dest, T const& data)
 230                 {
 231                     // // Code to copy \p data to \p dest
 232                     dest = data;
 233                 }
 234             };
 235             \endcode
 236             You may use \p boost:ref construction to pass functor \p f by reference.
 237
 238             <b>Requirements</b> The functor \p Func should not throw any exception.
 239         */
 240         template <typename Type, typename Func>
 241         bool dequeue( Type& dest, Func f )
 242         {
 243             typename base_class::dequeue_result res;
 244             if ( base_class::do_dequeue( res )) {
 245                 unref(f)( dest, node_traits::to_value_ptr( *res.pNext )->m_value );
 246
 247                 base_class::dispose_result( res );
 248
 249                 return true;
 250             }
 251             return false;
 252         }
 253
 254         /// Dequeues a value from the queue
 255         /**
 256             If queue is not empty, the function returns \p true, \p dest contains copy of
 257             dequeued value. The assignment operator for type \ref value_type is invoked.
 258             If queue is empty, the function returns \p false, \p dest is unchanged.
 259         */
 260         bool dequeue( value_type& dest )
 261         {
 262             typedef cds::details::trivial_assign<value_type, value_type> functor;
 263             return dequeue( dest, functor() );
 264         }
 265
 266         /// Synonym for \ref enqueue function
 267         bool push( const value_type& val )
 268         {
 269             return enqueue( val );
 270         }
 271
 272         /// Synonym for template version of \ref enqueue function
 273         template <typename Type, typename Func>
 274         bool push( const Type& data, Func f  )
 275         {
 276             return enqueue( data, f );
 277         }
 278
 279         /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 280         template <typename... Args>
 281         bool emplace( Args&&... args )
 282         {
 283             scoped_node_ptr p( alloc_node_move( std::forward<Args>(args)... ));
 284             if ( base_class::enqueue( *p )) {
 285                 p.release();
 286                 return true;
 287             }
 288             return false;
 289         }
 290
 291         /// Synonym for \ref dequeue function
 292         bool pop( value_type& dest )
 293         {
 294             return dequeue( dest );
 295         }
 296
 297         /// Synonym for template version of \ref dequeue function
 298         template <typename Type, typename Func>
 299         bool pop( Type& dest, Func f )
 300         {
 301             return dequeue( dest, f );
 302         }
 303
 304         /// Checks if the queue is empty
 305         bool empty() const
 306         {
 307             return base_class::empty();
 308         }
 309
 310         /// Clear the queue
 311         /**
 312             The function repeatedly calls \ref dequeue until it returns nullptr.
 313             The disposer defined in template \p Options is called for each item
 314             that can be safely disposed.
 315         */
 316         void clear()
 317         {
 318             base_class::clear();
 319         }
 320     };
 321
 322 }}  // namespace cds::container
 323
 324 #endif  // #ifndef __CDS_CONTAINER_MOIR_QUEUE_H
 325
 326