cds/container/basket_queue.h

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