cds/container/msqueue.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-2017
   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_MSQUEUE_H
  32 #define CDSLIB_CONTAINER_MSQUEUE_H
  33
  34 #include <memory>
  35 #include <cds/intrusive/msqueue.h>
  36 #include <cds/container/details/base.h>
  37
  38 namespace cds { namespace container {
  39
  40     /// MSQueue related definitions
  41     /** @ingroup cds_nonintrusive_helper
  42     */
  43     namespace msqueue {
  44         /// Internal statistics
  45         template <typename Counter = cds::intrusive::msqueue::stat<>::counter_type >
  46         using stat = cds::intrusive::msqueue::stat< Counter >;
  47
  48         /// Dummy internal statistics
  49         typedef cds::intrusive::msqueue::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 msqueue::stat, \p msqueue::empty_stat (the default),
  66                 user-provided class that supports \p %msqueue::stat interface.
  67             */
  68             typedef msqueue::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 msqueue::stat, \p msqueue::empty_stat, user-provided class that supports \p %msqueue::stat interface.
  90                 Default is \p %msqueue::empty_stat.
  91             - \p opt::padding - padding for internal critical atomic data. Default is \p opt::cache_line_padding
  92             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
  93                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
  94
  95             Example: declare \p %MSQueue with item counting and internal statistics
  96             \code
  97             typedef cds::container::MSQueue< cds::gc::HP, Foo,
  98                 typename cds::container::msqueue::make_traits<
  99                     cds::opt::item_counter< cds::atomicity::item_counter >,
 100                     cds::opt::stat< cds::container::msqueue::stat<> >
 101                 >::type
 102             > myQueue;
 103             \endcode
 104         */
 105         template <typename... Options>
 106         struct make_traits {
 107 #   ifdef CDS_DOXYGEN_INVOKED
 108             typedef implementation_defined type;   ///< Metafunction result
 109 #   else
 110             typedef typename cds::opt::make_options<
 111                 typename cds::opt::find_type_traits< traits, Options... >::type
 112                 , Options...
 113             >::type type;
 114 #   endif
 115         };
 116     } // namespace msqueue
 117
 118     //@cond
 119     namespace details {
 120         template <typename GC, typename T, typename Traits>
 121         struct make_msqueue
 122         {
 123             typedef GC gc;
 124             typedef T value_type;
 125             typedef Traits traits;
 126
 127             struct node_type : public intrusive::msqueue::node< gc >
 128             {
 129                 value_type  m_value;
 130
 131                 node_type( value_type const& val )
 132                     : m_value( val )
 133                 {}
 134
 135                 template <typename... Args>
 136                 node_type( Args&&... args )
 137                     : m_value( std::forward<Args>( args )... )
 138                 {}
 139             };
 140
 141             typedef typename traits::allocator::template rebind<node_type>::other allocator_type;
 142             typedef cds::details::Allocator< node_type, allocator_type >           cxx_allocator;
 143
 144             struct node_deallocator
 145             {
 146                 void operator ()( node_type * pNode )
 147                 {
 148                     cxx_allocator().Delete( pNode );
 149                 }
 150             };
 151
 152             struct intrusive_traits : public traits
 153             {
 154                 typedef cds::intrusive::msqueue::base_hook< cds::opt::gc<gc> > hook;
 155                 typedef node_deallocator disposer;
 156                 static CDS_CONSTEXPR const cds::intrusive::opt::link_check_type link_checker = cds::intrusive::msqueue::traits::link_checker;
 157             };
 158
 159             typedef intrusive::MSQueue< gc, node_type, intrusive_traits > type;
 160         };
 161     }
 162     //@endcond
 163
 164     /// Michael & Scott lock-free queue
 165     /** @ingroup cds_nonintrusive_queue
 166         It is non-intrusive version of Michael & Scott's queue algorithm based on intrusive implementation
 167         \p cds::intrusive::MSQueue.
 168
 169         Template arguments:
 170         - \p GC - garbage collector type: \p gc::HP, \p gc::DHP
 171         - \p T is a type stored in the queue.
 172         - \p Traits - queue traits, default is \p msqueue::traits. You can use \p msqueue::make_traits
 173             metafunction to make your traits or just derive your traits from \p %msqueue::traits:
 174             \code
 175             struct myTraits: public cds::container::msqueue::traits {
 176                 typedef cds::intrusive::msqueue::stat<> stat;
 177                 typedef cds::atomicity::item_counter    item_counter;
 178             };
 179             typedef cds::container::MSQueue< cds::gc::HP, Foo, myTraits > myQueue;
 180
 181             // Equivalent make_traits example:
 182             typedef cds::container::MSQueue< cds::gc::HP, Foo,
 183                 typename cds::container::msqueue::make_traits<
 184                     cds::opt::stat< cds::container::msqueue::stat<> >,
 185                     cds::opt::item_counter< cds::atomicity::item_counter >
 186                 >::type
 187             > myQueue;
 188             \endcode
 189     */
 190     template <typename GC, typename T, typename Traits = cds::container::msqueue::traits>
 191     class MSQueue:
 192 #ifdef CDS_DOXYGEN_INVOKED
 193         private intrusive::MSQueue< GC, cds::intrusive::msqueue::node< T >, Traits >
 194 #else
 195         private details::make_msqueue< GC, T, Traits >::type
 196 #endif
 197     {
 198         //@cond
 199         typedef details::make_msqueue< GC, T, Traits > maker;
 200         typedef typename maker::type base_class;
 201         //@endcond
 202
 203     public:
 204         /// Rebind template arguments
 205         template <typename GC2, typename T2, typename Traits2>
 206         struct rebind {
 207             typedef MSQueue< GC2, T2, Traits2> other   ;   ///< Rebinding result
 208         };
 209
 210     public:
 211         typedef T value_type;   ///< Value type stored in the queue
 212         typedef Traits traits;  ///< Queue traits
 213
 214         typedef typename base_class::gc             gc;             ///< Garbage collector used
 215         typedef typename base_class::back_off       back_off;       ///< Back-off strategy used
 216         typedef typename maker::allocator_type      allocator_type; ///< Allocator type used for allocate/deallocate the nodes
 217         typedef typename base_class::item_counter   item_counter;   ///< Item counting policy used
 218         typedef typename base_class::stat           stat;           ///< Internal statistics policy used
 219         typedef typename base_class::memory_model   memory_model;   ///< Memory ordering. See cds::opt::memory_model option
 220
 221         static CDS_CONSTEXPR const size_t c_nHazardPtrCount = base_class::c_nHazardPtrCount; ///< Count of hazard pointer required for the algorithm
 222
 223     protected:
 224         //@cond
 225         typedef typename maker::node_type  node_type;   ///< queue node type (derived from \p intrusive::msqueue::node)
 226
 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( value_type const& 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         MSQueue()
 264         {}
 265
 266         /// Destructor clears the queue
 267         ~MSQueue()
 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::MSQueue::enqueue.
 274             Returns \p true if success, \p false otherwise.
 275         */
 276         bool enqueue( value_type const& 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 in the queue, move semantics
 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 data to the 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::MSQueue< 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 from <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() function
 332         bool push( value_type const& val )
 333         {
 334             return enqueue( val );
 335         }
 336
 337         /// Synonym for \p enqueue() 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 \ref value_type is invoked.
 354             If queue is empty, the function returns \p false, \p dest is unchanged.
 355         */
 356         bool dequeue( value_type& dest )
 357         {
 358             return dequeue_with( [&dest]( value_type& src ) {
 359                 // TSan finds a race between this read of \p src and node_type constructor
 360                 // I think, it is wrong
 361                 CDS_TSAN_ANNOTATE_IGNORE_READS_BEGIN;
 362                 dest = std::move( src );
 363                 CDS_TSAN_ANNOTATE_IGNORE_READS_END;
 364             });
 365         }
 366
 367         /// Dequeues a value using a functor
 368         /**
 369             \p Func is a functor called to copy dequeued value.
 370             The functor takes one argument - a reference to removed node:
 371             \code
 372             cds:container::MSQueue< cds::gc::HP, Foo > myQueue;
 373             Bar bar;
 374             myQueue.dequeue_with( [&bar]( Foo& src ) { bar = std::move( src );});
 375             \endcode
 376             The functor is called only if the queue is not empty.
 377         */
 378         template <typename Func>
 379         bool dequeue_with( Func f )
 380         {
 381             typename base_class::dequeue_result res;
 382             if ( base_class::do_dequeue( res )) {
 383                 f( node_traits::to_value_ptr( *res.pNext )->m_value );
 384                 base_class::dispose_result( res );
 385                 return true;
 386             }
 387             return false;
 388         }
 389
 390         /// Synonym for \p dequeue() function
 391         bool pop( value_type& dest )
 392         {
 393             return dequeue( dest );
 394         }
 395
 396         /// Synonym for \p dequeue_with() function
 397         template <typename Func>
 398         bool pop_with( Func f )
 399         {
 400             return dequeue_with( f );
 401         }
 402
 403         /// Clear the queue
 404         /**
 405             The function repeatedly calls \ref dequeue until it returns \p nullptr.
 406         */
 407         void clear()
 408         {
 409             base_class::clear();
 410         }
 411
 412         /// Checks if the queue is empty
 413         bool empty() const
 414         {
 415             return base_class::empty();
 416         }
 417
 418         /// Returns queue's item count (see \ref intrusive::MSQueue::size for explanation)
 419         /** \copydetails cds::intrusive::MSQueue::size()
 420         */
 421         size_t size() const
 422         {
 423             return base_class::size();
 424         }
 425
 426         /// Returns reference to internal statistics
 427         const stat& statistics() const
 428         {
 429             return base_class::statistics();
 430         }
 431     };
 432
 433 }}  // namespace cds::container
 434
 435 #endif  // #ifndef CDSLIB_CONTAINER_MSQUEUE_H