3 #ifndef CDSLIB_CONTAINER_MOIR_QUEUE_H
4 #define CDSLIB_CONTAINER_MOIR_QUEUE_H
7 #include <cds/container/msqueue.h>
8 #include <cds/intrusive/moir_queue.h>
10 namespace cds { namespace container {
14 template <typename GC, typename T, typename Traits>
15 struct make_moir_queue: public cds::container::details::make_msqueue< GC, T, Traits >
17 typedef cds::container::details::make_msqueue< GC, T, Traits > base_class;
18 typedef cds::intrusive::MoirQueue< GC, typename base_class::node_type, typename base_class::intrusive_traits > type;
23 /// A variation of Michael & Scott's lock-free queue
24 /** @ingroup cds_nonintrusive_queue
25 It is non-intrusive version of \p cds::intrusive::MoirQueue.
28 - \p GC - garbage collector type: \p gc::HP, \p gc::DHP
29 - \p T - a type stored in the queue.
30 - \p Traits - queue traits, default is \p msqueue::traits. You can use \p msqueue::make_traits
31 metafunction to make your traits or just derive your traits from \p %msqueue::traits:
33 struct myTraits: public cds::container::msqueue::traits {
34 typedef cds::intrusive::msqueue::stat<> stat;
35 typedef cds::atomicity::item_counter item_counter;
37 typedef cds::container::MoirQueue< cds::gc::HP, Foo, myTraits > myQueue;
39 // Equivalent make_traits example:
40 typedef cds::container::MoirQueue< cds::gc::HP, Foo,
41 typename cds::container::msqueue::make_traits<
42 cds::opt::stat< cds::container::msqueue::stat<> >,
43 cds::opt::item_counter< cds::atomicity::item_counter >
48 template <typename GC, typename T, typename Traits = cds::container::msqueue::traits >
50 #ifdef CDS_DOXYGEN_INVOKED
51 private intrusive::MoirQueue< GC, intrusive::msqueue::node< T >, Traits >
53 private details::make_moir_queue< GC, T, Traits >::type
57 typedef details::make_moir_queue< GC, T, Traits > maker;
58 typedef typename maker::type base_class;
62 /// Rebind template arguments
63 template <typename GC2, typename T2, typename Traits2>
65 typedef MoirQueue< GC2, T2, Traits2 > other ; ///< Rebinding result
69 typedef T value_type ; ///< Value type stored in the queue
70 typedef typename base_class::gc gc; ///< Garbage collector
71 typedef typename base_class::back_off back_off; ///< Back-off strategy
72 typedef typename maker::allocator_type allocator_type; ///< Allocator type used for allocate/deallocate the nodes
73 typedef typename base_class::item_counter item_counter; ///< Item counting policy used
74 typedef typename base_class::stat stat; ///< Internal statistics policy used
75 typedef typename base_class::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
79 typedef typename maker::node_type node_type; ///< queue node type (derived from intrusive::msqueue::node)
81 typedef typename maker::cxx_allocator cxx_allocator;
82 typedef typename maker::node_deallocator node_deallocator; // deallocate node
83 typedef typename base_class::node_traits node_traits;
88 static node_type * alloc_node()
90 return cxx_allocator().New();
92 static node_type * alloc_node( const value_type& val )
94 return cxx_allocator().New( val );
96 template <typename... Args>
97 static node_type * alloc_node_move( Args&&... args )
99 return cxx_allocator().MoveNew( std::forward<Args>( args )... );
101 static void free_node( node_type * p )
103 node_deallocator()( p );
106 struct node_disposer {
107 void operator()( node_type * pNode )
112 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
116 /// Initializes empty queue
120 /// Destructor clears the queue
124 /// Enqueues \p val value into the queue.
126 The function makes queue node in dynamic memory calling copy constructor for \p val
127 and then it calls intrusive::MoirQueue::enqueue.
128 Returns \p true if success, \p false otherwise.
130 bool enqueue( value_type const& val )
132 scoped_node_ptr p( alloc_node(val) );
133 if ( base_class::enqueue( *p )) {
140 /// Enqueues \p data to queue using a functor
142 \p Func is a functor calling to create a new node.
143 The functor should initialize creating node
144 and it takes one argument - a reference to a new node of type \ref value_type :
146 cds:container::MoirQueue< cds::gc::HP, Foo > myQueue;
148 myQueue.enqueue_with( [&bar]( Foo& dest ) { dest = bar; } );
151 template <typename Func>
152 bool enqueue_with( Func f )
154 scoped_node_ptr p( alloc_node() );
156 if ( base_class::enqueue( *p )) {
163 /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
164 template <typename... Args>
165 bool emplace( Args&&... args )
167 scoped_node_ptr p( alloc_node_move( std::forward<Args>( args )... ) );
168 if ( base_class::enqueue( *p ) ) {
175 /// Synonym for \p enqueue() function
176 bool push( value_type const& val )
178 return enqueue( val );
181 /// Synonym for \p enqueue_with() function
182 template <typename Func>
183 bool push_with( Func f )
185 return enqueue_with( f );
188 /// Dequeues a value from the queue
190 If queue is not empty, the function returns \p true, \p dest contains copy of
191 dequeued value. The assignment operator for type \ref value_type is invoked.
192 If queue is empty, the function returns \p false, \p dest is unchanged.
194 bool dequeue( value_type& dest )
196 return dequeue_with( [&dest]( value_type& src ) { dest = src; } );
199 /// Dequeues a value using a functor
201 \p Func is a functor called to copy dequeued value.
202 The functor takes one argument - a reference to removed node:
204 cds:container::MoirQueue< cds::gc::HP, Foo > myQueue;
206 myQueue.dequeue_with( [&bar]( Foo& src ) { bar = std::move( src );});
208 The functor is called only if the queue is not empty.
210 template <typename Func>
211 bool dequeue_with( Func f )
213 typename base_class::dequeue_result res;
214 if ( base_class::do_dequeue( res )) {
215 f( node_traits::to_value_ptr( *res.pNext )->m_value );
216 base_class::dispose_result( res );
222 /// Synonym for \p dequeue() function
223 bool pop( value_type& dest )
225 return dequeue( dest );
228 /// Synonym for \p dequeue_with() function
229 template <typename Func>
230 bool pop_with( Func f )
232 return dequeue_with( f );
237 The function repeatedly calls \ref dequeue until it returns \p nullptr.
238 The disposer defined in template \p Traits is called for each item
239 that can be safely disposed.
246 /// Checks if the queue is empty
249 return base_class::empty();
252 /// Returns queue's item count (see \ref intrusive::MSQueue::size for explanation)
255 return base_class::size();
258 /// Returns refernce to internal statistics
259 const stat& statistics() const
261 return base_class::statistics();
266 }} // namespace cds::container
268 #endif // #ifndef CDSLIB_CONTAINER_MOIR_QUEUE_H