3 #ifndef CDSLIB_INTRUSIVE_VYUKOV_MPMC_CYCLE_QUEUE_H
4 #define CDSLIB_INTRUSIVE_VYUKOV_MPMC_CYCLE_QUEUE_H
6 #include <cds/intrusive/details/base.h>
7 #include <cds/container/vyukov_mpmc_cycle_queue.h>
9 namespace cds { namespace intrusive {
11 /// VyukovMPMCCycleQueue related definitions
12 /** @ingroup cds_intrusive_helper
14 namespace vyukov_queue {
16 /// VyukovMPMCCycleQueue traits
17 struct traits : public cds::container::vyukov_queue::traits
19 /// The functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used only in \p clear()
20 typedef opt::v::empty_disposer disposer;
23 /// Metafunction converting option list to \p vyukov_queue::traits
25 Supported \p Options are:
26 - \p opt::buffer - the buffer type for internal cyclic array. Possible types are:
27 \p opt::v::dynamic_buffer (the default), \p opt::v::static_buffer. The type of
28 element in the buffer is not important: it will be changed via \p rebind metafunction.
29 - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer.
30 This option is used only in \p clear() member function.
31 - \p opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter (item counting disabled)
32 To enable item counting use \p cds::atomicity::item_counter
33 - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
34 - \p opt::padding - padding for internal critical atomic data. Default is \p opt::cache_line_padding
35 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
36 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
38 Example: declare \p %VyukovMPMCCycleQueue with item counting and static iternal buffer of size 1024:
40 typedef cds::intrusive::VyukovMPMCCycleQueue< Foo,
41 typename cds::intrusive::vyukov_queue::make_traits<
42 cds::opt::buffer< cds::opt::v::static_buffer< void *, 1024 >,
43 cds::opt::item_counter< cds::atomicity::item_counter >
48 template <typename... Options>
50 # ifdef CDS_DOXYGEN_INVOKED
51 typedef implementation_defined type; ///< Metafunction result
53 typedef typename cds::opt::make_options<
54 typename cds::opt::find_type_traits< traits, Options... >::type
60 } // namespace vyukov_queue
62 /// Vyukov's MPMC bounded queue
63 /** @ingroup cds_intrusive_queue
64 This algorithm is developed by Dmitry Vyukov (see http://www.1024cores.net)
66 Implementation of intrusive version is based on container::VyukovMPMCCycleQueue.
69 - \p T - type stored in queue.
70 - \p Traits - queue traits, default is \p vykov_queue::traits. You can use \p vykov_queue::make_traits
71 metafunction to make your traits or just derive your traits from \p %vykov_queue::traits:
73 struct myTraits: public cds::intrusive::vykov_queue::traits {
74 typedef cds::atomicity::item_counter item_counter;
76 typedef cds::intrusive::VyukovMPMCCycleQueue< Foo, myTraits > myQueue;
78 // Equivalent make_traits example:
79 typedef cds::intrusive::VyukovMPMCCycleQueue< cds::gc::HP, Foo,
80 typename cds::intrusive::vykov_queue::make_traits<
81 cds::opt::item_counter< cds::atomicity::item_counter >
86 Instead of saving copy of enqueued data, the intrusive implementation stores pointer to passed data.
90 #include <cds/intrusive/vyukov_mpmc_cycle_queue.h>
96 // Queue of Foo pointers, capacity is 1024, statically allocated buffer:
97 typedef cds::intrusive::VyukovMPMCCycleQueue< Foo,
98 typename cds::intrusive::vyukov_queue::make_traits<
99 cds::opt::buffer< cds::opt::v::static_buffer< Foo, 1024 > >
102 static_queue stQueue;
104 // Queue of Foo pointers, capacity is 1024, dynamically allocated buffer:
105 struct queue_traits: public cds::intrusive::vyukov_queue::traits
107 typedef cds::opt::v::dynamic_buffer< Foo > buffer;
109 typedef cds::intrusive::VyukovMPMCCycleQueue< Foo, queue_traits > dynamic_queue;
110 dynamic_queue dynQueue( 1024 );
113 template <typename T, typename Traits = vyukov_queue::traits >
114 class VyukovMPMCCycleQueue
115 : private container::VyukovMPMCCycleQueue< T*, Traits >
118 typedef container::VyukovMPMCCycleQueue< T*, Traits > base_class;
121 typedef T value_type; ///< type of data to be stored in the queue
122 typedef Traits traits; ///< Queue traits
123 typedef typename traits::item_counter item_counter; ///< Item counter type
124 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
125 typedef typename traits::disposer disposer; ///< Item disposer
126 typedef typename traits::back_off back_off; ///< back-off strategy
129 /// Rebind template arguments
130 template <typename T2, typename Traits2>
132 typedef VyukovMPMCCycleQueue< T2, Traits2> other ; ///< Rebinding result
136 /// Constructs the queue of capacity \p nCapacity
138 For \p cds::opt::v::static_buffer the \p nCapacity parameter is ignored.
140 VyukovMPMCCycleQueue( size_t nCapacity = 0 )
141 : base_class( nCapacity )
144 /// Enqueues \p data to queue
146 @note The intrusive queue stores pointer to \p data passed, not the copy of \p data.
148 bool enqueue( value_type& data )
150 return base_class::enqueue( &data );
153 /// Dequeues an item from queue
155 \p Traits::disposer is not called. You may manually delete the returned pointer.
157 If queue is empty, returns \p nullptr.
159 value_type * dequeue()
161 value_type * p = nullptr;
162 return base_class::dequeue( p ) ? p : nullptr;
165 /// Synonym for \p enqueue()
166 bool push( value_type& data )
168 return enqueue( data );
171 /// Synonym for \p dequeue()
177 /// Clears queue in lock-free manner.
179 \p f parameter is a functor to dispose removed items.
180 The interface of \p Disposer is:
183 void operator ()( T * val );
186 The disposer will be called immediately for each item.
188 template <typename Disposer>
189 void clear( Disposer f )
192 while ( (pv = pop()) != nullptr ) {
199 This function uses the disposer that is specified in \p Traits.
206 /// Checks if the queue is empty
209 return base_class::empty();
212 /// Returns queue's item count
214 The value returned depends on \p vyukov_queue::traits::item_counter option.
215 For \p atomicity::empty_item_counter, this function always returns 0.
219 return base_class::size();
222 /// Returns capacity of the queue
223 size_t capacity() const
225 return base_class::capacity();
228 }} // namespace cds::intrusive
230 #endif // #ifndef CDSLIB_INTRUSIVE_VYUKOV_MPMC_CYCLE_QUEUE_H