cds/container/segmented_queue.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_SEGMENTED_QUEUE_H
   4 #define __CDS_CONTAINER_SEGMENTED_QUEUE_H
   5
   6 #include <memory>
   7 #include <cds/intrusive/segmented_queue.h>
   8 #include <cds/details/trivial_assign.h>
   9 #include <cds/ref.h>
  10
  11 namespace cds { namespace container {
  12
  13     /// SegmentedQueue -related declarations
  14     namespace segmented_queue {
  15
  16 #   ifdef CDS_DOXYGEN_INVOKED
  17         /// SegmentedQueue internal statistics
  18         typedef cds::intrusive::segmented_queue::stat stat;
  19 #   else
  20         using cds::intrusive::segmented_queue::stat;
  21 #   endif
  22
  23         /// SegmentedQueue empty internal statistics (no overhead)
  24         typedef cds::intrusive::segmented_queue::empty_stat empty_stat;
  25
  26         /// SegmentedQueue default type traits
  27         struct type_traits {
  28
  29             /// Item allocator. Default is \ref CDS_DEFAULT_ALLOCATOR
  30             typedef CDS_DEFAULT_ALLOCATOR   node_allocator;
  31
  32             /// Item counter, default is atomicity::item_counter
  33             /**
  34                 The item counting is an essential part of segmented queue algorithm.
  35                 The \p empty() member function is based on checking <tt>size() == 0</tt>.
  36                 Therefore, dummy item counter like atomicity::empty_item_counter is not the proper counter.
  37             */
  38             typedef atomicity::item_counter item_counter;
  39
  40             /// Internal statistics, possible predefined types are \ref stat, \ref empty_stat (the default)
  41             typedef segmented_queue::empty_stat        stat;
  42
  43             /// Memory model, default is opt::v::relaxed_ordering. See cds::opt::memory_model for the full list of possible types
  44             typedef opt::v::relaxed_ordering  memory_model;
  45
  46             /// Alignment of critical data, default is cache line alignment. See cds::opt::alignment option specification
  47             enum { alignment = opt::cache_line_alignment };
  48
  49             /// Segment allocator. Default is \ref CDS_DEFAULT_ALLOCATOR
  50             typedef CDS_DEFAULT_ALLOCATOR allocator;
  51
  52             /// Lock type used to maintain an internal list of allocated segments
  53             typedef cds::lock::Spin lock_type;
  54
  55             /// Random \ref cds::opt::permutation_generator "permutation generator" for sequence [0, quasi_factor)
  56             typedef cds::opt::v::random2_permutation<int>    permutation_generator;
  57         };
  58
  59          /// Metafunction converting option list to traits for SegmentedQueue
  60         /**
  61             The metafunction can be useful if a few fields in \ref type_traits should be changed.
  62             For example:
  63             \code
  64             typedef cds::container::segmented_queue::make_traits<
  65                 cds::opt::item_counter< cds::atomicity::item_counter >
  66             >::type my_segmented_queue_traits;
  67             \endcode
  68             This code creates \p %SegmentedQueue type traits with item counting feature,
  69             all other \p type_traits members left unchanged.
  70
  71             \p Options are:
  72             - \p opt::node_allocator - node allocator.
  73             - \p opt::stat - internal statistics, possible type: \ref stat, \ref empty_stat (the default)
  74             - \p opt::item_counter - item counting feature. Note that atomicity::empty_item_counetr is not suitable
  75                 for segmented queue.
  76             - \p opt::memory_model - memory model, default is \p opt::v::relaxed_ordering.
  77                 See option description for the full list of possible models
  78             - \p opt::alignment - the alignmentfor critical data, see option description for explanation
  79             - \p opt::allocator - the allocator used to maintain segments.
  80             - \p opt::lock_type - a mutual exclusion lock type used to maintain internal list of allocated
  81                 segments. Default is \p cds::opt::Spin, \p std::mutex is also suitable.
  82             - \p opt::permutation_generator - a random permutation generator for sequence [0, quasi_factor),
  83                 default is cds::opt::v::random2_permutation<int>
  84         */
  85         template <CDS_DECL_OPTIONS9>
  86         struct make_traits {
  87 #   ifdef CDS_DOXYGEN_INVOKED
  88             typedef implementation_defined type ;   ///< Metafunction result
  89 #   else
  90             typedef typename cds::opt::make_options<
  91                 typename cds::opt::find_type_traits< type_traits, CDS_OPTIONS9 >::type
  92                 ,CDS_OPTIONS9
  93             >::type   type;
  94 #   endif
  95         };
  96
  97     } // namespace segmented_queue
  98
  99     //@cond
 100     namespace details {
 101
 102         template <typename GC, typename T, typename Traits>
 103         struct make_segmented_queue
 104         {
 105             typedef GC      gc;
 106             typedef T       value_type;
 107             typedef Traits  original_type_traits;
 108
 109             typedef cds::details::Allocator< T, typename original_type_traits::node_allocator > cxx_node_allocator;
 110             struct node_disposer {
 111                 void operator()( T * p )
 112                 {
 113                     cxx_node_allocator().Delete( p );
 114                 }
 115             };
 116
 117             struct intrusive_type_traits: public original_type_traits {
 118                 typedef node_disposer   disposer;
 119             };
 120
 121             typedef cds::intrusive::SegmentedQueue< gc, value_type, intrusive_type_traits > type;
 122         };
 123
 124     } // namespace details
 125     //@endcond
 126
 127     /// Segmented queue
 128     /** @ingroup cds_nonintrusive_queue
 129
 130         The queue is based on work
 131         - [2010] Afek, Korland, Yanovsky "Quasi-Linearizability: relaxed consistency for improved concurrency"
 132
 133         In this paper the authors offer a relaxed version of linearizability, so-called quasi-linearizability,
 134         that preserves some of the intuition, provides a flexible way to control the level of relaxation
 135         and supports th implementation of more concurrent and scalable data structure.
 136         Intuitively, the linearizability requires each run to be equivalent in some sense to a serial run
 137         of the algorithm. This equivalence to some serial run imposes strong synchronization requirements
 138         that in many cases results in limited scalability and synchronization bottleneck.
 139
 140         The general idea is that the queue maintains a linked list of segments, each segment is an array of
 141         nodes in the size of the quasi factor, and each node has a deleted boolean marker, which states
 142         if it has been dequeued. Each producer iterates over last segment in the linked list in some random
 143         permutation order. Whet it finds an empty cell it performs a CAS operation attempting to enqueue its
 144         new element. In case the entire segment has been scanned and no available cell is found (implying
 145         that the segment is full), then it attempts to add a new segment to the list.
 146
 147         The dequeue operation is similar: the consumer iterates over the first segment in the linked list
 148         in some random permutation order. When it finds an item which has not yet been dequeued, it performs
 149         CAS on its deleted marker in order to "delete" it, if succeeded this item is considered dequeued.
 150         In case the entire segment was scanned and all the nodes have already been dequeued (implying that
 151         the segment is empty), then it attempts to remove this segment from the linked list and starts
 152         the same process on the next segment. If there is no next segment, the queue is considered empty.
 153
 154         Based on the fact that most of the time threads do not add or remove segments, most of the work
 155         is done in parallel on different cells in the segments. This ensures a controlled contention
 156         depending on the segment size, which is quasi factor.
 157
 158         The segmented queue is an <i>unfair</i> queue since it violates the strong FIFO order but no more than
 159         quasi factor. It means that the consumer dequeues any item from the current first segment.
 160
 161         Template parameters:
 162         - \p GC - a garbage collector, possible types are cds::gc::HP, cds::gc::PTB
 163         - \p T - the type of values stored in the queue
 164         - \p Traits - queue type traits, default is segmented_queue::type_traits.
 165             segmented_queue::make_traits metafunction can be used to construct your
 166             type traits.
 167     */
 168     template <class GC, typename T, typename Traits = segmented_queue::type_traits >
 169     class SegmentedQueue:
 170 #ifdef CDS_DOXYGEN_INVOKED
 171         public cds::intrusive::SegmentedQueue< GC, T, Traits >
 172 #else
 173         public details::make_segmented_queue< GC, T, Traits >::type
 174 #endif
 175     {
 176         //@cond
 177         typedef details::make_segmented_queue< GC, T, Traits > maker;
 178         typedef typename maker::type base_class;
 179         //@endcond
 180     public:
 181         typedef GC  gc          ;   ///< Garbage collector
 182         typedef T   value_type  ;   ///< type of the value stored in the queue
 183         typedef Traits options  ;   ///< Queue's traits
 184
 185         typedef typename options::node_allocator node_allocator;   ///< Node allocator
 186         typedef typename base_class::memory_model  memory_model;   ///< Memory ordering. See cds::opt::memory_model option
 187         typedef typename base_class::item_counter  item_counter;   ///< Item counting policy, see cds::opt::item_counter option setter
 188         typedef typename base_class::stat          stat        ;   ///< Internal statistics policy
 189         typedef typename base_class::lock_type     lock_type   ;   ///< Type of mutex for maintaining an internal list of allocated segments.
 190         typedef typename base_class::permutation_generator permutation_generator; ///< Random permutation generator for sequence [0, quasi-factor)
 191
 192         static const size_t m_nHazardPtrCount = base_class::m_nHazardPtrCount ; ///< Count of hazard pointer required for the algorithm
 193
 194     protected:
 195         //@cond
 196         typedef typename maker::cxx_node_allocator  cxx_node_allocator;
 197         typedef std::unique_ptr< value_type, typename maker::node_disposer >  scoped_node_ptr;
 198
 199         static value_type * alloc_node( value_type const& v )
 200         {
 201             return cxx_node_allocator().New( v );
 202         }
 203
 204         static value_type * alloc_node()
 205         {
 206             return cxx_node_allocator().New();
 207         }
 208
 209 #   ifdef CDS_EMPLACE_SUPPORT
 210         template <typename... Args>
 211         static value_type * alloc_node_move( Args&&... args )
 212         {
 213             return cxx_node_allocator().MoveNew( std::forward<Args>( args )... );
 214         }
 215 #   endif
 216
 217         struct dummy_disposer {
 218             void operator()( value_type * p )
 219             {}
 220         };
 221         //@endcond
 222
 223     public:
 224         /// Initializes the empty queue
 225         SegmentedQueue(
 226             size_t nQuasiFactor     ///< Quasi factor. If it is not a power of 2 it is rounded up to nearest power of 2. Minimum is 2.
 227             )
 228             : base_class( nQuasiFactor )
 229         {}
 230
 231         /// Clears the queue and deletes all internal data
 232         ~SegmentedQueue()
 233         {}
 234
 235         /// Inserts a new element at last segment of the queue
 236         /**
 237             The function makes queue node in dynamic memory calling copy constructor for \p val
 238             and then it calls intrusive::SEgmentedQueue::enqueue.
 239             Returns \p true if success, \p false otherwise.
 240         */
 241         bool enqueue( value_type const& val )
 242         {
 243             scoped_node_ptr p( alloc_node(val) );
 244             if ( base_class::enqueue( *p ) ) {
 245                 p.release();
 246                 return true;
 247             }
 248             return false;
 249         }
 250
 251         /// Synonym for <tt>enqueue(value_type const&)</tt> function
 252         bool push( value_type const& val )
 253         {
 254             return enqueue( val );
 255         }
 256
 257         /// Inserts a new element at last segment of the queue using copy functor
 258         /**
 259             \p Func is a functor called to copy value \p data of type \p Q
 260             which may be differ from type \ref value_type stored in the queue.
 261             The functor's interface is:
 262             \code
 263             struct myFunctor {
 264                 void operator()(value_type& dest, Q const& data)
 265                 {
 266                     // // Code to copy \p data to \p dest
 267                     dest = data;
 268                 }
 269             };
 270             \endcode
 271             You may use \p boost:ref construction to pass functor \p f by reference.
 272         */
 273         template <typename Q, typename Func>
 274         bool enqueue( Q const& data, Func f  )
 275         {
 276             scoped_node_ptr p( alloc_node() );
 277             unref(f)( *p, data );
 278             if ( base_class::enqueue( *p )) {
 279                 p.release();
 280                 return true;
 281             }
 282             return false;
 283         }
 284
 285         /// Synonym for <tt>enqueue(Q const&, Func)</tt> function
 286         template <typename Q, typename Func>
 287         bool push( Q const& data, Func f )
 288         {
 289             return enqueue( data, f );
 290         }
 291
 292 #   ifdef CDS_EMPLACE_SUPPORT
 293         /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 294         /**
 295             This function is available only for compiler that supports
 296             variadic template and move semantics
 297         */
 298         template <typename... Args>
 299         bool emplace( Args&&... args )
 300         {
 301             scoped_node_ptr p( alloc_node_move( std::forward<Args>(args)... ) );
 302             if ( base_class::enqueue( *p )) {
 303                 p.release();
 304                 return true;
 305             }
 306             return false;
 307         }
 308 #   endif
 309
 310         /// Removes an element from first segment of the queue
 311         /**
 312             \p Func is a functor called to copy dequeued value to \p dest of type \p Q
 313             which may be differ from type \ref value_type stored in the queue.
 314             The functor's interface is:
 315             \code
 316             struct myFunctor {
 317                 void operator()(Q& dest, value_type const& data)
 318                 {
 319                     // Code to copy \p data to \p dest
 320                     dest = data;
 321                 }
 322             };
 323             \endcode
 324             You may use \p boost:ref construction to pass functor \p f by reference.
 325         */
 326         template <typename Q, typename Func>
 327         bool dequeue( Q& dest, Func f )
 328         {
 329             value_type * p = base_class::dequeue();
 330             if ( p ) {
 331                 unref(f)( dest, *p );
 332                 gc::template retire< typename maker::node_disposer >( p );
 333                 return true;
 334             }
 335             return false;
 336         }
 337
 338         /// Synonym for <tt>dequeue( Q&, Func )</tt> function
 339         template <typename Q, typename Func>
 340         bool pop( Q& dest, Func f )
 341         {
 342             return dequeue( dest, f );
 343         }
 344
 345         /// Dequeues a value from the queue
 346         /**
 347             If queue is not empty, the function returns \p true, \p dest contains copy of
 348             dequeued value. The assignment operator for type \ref value_type is invoked.
 349             If queue is empty, the function returns \p false, \p dest is unchanged.
 350         */
 351         bool dequeue( value_type& dest )
 352         {
 353             typedef cds::details::trivial_assign<value_type, value_type> functor;
 354             return dequeue( dest, functor() );
 355         }
 356
 357         /// Synonym for <tt>dequeue(value_type&)</tt> function
 358         bool pop( value_type& dest )
 359         {
 360             return dequeue( dest );
 361         }
 362
 363         /// Checks if the queue is empty
 364         /**
 365             The original segmented queue algorithm does not allow to check emptiness accurately
 366             because \p empty() is unlinearizable.
 367             This function tests queue's emptiness checking <tt>size() == 0</tt>,
 368             so, the item counting feature is an essential part of queue's algorithm.
 369         */
 370         bool empty() const
 371         {
 372             return base_class::empty();
 373         }
 374
 375         /// Clear the queue
 376         /**
 377             The function repeatedly calls \ref dequeue until it returns \p nullptr.
 378             The disposer specified in \p Traits template argument is called for each removed item.
 379         */
 380         void clear()
 381         {
 382             base_class::clear();
 383         }
 384
 385         /// Returns queue's item count
 386         size_t size() const
 387         {
 388             return base_class::size();
 389         }
 390
 391         /// Returns reference to internal statistics
 392         /**
 393             The type of internal statistics is specified by \p Traits template argument.
 394         */
 395         const stat& statistics() const
 396         {
 397             return base_class::statistics();
 398         }
 399
 400         /// Returns quasi factor, a power-of-two number
 401         size_t quasi_factor() const
 402         {
 403             return base_class::quasi_factor();
 404         }
 405     };
 406
 407 }} // namespace cds::container
 408
 409 #endif // #ifndef __CDS_CONTAINER_SEGMENTED_QUEUE_H