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