-//$$CDS-header$$
+/*
+ This file is a part of libcds - Concurrent Data Structures library
-#ifndef __CDS_INTRUSIVE_BASKET_QUEUE_H
-#define __CDS_INTRUSIVE_BASKET_QUEUE_H
+ (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
-#include <cds/intrusive/base.h>
-#include <cds/details/marked_ptr.h>
-#include <cds/intrusive/queue_stat.h>
-#include <cds/intrusive/single_link_struct.h>
-#include <cds/ref.h>
-#include <cds/intrusive/details/dummy_node_holder.h>
+ 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.
+*/
-#include <cds/details/std/type_traits.h>
+#ifndef CDSLIB_INTRUSIVE_BASKET_QUEUE_H
+#define CDSLIB_INTRUSIVE_BASKET_QUEUE_H
+
+#include <type_traits>
+#include <cds/intrusive/details/single_link_struct.h>
+#include <cds/details/marked_ptr.h>
namespace cds { namespace intrusive {
namespace basket_queue {
/// BasketQueue node
/**
+ Template parameters:
Template parameters:
- GC - garbage collector used
- - Tag - a tag used to distinguish between different implementation
- */
+ - Tag - a \ref cds_intrusive_hook_tag "tag"
+ */
template <class GC, typename Tag = opt::none>
- struct node: public GC::container_node
+ struct node
{
typedef GC gc ; ///< Garbage collector
typedef Tag tag ; ///< tag
- typedef cds::details::marked_ptr<node, 1> marked_ptr ; ///< marked pointer
- typedef typename gc::template atomic_marked_ptr< marked_ptr> atomic_marked_ptr ; ///< atomic marked pointer specific for GC
+ typedef cds::details::marked_ptr<node, 1> marked_ptr; ///< marked pointer
+ typedef typename gc::template atomic_marked_ptr< marked_ptr> atomic_marked_ptr; ///< atomic marked pointer specific for GC
/// Rebind node for other template parameters
template <class GC2, typename Tag2 = tag>
atomic_marked_ptr m_pNext ; ///< pointer to the next node in the container
node()
- : m_pNext( nullptr )
- {}
- };
-
- //@cond
- // Specialization for HRC GC
- template <typename Tag>
- struct node< gc::HRC, Tag>: public gc::HRC::container_node
- {
- typedef gc::HRC gc ; ///< Garbage collector
- typedef Tag tag ; ///< tag
-
- typedef cds::details::marked_ptr<node, 1> marked_ptr ; ///< marked pointer
- typedef typename gc::template atomic_marked_ptr< marked_ptr> atomic_marked_ptr ; ///< atomic marked pointer specific for GC
-
- atomic_marked_ptr m_pNext ; ///< pointer to the next node in the container
-
- node()
- : m_pNext( nullptr )
- {}
-
- protected:
- virtual void cleanUp( cds::gc::hrc::ThreadGC * pGC )
{
- assert( pGC != nullptr );
- typename gc::template GuardArray<2> aGuards( *pGC );
-
- while ( true ) {
- marked_ptr pNext = aGuards.protect( 0, m_pNext );
- if ( pNext.ptr() && pNext->m_bDeleted.load(CDS_ATOMIC::memory_order_acquire) ) {
- marked_ptr p = aGuards.protect( 1, pNext->m_pNext );
- m_pNext.compare_exchange_strong( pNext, p, CDS_ATOMIC::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed );
- continue;
- }
- else {
- break;
- }
- }
- }
-
- virtual void terminate( cds::gc::hrc::ThreadGC * pGC, bool bConcurrent )
- {
- if ( bConcurrent ) {
- marked_ptr pNext = m_pNext.load(CDS_ATOMIC::memory_order_relaxed);
- do {} while ( !m_pNext.compare_exchange_weak( pNext, marked_ptr(), CDS_ATOMIC::memory_order_release, CDS_ATOMIC::memory_order_relaxed ) );
- }
- else {
- m_pNext.store( marked_ptr(), CDS_ATOMIC::memory_order_relaxed );
- }
+ m_pNext.store( marked_ptr(), atomics::memory_order_release );
}
};
- //@endcond
- using single_link::default_hook;
+ using cds::intrusive::single_link::default_hook;
//@cond
- template < typename HookType, CDS_DECL_OPTIONS2>
+ template < typename HookType, typename... Options>
struct hook
{
- typedef typename opt::make_options< default_hook, CDS_OPTIONS2>::type options;
+ typedef typename opt::make_options< default_hook, Options...>::type options;
typedef typename options::gc gc;
typedef typename options::tag tag;
typedef node<gc, tag> node_type;
/**
\p Options are:
- opt::gc - garbage collector used.
- - opt::tag - tag
+ - opt::tag - a \ref cds_intrusive_hook_tag "tag"
*/
- template < CDS_DECL_OPTIONS2 >
- struct base_hook: public hook< opt::base_hook_tag, CDS_OPTIONS2 >
+ template < typename... Options >
+ struct base_hook: public hook< opt::base_hook_tag, Options... >
{};
/// Member hook
\p Options are:
- opt::gc - garbage collector used.
- - opt::tag - tag
+ - opt::tag - a \ref cds_intrusive_hook_tag "tag"
*/
- template < size_t MemberOffset, CDS_DECL_OPTIONS2 >
- struct member_hook: public hook< opt::member_hook_tag, CDS_OPTIONS2 >
+ template < size_t MemberOffset, typename... Options >
+ struct member_hook: public hook< opt::member_hook_tag, Options... >
{
//@cond
static const size_t c_nMemberOffset = MemberOffset;
\p Options are:
- opt::gc - garbage collector used.
- - opt::tag - tag
+ - opt::tag - a \ref cds_intrusive_hook_tag "tag"
*/
- template <typename NodeTraits, CDS_DECL_OPTIONS2 >
- struct traits_hook: public hook< opt::traits_hook_tag, CDS_OPTIONS2 >
+ template <typename NodeTraits, typename... Options >
+ struct traits_hook: public hook< opt::traits_hook_tag, Options... >
{
//@cond
typedef NodeTraits node_traits;
//@endcond
};
-
-#if defined(CDS_CXX11_TEMPLATE_ALIAS_SUPPORT) && !defined(CDS_DOXYGEN_INVOKED)
- template < typename Node, opt::link_check_type LinkType > using get_link_checker = single_link::get_link_checker< Node, LinkType >;
-#else
- /// Metafunction for selecting appropriate link checking policy
- template < typename Node, opt::link_check_type LinkType >
- struct get_link_checker: public single_link::get_link_checker< Node, LinkType >
- {};
-
-#endif
-
- /// Basket queue internal statistics. May be used for debugging or profiling
+ /// BasketQueue internal statistics. May be used for debugging or profiling
/**
- Basket queue statistics derives from cds::intrusive::queue_stat
- and extends it by two additional fields specific for the algorithm.
+ Template argument \p Counter defines type of counter.
+ Default is \p cds::atomicity::event_counter, that is weak, i.e. it is not guaranteed
+ strict event counting.
+ You may use stronger type of counter like as \p cds::atomicity::item_counter,
+ or even integral type, for example, \p int.
*/
template <typename Counter = cds::atomicity::event_counter >
- struct stat: public cds::intrusive::queue_stat< Counter >
+ struct stat
{
- //@cond
- typedef cds::intrusive::queue_stat< Counter > base_class;
- typedef typename base_class::counter_type counter_type;
- //@endcond
-
- counter_type m_TryAddBasket ; ///< Count of attemps adding new item to a basket (only or BasketQueue, for other queue this metric is not used)
- counter_type m_AddBasketCount ; ///< Count of events "Enqueue a new item into basket" (only or BasketQueue, for other queue this metric is not used)
-
+ typedef Counter counter_type; ///< Counter type
+
+ counter_type m_EnqueueCount; ///< Enqueue call count
+ counter_type m_DequeueCount; ///< Dequeue call count
+ counter_type m_EnqueueRace; ///< Count of enqueue race conditions encountered
+ counter_type m_DequeueRace; ///< Count of dequeue race conditions encountered
+ counter_type m_AdvanceTailError;///< Count of "advance tail failed" events
+ counter_type m_BadTail; ///< Count of events "Tail is not pointed to the last item in the queue"
+ counter_type m_TryAddBasket; ///< Count of attemps adding new item to a basket (only or BasketQueue, for other queue this metric is not used)
+ counter_type m_AddBasketCount; ///< Count of events "Enqueue a new item into basket" (only or BasketQueue, for other queue this metric is not used)
+ counter_type m_EmptyDequeue; ///< Count of dequeue from empty queue
+
+ /// Register enqueue call
+ void onEnqueue() { ++m_EnqueueCount; }
+ /// Register dequeue call
+ void onDequeue() { ++m_DequeueCount; }
+ /// Register enqueue race event
+ void onEnqueueRace() { ++m_EnqueueRace; }
+ /// Register dequeue race event
+ void onDequeueRace() { ++m_DequeueRace; }
+ /// Register "advance tail failed" event
+ void onAdvanceTailFailed() { ++m_AdvanceTailError; }
+ /// Register event "Tail is not pointed to last item in the queue"
+ void onBadTail() { ++m_BadTail; }
/// Register an attempt t add new item to basket
void onTryAddBasket() { ++m_TryAddBasket; }
/// Register event "Enqueue a new item into basket" (only or BasketQueue, for other queue this metric is not used)
void onAddBasket() { ++m_AddBasketCount; }
+ /// Register dequeuing from empty queue
+ void onEmptyDequeue() { ++m_EmptyDequeue; }
+
//@cond
void reset()
{
- base_class::reset();
+ m_EnqueueCount.reset();
+ m_DequeueCount.reset();
+ m_EnqueueRace.reset();
+ m_DequeueRace.reset();
+ m_AdvanceTailError.reset();
+ m_BadTail.reset();
m_TryAddBasket.reset();
m_AddBasketCount.reset();
+ m_EmptyDequeue.reset();
}
stat& operator +=( stat const& s )
{
- base_class::operator +=( s );
- m_TryAddBasket += s.m_TryAddBasket.get();
+ m_EnqueueCount += s.m_EnqueueCount.get();
+ m_DequeueCount += s.m_DequeueCount.get();
+ m_EnqueueRace += s.m_EnqueueRace.get();
+ m_DequeueRace += s.m_DequeueRace.get();
+ m_AdvanceTailError += s.m_AdvanceTailError.get();
+ m_BadTail += s.m_BadTail.get();
+ m_TryAddBasket += s.m_TryAddBasket.get();
m_AddBasketCount += s.m_AddBasketCount.get();
+ m_EmptyDequeue += s.m_EmptyDequeue.get();
return *this;
}
//@endcond
};
- /// Dummy basket queue statistics - no counting is performed. Support interface like \ref stat
- struct dummy_stat: public cds::intrusive::queue_dummy_stat
+ /// Dummy BasketQueue statistics - no counting is performed, no overhead. Support interface like \p basket_queue::stat
+ struct empty_stat
{
//@cond
- void onTryAddBasket() {}
- void onAddBasket() {}
+ void onEnqueue() const {}
+ void onDequeue() const {}
+ void onEnqueueRace() const {}
+ void onDequeueRace() const {}
+ void onAdvanceTailFailed() const {}
+ void onBadTail() const {}
+ void onTryAddBasket() const {}
+ void onAddBasket() const {}
+ void onEmptyDequeue() const {}
void reset() {}
- dummy_stat& operator +=( dummy_stat const& )
+ empty_stat& operator +=( empty_stat const& )
{
return *this;
}
//@endcond
};
+ /// BasketQueue default type traits
+ struct traits
+ {
+ /// Back-off strategy
+ typedef cds::backoff::empty back_off;
+
+ /// Hook, possible types are \p basket_queue::base_hook, \p basket_queue::member_hook, \p basket_queue::traits_hook
+ typedef basket_queue::base_hook<> hook;
+
+ /// The functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used for dequeuing
+ typedef opt::v::empty_disposer disposer;
+
+ /// 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;
+
+ /// Link checking, see \p cds::opt::link_checker
+ static CDS_CONSTEXPR const opt::link_check_type link_checker = opt::debug_check_link;
+
+ /// 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::hook - hook used. Possible hooks are: \p basket_queue::base_hook, \p basket_queue::member_hook, \p basket_queue::traits_hook.
+ If the option is not specified, \p %basket_queue::base_hook<> is used.
+ - \p opt::back_off - back-off strategy used, default is \p cds::backoff::empty.
+ - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used
+ when dequeuing.
+ - \p opt::link_checker - the type of node's link fields checking. Default is \p opt::debug_check_link
+ - \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
+ - \p 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 (internal statistics disabled).
+ - \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::intrusive::BasketQueue< cds::gc::HP, Foo,
+ typename cds::intrusive::basket_queue::make_traits<
+ cds::intrusive::opt:hook< cds::intrusive::basket_queue::base_hook< cds::opt::gc<cds:gc::HP> >>,
+ 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
/// Basket lock-free queue (intrusive variant)
<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 FIFO 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
out-of-the-box queue.
- In order to enqueue, just as in MSQueue, a thread first tries to link the new node to
+ In order to enqueue, just as in \p MSQueue, a thread first tries to link the new node to
the last node. If it failed to do so, then another thread has already succeeded. Thus it
tries to insert the new node into the new basket that was created by the winner thread.
To dequeue a node, a thread first reads the head of the queue to obtain the
oldest basket. It may then dequeue any node in the oldest basket.
<b>Template arguments:</b>
- - \p GC - garbage collector type: gc::HP, gc::HRC, gc::PTB
- - \p T - type to be stored in the queue, should be convertible to \ref single_link::node
- - \p Options - options
-
- <b>Type of node</b>: \ref single_link::node
-
- \p Options are:
- - opt::hook - hook used. Possible values are: basket_queue::base_hook, basket_queue::member_hook, basket_queue::traits_hook.
- If the option is not specified, <tt>basket_queue::base_hook<></tt> is used.
- For Gidenstam's gc::HRC, only basket_queue::base_hook is supported.
- - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used.
- - opt::disposer - the functor used for dispose removed items. Default is opt::v::empty_disposer. This option is used
- in \ref dequeue function.
- - opt::link_checker - the type of node's link fields checking. Default is \ref opt::debug_check_link
- Note: for gc::HRC garbage collector, link checking policy is always selected as \ref opt::always_check_link.
- - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter (no item counting feature)
- - opt::stat - the type to gather internal statistics.
- Possible option value are: \ref basket_queue::stat, \ref basket_queue::dummy_stat,
- user-provided class that supports basket_queue::stat interface.
- Default is \ref basket_queue::dummy_stat.
- Generic option intrusive::queue_stat and intrusive::queue_dummy_stat are acceptable too, however,
- they will be automatically converted to basket_queue::stat and 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).
-
- Garbage collecting schema \p GC must be consistent with the basket_queue::node GC.
+ - \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::intrusive::basket_queue::traits {
+ typedef cds::intrusive::basket_queue::stat<> stat;
+ typedef cds::atomicity::item_counter item_counter;
+ };
+ typedef cds::intrusive::BasketQueue< cds::gc::HP, Foo, myTraits > myQueue;
+
+ // Equivalent make_traits example:
+ typedef cds::intrusive::BasketQueue< cds::gc::HP, Foo,
+ typename cds::intrusive::basket_queue::make_traits<
+ cds::opt::stat< cds::intrusive::basket_queue::stat<> >,
+ cds::opt::item_counter< cds::atomicity::item_counter >
+ >::type
+ > myQueue;
+ \endcode
+
+ Garbage collecting schema \p GC must be consistent with the \p basket_queue::node GC.
\par About item disposing
- Like MSQueue, the Baskets queue algo has a key feature: even if the queue is empty it contains one item that is "dummy" one from
- the standpoint of the algo. See \ref dequeue function doc for explanation.
+ Like \p MSQueue, the Baskets queue algo has a key feature: even if the queue is empty it contains one item that is "dummy" one from
+ the standpoint of the algo. See \p dequeue() function doc for explanation.
\par Examples
\code
}
};
- typedef ci::BasketQueue< hp_gc,
- Foo
- ,ci::opt::hook<
- ci::basket_queue::base_hook< ci::opt::gc<hp_gc> >
- >
- ,ci::opt::disposer< fooDisposer >
- > fooQueue;
+ struct fooTraits: public ci::basket_queue::traits {
+ typedef ci::basket_queue::base_hook< ci::opt::gc<hp_gc> > hook;
+ typedef fooDisposer disposer;
+ };
+ typedef ci::BasketQueue< hp_gc, Foo, fooTraits > fooQueue;
// BasketQueue with Hazard Pointer garbage collector,
// member hook + item disposer + item counter,
- // without alignment of internal queue data:
+ // without padding of internal queue data:
struct Bar
{
// Your data
ci::basket_queue::node< hp_gc > hMember;
};
- typedef ci::BasketQueue< hp_gc,
- Foo
- ,ci::opt::hook<
- ci::basket_queue::member_hook<
- offsetof(Bar, hMember)
- ,ci::opt::gc<hp_gc>
+ struct barTraits: public
+ ci::basket_queue::make_traits<
+ ci::opt::hook<
+ ci::basket_queue::member_hook<
+ offsetof(Bar, hMember)
+ ,ci::opt::gc<hp_gc>
+ >
>
- >
- ,ci::opt::disposer< fooDisposer >
- ,cds::opt::item_counter< cds::atomicity::item_counter >
- ,cds::opt::alignment< cds::opt::no_special_alignment >
- > barQueue;
+ ,ci::opt::disposer< fooDisposer >
+ ,cds::opt::item_counter< cds::atomicity::item_counter >
+ ,cds::opt::padding< cds::opt::no_special_padding >
+ >::type
+ {};
+ typedef ci::BasketQueue< hp_gc, Bar, barTraits > barQueue;
\endcode
*/
- template <typename GC, typename T, CDS_DECL_OPTIONS9>
+ template <typename GC, typename T, typename Traits = basket_queue::traits >
class BasketQueue
{
- //@cond
- struct default_options
- {
- typedef cds::backoff::empty back_off;
- typedef basket_queue::base_hook<> hook;
- typedef opt::v::empty_disposer disposer;
- typedef atomicity::empty_item_counter item_counter;
- typedef basket_queue::dummy_stat stat;
- typedef opt::v::relaxed_ordering memory_model;
- static const opt::link_check_type link_checker = opt::debug_check_link;
- enum { alignment = opt::cache_line_alignment };
- };
- //@endcond
-
public:
- //@cond
- typedef typename opt::make_options<
- typename cds::opt::find_type_traits< default_options, CDS_OPTIONS9 >::type
- ,CDS_OPTIONS9
- >::type options;
-
- typedef typename std::conditional<
- std::is_same<typename options::stat, cds::intrusive::queue_stat<> >::value
- ,basket_queue::stat<>
- ,typename std::conditional<
- std::is_same<typename options::stat, cds::intrusive::queue_dummy_stat>::value
- ,basket_queue::dummy_stat
- ,typename options::stat
- >::type
- >::type stat_type_;
-
- //@endcond
-
- public:
- typedef T value_type ; ///< type of value stored in the queue
- typedef typename options::hook hook ; ///< hook type
- typedef typename hook::node_type node_type ; ///< node type
- typedef typename options::disposer disposer ; ///< disposer used
- typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
- typedef typename basket_queue::get_link_checker< node_type, options::link_checker >::type link_checker ; ///< link checker
-
- typedef GC gc ; ///< Garbage collector
- typedef typename options::back_off back_off ; ///< back-off strategy
- typedef typename options::item_counter item_counter ; ///< Item counting policy used
-#ifdef CDS_DOXYGEN_INVOKED
- typedef typename options::stat stat ; ///< Internal statistics policy used
-#else
- typedef stat_type_ stat;
-#endif
- typedef typename options::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
+ typedef GC gc; ///< Garbage collector
+ typedef T value_type; ///< type of value stored in the queue
+ typedef Traits traits; ///< Queue traits
+ typedef typename traits::hook hook; ///< hook type
+ typedef typename hook::node_type node_type; ///< node type
+ typedef typename traits::disposer disposer; ///< disposer used
+ typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
+ typedef typename single_link::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
+
+ typedef typename traits::back_off back_off; ///< back-off strategy
+ typedef typename traits::item_counter item_counter; ///< Item counting policy used
+ typedef typename traits::stat stat; ///< Internal statistics policy used
+ typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
/// Rebind template arguments
- template <typename GC2, typename T2, CDS_DECL_OTHER_OPTIONS9>
+ template <typename GC2, typename T2, typename Traits2>
struct rebind {
- typedef BasketQueue< GC2, T2, CDS_OTHER_OPTIONS9> other ; ///< Rebinding result
+ typedef BasketQueue< GC2, T2, Traits2> other ; ///< Rebinding result
};
- static const size_t m_nHazardPtrCount = 6 ; ///< Count of hazard pointer required for the algorithm
+ static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 6 ; ///< Count of hazard pointer required for the algorithm
protected:
//@cond
-
- struct internal_disposer
- {
- void operator()( value_type * p )
- {
- assert( p != nullptr );
-
- BasketQueue::clear_links( node_traits::to_node_ptr(p) );
- disposer()( p );
- }
- };
-
typedef typename node_type::marked_ptr marked_ptr;
typedef typename node_type::atomic_marked_ptr atomic_marked_ptr;
- typedef intrusive::node_to_value<BasketQueue> node_to_value;
- typedef typename opt::details::alignment_setter< atomic_marked_ptr, options::alignment >::type aligned_node_ptr;
- typedef typename opt::details::alignment_setter<
- cds::intrusive::details::dummy_node< gc, node_type>,
- options::alignment
- >::type dummy_node_type;
-
+ // GC and node_type::gc must be the same
+ static_assert( std::is_same<gc, typename node_type::gc>::value, "GC and node_type::gc must be the same");
//@endcond
- aligned_node_ptr m_pHead ; ///< Queue's head pointer (aligned)
- aligned_node_ptr m_pTail ; ///< Queue's tail pointer (aligned)
-
- dummy_node_type m_Dummy ; ///< dummy node
+ atomic_marked_ptr m_pHead ; ///< Queue's head pointer (aligned)
+ //@cond
+ typename opt::details::apply_padding< atomic_marked_ptr, traits::padding >::padding_type pad1_;
+ //@endcond
+ atomic_marked_ptr m_pTail ; ///< Queue's tail pointer (aligned)
+ //@cond
+ typename opt::details::apply_padding< atomic_marked_ptr, traits::padding >::padding_type pad2_;
+ //@endcond
+ node_type m_Dummy ; ///< dummy node
+ //@cond
+ typename opt::details::apply_padding< node_type, traits::padding >::padding_type pad3_;
+ //@endcond
item_counter m_ItemCounter ; ///< Item counter
stat m_Stat ; ///< Internal statistics
//@cond
//@cond
- template <size_t Count>
- static marked_ptr guard_node( typename gc::template GuardArray<Count>& g, size_t idx, atomic_marked_ptr const& p )
- {
- marked_ptr pg;
- while ( true ) {
- pg = p.load( memory_model::memory_order_relaxed );
- g.assign( idx, node_traits::to_value_ptr( pg.ptr() ) );
- if ( p.load( memory_model::memory_order_acquire) == pg ) {
- return pg;
- }
- }
- }
-
- static marked_ptr guard_node( typename gc::Guard& g, atomic_marked_ptr const& p )
- {
- marked_ptr pg;
- while ( true ) {
- pg = p.load( memory_model::memory_order_relaxed );
- g.assign( node_traits::to_value_ptr( pg.ptr() ) );
- if ( p.load( memory_model::memory_order_acquire) == pg ) {
- return pg;
- }
- }
- }
-
struct dequeue_result {
typename gc::template GuardArray<3> guards;
node_type * pNext;
marked_ptr pNext;
while ( true ) {
- h = guard_node( res.guards, 0, m_pHead );
- t = guard_node( res.guards, 1, m_pTail );
- pNext = guard_node( res.guards, 2, h->m_pNext );
-
- if ( h == m_pHead.load( memory_model::memory_order_acquire ) ) {
- if ( h.ptr() == t.ptr() ) {
- if ( !pNext.ptr() )
+ h = res.guards.protect( 0, m_pHead, []( marked_ptr p ) -> value_type * { return node_traits::to_value_ptr( p.ptr());});
+ t = res.guards.protect( 1, m_pTail, []( marked_ptr p ) -> value_type * { return node_traits::to_value_ptr( p.ptr());});
+ pNext = res.guards.protect( 2, h->m_pNext, []( marked_ptr p ) -> value_type * { return node_traits::to_value_ptr( p.ptr());});
+
+ if ( h == m_pHead.load( memory_model::memory_order_acquire )) {
+ if ( h.ptr() == t.ptr()) {
+ if ( !pNext.ptr()) {
+ m_Stat.onEmptyDequeue();
return false;
+ }
{
typename gc::Guard g;
while ( pNext->m_pNext.load(memory_model::memory_order_relaxed).ptr() && m_pTail.load(memory_model::memory_order_relaxed) == t ) {
- pNext = guard_node( g, pNext->m_pNext );
- res.guards.assign( 2, g.template get<value_type>() );
+ pNext = g.protect( pNext->m_pNext, []( marked_ptr p ) -> value_type * { return node_traits::to_value_ptr( p.ptr());});
+ res.guards.copy( 2, g );
}
}
- m_pTail.compare_exchange_weak( t, marked_ptr(pNext.ptr()), memory_model::memory_order_release, memory_model::memory_order_relaxed );
+ m_pTail.compare_exchange_weak( t, marked_ptr(pNext.ptr()), memory_model::memory_order_acquire, atomics::memory_order_relaxed );
}
else {
marked_ptr iter( h );
while ( pNext.ptr() && pNext.bits() && iter.ptr() != t.ptr() && m_pHead.load(memory_model::memory_order_relaxed) == h ) {
iter = pNext;
- g.assign( res.guards.template get<value_type>(2) );
- pNext = guard_node( res.guards, 2, pNext->m_pNext );
+ g.assign( res.guards.template get<value_type>(2));
+ pNext = res.guards.protect( 2, pNext->m_pNext, []( marked_ptr p ) -> value_type * { return node_traits::to_value_ptr( p.ptr());});
++hops;
}
if ( m_pHead.load(memory_model::memory_order_relaxed) != h )
continue;
- if ( iter.ptr() == t.ptr() )
+ if ( iter.ptr() == t.ptr())
free_chain( h, iter );
else if ( bDeque ) {
res.pNext = pNext.ptr();
- if ( iter->m_pNext.compare_exchange_weak( pNext, marked_ptr( pNext.ptr(), 1 ), memory_model::memory_order_release, memory_model::memory_order_relaxed ) ) {
+ if ( iter->m_pNext.compare_exchange_weak( pNext, marked_ptr( pNext.ptr(), 1 ), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
if ( hops >= m_nMaxHops )
free_chain( h, pNext );
break;
{
// "head" and "newHead" are guarded
- if ( m_pHead.compare_exchange_strong( head, marked_ptr(newHead.ptr()), memory_model::memory_order_release, memory_model::memory_order_relaxed ))
+ if ( m_pHead.compare_exchange_strong( head, marked_ptr(newHead.ptr()), memory_model::memory_order_release, atomics::memory_order_relaxed ))
{
typename gc::template GuardArray<2> guards;
- guards.assign( 0, node_traits::to_value_ptr(head.ptr()) );
- while ( head.ptr() != newHead.ptr() ) {
- marked_ptr pNext = guard_node( guards, 1, head->m_pNext );
+ guards.assign( 0, node_traits::to_value_ptr(head.ptr()));
+ while ( head.ptr() != newHead.ptr()) {
+ marked_ptr pNext = guards.protect( 1, head->m_pNext, []( marked_ptr p ) -> value_type * { return node_traits::to_value_ptr( p.ptr());});
assert( pNext.bits() != 0 );
- dispose_node( head.ptr() );
- guards.assign( 0, guards.template get<value_type>(1) );
+ dispose_node( head.ptr());
+ guards.copy( 0, 1 );
head = pNext;
}
}
void dispose_node( node_type * p )
{
- if ( p != m_Dummy.get() ) {
- gc::template retire<internal_disposer>( node_traits::to_value_ptr(p) );
+ if ( p != &m_Dummy ) {
+ struct internal_disposer
+ {
+ void operator()( value_type * p )
+ {
+ assert( p != nullptr );
+ BasketQueue::clear_links( node_traits::to_node_ptr( p ));
+ disposer()(p);
+ }
+ };
+ gc::template retire<internal_disposer>( node_traits::to_value_ptr(p));
}
- else
- m_Dummy.retire();
}
//@endcond
public:
/// Initializes empty queue
BasketQueue()
- : m_pHead( nullptr )
- , m_pTail( nullptr )
+ : m_pHead( &m_Dummy )
+ , m_pTail( &m_Dummy )
, m_nMaxHops( 3 )
- {
- // GC and node_type::gc must be the same
- static_assert(( std::is_same<gc, typename node_type::gc>::value ), "GC and node_type::gc must be the same");
-
- // For cds::gc::HRC, only one base_hook is allowed
- static_assert((
- std::conditional<
- std::is_same<gc, cds::gc::HRC>::value,
- std::is_same< typename hook::hook_type, opt::base_hook_tag >,
- boost::true_type
- >::type::value
- ), "For cds::gc::HRC, only base_hook is allowed");
-
- // Head/tail initialization should be made via store call
- // because of gc::HRC manages reference counting
- m_pHead.store( marked_ptr(m_Dummy.get()), memory_model::memory_order_relaxed );
- m_pTail.store( marked_ptr(m_Dummy.get()), memory_model::memory_order_relaxed );
- }
+ {}
/// Destructor clears the queue
/**
dispose_node( pHead );
}
- /// Returns queue's item count
- /**
- The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
- this function always returns 0.
-
- <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the queue
- is empty. To check queue emptyness use \ref empty() method.
- */
- size_t size() const
- {
- return m_ItemCounter.value();
- }
-
- /// Returns reference to internal statistics
- const stat& statistics() const
- {
- return m_Stat;
- }
-
/// Enqueues \p val value into the queue.
/** @anchor cds_intrusive_BasketQueue_enqueue
The function always returns \p true.
link_checker::is_empty( pNew );
typename gc::Guard guard;
+ typename gc::Guard gNext;
back_off bkoff;
marked_ptr t;
while ( true ) {
- t = guard_node( guard, m_pTail );
+ t = guard.protect( m_pTail, []( marked_ptr p ) -> value_type * { return node_traits::to_value_ptr( p.ptr());});
- marked_ptr pNext = t->m_pNext.load(memory_model::memory_order_acquire );
+ marked_ptr pNext = t->m_pNext.load(memory_model::memory_order_relaxed );
if ( pNext.ptr() == nullptr ) {
- pNew->m_pNext.store( marked_ptr(), memory_model::memory_order_release );
- if ( t->m_pNext.compare_exchange_weak( pNext, marked_ptr(pNew), memory_model::memory_order_release, memory_model::memory_order_relaxed ) ) {
- if ( !m_pTail.compare_exchange_strong( t, marked_ptr(pNew), memory_model::memory_order_release, memory_model::memory_order_relaxed ))
+ pNew->m_pNext.store( marked_ptr(), memory_model::memory_order_relaxed );
+ if ( t->m_pNext.compare_exchange_weak( pNext, marked_ptr(pNew), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
+ if ( !m_pTail.compare_exchange_strong( t, marked_ptr(pNew), memory_model::memory_order_release, atomics::memory_order_relaxed ))
m_Stat.onAdvanceTailFailed();
break;
}
m_Stat.onTryAddBasket();
// Reread tail next
- typename gc::Guard gNext;
-
try_again:
- pNext = guard_node( gNext, t->m_pNext );
+ pNext = gNext.protect( t->m_pNext, []( marked_ptr p ) -> value_type * { return node_traits::to_value_ptr( p.ptr());});
// add to the basket
- if ( m_pTail.load(memory_model::memory_order_relaxed) == t
+ if ( m_pTail.load( memory_model::memory_order_relaxed ) == t
&& t->m_pNext.load( memory_model::memory_order_relaxed) == pNext
- && !pNext.bits() )
+ && !pNext.bits())
{
bkoff();
- pNew->m_pNext.store( pNext, memory_model::memory_order_release );
- if ( t->m_pNext.compare_exchange_weak( pNext, marked_ptr( pNew ), memory_model::memory_order_release, memory_model::memory_order_relaxed )) {
+ pNew->m_pNext.store( pNext, memory_model::memory_order_relaxed );
+ if ( t->m_pNext.compare_exchange_weak( pNext, marked_ptr( pNew ), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
m_Stat.onAddBasket();
break;
}
// Tail is misplaced, advance it
typename gc::template GuardArray<2> g;
- g.assign( 0, node_traits::to_value_ptr( pNext.ptr() ) );
- if ( t->m_pNext.load( memory_model::memory_order_relaxed ) != pNext ) {
+ g.assign( 0, node_traits::to_value_ptr( pNext.ptr()));
+ if ( m_pTail.load( memory_model::memory_order_acquire ) != t
+ || t->m_pNext.load( memory_model::memory_order_relaxed ) != pNext )
+ {
m_Stat.onEnqueueRace();
bkoff();
continue;
marked_ptr p;
bool bTailOk = true;
- while ( (p = pNext->m_pNext.load( memory_model::memory_order_relaxed )).ptr() != nullptr )
+ while ( (p = pNext->m_pNext.load( memory_model::memory_order_acquire )).ptr() != nullptr )
{
bTailOk = m_pTail.load( memory_model::memory_order_relaxed ) == t;
if ( !bTailOk )
break;
- g.assign( 1, node_traits::to_value_ptr( p.ptr() ));
- if ( pNext->m_pNext.load(memory_model::memory_order_relaxed) != p )
+ g.assign( 1, node_traits::to_value_ptr( p.ptr()));
+ if ( pNext->m_pNext.load( memory_model::memory_order_relaxed ) != p )
continue;
pNext = p;
- g.assign( 0, g.template get<value_type>( 1 ) );
+ g.assign( 0, g.template get<value_type>( 1 ));
}
- if ( !bTailOk || !m_pTail.compare_exchange_weak( t, marked_ptr( pNext.ptr() ), memory_model::memory_order_release, memory_model::memory_order_relaxed ))
+ if ( !bTailOk || !m_pTail.compare_exchange_weak( t, marked_ptr( pNext.ptr()), memory_model::memory_order_release, atomics::memory_order_relaxed ))
m_Stat.onAdvanceTailFailed();
m_Stat.onBadTail();
return true;
}
+ /// Synonym for \p enqueue() function
+ bool push( value_type& val )
+ {
+ return enqueue( val );
+ }
+
/// Dequeues a value from the queue
/** @anchor cds_intrusive_BasketQueue_dequeue
- If the queue is empty the function returns \p NULL.
+ If the queue is empty the function returns \p nullptr.
- <b>Warning</b>: see MSQueue::deque note about item disposing
+ @note See \p MSQueue::dequeue() note about item disposing
*/
value_type * dequeue()
{
return nullptr;
}
- /// Synonym for \ref cds_intrusive_BasketQueue_enqueue "enqueue" function
- bool push( value_type& val )
- {
- return enqueue( val );
- }
-
- /// Synonym for \ref cds_intrusive_BasketQueue_dequeue "dequeue" function
+ /// Synonym for \p dequeue() function
value_type * pop()
{
return dequeue();
/// Checks if the queue is empty
/**
Note that this function is not \p const.
- The function is based on \ref dequeue algorithm
- but really does not dequeued any item.
+ The function is based on \p dequeue() algorithm
+ but really it does not dequeue any item.
*/
bool empty()
{
/// Clear the queue
/**
- The function repeatedly calls \ref dequeue until it returns \p NULL.
- The disposer defined in template \p Options is called for each item
+ The function repeatedly calls \p dequeue() until it returns \p nullptr.
+ The disposer defined in template \p Traits is called for each item
that can be safely disposed.
*/
void clear()
{
- while ( dequeue() );
+ while ( dequeue());
+ }
+
+ /// Returns queue's item count
+ /**
+ The value returned depends on \p Traits (see basket_queue::traits::item_counter). For \p atomicity::empty_item_counter,
+ this function always returns 0.
+
+ @note Even if you use real item counter and it returns 0, this fact is not mean that the queue
+ is empty. To check queue emptyness use \p empty() method.
+ */
+ size_t size() const
+ {
+ return m_ItemCounter.value();
+ }
+
+ /// Returns reference to internal statistics
+ const stat& statistics() const
+ {
+ return m_Stat;
}
};
}} // namespace cds::intrusive
-#endif // #ifndef __CDS_INTRUSIVE_BASKET_QUEUE_H
+#endif // #ifndef CDSLIB_INTRUSIVE_BASKET_QUEUE_H
projects / libcds.git / blobdiff