3 #ifndef __CDS_CONTAINER_BASKET_QUEUE_H
4 #define __CDS_CONTAINER_BASKET_QUEUE_H
7 #include <cds/intrusive/basket_queue.h>
8 #include <cds/container/details/base.h>
9 //#include <cds/details/trivial_assign.h>
11 namespace cds { namespace container {
13 /// BasketQueue related definitions
14 /** @ingroup cds_nonintrusive_helper
16 namespace basket_queue {
18 /// Internal statistics
19 template <typename Counter = cds::intrusive::basket_queue::stat<>::counter_type >
20 using stat = cds::intrusive::basket_queue::stat< Counter >;
22 /// Dummy internal statistics
23 typedef cds::intrusive::basket_queue::empty_stat empty_stat;
25 /// BasketQueue default type traits
29 typedef CDS_DEFAULT_ALLOCATOR allocator;
32 typedef cds::backoff::empty back_off;
34 /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
35 typedef atomicity::empty_item_counter item_counter;
37 /// Internal statistics (by default, disabled)
39 Possible option value are: \p basket_queue::stat, \p basket_queue::empty_stat (the default),
40 user-provided class that supports \p %basket_queue::stat interface.
42 typedef basket_queue::empty_stat stat;
44 /// C++ memory ordering model
46 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
47 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
49 typedef opt::v::relaxed_ordering memory_model;
51 /// Alignment of internal queue data. Default is \p opt::cache_line_alignment
52 enum { alignment = opt::cache_line_alignment };
55 /// Metafunction converting option list to \p basket_queue::traits
57 Supported \p Options are:
58 - opt::allocator - allocator (like \p std::allocator) used for allocating queue nodes. Default is \ref CDS_DEFAULT_ALLOCATOR
59 - opt::back_off - back-off strategy used, default is \p cds::backoff::empty.
60 - opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter (item counting disabled)
61 To enable item counting use \p cds::atomicity::item_counter
62 - opt::stat - the type to gather internal statistics.
63 Possible statistics types are: \p basket_queue::stat, \p basket_queue::empty_stat, user-provided class that supports \p %basket_queue::stat interface.
64 Default is \p %basket_queue::empty_stat.
65 - opt::alignment - the alignment for internal queue data. Default is \p opt::cache_line_alignment
66 - opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
67 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
69 Example: declare \p %BasketQueue with item counting and internal statistics
71 typedef cds::container::BasketQueue< cds::gc::HP, Foo,
72 typename cds::container::basket_queue::make_traits<
73 cds::opt::item_counte< cds::atomicity::item_counter >,
74 cds::opt::stat< cds::intrusive::basket_queue::stat<> >
79 template <typename... Options>
81 # ifdef CDS_DOXYGEN_INVOKED
82 typedef implementation_defined type; ///< Metafunction result
84 typedef typename cds::opt::make_options<
85 typename cds::opt::find_type_traits< traits, Options... >::type
90 } // namespace basket_queue
94 template <typename GC, typename T, typename Traits>
95 struct make_basket_queue
99 typedef Traits traits;
101 struct node_type: public intrusive::basket_queue::node< gc >
105 node_type( const value_type& val )
108 template <typename... Args>
109 node_type( Args&&... args )
110 : m_value( std::forward<Args>(args)...)
114 typedef typename traits::allocator::template rebind<node_type>::other allocator_type;
115 typedef cds::details::Allocator< node_type, allocator_type > cxx_allocator;
117 struct node_deallocator
119 void operator ()( node_type * pNode )
121 cxx_allocator().Delete( pNode );
125 struct intrusive_traits : public traits
127 typedef intrusive::basket_queue::base_hook< opt::gc<gc> > hook;
128 typedef node_deallocator disposer;
131 typedef cds::intrusive::BasketQueue< gc, node_type, intrusive_traits > type;
136 /// Basket lock-free queue (non-intrusive variant)
137 /** @ingroup cds_nonintrusive_queue
138 It is non-intrusive version of basket queue algorithm based on intrusive::BasketQueue counterpart.
141 [2007] Moshe Hoffman, Ori Shalev, Nir Shavit "The Baskets Queue"
145 In the
\93basket
\94 approach, instead of
146 the traditional ordered list of nodes, the queue consists of an ordered list of groups
147 of nodes (logical baskets). The order of nodes in each basket need not be specified, and in
148 fact, it is easiest to maintain them in LIFO order. The baskets fulfill the following basic
150 - Each basket has a time interval in which all its nodes
\92 enqueue operations overlap.
151 - The baskets are ordered by the order of their respective time intervals.
152 - For each basket, its nodes
\92 dequeue operations occur after its time interval.
153 - The dequeue operations are performed according to the order of baskets.
155 Two properties define the FIFO order of nodes:
156 - The order of nodes in a basket is not specified.
157 - The order of nodes in different baskets is the FIFO-order of their respective baskets.
159 In algorithms such as the MS-queue or optimistic
160 queue, threads enqueue items by applying a Compare-and-swap (CAS) operation to the
161 queue
\92s tail pointer, and all the threads that fail on a particular CAS operation (and also
162 the winner of that CAS) overlap in time. In particular, they share the time interval of
163 the CAS operation itself. Hence, all the threads that fail to CAS on the tail-node of
164 the queue may be inserted into the same basket. By integrating the basket-mechanism
165 as the back-off mechanism, the time usually spent on backing-off before trying to link
166 onto the new tail, can now be utilized to insert the failed operations into the basket,
167 allowing enqueues to complete sooner. In the meantime, the next successful CAS operations
168 by enqueues allow new baskets to be formed down the list, and these can be
169 filled concurrently. Moreover, the failed operations don
\92t retry their link attempt on the
170 new tail, lowering the overall contention on it. This leads to a queue
171 algorithm that unlike all former concurrent queue algorithms requires virtually no tuning
172 of the backoff mechanisms to reduce contention, making the algorithm an attractive
173 out-of-the-box queue.
175 In order to enqueue, just as in MSQueue, a thread first tries to link the new node to
176 the last node. If it failed to do so, then another thread has already succeeded. Thus it
177 tries to insert the new node into the new basket that was created by the winner thread.
178 To dequeue a node, a thread first reads the head of the queue to obtain the
179 oldest basket. It may then dequeue any node in the oldest basket.
183 - \p GC - garbage collector type: \p gc::HP, \p gc::DHP
184 - \p T - type of value to be stored in the queue
185 - \p Traits - queue traits, default is \p basket_queue::traits. You can use \p basket_queue::make_traits
186 metafunction to make your traits or just derive your traits from \p %basket_queue::traits:
188 struct myTraits: public cds::container::basket_queue::traits {
189 typedef cds::intrusive::basket_queue::stat<> stat;
190 typedef cds::atomicity::item_counter item_counter;
192 typedef cds::container::BasketQueue< cds::gc::HP, Foo, myTraits > myQueue;
194 // Equivalent make_traits example:
195 typedef cds::container::BasketQueue< cds::gc::HP, Foo,
196 typename cds::container::basket_queue::make_traits<
197 cds::opt::stat< cds::container::basket_queue::stat<> >,
198 cds::opt::item_counter< cds::atomicity::item_counter >
203 template <typename GC, typename T, typename Traits = basket_queue::traits >
205 #ifdef CDS_DOXYGEN_INVOKED
206 private intrusive::BasketQueue< GC, intrusive::basket_queue::node< T >, Traits >
208 protected details::make_basket_queue< GC, T, Traits >::type
212 typedef details::make_basket_queue< GC, T, Options... > maker;
213 typedef typename maker::type base_class;
217 /// Rebind template arguments
218 template <typename GC2, typename T2, typename Traits2>
220 typedef BasketQueue< GC2, T2, Traits2> other ; ///< Rebinding result
224 typedef GC gc; ///< Garbage collector
225 typedef T value_type; ///< Type of value to be stored in the queue
226 typedef Traits traits; ///< Queue's traits
228 typedef typename base_class::back_off back_off; ///< Back-off strategy used
229 typedef typename maker::allocator_type allocator_type; ///< Allocator type used for allocate/deallocate the nodes
230 typedef typename base_class::item_counter item_counter; ///< Item counting policy used
231 typedef typename base_class::stat stat; ///< Internal statistics policy used
232 typedef typename base_class::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
235 typedef typename maker::node_type node_type; ///< queue node type (derived from intrusive::basket_queue::node)
238 typedef typename maker::cxx_allocator cxx_allocator;
239 typedef typename maker::node_deallocator node_deallocator; // deallocate node
240 typedef typename base_class::node_traits node_traits;
245 static node_type * alloc_node()
247 return cxx_allocator().New();
249 static node_type * alloc_node( const value_type& val )
251 return cxx_allocator().New( val );
253 template <typename... Args>
254 static node_type * alloc_node_move( Args&&... args )
256 return cxx_allocator().MoveNew( std::forward<Args>( args )... );
258 static void free_node( node_type * p )
260 node_deallocator()( p );
263 struct node_disposer {
264 void operator()( node_type * pNode )
269 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
273 /// Initializes empty queue
277 /// Destructor clears the queue
281 /// Enqueues \p val value into the queue.
283 The function makes queue node in dynamic memory calling copy constructor for \p val
284 and then it calls \p intrusive::BasketQueue::enqueue().
285 Returns \p true if success, \p false otherwise.
287 bool enqueue( value_type const& val )
289 scoped_node_ptr p( alloc_node(val));
290 if ( base_class::enqueue( *p )) {
297 /// Enqueues \p data to queue using a functor
299 \p Func is a functor called to create node.
300 The functor \p f takes one argument - a reference to a new node of type \ref value_type :
302 cds::container::BasketQueue< cds::gc::HP, Foo > myQueue;
304 myQueue.enqueue_with( [&bar]( Foo& dest ) { dest = bar; } );
307 template <typename Func>
308 bool enqueue_with( Func f )
310 scoped_node_ptr p( alloc_node() );
312 if ( base_class::enqueue( *p )) {
319 /// Synonym for \p enqueue() function
320 bool push( const value_type& val )
322 return enqueue( val );
325 /// Synonym for \p enqueue_with() function
326 template <typename Func>
327 bool push_with( Func f )
329 return enqueue_with( f );
332 /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
333 template <typename... Args>
334 bool emplace( Args&&... args )
336 scoped_node_ptr p( alloc_node_move( std::forward<Args>(args)...));
337 if ( base_class::enqueue( *p )) {
344 /// Dequeues a value from the queue
346 If queue is not empty, the function returns \p true, \p dest contains copy of
347 dequeued value. The assignment operator for type \ref value_type is invoked.
348 If queue is empty, the function returns \p false, \p dest is unchanged.
350 bool dequeue( value_type& dest )
352 return dequeue_with( [&dest]( value_type& src ) { dest = src; } );
355 /// Dequeues a value using a functor
357 \p Func is a functor called to copy dequeued value.
358 The functor takes one argument - a reference to removed node:
360 cds:container::BasketQueue< cds::gc::HP, Foo > myQueue;
362 myQueue.dequeue_with( [&bar]( Foo& src ) { bar = std::move( src );});
364 The functor is called only if the queue is not empty.
366 template <typename Func>
367 bool dequeue_with( Func f )
369 typename base_class::dequeue_result res;
370 if ( base_class::do_dequeue( res, true )) {
371 f( node_traits::to_value_ptr( *res.pNext )->m_value );
372 base_class::dispose_result( res );
378 /// Synonym for \p dequeue() function
379 bool pop( value_type& dest )
381 return dequeue( dest );
384 /// Synonym for \p dequeue_with() function
385 template <typename Func>
386 bool pop_with( Func f )
388 return dequeue_with( f );
391 /// Checks if the queue is empty
393 Note that this function is not \p const.
394 The function is based on \p dequeue() algorithm.
398 return base_class::empty();
403 The function repeatedly calls \ref dequeue until it returns \p nullptr.
410 /// Returns queue's item count
411 /** \copydetails cds::intrusive::BasketQueue::size()
415 return base_class::size();
418 /// Returns reference to internal statistics
419 const stat& statistics() const
421 return base_class::statistics();
426 }} // namespace cds::container
428 #endif // #ifndef __CDS_CONTAINER_BASKET_QUEUE_H