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