3 #ifndef __CDS_CONTAINER_BASKET_QUEUE_H
4 #define __CDS_CONTAINER_BASKET_QUEUE_H
6 #include <cds/intrusive/basket_queue.h>
7 #include <cds/container/base.h>
9 #include <cds/details/trivial_assign.h>
10 #include <cds/details/std/memory.h>
12 namespace cds { namespace container {
16 template <typename GC, typename T, CDS_DECL_OPTIONS7>
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, CDS_OPTIONS7 >::type
36 struct node_type: public intrusive::basket_queue::node< gc >
40 node_type( const value_type& val )
43 # ifdef CDS_EMPLACE_SUPPORT
44 template <typename... Args>
45 node_type( Args&&... args )
46 : m_value( std::forward<Args>(args)...)
54 typedef typename options::allocator::template rebind<node_type>::other allocator_type;
55 typedef cds::details::Allocator< node_type, allocator_type > cxx_allocator;
57 struct node_deallocator
59 void operator ()( node_type * pNode )
61 cxx_allocator().Delete( pNode );
65 typedef intrusive::BasketQueue< gc,
67 ,intrusive::opt::hook<
68 intrusive::basket_queue::base_hook< opt::gc<gc> >
70 ,opt::back_off< typename options::back_off >
71 ,intrusive::opt::disposer< node_deallocator >
72 ,opt::item_counter< typename options::item_counter >
73 ,opt::stat< typename options::stat >
74 ,opt::alignment< options::alignment >
75 ,opt::memory_model< typename options::memory_model >
81 /// Basket lock-free queue (non-intrusive variant)
82 /** @ingroup cds_nonintrusive_queue
83 It is non-intrusive version of basket queue algorithm based on intrusive::BasketQueue counterpart.
86 [2007] Moshe Hoffman, Ori Shalev, Nir Shavit "The Baskets Queue"
90 In the
\93basket
\94 approach, instead of
91 the traditional ordered list of nodes, the queue consists of an ordered list of groups
92 of nodes (logical baskets). The order of nodes in each basket need not be specified, and in
93 fact, it is easiest to maintain them in LIFO order. The baskets fulfill the following basic
95 - Each basket has a time interval in which all its nodes
\92 enqueue operations overlap.
96 - The baskets are ordered by the order of their respective time intervals.
97 - For each basket, its nodes
\92 dequeue operations occur after its time interval.
98 - The dequeue operations are performed according to the order of baskets.
100 Two properties define the FIFO order of nodes:
101 - The order of nodes in a basket is not specified.
102 - The order of nodes in different baskets is the FIFO-order of their respective baskets.
104 In algorithms such as the MS-queue or optimistic
105 queue, threads enqueue items by applying a Compare-and-swap (CAS) operation to the
106 queue
\92s tail pointer, and all the threads that fail on a particular CAS operation (and also
107 the winner of that CAS) overlap in time. In particular, they share the time interval of
108 the CAS operation itself. Hence, all the threads that fail to CAS on the tail-node of
109 the queue may be inserted into the same basket. By integrating the basket-mechanism
110 as the back-off mechanism, the time usually spent on backing-off before trying to link
111 onto the new tail, can now be utilized to insert the failed operations into the basket,
112 allowing enqueues to complete sooner. In the meantime, the next successful CAS operations
113 by enqueues allow new baskets to be formed down the list, and these can be
114 filled concurrently. Moreover, the failed operations don
\92t retry their link attempt on the
115 new tail, lowering the overall contention on it. This leads to a queue
116 algorithm that unlike all former concurrent queue algorithms requires virtually no tuning
117 of the backoff mechanisms to reduce contention, making the algorithm an attractive
118 out-of-the-box queue.
120 In order to enqueue, just as in MSQueue, a thread first tries to link the new node to
121 the last node. If it failed to do so, then another thread has already succeeded. Thus it
122 tries to insert the new node into the new basket that was created by the winner thread.
123 To dequeue a node, a thread first reads the head of the queue to obtain the
124 oldest basket. It may then dequeue any node in the oldest basket.
128 - \p GC - garbage collector type: gc::HP, gc::HRC, gc::PTB
129 - \p T is a type stored in the queue. It should be default-constructible, copy-constructible, assignable type.
130 - \p Options - options
132 Permissible \p Options:
133 - opt::allocator - allocator (like \p std::allocator). Default is \ref CDS_DEFAULT_ALLOCATOR
134 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used
135 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter
136 - opt::stat - the type to gather internal statistics for debugging and profiling purposes.
137 Possible option value are: intrusive::basket_queue::stat, intrusive::basket_queue::dummy_stat (the default),
138 user-provided class that supports intrusive::basket_queue::stat interface.
139 Generic option intrusive::queue_stat and intrusive::queue_dummy_stat are acceptable too, however,
140 they will be automatically converted to intrusive::basket_queue::stat and intrusive::basket_queue::dummy_stat
142 - opt::alignment - the alignment for internal queue data. Default is opt::cache_line_alignment
143 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
144 or opt::v::sequential_consistent (sequentially consisnent memory model).
146 template <typename GC, typename T, CDS_DECL_OPTIONS7>
148 #ifdef CDS_DOXYGEN_INVOKED
149 intrusive::BasketQueue< GC, intrusive::basket_queue::node< T >, Options... >
151 details::make_basket_queue< GC, T, CDS_OPTIONS7 >::type
155 typedef details::make_basket_queue< GC, T, CDS_OPTIONS7 > options;
156 typedef typename options::type base_class;
160 /// Rebind template arguments
161 template <typename GC2, typename T2, CDS_DECL_OTHER_OPTIONS7>
163 typedef BasketQueue< GC2, T2, CDS_OTHER_OPTIONS7> other ; ///< Rebinding result
167 typedef T value_type ; ///< Value type stored in the queue
169 typedef typename base_class::gc gc ; ///< Garbage collector used
170 typedef typename base_class::back_off back_off ; ///< Back-off strategy used
171 typedef typename options::allocator_type allocator_type ; ///< Allocator type used for allocate/deallocate the nodes
172 typedef typename base_class::item_counter item_counter ; ///< Item counting policy used
173 typedef typename base_class::stat stat ; ///< Internal statistics policy used
174 typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
177 typedef typename options::node_type node_type ; ///< queue node type (derived from intrusive::single_link::node)
180 typedef typename options::cxx_allocator cxx_allocator;
181 typedef typename options::node_deallocator node_deallocator; // deallocate node
182 typedef typename base_class::node_traits node_traits;
187 static node_type * alloc_node()
189 return cxx_allocator().New();
191 static node_type * alloc_node( const value_type& val )
193 return cxx_allocator().New( val );
195 # ifdef CDS_EMPLACE_SUPPORT
196 template <typename... Args>
197 static node_type * alloc_node_move( Args&&... args )
199 return cxx_allocator().MoveNew( std::forward<Args>( args )... );
202 static void free_node( node_type * p )
204 node_deallocator()( p );
207 struct node_disposer {
208 void operator()( node_type * pNode )
213 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
217 /// Initializes empty queue
221 /// Destructor clears the queue
225 /// Returns queue's item count
226 /** \copydetails cds::intrusive::BasketQueue::size()
230 return base_class::size();
233 /// Returns reference to internal statistics
234 const stat& statistics() const
236 return base_class::statistics();
239 /// Enqueues \p val value into the queue.
241 The function makes queue node in dynamic memory calling copy constructor for \p val
242 and then it calls intrusive::BasketQueue::enqueue.
243 Returns \p true if success, \p false otherwise.
245 bool enqueue( const value_type& val )
247 scoped_node_ptr p( alloc_node(val));
248 if ( base_class::enqueue( *p )) {
255 /// Enqueues \p data to queue using copy functor
257 \p Func is a functor called to copy value \p data of type \p Type
258 which may be differ from type \p T stored in the queue.
259 The functor's interface is:
262 void operator()(T& dest, Type const& data)
264 // // Code to copy \p data to \p dest
269 You may use \p boost:ref construction to pass functor \p f by reference.
271 <b>Requirements</b> The functor \p Func should not throw any exception.
273 template <typename Type, typename Func>
274 bool enqueue( const Type& data, Func f )
276 scoped_node_ptr p( alloc_node());
277 cds::unref(f)( p->m_value, data );
278 if ( base_class::enqueue( *p )) {
285 # ifdef CDS_EMPLACE_SUPPORT
286 /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
288 This function is available only for compiler that supports
289 variadic template and move semantics
291 template <typename... Args>
292 bool emplace( Args&&... args )
294 scoped_node_ptr p( alloc_node_move( std::forward<Args>(args)...));
295 if ( base_class::enqueue( *p )) {
304 /// Dequeues a value using copy functor
306 \p Func is a functor called to copy dequeued value to \p dest of type \p Type
307 which may be differ from type \p T stored in the queue.
308 The functor's interface is:
311 void operator()(Type& dest, T const& data)
313 // Code to copy \p data to \p dest
318 You may use \p boost:ref construction to pass functor \p f by reference.
320 <b>Requirements</b> The functor \p Func should not throw any exception.
322 template <typename Type, typename Func>
323 bool dequeue( Type& dest, Func f )
325 typename base_class::dequeue_result res;
326 if ( base_class::do_dequeue( res, true )) {
327 cds::unref(f)( dest, node_traits::to_value_ptr( *res.pNext )->m_value );
333 /// Dequeues a value from the queue
335 If queue is not empty, the function returns \p true, \p dest contains copy of
336 dequeued value. The assignment operator for type \ref value_type is invoked.
337 If queue is empty, the function returns \p false, \p dest is unchanged.
339 bool dequeue( value_type& dest )
341 typedef cds::details::trivial_assign<value_type, value_type> functor;
342 return dequeue( dest, functor() );
345 /// Synonym for \ref enqueue function
346 bool push( const value_type& val )
348 return enqueue( val );
351 /// Synonym for template version of \ref enqueue function
352 template <typename Type, typename Func>
353 bool push( const Type& data, Func f )
355 return enqueue( data, f );
358 /// Synonym for \ref dequeue function
359 bool pop( value_type& dest )
361 return dequeue( dest );
364 /// Synonym for template version of \ref dequeue function
365 template <typename Type, typename Func>
366 bool pop( Type& dest, Func f )
368 return dequeue( dest, f );
371 /// Checks if the queue is empty
373 Note that this function is not \p const.
374 The function is based on \ref dequeue algorithm.
378 return base_class::empty();
383 The function repeatedly calls \ref dequeue until it returns NULL.
391 }} // namespace cds::container
393 #endif // #ifndef __CDS_CONTAINER_BASKET_QUEUE_H