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