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/base.h>
9 #include <cds/details/trivial_assign.h>
11 namespace cds { namespace container {
15 template <typename T, typename... Options>
16 struct make_tsigas_cycle_queue
20 struct default_options {
21 typedef cds::backoff::empty back_off;
22 typedef CDS_DEFAULT_ALLOCATOR allocator;
23 typedef atomicity::empty_item_counter item_counter;
24 typedef opt::v::relaxed_ordering memory_model;
25 enum { alignment = opt::cache_line_alignment };
28 typedef typename opt::make_options<
29 typename cds::opt::find_type_traits< default_options, Options... >::type
33 typedef typename options::allocator::template rebind<value_type>::other allocator_type;
34 typedef cds::details::Allocator< value_type, allocator_type > cxx_allocator;
36 struct node_deallocator
38 void operator ()( value_type * pNode )
40 cxx_allocator().Delete( pNode );
43 typedef node_deallocator node_disposer;
45 typedef intrusive::TsigasCycleQueue<
47 ,opt::buffer< typename options::buffer >
48 ,opt::back_off< typename options::back_off >
49 ,intrusive::opt::disposer< node_disposer >
50 ,opt::item_counter< typename options::item_counter >
51 ,opt::alignment< options::alignment >
52 ,opt::memory_model< typename options::memory_model >
59 /// Non-blocking cyclic queue discovered by Philippas Tsigas and Yi Zhang
60 /** @ingroup cds_nonintrusive_queue
61 It is non-intrusive implementation of Tsigas & Zhang cyclic queue based on intrusive::TsigasCycleQueue.
64 \li [2000] Philippas Tsigas, Yi Zhang "A Simple, Fast and Scalable Non-Blocking Concurrent FIFO Queue
65 for Shared Memory Multiprocessor Systems"
67 \p T is a type stored in the queue. It should be default-constructible, copy-constructible, assignable type.
70 - opt::buffer - buffer to store items. Mandatory option, see option description for full list of possible types.
71 - opt::allocator - allocator (like \p std::allocator). Default is \ref CDS_DEFAULT_ALLOCATOR
72 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter
73 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used.
74 - opt::alignment - the alignment for internal queue data. Default is opt::cache_line_alignment
75 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
76 or opt::v::sequential_consistent (sequentially consisnent memory model).
80 #include <cds/container/tsigas_cycle_queue.h>
86 // Queue of Foo, capacity is 1024, statically allocated buffer:
87 typedef cds::intrusive::TsigasCycleQueue<
89 ,cds::opt::buffer< cds::opt::v::static_buffer< Foo, 1024 > >
93 // Queue of Foo, capacity is 1024, dynamically allocated buffer:
94 typedef cds::intrusive::TsigasCycleQueue<
96 ,cds::opt::buffer< cds::opt::v::dynamic_buffer< Foo > >
98 dynamic_queue dynQueue( 1024 );
101 template <typename T, typename... Options>
102 class TsigasCycleQueue:
103 #ifdef CDS_DOXYGEN_INVOKED
104 intrusive::TsigasCycleQueue< T, Options... >
106 details::make_tsigas_cycle_queue< T, Options... >::type
110 typedef details::make_tsigas_cycle_queue< T, Options... > options;
111 typedef typename options::type base_class;
114 typedef T value_type ; ///< Value type stored in the stack
116 typedef typename base_class::back_off back_off ; ///< Back-off strategy used
117 typedef typename options::allocator_type allocator_type ; ///< Allocator type used for allocate/deallocate the nodes
118 typedef typename options::options::item_counter item_counter ; ///< Item counting policy used
119 typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
121 /// Rebind template arguments
122 template <typename T2, typename... Options2>
124 typedef TsigasCycleQueue< T2, Options2...> other ; ///< Rebinding result
129 typedef typename options::cxx_allocator cxx_allocator;
130 typedef typename options::node_deallocator node_deallocator; // deallocate node
131 typedef typename options::node_disposer node_disposer;
136 static value_type * alloc_node()
138 return cxx_allocator().New();
140 static value_type * alloc_node( const value_type& val )
142 return cxx_allocator().New( val );
144 template <typename... Args>
145 static value_type * alloc_node_move( Args&&... args )
147 return cxx_allocator().MoveNew( std::forward<Args>( args )... );
149 static void free_node( value_type * p )
151 node_deallocator()( p );
154 struct node_disposer2 {
155 void operator()( value_type * pNode )
160 typedef std::unique_ptr< value_type, node_disposer2 > scoped_node_ptr;
164 /// Initialize empty queue of capacity \p nCapacity
166 For cds::opt::v::static_buffer the \p nCapacity parameter is ignored.
168 Note that the real capacity of queue is \p nCapacity - 2.
170 TsigasCycleQueue( size_t nCapacity = 0 )
171 : base_class( nCapacity )
174 /// Returns queue's item count (see \ref intrusive::TsigasCycleQueue::size for explanation)
177 return base_class::size();
180 /// Returns capacity of cyclic buffer
182 Warning: real capacity of queue is two less than returned value of this function.
184 size_t capacity() const
186 return base_class::capacity();
189 /// Enqueues \p val value into the queue.
191 The function makes queue node in dynamic memory calling copy constructor for \p val
192 and then it calls intrusive::TsigasCycleQueue::enqueue.
193 Returns \p true if success, \p false otherwise.
195 bool enqueue( value_type const& val )
197 scoped_node_ptr p( alloc_node(val));
198 if ( base_class::enqueue( *p )) {
205 /// Enqueues \p data to queue using copy functor
207 \p Func is a functor called to copy value \p data of type \p Type
208 which may be differ from type \p T stored in the queue.
209 The functor's interface is:
212 void operator()(T& dest, SOURCE const& data)
214 // // Code to copy \p data to \p dest
219 You may use \p boost:ref construction to pass functor \p f by reference.
221 <b>Requirements</b> The functor \p Func should not throw any exception.
223 template <typename Type, typename Func>
224 bool enqueue( const Type& data, Func f )
226 scoped_node_ptr p( alloc_node());
227 unref(f)( *p, data );
228 if ( base_class::enqueue( *p )) {
235 /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
236 template <typename... Args>
237 bool emplace( Args&&... args )
239 scoped_node_ptr p ( alloc_node_move( std::forward<Args>(args)...));
240 if ( base_class::enqueue( *p)) {
247 /// Dequeues a value using copy functor
249 \p Func is a functor called to copy dequeued value to \p dest of type \p Type
250 which may be differ from type \p T stored in the queue.
251 The functor's interface is:
254 void operator()(Type& dest, T const& data)
256 // // Code to copy \p data to \p dest
261 You may use \p boost:ref construction to pass functor \p f by reference.
263 <b>Requirements</b> The functor \p Func should not throw any exception.
265 template <typename Type, typename Func>
266 bool dequeue( Type& dest, Func f )
268 value_type * p = base_class::dequeue();
270 unref(f)( dest, *p );
271 node_disposer()( p );
277 /// Dequeues a value from the queue
279 If queue is not empty, the function returns \p true, \p dest contains copy of
280 dequeued value. The assignment operator for type \ref value_type is invoked.
281 If queue is empty, the function returns \p false, \p dest is unchanged.
283 bool dequeue( value_type& dest )
285 typedef cds::details::trivial_assign<value_type, value_type> functor;
286 return dequeue( dest, functor() );
289 /// Synonym for \ref enqueue function
290 bool push( const value_type& val )
292 return enqueue( val );
295 /// Synonym for template version of \ref enqueue function
296 template <typename Type, typename Func>
297 bool push( const Type& data, Func f )
299 return enqueue( data, f );
302 /// Synonym for \ref dequeue function
303 bool pop( value_type& dest )
305 return dequeue( dest );
308 /// Synonym for template version of \ref dequeue function
309 template <typename Type, typename Func>
310 bool pop( Type& dest, Func f )
312 return dequeue( dest, f );
315 /// Checks if the queue is empty
318 return base_class::empty();
323 The function repeatedly calls \ref dequeue until it returns \p nullptr.
331 }} // namespace cds::intrusive
333 #endif // #ifndef __CDS_CONTAINER_TSIGAS_CYCLE_QUEUE_H