3 #ifndef __CDS_CONTAINER_SEGMENTED_QUEUE_H
4 #define __CDS_CONTAINER_SEGMENTED_QUEUE_H
7 #include <cds/intrusive/segmented_queue.h>
8 #include <cds/details/trivial_assign.h>
11 namespace cds { namespace container {
13 /// SegmentedQueue -related declarations
14 namespace segmented_queue {
16 # ifdef CDS_DOXYGEN_INVOKED
17 /// SegmentedQueue internal statistics
18 typedef cds::intrusive::segmented_queue::stat stat;
20 using cds::intrusive::segmented_queue::stat;
23 /// SegmentedQueue empty internal statistics (no overhead)
24 typedef cds::intrusive::segmented_queue::empty_stat empty_stat;
26 /// SegmentedQueue default type traits
29 /// Item allocator. Default is \ref CDS_DEFAULT_ALLOCATOR
30 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
32 /// Item counter, default is atomicity::item_counter
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.
38 typedef atomicity::item_counter item_counter;
40 /// Internal statistics, possible predefined types are \ref stat, \ref empty_stat (the default)
41 typedef segmented_queue::empty_stat stat;
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;
46 /// Alignment of critical data, default is cache line alignment. See cds::opt::alignment option specification
47 enum { alignment = opt::cache_line_alignment };
49 /// Segment allocator. Default is \ref CDS_DEFAULT_ALLOCATOR
50 typedef CDS_DEFAULT_ALLOCATOR allocator;
52 /// Lock type used to maintain an internal list of allocated segments
53 typedef cds::lock::Spin lock_type;
55 /// Random \ref cds::opt::permutation_generator "permutation generator" for sequence [0, quasi_factor)
56 typedef cds::opt::v::random2_permutation<int> permutation_generator;
59 /// Metafunction converting option list to traits for SegmentedQueue
61 The metafunction can be useful if a few fields in \ref type_traits should be changed.
64 typedef cds::container::segmented_queue::make_traits<
65 cds::opt::item_counter< cds::atomicity::item_counter >
66 >::type my_segmented_queue_traits;
68 This code creates \p %SegmentedQueue type traits with item counting feature,
69 all other \p type_traits members left unchanged.
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
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>
85 template <CDS_DECL_OPTIONS9>
87 # ifdef CDS_DOXYGEN_INVOKED
88 typedef implementation_defined type ; ///< Metafunction result
90 typedef typename cds::opt::make_options<
91 typename cds::opt::find_type_traits< type_traits, CDS_OPTIONS9 >::type
97 } // namespace segmented_queue
102 template <typename GC, typename T, typename Traits>
103 struct make_segmented_queue
106 typedef T value_type;
107 typedef Traits original_type_traits;
109 typedef cds::details::Allocator< T, typename original_type_traits::node_allocator > cxx_node_allocator;
110 struct node_disposer {
111 void operator()( T * p )
113 cxx_node_allocator().Delete( p );
117 struct intrusive_type_traits: public original_type_traits {
118 typedef node_disposer disposer;
121 typedef cds::intrusive::SegmentedQueue< gc, value_type, intrusive_type_traits > type;
124 } // namespace details
128 /** @ingroup cds_nonintrusive_queue
130 The queue is based on work
131 - [2010] Afek, Korland, Yanovsky "Quasi-Linearizability: relaxed consistency for improved concurrency"
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.
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.
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.
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.
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.
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
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 >
173 public details::make_segmented_queue< GC, T, Traits >::type
177 typedef details::make_segmented_queue< GC, T, Traits > maker;
178 typedef typename maker::type base_class;
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
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)
192 static const size_t m_nHazardPtrCount = base_class::m_nHazardPtrCount ; ///< Count of hazard pointer required for the algorithm
196 typedef typename maker::cxx_node_allocator cxx_node_allocator;
197 typedef std::unique_ptr< value_type, typename maker::node_disposer > scoped_node_ptr;
199 static value_type * alloc_node( value_type const& v )
201 return cxx_node_allocator().New( v );
204 static value_type * alloc_node()
206 return cxx_node_allocator().New();
209 # ifdef CDS_EMPLACE_SUPPORT
210 template <typename... Args>
211 static value_type * alloc_node_move( Args&&... args )
213 return cxx_node_allocator().MoveNew( std::forward<Args>( args )... );
217 struct dummy_disposer {
218 void operator()( value_type * p )
224 /// Initializes the empty queue
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.
228 : base_class( nQuasiFactor )
231 /// Clears the queue and deletes all internal data
235 /// Inserts a new element at last segment of the queue
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.
241 bool enqueue( value_type const& val )
243 scoped_node_ptr p( alloc_node(val) );
244 if ( base_class::enqueue( *p ) ) {
251 /// Synonym for <tt>enqueue(value_type const&)</tt> function
252 bool push( value_type const& val )
254 return enqueue( val );
257 /// Inserts a new element at last segment of the queue using copy functor
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:
264 void operator()(value_type& dest, Q const& data)
266 // // Code to copy \p data to \p dest
271 You may use \p boost:ref construction to pass functor \p f by reference.
273 template <typename Q, typename Func>
274 bool enqueue( Q const& data, Func f )
276 scoped_node_ptr p( alloc_node() );
277 unref(f)( *p, data );
278 if ( base_class::enqueue( *p )) {
285 /// Synonym for <tt>enqueue(Q const&, Func)</tt> function
286 template <typename Q, typename Func>
287 bool push( Q const& data, Func f )
289 return enqueue( data, f );
292 # ifdef CDS_EMPLACE_SUPPORT
293 /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
295 This function is available only for compiler that supports
296 variadic template and move semantics
298 template <typename... Args>
299 bool emplace( Args&&... args )
301 scoped_node_ptr p( alloc_node_move( std::forward<Args>(args)... ) );
302 if ( base_class::enqueue( *p )) {
310 /// Removes an element from first segment of the queue
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:
317 void operator()(Q& dest, value_type const& data)
319 // Code to copy \p data to \p dest
324 You may use \p boost:ref construction to pass functor \p f by reference.
326 template <typename Q, typename Func>
327 bool dequeue( Q& dest, Func f )
329 value_type * p = base_class::dequeue();
331 unref(f)( dest, *p );
332 gc::template retire< typename maker::node_disposer >( p );
338 /// Synonym for <tt>dequeue( Q&, Func )</tt> function
339 template <typename Q, typename Func>
340 bool pop( Q& dest, Func f )
342 return dequeue( dest, f );
345 /// Dequeues a value from the queue
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.
351 bool dequeue( value_type& dest )
353 typedef cds::details::trivial_assign<value_type, value_type> functor;
354 return dequeue( dest, functor() );
357 /// Synonym for <tt>dequeue(value_type&)</tt> function
358 bool pop( value_type& dest )
360 return dequeue( dest );
363 /// Checks if the queue is empty
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.
372 return base_class::empty();
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.
385 /// Returns queue's item count
388 return base_class::size();
391 /// Returns reference to internal statistics
393 The type of internal statistics is specified by \p Traits template argument.
395 const stat& statistics() const
397 return base_class::statistics();
400 /// Returns quasi factor, a power-of-two number
401 size_t quasi_factor() const
403 return base_class::quasi_factor();
407 }} // namespace cds::container
409 #endif // #ifndef __CDS_CONTAINER_SEGMENTED_QUEUE_H