3 #ifndef __CDS_CONTAINER_TSIGAS_CYCLE_QUEUE_H
4 #define __CDS_CONTAINER_TSIGAS_CYCLE_QUEUE_H
7 #include <cds/intrusive/tsigas_cycle_queue.h>
8 #include <cds/container/details/base.h>
10 namespace cds { namespace container {
12 /// TsigasCycleQueue related definitions
13 /** @ingroup cds_nonintrusive_helper
15 namespace tsigas_queue {
17 /// TsigasCycleQueue default traits
20 /// Buffer type for cyclic array
22 The type of element for the buffer is not important: the queue rebinds
23 buffer for required type via \p rebind metafunction.
25 For \p TsigasCycleQueue queue the buffer size should have power-of-2 size.
27 typedef cds::opt::v::dynamic_buffer< void * > buffer;
30 typedef CDS_DEFAULT_ALLOCATOR allocator;
33 typedef cds::backoff::empty back_off;
35 /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
36 typedef atomicity::empty_item_counter item_counter;
38 /// C++ memory ordering model
40 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
41 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
43 typedef opt::v::relaxed_ordering memory_model;
45 /// Alignment for internal queue data. Default is \p opt::cache_line_alignment
46 enum { alignment = opt::cache_line_alignment };
49 /// Metafunction converting option list to \p tsigas_queue::traits
51 Supported \p Options are:
52 - \p opt::buffer - the buffer type for internal cyclic array. Possible types are:
53 \p opt::v::dynamic_buffer (the default), \p opt::v::static_buffer. The type of
54 element in the buffer is not important: it will be changed via \p rebind metafunction.
55 - \p opt::allocator - allocator (like \p std::allocator) used for allocating queue items. Default is \ref CDS_DEFAULT_ALLOCATOR
56 - \p opt::back_off - back-off strategy used, default is \p cds::backoff::empty.
57 - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used
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::alignment - the alignment for internal queue data. Default is \p opt::cache_line_alignment
62 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
63 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
65 Example: declare \p %TsigasCycleQueue with item counting and static iternal buffer of size 1024:
67 typedef cds::container::TsigasCycleQueue< Foo,
68 typename cds::container::tsigas_queue::make_traits<
69 cds::opt::buffer< cds::opt::v::static_buffer< void *, 1024 >,
70 cds::opt::item_counte< cds::atomicity::item_counter >
75 template <typename... Options>
77 # ifdef CDS_DOXYGEN_INVOKED
78 typedef implementation_defined type; ///< Metafunction result
80 typedef typename cds::opt::make_options<
81 typename cds::opt::find_type_traits< traits, Options... >::type
87 } // namespace tsigas_queue
91 template <typename T, typename Traits>
92 struct make_tsigas_cycle_queue
95 typedef Traits traits;
97 typedef typename traits::allocator::template rebind<value_type>::other allocator_type;
98 typedef cds::details::Allocator< value_type, allocator_type > cxx_allocator;
100 struct node_deallocator
102 void operator ()( value_type * pNode )
104 cxx_allocator().Delete( pNode );
107 typedef node_deallocator node_disposer;
109 struct intrusive_traits: public traits
111 typedef node_deallocator disposer;
114 typedef intrusive::TsigasCycleQueue< value_type, intrusive_traits > type;
119 /// Non-blocking cyclic bounded queue
120 /** @ingroup cds_nonintrusive_queue
121 It is non-intrusive implementation of Tsigas & Zhang cyclic queue based on \p intrusive::TsigasCycleQueue.
124 - [2000] Philippas Tsigas, Yi Zhang "A Simple, Fast and Scalable Non-Blocking Concurrent FIFO Queue
125 for Shared Memory Multiprocessor Systems"
128 - \p T is a type stored in the queue.
129 - \p Traits - queue traits, default is \p tsigas_queue::traits. You can use \p tsigas_queue::make_traits
130 metafunction to make your traits or just derive your traits from \p %tsigas_queue::traits:
132 struct myTraits: public cds::container::tsigas_queue::traits {
133 typedef cds::atomicity::item_counter item_counter;
135 typedef cds::container::TsigasCycleQueue< Foo, myTraits > myQueue;
137 // Equivalent make_traits example:
138 typedef cds::container::TsigasCycleQueue< cds::gc::HP, Foo,
139 typename cds::container::tsigas_queue::make_traits<
140 cds::opt::item_counter< cds::atomicity::item_counter >
147 #include <cds/container/tsigas_cycle_queue.h>
153 // Queue of Foo, capacity is 1024, statically allocated buffer:
154 typedef cds::container::TsigasCycleQueue< Foo,
155 typename cds::container::tsigas_queue::make_traits<
156 cds::opt::buffer< cds::opt::v::static_buffer< Foo, 1024 > >
159 static_queue stQueue;
161 // Queue of Foo, capacity is 1024, dynamically allocated buffer:
162 typedef cds::container::TsigasCycleQueue< Foo
163 typename cds::container::tsigas_queue::make_traits<
164 cds::opt::buffer< cds::opt::v::dynamic_buffer< Foo > >
167 dynamic_queue dynQueue( 1024 );
170 template <typename T, typename Traits = tsigas_queue::traits>
171 class TsigasCycleQueue:
172 #ifdef CDS_DOXYGEN_INVOKED
173 intrusive::TsigasCycleQueue< T, Traits >
175 details::make_tsigas_cycle_queue< T, Traits >::type
179 typedef details::make_tsigas_cycle_queue< T, Traits > maker;
180 typedef typename maker::type base_class;
183 typedef T value_type ; ///< Value type stored in the stack
184 typedef Traits traits; ///< Queue traits
186 typedef typename traits::back_off back_off; ///< Back-off strategy used
187 typedef typename maker::allocator_type allocator_type; ///< Allocator type used for allocate/deallocate the items
188 typedef typename traits::item_counter item_counter; ///< Item counting policy used
189 typedef typename traits::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option
191 /// Rebind template arguments
192 template <typename T2, typename Traits2>
194 typedef TsigasCycleQueue< T2, Traits2> other ; ///< Rebinding result
199 typedef typename maker::cxx_allocator cxx_allocator;
200 typedef typename maker::node_deallocator node_deallocator; // deallocate node
201 typedef typename maker::node_disposer node_disposer;
206 static value_type * alloc_node()
208 return cxx_allocator().New();
210 static value_type * alloc_node( const value_type& val )
212 return cxx_allocator().New( val );
214 template <typename... Args>
215 static value_type * alloc_node_move( Args&&... args )
217 return cxx_allocator().MoveNew( std::forward<Args>( args )... );
219 static void free_node( value_type * p )
221 node_deallocator()( p );
224 struct node_disposer2 {
225 void operator()( value_type * pNode )
230 typedef std::unique_ptr< value_type, node_disposer2 > scoped_node_ptr;
234 /// Initialize empty queue of capacity \p nCapacity
236 If internal buffer type is \p cds::opt::v::static_buffer, the \p nCapacity parameter is ignored.
238 Note, the real capacity of queue is \p nCapacity - 2.
240 TsigasCycleQueue( size_t nCapacity = 0 )
241 : base_class( nCapacity )
244 /// Enqueues \p val value into the queue.
246 The function makes queue node in dynamic memory calling copy constructor for \p val
247 and then it calls \p intrusive::TsigasCycleQueue::enqueue.
249 Returns \p true if success, \p false if the queue is full.
251 bool enqueue( value_type const& val )
253 scoped_node_ptr p( alloc_node(val));
254 if ( base_class::enqueue( *p )) {
261 /// Enqueues data to the queue using a functor
263 \p Func is a functor called to create node.
264 The functor \p f takes one argument - a reference to a new node of type \ref value_type :
266 cds::container::TsigasCysleQueue< Foo > myQueue;
268 myQueue.enqueue_with( [&bar]( Foo& dest ) { dest = bar; } );
271 template <typename Func>
272 bool enqueue_with( Func f )
274 scoped_node_ptr p( alloc_node() );
276 if ( base_class::enqueue( *p )) {
283 /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
284 template <typename... Args>
285 bool emplace( Args&&... args )
287 scoped_node_ptr p ( alloc_node_move( std::forward<Args>(args)...));
288 if ( base_class::enqueue( *p)) {
295 /// Synonym for template version of \p enqueue() function
296 bool push( value_type const& data )
298 return enqueue( data );
301 /// Synonym for \p enqueue_with() function
302 template <typename Func>
303 bool push_with( Func f )
305 return enqueue_with( f );
309 /// Dequeues a value using a functor
311 \p Func is a functor called to copy dequeued value.
312 The functor takes one argument - a reference to removed node:
314 cds:container::TsigasCycleQueue< Foo > myQueue;
316 myQueue.dequeue_with( [&bar]( Foo& src ) { bar = std::move( src );});
318 The functor is called only if the queue is not empty.
320 template <typename Func>
321 bool dequeue_with( Func f )
323 value_type * p = base_class::dequeue();
332 /// Dequeues a value from the queue
334 If queue is not empty, the function returns \p true, \p dest contains copy of
335 dequeued value. The assignment operator for type \ref value_type is invoked.
336 If queue is empty, the function returns \p false, \p dest is unchanged.
338 bool dequeue( value_type& dest )
340 return dequeue_with( [&dest]( value_type& src ) { dest = src; } );
343 /// Synonym for \p dequeue() function
344 bool pop( value_type& dest )
346 return dequeue( dest );
349 /// Synonym for \p dequeue_with() function
350 template <typename Func>
351 bool pop_with( Func f )
353 return dequeue_with( f );
356 /// Checks if the queue is empty
359 return base_class::empty();
364 The function repeatedly calls \p dequeue() until it returns \p nullptr.
371 /// Returns queue's item count
372 /** \copydetails cds::intrusive::TsigasCycleQueue::size()
376 return base_class::size();
379 /// Returns capacity of cyclic buffer
380 size_t capacity() const
382 return base_class::capacity();
386 }} // namespace cds::intrusive
388 #endif // #ifndef __CDS_CONTAINER_TSIGAS_CYCLE_QUEUE_H