3 #ifndef __CDS_INTRUSIVE_VYUKOV_MPMC_CYCLE_QUEUE_H
4 #define __CDS_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 {
15 struct traits : public cds::container::vyukov_queue::traits
17 /// The functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used only in \p clear()
18 typedef opt::v::empty_disposer disposer;
21 /// Metafunction converting option list to \p vyukov_queue::traits
23 Supported \p Options are:
24 - \p opt::buffer - the buffer type for internal cyclic array. Possible types are:
25 \p opt::v::dynamic_buffer (the default), \p opt::v::static_buffer. The type of
26 element in the buffer is not important: it will be changed via \p rebind metafunction.
27 - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer.
28 This option is used only in \p clear() member function.
29 - \p opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter (item counting disabled)
30 To enable item counting use \p cds::atomicity::item_counter
31 - \p opt::alignment - the alignment for internal queue data. Default is \p opt::cache_line_alignment
32 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
33 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
35 Example: declare \p %VyukovMPMCCycleQueue with item counting and static iternal buffer of size 1024:
37 typedef cds::intrusive::VyukovMPMCCycleQueue< Foo,
38 typename cds::intrusive::vyukov_queue::make_traits<
39 cds::opt::buffer< cds::opt::v::static_buffer< void *, 1024 >,
40 cds::opt::item_counte< cds::atomicity::item_counter >
45 template <typename... Options>
47 # ifdef CDS_DOXYGEN_INVOKED
48 typedef implementation_defined type; ///< Metafunction result
50 typedef typename cds::opt::make_options<
51 typename cds::opt::find_type_traits< traits, Options... >::type
57 } // namespace vyukov_queue
59 /// Vyukov's MPMC bounded queue
60 /** @ingroup cds_intrusive_queue
61 This algorithm is developed by Dmitry Vyukov (see http://www.1024cores.net)
63 Implementation of intrusive version is based on container::VyukovMPMCCycleQueue.
66 - \p T - type stored in queue.
67 - \p Traits - queue traits, default is \p vykov_queue::traits. You can use \p vykov_queue::make_traits
68 metafunction to make your traits or just derive your traits from \p %vykov_queue::traits:
70 struct myTraits: public cds::intrusive::vykov_queue::traits {
71 typedef cds::atomicity::item_counter item_counter;
73 typedef cds::intrusive::VyukovMPMCCycleQueue< Foo, myTraits > myQueue;
75 // Equivalent make_traits example:
76 typedef cds::intrusive::VyukovMPMCCycleQueue< cds::gc::HP, Foo,
77 typename cds::intrusive::vykov_queue::make_traits<
78 cds::opt::item_counter< cds::atomicity::item_counter >
83 Instead of saving copy of enqueued data, the intrusive implementation stores pointer to passed data.
87 #include <cds/intrusive/vyukov_mpmc_cycle_queue.h>
93 // Queue of Foo pointers, capacity is 1024, statically allocated buffer:
94 typedef cds::intrusive::VyukovMPMCCycleQueue< Foo,
95 typename cds::intrusive::vyukov_queue::make_traits<
96 cds::opt::buffer< cds::opt::v::static_buffer< Foo, 1024 > >
101 // Queue of Foo pointers, capacity is 1024, dynamically allocated buffer:
102 struct queue_traits: public cds::intrusive::vyukov_queue::traits
104 typedef cds::opt::v::dynamic_buffer< Foo > buffer;
106 typedef cds::intrusive::VyukovMPMCCycleQueue< Foo, queue_traits > dynamic_queue;
107 dynamic_queue dynQueue( 1024 );
110 template <typename T, typename Traits = vyukov_queue::traits >
111 class VyukovMPMCCycleQueue
112 : private container::VyukovMPMCCycleQueue< T*, Traits >
115 typedef container::VyukovMPMCCycleQueue< T*, Traits > base_class;
118 typedef T value_type; ///< type of data to be stored in the queue
119 typedef Traits traits; ///< Queue traits
120 typedef typename traits::item_counter item_counter; ///< Item counter type
121 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
122 typedef typename traits::disposer disposer; ///< Item disposer
125 /// Rebind template arguments
126 template <typename T2, typename Traits2>
128 typedef VyukovMPMCCycleQueue< T2, Traits2> other ; ///< Rebinding result
132 /// Constructs the queue of capacity \p nCapacity
134 For \p cds::opt::v::static_buffer the \p nCapacity parameter is ignored.
136 VyukovMPMCCycleQueue( size_t nCapacity = 0 )
137 : base_class( nCapacity )
140 /// Enqueues \p data to queue
142 @note The intrusive queue stores pointer to \p data passed, not the copy of \p data.
144 bool enqueue( value_type& data )
146 return base_class::enqueue( &data );
149 /// Dequeues an item from queue
151 \p Traits::disposer is not called. You may manually delete the returned pointer.
153 If queue is empty, returns \p nullptr.
155 value_type * dequeue()
157 value_type * p = nullptr;
158 return base_class::dequeue( p ) ? p : nullptr;
161 /// Synonym for \p enqueue()
162 bool push( value_type& data )
164 return enqueue( data );
167 /// Synonym for \p dequeue()
173 /// Clears queue in lock-free manner.
175 \p f parameter is a functor to dispose removed items.
176 The interface of \p Disposer is:
179 void operator ()( T * val );
182 You can pass \p disposer by reference using \p std::ref.
183 The disposer will be called immediately for each item.
185 template <typename Disposer>
186 void clear( Disposer f )
189 while ( (pv = pop()) != nullptr ) {
196 This function uses the disposer that is specified in \p Traits.
203 /// Checks if the queue is empty
206 return base_class::empty();
209 /// Returns queue's item count
211 The value returned depends on \p vyukov_queue::traits::item_counter option.
212 For \p atomicity::empty_item_counter, this function always returns 0.
216 return base_class::size();
219 /// Returns capacity of the queue
220 size_t capacity() const
222 return base_class::capacity();
225 }} // namespace cds::intrusive
227 #endif // #ifndef __CDS_INTRUSIVE_VYUKOV_MPMC_CYCLE_QUEUE_H