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_MOIR_QUEUE_H
32 #define CDSLIB_CONTAINER_MOIR_QUEUE_H
35 #include <cds/container/msqueue.h>
36 #include <cds/intrusive/moir_queue.h>
38 namespace cds { namespace container {
42 template <typename GC, typename T, typename Traits>
43 struct make_moir_queue: public cds::container::details::make_msqueue< GC, T, Traits >
45 typedef cds::container::details::make_msqueue< GC, T, Traits > base_class;
46 typedef cds::intrusive::MoirQueue< GC, typename base_class::node_type, typename base_class::intrusive_traits > type;
51 /// A variation of Michael & Scott's lock-free queue
52 /** @ingroup cds_nonintrusive_queue
53 It is non-intrusive version of \p cds::intrusive::MoirQueue.
56 - \p GC - garbage collector type: \p gc::HP, \p gc::DHP
57 - \p T - a type stored in the queue.
58 - \p Traits - queue traits, default is \p msqueue::traits. You can use \p msqueue::make_traits
59 metafunction to make your traits or just derive your traits from \p %msqueue::traits:
61 struct myTraits: public cds::container::msqueue::traits {
62 typedef cds::intrusive::msqueue::stat<> stat;
63 typedef cds::atomicity::item_counter item_counter;
65 typedef cds::container::MoirQueue< cds::gc::HP, Foo, myTraits > myQueue;
67 // Equivalent make_traits example:
68 typedef cds::container::MoirQueue< cds::gc::HP, Foo,
69 typename cds::container::msqueue::make_traits<
70 cds::opt::stat< cds::container::msqueue::stat<> >,
71 cds::opt::item_counter< cds::atomicity::item_counter >
76 template <typename GC, typename T, typename Traits = cds::container::msqueue::traits >
78 #ifdef CDS_DOXYGEN_INVOKED
79 private intrusive::MoirQueue< GC, intrusive::msqueue::node< T >, Traits >
81 private details::make_moir_queue< GC, T, Traits >::type
85 typedef details::make_moir_queue< GC, T, Traits > maker;
86 typedef typename maker::type base_class;
90 /// Rebind template arguments
91 template <typename GC2, typename T2, typename Traits2>
93 typedef MoirQueue< GC2, T2, Traits2 > other ; ///< Rebinding result
96 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = base_class::c_nHazardPtrCount; ///< Count of hazard pointer required for the algorithm
99 typedef T value_type ; ///< Value type stored in the queue
100 typedef typename base_class::gc gc; ///< Garbage collector
101 typedef typename base_class::back_off back_off; ///< Back-off strategy
102 typedef typename maker::allocator_type allocator_type; ///< Allocator type used for allocate/deallocate the nodes
103 typedef typename base_class::item_counter item_counter; ///< Item counting policy used
104 typedef typename base_class::stat stat; ///< Internal statistics policy used
105 typedef typename base_class::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
109 typedef typename maker::node_type node_type; ///< queue node type (derived from intrusive::msqueue::node)
111 typedef typename maker::cxx_allocator cxx_allocator;
112 typedef typename maker::node_deallocator node_deallocator; // deallocate node
113 typedef typename base_class::node_traits node_traits;
118 static node_type * alloc_node()
120 return cxx_allocator().New();
122 static node_type * alloc_node( const value_type& val )
124 return cxx_allocator().New( val );
126 template <typename... Args>
127 static node_type * alloc_node_move( Args&&... args )
129 return cxx_allocator().MoveNew( std::forward<Args>( args )... );
131 static void free_node( node_type * p )
133 node_deallocator()( p );
136 struct node_disposer {
137 void operator()( node_type * pNode )
142 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
146 /// Initializes empty queue
150 /// Destructor clears the queue
154 /// Enqueues \p val value into the queue.
156 The function makes queue node in dynamic memory calling copy constructor for \p val
157 and then it calls \p intrusive::MoirQueue::enqueue.
158 Returns \p true if success, \p false otherwise.
160 bool enqueue( value_type const& val )
162 scoped_node_ptr p( alloc_node(val));
163 if ( base_class::enqueue( *p )) {
170 /// Enqueues \p val value into the queue, move semantics
171 bool enqueue( value_type&& val )
173 scoped_node_ptr p( alloc_node_move( std::move( val )));
174 if ( base_class::enqueue( *p )) {
181 /// Enqueues \p data to queue using a functor
183 \p Func is a functor calling to create a new node.
184 The functor should initialize creating node
185 and it takes one argument - a reference to a new node of type \ref value_type :
187 cds:container::MoirQueue< cds::gc::HP, Foo > myQueue;
189 myQueue.enqueue_with( [&bar]( Foo& dest ) { dest = bar; } );
192 template <typename Func>
193 bool enqueue_with( Func f )
195 scoped_node_ptr p( alloc_node());
197 if ( base_class::enqueue( *p )) {
204 /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
205 template <typename... Args>
206 bool emplace( Args&&... args )
208 scoped_node_ptr p( alloc_node_move( std::forward<Args>( args )... ));
209 if ( base_class::enqueue( *p )) {
216 /// Synonym for \p enqueue() function
217 bool push( value_type const& val )
219 return enqueue( val );
222 /// Synonym for \p enqueue() function, move semantics
223 bool push( value_type&& val )
225 return enqueue( std::move( val ));
228 /// Synonym for \p enqueue_with() function
229 template <typename Func>
230 bool push_with( Func f )
232 return enqueue_with( f );
235 /// Dequeues a value from the queue
237 If queue is not empty, the function returns \p true, \p dest contains copy of
238 dequeued value. The assignment operator for type \ref value_type is invoked.
239 If queue is empty, the function returns \p false, \p dest is unchanged.
241 bool dequeue( value_type& dest )
243 return dequeue_with( [&dest]( value_type& src ) {
244 // TSan finds a race between this read of \p src and node_type constructor
245 // I think, it is wrong
246 CDS_TSAN_ANNOTATE_IGNORE_READS_BEGIN;
247 dest = std::move( src );
248 CDS_TSAN_ANNOTATE_IGNORE_READS_END;
252 /// Dequeues a value using a functor
254 \p Func is a functor called to copy dequeued value.
255 The functor takes one argument - a reference to removed node:
257 cds:container::MoirQueue< cds::gc::HP, Foo > myQueue;
259 myQueue.dequeue_with( [&bar]( Foo& src ) { bar = std::move( src );});
261 The functor is called only if the queue is not empty.
263 template <typename Func>
264 bool dequeue_with( Func f )
266 typename base_class::dequeue_result res;
267 if ( base_class::do_dequeue( res )) {
268 f( node_traits::to_value_ptr( *res.pNext )->m_value );
269 base_class::dispose_result( res );
275 /// Synonym for \p dequeue() function
276 bool pop( value_type& dest )
278 return dequeue( dest );
281 /// Synonym for \p dequeue_with() function
282 template <typename Func>
283 bool pop_with( Func f )
285 return dequeue_with( f );
290 The function repeatedly calls \ref dequeue until it returns \p nullptr.
291 The disposer defined in template \p Traits is called for each item
292 that can be safely disposed.
299 /// Checks if the queue is empty
302 return base_class::empty();
305 /// Returns queue's item count (see \ref intrusive::MSQueue::size for explanation)
308 return base_class::size();
311 /// Returns refernce to internal statistics
312 const stat& statistics() const
314 return base_class::statistics();
319 }} // namespace cds::container
321 #endif // #ifndef CDSLIB_CONTAINER_MOIR_QUEUE_H