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/base.h>
10 #include <cds/details/trivial_assign.h>
13 namespace cds { namespace container {
17 template <typename GC, typename T, typename... Options>
18 struct make_basket_queue
23 struct default_options {
24 typedef cds::backoff::empty back_off;
25 typedef CDS_DEFAULT_ALLOCATOR allocator;
26 typedef atomicity::empty_item_counter item_counter;
27 typedef intrusive::basket_queue::dummy_stat stat;
28 typedef opt::v::relaxed_ordering memory_model;
29 enum { alignment = opt::cache_line_alignment };
32 typedef typename opt::make_options<
33 typename cds::opt::find_type_traits< default_options, Options... >::type
37 struct node_type: public intrusive::basket_queue::node< gc >
41 node_type( const value_type& val )
44 template <typename... Args>
45 node_type( Args&&... args )
46 : m_value( std::forward<Args>(args)...)
50 typedef typename options::allocator::template rebind<node_type>::other allocator_type;
51 typedef cds::details::Allocator< node_type, allocator_type > cxx_allocator;
53 struct node_deallocator
55 void operator ()( node_type * pNode )
57 cxx_allocator().Delete( pNode );
61 typedef intrusive::BasketQueue< gc,
63 ,intrusive::opt::hook<
64 intrusive::basket_queue::base_hook< opt::gc<gc> >
66 ,opt::back_off< typename options::back_off >
67 ,intrusive::opt::disposer< node_deallocator >
68 ,opt::item_counter< typename options::item_counter >
69 ,opt::stat< typename options::stat >
70 ,opt::alignment< options::alignment >
71 ,opt::memory_model< typename options::memory_model >
77 /// Basket lock-free queue (non-intrusive variant)
78 /** @ingroup cds_nonintrusive_queue
79 It is non-intrusive version of basket queue algorithm based on intrusive::BasketQueue counterpart.
82 [2007] Moshe Hoffman, Ori Shalev, Nir Shavit "The Baskets Queue"
86 In the
\93basket
\94 approach, instead of
87 the traditional ordered list of nodes, the queue consists of an ordered list of groups
88 of nodes (logical baskets). The order of nodes in each basket need not be specified, and in
89 fact, it is easiest to maintain them in LIFO order. The baskets fulfill the following basic
91 - Each basket has a time interval in which all its nodes
\92 enqueue operations overlap.
92 - The baskets are ordered by the order of their respective time intervals.
93 - For each basket, its nodes
\92 dequeue operations occur after its time interval.
94 - The dequeue operations are performed according to the order of baskets.
96 Two properties define the FIFO order of nodes:
97 - The order of nodes in a basket is not specified.
98 - The order of nodes in different baskets is the FIFO-order of their respective baskets.
100 In algorithms such as the MS-queue or optimistic
101 queue, threads enqueue items by applying a Compare-and-swap (CAS) operation to the
102 queue
\92s tail pointer, and all the threads that fail on a particular CAS operation (and also
103 the winner of that CAS) overlap in time. In particular, they share the time interval of
104 the CAS operation itself. Hence, all the threads that fail to CAS on the tail-node of
105 the queue may be inserted into the same basket. By integrating the basket-mechanism
106 as the back-off mechanism, the time usually spent on backing-off before trying to link
107 onto the new tail, can now be utilized to insert the failed operations into the basket,
108 allowing enqueues to complete sooner. In the meantime, the next successful CAS operations
109 by enqueues allow new baskets to be formed down the list, and these can be
110 filled concurrently. Moreover, the failed operations don
\92t retry their link attempt on the
111 new tail, lowering the overall contention on it. This leads to a queue
112 algorithm that unlike all former concurrent queue algorithms requires virtually no tuning
113 of the backoff mechanisms to reduce contention, making the algorithm an attractive
114 out-of-the-box queue.
116 In order to enqueue, just as in MSQueue, a thread first tries to link the new node to
117 the last node. If it failed to do so, then another thread has already succeeded. Thus it
118 tries to insert the new node into the new basket that was created by the winner thread.
119 To dequeue a node, a thread first reads the head of the queue to obtain the
120 oldest basket. It may then dequeue any node in the oldest basket.
124 - \p GC - garbage collector type: gc::HP, gc::HRC, gc::PTB
125 - \p T is a type stored in the queue. It should be default-constructible, copy-constructible, assignable type.
126 - \p Options - options
128 Permissible \p Options:
129 - opt::allocator - allocator (like \p std::allocator). Default is \ref CDS_DEFAULT_ALLOCATOR
130 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used
131 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter
132 - opt::stat - the type to gather internal statistics for debugging and profiling purposes.
133 Possible option value are: intrusive::basket_queue::stat, intrusive::basket_queue::dummy_stat (the default),
134 user-provided class that supports intrusive::basket_queue::stat interface.
135 Generic option intrusive::queue_stat and intrusive::queue_dummy_stat are acceptable too, however,
136 they will be automatically converted to intrusive::basket_queue::stat and intrusive::basket_queue::dummy_stat
138 - opt::alignment - the alignment for internal queue data. Default is opt::cache_line_alignment
139 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
140 or opt::v::sequential_consistent (sequentially consisnent memory model).
142 template <typename GC, typename T, typename... Options>
144 #ifdef CDS_DOXYGEN_INVOKED
145 intrusive::BasketQueue< GC, intrusive::basket_queue::node< T >, Options... >
147 details::make_basket_queue< GC, T, Options... >::type
151 typedef details::make_basket_queue< GC, T, Options... > options;
152 typedef typename options::type base_class;
156 /// Rebind template arguments
157 template <typename GC2, typename T2, typename... Options2>
159 typedef BasketQueue< GC2, T2, Options2...> other ; ///< Rebinding result
163 typedef T value_type ; ///< Value type stored in the queue
165 typedef typename base_class::gc gc ; ///< Garbage collector used
166 typedef typename base_class::back_off back_off ; ///< Back-off strategy used
167 typedef typename options::allocator_type allocator_type ; ///< Allocator type used for allocate/deallocate the nodes
168 typedef typename base_class::item_counter item_counter ; ///< Item counting policy used
169 typedef typename base_class::stat stat ; ///< Internal statistics policy used
170 typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
173 typedef typename options::node_type node_type ; ///< queue node type (derived from intrusive::single_link::node)
176 typedef typename options::cxx_allocator cxx_allocator;
177 typedef typename options::node_deallocator node_deallocator; // deallocate node
178 typedef typename base_class::node_traits node_traits;
183 static node_type * alloc_node()
185 return cxx_allocator().New();
187 static node_type * alloc_node( const value_type& val )
189 return cxx_allocator().New( val );
191 template <typename... Args>
192 static node_type * alloc_node_move( Args&&... args )
194 return cxx_allocator().MoveNew( std::forward<Args>( args )... );
196 static void free_node( node_type * p )
198 node_deallocator()( p );
201 struct node_disposer {
202 void operator()( node_type * pNode )
207 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
211 /// Initializes empty queue
215 /// Destructor clears the queue
219 /// Returns queue's item count
220 /** \copydetails cds::intrusive::BasketQueue::size()
224 return base_class::size();
227 /// Returns reference to internal statistics
228 const stat& statistics() const
230 return base_class::statistics();
233 /// Enqueues \p val value into the queue.
235 The function makes queue node in dynamic memory calling copy constructor for \p val
236 and then it calls intrusive::BasketQueue::enqueue.
237 Returns \p true if success, \p false otherwise.
239 bool enqueue( const value_type& val )
241 scoped_node_ptr p( alloc_node(val));
242 if ( base_class::enqueue( *p )) {
249 /// Enqueues \p data to queue using copy functor
251 \p Func is a functor called to copy value \p data of type \p Type
252 which may be differ from type \p T stored in the queue.
253 The functor's interface is:
256 void operator()(T& dest, Type const& data)
258 // // Code to copy \p data to \p dest
263 You may use \p boost:ref construction to pass functor \p f by reference.
265 <b>Requirements</b> The functor \p Func should not throw any exception.
267 template <typename Type, typename Func>
268 bool enqueue( const Type& data, Func f )
270 scoped_node_ptr p( alloc_node());
271 cds::unref(f)( p->m_value, data );
272 if ( base_class::enqueue( *p )) {
279 /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
280 template <typename... Args>
281 bool emplace( Args&&... args )
283 scoped_node_ptr p( alloc_node_move( std::forward<Args>(args)...));
284 if ( base_class::enqueue( *p )) {
291 /// Dequeues a value using copy functor
293 \p Func is a functor called to copy dequeued value to \p dest of type \p Type
294 which may be differ from type \p T stored in the queue.
295 The functor's interface is:
298 void operator()(Type& dest, T const& data)
300 // Code to copy \p data to \p dest
305 You may use \p boost:ref construction to pass functor \p f by reference.
307 <b>Requirements</b> The functor \p Func should not throw any exception.
309 template <typename Type, typename Func>
310 bool dequeue( Type& dest, Func f )
312 typename base_class::dequeue_result res;
313 if ( base_class::do_dequeue( res, true )) {
314 cds::unref(f)( dest, node_traits::to_value_ptr( *res.pNext )->m_value );
320 /// Dequeues a value from the queue
322 If queue is not empty, the function returns \p true, \p dest contains copy of
323 dequeued value. The assignment operator for type \ref value_type is invoked.
324 If queue is empty, the function returns \p false, \p dest is unchanged.
326 bool dequeue( value_type& dest )
328 typedef cds::details::trivial_assign<value_type, value_type> functor;
329 return dequeue( dest, functor() );
332 /// Synonym for \ref enqueue function
333 bool push( const value_type& val )
335 return enqueue( val );
338 /// Synonym for template version of \ref enqueue function
339 template <typename Type, typename Func>
340 bool push( const Type& data, Func f )
342 return enqueue( data, f );
345 /// Synonym for \ref dequeue function
346 bool pop( value_type& dest )
348 return dequeue( dest );
351 /// Synonym for template version of \ref dequeue function
352 template <typename Type, typename Func>
353 bool pop( Type& dest, Func f )
355 return dequeue( dest, f );
358 /// Checks if the queue is empty
360 Note that this function is not \p const.
361 The function is based on \ref dequeue algorithm.
365 return base_class::empty();
370 The function repeatedly calls \ref dequeue until it returns \p nullptr.
378 }} // namespace cds::container
380 #endif // #ifndef __CDS_CONTAINER_BASKET_QUEUE_H