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-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_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     protected:
 222         //@cond
 223         typedef typename maker::node_type  node_type;   ///< queue node type (derived from \p intrusive::msqueue::node)
 224
 225         typedef typename maker::cxx_allocator     cxx_allocator;
 226         typedef typename maker::node_deallocator  node_deallocator;   // deallocate node
 227         typedef typename base_class::node_traits  node_traits;
 228         //@endcond
 229
 230     protected:
 231         ///@cond
 232         static node_type * alloc_node()
 233         {
 234             return cxx_allocator().New();
 235         }
 236         static node_type * alloc_node( value_type const& val )
 237         {
 238             return cxx_allocator().New( val );
 239         }
 240         template <typename... Args>
 241         static node_type * alloc_node_move( Args&&... args )
 242         {
 243             return cxx_allocator().MoveNew( std::forward<Args>( args )... );
 244         }
 245         static void free_node( node_type * p )
 246         {
 247             node_deallocator()( p );
 248         }
 249
 250         struct node_disposer {
 251             void operator()( node_type * pNode )
 252             {
 253                 free_node( pNode );
 254             }
 255         };
 256         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
 257         //@endcond
 258
 259     public:
 260         /// Initializes empty queue
 261         MSQueue()
 262         {}
 263
 264         /// Destructor clears the queue
 265         ~MSQueue()
 266         {}
 267
 268         /// Enqueues \p val value into the queue.
 269         /**
 270             The function makes queue node in dynamic memory calling copy constructor for \p val
 271             and then it calls intrusive::MSQueue::enqueue.
 272             Returns \p true if success, \p false otherwise.
 273         */
 274         bool enqueue( value_type const& val )
 275         {
 276             scoped_node_ptr p( alloc_node(val) );
 277             if ( base_class::enqueue( *p ) ) {
 278                 p.release();
 279                 return true;
 280             }
 281             return false;
 282         }
 283
 284         /// Enqueues data to the queue using a functor
 285         /**
 286             \p Func is a functor called to create node.
 287             The functor \p f takes one argument - a reference to a new node of type \ref value_type :
 288             \code
 289             cds::container::MSQueue< cds::gc::HP, Foo > myQueue;
 290             Bar bar;
 291             myQueue.enqueue_with( [&bar]( Foo& dest ) { dest = bar; } );
 292             \endcode
 293         */
 294         template <typename Func>
 295         bool enqueue_with( Func f )
 296         {
 297             scoped_node_ptr p( alloc_node() );
 298             f( p->m_value );
 299             if ( base_class::enqueue( *p )) {
 300                 p.release();
 301                 return true;
 302             }
 303             return false;
 304         }
 305
 306         /// Enqueues data of type \ref value_type constructed from <tt>std::forward<Args>(args)...</tt>
 307         template <typename... Args>
 308         bool emplace( Args&&... args )
 309         {
 310             scoped_node_ptr p( alloc_node_move( std::forward<Args>( args )... ) );
 311             if ( base_class::enqueue( *p ) ) {
 312                 p.release();
 313                 return true;
 314             }
 315             return false;
 316         }
 317
 318         /// Synonym for \p enqueue() function
 319         bool push( value_type const& val )
 320         {
 321             return enqueue( val );
 322         }
 323
 324         /// Synonym for \p enqueue_with() function
 325         template <typename Func>
 326         bool push_with( Func f )
 327         {
 328             return enqueue_with( f );
 329         }
 330
 331         /// Dequeues a value from the queue
 332         /**
 333             If queue is not empty, the function returns \p true, \p dest contains copy of
 334             dequeued value. The assignment operator for type \ref value_type is invoked.
 335             If queue is empty, the function returns \p false, \p dest is unchanged.
 336         */
 337         bool dequeue( value_type& dest )
 338         {
 339             return dequeue_with( [&dest]( value_type& src ) { dest = src;  } );
 340         }
 341
 342         /// Dequeues a value using a functor
 343         /**
 344             \p Func is a functor called to copy dequeued value.
 345             The functor takes one argument - a reference to removed node:
 346             \code
 347             cds:container::MSQueue< cds::gc::HP, Foo > myQueue;
 348             Bar bar;
 349             myQueue.dequeue_with( [&bar]( Foo& src ) { bar = std::move( src );});
 350             \endcode
 351             The functor is called only if the queue is not empty.
 352         */
 353         template <typename Func>
 354         bool dequeue_with( Func f )
 355         {
 356             typename base_class::dequeue_result res;
 357             if ( base_class::do_dequeue( res )) {
 358                 f( node_traits::to_value_ptr( *res.pNext )->m_value );
 359                 base_class::dispose_result( res );
 360                 return true;
 361             }
 362             return false;
 363         }
 364
 365         /// Synonym for \p dequeue() function
 366         bool pop( value_type& dest )
 367         {
 368             return dequeue( dest );
 369         }
 370
 371         /// Synonym for \p dequeue_with() function
 372         template <typename Func>
 373         bool pop_with( Func f )
 374         {
 375             return dequeue_with( f );
 376         }
 377
 378         /// Clear the queue
 379         /**
 380             The function repeatedly calls \ref dequeue until it returns \p nullptr.
 381         */
 382         void clear()
 383         {
 384             base_class::clear();
 385         }
 386
 387         /// Checks if the queue is empty
 388         bool empty() const
 389         {
 390             return base_class::empty();
 391         }
 392
 393         /// Returns queue's item count (see \ref intrusive::MSQueue::size for explanation)
 394         /** \copydetails cds::intrusive::MSQueue::size()
 395         */
 396         size_t size() const
 397         {
 398             return base_class::size();
 399         }
 400
 401         /// Returns reference to internal statistics
 402         const stat& statistics() const
 403         {
 404             return base_class::statistics();
 405         }
 406     };
 407
 408 }}  // namespace cds::container
 409
 410 #endif  // #ifndef CDSLIB_CONTAINER_MSQUEUE_H