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, CDS_DECL_OPTIONS7>
  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, CDS_OPTIONS7 >::type
  30                 ,CDS_OPTIONS7
  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, CDS_DECL_OPTIONS7>
 102     class TsigasCycleQueue:
 103 #ifdef CDS_DOXYGEN_INVOKED
 104         intrusive::TsigasCycleQueue< T, Options... >
 105 #else
 106         details::make_tsigas_cycle_queue< T, CDS_OPTIONS7 >::type
 107 #endif
 108     {
 109         //@cond
 110         typedef details::make_tsigas_cycle_queue< T, CDS_OPTIONS7 > 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, CDS_DECL_OTHER_OPTIONS7>
 123         struct rebind {
 124             typedef TsigasCycleQueue< T2, CDS_OTHER_OPTIONS7> 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 #   ifdef CDS_EMPLACE_SUPPORT
 145         template <typename... Args>
 146         static value_type * alloc_node_move( Args&&... args )
 147         {
 148             return cxx_allocator().MoveNew( std::forward<Args>( args )... );
 149         }
 150 #   endif
 151         static void free_node( value_type * p )
 152         {
 153             node_deallocator()( p );
 154         }
 155
 156         struct node_disposer2 {
 157             void operator()( value_type * pNode )
 158             {
 159                 free_node( pNode );
 160             }
 161         };
 162         typedef std::unique_ptr< value_type, node_disposer2 >     scoped_node_ptr;
 163         //@endcond
 164
 165     public:
 166         /// Initialize empty queue of capacity \p nCapacity
 167         /**
 168             For cds::opt::v::static_buffer the \p nCapacity parameter is ignored.
 169
 170             Note that the real capacity of queue is \p nCapacity - 2.
 171         */
 172         TsigasCycleQueue( size_t nCapacity = 0 )
 173             : base_class( nCapacity )
 174         {}
 175
 176         /// Returns queue's item count (see \ref intrusive::TsigasCycleQueue::size for explanation)
 177         size_t size() const
 178         {
 179             return base_class::size();
 180         }
 181
 182         /// Returns capacity of cyclic buffer
 183         /**
 184             Warning: real capacity of queue is two less than returned value of this function.
 185         */
 186         size_t capacity() const
 187         {
 188             return base_class::capacity();
 189         }
 190
 191         /// Enqueues \p val value into the queue.
 192         /**
 193             The function makes queue node in dynamic memory calling copy constructor for \p val
 194             and then it calls intrusive::TsigasCycleQueue::enqueue.
 195             Returns \p true if success, \p false otherwise.
 196         */
 197         bool enqueue( value_type const& val )
 198         {
 199             scoped_node_ptr p( alloc_node(val));
 200             if ( base_class::enqueue( *p )) {
 201                 p.release();
 202                 return true;
 203             }
 204             return false;
 205         }
 206
 207         /// Enqueues \p data to queue using copy functor
 208         /**
 209             \p Func is a functor called to copy value \p data of type \p Type
 210             which may be differ from type \p T stored in the queue.
 211             The functor's interface is:
 212             \code
 213             struct myFunctor {
 214                 void operator()(T& dest, SOURCE const& data)
 215                 {
 216                     // // Code to copy \p data to \p dest
 217                     dest = data;
 218                 }
 219             };
 220             \endcode
 221             You may use \p boost:ref construction to pass functor \p f by reference.
 222
 223             <b>Requirements</b> The functor \p Func should not throw any exception.
 224         */
 225         template <typename Type, typename Func>
 226         bool enqueue( const Type& data, Func f  )
 227         {
 228             scoped_node_ptr p( alloc_node());
 229             unref(f)( *p, data );
 230             if ( base_class::enqueue( *p )) {
 231                 p.release();
 232                 return true;
 233             }
 234             return false;
 235         }
 236
 237 #   ifdef CDS_EMPLACE_SUPPORT
 238         /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 239         /**
 240             This function is available only for compiler that supports
 241             variadic template and move semantics
 242         */
 243         template <typename... Args>
 244         bool emplace( Args&&... args )
 245         {
 246             scoped_node_ptr p ( alloc_node_move( std::forward<Args>(args)...));
 247             if ( base_class::enqueue( *p)) {
 248                 p.release();
 249                 return true;
 250             }
 251             return false;
 252         }
 253 #   endif
 254
 255         /// Dequeues a value using copy functor
 256         /**
 257             \p Func is a functor called to copy dequeued value to \p dest of type \p Type
 258             which may be differ from type \p T stored in the queue.
 259             The functor's interface is:
 260             \code
 261             struct myFunctor {
 262                 void operator()(Type& dest, T const& data)
 263                 {
 264                     // // Code to copy \p data to \p dest
 265                     dest = data;
 266                 }
 267             };
 268             \endcode
 269             You may use \p boost:ref construction to pass functor \p f by reference.
 270
 271             <b>Requirements</b> The functor \p Func should not throw any exception.
 272         */
 273         template <typename Type, typename Func>
 274         bool dequeue( Type& dest, Func f )
 275         {
 276             value_type * p = base_class::dequeue();
 277             if ( p ) {
 278                 unref(f)( dest, *p );
 279                 node_disposer()( p );
 280                 return true;
 281             }
 282             return false;
 283         }
 284
 285         /// Dequeues a value from the queue
 286         /**
 287             If queue is not empty, the function returns \p true, \p dest contains copy of
 288             dequeued value. The assignment operator for type \ref value_type is invoked.
 289             If queue is empty, the function returns \p false, \p dest is unchanged.
 290         */
 291         bool dequeue( value_type& dest )
 292         {
 293             typedef cds::details::trivial_assign<value_type, value_type> functor;
 294             return dequeue( dest, functor() );
 295         }
 296
 297         /// Synonym for \ref enqueue function
 298         bool push( const value_type& val )
 299         {
 300             return enqueue( val );
 301         }
 302
 303         /// Synonym for template version of \ref enqueue function
 304         template <typename Type, typename Func>
 305         bool push( const Type& data, Func f  )
 306         {
 307             return enqueue( data, f );
 308         }
 309
 310         /// Synonym for \ref dequeue function
 311         bool pop( value_type& dest )
 312         {
 313             return dequeue( dest );
 314         }
 315
 316         /// Synonym for template version of \ref dequeue function
 317         template <typename Type, typename Func>
 318         bool pop( Type& dest, Func f )
 319         {
 320             return dequeue( dest, f );
 321         }
 322
 323         /// Checks if the queue is empty
 324         bool empty() const
 325         {
 326             return base_class::empty();
 327         }
 328
 329         /// Clear the queue
 330         /**
 331             The function repeatedly calls \ref dequeue until it returns \p nullptr.
 332         */
 333         void clear()
 334         {
 335             base_class::clear();
 336         }
 337     };
 338
 339 }} // namespace cds::intrusive
 340
 341 #endif // #ifndef __CDS_CONTAINER_TSIGAS_CYCLE_QUEUE_H