3 #ifndef __CDS_CONTAINER_BASKET_QUEUE_H
4 #define __CDS_CONTAINER_BASKET_QUEUE_H
7 #include <functional> // ref
8 #include <cds/intrusive/basket_queue.h>
9 #include <cds/container/details/base.h>
10 #include <cds/details/trivial_assign.h>
12 namespace cds { namespace container {
16 template <typename GC, typename T, typename... Options>
17 struct make_basket_queue
22 struct default_options {
23 typedef cds::backoff::empty back_off;
24 typedef CDS_DEFAULT_ALLOCATOR allocator;
25 typedef atomicity::empty_item_counter item_counter;
26 typedef intrusive::basket_queue::dummy_stat stat;
27 typedef opt::v::relaxed_ordering memory_model;
28 enum { alignment = opt::cache_line_alignment };
31 typedef typename opt::make_options<
32 typename cds::opt::find_type_traits< default_options, Options... >::type
36 struct node_type: public intrusive::basket_queue::node< gc >
40 node_type( const value_type& val )
43 template <typename... Args>
44 node_type( Args&&... args )
45 : m_value( std::forward<Args>(args)...)
49 typedef typename options::allocator::template rebind<node_type>::other allocator_type;
50 typedef cds::details::Allocator< node_type, allocator_type > cxx_allocator;
52 struct node_deallocator
54 void operator ()( node_type * pNode )
56 cxx_allocator().Delete( pNode );
60 typedef intrusive::BasketQueue< gc,
62 ,intrusive::opt::hook<
63 intrusive::basket_queue::base_hook< opt::gc<gc> >
65 ,opt::back_off< typename options::back_off >
66 ,intrusive::opt::disposer< node_deallocator >
67 ,opt::item_counter< typename options::item_counter >
68 ,opt::stat< typename options::stat >
69 ,opt::alignment< options::alignment >
70 ,opt::memory_model< typename options::memory_model >
76 /// Basket lock-free queue (non-intrusive variant)
77 /** @ingroup cds_nonintrusive_queue
78 It is non-intrusive version of basket queue algorithm based on intrusive::BasketQueue counterpart.
81 [2007] Moshe Hoffman, Ori Shalev, Nir Shavit "The Baskets Queue"
85 In the
\93basket
\94 approach, instead of
86 the traditional ordered list of nodes, the queue consists of an ordered list of groups
87 of nodes (logical baskets). The order of nodes in each basket need not be specified, and in
88 fact, it is easiest to maintain them in LIFO order. The baskets fulfill the following basic
90 - Each basket has a time interval in which all its nodes
\92 enqueue operations overlap.
91 - The baskets are ordered by the order of their respective time intervals.
92 - For each basket, its nodes
\92 dequeue operations occur after its time interval.
93 - The dequeue operations are performed according to the order of baskets.
95 Two properties define the FIFO order of nodes:
96 - The order of nodes in a basket is not specified.
97 - The order of nodes in different baskets is the FIFO-order of their respective baskets.
99 In algorithms such as the MS-queue or optimistic
100 queue, threads enqueue items by applying a Compare-and-swap (CAS) operation to the
101 queue
\92s tail pointer, and all the threads that fail on a particular CAS operation (and also
102 the winner of that CAS) overlap in time. In particular, they share the time interval of
103 the CAS operation itself. Hence, all the threads that fail to CAS on the tail-node of
104 the queue may be inserted into the same basket. By integrating the basket-mechanism
105 as the back-off mechanism, the time usually spent on backing-off before trying to link
106 onto the new tail, can now be utilized to insert the failed operations into the basket,
107 allowing enqueues to complete sooner. In the meantime, the next successful CAS operations
108 by enqueues allow new baskets to be formed down the list, and these can be
109 filled concurrently. Moreover, the failed operations don
\92t retry their link attempt on the
110 new tail, lowering the overall contention on it. This leads to a queue
111 algorithm that unlike all former concurrent queue algorithms requires virtually no tuning
112 of the backoff mechanisms to reduce contention, making the algorithm an attractive
113 out-of-the-box queue.
115 In order to enqueue, just as in MSQueue, a thread first tries to link the new node to
116 the last node. If it failed to do so, then another thread has already succeeded. Thus it
117 tries to insert the new node into the new basket that was created by the winner thread.
118 To dequeue a node, a thread first reads the head of the queue to obtain the
119 oldest basket. It may then dequeue any node in the oldest basket.
123 - \p GC - garbage collector type: gc::HP, gc::HRC, gc::PTB
124 - \p T is a type stored in the queue. It should be default-constructible, copy-constructible, assignable type.
125 - \p Options - options
127 Permissible \p Options:
128 - opt::allocator - allocator (like \p std::allocator). Default is \ref CDS_DEFAULT_ALLOCATOR
129 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used
130 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter
131 - opt::stat - the type to gather internal statistics for debugging and profiling purposes.
132 Possible option value are: intrusive::basket_queue::stat, intrusive::basket_queue::dummy_stat (the default),
133 user-provided class that supports intrusive::basket_queue::stat interface.
134 Generic option intrusive::queue_stat and intrusive::queue_dummy_stat are acceptable too, however,
135 they will be automatically converted to intrusive::basket_queue::stat and intrusive::basket_queue::dummy_stat
137 - opt::alignment - the alignment for internal queue data. Default is opt::cache_line_alignment
138 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
139 or opt::v::sequential_consistent (sequentially consisnent memory model).
141 template <typename GC, typename T, typename... Options>
143 #ifdef CDS_DOXYGEN_INVOKED
144 intrusive::BasketQueue< GC, intrusive::basket_queue::node< T >, Options... >
146 details::make_basket_queue< GC, T, Options... >::type
150 typedef details::make_basket_queue< GC, T, Options... > options;
151 typedef typename options::type base_class;
155 /// Rebind template arguments
156 template <typename GC2, typename T2, typename... Options2>
158 typedef BasketQueue< GC2, T2, Options2...> other ; ///< Rebinding result
162 typedef T value_type ; ///< Value type stored in the queue
164 typedef typename base_class::gc gc ; ///< Garbage collector used
165 typedef typename base_class::back_off back_off ; ///< Back-off strategy used
166 typedef typename options::allocator_type allocator_type ; ///< Allocator type used for allocate/deallocate the nodes
167 typedef typename base_class::item_counter item_counter ; ///< Item counting policy used
168 typedef typename base_class::stat stat ; ///< Internal statistics policy used
169 typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
172 typedef typename options::node_type node_type ; ///< queue node type (derived from intrusive::single_link::node)
175 typedef typename options::cxx_allocator cxx_allocator;
176 typedef typename options::node_deallocator node_deallocator; // deallocate node
177 typedef typename base_class::node_traits node_traits;
182 static node_type * alloc_node()
184 return cxx_allocator().New();
186 static node_type * alloc_node( const value_type& val )
188 return cxx_allocator().New( val );
190 template <typename... Args>
191 static node_type * alloc_node_move( Args&&... args )
193 return cxx_allocator().MoveNew( std::forward<Args>( args )... );
195 static void free_node( node_type * p )
197 node_deallocator()( p );
200 struct node_disposer {
201 void operator()( node_type * pNode )
206 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
210 /// Initializes empty queue
214 /// Destructor clears the queue
218 /// Returns queue's item count
219 /** \copydetails cds::intrusive::BasketQueue::size()
223 return base_class::size();
226 /// Returns reference to internal statistics
227 const stat& statistics() const
229 return base_class::statistics();
232 /// Enqueues \p val value into the queue.
234 The function makes queue node in dynamic memory calling copy constructor for \p val
235 and then it calls intrusive::BasketQueue::enqueue.
236 Returns \p true if success, \p false otherwise.
238 bool enqueue( const value_type& val )
240 scoped_node_ptr p( alloc_node(val));
241 if ( base_class::enqueue( *p )) {
248 /// Enqueues \p data to queue using copy functor
250 \p Func is a functor called to copy value \p data of type \p Type
251 which may be differ from type \p T stored in the queue.
252 The functor's interface is:
255 void operator()(T& dest, Type const& data)
257 // // Code to copy \p data to \p dest
262 You may use \p boost:ref construction to pass functor \p f by reference.
264 <b>Requirements</b> The functor \p Func should not throw any exception.
266 template <typename Type, typename Func>
267 bool enqueue( const Type& data, Func f )
269 scoped_node_ptr p( alloc_node());
270 f( p->m_value, data );
271 if ( base_class::enqueue( *p )) {
278 /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
279 template <typename... Args>
280 bool emplace( Args&&... args )
282 scoped_node_ptr p( alloc_node_move( std::forward<Args>(args)...));
283 if ( base_class::enqueue( *p )) {
290 /// Dequeues a value using copy functor
292 \p Func is a functor called to copy dequeued value to \p dest of type \p Type
293 which may be differ from type \p T stored in the queue.
294 The functor's interface is:
297 void operator()(Type& dest, T const& data)
299 // Code to copy \p data to \p dest
304 You may use \p boost:ref construction to pass functor \p f by reference.
306 <b>Requirements</b> The functor \p Func should not throw any exception.
308 template <typename Type, typename Func>
309 bool dequeue( Type& dest, Func f )
311 typename base_class::dequeue_result res;
312 if ( base_class::do_dequeue( res, true )) {
313 f( dest, node_traits::to_value_ptr( *res.pNext )->m_value );
319 /// Dequeues a value from the queue
321 If queue is not empty, the function returns \p true, \p dest contains copy of
322 dequeued value. The assignment operator for type \ref value_type is invoked.
323 If queue is empty, the function returns \p false, \p dest is unchanged.
325 bool dequeue( value_type& dest )
327 typedef cds::details::trivial_assign<value_type, value_type> functor;
328 return dequeue( dest, functor() );
331 /// Synonym for \ref enqueue function
332 bool push( const value_type& val )
334 return enqueue( val );
337 /// Synonym for template version of \ref enqueue function
338 template <typename Type, typename Func>
339 bool push( const Type& data, Func f )
341 return enqueue( data, f );
344 /// Synonym for \ref dequeue function
345 bool pop( value_type& dest )
347 return dequeue( dest );
350 /// Synonym for template version of \ref dequeue function
351 template <typename Type, typename Func>
352 bool pop( Type& dest, Func f )
354 return dequeue( dest, f );
357 /// Checks if the queue is empty
359 Note that this function is not \p const.
360 The function is based on \ref dequeue algorithm.
364 return base_class::empty();
369 The function repeatedly calls \ref dequeue until it returns \p nullptr.
377 }} // namespace cds::container
379 #endif // #ifndef __CDS_CONTAINER_BASKET_QUEUE_H