-//$$CDS-header$$
-
-#ifndef __CDS_CONTAINER_BASKET_QUEUE_H
-#define __CDS_CONTAINER_BASKET_QUEUE_H
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+
+ Source code repo: http://github.com/khizmax/libcds/
+ Download: http://sourceforge.net/projects/libcds/files/
+
+ Redistribution and use in source and binary forms, with or without
+ modification, are permitted provided that the following conditions are met:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#ifndef CDSLIB_CONTAINER_BASKET_QUEUE_H
+#define CDSLIB_CONTAINER_BASKET_QUEUE_H
#include <memory>
#include <cds/intrusive/basket_queue.h>
-#include <cds/container/base.h>
-#include <cds/ref.h>
-#include <cds/details/trivial_assign.h>
-
+#include <cds/container/details/base.h>
+//#include <cds/details/trivial_assign.h>
namespace cds { namespace container {
+ /// BasketQueue related definitions
+ /** @ingroup cds_nonintrusive_helper
+ */
+ namespace basket_queue {
+
+ /// Internal statistics
+ template <typename Counter = cds::intrusive::basket_queue::stat<>::counter_type >
+ using stat = cds::intrusive::basket_queue::stat< Counter >;
+
+ /// Dummy internal statistics
+ typedef cds::intrusive::basket_queue::empty_stat empty_stat;
+
+ /// BasketQueue default type traits
+ struct traits
+ {
+ /// Node allocator
+ typedef CDS_DEFAULT_ALLOCATOR allocator;
+
+ /// Back-off strategy
+ typedef cds::backoff::empty back_off;
+
+ /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
+ typedef atomicity::empty_item_counter item_counter;
+
+ /// Internal statistics (by default, disabled)
+ /**
+ Possible option value are: \p basket_queue::stat, \p basket_queue::empty_stat (the default),
+ user-provided class that supports \p %basket_queue::stat interface.
+ */
+ typedef basket_queue::empty_stat stat;
+
+ /// C++ memory ordering model
+ /**
+ Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
+ or \p opt::v::sequential_consistent (sequentially consisnent memory model).
+ */
+ typedef opt::v::relaxed_ordering memory_model;
+
+ /// Padding for internal critical atomic data. Default is \p opt::cache_line_padding
+ enum { padding = opt::cache_line_padding };
+ };
+
+ /// Metafunction converting option list to \p basket_queue::traits
+ /**
+ Supported \p Options are:
+ - \p opt::allocator - allocator (like \p std::allocator) used for allocating queue nodes. Default is \ref CDS_DEFAULT_ALLOCATOR
+ - \p opt::back_off - back-off strategy used, default is \p cds::backoff::empty.
+ - \p opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter (item counting disabled)
+ To enable item counting use \p cds::atomicity::item_counter
+ - \ opt::stat - the type to gather internal statistics.
+ Possible statistics types are: \p basket_queue::stat, \p basket_queue::empty_stat, user-provided class that supports \p %basket_queue::stat interface.
+ Default is \p %basket_queue::empty_stat.
+ - \p opt::padding - padding for internal critical atomic data. Default is \p opt::cache_line_padding
+ - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
+ or \p opt::v::sequential_consistent (sequentially consisnent memory model).
+
+ Example: declare \p %BasketQueue with item counting and internal statistics
+ \code
+ typedef cds::container::BasketQueue< cds::gc::HP, Foo,
+ typename cds::container::basket_queue::make_traits<
+ cds::opt::item_counte< cds::atomicity::item_counter >,
+ cds::opt::stat< cds::intrusive::basket_queue::stat<> >
+ >::type
+ > myQueue;
+ \endcode
+ */
+ template <typename... Options>
+ struct make_traits {
+# ifdef CDS_DOXYGEN_INVOKED
+ typedef implementation_defined type; ///< Metafunction result
+# else
+ typedef typename cds::opt::make_options<
+ typename cds::opt::find_type_traits< traits, Options... >::type
+ , Options...
+ >::type type;
+# endif
+ };
+ } // namespace basket_queue
+
//@cond
namespace details {
- template <typename GC, typename T, CDS_DECL_OPTIONS7>
+ template <typename GC, typename T, typename Traits>
struct make_basket_queue
{
typedef GC gc;
typedef T value_type;
-
- struct default_options {
- typedef cds::backoff::empty back_off;
- typedef CDS_DEFAULT_ALLOCATOR allocator;
- typedef atomicity::empty_item_counter item_counter;
- typedef intrusive::basket_queue::dummy_stat stat;
- typedef opt::v::relaxed_ordering memory_model;
- enum { alignment = opt::cache_line_alignment };
- };
-
- typedef typename opt::make_options<
- typename cds::opt::find_type_traits< default_options, CDS_OPTIONS7 >::type
- ,CDS_OPTIONS7
- >::type options;
+ typedef Traits traits;
struct node_type: public intrusive::basket_queue::node< gc >
{
node_type( const value_type& val )
: m_value( val )
{}
-# ifdef CDS_EMPLACE_SUPPORT
template <typename... Args>
node_type( Args&&... args )
: m_value( std::forward<Args>(args)...)
{}
-# else
- node_type()
- {}
-# endif
};
- typedef typename options::allocator::template rebind<node_type>::other allocator_type;
+ typedef typename traits::allocator::template rebind<node_type>::other allocator_type;
typedef cds::details::Allocator< node_type, allocator_type > cxx_allocator;
struct node_deallocator
}
};
- typedef intrusive::BasketQueue< gc,
- node_type
- ,intrusive::opt::hook<
- intrusive::basket_queue::base_hook< opt::gc<gc> >
- >
- ,opt::back_off< typename options::back_off >
- ,intrusive::opt::disposer< node_deallocator >
- ,opt::item_counter< typename options::item_counter >
- ,opt::stat< typename options::stat >
- ,opt::alignment< options::alignment >
- ,opt::memory_model< typename options::memory_model >
- > type;
+ struct intrusive_traits : public traits
+ {
+ typedef cds::intrusive::basket_queue::base_hook< opt::gc<gc> > hook;
+ typedef node_deallocator disposer;
+ static CDS_CONSTEXPR const cds::intrusive::opt::link_check_type link_checker = cds::intrusive::basket_queue::traits::link_checker;
+ };
+
+ typedef cds::intrusive::BasketQueue< gc, node_type, intrusive_traits > type;
};
}
//@endcond
<b>Key idea</b>
- In the \93basket\94 approach, instead of
+ In the 'basket' approach, instead of
the traditional ordered list of nodes, the queue consists of an ordered list of groups
of nodes (logical baskets). The order of nodes in each basket need not be specified, and in
fact, it is easiest to maintain them in LIFO order. The baskets fulfill the following basic
rules:
- - Each basket has a time interval in which all its nodes\92 enqueue operations overlap.
+ - Each basket has a time interval in which all its nodes' enqueue operations overlap.
- The baskets are ordered by the order of their respective time intervals.
- - For each basket, its nodes\92 dequeue operations occur after its time interval.
+ - For each basket, its nodes' dequeue operations occur after its time interval.
- The dequeue operations are performed according to the order of baskets.
Two properties define the FIFO order of nodes:
In algorithms such as the MS-queue or optimistic
queue, threads enqueue items by applying a Compare-and-swap (CAS) operation to the
- queue\92s tail pointer, and all the threads that fail on a particular CAS operation (and also
+ queue's tail pointer, and all the threads that fail on a particular CAS operation (and also
the winner of that CAS) overlap in time. In particular, they share the time interval of
the CAS operation itself. Hence, all the threads that fail to CAS on the tail-node of
the queue may be inserted into the same basket. By integrating the basket-mechanism
onto the new tail, can now be utilized to insert the failed operations into the basket,
allowing enqueues to complete sooner. In the meantime, the next successful CAS operations
by enqueues allow new baskets to be formed down the list, and these can be
- filled concurrently. Moreover, the failed operations don\92t retry their link attempt on the
+ filled concurrently. Moreover, the failed operations don't retry their link attempt on the
new tail, lowering the overall contention on it. This leads to a queue
algorithm that unlike all former concurrent queue algorithms requires virtually no tuning
of the backoff mechanisms to reduce contention, making the algorithm an attractive
Template arguments:
- - \p GC - garbage collector type: gc::HP, gc::HRC, gc::PTB
- - \p T is a type stored in the queue. It should be default-constructible, copy-constructible, assignable type.
- - \p Options - options
-
- Permissible \p Options:
- - opt::allocator - allocator (like \p std::allocator). Default is \ref CDS_DEFAULT_ALLOCATOR
- - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used
- - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter
- - opt::stat - the type to gather internal statistics for debugging and profiling purposes.
- Possible option value are: intrusive::basket_queue::stat, intrusive::basket_queue::dummy_stat (the default),
- user-provided class that supports intrusive::basket_queue::stat interface.
- Generic option intrusive::queue_stat and intrusive::queue_dummy_stat are acceptable too, however,
- they will be automatically converted to intrusive::basket_queue::stat and intrusive::basket_queue::dummy_stat
- respectively.
- - opt::alignment - the alignment for internal queue data. Default is opt::cache_line_alignment
- - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
- or opt::v::sequential_consistent (sequentially consisnent memory model).
+ - \p GC - garbage collector type: \p gc::HP, \p gc::DHP
+ - \p T - type of value to be stored in the queue
+ - \p Traits - queue traits, default is \p basket_queue::traits. You can use \p basket_queue::make_traits
+ metafunction to make your traits or just derive your traits from \p %basket_queue::traits:
+ \code
+ struct myTraits: public cds::container::basket_queue::traits {
+ typedef cds::intrusive::basket_queue::stat<> stat;
+ typedef cds::atomicity::item_counter item_counter;
+ };
+ typedef cds::container::BasketQueue< cds::gc::HP, Foo, myTraits > myQueue;
+
+ // Equivalent make_traits example:
+ typedef cds::container::BasketQueue< cds::gc::HP, Foo,
+ typename cds::container::basket_queue::make_traits<
+ cds::opt::stat< cds::container::basket_queue::stat<> >,
+ cds::opt::item_counter< cds::atomicity::item_counter >
+ >::type
+ > myQueue;
+ \endcode
*/
- template <typename GC, typename T, CDS_DECL_OPTIONS7>
+ template <typename GC, typename T, typename Traits = basket_queue::traits >
class BasketQueue:
#ifdef CDS_DOXYGEN_INVOKED
- intrusive::BasketQueue< GC, intrusive::basket_queue::node< T >, Options... >
+ private intrusive::BasketQueue< GC, intrusive::basket_queue::node< T >, Traits >
#else
- details::make_basket_queue< GC, T, CDS_OPTIONS7 >::type
+ protected details::make_basket_queue< GC, T, Traits >::type
#endif
{
//@cond
- typedef details::make_basket_queue< GC, T, CDS_OPTIONS7 > options;
- typedef typename options::type base_class;
+ typedef details::make_basket_queue< GC, T, Traits > maker;
+ typedef typename maker::type base_class;
//@endcond
public:
/// Rebind template arguments
- template <typename GC2, typename T2, CDS_DECL_OTHER_OPTIONS7>
+ template <typename GC2, typename T2, typename Traits2>
struct rebind {
- typedef BasketQueue< GC2, T2, CDS_OTHER_OPTIONS7> other ; ///< Rebinding result
+ typedef BasketQueue< GC2, T2, Traits2> other ; ///< Rebinding result
};
public:
- typedef T value_type ; ///< Value type stored in the queue
+ typedef GC gc; ///< Garbage collector
+ typedef T value_type; ///< Type of value to be stored in the queue
+ typedef Traits traits; ///< Queue's traits
- typedef typename base_class::gc gc ; ///< Garbage collector used
- typedef typename base_class::back_off back_off ; ///< Back-off strategy used
- typedef typename options::allocator_type allocator_type ; ///< Allocator type used for allocate/deallocate the nodes
- typedef typename base_class::item_counter item_counter ; ///< Item counting policy used
- typedef typename base_class::stat stat ; ///< Internal statistics policy used
- typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
+ typedef typename base_class::back_off back_off; ///< Back-off strategy used
+ typedef typename maker::allocator_type allocator_type; ///< Allocator type used for allocate/deallocate the nodes
+ typedef typename base_class::item_counter item_counter; ///< Item counting policy used
+ typedef typename base_class::stat stat; ///< Internal statistics policy used
+ typedef typename base_class::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
protected:
- typedef typename options::node_type node_type ; ///< queue node type (derived from intrusive::single_link::node)
+ typedef typename maker::node_type node_type; ///< queue node type (derived from intrusive::basket_queue::node)
//@cond
- typedef typename options::cxx_allocator cxx_allocator;
- typedef typename options::node_deallocator node_deallocator; // deallocate node
- typedef typename base_class::node_traits node_traits;
+ typedef typename maker::cxx_allocator cxx_allocator;
+ typedef typename maker::node_deallocator node_deallocator; // deallocate node
+ typedef typename base_class::node_traits node_traits;
//@endcond
protected:
{
return cxx_allocator().New( val );
}
-# ifdef CDS_EMPLACE_SUPPORT
template <typename... Args>
static node_type * alloc_node_move( Args&&... args )
{
return cxx_allocator().MoveNew( std::forward<Args>( args )... );
}
-# endif
static void free_node( node_type * p )
{
node_deallocator()( p );
free_node( pNode );
}
};
- typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
+ typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
//@endcond
public:
~BasketQueue()
{}
- /// Returns queue's item count
- /** \copydetails cds::intrusive::BasketQueue::size()
- */
- size_t size() const
- {
- return base_class::size();
- }
-
- /// Returns reference to internal statistics
- const stat& statistics() const
- {
- return base_class::statistics();
- }
-
/// Enqueues \p val value into the queue.
/**
The function makes queue node in dynamic memory calling copy constructor for \p val
- and then it calls intrusive::BasketQueue::enqueue.
+ and then it calls \p intrusive::BasketQueue::enqueue().
Returns \p true if success, \p false otherwise.
*/
- bool enqueue( const value_type& val )
+ bool enqueue( value_type const& val )
{
scoped_node_ptr p( alloc_node(val));
if ( base_class::enqueue( *p )) {
return false;
}
- /// Enqueues \p data to queue using copy functor
+ /// Enqueues \p data to queue using a functor
/**
- \p Func is a functor called to copy value \p data of type \p Type
- which may be differ from type \p T stored in the queue.
- The functor's interface is:
+ \p Func is a functor called to create node.
+ The functor \p f takes one argument - a reference to a new node of type \ref value_type :
\code
- struct myFunctor {
- void operator()(T& dest, Type const& data)
- {
- // // Code to copy \p data to \p dest
- dest = data;
- }
- };
+ cds::container::BasketQueue< cds::gc::HP, Foo > myQueue;
+ Bar bar;
+ myQueue.enqueue_with( [&bar]( Foo& dest ) { dest = bar; } );
\endcode
- You may use \p boost:ref construction to pass functor \p f by reference.
-
- <b>Requirements</b> The functor \p Func should not throw any exception.
*/
- template <typename Type, typename Func>
- bool enqueue( const Type& data, Func f )
+ template <typename Func>
+ bool enqueue_with( Func f )
{
- scoped_node_ptr p( alloc_node());
- cds::unref(f)( p->m_value, data );
+ scoped_node_ptr p( alloc_node() );
+ f( p->m_value );
if ( base_class::enqueue( *p )) {
p.release();
return true;
return false;
}
-# ifdef CDS_EMPLACE_SUPPORT
+ /// Synonym for \p enqueue() function
+ bool push( const value_type& val )
+ {
+ return enqueue( val );
+ }
+
+ /// Synonym for \p enqueue_with() function
+ template <typename Func>
+ bool push_with( Func f )
+ {
+ return enqueue_with( f );
+ }
+
/// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
- /**
- This function is available only for compiler that supports
- variadic template and move semantics
- */
template <typename... Args>
bool emplace( Args&&... args )
{
}
return false;
}
-# endif
-
-
- /// Dequeues a value using copy functor
- /**
- \p Func is a functor called to copy dequeued value to \p dest of type \p Type
- which may be differ from type \p T stored in the queue.
- The functor's interface is:
- \code
- struct myFunctor {
- void operator()(Type& dest, T const& data)
- {
- // Code to copy \p data to \p dest
- dest = data;
- }
- };
- \endcode
- You may use \p boost:ref construction to pass functor \p f by reference.
-
- <b>Requirements</b> The functor \p Func should not throw any exception.
- */
- template <typename Type, typename Func>
- bool dequeue( Type& dest, Func f )
- {
- typename base_class::dequeue_result res;
- if ( base_class::do_dequeue( res, true )) {
- cds::unref(f)( dest, node_traits::to_value_ptr( *res.pNext )->m_value );
- return true;
- }
- return false;
- }
/// Dequeues a value from the queue
/**
*/
bool dequeue( value_type& dest )
{
- typedef cds::details::trivial_assign<value_type, value_type> functor;
- return dequeue( dest, functor() );
+ return dequeue_with( [&dest]( value_type& src ) { dest = src; } );
}
- /// Synonym for \ref enqueue function
- bool push( const value_type& val )
- {
- return enqueue( val );
- }
-
- /// Synonym for template version of \ref enqueue function
- template <typename Type, typename Func>
- bool push( const Type& data, Func f )
+ /// Dequeues a value using a functor
+ /**
+ \p Func is a functor called to copy dequeued value.
+ The functor takes one argument - a reference to removed node:
+ \code
+ cds:container::BasketQueue< cds::gc::HP, Foo > myQueue;
+ Bar bar;
+ myQueue.dequeue_with( [&bar]( Foo& src ) { bar = std::move( src );});
+ \endcode
+ The functor is called only if the queue is not empty.
+ */
+ template <typename Func>
+ bool dequeue_with( Func f )
{
- return enqueue( data, f );
+ typename base_class::dequeue_result res;
+ if ( base_class::do_dequeue( res, true )) {
+ f( node_traits::to_value_ptr( *res.pNext )->m_value );
+ return true;
+ }
+ return false;
}
- /// Synonym for \ref dequeue function
+ /// Synonym for \p dequeue() function
bool pop( value_type& dest )
{
return dequeue( dest );
}
- /// Synonym for template version of \ref dequeue function
- template <typename Type, typename Func>
- bool pop( Type& dest, Func f )
+ /// Synonym for \p dequeue_with() function
+ template <typename Func>
+ bool pop_with( Func f )
{
- return dequeue( dest, f );
+ return dequeue_with( f );
}
/// Checks if the queue is empty
/**
Note that this function is not \p const.
- The function is based on \ref dequeue algorithm.
+ The function is based on \p dequeue() algorithm.
*/
bool empty()
{
{
base_class::clear();
}
+
+ /// Returns queue's item count
+ /** \copydetails cds::intrusive::BasketQueue::size()
+ */
+ size_t size() const
+ {
+ return base_class::size();
+ }
+
+ /// Returns reference to internal statistics
+ const stat& statistics() const
+ {
+ return base_class::statistics();
+ }
+
};
}} // namespace cds::container
-#endif // #ifndef __CDS_CONTAINER_BASKET_QUEUE_H
+#endif // #ifndef CDSLIB_CONTAINER_BASKET_QUEUE_H
projects / libcds.git / blobdiff