2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_CONTAINER_BASKET_QUEUE_H
32 #define CDSLIB_CONTAINER_BASKET_QUEUE_H
35 #include <cds/intrusive/basket_queue.h>
36 #include <cds/container/details/base.h>
37 //#include <cds/details/trivial_assign.h>
39 namespace cds { namespace container {
41 /// BasketQueue related definitions
42 /** @ingroup cds_nonintrusive_helper
44 namespace basket_queue {
46 /// Internal statistics
47 template <typename Counter = cds::intrusive::basket_queue::stat<>::counter_type >
48 using stat = cds::intrusive::basket_queue::stat< Counter >;
50 /// Dummy internal statistics
51 typedef cds::intrusive::basket_queue::empty_stat empty_stat;
53 /// BasketQueue default type traits
57 typedef CDS_DEFAULT_ALLOCATOR allocator;
60 typedef cds::backoff::empty back_off;
62 /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
63 typedef atomicity::empty_item_counter item_counter;
65 /// Internal statistics (by default, disabled)
67 Possible option value are: \p basket_queue::stat, \p basket_queue::empty_stat (the default),
68 user-provided class that supports \p %basket_queue::stat interface.
70 typedef basket_queue::empty_stat stat;
72 /// C++ memory ordering model
74 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
75 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
77 typedef opt::v::relaxed_ordering memory_model;
79 /// Padding for internal critical atomic data. Default is \p opt::cache_line_padding
80 enum { padding = opt::cache_line_padding };
83 /// Metafunction converting option list to \p basket_queue::traits
85 Supported \p Options are:
86 - \p opt::allocator - allocator (like \p std::allocator) used for allocating queue nodes. Default is \ref CDS_DEFAULT_ALLOCATOR
87 - \p opt::back_off - back-off strategy used, default is \p cds::backoff::empty.
88 - \p opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter (item counting disabled)
89 To enable item counting use \p cds::atomicity::item_counter
90 - \ opt::stat - the type to gather internal statistics.
91 Possible statistics types are: \p basket_queue::stat, \p basket_queue::empty_stat, user-provided class that supports \p %basket_queue::stat interface.
92 Default is \p %basket_queue::empty_stat.
93 - \p opt::padding - padding for internal critical atomic data. Default is \p opt::cache_line_padding
94 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
95 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
97 Example: declare \p %BasketQueue with item counting and internal statistics
99 typedef cds::container::BasketQueue< cds::gc::HP, Foo,
100 typename cds::container::basket_queue::make_traits<
101 cds::opt::item_counte< cds::atomicity::item_counter >,
102 cds::opt::stat< cds::intrusive::basket_queue::stat<> >
107 template <typename... Options>
109 # ifdef CDS_DOXYGEN_INVOKED
110 typedef implementation_defined type; ///< Metafunction result
112 typedef typename cds::opt::make_options<
113 typename cds::opt::find_type_traits< traits, Options... >::type
118 } // namespace basket_queue
122 template <typename GC, typename T, typename Traits>
123 struct make_basket_queue
126 typedef T value_type;
127 typedef Traits traits;
129 struct node_type: public intrusive::basket_queue::node< gc >
133 node_type( const value_type& val )
136 template <typename... Args>
137 node_type( Args&&... args )
138 : m_value( std::forward<Args>(args)...)
142 typedef typename traits::allocator::template rebind<node_type>::other allocator_type;
143 typedef cds::details::Allocator< node_type, allocator_type > cxx_allocator;
145 struct node_deallocator
147 void operator ()( node_type * pNode )
149 cxx_allocator().Delete( pNode );
153 struct intrusive_traits : public traits
155 typedef cds::intrusive::basket_queue::base_hook< opt::gc<gc> > hook;
156 typedef node_deallocator disposer;
157 static CDS_CONSTEXPR const cds::intrusive::opt::link_check_type link_checker = cds::intrusive::basket_queue::traits::link_checker;
160 typedef cds::intrusive::BasketQueue< gc, node_type, intrusive_traits > type;
165 /// Basket lock-free queue (non-intrusive variant)
166 /** @ingroup cds_nonintrusive_queue
167 It is non-intrusive version of basket queue algorithm based on intrusive::BasketQueue counterpart.
170 [2007] Moshe Hoffman, Ori Shalev, Nir Shavit "The Baskets Queue"
174 In the 'basket' approach, instead of
175 the traditional ordered list of nodes, the queue consists of an ordered list of groups
176 of nodes (logical baskets). The order of nodes in each basket need not be specified, and in
177 fact, it is easiest to maintain them in LIFO order. The baskets fulfill the following basic
179 - Each basket has a time interval in which all its nodes' enqueue operations overlap.
180 - The baskets are ordered by the order of their respective time intervals.
181 - For each basket, its nodes' dequeue operations occur after its time interval.
182 - The dequeue operations are performed according to the order of baskets.
184 Two properties define the FIFO order of nodes:
185 - The order of nodes in a basket is not specified.
186 - The order of nodes in different baskets is the FIFO-order of their respective baskets.
188 In algorithms such as the MS-queue or optimistic
189 queue, threads enqueue items by applying a Compare-and-swap (CAS) operation to the
190 queue's tail pointer, and all the threads that fail on a particular CAS operation (and also
191 the winner of that CAS) overlap in time. In particular, they share the time interval of
192 the CAS operation itself. Hence, all the threads that fail to CAS on the tail-node of
193 the queue may be inserted into the same basket. By integrating the basket-mechanism
194 as the back-off mechanism, the time usually spent on backing-off before trying to link
195 onto the new tail, can now be utilized to insert the failed operations into the basket,
196 allowing enqueues to complete sooner. In the meantime, the next successful CAS operations
197 by enqueues allow new baskets to be formed down the list, and these can be
198 filled concurrently. Moreover, the failed operations don't retry their link attempt on the
199 new tail, lowering the overall contention on it. This leads to a queue
200 algorithm that unlike all former concurrent queue algorithms requires virtually no tuning
201 of the backoff mechanisms to reduce contention, making the algorithm an attractive
202 out-of-the-box queue.
204 In order to enqueue, just as in MSQueue, a thread first tries to link the new node to
205 the last node. If it failed to do so, then another thread has already succeeded. Thus it
206 tries to insert the new node into the new basket that was created by the winner thread.
207 To dequeue a node, a thread first reads the head of the queue to obtain the
208 oldest basket. It may then dequeue any node in the oldest basket.
212 - \p GC - garbage collector type: \p gc::HP, \p gc::DHP
213 - \p T - type of value to be stored in the queue
214 - \p Traits - queue traits, default is \p basket_queue::traits. You can use \p basket_queue::make_traits
215 metafunction to make your traits or just derive your traits from \p %basket_queue::traits:
217 struct myTraits: public cds::container::basket_queue::traits {
218 typedef cds::intrusive::basket_queue::stat<> stat;
219 typedef cds::atomicity::item_counter item_counter;
221 typedef cds::container::BasketQueue< cds::gc::HP, Foo, myTraits > myQueue;
223 // Equivalent make_traits example:
224 typedef cds::container::BasketQueue< cds::gc::HP, Foo,
225 typename cds::container::basket_queue::make_traits<
226 cds::opt::stat< cds::container::basket_queue::stat<> >,
227 cds::opt::item_counter< cds::atomicity::item_counter >
232 template <typename GC, typename T, typename Traits = basket_queue::traits >
234 #ifdef CDS_DOXYGEN_INVOKED
235 private intrusive::BasketQueue< GC, intrusive::basket_queue::node< T >, Traits >
237 protected details::make_basket_queue< GC, T, Traits >::type
241 typedef details::make_basket_queue< GC, T, Traits > maker;
242 typedef typename maker::type base_class;
246 /// Rebind template arguments
247 template <typename GC2, typename T2, typename Traits2>
249 typedef BasketQueue< GC2, T2, Traits2> other ; ///< Rebinding result
253 typedef GC gc; ///< Garbage collector
254 typedef T value_type; ///< Type of value to be stored in the queue
255 typedef Traits traits; ///< Queue's traits
257 typedef typename base_class::back_off back_off; ///< Back-off strategy used
258 typedef typename maker::allocator_type allocator_type; ///< Allocator type used for allocate/deallocate the nodes
259 typedef typename base_class::item_counter item_counter; ///< Item counting policy used
260 typedef typename base_class::stat stat; ///< Internal statistics policy used
261 typedef typename base_class::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
263 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = base_class::c_nHazardPtrCount; ///< Count of hazard pointer required for the algorithm
266 typedef typename maker::node_type node_type; ///< queue node type (derived from intrusive::basket_queue::node)
269 typedef typename maker::cxx_allocator cxx_allocator;
270 typedef typename maker::node_deallocator node_deallocator; // deallocate node
271 typedef typename base_class::node_traits node_traits;
276 static node_type * alloc_node()
278 return cxx_allocator().New();
280 static node_type * alloc_node( const value_type& val )
282 return cxx_allocator().New( val );
284 template <typename... Args>
285 static node_type * alloc_node_move( Args&&... args )
287 return cxx_allocator().MoveNew( std::forward<Args>( args )... );
289 static void free_node( node_type * p )
291 node_deallocator()( p );
294 struct node_disposer {
295 void operator()( node_type * pNode )
300 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
304 /// Initializes empty queue
308 /// Destructor clears the queue
312 /// Enqueues \p val value into the queue.
314 The function makes queue node in dynamic memory calling copy constructor for \p val
315 and then it calls \p intrusive::BasketQueue::enqueue().
316 Returns \p true if success, \p false otherwise.
318 bool enqueue( value_type const& val )
320 scoped_node_ptr p( alloc_node(val));
321 if ( base_class::enqueue( *p )) {
328 /// Enqueues \p val value into the queue, move semantics
329 bool enqueue( value_type&& val )
331 scoped_node_ptr p( alloc_node_move( std::move( val )));
332 if ( base_class::enqueue( *p )) {
339 /// Enqueues \p data to queue using a functor
341 \p Func is a functor called to create node.
342 The functor \p f takes one argument - a reference to a new node of type \ref value_type :
344 cds::container::BasketQueue< cds::gc::HP, Foo > myQueue;
346 myQueue.enqueue_with( [&bar]( Foo& dest ) { dest = bar; } );
349 template <typename Func>
350 bool enqueue_with( Func f )
352 scoped_node_ptr p( alloc_node());
354 if ( base_class::enqueue( *p )) {
361 /// Synonym for \p enqueue() function
362 bool push( value_type const& val )
364 return enqueue( val );
367 /// Synonym for \p enqueue() function, move semantics
368 bool push( value_type&& val )
370 return enqueue( std::move( val ));
373 /// Synonym for \p enqueue_with() function
374 template <typename Func>
375 bool push_with( Func f )
377 return enqueue_with( f );
380 /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
381 template <typename... Args>
382 bool emplace( Args&&... args )
384 scoped_node_ptr p( alloc_node_move( std::forward<Args>(args)...));
385 if ( base_class::enqueue( *p )) {
392 /// Dequeues a value from the queue
394 If queue is not empty, the function returns \p true, \p dest contains copy of
395 dequeued value. The assignment operator for \p value_type is invoked.
396 If queue is empty, the function returns \p false, \p dest is unchanged.
398 bool dequeue( value_type& dest )
400 return dequeue_with( [&dest]( value_type& src ) {
401 // TSan finds a race between this read of \p src and node_type constructor
402 // I think, it is wrong
403 CDS_TSAN_ANNOTATE_IGNORE_READS_BEGIN;
404 dest = std::move( src );
405 CDS_TSAN_ANNOTATE_IGNORE_READS_END;
409 /// Dequeues a value using a functor
411 \p Func is a functor called to copy dequeued value.
412 The functor takes one argument - a reference to removed node:
414 cds:container::BasketQueue< cds::gc::HP, Foo > myQueue;
416 myQueue.dequeue_with( [&bar]( Foo& src ) { bar = std::move( src );});
418 The functor is called only if the queue is not empty.
420 template <typename Func>
421 bool dequeue_with( Func f )
423 typename base_class::dequeue_result res;
424 if ( base_class::do_dequeue( res, true )) {
425 f( node_traits::to_value_ptr( *res.pNext )->m_value );
431 /// Synonym for \p dequeue() function
432 bool pop( value_type& dest )
434 return dequeue( dest );
437 /// Synonym for \p dequeue_with() function
438 template <typename Func>
439 bool pop_with( Func f )
441 return dequeue_with( f );
444 /// Checks if the queue is empty
446 Note that this function is not \p const.
447 The function is based on \p dequeue() algorithm.
451 return base_class::empty();
456 The function repeatedly calls \ref dequeue until it returns \p nullptr.
463 /// Returns queue's item count
464 /** \copydetails cds::intrusive::BasketQueue::size()
468 return base_class::size();
471 /// Returns reference to internal statistics
472 const stat& statistics() const
474 return base_class::statistics();
479 }} // namespace cds::container
481 #endif // #ifndef CDSLIB_CONTAINER_BASKET_QUEUE_H