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_OPTIMISTIC_QUEUE_H
32 #define CDSLIB_CONTAINER_OPTIMISTIC_QUEUE_H
35 #include <cds/intrusive/optimistic_queue.h>
36 #include <cds/container/details/base.h>
38 namespace cds { namespace container {
40 /// OptimisticQueue related definitions
41 /** @ingroup cds_nonintrusive_helper
43 namespace optimistic_queue {
44 /// Internal statistics
45 template <typename Counter = cds::intrusive::optimistic_queue::stat<>::counter_type >
46 using stat = cds::intrusive::optimistic_queue::stat< Counter >;
48 /// Dummy internal statistics
49 typedef cds::intrusive::optimistic_queue::empty_stat empty_stat;
51 /// MSQueue default type traits
55 typedef CDS_DEFAULT_ALLOCATOR allocator;
58 typedef cds::backoff::empty back_off;
60 /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
61 typedef atomicity::empty_item_counter item_counter;
63 /// Internal statistics (by default, disabled)
65 Possible option value are: \p optimistic_queue::stat, \p optimistic_queue::empty_stat (the default),
66 user-provided class that supports \p %optimistic_queue::stat interface.
68 typedef optimistic_queue::empty_stat stat;
70 /// C++ memory ordering model
72 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
73 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
75 typedef opt::v::relaxed_ordering memory_model;
77 /// Padding for internal critical atomic data. Default is \p opt::cache_line_padding
78 enum { padding = opt::cache_line_padding };
81 /// Metafunction converting option list to \p msqueue::traits
83 Supported \p Options are:
84 - \p opt::allocator - allocator (like \p std::allocator) used for allocating queue nodes. Default is \ref CDS_DEFAULT_ALLOCATOR
85 - \p opt::back_off - back-off strategy used, default is \p cds::backoff::empty.
86 - \p opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter (item counting disabled)
87 To enable item counting use \p cds::atomicity::item_counter
88 - \p opt::stat - the type to gather internal statistics.
89 Possible statistics types are: \p optimistic_queue::stat, \p optimistic_queue::empty_stat,
90 user-provided class that supports \p %optimistic_queue::stat interface.
91 Default is \p %optimistic_queue::empty_stat.
92 - \p opt::padding - padding for internal critical atomic data. Default is \p opt::cache_line_padding
93 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
94 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
96 Example: declare \p OptimisticQueue with item counting and internal statistics
98 typedef cds::container::OptimisticQueue< cds::gc::HP, Foo,
99 typename cds::container::optimistic_queue::make_traits<
100 cds::opt::item_counter< cds::atomicity::item_counter >,
101 cds::opt::stat< cds::container::optimistic_queue::stat<> >
106 template <typename... Options>
108 # ifdef CDS_DOXYGEN_INVOKED
109 typedef implementation_defined type; ///< Metafunction result
111 typedef typename cds::opt::make_options<
112 typename cds::opt::find_type_traits< traits, Options... >::type
117 } // namespace optimistic_queue
121 template <typename GC, typename T, typename Traits>
122 struct make_optimistic_queue
125 typedef T value_type;
126 typedef Traits traits;
128 struct node_type: public cds::intrusive::optimistic_queue::node< gc >
132 node_type( value_type const& val )
136 template <typename... Args>
137 node_type( Args&&... args )
138 : m_value( std::forward<Args>(args)...)
142 typedef typename traits::allocator::template rebind<node_type>::other allocator_type;
143 typedef cds::details::Allocator< node_type, allocator_type > cxx_allocator;
145 struct node_deallocator
147 void operator ()( node_type * pNode )
149 cxx_allocator().Delete( pNode );
153 struct intrusive_traits : public traits
155 typedef cds::intrusive::optimistic_queue::base_hook< opt::gc<gc> > hook;
156 typedef node_deallocator disposer;
157 static CDS_CONSTEXPR const opt::link_check_type link_checker = cds::intrusive::optimistic_queue::traits::link_checker;
160 typedef intrusive::OptimisticQueue< gc, node_type, intrusive_traits > type;
162 } // namespace details
166 /** @ingroup cds_nonintrusive_queue
167 Implementation of Ladan-Mozes & Shavit optimistic queue algorithm.
168 - [2008] Edya Ladan-Mozes, Nir Shavit "An Optimistic Approach to Lock-Free FIFO Queues"
171 - \p GC - garbage collector type: \p gc::HP, \p gc::DHP.
172 - \p T - type of values to be stored in the queue
173 - \p Traits - queue traits, default is \p optimistic_queue::traits. You can use \p optimistic_queue::make_traits
174 metafunction to make your traits or just derive your traits from \p %optimistic_queue::traits:
176 struct myTraits: public cds::container::optimistic_queue::traits {
177 typedef cds::intrusive::optimistic_queue::stat<> stat;
178 typedef cds::atomicity::item_counter item_counter;
180 typedef cds::container::OptimisticQueue< cds::gc::HP, Foo, myTraits > myQueue;
182 // Equivalent make_traits example:
183 typedef cds::container::OptimisticQueue< cds::gc::HP, Foo,
184 typename cds::container::optimistic_queue::make_traits<
185 cds::opt::stat< cds::container::optimistic_queue::stat<> >,
186 cds::opt::item_counter< cds::atomicity::item_counter >
191 template <typename GC, typename T, typename Traits = optimistic_queue::traits >
192 class OptimisticQueue:
193 #ifdef CDS_DOXYGEN_INVOKED
194 private intrusive::OptimisticQueue< GC, cds::intrusive::optimistic_queue::node< T >, Traits >
196 private details::make_optimistic_queue< GC, T, Traits >::type
200 typedef details::make_optimistic_queue< GC, T, Traits > maker;
201 typedef typename maker::type base_class;
205 /// Rebind template arguments
206 template <typename GC2, typename T2, typename Traits2>
208 typedef OptimisticQueue< GC2, T2, Traits2 > other ; ///< Rebinding result
212 typedef GC gc; ///< Garbage collector
213 typedef T value_type; ///< Value type to be stored in the queue
214 typedef Traits traits; ///< Queue traits
216 typedef typename base_class::back_off back_off; ///< Back-off strategy used
217 typedef typename maker::allocator_type allocator_type; ///< Allocator type used for allocate/deallocate the nodes
218 typedef typename base_class::item_counter item_counter; ///< Item counting policy used
219 typedef typename base_class::stat stat; ///< Internal statistics policy used
220 typedef typename base_class::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option
222 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = base_class::c_nHazardPtrCount; ///< Count of hazard pointer required for the algorithm
226 typedef typename maker::node_type node_type; ///< queue node type (derived from intrusive::optimistic_queue::node)
227 typedef typename maker::cxx_allocator cxx_allocator;
228 typedef typename maker::node_deallocator node_deallocator; // deallocate node
229 typedef typename base_class::node_traits node_traits;
234 static node_type * alloc_node()
236 return cxx_allocator().New();
238 static node_type * alloc_node( const value_type& val )
240 return cxx_allocator().New( val );
242 template <typename... Args>
243 static node_type * alloc_node_move( Args&&... args )
245 return cxx_allocator().MoveNew( std::forward<Args>( args )... );
247 static void free_node( node_type * p )
249 node_deallocator()( p );
252 struct node_disposer {
253 void operator()( node_type * pNode )
258 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
262 /// Initializes empty queue
266 /// Destructor clears the queue
270 /// Enqueues \p val value into the queue.
272 The function makes queue node in dynamic memory calling copy constructor for \p val
273 and then it calls \p intrusive::OptimisticQueue::enqueue.
274 Returns \p true if success, \p false otherwise.
276 bool enqueue( const value_type& val )
278 scoped_node_ptr p( alloc_node(val));
279 if ( base_class::enqueue( *p )) {
286 /// Enqueues \p val value into the queue, move semntics
287 bool enqueue( value_type&& val )
289 scoped_node_ptr p( alloc_node_move( std::move( val )));
290 if ( base_class::enqueue( *p )) {
297 /// Enqueues \p data to queue using a functor
299 \p Func is a functor called to create node.
300 The functor \p f takes one argument - a reference to a new node of type \ref value_type :
302 cds::container::OptimisticQueue< cds::gc::HP, Foo > myQueue;
304 myQueue.enqueue_with( [&bar]( Foo& dest ) { dest = bar; } );
307 template <typename Func>
308 bool enqueue_with( Func f )
310 scoped_node_ptr p( alloc_node());
312 if ( base_class::enqueue( *p )) {
319 /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
320 template <typename... Args>
321 bool emplace( Args&&... args )
323 scoped_node_ptr p( alloc_node_move( std::forward<Args>(args)... ));
324 if ( base_class::enqueue( *p )) {
331 /// Synonym for \p enqueue( const value_type& ) function
332 bool push( const value_type& val )
334 return enqueue( val );
337 /// Synonym for \p enqueue( value_type&& ) function
338 bool push( value_type&& val )
340 return enqueue( std::move( val ));
343 /// Synonym for \p enqueue_with() function
344 template <typename Func>
345 bool push_with( Func f )
347 return enqueue_with( f );
350 /// Dequeues a value from the queue
352 If queue is not empty, the function returns \p true, \p dest contains copy of
353 dequeued value. The assignment operator for type \p value_type is invoked.
355 If queue is empty, the function returns \p false, \p dest is unchanged.
357 bool dequeue( value_type& dest )
359 return dequeue_with( [&dest]( value_type& src ) { dest = std::move( src ); });
362 /// Dequeues a value using a functor
364 \p Func is a functor called to copy dequeued value.
365 The functor takes one argument - a reference to removed node:
367 cds:container::OptimisticQueue< cds::gc::HP, Foo > myQueue;
369 myQueue.dequeue_with( [&bar]( Foo& src ) { bar = std::move( src );});
371 The functor is called only if the queue is not empty.
373 template <typename Func>
374 bool dequeue_with( Func f )
376 typename base_class::dequeue_result res;
377 if ( base_class::do_dequeue( res )) {
378 f( node_traits::to_value_ptr( *res.pNext )->m_value );
380 base_class::dispose_result( res );
387 /// Synonym for \ref dequeue() function
388 bool pop( value_type& dest )
390 return dequeue( dest );
393 /// Synonym for template version of \p dequeue_with() function
394 template <typename Func>
395 bool pop_with( Func f )
397 return dequeue_with( f );
400 /// Checks if the queue is empty
403 return base_class::empty();
408 The function repeatedly calls \ref dequeue until it returns \p nullptr.
415 /// Returns queue's item count
416 /** \copydetails cds::intrusive::OptimisticQueue::size()
420 return base_class::size();
423 /// Returns reference to internal statistics
424 const stat& statistics() const
426 return base_class::statistics();
430 }} // namespace cds::container
432 #endif //#ifndef CDSLIB_CONTAINER_OPTIMISTIC_QUEUE_H