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/queue_stat.h>
9 #include <cds/container/base.h>
11 #include <cds/details/trivial_assign.h>
13 namespace cds { namespace container {
17 template <typename GC, typename T, CDS_DECL_OPTIONS7>
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, CDS_OPTIONS7 >::type
37 struct node_type: public intrusive::single_link::node< gc >
41 node_type( const value_type& val )
44 # ifdef CDS_EMPLACE_SUPPORT
45 template <typename... Args>
46 node_type( Args&&... args )
47 : m_value( std::forward<Args>(args)...)
55 typedef typename options::allocator::template rebind<node_type>::other allocator_type;
56 typedef cds::details::Allocator< node_type, allocator_type > cxx_allocator;
58 struct node_deallocator
60 void operator ()( node_type * pNode )
62 cxx_allocator().Delete( pNode );
66 typedef intrusive::MoirQueue<
69 ,intrusive::opt::hook<
70 intrusive::single_link::base_hook< opt::gc<gc> >
72 ,opt::back_off< typename options::back_off >
73 ,intrusive::opt::disposer< node_deallocator >
74 ,opt::item_counter< typename options::item_counter >
75 ,opt::stat< typename options::stat >
76 ,opt::alignment< options::alignment >
77 ,opt::memory_model< typename options::memory_model >
83 /// A variation of Michael & Scott's lock-free queue
84 /** @ingroup cds_nonintrusive_queue
85 It is non-intrusive version of intrusive::MoirQueue.
87 \p T is a type stored in the queue. It should be default-constructible, copy-constructible, assignable type.
89 \p Options description see MSQueue
91 template <typename GC, typename T, CDS_DECL_OPTIONS7>
93 #ifdef CDS_DOXYGEN_INVOKED
94 intrusive::MoirQueue< GC, intrusive::single_link::node< T >, Options... >
96 details::make_moir_queue< GC, T, CDS_OPTIONS7 >::type
100 typedef details::make_moir_queue< GC, T, CDS_OPTIONS7 > options;
101 typedef typename options::type base_class;
105 /// Rebind template arguments
106 template <typename GC2, typename T2, CDS_DECL_OTHER_OPTIONS7>
108 typedef MoirQueue< GC2, T2, CDS_OTHER_OPTIONS7> other ; ///< Rebinding result
112 typedef T value_type ; ///< Value type stored in the stack
114 typedef typename base_class::gc gc ; ///< Garbage collector used
115 typedef typename base_class::back_off back_off ; ///< Back-off strategy used
116 typedef typename options::allocator_type allocator_type ; ///< Allocator type used for allocate/deallocate the nodes
117 typedef typename options::options::item_counter item_counter ; ///< Item counting policy used
118 typedef typename options::options::stat stat ; ///< Internal statistics policy used
119 typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
122 typedef typename options::node_type node_type ; ///< queue node type (derived from intrusive::single_link::node)
125 typedef typename options::cxx_allocator cxx_allocator;
126 typedef typename options::node_deallocator node_deallocator; // deallocate node
127 typedef typename base_class::node_traits node_traits;
132 static node_type * alloc_node()
134 return cxx_allocator().New();
136 static node_type * alloc_node( const value_type& val )
138 return cxx_allocator().New( val );
140 # ifdef CDS_EMPLACE_SUPPORT
141 template <typename... Args>
142 static node_type * alloc_node_move( Args&&... args )
144 return cxx_allocator().MoveNew( std::forward<Args>( args )... );
147 static void free_node( node_type * p )
149 node_deallocator()( p );
152 struct node_disposer {
153 void operator()( node_type * pNode )
158 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
162 /// Initializes empty queue
166 /// Destructor clears the queue
170 /// Returns queue's item count (see \ref intrusive::MSQueue::size for explanation)
173 return base_class::size();
176 /// Returns refernce to internal statistics
177 const stat& statistics() const
179 return base_class::statistics();
182 /// Enqueues \p val value into the queue.
184 The function makes queue node in dynamic memory calling copy constructor for \p val
185 and then it calls intrusive::MSQueue::enqueue.
186 Returns \p true if success, \p false otherwise.
188 bool enqueue( value_type const& val )
190 scoped_node_ptr p( alloc_node(val) );
191 if ( base_class::enqueue( *p )) {
198 /// Enqueues \p data to queue using copy functor
200 \p Func is a functor called to copy value \p data of type \p Type
201 which may be differ from type \p T stored in the queue.
202 The functor's interface is:
205 void operator()(T& dest, SOURCE const& data)
207 // // Code to copy \p data to \p dest
212 You may use \p boost:ref construction to pass functor \p f by reference.
214 <b>Requirements</b> The functor \p Func should not throw any exception.
216 template <typename Type, typename Func>
217 bool enqueue( const Type& data, Func f )
219 scoped_node_ptr p( alloc_node());
220 unref(f)( node_traits::to_value_ptr( *p )->m_value, data );
221 if ( base_class::enqueue( *p )) {
228 /// Dequeues a value using copy functor
230 \p Func is a functor called to copy dequeued value to \p dest of type \p Type
231 which may be differ from type \p T stored in the queue.
232 The functor's interface is:
235 void operator()(Type& dest, T const& data)
237 // // Code to copy \p data to \p dest
242 You may use \p boost:ref construction to pass functor \p f by reference.
244 <b>Requirements</b> The functor \p Func should not throw any exception.
246 template <typename Type, typename Func>
247 bool dequeue( Type& dest, Func f )
249 typename base_class::dequeue_result res;
250 if ( base_class::do_dequeue( res )) {
251 unref(f)( dest, node_traits::to_value_ptr( *res.pNext )->m_value );
253 base_class::dispose_result( res );
260 /// Dequeues a value from the queue
262 If queue is not empty, the function returns \p true, \p dest contains copy of
263 dequeued value. The assignment operator for type \ref value_type is invoked.
264 If queue is empty, the function returns \p false, \p dest is unchanged.
266 bool dequeue( value_type& dest )
268 typedef cds::details::trivial_assign<value_type, value_type> functor;
269 return dequeue( dest, functor() );
272 /// Synonym for \ref enqueue function
273 bool push( const value_type& val )
275 return enqueue( val );
278 /// Synonym for template version of \ref enqueue function
279 template <typename Type, typename Func>
280 bool push( const Type& data, Func f )
282 return enqueue( data, f );
285 # ifdef CDS_EMPLACE_SUPPORT
286 /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
288 This function is available only for compiler that supports
289 variadic template and move semantics
291 template <typename... Args>
292 bool emplace( Args&&... args )
294 scoped_node_ptr p( alloc_node_move( std::forward<Args>(args)... ));
295 if ( base_class::enqueue( *p )) {
304 /// Synonym for \ref dequeue function
305 bool pop( value_type& dest )
307 return dequeue( dest );
310 /// Synonym for template version of \ref dequeue function
311 template <typename Type, typename Func>
312 bool pop( Type& dest, Func f )
314 return dequeue( dest, f );
317 /// Checks if the queue is empty
320 return base_class::empty();
325 The function repeatedly calls \ref dequeue until it returns nullptr.
326 The disposer defined in template \p Options is called for each item
327 that can be safely disposed.
335 }} // namespace cds::container
337 #endif // #ifndef __CDS_CONTAINER_MOIR_QUEUE_H