2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_CONTAINER_SEGMENTED_QUEUE_H
32 #define CDSLIB_CONTAINER_SEGMENTED_QUEUE_H
35 #include <functional> // ref
36 #include <cds/intrusive/segmented_queue.h>
37 #include <cds/details/trivial_assign.h>
39 namespace cds { namespace container {
41 /// SegmentedQueue -related declarations
42 namespace segmented_queue {
44 # ifdef CDS_DOXYGEN_INVOKED
45 /// SegmentedQueue internal statistics
46 typedef cds::intrusive::segmented_queue::stat stat;
48 using cds::intrusive::segmented_queue::stat;
51 /// SegmentedQueue empty internal statistics (no overhead)
52 typedef cds::intrusive::segmented_queue::empty_stat empty_stat;
54 /// SegmentedQueue default type traits
57 /// Item allocator. Default is \ref CDS_DEFAULT_ALLOCATOR
58 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
60 /// Item counter, default is atomicity::item_counter
62 The item counting is an essential part of segmented queue algorithm.
63 The \p empty() member function is based on checking <tt>size() == 0</tt>.
64 Therefore, dummy item counter like atomicity::empty_item_counter is not the proper counter.
66 typedef atomicity::item_counter item_counter;
68 /// Internal statistics, possible predefined types are \ref stat, \ref empty_stat (the default)
69 typedef segmented_queue::empty_stat stat;
71 /// Memory model, default is opt::v::relaxed_ordering. See cds::opt::memory_model for the full list of possible types
72 typedef opt::v::relaxed_ordering memory_model;
74 /// Alignment of critical data, default is cache line alignment. See cds::opt::alignment option specification
75 enum { alignment = opt::cache_line_alignment };
77 /// Padding of segment data, default is no special padding
79 The segment is just an array of atomic data pointers,
80 so, the high load leads to false sharing and performance degradation.
81 A padding of segment data can eliminate false sharing issue.
82 On the other hand, the padding leads to increase segment size.
84 enum { padding = cds::intrusive::segmented_queue::traits::padding };
86 /// Segment allocator. Default is \ref CDS_DEFAULT_ALLOCATOR
87 typedef CDS_DEFAULT_ALLOCATOR allocator;
89 /// Lock type used to maintain an internal list of allocated segments
90 typedef cds::sync::spin lock_type;
92 /// Random \ref cds::opt::permutation_generator "permutation generator" for sequence [0, quasi_factor)
93 typedef cds::opt::v::random2_permutation<int> permutation_generator;
96 /// Metafunction converting option list to traits for SegmentedQueue
98 The metafunction can be useful if a few fields in \p segmented_queue::traits should be changed.
101 typedef cds::container::segmented_queue::make_traits<
102 cds::opt::item_counter< cds::atomicity::item_counter >
103 >::type my_segmented_queue_traits;
105 This code creates \p %SegmentedQueue type traits with item counting feature,
106 all other \p segmented_queue::traits members left unchanged.
109 - \p opt::node_allocator - node allocator.
110 - \p opt::stat - internal statistics, possible type: \p segmented_queue::stat, \p segmented_queue::empty_stat (the default)
111 - \p opt::item_counter - item counting feature. Note that \p atomicity::empty_item_counetr is not suitable
113 - \p opt::memory_model - memory model, default is \p opt::v::relaxed_ordering.
114 See option description for the full list of possible models
115 - \p opt::alignment - the alignment of critical data, see option description for explanation
116 - \p opt::padding - the padding of segment data, default no special padding.
117 See \p traits::padding for explanation.
118 - \p opt::allocator - the allocator used to maintain segments.
119 - \p opt::lock_type - a mutual exclusion lock type used to maintain internal list of allocated
120 segments. Default is \p cds::opt::Spin, \p std::mutex is also suitable.
121 - \p opt::permutation_generator - a random permutation generator for sequence [0, quasi_factor),
122 default is \p cds::opt::v::random2_permutation<int>
124 template <typename... Options>
126 # ifdef CDS_DOXYGEN_INVOKED
127 typedef implementation_defined type ; ///< Metafunction result
129 typedef typename cds::opt::make_options<
130 typename cds::opt::find_type_traits< traits, Options... >::type
136 } // namespace segmented_queue
141 template <typename GC, typename T, typename Traits>
142 struct make_segmented_queue
145 typedef T value_type;
146 typedef Traits original_type_traits;
148 typedef cds::details::Allocator< T, typename original_type_traits::node_allocator > cxx_node_allocator;
149 struct node_disposer {
150 void operator()( T * p )
152 cxx_node_allocator().Delete( p );
156 struct intrusive_type_traits: public original_type_traits
158 typedef node_disposer disposer;
161 typedef cds::intrusive::SegmentedQueue< gc, value_type, intrusive_type_traits > type;
164 } // namespace details
168 /** @ingroup cds_nonintrusive_queue
170 The queue is based on work
171 - [2010] Afek, Korland, Yanovsky "Quasi-Linearizability: relaxed consistency for improved concurrency"
173 In this paper the authors offer a relaxed version of linearizability, so-called quasi-linearizability,
174 that preserves some of the intuition, provides a flexible way to control the level of relaxation
175 and supports th implementation of more concurrent and scalable data structure.
176 Intuitively, the linearizability requires each run to be equivalent in some sense to a serial run
177 of the algorithm. This equivalence to some serial run imposes strong synchronization requirements
178 that in many cases results in limited scalability and synchronization bottleneck.
180 The general idea is that the queue maintains a linked list of segments, each segment is an array of
181 nodes in the size of the quasi factor, and each node has a deleted boolean marker, which states
182 if it has been dequeued. Each producer iterates over last segment in the linked list in some random
183 permutation order. Whet it finds an empty cell it performs a CAS operation attempting to enqueue its
184 new element. In case the entire segment has been scanned and no available cell is found (implying
185 that the segment is full), then it attempts to add a new segment to the list.
187 The dequeue operation is similar: the consumer iterates over the first segment in the linked list
188 in some random permutation order. When it finds an item which has not yet been dequeued, it performs
189 CAS on its deleted marker in order to "delete" it, if succeeded this item is considered dequeued.
190 In case the entire segment was scanned and all the nodes have already been dequeued (implying that
191 the segment is empty), then it attempts to remove this segment from the linked list and starts
192 the same process on the next segment. If there is no next segment, the queue is considered empty.
194 Based on the fact that most of the time threads do not add or remove segments, most of the work
195 is done in parallel on different cells in the segments. This ensures a controlled contention
196 depending on the segment size, which is quasi factor.
198 The segmented queue is an <i>unfair</i> queue since it violates the strong FIFO order but no more than
199 quasi factor. It means that the consumer dequeues any item from the current first segment.
202 - \p GC - a garbage collector, possible types are cds::gc::HP, cds::gc::DHP
203 - \p T - the type of values stored in the queue
204 - \p Traits - queue type traits, default is \p segmented_queue::traits.
205 \p segmented_queue::make_traits metafunction can be used to construct your
208 template <class GC, typename T, typename Traits = segmented_queue::traits >
209 class SegmentedQueue:
210 #ifdef CDS_DOXYGEN_INVOKED
211 public cds::intrusive::SegmentedQueue< GC, T, Traits >
213 public details::make_segmented_queue< GC, T, Traits >::type
217 typedef details::make_segmented_queue< GC, T, Traits > maker;
218 typedef typename maker::type base_class;
221 typedef GC gc; ///< Garbage collector
222 typedef T value_type; ///< type of the value stored in the queue
223 typedef Traits traits; ///< Queue traits
225 typedef typename traits::node_allocator node_allocator; ///< Node allocator
226 typedef typename base_class::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
227 typedef typename base_class::item_counter item_counter; ///< Item counting policy, see cds::opt::item_counter option setter
228 typedef typename base_class::stat stat ; ///< Internal statistics policy
229 typedef typename base_class::lock_type lock_type ; ///< Type of mutex for maintaining an internal list of allocated segments.
230 typedef typename base_class::permutation_generator permutation_generator; ///< Random permutation generator for sequence [0, quasi-factor)
232 static const size_t c_nHazardPtrCount = base_class::c_nHazardPtrCount ; ///< Count of hazard pointer required for the algorithm
236 typedef typename maker::cxx_node_allocator cxx_node_allocator;
237 typedef std::unique_ptr< value_type, typename maker::node_disposer > scoped_node_ptr;
239 static value_type * alloc_node( value_type const& v )
241 return cxx_node_allocator().New( v );
244 static value_type * alloc_node()
246 return cxx_node_allocator().New();
249 template <typename... Args>
250 static value_type * alloc_node_move( Args&&... args )
252 return cxx_node_allocator().MoveNew( std::forward<Args>( args )... );
257 /// Initializes the empty queue
259 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.
261 : base_class( nQuasiFactor )
264 /// Clears the queue and deletes all internal data
268 /// Inserts a new element at last segment of the queue
270 The function makes queue node in dynamic memory calling copy constructor for \p val
271 and then it calls intrusive::SEgmentedQueue::enqueue.
272 Returns \p true if success, \p false otherwise.
274 bool enqueue( value_type const& val )
276 scoped_node_ptr p( alloc_node(val));
277 if ( base_class::enqueue( *p )) {
284 /// Inserts a new element at last segment of the queue, move semantics
285 bool enqueue( value_type&& val )
287 scoped_node_ptr p( alloc_node_move( std::move( val )));
288 if ( base_class::enqueue( *p )) {
295 /// Enqueues data to the queue using a functor
297 \p Func is a functor called to create node.
298 The functor \p f takes one argument - a reference to a new node of type \ref value_type :
300 cds::container::SegmentedQueue< cds::gc::HP, Foo > myQueue;
302 myQueue.enqueue_with( [&bar]( Foo& dest ) { dest = bar; } );
305 template <typename Func>
306 bool enqueue_with( Func f )
308 scoped_node_ptr p( alloc_node());
310 if ( base_class::enqueue( *p )) {
318 /// Synonym for \p enqueue( value_type const& ) member function
319 bool push( value_type const& val )
321 return enqueue( val );
324 /// Synonym for \p enqueue( value_type&& ) member function
325 bool push( value_type&& val )
327 return enqueue( std::move( val ));
330 /// Synonym for \p enqueue_with() member function
331 template <typename Func>
332 bool push_with( Func f )
334 return enqueue_with( f );
337 /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
338 template <typename... Args>
339 bool emplace( Args&&... args )
341 scoped_node_ptr p( alloc_node_move( std::forward<Args>(args)... ));
342 if ( base_class::enqueue( *p )) {
349 /// Dequeues a value from the queue
351 If queue is not empty, the function returns \p true, \p dest contains copy of
352 dequeued value. The assignment operator for type \ref value_type is invoked.
353 If queue is empty, the function returns \p false, \p dest is unchanged.
355 bool dequeue( value_type& dest )
357 return dequeue_with( [&dest]( value_type& src ) { dest = std::move( src );});
360 /// Dequeues a value using a functor
362 \p Func is a functor called to copy dequeued value.
363 The functor takes one argument - a reference to removed node:
365 cds:container::MSQueue< cds::gc::HP, Foo > myQueue;
367 myQueue.dequeue_with( [&bar]( Foo& src ) { bar = std::move( src );});
369 The functor is called only if the queue is not empty.
371 template <typename Func>
372 bool dequeue_with( Func f )
374 value_type * p = base_class::dequeue();
377 gc::template retire< typename maker::node_disposer >( p );
383 /// Synonym for \p dequeue_with() function
384 template <typename Func>
385 bool pop_with( Func f )
387 return dequeue_with( f );
390 /// Synonym for \p dequeue() function
391 bool pop( value_type& dest )
393 return dequeue( dest );
396 /// Checks if the queue is empty
398 The original segmented queue algorithm does not allow to check emptiness accurately
399 because \p empty() is unlinearizable.
400 This function tests queue's emptiness checking <tt>size() == 0</tt>,
401 so, the item counting feature is an essential part of queue's algorithm.
405 return base_class::empty();
410 The function repeatedly calls \p dequeue() until it returns \p nullptr.
411 The disposer specified in \p Traits template argument is called for each removed item.
418 /// Returns queue's item count
421 return base_class::size();
424 /// Returns reference to internal statistics
426 The type of internal statistics is specified by \p Traits template argument.
428 const stat& statistics() const
430 return base_class::statistics();
433 /// Returns quasi factor, a power-of-two number
434 size_t quasi_factor() const
436 return base_class::quasi_factor();
440 }} // namespace cds::container
442 #endif // #ifndef CDSLIB_CONTAINER_SEGMENTED_QUEUE_H