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