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 data to the queue using a functor
 288         /**
 289             \p Func is a functor called to create node.
 290             The functor \p f takes one argument - a reference to a new node of type \ref value_type :
 291             \code
 292             cds::container::TsigasCysleQueue< Foo > myQueue;
 293             Bar bar;
 294             myQueue.enqueue_with( [&bar]( Foo& dest ) { dest = bar; } );
 295             \endcode
 296         */
 297         template <typename Func>
 298         bool enqueue_with( Func f )
 299         {
 300             scoped_node_ptr p( alloc_node() );
 301             f( *p );
 302             if ( base_class::enqueue( *p )) {
 303                 p.release();
 304                 return true;
 305             }
 306             return false;
 307         }
 308
 309         /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 310         template <typename... Args>
 311         bool emplace( Args&&... args )
 312         {
 313             scoped_node_ptr p ( alloc_node_move( std::forward<Args>(args)...));
 314             if ( base_class::enqueue( *p)) {
 315                 p.release();
 316                 return true;
 317             }
 318             return false;
 319         }
 320
 321         /// Synonym for template version of \p enqueue() function
 322         bool push( value_type const& data )
 323         {
 324             return enqueue( data );
 325         }
 326
 327         /// Synonym for \p enqueue_with() function
 328         template <typename Func>
 329         bool push_with( Func f )
 330         {
 331             return enqueue_with( f );
 332         }
 333
 334         /// Dequeues a value using a functor
 335         /**
 336             \p Func is a functor called to copy dequeued value.
 337             The functor takes one argument - a reference to removed node:
 338             \code
 339             cds:container::TsigasCycleQueue< Foo > myQueue;
 340             Bar bar;
 341             myQueue.dequeue_with( [&bar]( Foo& src ) { bar = std::move( src );});
 342             \endcode
 343             The functor is called only if the queue is not empty.
 344         */
 345         template <typename Func>
 346         bool dequeue_with( Func f )
 347         {
 348             value_type * p = base_class::dequeue();
 349             if ( p ) {
 350                 f( *p );
 351                 free_node( p );
 352                 return true;
 353             }
 354             return false;
 355         }
 356
 357         /// Dequeues a value from the queue
 358         /**
 359             If queue is not empty, the function returns \p true, \p dest contains copy of
 360             dequeued value. The assignment operator for type \ref value_type is invoked.
 361             If queue is empty, the function returns \p false, \p dest is unchanged.
 362         */
 363         bool dequeue( value_type& dest )
 364         {
 365             return dequeue_with( [&dest]( value_type& src ) { dest = src; } );
 366         }
 367
 368         /// Synonym for \p dequeue() function
 369         bool pop( value_type& dest )
 370         {
 371             return dequeue( dest );
 372         }
 373
 374         /// Synonym for \p dequeue_with() function
 375         template <typename Func>
 376         bool pop_with( Func f )
 377         {
 378             return dequeue_with( f );
 379         }
 380
 381         /// Checks if the queue is empty
 382         bool empty() const
 383         {
 384             return base_class::empty();
 385         }
 386
 387         /// Clear the queue
 388         /**
 389             The function repeatedly calls \p dequeue() until it returns \p nullptr.
 390         */
 391         void clear()
 392         {
 393             base_class::clear();
 394         }
 395
 396         /// Returns queue's item count
 397         /** \copydetails cds::intrusive::TsigasCycleQueue::size()
 398         */
 399         size_t size() const
 400         {
 401             return base_class::size();
 402         }
 403
 404         /// Returns capacity of cyclic buffer
 405         size_t capacity() const
 406         {
 407             return base_class::capacity();
 408         }
 409     };
 410
 411 }} // namespace cds::intrusive
 412
 413 #endif // #ifndef CDSLIB_CONTAINER_TSIGAS_CYCLE_QUEUE_H