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 cds::intrusive::basket_queue::base_hook< opt::gc<gc> > hook;
128 typedef node_deallocator disposer;
129 static CDS_CONSTEXPR const cds::intrusive::opt::link_check_type link_checker = cds::intrusive::basket_queue::traits::link_checker;
132 typedef cds::intrusive::BasketQueue< gc, node_type, intrusive_traits > type;
137 /// Basket lock-free queue (non-intrusive variant)
138 /** @ingroup cds_nonintrusive_queue
139 It is non-intrusive version of basket queue algorithm based on intrusive::BasketQueue counterpart.
142 [2007] Moshe Hoffman, Ori Shalev, Nir Shavit "The Baskets Queue"
146 In the
\93basket
\94 approach, instead of
147 the traditional ordered list of nodes, the queue consists of an ordered list of groups
148 of nodes (logical baskets). The order of nodes in each basket need not be specified, and in
149 fact, it is easiest to maintain them in LIFO order. The baskets fulfill the following basic
151 - Each basket has a time interval in which all its nodes
\92 enqueue operations overlap.
152 - The baskets are ordered by the order of their respective time intervals.
153 - For each basket, its nodes
\92 dequeue operations occur after its time interval.
154 - The dequeue operations are performed according to the order of baskets.
156 Two properties define the FIFO order of nodes:
157 - The order of nodes in a basket is not specified.
158 - The order of nodes in different baskets is the FIFO-order of their respective baskets.
160 In algorithms such as the MS-queue or optimistic
161 queue, threads enqueue items by applying a Compare-and-swap (CAS) operation to the
162 queue
\92s tail pointer, and all the threads that fail on a particular CAS operation (and also
163 the winner of that CAS) overlap in time. In particular, they share the time interval of
164 the CAS operation itself. Hence, all the threads that fail to CAS on the tail-node of
165 the queue may be inserted into the same basket. By integrating the basket-mechanism
166 as the back-off mechanism, the time usually spent on backing-off before trying to link
167 onto the new tail, can now be utilized to insert the failed operations into the basket,
168 allowing enqueues to complete sooner. In the meantime, the next successful CAS operations
169 by enqueues allow new baskets to be formed down the list, and these can be
170 filled concurrently. Moreover, the failed operations don
\92t retry their link attempt on the
171 new tail, lowering the overall contention on it. This leads to a queue
172 algorithm that unlike all former concurrent queue algorithms requires virtually no tuning
173 of the backoff mechanisms to reduce contention, making the algorithm an attractive
174 out-of-the-box queue.
176 In order to enqueue, just as in MSQueue, a thread first tries to link the new node to
177 the last node. If it failed to do so, then another thread has already succeeded. Thus it
178 tries to insert the new node into the new basket that was created by the winner thread.
179 To dequeue a node, a thread first reads the head of the queue to obtain the
180 oldest basket. It may then dequeue any node in the oldest basket.
184 - \p GC - garbage collector type: \p gc::HP, \p gc::DHP
185 - \p T - type of value to be stored in the queue
186 - \p Traits - queue traits, default is \p basket_queue::traits. You can use \p basket_queue::make_traits
187 metafunction to make your traits or just derive your traits from \p %basket_queue::traits:
189 struct myTraits: public cds::container::basket_queue::traits {
190 typedef cds::intrusive::basket_queue::stat<> stat;
191 typedef cds::atomicity::item_counter item_counter;
193 typedef cds::container::BasketQueue< cds::gc::HP, Foo, myTraits > myQueue;
195 // Equivalent make_traits example:
196 typedef cds::container::BasketQueue< cds::gc::HP, Foo,
197 typename cds::container::basket_queue::make_traits<
198 cds::opt::stat< cds::container::basket_queue::stat<> >,
199 cds::opt::item_counter< cds::atomicity::item_counter >
204 template <typename GC, typename T, typename Traits = basket_queue::traits >
206 #ifdef CDS_DOXYGEN_INVOKED
207 private intrusive::BasketQueue< GC, intrusive::basket_queue::node< T >, Traits >
209 protected details::make_basket_queue< GC, T, Traits >::type
213 typedef details::make_basket_queue< GC, T, Traits > maker;
214 typedef typename maker::type base_class;
218 /// Rebind template arguments
219 template <typename GC2, typename T2, typename Traits2>
221 typedef BasketQueue< GC2, T2, Traits2> other ; ///< Rebinding result
225 typedef GC gc; ///< Garbage collector
226 typedef T value_type; ///< Type of value to be stored in the queue
227 typedef Traits traits; ///< Queue's traits
229 typedef typename base_class::back_off back_off; ///< Back-off strategy used
230 typedef typename maker::allocator_type allocator_type; ///< Allocator type used for allocate/deallocate the nodes
231 typedef typename base_class::item_counter item_counter; ///< Item counting policy used
232 typedef typename base_class::stat stat; ///< Internal statistics policy used
233 typedef typename base_class::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
236 typedef typename maker::node_type node_type; ///< queue node type (derived from intrusive::basket_queue::node)
239 typedef typename maker::cxx_allocator cxx_allocator;
240 typedef typename maker::node_deallocator node_deallocator; // deallocate node
241 typedef typename base_class::node_traits node_traits;
246 static node_type * alloc_node()
248 return cxx_allocator().New();
250 static node_type * alloc_node( const value_type& val )
252 return cxx_allocator().New( val );
254 template <typename... Args>
255 static node_type * alloc_node_move( Args&&... args )
257 return cxx_allocator().MoveNew( std::forward<Args>( args )... );
259 static void free_node( node_type * p )
261 node_deallocator()( p );
264 struct node_disposer {
265 void operator()( node_type * pNode )
270 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
274 /// Initializes empty queue
278 /// Destructor clears the queue
282 /// Enqueues \p val value into the queue.
284 The function makes queue node in dynamic memory calling copy constructor for \p val
285 and then it calls \p intrusive::BasketQueue::enqueue().
286 Returns \p true if success, \p false otherwise.
288 bool enqueue( value_type const& val )
290 scoped_node_ptr p( alloc_node(val));
291 if ( base_class::enqueue( *p )) {
298 /// Enqueues \p data to queue using a functor
300 \p Func is a functor called to create node.
301 The functor \p f takes one argument - a reference to a new node of type \ref value_type :
303 cds::container::BasketQueue< cds::gc::HP, Foo > myQueue;
305 myQueue.enqueue_with( [&bar]( Foo& dest ) { dest = bar; } );
308 template <typename Func>
309 bool enqueue_with( Func f )
311 scoped_node_ptr p( alloc_node() );
313 if ( base_class::enqueue( *p )) {
320 /// Synonym for \p enqueue() function
321 bool push( const value_type& val )
323 return enqueue( val );
326 /// Synonym for \p enqueue_with() function
327 template <typename Func>
328 bool push_with( Func f )
330 return enqueue_with( f );
333 /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
334 template <typename... Args>
335 bool emplace( Args&&... args )
337 scoped_node_ptr p( alloc_node_move( std::forward<Args>(args)...));
338 if ( base_class::enqueue( *p )) {
345 /// Dequeues a value from the queue
347 If queue is not empty, the function returns \p true, \p dest contains copy of
348 dequeued value. The assignment operator for type \ref value_type is invoked.
349 If queue is empty, the function returns \p false, \p dest is unchanged.
351 bool dequeue( value_type& dest )
353 return dequeue_with( [&dest]( value_type& src ) { dest = src; } );
356 /// Dequeues a value using a functor
358 \p Func is a functor called to copy dequeued value.
359 The functor takes one argument - a reference to removed node:
361 cds:container::BasketQueue< cds::gc::HP, Foo > myQueue;
363 myQueue.dequeue_with( [&bar]( Foo& src ) { bar = std::move( src );});
365 The functor is called only if the queue is not empty.
367 template <typename Func>
368 bool dequeue_with( Func f )
370 typename base_class::dequeue_result res;
371 if ( base_class::do_dequeue( res, true )) {
372 f( node_traits::to_value_ptr( *res.pNext )->m_value );
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