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