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