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 intrusive::basket_queue::base_hook< opt::gc<gc> > hook;
 128                 typedef node_deallocator disposer;
 129             };
 130
 131             typedef cds::intrusive::BasketQueue< gc, node_type, intrusive_traits > type;
 132         };
 133     }
 134     //@endcond
 135
 136     /// Basket lock-free queue (non-intrusive variant)
 137     /** @ingroup cds_nonintrusive_queue
 138         It is non-intrusive version of basket queue algorithm based on intrusive::BasketQueue counterpart.
 139
 140         \par Source:
 141             [2007] Moshe Hoffman, Ori Shalev, Nir Shavit "The Baskets Queue"
 142
 143         <b>Key idea</b>
 144
 145         In the \93basket\94 approach, instead of
 146         the traditional ordered list of nodes, the queue consists of an ordered list of groups
 147         of nodes (logical baskets). The order of nodes in each basket need not be specified, and in
 148         fact, it is easiest to maintain them in LIFO order. The baskets fulfill the following basic
 149         rules:
 150         - Each basket has a time interval in which all its nodes\92 enqueue operations overlap.
 151         - The baskets are ordered by the order of their respective time intervals.
 152         - For each basket, its nodes\92 dequeue operations occur after its time interval.
 153         - The dequeue operations are performed according to the order of baskets.
 154
 155         Two properties define the FIFO order of nodes:
 156         - The order of nodes in a basket is not specified.
 157         - The order of nodes in different baskets is the FIFO-order of their respective baskets.
 158
 159         In algorithms such as the MS-queue or optimistic
 160         queue, threads enqueue items by applying a Compare-and-swap (CAS) operation to the
 161         queue\92s tail pointer, and all the threads that fail on a particular CAS operation (and also
 162         the winner of that CAS) overlap in time. In particular, they share the time interval of
 163         the CAS operation itself. Hence, all the threads that fail to CAS on the tail-node of
 164         the queue may be inserted into the same basket. By integrating the basket-mechanism
 165         as the back-off mechanism, the time usually spent on backing-off before trying to link
 166         onto the new tail, can now be utilized to insert the failed operations into the basket,
 167         allowing enqueues to complete sooner. In the meantime, the next successful CAS operations
 168         by enqueues allow new baskets to be formed down the list, and these can be
 169         filled concurrently. Moreover, the failed operations don\92t retry their link attempt on the
 170         new tail, lowering the overall contention on it. This leads to a queue
 171         algorithm that unlike all former concurrent queue algorithms requires virtually no tuning
 172         of the backoff mechanisms to reduce contention, making the algorithm an attractive
 173         out-of-the-box queue.
 174
 175         In order to enqueue, just as in MSQueue, a thread first tries to link the new node to
 176         the last node. If it failed to do so, then another thread has already succeeded. Thus it
 177         tries to insert the new node into the new basket that was created by the winner thread.
 178         To dequeue a node, a thread first reads the head of the queue to obtain the
 179         oldest basket. It may then dequeue any node in the oldest basket.
 180
 181
 182         Template arguments:
 183         - \p GC - garbage collector type: \p gc::HP, \p gc::DHP
 184         - \p T - type of value to be stored in the queue
 185         - \p Traits - queue traits, default is \p basket_queue::traits. You can use \p basket_queue::make_traits
 186             metafunction to make your traits or just derive your traits from \p %basket_queue::traits:
 187             \code
 188             struct myTraits: public cds::container::basket_queue::traits {
 189                 typedef cds::intrusive::basket_queue::stat<> stat;
 190                 typedef cds::atomicity::item_counter    item_counter;
 191             };
 192             typedef cds::container::BasketQueue< cds::gc::HP, Foo, myTraits > myQueue;
 193
 194             // Equivalent make_traits example:
 195             typedef cds::container::BasketQueue< cds::gc::HP, Foo,
 196                 typename cds::container::basket_queue::make_traits<
 197                     cds::opt::stat< cds::container::basket_queue::stat<> >,
 198                     cds::opt::item_counter< cds::atomicity::item_counter >
 199                 >::type
 200             > myQueue;
 201             \endcode
 202     */
 203     template <typename GC, typename T, typename Traits = basket_queue::traits >
 204     class BasketQueue:
 205 #ifdef CDS_DOXYGEN_INVOKED
 206         private intrusive::BasketQueue< GC, intrusive::basket_queue::node< T >, Traits >
 207 #else
 208         protected details::make_basket_queue< GC, T, Traits >::type
 209 #endif
 210     {
 211         //@cond
 212         typedef details::make_basket_queue< GC, T, Options... > maker;
 213         typedef typename maker::type base_class;
 214         //@endcond
 215
 216     public:
 217         /// Rebind template arguments
 218         template <typename GC2, typename T2, typename Traits2>
 219         struct rebind {
 220             typedef BasketQueue< GC2, T2, Traits2> other   ;   ///< Rebinding result
 221         };
 222
 223     public:
 224         typedef GC gc;          ///< Garbage collector
 225         typedef T  value_type;  ///< Type of value to be stored in the queue
 226         typedef Traits traits;  ///< Queue's traits
 227
 228         typedef typename base_class::back_off       back_off;       ///< Back-off strategy used
 229         typedef typename maker::allocator_type      allocator_type; ///< Allocator type used for allocate/deallocate the nodes
 230         typedef typename base_class::item_counter   item_counter;   ///< Item counting policy used
 231         typedef typename base_class::stat           stat;           ///< Internal statistics policy used
 232         typedef typename base_class::memory_model   memory_model;   ///< Memory ordering. See cds::opt::memory_model option
 233
 234     protected:
 235         typedef typename maker::node_type node_type; ///< queue node type (derived from intrusive::basket_queue::node)
 236
 237         //@cond
 238         typedef typename maker::cxx_allocator     cxx_allocator;
 239         typedef typename maker::node_deallocator  node_deallocator;   // deallocate node
 240         typedef typename base_class::node_traits  node_traits;
 241         //@endcond
 242
 243     protected:
 244         ///@cond
 245         static node_type * alloc_node()
 246         {
 247             return cxx_allocator().New();
 248         }
 249         static node_type * alloc_node( const value_type& val )
 250         {
 251             return cxx_allocator().New( val );
 252         }
 253         template <typename... Args>
 254         static node_type * alloc_node_move( Args&&... args )
 255         {
 256             return cxx_allocator().MoveNew( std::forward<Args>( args )... );
 257         }
 258         static void free_node( node_type * p )
 259         {
 260             node_deallocator()( p );
 261         }
 262
 263         struct node_disposer {
 264             void operator()( node_type * pNode )
 265             {
 266                 free_node( pNode );
 267             }
 268         };
 269         typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
 270         //@endcond
 271
 272     public:
 273         /// Initializes empty queue
 274         BasketQueue()
 275         {}
 276
 277         /// Destructor clears the queue
 278         ~BasketQueue()
 279         {}
 280
 281         /// Enqueues \p val value into the queue.
 282         /**
 283             The function makes queue node in dynamic memory calling copy constructor for \p val
 284             and then it calls \p intrusive::BasketQueue::enqueue().
 285             Returns \p true if success, \p false otherwise.
 286         */
 287         bool enqueue( value_type const& val )
 288         {
 289             scoped_node_ptr p( alloc_node(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::BasketQueue< 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         /// Synonym for \p enqueue() function
 320         bool push( const value_type& val )
 321         {
 322             return enqueue( val );
 323         }
 324
 325         /// Synonym for \p enqueue_with() function
 326         template <typename Func>
 327         bool push_with( Func f )
 328         {
 329             return enqueue_with( f );
 330         }
 331
 332         /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 333         template <typename... Args>
 334         bool emplace( Args&&... args )
 335         {
 336             scoped_node_ptr p( alloc_node_move( std::forward<Args>(args)...));
 337             if ( base_class::enqueue( *p )) {
 338                 p.release();
 339                 return true;
 340             }
 341             return false;
 342         }
 343
 344         /// Dequeues a value from the queue
 345         /**
 346             If queue is not empty, the function returns \p true, \p dest contains copy of
 347             dequeued value. The assignment operator for type \ref value_type is invoked.
 348             If queue is empty, the function returns \p false, \p dest is unchanged.
 349         */
 350         bool dequeue( value_type& dest )
 351         {
 352             return dequeue_with( [&dest]( value_type& src ) { dest = src;  } );
 353         }
 354
 355         /// Dequeues a value using a functor
 356         /**
 357             \p Func is a functor called to copy dequeued value.
 358             The functor takes one argument - a reference to removed node:
 359             \code
 360             cds:container::BasketQueue< cds::gc::HP, Foo > myQueue;
 361             Bar bar;
 362             myQueue.dequeue_with( [&bar]( Foo& src ) { bar = std::move( src );});
 363             \endcode
 364             The functor is called only if the queue is not empty.
 365         */
 366         template <typename Func>
 367         bool dequeue_with( Func f )
 368         {
 369             typename base_class::dequeue_result res;
 370             if ( base_class::do_dequeue( res, true )) {
 371                 f( node_traits::to_value_ptr( *res.pNext )->m_value );
 372                 base_class::dispose_result( res );
 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