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