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/base.h>
   9 #include <cds/details/trivial_assign.h>
  10
  11 namespace cds { namespace container {
  12
  13     //@cond
  14     namespace details {
  15         template <typename T, typename... Options>
  16         struct make_tsigas_cycle_queue
  17         {
  18             typedef T value_type;
  19
  20             struct default_options {
  21                 typedef cds::backoff::empty     back_off;
  22                 typedef CDS_DEFAULT_ALLOCATOR   allocator;
  23                 typedef atomicity::empty_item_counter item_counter;
  24                 typedef opt::v::relaxed_ordering    memory_model;
  25                 enum { alignment = opt::cache_line_alignment };
  26             };
  27
  28             typedef typename opt::make_options<
  29                 typename cds::opt::find_type_traits< default_options, Options... >::type
  30                 ,Options...
  31             >::type   options;
  32
  33             typedef typename options::allocator::template rebind<value_type>::other allocator_type;
  34             typedef cds::details::Allocator< value_type, allocator_type >           cxx_allocator;
  35
  36             struct node_deallocator
  37             {
  38                 void operator ()( value_type * pNode )
  39                 {
  40                     cxx_allocator().Delete( pNode );
  41                 }
  42             };
  43             typedef node_deallocator node_disposer;
  44
  45             typedef intrusive::TsigasCycleQueue<
  46                 value_type
  47                 ,opt::buffer< typename options::buffer >
  48                 ,opt::back_off< typename options::back_off >
  49                 ,intrusive::opt::disposer< node_disposer >
  50                 ,opt::item_counter< typename options::item_counter >
  51                 ,opt::alignment< options::alignment >
  52                 ,opt::memory_model< typename options::memory_model >
  53             >   type;
  54         };
  55
  56     }
  57     //@endcond
  58
  59     /// Non-blocking cyclic queue discovered by Philippas Tsigas and Yi Zhang
  60     /** @ingroup cds_nonintrusive_queue
  61         It is non-intrusive implementation of Tsigas & Zhang cyclic queue based on intrusive::TsigasCycleQueue.
  62
  63         Source:
  64         \li [2000] Philippas Tsigas, Yi Zhang "A Simple, Fast and Scalable Non-Blocking Concurrent FIFO Queue
  65             for Shared Memory Multiprocessor Systems"
  66
  67         \p T is a type stored in the queue. It should be default-constructible, copy-constructible, assignable type.
  68
  69         Available \p Options:
  70         - opt::buffer - buffer to store items. Mandatory option, see option description for full list of possible types.
  71         - opt::allocator - allocator (like \p std::allocator). Default is \ref CDS_DEFAULT_ALLOCATOR
  72         - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter
  73         - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used.
  74         - opt::alignment - the alignment for internal queue data. Default is opt::cache_line_alignment
  75         - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
  76             or opt::v::sequential_consistent (sequentially consisnent memory model).
  77
  78         \par Examples:
  79         \code
  80         #include <cds/container/tsigas_cycle_queue.h>
  81
  82         struct Foo {
  83             ...
  84         };
  85
  86         // Queue of Foo, capacity is 1024, statically allocated buffer:
  87         typedef cds::intrusive::TsigasCycleQueue<
  88             Foo
  89             ,cds::opt::buffer< cds::opt::v::static_buffer< Foo, 1024 > >
  90         > static_queue;
  91         static_queue    stQueue;
  92
  93         // Queue of Foo, capacity is 1024, dynamically allocated buffer:
  94         typedef cds::intrusive::TsigasCycleQueue<
  95             Foo
  96             ,cds::opt::buffer< cds::opt::v::dynamic_buffer< Foo > >
  97         > dynamic_queue;
  98         dynamic_queue    dynQueue( 1024 );
  99         \endcode
 100     */
 101     template <typename T, typename... Options>
 102     class TsigasCycleQueue:
 103 #ifdef CDS_DOXYGEN_INVOKED
 104         intrusive::TsigasCycleQueue< T, Options... >
 105 #else
 106         details::make_tsigas_cycle_queue< T, Options... >::type
 107 #endif
 108     {
 109         //@cond
 110         typedef details::make_tsigas_cycle_queue< T, Options... > options;
 111         typedef typename options::type base_class;
 112         //@endcond
 113     public:
 114         typedef T value_type ; ///< Value type stored in the stack
 115
 116         typedef typename base_class::back_off           back_off        ; ///< Back-off strategy used
 117         typedef typename options::allocator_type        allocator_type  ; ///< Allocator type used for allocate/deallocate the nodes
 118         typedef typename options::options::item_counter item_counter    ; ///< Item counting policy used
 119         typedef typename base_class::memory_model       memory_model    ; ///< Memory ordering. See cds::opt::memory_model option
 120
 121         /// Rebind template arguments
 122         template <typename T2, typename... Options2>
 123         struct rebind {
 124             typedef TsigasCycleQueue< T2, Options2...> other   ;   ///< Rebinding result
 125         };
 126
 127     protected:
 128         //@cond
 129         typedef typename options::cxx_allocator     cxx_allocator;
 130         typedef typename options::node_deallocator  node_deallocator;   // deallocate node
 131         typedef typename options::node_disposer     node_disposer;
 132         //@endcond
 133
 134     protected:
 135         ///@cond
 136         static value_type * alloc_node()
 137         {
 138             return cxx_allocator().New();
 139         }
 140         static value_type * alloc_node( const value_type& val )
 141         {
 142             return cxx_allocator().New( val );
 143         }
 144         template <typename... Args>
 145         static value_type * alloc_node_move( Args&&... args )
 146         {
 147             return cxx_allocator().MoveNew( std::forward<Args>( args )... );
 148         }
 149         static void free_node( value_type * p )
 150         {
 151             node_deallocator()( p );
 152         }
 153
 154         struct node_disposer2 {
 155             void operator()( value_type * pNode )
 156             {
 157                 free_node( pNode );
 158             }
 159         };
 160         typedef std::unique_ptr< value_type, node_disposer2 >     scoped_node_ptr;
 161         //@endcond
 162
 163     public:
 164         /// Initialize empty queue of capacity \p nCapacity
 165         /**
 166             For cds::opt::v::static_buffer the \p nCapacity parameter is ignored.
 167
 168             Note that the real capacity of queue is \p nCapacity - 2.
 169         */
 170         TsigasCycleQueue( size_t nCapacity = 0 )
 171             : base_class( nCapacity )
 172         {}
 173
 174         /// Returns queue's item count (see \ref intrusive::TsigasCycleQueue::size for explanation)
 175         size_t size() const
 176         {
 177             return base_class::size();
 178         }
 179
 180         /// Returns capacity of cyclic buffer
 181         /**
 182             Warning: real capacity of queue is two less than returned value of this function.
 183         */
 184         size_t capacity() const
 185         {
 186             return base_class::capacity();
 187         }
 188
 189         /// Enqueues \p val value into the queue.
 190         /**
 191             The function makes queue node in dynamic memory calling copy constructor for \p val
 192             and then it calls intrusive::TsigasCycleQueue::enqueue.
 193             Returns \p true if success, \p false otherwise.
 194         */
 195         bool enqueue( value_type const& val )
 196         {
 197             scoped_node_ptr p( alloc_node(val));
 198             if ( base_class::enqueue( *p )) {
 199                 p.release();
 200                 return true;
 201             }
 202             return false;
 203         }
 204
 205         /// Enqueues \p data to queue using copy functor
 206         /**
 207             \p Func is a functor called to copy value \p data of type \p Type
 208             which may be differ from type \p T stored in the queue.
 209             The functor's interface is:
 210             \code
 211             struct myFunctor {
 212                 void operator()(T& dest, SOURCE const& data)
 213                 {
 214                     // // Code to copy \p data to \p dest
 215                     dest = data;
 216                 }
 217             };
 218             \endcode
 219             You may use \p boost:ref construction to pass functor \p f by reference.
 220
 221             <b>Requirements</b> The functor \p Func should not throw any exception.
 222         */
 223         template <typename Type, typename Func>
 224         bool enqueue( const Type& data, Func f  )
 225         {
 226             scoped_node_ptr p( alloc_node());
 227             unref(f)( *p, data );
 228             if ( base_class::enqueue( *p )) {
 229                 p.release();
 230                 return true;
 231             }
 232             return false;
 233         }
 234
 235         /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 236         template <typename... Args>
 237         bool emplace( Args&&... args )
 238         {
 239             scoped_node_ptr p ( alloc_node_move( std::forward<Args>(args)...));
 240             if ( base_class::enqueue( *p)) {
 241                 p.release();
 242                 return true;
 243             }
 244             return false;
 245         }
 246
 247         /// Dequeues a value using copy functor
 248         /**
 249             \p Func is a functor called to copy dequeued value to \p dest of type \p Type
 250             which may be differ from type \p T stored in the queue.
 251             The functor's interface is:
 252             \code
 253             struct myFunctor {
 254                 void operator()(Type& dest, T const& data)
 255                 {
 256                     // // Code to copy \p data to \p dest
 257                     dest = data;
 258                 }
 259             };
 260             \endcode
 261             You may use \p boost:ref construction to pass functor \p f by reference.
 262
 263             <b>Requirements</b> The functor \p Func should not throw any exception.
 264         */
 265         template <typename Type, typename Func>
 266         bool dequeue( Type& dest, Func f )
 267         {
 268             value_type * p = base_class::dequeue();
 269             if ( p ) {
 270                 unref(f)( dest, *p );
 271                 node_disposer()( p );
 272                 return true;
 273             }
 274             return false;
 275         }
 276
 277         /// Dequeues a value from the queue
 278         /**
 279             If queue is not empty, the function returns \p true, \p dest contains copy of
 280             dequeued value. The assignment operator for type \ref value_type is invoked.
 281             If queue is empty, the function returns \p false, \p dest is unchanged.
 282         */
 283         bool dequeue( value_type& dest )
 284         {
 285             typedef cds::details::trivial_assign<value_type, value_type> functor;
 286             return dequeue( dest, functor() );
 287         }
 288
 289         /// Synonym for \ref enqueue function
 290         bool push( const value_type& val )
 291         {
 292             return enqueue( val );
 293         }
 294
 295         /// Synonym for template version of \ref enqueue function
 296         template <typename Type, typename Func>
 297         bool push( const Type& data, Func f  )
 298         {
 299             return enqueue( data, f );
 300         }
 301
 302         /// Synonym for \ref dequeue function
 303         bool pop( value_type& dest )
 304         {
 305             return dequeue( dest );
 306         }
 307
 308         /// Synonym for template version of \ref dequeue function
 309         template <typename Type, typename Func>
 310         bool pop( Type& dest, Func f )
 311         {
 312             return dequeue( dest, f );
 313         }
 314
 315         /// Checks if the queue is empty
 316         bool empty() const
 317         {
 318             return base_class::empty();
 319         }
 320
 321         /// Clear the queue
 322         /**
 323             The function repeatedly calls \ref dequeue until it returns \p nullptr.
 324         */
 325         void clear()
 326         {
 327             base_class::clear();
 328         }
 329     };
 330
 331 }} // namespace cds::intrusive
 332
 333 #endif // #ifndef __CDS_CONTAINER_TSIGAS_CYCLE_QUEUE_H