cds/container/msqueue.h

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