3 #ifndef __CDS_CONTAINER_MOIR_QUEUE_H
4 #define __CDS_CONTAINER_MOIR_QUEUE_H
7 #include <cds/intrusive/moir_queue.h>
8 #include <cds/intrusive/details/queue_stat.h>
9 #include <cds/container/details/base.h>
11 #include <cds/details/trivial_assign.h>
13 namespace cds { namespace container {
17 template <typename GC, typename T, typename... Options>
18 struct make_moir_queue
23 struct default_options {
24 typedef cds::backoff::empty back_off;
25 typedef CDS_DEFAULT_ALLOCATOR allocator;
26 typedef atomicity::empty_item_counter item_counter;
27 typedef intrusive::queue_dummy_stat stat;
28 typedef opt::v::relaxed_ordering memory_model;
29 enum { alignment = opt::cache_line_alignment };
32 typedef typename opt::make_options<
33 typename cds::opt::find_type_traits< default_options, Options... >::type
37 struct node_type: public intrusive::single_link::node< gc >
41 node_type( const value_type& val )
45 template <typename... Args>
46 node_type( Args&&... args )
47 : m_value( std::forward<Args>(args)...)
51 typedef typename options::allocator::template rebind<node_type>::other allocator_type;
52 typedef cds::details::Allocator< node_type, allocator_type > cxx_allocator;
54 struct node_deallocator
56 void operator ()( node_type * pNode )
58 cxx_allocator().Delete( pNode );
62 typedef intrusive::MoirQueue<
65 ,intrusive::opt::hook<
66 intrusive::single_link::base_hook< opt::gc<gc> >
68 ,opt::back_off< typename options::back_off >
69 ,intrusive::opt::disposer< node_deallocator >
70 ,opt::item_counter< typename options::item_counter >
71 ,opt::stat< typename options::stat >
72 ,opt::alignment< options::alignment >
73 ,opt::memory_model< typename options::memory_model >
79 /// A variation of Michael & Scott's lock-free queue
80 /** @ingroup cds_nonintrusive_queue
81 It is non-intrusive version of intrusive::MoirQueue.
83 \p T is a type stored in the queue. It should be default-constructible, copy-constructible, assignable type.
85 \p Options description see MSQueue
87 template <typename GC, typename T, typename... Options>
89 #ifdef CDS_DOXYGEN_INVOKED
90 intrusive::MoirQueue< GC, intrusive::single_link::node< T >, Options... >
92 details::make_moir_queue< GC, T, Options... >::type
96 typedef details::make_moir_queue< GC, T, Options... > options;
97 typedef typename options::type base_class;
101 /// Rebind template arguments
102 template <typename GC2, typename T2, typename... Options2>
104 typedef MoirQueue< GC2, T2, Options2...> other ; ///< Rebinding result
108 typedef T value_type ; ///< Value type stored in the stack
110 typedef typename base_class::gc gc ; ///< Garbage collector used
111 typedef typename base_class::back_off back_off ; ///< Back-off strategy used
112 typedef typename options::allocator_type allocator_type ; ///< Allocator type used for allocate/deallocate the nodes
113 typedef typename options::options::item_counter item_counter ; ///< Item counting policy used
114 typedef typename options::options::stat stat ; ///< Internal statistics policy used
115 typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
118 typedef typename options::node_type node_type ; ///< queue node type (derived from intrusive::single_link::node)
121 typedef typename options::cxx_allocator cxx_allocator;
122 typedef typename options::node_deallocator node_deallocator; // deallocate node
123 typedef typename base_class::node_traits node_traits;
128 static node_type * alloc_node()
130 return cxx_allocator().New();
132 static node_type * alloc_node( const value_type& val )
134 return cxx_allocator().New( val );
136 template <typename... Args>
137 static node_type * alloc_node_move( Args&&... args )
139 return cxx_allocator().MoveNew( std::forward<Args>( args )... );
141 static void free_node( node_type * p )
143 node_deallocator()( p );
146 struct node_disposer {
147 void operator()( node_type * pNode )
152 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
156 /// Initializes empty queue
160 /// Destructor clears the queue
164 /// Returns queue's item count (see \ref intrusive::MSQueue::size for explanation)
167 return base_class::size();
170 /// Returns refernce to internal statistics
171 const stat& statistics() const
173 return base_class::statistics();
176 /// Enqueues \p val value into the queue.
178 The function makes queue node in dynamic memory calling copy constructor for \p val
179 and then it calls intrusive::MSQueue::enqueue.
180 Returns \p true if success, \p false otherwise.
182 bool enqueue( value_type const& val )
184 scoped_node_ptr p( alloc_node(val) );
185 if ( base_class::enqueue( *p )) {
192 /// Enqueues \p data to queue using copy functor
194 \p Func is a functor called to copy value \p data of type \p Type
195 which may be differ from type \p T stored in the queue.
196 The functor's interface is:
199 void operator()(T& dest, SOURCE const& data)
201 // // Code to copy \p data to \p dest
206 You may use \p boost:ref construction to pass functor \p f by reference.
208 <b>Requirements</b> The functor \p Func should not throw any exception.
210 template <typename Type, typename Func>
211 bool enqueue( const Type& data, Func f )
213 scoped_node_ptr p( alloc_node());
214 unref(f)( node_traits::to_value_ptr( *p )->m_value, data );
215 if ( base_class::enqueue( *p )) {
222 /// Dequeues a value using copy functor
224 \p Func is a functor called to copy dequeued value to \p dest of type \p Type
225 which may be differ from type \p T stored in the queue.
226 The functor's interface is:
229 void operator()(Type& dest, T const& data)
231 // // Code to copy \p data to \p dest
236 You may use \p boost:ref construction to pass functor \p f by reference.
238 <b>Requirements</b> The functor \p Func should not throw any exception.
240 template <typename Type, typename Func>
241 bool dequeue( Type& dest, Func f )
243 typename base_class::dequeue_result res;
244 if ( base_class::do_dequeue( res )) {
245 unref(f)( dest, node_traits::to_value_ptr( *res.pNext )->m_value );
247 base_class::dispose_result( res );
254 /// Dequeues a value from the queue
256 If queue is not empty, the function returns \p true, \p dest contains copy of
257 dequeued value. The assignment operator for type \ref value_type is invoked.
258 If queue is empty, the function returns \p false, \p dest is unchanged.
260 bool dequeue( value_type& dest )
262 typedef cds::details::trivial_assign<value_type, value_type> functor;
263 return dequeue( dest, functor() );
266 /// Synonym for \ref enqueue function
267 bool push( const value_type& val )
269 return enqueue( val );
272 /// Synonym for template version of \ref enqueue function
273 template <typename Type, typename Func>
274 bool push( const Type& data, Func f )
276 return enqueue( data, f );
279 /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
280 template <typename... Args>
281 bool emplace( Args&&... args )
283 scoped_node_ptr p( alloc_node_move( std::forward<Args>(args)... ));
284 if ( base_class::enqueue( *p )) {
291 /// Synonym for \ref dequeue function
292 bool pop( value_type& dest )
294 return dequeue( dest );
297 /// Synonym for template version of \ref dequeue function
298 template <typename Type, typename Func>
299 bool pop( Type& dest, Func f )
301 return dequeue( dest, f );
304 /// Checks if the queue is empty
307 return base_class::empty();
312 The function repeatedly calls \ref dequeue until it returns nullptr.
313 The disposer defined in template \p Options is called for each item
314 that can be safely disposed.
322 }} // namespace cds::container
324 #endif // #ifndef __CDS_CONTAINER_MOIR_QUEUE_H