cds/container/tsigas_cycle_queue.h

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