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