cds/container/optimistic_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_OPTIMISTIC_QUEUE_H
  32 #define CDSLIB_CONTAINER_OPTIMISTIC_QUEUE_H
  33
  34 #include <memory>
  35 #include <cds/intrusive/optimistic_queue.h>
  36 #include <cds/container/details/base.h>
  37
  38 namespace cds { namespace container {
  39
  40     /// OptimisticQueue related definitions
  41     /** @ingroup cds_nonintrusive_helper
  42     */
  43     namespace optimistic_queue {
  44         /// Internal statistics
  45         template <typename Counter = cds::intrusive::optimistic_queue::stat<>::counter_type >
  46         using stat = cds::intrusive::optimistic_queue::stat< Counter >;
  47
  48         /// Dummy internal statistics
  49         typedef cds::intrusive::optimistic_queue::empty_stat empty_stat;
  50
  51         /// MSQueue default type traits
  52         struct traits
  53         {
  54             /// Node allocator
  55             typedef CDS_DEFAULT_ALLOCATOR       allocator;
  56
  57             /// Back-off strategy
  58             typedef cds::backoff::empty         back_off;
  59
  60             /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
  61             typedef atomicity::empty_item_counter   item_counter;
  62
  63             /// Internal statistics (by default, disabled)
  64             /**
  65                 Possible option value are: \p optimistic_queue::stat, \p optimistic_queue::empty_stat (the default),
  66                 user-provided class that supports \p %optimistic_queue::stat interface.
  67             */
  68             typedef optimistic_queue::empty_stat         stat;
  69
  70             /// C++ memory ordering model
  71             /**
  72                 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
  73                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
  74             */
  75             typedef opt::v::relaxed_ordering    memory_model;
  76
  77             /// Padding for internal critical atomic data. Default is \p opt::cache_line_padding
  78             enum { padding = opt::cache_line_padding };
  79         };
  80
  81         /// Metafunction converting option list to \p msqueue::traits
  82         /**
  83             Supported \p Options are:
  84             - \p opt::allocator - allocator (like \p std::allocator) used for allocating queue nodes. Default is \ref CDS_DEFAULT_ALLOCATOR
  85             - \p opt::back_off - back-off strategy used, default is \p cds::backoff::empty.
  86             - \p opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter (item counting disabled)
  87                 To enable item counting use \p cds::atomicity::item_counter
  88             - \p opt::stat - the type to gather internal statistics.
  89                 Possible statistics types are: \p optimistic_queue::stat, \p optimistic_queue::empty_stat,
  90                 user-provided class that supports \p %optimistic_queue::stat interface.
  91                 Default is \p %optimistic_queue::empty_stat.
  92             - \p opt::padding - padding for internal critical atomic data. Default is \p opt::cache_line_padding
  93             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
  94                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
  95
  96             Example: declare \p OptimisticQueue with item counting and internal statistics
  97             \code
  98                 typedef cds::container::OptimisticQueue< cds::gc::HP, Foo,
  99                     typename cds::container::optimistic_queue::make_traits<
 100                         cds::opt::item_counter< cds::atomicity::item_counter >,
 101                         cds::opt::stat< cds::container::optimistic_queue::stat<> >
 102                     >::type
 103                 > myQueue;
 104             \endcode
 105         */
 106         template <typename... Options>
 107         struct make_traits {
 108 #   ifdef CDS_DOXYGEN_INVOKED
 109             typedef implementation_defined type;   ///< Metafunction result
 110 #   else
 111             typedef typename cds::opt::make_options<
 112                 typename cds::opt::find_type_traits< traits, Options... >::type
 113                 , Options...
 114             >::type type;
 115 #   endif
 116         };
 117     } // namespace optimistic_queue
 118
 119     //@cond
 120     namespace details {
 121         template <typename GC, typename T, typename Traits>
 122         struct make_optimistic_queue
 123         {
 124             typedef GC gc;
 125             typedef T value_type;
 126             typedef Traits traits;
 127
 128             struct node_type: public cds::intrusive::optimistic_queue::node< gc >
 129             {
 130                 value_type  m_value;
 131
 132                 node_type( value_type const& val )
 133                     : m_value( val )
 134                 {}
 135
 136                 template <typename... Args>
 137                 node_type( Args&&... args )
 138                     : m_value( std::forward<Args>(args)...)
 139                 {}
 140             };
 141
 142             typedef typename traits::allocator::template rebind<node_type>::other allocator_type;
 143             typedef cds::details::Allocator< node_type, allocator_type >          cxx_allocator;
 144
 145             struct node_deallocator
 146             {
 147                 void operator ()( node_type * pNode )
 148                 {
 149                     cxx_allocator().Delete( pNode );
 150                 }
 151             };
 152
 153             struct intrusive_traits : public traits
 154             {
 155                 typedef cds::intrusive::optimistic_queue::base_hook< opt::gc<gc> > hook;
 156                 typedef node_deallocator disposer;
 157                 static CDS_CONSTEXPR const opt::link_check_type link_checker = cds::intrusive::optimistic_queue::traits::link_checker;
 158             };
 159
 160             typedef intrusive::OptimisticQueue< gc, node_type, intrusive_traits > type;
 161         };
 162     }   // namespace details
 163     //@endcond
 164
 165     /// Optimistic queue
 166     /** @ingroup cds_nonintrusive_queue
 167         Implementation of Ladan-Mozes & Shavit optimistic queue algorithm.
 168             - [2008] Edya Ladan-Mozes, Nir Shavit "An Optimistic Approach to Lock-Free FIFO Queues"
 169
 170         Template arguments:
 171         - \p GC - garbage collector type: \p gc::HP, \p gc::DHP.
 172         - \p T - type of values to be stored in the queue
 173         - \p Traits - queue traits, default is \p optimistic_queue::traits. You can use \p optimistic_queue::make_traits
 174             metafunction to make your traits or just derive your traits from \p %optimistic_queue::traits:
 175             \code
 176             struct myTraits: public cds::container::optimistic_queue::traits {
 177                 typedef cds::intrusive::optimistic_queue::stat<> stat;
 178                 typedef cds::atomicity::item_counter    item_counter;
 179             };
 180             typedef cds::container::OptimisticQueue< cds::gc::HP, Foo, myTraits > myQueue;
 181
 182             // Equivalent make_traits example:
 183             typedef cds::container::OptimisticQueue< cds::gc::HP, Foo,
 184                 typename cds::container::optimistic_queue::make_traits<
 185                     cds::opt::stat< cds::container::optimistic_queue::stat<> >,
 186                     cds::opt::item_counter< cds::atomicity::item_counter >
 187                 >::type
 188             > myQueue;
 189             \endcode
 190     */
 191     template <typename GC, typename T, typename Traits = optimistic_queue::traits >
 192     class OptimisticQueue:
 193 #ifdef CDS_DOXYGEN_INVOKED
 194         private intrusive::OptimisticQueue< GC, cds::intrusive::optimistic_queue::node< T >, Traits >
 195 #else
 196         private details::make_optimistic_queue< GC, T, Traits >::type
 197 #endif
 198     {
 199         //@cond
 200         typedef details::make_optimistic_queue< GC, T, Traits > maker;
 201         typedef typename maker::type base_class;
 202         //@endcond
 203
 204     public:
 205         /// Rebind template arguments
 206         template <typename GC2, typename T2, typename Traits2>
 207         struct rebind {
 208             typedef OptimisticQueue< GC2, T2, Traits2 > other   ;   ///< Rebinding result
 209         };
 210
 211     public:
 212         typedef GC gc;          ///< Garbage collector
 213         typedef T value_type;   ///< Value type to be stored in the queue
 214         typedef Traits traits;  ///< Queue traits
 215
 216         typedef typename base_class::back_off           back_off;       ///< Back-off strategy used
 217         typedef typename maker::allocator_type          allocator_type; ///< Allocator type used for allocate/deallocate the nodes
 218         typedef typename base_class::item_counter       item_counter;   ///< Item counting policy used
 219         typedef typename base_class::stat               stat;           ///< Internal statistics policy used
 220         typedef typename base_class::memory_model       memory_model;   ///< Memory ordering. See \p cds::opt::memory_model option
 221
 222         static CDS_CONSTEXPR const size_t c_nHazardPtrCount = base_class::c_nHazardPtrCount; ///< Count of hazard pointer required for the algorithm
 223
 224     protected:
 225         //@cond
 226         typedef typename maker::node_type           node_type;   ///< queue node type (derived from intrusive::optimistic_queue::node)
 227         typedef typename maker::cxx_allocator       cxx_allocator;
 228         typedef typename maker::node_deallocator    node_deallocator; // deallocate node
 229         typedef typename base_class::node_traits    node_traits;
 230         //@endcond
 231
 232     protected:
 233         ///@cond
 234         static node_type * alloc_node()
 235         {
 236             return cxx_allocator().New();
 237         }
 238         static node_type * alloc_node( const value_type& val )
 239         {
 240             return cxx_allocator().New( val );
 241         }
 242         template <typename... Args>
 243         static node_type * alloc_node_move( Args&&... args )
 244         {
 245             return cxx_allocator().MoveNew( std::forward<Args>( args )... );
 246         }
 247         static void free_node( node_type * p )
 248         {
 249             node_deallocator()( p );
 250         }
 251
 252         struct node_disposer {
 253             void operator()( node_type * pNode )
 254             {
 255                 free_node( pNode );
 256             }
 257         };
 258         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
 259         //@endcond
 260
 261     public:
 262         /// Initializes empty queue
 263         OptimisticQueue()
 264         {}
 265
 266         /// Destructor clears the queue
 267         ~OptimisticQueue()
 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::OptimisticQueue::enqueue.
 274             Returns \p true if success, \p false otherwise.
 275         */
 276         bool enqueue( const value_type& val )
 277         {
 278             scoped_node_ptr p( alloc_node(val));
 279             if ( base_class::enqueue( *p )) {
 280                 p.release();
 281                 return true;
 282             }
 283             return false;
 284         }
 285
 286         /// Enqueues \p val value into the queue, move semntics
 287         bool enqueue( value_type&& val )
 288         {
 289             scoped_node_ptr p( alloc_node_move( std::move( val )));
 290             if ( base_class::enqueue( *p )) {
 291                 p.release();
 292                 return true;
 293             }
 294             return false;
 295         }
 296
 297         /// Enqueues \p data to queue using a functor
 298         /**
 299             \p Func is a functor called to create node.
 300             The functor \p f takes one argument - a reference to a new node of type \ref value_type :
 301             \code
 302             cds::container::OptimisticQueue< cds::gc::HP, Foo > myQueue;
 303             Bar bar;
 304             myQueue.enqueue_with( [&bar]( Foo& dest ) { dest = bar; } );
 305             \endcode
 306         */
 307         template <typename Func>
 308         bool enqueue_with( Func f )
 309         {
 310             scoped_node_ptr p( alloc_node());
 311             f( p->m_value );
 312             if ( base_class::enqueue( *p )) {
 313                 p.release();
 314                 return true;
 315             }
 316             return false;
 317         }
 318
 319         /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 320         template <typename... Args>
 321         bool emplace( Args&&... args )
 322         {
 323             scoped_node_ptr p( alloc_node_move( std::forward<Args>(args)... ));
 324             if ( base_class::enqueue( *p )) {
 325                 p.release();
 326                 return true;
 327             }
 328             return false;
 329         }
 330
 331         /// Synonym for \p enqueue( const value_type& ) function
 332         bool push( const value_type& val )
 333         {
 334             return enqueue( val );
 335         }
 336
 337         /// Synonym for \p enqueue( value_type&& ) function
 338         bool push( value_type&& val )
 339         {
 340             return enqueue( std::move( val ));
 341         }
 342
 343         /// Synonym for \p enqueue_with() function
 344         template <typename Func>
 345         bool push_with( Func f )
 346         {
 347             return enqueue_with( f );
 348         }
 349
 350         /// Dequeues a value from the queue
 351         /**
 352             If queue is not empty, the function returns \p true, \p dest contains copy of
 353             dequeued value. The assignment operator for type \p value_type is invoked.
 354
 355             If queue is empty, the function returns \p false, \p dest is unchanged.
 356         */
 357         bool dequeue( value_type& dest )
 358         {
 359             return dequeue_with( [&dest]( value_type& src ) { dest = std::move( src ); });
 360         }
 361
 362         /// Dequeues a value using a functor
 363         /**
 364             \p Func is a functor called to copy dequeued value.
 365             The functor takes one argument - a reference to removed node:
 366             \code
 367             cds:container::OptimisticQueue< cds::gc::HP, Foo > myQueue;
 368             Bar bar;
 369             myQueue.dequeue_with( [&bar]( Foo& src ) { bar = std::move( src );});
 370             \endcode
 371             The functor is called only if the queue is not empty.
 372         */
 373         template <typename Func>
 374         bool dequeue_with( Func f )
 375         {
 376             typename base_class::dequeue_result res;
 377             if ( base_class::do_dequeue( res )) {
 378                 f( node_traits::to_value_ptr( *res.pNext )->m_value );
 379
 380                 base_class::dispose_result( res );
 381
 382                 return true;
 383             }
 384             return false;
 385         }
 386
 387         /// Synonym for \ref dequeue() function
 388         bool pop( value_type& dest )
 389         {
 390             return dequeue( dest );
 391         }
 392
 393         /// Synonym for template version of \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 \ref 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::OptimisticQueue::size()
 417         */
 418         size_t size() const
 419         {
 420             return base_class::size();
 421         }
 422
 423         /// Returns reference to internal statistics
 424         const stat& statistics() const
 425         {
 426             return base_class::statistics();
 427         }
 428     };
 429
 430 }}  // namespace cds::container
 431
 432 #endif //#ifndef CDSLIB_CONTAINER_OPTIMISTIC_QUEUE_H