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_CONTAINER_TSIGAS_CYCLE_QUEUE_H
32 #define CDSLIB_CONTAINER_TSIGAS_CYCLE_QUEUE_H
35 #include <cds/intrusive/tsigas_cycle_queue.h>
36 #include <cds/container/details/base.h>
38 namespace cds { namespace container {
40 /// TsigasCycleQueue related definitions
41 /** @ingroup cds_nonintrusive_helper
43 namespace tsigas_queue {
45 /// TsigasCycleQueue default traits
48 /// Buffer type for cyclic array
50 The type of element for the buffer is not important: the queue rebinds
51 buffer for required type via \p rebind metafunction.
53 For \p TsigasCycleQueue queue the buffer size should have power-of-2 size.
55 You should use any initialized buffer type, see \p opt::buffer.
57 typedef cds::opt::v::initialized_dynamic_buffer< void * > buffer;
60 typedef CDS_DEFAULT_ALLOCATOR allocator;
63 typedef cds::backoff::empty back_off;
65 /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
66 typedef atomicity::empty_item_counter item_counter;
68 /// C++ memory ordering model
70 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
71 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
73 typedef opt::v::relaxed_ordering memory_model;
75 /// Padding for internal critical atomic data. Default is \p opt::cache_line_padding
76 enum { padding = opt::cache_line_padding };
79 /// Metafunction converting option list to \p tsigas_queue::traits
81 Supported \p Options are:
82 - \p opt::buffer - the buffer type for internal cyclic array. Possible types are:
83 \p opt::v::initialized_dynamic_buffer (the default), \p opt::v::initialized_static_buffer. The type of
84 element in the buffer is not important: it will be changed via \p rebind metafunction.
85 - \p opt::allocator - allocator (like \p std::allocator) used for allocating queue items. Default is \ref CDS_DEFAULT_ALLOCATOR
86 - \p opt::back_off - back-off strategy used, default is \p cds::backoff::empty.
87 - \p opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter (item counting disabled)
88 To enable item counting use \p cds::atomicity::item_counter
89 - \p opt::padding - padding for internal critical atomic data. Default is \p opt::cache_line_padding
90 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
91 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
93 Example: declare \p %TsigasCycleQueue with item counting and static iternal buffer of size 1024:
95 typedef cds::container::TsigasCycleQueue< Foo,
96 typename cds::container::tsigas_queue::make_traits<
97 cds::opt::buffer< cds::opt::v::initialized_static_buffer< void *, 1024 >,
98 cds::opt::item_counter< cds::atomicity::item_counter >
103 template <typename... Options>
105 # ifdef CDS_DOXYGEN_INVOKED
106 typedef implementation_defined type; ///< Metafunction result
108 typedef typename cds::opt::make_options<
109 typename cds::opt::find_type_traits< traits, Options... >::type
115 } // namespace tsigas_queue
119 template <typename T, typename Traits>
120 struct make_tsigas_cycle_queue
122 typedef T value_type;
123 typedef Traits traits;
125 typedef typename traits::allocator::template rebind<value_type>::other allocator_type;
126 typedef cds::details::Allocator< value_type, allocator_type > cxx_allocator;
128 struct node_deallocator
130 void operator ()( value_type * pNode )
132 cxx_allocator().Delete( pNode );
135 typedef node_deallocator node_disposer;
137 struct intrusive_traits: public traits
139 typedef node_deallocator disposer;
142 typedef intrusive::TsigasCycleQueue< value_type, intrusive_traits > type;
147 /// Non-blocking cyclic bounded queue
148 /** @ingroup cds_nonintrusive_queue
149 It is non-intrusive implementation of Tsigas & Zhang cyclic queue based on \p intrusive::TsigasCycleQueue.
152 - [2000] Philippas Tsigas, Yi Zhang "A Simple, Fast and Scalable Non-Blocking Concurrent FIFO Queue
153 for Shared Memory Multiprocessor Systems"
156 - \p T is a type stored in the queue.
157 - \p Traits - queue traits, default is \p tsigas_queue::traits. You can use \p tsigas_queue::make_traits
158 metafunction to make your traits or just derive your traits from \p %tsigas_queue::traits:
160 struct myTraits: public cds::container::tsigas_queue::traits {
161 typedef cds::atomicity::item_counter item_counter;
163 typedef cds::container::TsigasCycleQueue< Foo, myTraits > myQueue;
165 // Equivalent make_traits example:
166 typedef cds::container::TsigasCycleQueue< cds::gc::HP, Foo,
167 typename cds::container::tsigas_queue::make_traits<
168 cds::opt::item_counter< cds::atomicity::item_counter >
175 #include <cds/container/tsigas_cycle_queue.h>
181 // Queue of Foo, capacity is 1024, statically allocated buffer:
182 typedef cds::container::TsigasCycleQueue< Foo,
183 typename cds::container::tsigas_queue::make_traits<
184 cds::opt::buffer< cds::opt::v::initialized_static_buffer< Foo, 1024 > >
187 static_queue stQueue;
189 // Queue of Foo, capacity is 1024, dynamically allocated buffer:
190 typedef cds::container::TsigasCycleQueue< Foo
191 typename cds::container::tsigas_queue::make_traits<
192 cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer< Foo > >
195 dynamic_queue dynQueue( 1024 );
198 template <typename T, typename Traits = tsigas_queue::traits>
199 class TsigasCycleQueue:
200 #ifdef CDS_DOXYGEN_INVOKED
201 intrusive::TsigasCycleQueue< T, Traits >
203 details::make_tsigas_cycle_queue< T, Traits >::type
207 typedef details::make_tsigas_cycle_queue< T, Traits > maker;
208 typedef typename maker::type base_class;
211 typedef T value_type ; ///< Value type stored in the stack
212 typedef Traits traits; ///< Queue traits
214 typedef typename traits::back_off back_off; ///< Back-off strategy used
215 typedef typename maker::allocator_type allocator_type; ///< Allocator type used for allocate/deallocate the items
216 typedef typename traits::item_counter item_counter; ///< Item counting policy used
217 typedef typename traits::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option
219 /// Rebind template arguments
220 template <typename T2, typename Traits2>
222 typedef TsigasCycleQueue< T2, Traits2> other ; ///< Rebinding result
227 typedef typename maker::cxx_allocator cxx_allocator;
228 typedef typename maker::node_deallocator node_deallocator; // deallocate node
229 typedef typename maker::node_disposer node_disposer;
234 static value_type * alloc_node()
236 return cxx_allocator().New();
238 static value_type * alloc_node( const value_type& val )
240 return cxx_allocator().New( val );
242 template <typename... Args>
243 static value_type * alloc_node_move( Args&&... args )
245 return cxx_allocator().MoveNew( std::forward<Args>( args )... );
247 static void free_node( value_type * p )
249 node_deallocator()( p );
252 struct node_disposer2 {
253 void operator()( value_type * pNode )
258 typedef std::unique_ptr< value_type, node_disposer2 > scoped_node_ptr;
262 /// Initialize empty queue of capacity \p nCapacity
264 If internal buffer type is \p cds::opt::v::initialized_static_buffer, the \p nCapacity parameter is ignored.
266 Note, the real capacity of queue is \p nCapacity - 2.
268 TsigasCycleQueue( size_t nCapacity = 0 )
269 : base_class( nCapacity )
272 /// Enqueues \p val value into the queue.
274 The function makes queue node in dynamic memory calling copy constructor for \p val
275 and then it calls \p intrusive::TsigasCycleQueue::enqueue.
277 Returns \p true if success, \p false if the queue is full.
279 bool enqueue( value_type const& val )
281 scoped_node_ptr p( alloc_node(val));
282 if ( base_class::enqueue( *p )) {
289 /// Enqueues \p val value into the queue, move semantics
290 bool enqueue( value_type&& val )
292 scoped_node_ptr p( alloc_node_move( std::move( val )));
293 if ( base_class::enqueue( *p ) ) {
300 /// Enqueues data to the queue using a functor
302 \p Func is a functor called to create node.
303 The functor \p f takes one argument - a reference to a new node of type \ref value_type :
305 cds::container::TsigasCysleQueue< Foo > myQueue;
307 myQueue.enqueue_with( [&bar]( Foo& dest ) { dest = bar; } );
310 template <typename Func>
311 bool enqueue_with( Func f )
313 scoped_node_ptr p( alloc_node() );
315 if ( base_class::enqueue( *p )) {
322 /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
323 template <typename... Args>
324 bool emplace( Args&&... args )
326 scoped_node_ptr p ( alloc_node_move( std::forward<Args>(args)...));
327 if ( base_class::enqueue( *p)) {
334 /// Synonym for \p enqueue( value_type const& )
335 bool push( value_type const& data )
337 return enqueue( data );
340 /// Synonym for \p enqueue( value_type&& )
341 bool push( value_type&& data )
343 return enqueue( std::move( data ));
346 /// Synonym for \p enqueue_with() function
347 template <typename Func>
348 bool push_with( Func f )
350 return enqueue_with( f );
353 /// Dequeues a value using a functor
355 \p Func is a functor called to copy dequeued value.
356 The functor takes one argument - a reference to removed node:
358 cds:container::TsigasCycleQueue< Foo > myQueue;
360 myQueue.dequeue_with( [&bar]( Foo& src ) { bar = std::move( src );});
362 The functor is called only if the queue is not empty.
364 template <typename Func>
365 bool dequeue_with( Func f )
367 value_type * p = base_class::dequeue();
376 /// Dequeues a value from the queue
378 If queue is not empty, the function returns \p true, \p dest contains copy of
379 dequeued value. The assignment operator for type \ref value_type is invoked.
380 If queue is empty, the function returns \p false, \p dest is unchanged.
382 bool dequeue( value_type& dest )
384 return dequeue_with( [&dest]( value_type& src ) { dest = std::move( src );});
387 /// Synonym for \p dequeue() function
388 bool pop( value_type& dest )
390 return dequeue( dest );
393 /// Synonym for \p dequeue_with() function
394 template <typename Func>
395 bool pop_with( Func f )
397 return dequeue_with( f );
400 /// Checks if the queue is empty
403 return base_class::empty();
408 The function repeatedly calls \p dequeue() until it returns \p nullptr.
415 /// Returns queue's item count
416 /** \copydetails cds::intrusive::TsigasCycleQueue::size()
420 return base_class::size();
423 /// Returns capacity of cyclic buffer
424 size_t capacity() const
426 return base_class::capacity();
430 }} // namespace cds::intrusive
432 #endif // #ifndef CDSLIB_CONTAINER_TSIGAS_CYCLE_QUEUE_H