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::alignment - the alignment for internal queue data. Default is \p opt::cache_line_alignment
34 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
35 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
37 Example: declare \p %VyukovMPMCCycleQueue with item counting and static iternal buffer of size 1024:
39 typedef cds::intrusive::VyukovMPMCCycleQueue< Foo,
40 typename cds::intrusive::vyukov_queue::make_traits<
41 cds::opt::buffer< cds::opt::v::static_buffer< void *, 1024 >,
42 cds::opt::item_counte< cds::atomicity::item_counter >
47 template <typename... Options>
49 # ifdef CDS_DOXYGEN_INVOKED
50 typedef implementation_defined type; ///< Metafunction result
52 typedef typename cds::opt::make_options<
53 typename cds::opt::find_type_traits< traits, Options... >::type
59 } // namespace vyukov_queue
61 /// Vyukov's MPMC bounded queue
62 /** @ingroup cds_intrusive_queue
63 This algorithm is developed by Dmitry Vyukov (see http://www.1024cores.net)
65 Implementation of intrusive version is based on container::VyukovMPMCCycleQueue.
68 - \p T - type stored in queue.
69 - \p Traits - queue traits, default is \p vykov_queue::traits. You can use \p vykov_queue::make_traits
70 metafunction to make your traits or just derive your traits from \p %vykov_queue::traits:
72 struct myTraits: public cds::intrusive::vykov_queue::traits {
73 typedef cds::atomicity::item_counter item_counter;
75 typedef cds::intrusive::VyukovMPMCCycleQueue< Foo, myTraits > myQueue;
77 // Equivalent make_traits example:
78 typedef cds::intrusive::VyukovMPMCCycleQueue< cds::gc::HP, Foo,
79 typename cds::intrusive::vykov_queue::make_traits<
80 cds::opt::item_counter< cds::atomicity::item_counter >
85 Instead of saving copy of enqueued data, the intrusive implementation stores pointer to passed data.
89 #include <cds/intrusive/vyukov_mpmc_cycle_queue.h>
95 // Queue of Foo pointers, capacity is 1024, statically allocated buffer:
96 typedef cds::intrusive::VyukovMPMCCycleQueue< Foo,
97 typename cds::intrusive::vyukov_queue::make_traits<
98 cds::opt::buffer< cds::opt::v::static_buffer< Foo, 1024 > >
101 static_queue stQueue;
103 // Queue of Foo pointers, capacity is 1024, dynamically allocated buffer:
104 struct queue_traits: public cds::intrusive::vyukov_queue::traits
106 typedef cds::opt::v::dynamic_buffer< Foo > buffer;
108 typedef cds::intrusive::VyukovMPMCCycleQueue< Foo, queue_traits > dynamic_queue;
109 dynamic_queue dynQueue( 1024 );
112 template <typename T, typename Traits = vyukov_queue::traits >
113 class VyukovMPMCCycleQueue
114 : private container::VyukovMPMCCycleQueue< T*, Traits >
117 typedef container::VyukovMPMCCycleQueue< T*, Traits > base_class;
120 typedef T value_type; ///< type of data to be stored in the queue
121 typedef Traits traits; ///< Queue traits
122 typedef typename traits::item_counter item_counter; ///< Item counter type
123 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
124 typedef typename traits::disposer disposer; ///< Item disposer
127 /// Rebind template arguments
128 template <typename T2, typename Traits2>
130 typedef VyukovMPMCCycleQueue< T2, Traits2> other ; ///< Rebinding result
134 /// Constructs the queue of capacity \p nCapacity
136 For \p cds::opt::v::static_buffer the \p nCapacity parameter is ignored.
138 VyukovMPMCCycleQueue( size_t nCapacity = 0 )
139 : base_class( nCapacity )
142 /// Enqueues \p data to queue
144 @note The intrusive queue stores pointer to \p data passed, not the copy of \p data.
146 bool enqueue( value_type& data )
148 return base_class::enqueue( &data );
151 /// Dequeues an item from queue
153 \p Traits::disposer is not called. You may manually delete the returned pointer.
155 If queue is empty, returns \p nullptr.
157 value_type * dequeue()
159 value_type * p = nullptr;
160 return base_class::dequeue( p ) ? p : nullptr;
163 /// Synonym for \p enqueue()
164 bool push( value_type& data )
166 return enqueue( data );
169 /// Synonym for \p dequeue()
175 /// Clears queue in lock-free manner.
177 \p f parameter is a functor to dispose removed items.
178 The interface of \p Disposer is:
181 void operator ()( T * val );
184 The disposer will be called immediately for each item.
186 template <typename Disposer>
187 void clear( Disposer f )
190 while ( (pv = pop()) != nullptr ) {
197 This function uses the disposer that is specified in \p Traits.
204 /// Checks if the queue is empty
207 return base_class::empty();
210 /// Returns queue's item count
212 The value returned depends on \p vyukov_queue::traits::item_counter option.
213 For \p atomicity::empty_item_counter, this function always returns 0.
217 return base_class::size();
220 /// Returns capacity of the queue
221 size_t capacity() const
223 return base_class::capacity();
226 }} // namespace cds::intrusive
228 #endif // #ifndef CDSLIB_INTRUSIVE_VYUKOV_MPMC_CYCLE_QUEUE_H