3 #ifndef __CDS_CONTAINER_RWQUEUE_H
4 #define __CDS_CONTAINER_RWQUEUE_H
7 #include <cds/opt/options.h>
8 #include <cds/lock/spinlock.h>
9 #include <cds/intrusive/queue_stat.h>
10 #include <cds/details/allocator.h>
11 #include <cds/details/trivial_assign.h>
14 namespace cds { namespace container {
16 /// Michael & Scott blocking queue with fine-grained synchronization schema
17 /** @ingroup cds_nonintrusive_queue
18 The queue has two different locks: one for reading and one for writing.
19 Therefore, one writer and one reader can simultaneously access to the queue.
20 The queue does not require any garbage collector.
23 - [1998] Maged Michael, Michael Scott "Simple, fast, and practical non-blocking
24 and blocking concurrent queue algorithms"
26 <b>Template arguments</b>
27 - \p T - type to be stored in the queue
28 - \p Options - options
31 - opt::allocator - allocator (like \p std::allocator). Default is \ref CDS_DEFAULT_ALLOCATOR
32 - opt::lock_type - type of lock primitive. Default is cds::lock::Spin.
33 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter
34 - opt::stat - the type to gather internal statistics.
35 Possible option value are: queue_stat, queue_dummy_stat, user-provided class that supports queue_stat interface.
36 Default is \ref intrusive::queue_dummy_stat.
37 <tt>RWQueue</tt> uses only \p onEnqueue and \p onDequeue counter.
38 - opt::alignment - the alignment for \p lock_type to prevent false sharing. Default is opt::cache_line_alignment
40 This queue has no intrusive counterpart.
42 template <typename T, typename... Options>
46 struct default_options
48 typedef lock::Spin lock_type;
49 typedef CDS_DEFAULT_ALLOCATOR allocator;
50 typedef atomicity::empty_item_counter item_counter;
51 typedef intrusive::queue_dummy_stat stat;
52 enum { alignment = opt::cache_line_alignment };
58 typedef typename opt::make_options<
59 typename cds::opt::find_type_traits< default_options, Options... >::type
65 /// Rebind template arguments
66 template <typename T2, typename... Options2>
68 typedef RWQueue< T2, Options2...> other ; ///< Rebinding result
72 typedef T value_type ; ///< type of value stored in the queue
74 typedef typename options::lock_type lock_type ; ///< Locking primitive used
81 node_type * volatile m_pNext ; ///< Pointer to the next node in queue
82 value_type m_value ; ///< Value stored in the node
84 node_type( value_type const& v )
93 template <typename... Args>
94 node_type( Args&&... args )
96 , m_value( std::forward<Args>(args)...)
102 typedef typename options::allocator::template rebind<node_type>::other allocator_type ; ///< Allocator type used for allocate/deallocate the queue nodes
103 typedef typename options::item_counter item_counter ; ///< Item counting policy used
104 typedef typename options::stat stat ; ///< Internal statistics policy used
108 typedef typename opt::details::alignment_setter< lock_type, options::alignment >::type aligned_lock_type;
109 typedef cds::lock::scoped_lock<lock_type> auto_lock;
110 typedef cds::details::Allocator< node_type, allocator_type > node_allocator;
112 item_counter m_ItemCounter;
115 mutable aligned_lock_type m_HeadLock;
117 mutable aligned_lock_type m_TailLock;
123 static node_type * alloc_node()
125 return node_allocator().New();
128 static node_type * alloc_node( T const& data )
130 return node_allocator().New( data );
133 template <typename... Args>
134 static node_type * alloc_node_move( Args&&... args )
136 return node_allocator().MoveNew( std::forward<Args>( args )... );
139 static void free_node( node_type * pNode )
141 node_allocator().Delete( pNode );
144 bool enqueue_node( node_type * p )
146 assert( p != nullptr );
148 auto_lock lock( m_TailLock );
150 m_pTail->m_pNext = p;
157 struct node_disposer {
158 void operator()( node_type * pNode )
163 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
167 /// Makes empty queue
170 node_type * pNode = alloc_node();
175 /// Destructor clears queue
179 assert( m_pHead == m_pTail );
180 free_node( m_pHead );
183 /// Enqueues \p data. Always return \a true
184 bool enqueue( value_type const& data )
186 scoped_node_ptr p( alloc_node( data ));
187 if ( enqueue_node( p.get() )) {
194 /// Enqueues \p data to queue using copy functor
196 \p Func is a functor called to copy value \p data of type \p Type
197 which may be differ from type \p T stored in the queue.
198 The functor's interface is:
201 void operator()(T& dest, Type const& data)
203 // // Code to copy \p data to \p dest
208 You may use \p boost:ref construction to pass functor \p f by reference.
210 <b>Requirements</b> The functor \p Func should not throw any exception.
212 template <typename Type, typename Func>
213 bool enqueue( Type const& data, Func f )
215 scoped_node_ptr p( alloc_node());
216 unref(f)( p->m_value, data );
217 if ( enqueue_node( p.get() )) {
224 /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
225 template <typename... Args>
226 bool emplace( Args&&... args )
228 scoped_node_ptr p( alloc_node_move( std::forward<Args>(args)... ));
229 if ( enqueue_node( p.get() )) {
236 /// Dequeues a value using copy functor
238 \p Func is a functor called to copy dequeued value to \p dest of type \p Type
239 which may be differ from type \p T stored in the queue.
240 The functor's interface is:
243 void operator()(Type& dest, T const& data)
245 // // Copy \p data to \p dest
250 You may use \p boost:ref construction to pass functor \p f by reference.
252 <b>Requirements</b> The functor \p Func should not throw any exception.
254 template <typename Type, typename Func>
255 bool dequeue( Type& dest, Func f )
259 auto_lock lock( m_HeadLock );
261 node_type * pNewHead = pNode->m_pNext;
262 if ( pNewHead == nullptr )
264 unref(f)( dest, pNewHead->m_value );
273 /** Dequeues a value to \p dest.
275 If queue is empty returns \a false, \p dest may be corrupted.
276 If queue is not empty returns \a true, \p dest contains the value dequeued
278 bool dequeue( value_type& dest )
280 typedef cds::details::trivial_assign<value_type, value_type> functor;
281 return dequeue( dest, functor() );
284 /// Synonym for \ref enqueue
285 bool push( value_type const& data )
287 return enqueue( data );
290 /// Synonym for template version of \ref enqueue function
291 template <typename Type, typename Func>
292 bool push( Type const& data, Func f )
294 return enqueue( data, f );
297 /// Synonym for \ref dequeue
298 bool pop( value_type& data )
300 return dequeue( data );
303 /// Synonym for template version of \ref dequeue function
304 template <typename Type, typename Func>
305 bool pop( Type& dest, Func f )
307 return dequeue( dest, f );
310 /// Checks if queue is empty
313 auto_lock lock( m_HeadLock );
314 return m_pHead->m_pNext == nullptr;
320 auto_lock lockR( m_HeadLock );
321 auto_lock lockW( m_TailLock );
322 while ( m_pHead->m_pNext != nullptr ) {
323 node_type * pHead = m_pHead;
324 m_pHead = m_pHead->m_pNext;
329 /// Returns queue's item count
331 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
332 this function always returns 0.
334 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the queue
335 is empty. To check queue emptyness use \ref empty() method.
339 return m_ItemCounter.value();
342 /// Returns reference to internal statistics
343 stat const& statistics() const
350 }} // namespace cds::container
352 #endif // #ifndef __CDS_CONTAINER_RWQUEUE_H