cds/container/basket_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_BASKET_QUEUE_H
  32 #define CDSLIB_CONTAINER_BASKET_QUEUE_H
  33
  34 #include <memory>
  35 #include <cds/intrusive/basket_queue.h>
  36 #include <cds/container/details/base.h>
  37 //#include <cds/details/trivial_assign.h>
  38
  39 namespace cds { namespace container {
  40
  41     /// BasketQueue related definitions
  42     /** @ingroup cds_nonintrusive_helper
  43     */
  44     namespace basket_queue {
  45
  46         /// Internal statistics
  47         template <typename Counter = cds::intrusive::basket_queue::stat<>::counter_type >
  48         using stat = cds::intrusive::basket_queue::stat< Counter >;
  49
  50         /// Dummy internal statistics
  51         typedef cds::intrusive::basket_queue::empty_stat empty_stat;
  52
  53         /// BasketQueue default type traits
  54         struct traits
  55         {
  56             /// Node allocator
  57             typedef CDS_DEFAULT_ALLOCATOR       allocator;
  58
  59             /// Back-off strategy
  60             typedef cds::backoff::empty         back_off;
  61
  62             /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
  63             typedef atomicity::empty_item_counter   item_counter;
  64
  65             /// Internal statistics (by default, disabled)
  66             /**
  67                 Possible option value are: \p basket_queue::stat, \p basket_queue::empty_stat (the default),
  68                 user-provided class that supports \p %basket_queue::stat interface.
  69             */
  70             typedef basket_queue::empty_stat         stat;
  71
  72             /// C++ memory ordering model
  73             /**
  74                 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
  75                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
  76             */
  77             typedef opt::v::relaxed_ordering    memory_model;
  78
  79             /// Padding for internal critical atomic data. Default is \p opt::cache_line_padding
  80             enum { padding = opt::cache_line_padding };
  81         };
  82
  83         /// Metafunction converting option list to \p basket_queue::traits
  84         /**
  85             Supported \p Options are:
  86             - \p opt::allocator - allocator (like \p std::allocator) used for allocating queue nodes. Default is \ref CDS_DEFAULT_ALLOCATOR
  87             - \p opt::back_off - back-off strategy used, default is \p cds::backoff::empty.
  88             - \p opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter (item counting disabled)
  89                 To enable item counting use \p cds::atomicity::item_counter
  90             - \ opt::stat - the type to gather internal statistics.
  91                 Possible statistics types are: \p basket_queue::stat, \p basket_queue::empty_stat, user-provided class that supports \p %basket_queue::stat interface.
  92                 Default is \p %basket_queue::empty_stat.
  93             - \p opt::padding - padding for internal critical atomic data. Default is \p opt::cache_line_padding
  94             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
  95                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
  96
  97             Example: declare \p %BasketQueue with item counting and internal statistics
  98             \code
  99             typedef cds::container::BasketQueue< cds::gc::HP, Foo,
 100                 typename cds::container::basket_queue::make_traits<
 101                     cds::opt::item_counte< cds::atomicity::item_counter >,
 102                     cds::opt::stat< cds::intrusive::basket_queue::stat<> >
 103                 >::type
 104             > myQueue;
 105             \endcode
 106         */
 107         template <typename... Options>
 108         struct make_traits {
 109 #   ifdef CDS_DOXYGEN_INVOKED
 110             typedef implementation_defined type;   ///< Metafunction result
 111 #   else
 112             typedef typename cds::opt::make_options<
 113                 typename cds::opt::find_type_traits< traits, Options... >::type
 114                 , Options...
 115             >::type type;
 116 #   endif
 117         };
 118     } // namespace basket_queue
 119
 120     //@cond
 121     namespace details {
 122         template <typename GC, typename T, typename Traits>
 123         struct make_basket_queue
 124         {
 125             typedef GC gc;
 126             typedef T value_type;
 127             typedef Traits traits;
 128
 129             struct node_type: public intrusive::basket_queue::node< gc >
 130             {
 131                 value_type  m_value;
 132
 133                 node_type( const value_type& val )
 134                     : m_value( val )
 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::basket_queue::base_hook< opt::gc<gc> > hook;
 156                 typedef node_deallocator disposer;
 157                 static CDS_CONSTEXPR const cds::intrusive::opt::link_check_type link_checker = cds::intrusive::basket_queue::traits::link_checker;
 158             };
 159
 160             typedef cds::intrusive::BasketQueue< gc, node_type, intrusive_traits > type;
 161         };
 162     }
 163     //@endcond
 164
 165     /// Basket lock-free queue (non-intrusive variant)
 166     /** @ingroup cds_nonintrusive_queue
 167         It is non-intrusive version of basket queue algorithm based on intrusive::BasketQueue counterpart.
 168
 169         \par Source:
 170             [2007] Moshe Hoffman, Ori Shalev, Nir Shavit "The Baskets Queue"
 171
 172         <b>Key idea</b>
 173
 174         In the 'basket' approach, instead of
 175         the traditional ordered list of nodes, the queue consists of an ordered list of groups
 176         of nodes (logical baskets). The order of nodes in each basket need not be specified, and in
 177         fact, it is easiest to maintain them in LIFO order. The baskets fulfill the following basic
 178         rules:
 179         - Each basket has a time interval in which all its nodes' enqueue operations overlap.
 180         - The baskets are ordered by the order of their respective time intervals.
 181         - For each basket, its nodes' dequeue operations occur after its time interval.
 182         - The dequeue operations are performed according to the order of baskets.
 183
 184         Two properties define the FIFO order of nodes:
 185         - The order of nodes in a basket is not specified.
 186         - The order of nodes in different baskets is the FIFO-order of their respective baskets.
 187
 188         In algorithms such as the MS-queue or optimistic
 189         queue, threads enqueue items by applying a Compare-and-swap (CAS) operation to the
 190         queue's tail pointer, and all the threads that fail on a particular CAS operation (and also
 191         the winner of that CAS) overlap in time. In particular, they share the time interval of
 192         the CAS operation itself. Hence, all the threads that fail to CAS on the tail-node of
 193         the queue may be inserted into the same basket. By integrating the basket-mechanism
 194         as the back-off mechanism, the time usually spent on backing-off before trying to link
 195         onto the new tail, can now be utilized to insert the failed operations into the basket,
 196         allowing enqueues to complete sooner. In the meantime, the next successful CAS operations
 197         by enqueues allow new baskets to be formed down the list, and these can be
 198         filled concurrently. Moreover, the failed operations don't retry their link attempt on the
 199         new tail, lowering the overall contention on it. This leads to a queue
 200         algorithm that unlike all former concurrent queue algorithms requires virtually no tuning
 201         of the backoff mechanisms to reduce contention, making the algorithm an attractive
 202         out-of-the-box queue.
 203
 204         In order to enqueue, just as in MSQueue, a thread first tries to link the new node to
 205         the last node. If it failed to do so, then another thread has already succeeded. Thus it
 206         tries to insert the new node into the new basket that was created by the winner thread.
 207         To dequeue a node, a thread first reads the head of the queue to obtain the
 208         oldest basket. It may then dequeue any node in the oldest basket.
 209
 210
 211         Template arguments:
 212         - \p GC - garbage collector type: \p gc::HP, \p gc::DHP
 213         - \p T - type of value to be stored in the queue
 214         - \p Traits - queue traits, default is \p basket_queue::traits. You can use \p basket_queue::make_traits
 215             metafunction to make your traits or just derive your traits from \p %basket_queue::traits:
 216             \code
 217             struct myTraits: public cds::container::basket_queue::traits {
 218                 typedef cds::intrusive::basket_queue::stat<> stat;
 219                 typedef cds::atomicity::item_counter    item_counter;
 220             };
 221             typedef cds::container::BasketQueue< cds::gc::HP, Foo, myTraits > myQueue;
 222
 223             // Equivalent make_traits example:
 224             typedef cds::container::BasketQueue< cds::gc::HP, Foo,
 225                 typename cds::container::basket_queue::make_traits<
 226                     cds::opt::stat< cds::container::basket_queue::stat<> >,
 227                     cds::opt::item_counter< cds::atomicity::item_counter >
 228                 >::type
 229             > myQueue;
 230             \endcode
 231     */
 232     template <typename GC, typename T, typename Traits = basket_queue::traits >
 233     class BasketQueue:
 234 #ifdef CDS_DOXYGEN_INVOKED
 235         private intrusive::BasketQueue< GC, intrusive::basket_queue::node< T >, Traits >
 236 #else
 237         protected details::make_basket_queue< GC, T, Traits >::type
 238 #endif
 239     {
 240         //@cond
 241         typedef details::make_basket_queue< GC, T, Traits > maker;
 242         typedef typename maker::type base_class;
 243         //@endcond
 244
 245     public:
 246         /// Rebind template arguments
 247         template <typename GC2, typename T2, typename Traits2>
 248         struct rebind {
 249             typedef BasketQueue< GC2, T2, Traits2> other   ;   ///< Rebinding result
 250         };
 251
 252     public:
 253         typedef GC gc;          ///< Garbage collector
 254         typedef T  value_type;  ///< Type of value to be stored in the queue
 255         typedef Traits traits;  ///< Queue's traits
 256
 257         typedef typename base_class::back_off       back_off;       ///< Back-off strategy used
 258         typedef typename maker::allocator_type      allocator_type; ///< Allocator type used for allocate/deallocate the nodes
 259         typedef typename base_class::item_counter   item_counter;   ///< Item counting policy used
 260         typedef typename base_class::stat           stat;           ///< Internal statistics policy used
 261         typedef typename base_class::memory_model   memory_model;   ///< Memory ordering. See cds::opt::memory_model option
 262
 263     protected:
 264         typedef typename maker::node_type node_type; ///< queue node type (derived from intrusive::basket_queue::node)
 265
 266         //@cond
 267         typedef typename maker::cxx_allocator     cxx_allocator;
 268         typedef typename maker::node_deallocator  node_deallocator;   // deallocate node
 269         typedef typename base_class::node_traits  node_traits;
 270         //@endcond
 271
 272     protected:
 273         ///@cond
 274         static node_type * alloc_node()
 275         {
 276             return cxx_allocator().New();
 277         }
 278         static node_type * alloc_node( const value_type& val )
 279         {
 280             return cxx_allocator().New( val );
 281         }
 282         template <typename... Args>
 283         static node_type * alloc_node_move( Args&&... args )
 284         {
 285             return cxx_allocator().MoveNew( std::forward<Args>( args )... );
 286         }
 287         static void free_node( node_type * p )
 288         {
 289             node_deallocator()( p );
 290         }
 291
 292         struct node_disposer {
 293             void operator()( node_type * pNode )
 294             {
 295                 free_node( pNode );
 296             }
 297         };
 298         typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
 299         //@endcond
 300
 301     public:
 302         /// Initializes empty queue
 303         BasketQueue()
 304         {}
 305
 306         /// Destructor clears the queue
 307         ~BasketQueue()
 308         {}
 309
 310         /// Enqueues \p val value into the queue.
 311         /**
 312             The function makes queue node in dynamic memory calling copy constructor for \p val
 313             and then it calls \p intrusive::BasketQueue::enqueue().
 314             Returns \p true if success, \p false otherwise.
 315         */
 316         bool enqueue( value_type const& val )
 317         {
 318             scoped_node_ptr p( alloc_node(val));
 319             if ( base_class::enqueue( *p )) {
 320                 p.release();
 321                 return true;
 322             }
 323             return false;
 324         }
 325
 326         /// Enqueues \p data to queue using a functor
 327         /**
 328             \p Func is a functor called to create node.
 329             The functor \p f takes one argument - a reference to a new node of type \ref value_type :
 330             \code
 331             cds::container::BasketQueue< cds::gc::HP, Foo > myQueue;
 332             Bar bar;
 333             myQueue.enqueue_with( [&bar]( Foo& dest ) { dest = bar; } );
 334             \endcode
 335         */
 336         template <typename Func>
 337         bool enqueue_with( Func f )
 338         {
 339             scoped_node_ptr p( alloc_node() );
 340             f( p->m_value );
 341             if ( base_class::enqueue( *p )) {
 342                 p.release();
 343                 return true;
 344             }
 345             return false;
 346         }
 347
 348         /// Synonym for \p enqueue() function
 349         bool push( const value_type& val )
 350         {
 351             return enqueue( val );
 352         }
 353
 354         /// Synonym for \p enqueue_with() function
 355         template <typename Func>
 356         bool push_with( Func f )
 357         {
 358             return enqueue_with( f );
 359         }
 360
 361         /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 362         template <typename... Args>
 363         bool emplace( Args&&... args )
 364         {
 365             scoped_node_ptr p( alloc_node_move( std::forward<Args>(args)...));
 366             if ( base_class::enqueue( *p )) {
 367                 p.release();
 368                 return true;
 369             }
 370             return false;
 371         }
 372
 373         /// Dequeues a value from the queue
 374         /**
 375             If queue is not empty, the function returns \p true, \p dest contains copy of
 376             dequeued value. The assignment operator for type \ref value_type is invoked.
 377             If queue is empty, the function returns \p false, \p dest is unchanged.
 378         */
 379         bool dequeue( value_type& dest )
 380         {
 381             return dequeue_with( [&dest]( value_type& src ) { dest = src;  } );
 382         }
 383
 384         /// Dequeues a value using a functor
 385         /**
 386             \p Func is a functor called to copy dequeued value.
 387             The functor takes one argument - a reference to removed node:
 388             \code
 389             cds:container::BasketQueue< cds::gc::HP, Foo > myQueue;
 390             Bar bar;
 391             myQueue.dequeue_with( [&bar]( Foo& src ) { bar = std::move( src );});
 392             \endcode
 393             The functor is called only if the queue is not empty.
 394         */
 395         template <typename Func>
 396         bool dequeue_with( Func f )
 397         {
 398             typename base_class::dequeue_result res;
 399             if ( base_class::do_dequeue( res, true )) {
 400                 f( node_traits::to_value_ptr( *res.pNext )->m_value );
 401                 return true;
 402             }
 403             return false;
 404         }
 405
 406         /// Synonym for \p dequeue() function
 407         bool pop( value_type& dest )
 408         {
 409             return dequeue( dest );
 410         }
 411
 412         /// Synonym for \p dequeue_with() function
 413         template <typename Func>
 414         bool pop_with( Func f )
 415         {
 416             return dequeue_with( f );
 417         }
 418
 419         /// Checks if the queue is empty
 420         /**
 421             Note that this function is not \p const.
 422             The function is based on \p dequeue() algorithm.
 423         */
 424         bool empty()
 425         {
 426             return base_class::empty();
 427         }
 428
 429         /// Clear the queue
 430         /**
 431             The function repeatedly calls \ref dequeue until it returns \p nullptr.
 432         */
 433         void clear()
 434         {
 435             base_class::clear();
 436         }
 437
 438         /// Returns queue's item count
 439         /** \copydetails cds::intrusive::BasketQueue::size()
 440         */
 441         size_t size() const
 442         {
 443             return base_class::size();
 444         }
 445
 446         /// Returns reference to internal statistics
 447         const stat& statistics() const
 448         {
 449             return base_class::statistics();
 450         }
 451
 452     };
 453
 454 }}  // namespace cds::container
 455
 456 #endif  // #ifndef CDSLIB_CONTAINER_BASKET_QUEUE_H