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, CDS_DECL_OPTIONS7>
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, CDS_OPTIONS7 >::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, CDS_DECL_OPTIONS7>
102 class TsigasCycleQueue:
103 #ifdef CDS_DOXYGEN_INVOKED
104 intrusive::TsigasCycleQueue< T, Options... >
106 details::make_tsigas_cycle_queue< T, CDS_OPTIONS7 >::type
110 typedef details::make_tsigas_cycle_queue< T, CDS_OPTIONS7 > 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, CDS_DECL_OTHER_OPTIONS7>
124 typedef TsigasCycleQueue< T2, CDS_OTHER_OPTIONS7> 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 # ifdef CDS_EMPLACE_SUPPORT
145 template <typename... Args>
146 static value_type * alloc_node_move( Args&&... args )
148 return cxx_allocator().MoveNew( std::forward<Args>( args )... );
151 static void free_node( value_type * p )
153 node_deallocator()( p );
156 struct node_disposer2 {
157 void operator()( value_type * pNode )
162 typedef std::unique_ptr< value_type, node_disposer2 > scoped_node_ptr;
166 /// Initialize empty queue of capacity \p nCapacity
168 For cds::opt::v::static_buffer the \p nCapacity parameter is ignored.
170 Note that the real capacity of queue is \p nCapacity - 2.
172 TsigasCycleQueue( size_t nCapacity = 0 )
173 : base_class( nCapacity )
176 /// Returns queue's item count (see \ref intrusive::TsigasCycleQueue::size for explanation)
179 return base_class::size();
182 /// Returns capacity of cyclic buffer
184 Warning: real capacity of queue is two less than returned value of this function.
186 size_t capacity() const
188 return base_class::capacity();
191 /// Enqueues \p val value into the queue.
193 The function makes queue node in dynamic memory calling copy constructor for \p val
194 and then it calls intrusive::TsigasCycleQueue::enqueue.
195 Returns \p true if success, \p false otherwise.
197 bool enqueue( value_type const& val )
199 scoped_node_ptr p( alloc_node(val));
200 if ( base_class::enqueue( *p )) {
207 /// Enqueues \p data to queue using copy functor
209 \p Func is a functor called to copy value \p data of type \p Type
210 which may be differ from type \p T stored in the queue.
211 The functor's interface is:
214 void operator()(T& dest, SOURCE const& data)
216 // // Code to copy \p data to \p dest
221 You may use \p boost:ref construction to pass functor \p f by reference.
223 <b>Requirements</b> The functor \p Func should not throw any exception.
225 template <typename Type, typename Func>
226 bool enqueue( const Type& data, Func f )
228 scoped_node_ptr p( alloc_node());
229 unref(f)( *p, data );
230 if ( base_class::enqueue( *p )) {
237 # ifdef CDS_EMPLACE_SUPPORT
238 /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
240 This function is available only for compiler that supports
241 variadic template and move semantics
243 template <typename... Args>
244 bool emplace( Args&&... args )
246 scoped_node_ptr p ( alloc_node_move( std::forward<Args>(args)...));
247 if ( base_class::enqueue( *p)) {
255 /// Dequeues a value using copy functor
257 \p Func is a functor called to copy dequeued value to \p dest of type \p Type
258 which may be differ from type \p T stored in the queue.
259 The functor's interface is:
262 void operator()(Type& dest, T const& data)
264 // // Code to copy \p data to \p dest
269 You may use \p boost:ref construction to pass functor \p f by reference.
271 <b>Requirements</b> The functor \p Func should not throw any exception.
273 template <typename Type, typename Func>
274 bool dequeue( Type& dest, Func f )
276 value_type * p = base_class::dequeue();
278 unref(f)( dest, *p );
279 node_disposer()( p );
285 /// Dequeues a value from the queue
287 If queue is not empty, the function returns \p true, \p dest contains copy of
288 dequeued value. The assignment operator for type \ref value_type is invoked.
289 If queue is empty, the function returns \p false, \p dest is unchanged.
291 bool dequeue( value_type& dest )
293 typedef cds::details::trivial_assign<value_type, value_type> functor;
294 return dequeue( dest, functor() );
297 /// Synonym for \ref enqueue function
298 bool push( const value_type& val )
300 return enqueue( val );
303 /// Synonym for template version of \ref enqueue function
304 template <typename Type, typename Func>
305 bool push( const Type& data, Func f )
307 return enqueue( data, f );
310 /// Synonym for \ref dequeue function
311 bool pop( value_type& dest )
313 return dequeue( dest );
316 /// Synonym for template version of \ref dequeue function
317 template <typename Type, typename Func>
318 bool pop( Type& dest, Func f )
320 return dequeue( dest, f );
323 /// Checks if the queue is empty
326 return base_class::empty();
331 The function repeatedly calls \ref dequeue until it returns \p nullptr.
339 }} // namespace cds::intrusive
341 #endif // #ifndef __CDS_CONTAINER_TSIGAS_CYCLE_QUEUE_H