cds/container/tsigas_cycle_queue.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_CONTAINER_TSIGAS_CYCLE_QUEUE_H
  32 #define CDSLIB_CONTAINER_TSIGAS_CYCLE_QUEUE_H
  33
  34 #include <memory>
  35 #include <cds/intrusive/tsigas_cycle_queue.h>
  36 #include <cds/container/details/base.h>
  37
  38 namespace cds { namespace container {
  39
  40     /// TsigasCycleQueue related definitions
  41     /** @ingroup cds_nonintrusive_helper
  42     */
  43     namespace tsigas_queue {
  44
  45         /// TsigasCycleQueue default traits
  46         struct traits
  47         {
  48             /// Buffer type for cyclic array
  49             /*
  50                 The type of element for the buffer is not important: the queue rebinds
  51                 buffer for required type via \p rebind metafunction.
  52
  53                 For \p TsigasCycleQueue queue the buffer size should have power-of-2 size.
  54             */
  55             typedef cds::opt::v::dynamic_buffer< void * > buffer;
  56
  57             /// Node allocator
  58             typedef CDS_DEFAULT_ALLOCATOR       allocator;
  59
  60             /// Back-off strategy
  61             typedef cds::backoff::empty         back_off;
  62
  63             /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
  64             typedef atomicity::empty_item_counter item_counter;
  65
  66             /// C++ memory ordering model
  67             /**
  68                 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
  69                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
  70             */
  71             typedef opt::v::relaxed_ordering    memory_model;
  72
  73             /// Alignment for internal queue data. Default is \p opt::cache_line_alignment
  74             enum { alignment = opt::cache_line_alignment };
  75         };
  76
  77         /// Metafunction converting option list to \p tsigas_queue::traits
  78         /**
  79             Supported \p Options are:
  80             - \p opt::buffer - the buffer type for internal cyclic array. Possible types are:
  81                 \p opt::v::dynamic_buffer (the default), \p opt::v::static_buffer. The type of
  82                 element in the buffer is not important: it will be changed via \p rebind metafunction.
  83             - \p opt::allocator - allocator (like \p std::allocator) used for allocating queue items. Default is \ref CDS_DEFAULT_ALLOCATOR
  84             - \p opt::back_off - back-off strategy used, default is \p cds::backoff::empty.
  85             - \p opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter (item counting disabled)
  86                 To enable item counting use \p cds::atomicity::item_counter
  87             - \p opt::alignment - the alignment for internal queue data. Default is \p opt::cache_line_alignment
  88             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
  89                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
  90
  91             Example: declare \p %TsigasCycleQueue with item counting and static iternal buffer of size 1024:
  92             \code
  93             typedef cds::container::TsigasCycleQueue< Foo,
  94                 typename cds::container::tsigas_queue::make_traits<
  95                     cds::opt::buffer< cds::opt::v::static_buffer< void *, 1024 >,
  96                     cds::opt::item_counte< cds::atomicity::item_counter >
  97                 >::type
  98             > myQueue;
  99             \endcode
 100         */
 101         template <typename... Options>
 102         struct make_traits {
 103 #   ifdef CDS_DOXYGEN_INVOKED
 104             typedef implementation_defined type;   ///< Metafunction result
 105 #   else
 106             typedef typename cds::opt::make_options<
 107                 typename cds::opt::find_type_traits< traits, Options... >::type
 108                 , Options...
 109             >::type type;
 110 #   endif
 111         };
 112
 113     } // namespace tsigas_queue
 114
 115     //@cond
 116     namespace details {
 117         template <typename T, typename Traits>
 118         struct make_tsigas_cycle_queue
 119         {
 120             typedef T value_type;
 121             typedef Traits traits;
 122
 123             typedef typename traits::allocator::template rebind<value_type>::other allocator_type;
 124             typedef cds::details::Allocator< value_type, allocator_type >           cxx_allocator;
 125
 126             struct node_deallocator
 127             {
 128                 void operator ()( value_type * pNode )
 129                 {
 130                     cxx_allocator().Delete( pNode );
 131                 }
 132             };
 133             typedef node_deallocator node_disposer;
 134
 135             struct intrusive_traits: public traits
 136             {
 137                 typedef node_deallocator disposer;
 138             };
 139
 140             typedef intrusive::TsigasCycleQueue< value_type, intrusive_traits > type;
 141         };
 142     } // namespace
 143     //@endcond
 144
 145     /// Non-blocking cyclic bounded queue
 146     /** @ingroup cds_nonintrusive_queue
 147         It is non-intrusive implementation of Tsigas & Zhang cyclic queue based on \p intrusive::TsigasCycleQueue.
 148
 149         Source:
 150         - [2000] Philippas Tsigas, Yi Zhang "A Simple, Fast and Scalable Non-Blocking Concurrent FIFO Queue
 151             for Shared Memory Multiprocessor Systems"
 152
 153         Template arguments:
 154         - \p T is a type stored in the queue.
 155         - \p Traits - queue traits, default is \p tsigas_queue::traits. You can use \p tsigas_queue::make_traits
 156             metafunction to make your traits or just derive your traits from \p %tsigas_queue::traits:
 157             \code
 158             struct myTraits: public cds::container::tsigas_queue::traits {
 159                 typedef cds::atomicity::item_counter    item_counter;
 160             };
 161             typedef cds::container::TsigasCycleQueue< Foo, myTraits > myQueue;
 162
 163             // Equivalent make_traits example:
 164             typedef cds::container::TsigasCycleQueue< cds::gc::HP, Foo,
 165                 typename cds::container::tsigas_queue::make_traits<
 166                     cds::opt::item_counter< cds::atomicity::item_counter >
 167                 >::type
 168             > myQueue;
 169             \endcode
 170
 171         \par Examples:
 172         \code
 173         #include <cds/container/tsigas_cycle_queue.h>
 174
 175         struct Foo {
 176             ...
 177         };
 178
 179         // Queue of Foo, capacity is 1024, statically allocated buffer:
 180         typedef cds::container::TsigasCycleQueue< Foo,
 181             typename cds::container::tsigas_queue::make_traits<
 182                 cds::opt::buffer< cds::opt::v::static_buffer< Foo, 1024 > >
 183             >::type
 184         > static_queue;
 185         static_queue    stQueue;
 186
 187         // Queue of Foo, capacity is 1024, dynamically allocated buffer:
 188         typedef cds::container::TsigasCycleQueue< Foo
 189             typename cds::container::tsigas_queue::make_traits<
 190                 cds::opt::buffer< cds::opt::v::dynamic_buffer< Foo > >
 191             >::type
 192         > dynamic_queue;
 193         dynamic_queue    dynQueue( 1024 );
 194         \endcode
 195     */
 196     template <typename T, typename Traits = tsigas_queue::traits>
 197     class TsigasCycleQueue:
 198 #ifdef CDS_DOXYGEN_INVOKED
 199         intrusive::TsigasCycleQueue< T, Traits >
 200 #else
 201         details::make_tsigas_cycle_queue< T, Traits >::type
 202 #endif
 203     {
 204         //@cond
 205         typedef details::make_tsigas_cycle_queue< T, Traits > maker;
 206         typedef typename maker::type base_class;
 207         //@endcond
 208     public:
 209         typedef T value_type ;  ///< Value type stored in the stack
 210         typedef Traits traits;  ///< Queue traits
 211
 212         typedef typename traits::back_off       back_off;       ///< Back-off strategy used
 213         typedef typename maker::allocator_type  allocator_type; ///< Allocator type used for allocate/deallocate the items
 214         typedef typename traits::item_counter   item_counter;   ///< Item counting policy used
 215         typedef typename traits::memory_model   memory_model;   ///< Memory ordering. See \p cds::opt::memory_model option
 216
 217         /// Rebind template arguments
 218         template <typename T2, typename Traits2>
 219         struct rebind {
 220             typedef TsigasCycleQueue< T2, Traits2> other   ;   ///< Rebinding result
 221         };
 222
 223     protected:
 224         //@cond
 225         typedef typename maker::cxx_allocator     cxx_allocator;
 226         typedef typename maker::node_deallocator  node_deallocator;   // deallocate node
 227         typedef typename maker::node_disposer     node_disposer;
 228         //@endcond
 229
 230     protected:
 231         ///@cond
 232         static value_type * alloc_node()
 233         {
 234             return cxx_allocator().New();
 235         }
 236         static value_type * alloc_node( const value_type& val )
 237         {
 238             return cxx_allocator().New( val );
 239         }
 240         template <typename... Args>
 241         static value_type * alloc_node_move( Args&&... args )
 242         {
 243             return cxx_allocator().MoveNew( std::forward<Args>( args )... );
 244         }
 245         static void free_node( value_type * p )
 246         {
 247             node_deallocator()( p );
 248         }
 249
 250         struct node_disposer2 {
 251             void operator()( value_type * pNode )
 252             {
 253                 free_node( pNode );
 254             }
 255         };
 256         typedef std::unique_ptr< value_type, node_disposer2 > scoped_node_ptr;
 257         //@endcond
 258
 259     public:
 260         /// Initialize empty queue of capacity \p nCapacity
 261         /**
 262             If internal buffer type is \p cds::opt::v::static_buffer, the \p nCapacity parameter is ignored.
 263
 264             Note, the real capacity of queue is \p nCapacity - 2.
 265         */
 266         TsigasCycleQueue( size_t nCapacity = 0 )
 267             : base_class( nCapacity )
 268         {}
 269
 270         /// Enqueues \p val value into the queue.
 271         /**
 272             The function makes queue node in dynamic memory calling copy constructor for \p val
 273             and then it calls \p intrusive::TsigasCycleQueue::enqueue.
 274
 275             Returns \p true if success, \p false if the queue is full.
 276         */
 277         bool enqueue( value_type const& val )
 278         {
 279             scoped_node_ptr p( alloc_node(val));
 280             if ( base_class::enqueue( *p )) {
 281                 p.release();
 282                 return true;
 283             }
 284             return false;
 285         }
 286
 287         /// Enqueues \p val value into the queue, move semantics
 288         bool enqueue( value_type&& val )
 289         {
 290             scoped_node_ptr p( alloc_node_move( std::move( val )));
 291             if ( base_class::enqueue( *p ) ) {
 292                 p.release();
 293                 return true;
 294             }
 295             return false;
 296         }
 297
 298         /// Enqueues data to the queue using a functor
 299         /**
 300             \p Func is a functor called to create node.
 301             The functor \p f takes one argument - a reference to a new node of type \ref value_type :
 302             \code
 303             cds::container::TsigasCysleQueue< Foo > myQueue;
 304             Bar bar;
 305             myQueue.enqueue_with( [&bar]( Foo& dest ) { dest = bar; } );
 306             \endcode
 307         */
 308         template <typename Func>
 309         bool enqueue_with( Func f )
 310         {
 311             scoped_node_ptr p( alloc_node() );
 312             f( *p );
 313             if ( base_class::enqueue( *p )) {
 314                 p.release();
 315                 return true;
 316             }
 317             return false;
 318         }
 319
 320         /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 321         template <typename... Args>
 322         bool emplace( Args&&... args )
 323         {
 324             scoped_node_ptr p ( alloc_node_move( std::forward<Args>(args)...));
 325             if ( base_class::enqueue( *p)) {
 326                 p.release();
 327                 return true;
 328             }
 329             return false;
 330         }
 331
 332         /// Synonym for \p enqueue( value_type const& )
 333         bool push( value_type const& data )
 334         {
 335             return enqueue( data );
 336         }
 337
 338         /// Synonym for \p enqueue( value_type&& )
 339         bool push( value_type&& data )
 340         {
 341             return enqueue( std::move( data ));
 342         }
 343
 344         /// Synonym for \p enqueue_with() function
 345         template <typename Func>
 346         bool push_with( Func f )
 347         {
 348             return enqueue_with( f );
 349         }
 350
 351         /// Dequeues a value using a functor
 352         /**
 353             \p Func is a functor called to copy dequeued value.
 354             The functor takes one argument - a reference to removed node:
 355             \code
 356             cds:container::TsigasCycleQueue< Foo > myQueue;
 357             Bar bar;
 358             myQueue.dequeue_with( [&bar]( Foo& src ) { bar = std::move( src );});
 359             \endcode
 360             The functor is called only if the queue is not empty.
 361         */
 362         template <typename Func>
 363         bool dequeue_with( Func f )
 364         {
 365             value_type * p = base_class::dequeue();
 366             if ( p ) {
 367                 f( *p );
 368                 free_node( p );
 369                 return true;
 370             }
 371             return false;
 372         }
 373
 374         /// Dequeues a value from the queue
 375         /**
 376             If queue is not empty, the function returns \p true, \p dest contains copy of
 377             dequeued value. The assignment operator for type \ref value_type is invoked.
 378             If queue is empty, the function returns \p false, \p dest is unchanged.
 379         */
 380         bool dequeue( value_type& dest )
 381         {
 382             return dequeue_with( [&dest]( value_type& src ) { dest = std::move( src );});
 383         }
 384
 385         /// Synonym for \p dequeue() function
 386         bool pop( value_type& dest )
 387         {
 388             return dequeue( dest );
 389         }
 390
 391         /// Synonym for \p dequeue_with() function
 392         template <typename Func>
 393         bool pop_with( Func f )
 394         {
 395             return dequeue_with( f );
 396         }
 397
 398         /// Checks if the queue is empty
 399         bool empty() const
 400         {
 401             return base_class::empty();
 402         }
 403
 404         /// Clear the queue
 405         /**
 406             The function repeatedly calls \p dequeue() until it returns \p nullptr.
 407         */
 408         void clear()
 409         {
 410             base_class::clear();
 411         }
 412
 413         /// Returns queue's item count
 414         /** \copydetails cds::intrusive::TsigasCycleQueue::size()
 415         */
 416         size_t size() const
 417         {
 418             return base_class::size();
 419         }
 420
 421         /// Returns capacity of cyclic buffer
 422         size_t capacity() const
 423         {
 424             return base_class::capacity();
 425         }
 426     };
 427
 428 }} // namespace cds::intrusive
 429
 430 #endif // #ifndef CDSLIB_CONTAINER_TSIGAS_CYCLE_QUEUE_H