2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
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_INTRUSIVE_VYUKOV_MPMC_CYCLE_QUEUE_H
32 #define CDSLIB_INTRUSIVE_VYUKOV_MPMC_CYCLE_QUEUE_H
34 #include <cds/intrusive/details/base.h>
35 #include <cds/container/vyukov_mpmc_cycle_queue.h>
37 namespace cds { namespace intrusive {
39 /// VyukovMPMCCycleQueue related definitions
40 /** @ingroup cds_intrusive_helper
42 namespace vyukov_queue {
44 /// VyukovMPMCCycleQueue traits
45 struct traits : public cds::container::vyukov_queue::traits
47 /// The functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used only in \p clear()
48 typedef opt::v::empty_disposer disposer;
51 /// Metafunction converting option list to \p vyukov_queue::traits
53 Supported \p Options are:
54 - \p opt::buffer - an uninitialized buffer type for internal cyclic array. Possible types are:
55 \p opt::v::uninitialized_dynamic_buffer (the default), \p opt::v::uninitialized_static_buffer. The type of
56 element in the buffer is not important: it will be changed via \p rebind metafunction.
57 - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer.
58 This option is used only in \p clear() member function.
59 - \p opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter (item counting disabled)
60 To enable item counting use \p cds::atomicity::item_counter
61 - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
62 - \p opt::padding - padding for internal critical atomic data. Default is \p opt::cache_line_padding
63 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
64 or \p opt::v::sequential_consistent (sequentially consistent memory model).
66 Example: declare \p %VyukovMPMCCycleQueue with item counting and static internal buffer of size 1024:
68 typedef cds::intrusive::VyukovMPMCCycleQueue< Foo,
69 typename cds::intrusive::vyukov_queue::make_traits<
70 cds::opt::buffer< cds::opt::v::uninitialized_static_buffer< void *, 1024 >,
71 cds::opt::item_counter< cds::atomicity::item_counter >
76 template <typename... Options>
78 # ifdef CDS_DOXYGEN_INVOKED
79 typedef implementation_defined type; ///< Metafunction result
81 typedef typename cds::opt::make_options<
82 typename cds::opt::find_type_traits< traits, Options... >::type
88 } // namespace vyukov_queue
90 /// Vyukov's MPMC bounded queue
91 /** @ingroup cds_intrusive_queue
92 This algorithm is developed by Dmitry Vyukov (see http://www.1024cores.net)
94 Implementation of intrusive version is based on container::VyukovMPMCCycleQueue.
97 - \p T - type stored in queue.
98 - \p Traits - queue traits, default is \p vyukov_queue::traits. You can use \p vyukov_queue::make_traits
99 metafunction to make your traits or just derive your traits from \p %vyukov_queue::traits:
101 struct myTraits: public cds::intrusive::vyukov_queue::traits {
102 typedef cds::atomicity::item_counter item_counter;
104 typedef cds::intrusive::VyukovMPMCCycleQueue< Foo, myTraits > myQueue;
106 // Equivalent make_traits example:
107 typedef cds::intrusive::VyukovMPMCCycleQueue< cds::gc::HP, Foo,
108 typename cds::intrusive::vyukov_queue::make_traits<
109 cds::opt::item_counter< cds::atomicity::item_counter >
114 Instead of saving copy of enqueued data, the intrusive implementation stores pointer to passed data.
118 #include <cds/intrusive/vyukov_mpmc_cycle_queue.h>
124 // Queue of Foo pointers, capacity is 1024, statically allocated buffer:
125 typedef cds::intrusive::VyukovMPMCCycleQueue< Foo,
126 typename cds::intrusive::vyukov_queue::make_traits<
127 cds::opt::buffer< cds::opt::v::uninitialized_static_buffer< Foo, 1024 > >
130 static_queue stQueue;
132 // Queue of Foo pointers, capacity is 1024, dynamically allocated buffer:
133 struct queue_traits: public cds::intrusive::vyukov_queue::traits
135 typedef cds::opt::v::uninitialized_dynamic_buffer< Foo > buffer;
137 typedef cds::intrusive::VyukovMPMCCycleQueue< Foo, queue_traits > dynamic_queue;
138 dynamic_queue dynQueue( 1024 );
141 template <typename T, typename Traits = vyukov_queue::traits >
142 class VyukovMPMCCycleQueue
143 : private container::VyukovMPMCCycleQueue< T*, Traits >
146 typedef container::VyukovMPMCCycleQueue< T*, Traits > base_class;
149 typedef T value_type; ///< type of data to be stored in the queue
150 typedef Traits traits; ///< Queue traits
151 typedef typename traits::item_counter item_counter; ///< Item counter type
152 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
153 typedef typename traits::disposer disposer; ///< Item disposer
154 typedef typename traits::back_off back_off; ///< back-off strategy
157 /// Rebind template arguments
158 template <typename T2, typename Traits2>
160 typedef VyukovMPMCCycleQueue< T2, Traits2> other ; ///< Rebinding result
164 /// Constructs the queue of capacity \p nCapacity
166 For \p cds::opt::v::uninitialized_static_buffer the \p nCapacity parameter is ignored.
168 VyukovMPMCCycleQueue( size_t nCapacity = 0 )
169 : base_class( nCapacity )
172 /// Enqueues \p data to queue
174 @note The intrusive queue stores pointer to \p data passed, not the copy of \p data.
176 bool enqueue( value_type& data )
178 return base_class::enqueue( &data );
181 /// Dequeues an item from queue
183 \p Traits::disposer is not called. You may manually delete the returned pointer.
185 If queue is empty, returns \p nullptr.
187 value_type * dequeue()
189 value_type * p = nullptr;
190 return base_class::dequeue( p ) ? p : nullptr;
193 /// Synonym for \p enqueue()
194 bool push( value_type& data )
196 return enqueue( data );
199 /// Synonym for \p dequeue()
205 /// Clears queue in lock-free manner.
207 \p f parameter is a functor to dispose removed items.
208 The interface of \p Disposer is:
211 void operator ()( T * val );
214 The disposer will be called immediately for each item.
216 template <typename Disposer>
217 void clear( Disposer f )
220 while ( (pv = pop()) != nullptr ) {
227 This function uses the disposer that is specified in \p Traits.
234 /// Checks if the queue is empty
237 return base_class::empty();
240 /// Returns queue's item count
242 The value returned depends on \p vyukov_queue::traits::item_counter option.
243 For \p atomicity::empty_item_counter, this function always returns 0.
247 return base_class::size();
250 /// Returns capacity of the queue
251 size_t capacity() const
253 return base_class::capacity();
256 }} // namespace cds::intrusive
258 #endif // #ifndef CDSLIB_INTRUSIVE_VYUKOV_MPMC_CYCLE_QUEUE_H