cds/container/optimistic_queue.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_OPTIMISTIC_QUEUE_H
   4 #define __CDS_CONTAINER_OPTIMISTIC_QUEUE_H
   5
   6 #include <memory>
   7 #include <cds/intrusive/optimistic_queue.h>
   8 #include <cds/container/details/base.h>
   9
  10 namespace cds { namespace container {
  11
  12     /// OptimisticQueue related definitions
  13     /** @ingroup cds_nonintrusive_helper
  14     */
  15     namespace optimistic_queue {
  16         /// Internal statistics
  17         template <typename Counter = cds::intrusive::optimistic_queue::stat<>::counter_type >
  18         using stat = cds::intrusive::optimistic_queue::stat< Counter >;
  19
  20         /// Dummy internal statistics
  21         typedef cds::intrusive::optimistic_queue::empty_stat empty_stat;
  22
  23         /// MSQueue default type traits
  24         struct traits
  25         {
  26             /// Node allocator
  27             typedef CDS_DEFAULT_ALLOCATOR       allocator;
  28
  29             /// Back-off strategy
  30             typedef cds::backoff::empty         back_off;
  31
  32             /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
  33             typedef atomicity::empty_item_counter   item_counter;
  34
  35             /// Internal statistics (by default, disabled)
  36             /**
  37                 Possible option value are: \p optimistic_queue::stat, \p optimistic_queue::empty_stat (the default),
  38                 user-provided class that supports \p %optimistic_queue::stat interface.
  39             */
  40             typedef optimistic_queue::empty_stat         stat;
  41
  42             /// C++ memory ordering model
  43             /**
  44                 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
  45                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
  46             */
  47             typedef opt::v::relaxed_ordering    memory_model;
  48
  49             /// Alignment of internal queue data. Default is \p opt::cache_line_alignment
  50             enum { alignment = opt::cache_line_alignment };
  51         };
  52
  53         /// Metafunction converting option list to \p msqueue::traits
  54         /**
  55             Supported \p Options are:
  56             - opt::allocator - allocator (like \p std::allocator) used for allocating queue nodes. Default is \ref CDS_DEFAULT_ALLOCATOR
  57             - opt::back_off - back-off strategy used, default is \p cds::backoff::empty.
  58             - opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter (item counting disabled)
  59                 To enable item counting use \p cds::atomicity::item_counter
  60             - opt::stat - the type to gather internal statistics.
  61                 Possible statistics types are: \p optimistic_queue::stat, \p optimistic_queue::empty_stat,
  62                 user-provided class that supports \p %optimistic_queue::stat interface.
  63                 Default is \p %optimistic_queue::empty_stat.
  64             - opt::alignment - the alignment for internal queue data. Default is \p opt::cache_line_alignment
  65             - opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
  66                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
  67
  68             Example: declare \p OptimisticQueue with item counting and internal statistics
  69             \code
  70                 typedef cds::container::OptimisticQueue< cds::gc::HP, Foo,
  71                     typename cds::container::optimistic_queue::make_traits<
  72                         cds::opt::item_counter< cds::atomicity::item_counter >,
  73                         cds::opt::stat< cds::container::optimistic_queue::stat<> >
  74                     >::type
  75                 > myQueue;
  76             \endcode
  77         */
  78         template <typename... Options>
  79         struct make_traits {
  80 #   ifdef CDS_DOXYGEN_INVOKED
  81             typedef implementation_defined type;   ///< Metafunction result
  82 #   else
  83             typedef typename cds::opt::make_options<
  84                 typename cds::opt::find_type_traits< traits, Options... >::type
  85                 , Options...
  86             >::type type;
  87 #   endif
  88         };
  89     } // namespace optimistic_queue
  90
  91     //@cond
  92     namespace details {
  93         template <typename GC, typename T, typename Traits>
  94         struct make_optimistic_queue
  95         {
  96             typedef GC gc;
  97             typedef T value_type;
  98             typedef Traits traits;
  99
 100             struct node_type: public cds::intrusive::optimistic_queue::node< gc >
 101             {
 102                 value_type  m_value;
 103
 104                 node_type( value_type const& val )
 105                     : m_value( val )
 106                 {}
 107
 108                 template <typename... Args>
 109                 node_type( Args&&... args )
 110                     : m_value( std::forward<Args>(args)...)
 111                 {}
 112             };
 113
 114             typedef typename traits::allocator::template rebind<node_type>::other allocator_type;
 115             typedef cds::details::Allocator< node_type, allocator_type >          cxx_allocator;
 116
 117             struct node_deallocator
 118             {
 119                 void operator ()( node_type * pNode )
 120                 {
 121                     cxx_allocator().Delete( pNode );
 122                 }
 123             };
 124
 125             struct intrusive_traits : public traits
 126             {
 127                 typedef cds::intrusive::optimistic_queue::base_hook< opt::gc<gc> > hook;
 128                 typedef node_deallocator disposer;
 129                 static CDS_CONSTEXPR const opt::link_check_type link_checker = cds::intrusive::optimistic_queue::traits::link_checker;
 130             };
 131
 132             typedef intrusive::OptimisticQueue< gc, node_type, intrusive_traits > type;
 133         };
 134     }   // namespace details
 135     //@endcond
 136
 137     /// Optimistic queue
 138     /** @ingroup cds_nonintrusive_queue
 139         Implementation of Ladan-Mozes & Shavit optimistic queue algorithm.
 140             - [2008] Edya Ladan-Mozes, Nir Shavit "An Optimistic Approach to Lock-Free FIFO Queues"
 141
 142         Template arguments:
 143         - \p GC - garbage collector type: gc::HP, gc::PTB. Note that gc::HRC is <b>not</b> supported
 144         - \p T - type of values to be stored in the queue
 145         - \p Traits - queue traits, default is \p optimistic_queue::traits. You can use \p optimistic_queue::make_traits
 146             metafunction to make your traits or just derive your traits from \p %optimistic_queue::traits:
 147             \code
 148             struct myTraits: public cds::container::optimistic_queue::traits {
 149                 typedef cds::intrusive::optimistic_queue::stat<> stat;
 150                 typedef cds::atomicity::item_counter    item_counter;
 151             };
 152             typedef cds::container::OptimisticQueue< cds::gc::HP, Foo, myTraits > myQueue;
 153
 154             // Equivalent make_traits example:
 155             typedef cds::container::OptimisticQueue< cds::gc::HP, Foo,
 156                 typename cds::container::optimistic_queue::make_traits<
 157                     cds::opt::stat< cds::container::optimistic_queue::stat<> >,
 158                     cds::opt::item_counter< cds::atomicity::item_counter >
 159                 >::type
 160             > myQueue;
 161             \endcode
 162     */
 163     template <typename GC, typename T, typename Traits = optimistic_queue::traits >
 164     class OptimisticQueue:
 165 #ifdef CDS_DOXYGEN_INVOKED
 166         private intrusive::OptimisticQueue< GC, cds::intrusive::optimistic_queue::node< T >, Traits >
 167 #else
 168         private details::make_optimistic_queue< GC, T, Traits >::type
 169 #endif
 170     {
 171         //@cond
 172         typedef details::make_optimistic_queue< GC, T, Traits > maker;
 173         typedef typename maker::type base_class;
 174         //@endcond
 175
 176     public:
 177         /// Rebind template arguments
 178         template <typename GC2, typename T2, typename Traits2>
 179         struct rebind {
 180             typedef OptimisticQueue< GC2, T2, Traits2 > other   ;   ///< Rebinding result
 181         };
 182
 183     public:
 184         typedef GC gc;          ///< Garbage collector
 185         typedef T value_type;   ///< Value type to be stored in the queue
 186         typedef Traits traits;  ///< Queue traits
 187
 188         typedef typename base_class::back_off           back_off;       ///< Back-off strategy used
 189         typedef typename maker::allocator_type          allocator_type; ///< Allocator type used for allocate/deallocate the nodes
 190         typedef typename base_class::item_counter       item_counter;   ///< Item counting policy used
 191         typedef typename base_class::stat               stat;           ///< Internal statistics policy used
 192         typedef typename base_class::memory_model       memory_model;   ///< Memory ordering. See \p cds::opt::memory_model option
 193
 194         static CDS_CONSTEXPR const size_t c_nHazardPtrCount = base_class::c_nHazardPtrCount; ///< Count of hazard pointer required for the algorithm
 195
 196     protected:
 197         //@cond
 198         typedef typename maker::node_type           node_type;   ///< queue node type (derived from intrusive::optimistic_queue::node)
 199         typedef typename maker::cxx_allocator       cxx_allocator;
 200         typedef typename maker::node_deallocator    node_deallocator; // deallocate node
 201         typedef typename base_class::node_traits    node_traits;
 202         //@endcond
 203
 204     protected:
 205         ///@cond
 206         static node_type * alloc_node()
 207         {
 208             return cxx_allocator().New();
 209         }
 210         static node_type * alloc_node( const value_type& val )
 211         {
 212             return cxx_allocator().New( val );
 213         }
 214         template <typename... Args>
 215         static node_type * alloc_node_move( Args&&... args )
 216         {
 217             return cxx_allocator().MoveNew( std::forward<Args>( args )... );
 218         }
 219         static void free_node( node_type * p )
 220         {
 221             node_deallocator()( p );
 222         }
 223
 224         struct node_disposer {
 225             void operator()( node_type * pNode )
 226             {
 227                 free_node( pNode );
 228             }
 229         };
 230         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
 231         //@endcond
 232
 233     public:
 234         /// Initializes empty queue
 235         OptimisticQueue()
 236         {}
 237
 238         /// Destructor clears the queue
 239         ~OptimisticQueue()
 240         {}
 241
 242         /// Enqueues \p val value into the queue.
 243         /**
 244             The function makes queue node in dynamic memory calling copy constructor for \p val
 245             and then it calls \p intrusive::OptimisticQueue::enqueue.
 246             Returns \p true if success, \p false otherwise.
 247         */
 248         bool enqueue( const value_type& val )
 249         {
 250             scoped_node_ptr p( alloc_node(val));
 251             if ( base_class::enqueue( *p )) {
 252                 p.release();
 253                 return true;
 254             }
 255             return false;
 256         }
 257
 258         /// Enqueues \p data to queue using a functor
 259         /**
 260             \p Func is a functor called to create node.
 261             The functor \p f takes one argument - a reference to a new node of type \ref value_type :
 262             \code
 263             cds::container::OptimisticQueue< cds::gc::HP, Foo > myQueue;
 264             Bar bar;
 265             myQueue.enqueue_with( [&bar]( Foo& dest ) { dest = bar; } );
 266             \endcode
 267         */
 268         template <typename Func>
 269         bool enqueue_with( Func f )
 270         {
 271             scoped_node_ptr p( alloc_node() );
 272             f( p->m_value );
 273             if ( base_class::enqueue( *p )) {
 274                 p.release();
 275                 return true;
 276             }
 277             return false;
 278         }
 279
 280         /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 281         template <typename... Args>
 282         bool emplace( Args&&... args )
 283         {
 284             scoped_node_ptr p( alloc_node_move( std::forward<Args>(args)... ));
 285             if ( base_class::enqueue( *p )) {
 286                 p.release();
 287                 return true;
 288             }
 289             return false;
 290         }
 291
 292         /// Synonym for \p enqueue() function
 293         bool push( const value_type& val )
 294         {
 295             return enqueue( val );
 296         }
 297
 298         /// Synonym for \p enqueue_with() function
 299         template <typename Func>
 300         bool push_with( Func f )
 301         {
 302             return enqueue_with( f );
 303         }
 304
 305         /// Dequeues a value from the queue
 306         /**
 307             If queue is not empty, the function returns \p true, \p dest contains copy of
 308             dequeued value. The assignment operator for type \p value_type is invoked.
 309
 310             If queue is empty, the function returns \p false, \p dest is unchanged.
 311         */
 312         bool dequeue( value_type& dest )
 313         {
 314             return dequeue_with( [&dest]( value_type& src ) { dest = src; } );
 315         }
 316
 317         /// Dequeues a value using a functor
 318         /**
 319             \p Func is a functor called to copy dequeued value.
 320             The functor takes one argument - a reference to removed node:
 321             \code
 322             cds:container::OptimisticQueue< cds::gc::HP, Foo > myQueue;
 323             Bar bar;
 324             myQueue.dequeue_with( [&bar]( Foo& src ) { bar = std::move( src );});
 325             \endcode
 326             The functor is called only if the queue is not empty.
 327         */
 328         template <typename Func>
 329         bool dequeue_with( Func f )
 330         {
 331             typename base_class::dequeue_result res;
 332             if ( base_class::do_dequeue( res ) ) {
 333                 f( node_traits::to_value_ptr( *res.pNext )->m_value );
 334
 335                 base_class::dispose_result( res );
 336
 337                 return true;
 338             }
 339             return false;
 340         }
 341
 342         /// Synonym for \ref dequeue() function
 343         bool pop( value_type& dest )
 344         {
 345             return dequeue( dest );
 346         }
 347
 348         /// Synonym for template version of \p dequeue_with() function
 349         template <typename Func>
 350         bool pop_with( Func f )
 351         {
 352             return dequeue_with( f );
 353         }
 354
 355         /// Checks if the queue is empty
 356         bool empty() const
 357         {
 358             return base_class::empty();
 359         }
 360
 361         /// Clear the queue
 362         /**
 363             The function repeatedly calls \ref dequeue until it returns \p nullptr.
 364         */
 365         void clear()
 366         {
 367             base_class::clear();
 368         }
 369
 370         /// Returns queue's item count
 371         /** \copydetails cds::intrusive::OptimisticQueue::size()
 372         */
 373         size_t size() const
 374         {
 375             return base_class::size();
 376         }
 377
 378         /// Returns reference to internal statistics
 379         const stat& statistics() const
 380         {
 381             return base_class::statistics();
 382         }
 383     };
 384
 385 }}  // namespace cds::container
 386
 387 #endif //#ifndef __CDS_CONTAINER_OPTIMISTIC_QUEUE_H