-//$$CDS-header$$
-
-#ifndef __CDS_INTRUSIVE_OPTIMISTIC_QUEUE_H
-#define __CDS_INTRUSIVE_OPTIMISTIC_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_INTRUSIVE_OPTIMISTIC_QUEUE_H
+#define CDSLIB_INTRUSIVE_OPTIMISTIC_QUEUE_H
#include <type_traits>
-#include <cds/intrusive/base.h>
-#include <cds/cxx11_atomic.h>
+#include <cds/intrusive/details/base.h>
+#include <cds/algo/atomic.h>
#include <cds/gc/default_gc.h>
-#include <cds/gc/hrc/gc_fwd.h>
-#include <cds/intrusive/queue_stat.h>
-#include <cds/ref.h>
namespace cds { namespace intrusive {
- /// Optimistic queue related definitions
+ /// \p OptimisticQueue related definitions
/** @ingroup cds_intrusive_helper
*/
namespace optimistic_queue {
/// Optimistic queue node
/**
Template parameters:
- - GC - garbage collector used. gc::HRC is not supported.
- - Tag - a tag used to distinguish between different implementation
+ - \p GC - garbage collector
+ - \p 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 typename gc::template atomic_ref<node> atomic_node_ptr ; ///< atomic pointer
- atomic_node_ptr m_pPrev ; ///< Pointer to previous node
atomic_node_ptr m_pNext ; ///< Pointer to next node
+ atomic_node_ptr m_pPrev ; ///< Pointer to previous node
CDS_CONSTEXPR node() CDS_NOEXCEPT
- : m_pPrev( nullptr )
- , m_pNext( nullptr )
+ : m_pNext( nullptr )
+ , m_pPrev( nullptr )
{}
};
//@endcond
//@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;
/// Base hook
/**
\p Options are:
- - opt::gc - garbage collector used.
- - opt::tag - tag
+ - \p opt::gc - garbage collector used.
+ - \p 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 MemberOffset defines offset in bytes of \ref node member into your structure.
+ \p MemberOffset specifies offset in bytes of \ref node member into your structure.
Use \p offsetof macro to define \p MemberOffset
\p Options are:
- - opt::gc - garbage collector used.
- - opt::tag - tag
+ - \p opt::gc - garbage collector used.
+ - \p 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;
See \ref node_traits for \p NodeTraits interface description
\p Options are:
- - opt::gc - garbage collector used.
- - opt::tag - tag
+ - \p opt::gc - garbage collector used.
+ - \p 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;
typedef Node node_type;
//@endcond
- /// Checks if the link fields of node \p pNode is NULL
+ /// Checks if the link fields of node \p pNode is \p nullptr
/**
- An asserting is generated if \p pNode link fields is not NULL
+ An asserting is generated if \p pNode link fields is not \p nullptr
*/
static void is_empty( const node_type * pNode )
{
- assert( pNode->m_pNext.load( CDS_ATOMIC::memory_order_relaxed ) == nullptr );
- assert( pNode->m_pPrev.load( CDS_ATOMIC::memory_order_relaxed ) == nullptr );
+ assert( pNode->m_pNext.load( atomics::memory_order_relaxed ) == nullptr );
+ assert( pNode->m_pPrev.load( atomics::memory_order_relaxed ) == nullptr );
+ CDS_UNUSED( pNode );
}
};
};
//@endcond
- /// OptimisticQueue internal statistics. May be used for debugging or profiling
+ /// \p OptimisticQueue internal statistics. May be used for debugging or profiling
/**
Template argument \p Counter defines type of counter.
- Default is 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 cds::atomicity::item_counter,
+ Default is \p cds::atomicity::event_counter.
+ You may use stronger type of counter like as \p cds::atomicity::item_counter,
or even integral type, for example, \p int.
-
- The class extends intrusive::queue_stat interface for OptimisticQueue.
*/
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_FixListCount ; ///< Count of fix list event
-
+ 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_FixListCount; ///< Count of fix list event
+ 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 fix list event
void onFixList() { ++m_FixListCount; }
+ /// 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_FixListCount.reset();
+ m_EmptyDequeue.reset();
}
stat& operator +=( stat const& s )
{
- base_class::operator +=( s );
+ 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_FixListCount += s.m_FixListCount.get();
+ m_EmptyDequeue += s.m_EmptyDequeue.get();
+
return *this;
}
//@endcond
};
- /// Dummy OptimisticQueue statistics - no counting is performed. Support interface like \ref optimistic_queue::stat
- struct dummy_stat: public cds::intrusive::queue_dummy_stat
+ /// Dummy \p OptimisticQueue statistics - no counting is performed. Support interface like \p optimistic_queue::stat
+ struct empty_stat
{
//@cond
- void onFixList() {}
+ void onEnqueue() const {}
+ void onDequeue() const {}
+ void onEnqueueRace() const {}
+ void onDequeueRace() const {}
+ void onAdvanceTailFailed() const {}
+ void onBadTail() const {}
+ void onFixList() const {}
+ void onEmptyDequeue() const {}
void reset() {}
- dummy_stat& operator +=( dummy_stat const& )
+ empty_stat& operator +=( empty_stat const& )
{
return *this;
}
//@endcond
};
+ /// \p OptimisticQueue default type traits
+ struct traits
+ {
+ /// Back-off strategy
+ typedef cds::backoff::empty back_off;
+
+ /// Hook, possible types are \p optimistic_queue::base_hook, \p optimistic_queue::member_hook, \p optimistic_queue::traits_hook
+ typedef optimistic_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 cds::atomicity::empty_item_counter item_counter;
+
+ /// 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;
+
+ /// Internal statistics (by default, disabled)
+ /**
+ Possible option value are: \p optimistic_queue::stat, \p optimistic_queue::empty_stat (the default),
+ user-provided class that supports \p %optimistic_queue::stat interface.
+ */
+ typedef optimistic_queue::empty_stat stat;
+
+ /// 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 optimistic_queue::traits
+ /**
+ Supported \p Options are:
+
+ - \p opt::hook - hook used. Possible hooks are: \p optimistic_queue::base_hook, \p optimistic_queue::member_hook, \p optimistic_queue::traits_hook.
+ If the option is not specified, \p %optimistic_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 optimistic_queue::stat, \p optimistic_queue::empty_stat,
+ user-provided class that supports \p %optimistic_queue::stat interface.
+ Default is \p %optimistic_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 %OptimisticQueue with item counting and internal statistics
+ \code
+ typedef cds::intrusive::OptimisticQueue< cds::gc::HP, Foo,
+ typename cds::intrusive::optimistic_queue::make_traits<
+ cds::intrusive::opt:hook< cds::intrusive::optimistic_queue::base_hook< cds::opt::gc<cds:gc::HP> >>,
+ cds::opt::item_counte< cds::atomicity::item_counter >,
+ cds::opt::stat< cds::intrusive::optimistic_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 optimistic_queue
- /// Optimistic queue
+ /// Optimistic intruive lock-free queue
/** @ingroup cds_intrusive_queue
Implementation of Ladan-Mozes & Shavit optimistic queue algorithm.
-
- \par Source:
[2008] Edya Ladan-Mozes, Nir Shavit "An Optimistic Approach to Lock-Free FIFO Queues"
Template arguments:
- - \p GC - garbage collector type: gc::HP, gc::PTB. Note that gc::HRC is <b>not</b> supported
- - \p T - type to be stored in the queue
- - \p Options - options
-
- Type of node: \ref optimistic_queue::node.
-
- \p Options are:
- - opt::hook - hook used. Possible values are: optimistic_queue::base_hook, optimistic_queue::member_hook, optimistic_queue::traits_hook.
- If the option is not specified, <tt>optimistic_queue::base_hook<></tt> is used.
- - 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
- - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter
- - opt::stat - the type to gather internal statistics.
- Possible option value are: optimistic_queue::stat, optimistic_queue::dummy_stat,
- user-provided class that supports optimistic_queue::stat interface.
- Generic option intrusive::queue_stat and intrusive::queue_dummy_stat are acceptable too, however,
- they will be automatically converted to optimistic_queue::stat and optimistic_queue::dummy_stat
- respectively.
- Default is \ref optimistic_queue::dummy_stat.
- - 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. A value of type \p T must be derived from \p optimistic_queue::node for \p optimistic_queue::base_hook,
+ or it should have a member of type \p %optimistic_queue::node for \p optimistic_queue::member_hook,
+ or it should be convertible to \p %optimistic_queue::node for \p optimistic_queue::traits_hook.
+ - \p Traits - queue traits, default is \p optimistic_queue::traits. You can use \p optimistic_queue::make_traits
+ metafunction to make your traits or just derive your traits from \p %optimistic_queue::traits:
+ \code
+ struct myTraits: public cds::intrusive::optimistic_queue::traits {
+ typedef cds::intrusive::optimistic_queue::stat<> stat;
+ typedef cds::atomicity::item_counter item_counter;
+ };
+ typedef cds::intrusive::OptimisticQueue< cds::gc::HP, Foo, myTraits > myQueue;
+
+ // Equivalent make_traits example:
+ typedef cds::intrusive::OptimisticQueue< cds::gc::HP, Foo,
+ typename cds::intrusive::optimistic_queue::make_traits<
+ cds::opt::stat< cds::intrusive::optimistic_queue::stat<> >,
+ cds::opt::item_counter< cds::atomicity::item_counter >
+ >::type
+ > myQueue;
+ \endcode
Garbage collecting schema \p GC must be consistent with the optimistic_queue::node GC.
\par About item disposing
The optimistic 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 for explanation.
+ the standpoint of the algo. See \p dequeue() function for explanation.
\par Examples
\code
- #include <cds/intrusive/optimistic_queue.h>
#include <cds/gc/hp.h>
+ #include <cds/intrusive/optimistic_queue.h>
namespace ci = cds::inrtusive;
typedef cds::gc::HP hp_gc;
};
typedef ci::OptimisticQueue< hp_gc,
- Foo
- ,ci::opt::hook<
- ci::optimistic_queue::base_hook< ci::opt::gc< hp_gc > >
- >
- ,cds::opt::item_counter< cds::atomicity::item_counter >
+ Foo,
+ typename ci::optimistic_queue::make_traits<
+ ci::opt::hook<
+ ci::optimistic_queue::base_hook< ci::opt::gc< hp_gc > >
+ >
+ ,cds::opt::item_counter< cds::atomicity::item_counter >
+ >::type
> FooQueue;
// Optimistic queue with Hazard Pointer garbage collector, member hook, no item counter:
};
typedef ci::OptimisticQueue< hp_gc,
- Bar
- ,ci::opt::hook<
- ci::optimistic_queue::member_hook<
- offsetof(Bar, hMember)
- ,ci::opt::gc< hp_gc >
+ Bar,
+ typename ci::optimistic_queue::make_traits<
+ ci::opt::hook<
+ ci::optimistic_queue::member_hook<
+ offsetof(Bar, hMember)
+ ,ci::opt::gc< hp_gc >
+ >
>
- >
+ >::type
> BarQueue;
-
\endcode
*/
- template <typename GC, typename T, CDS_DECL_OPTIONS9>
+ template <typename GC, typename T, typename Traits = optimistic_queue::traits >
class OptimisticQueue
{
- //@cond
- struct default_options
- {
- typedef cds::backoff::empty back_off;
- typedef optimistic_queue::base_hook<> hook;
- typedef opt::v::empty_disposer disposer;
- typedef atomicity::empty_item_counter item_counter;
- typedef opt::v::relaxed_ordering memory_model;
- typedef optimistic_queue::dummy_stat stat;
- 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
- ,optimistic_queue::stat<>
- ,typename std::conditional<
- std::is_same<typename options::stat, cds::intrusive::queue_dummy_stat>::value
- ,optimistic_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 optimistic_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
- typedef typename options::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
-#ifdef CDS_DOXYGEN_INVOKED
- typedef typename options::stat stat ; ///< Internal statistics policy used
-#else
- typedef stat_type_ stat;
-#endif
+ typedef GC gc; ///< Garbage collector
+ typedef T value_type; ///< type of value to be 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 optimistic_queue::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::memory_model memory_model;///< Memory ordering. See cds::opt::memory_model option
+ typedef typename traits::stat stat; ///< Internal statistics policy used
/// Rebind template arguments
- template <typename GC2, typename T2, CDS_DECL_OTHER_OPTIONS9>
+ template <typename GC2, typename T2, typename Traits2>
struct rebind {
- typedef OptimisticQueue< GC2, T2, CDS_OTHER_OPTIONS9> other ; ///< Rebinding result
+ typedef OptimisticQueue< GC2, T2, Traits2 > other ; ///< Rebinding result
};
+ static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 5; ///< Count of hazard pointer required for the algorithm
+
protected:
//@cond
+ typedef typename node_type::atomic_node_ptr atomic_node_ptr;
- struct internal_disposer
- {
- void operator ()( value_type * p )
- {
- assert( p != nullptr );
-
- OptimisticQueue::clear_links( node_traits::to_node_ptr(*p) );
- disposer()( p );
- }
- };
-
- typedef intrusive::node_to_value<OptimisticQueue> node_to_value;
- typedef typename opt::details::alignment_setter< typename node_type::atomic_node_ptr, options::alignment >::type aligned_node_ptr;
+ // 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_pTail ; ///< Pointer to tail node
- aligned_node_ptr m_pHead ; ///< Pointer to head node
- node_type m_Dummy ; ///< dummy node
-
+ atomic_node_ptr m_pTail; ///< Pointer to tail node
+ //@cond
+ typename opt::details::apply_padding< atomic_node_ptr, traits::padding >::padding_type pad1_;
+ //@endcond
+ atomic_node_ptr m_pHead; ///< Pointer to head node
+ //@cond
+ typename opt::details::apply_padding< atomic_node_ptr, traits::padding >::padding_type pad2_;
+ //@endcond
+ node_type m_Dummy ; ///< dummy node
+ //@cond
+ typename opt::details::apply_padding< atomic_node_ptr, traits::padding >::padding_type pad3_;
+ //@endcond
item_counter m_ItemCounter ; ///< Item counter
stat m_Stat ; ///< Internal statistics
- static CDS_CONSTEXPR_CONST size_t c_nHazardPtrCount = 5 ; ///< Count of hazard pointer required for the algorithm
-
protected:
//@cond
static void clear_links( node_type * pNode )
back_off bkoff;
while ( true ) { // Try till success or empty
- pHead = res.guards.protect( 0, m_pHead, node_to_value() );
- pTail = res.guards.protect( 1, m_pTail, node_to_value() );
+ pHead = res.guards.protect( 0, m_pHead, [](node_type * p) -> value_type * {return node_traits::to_value_ptr(p);});
+ pTail = res.guards.protect( 1, m_pTail, [](node_type * p) -> value_type * {return node_traits::to_value_ptr(p);});
assert( pHead != nullptr );
- pFirstNodePrev = res.guards.protect( 2, pHead->m_pPrev, node_to_value() );
+ pFirstNodePrev = res.guards.protect( 2, pHead->m_pPrev, [](node_type * p) -> value_type * {return node_traits::to_value_ptr(p);});
- if ( pHead == m_pHead.load(memory_model::memory_order_relaxed)) {
+ if ( pHead == m_pHead.load(memory_model::memory_order_acquire)) {
if ( pTail != pHead ) {
if ( pFirstNodePrev == nullptr
- || pFirstNodePrev->m_pNext.load(memory_model::memory_order_relaxed) != pHead )
+ || pFirstNodePrev->m_pNext.load(memory_model::memory_order_acquire) != pHead )
{
fix_list( pTail, pHead );
continue;
}
- if ( m_pHead.compare_exchange_weak( pHead, pFirstNodePrev, memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed )) {
+ if ( m_pHead.compare_exchange_weak( pHead, pFirstNodePrev, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
// dequeue success
break;
}
}
else {
// the queue is empty
+ m_Stat.onEmptyDequeue();
return false;
}
}
pCurNode = pTail;
while ( pCurNode != pHead ) { // While not at head
- pCurNodeNext = guards.protect(0, pCurNode->m_pNext, node_to_value() );
- if ( pHead != m_pHead.load(memory_model::memory_order_relaxed) )
+ pCurNodeNext = guards.protect(0, pCurNode->m_pNext, [](node_type * p) -> value_type * { return node_traits::to_value_ptr(p);});
+ if ( pHead != m_pHead.load(memory_model::memory_order_acquire))
break;
pCurNodeNext->m_pPrev.store( pCurNode, memory_model::memory_order_release );
guards.assign( 1, node_traits::to_value_ptr( pCurNode = pCurNodeNext ));
assert( p != nullptr );
if ( p != &m_Dummy ) {
+ struct internal_disposer
+ {
+ void operator ()( value_type * p )
+ {
+ assert( p != nullptr );
+
+ OptimisticQueue::clear_links( node_traits::to_node_ptr( *p ) );
+ disposer()(p);
+ }
+ };
gc::template retire<internal_disposer>( node_traits::to_value_ptr(p) );
}
}
public:
/// Constructor creates empty queue
OptimisticQueue()
- : m_pTail( nullptr )
- , m_pHead( nullptr )
- {
- // 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");
-
- // cds::gc::HRC is not allowed
- static_assert(( !std::is_same<gc, cds::gc::HRC>::value ), "cds::gc::HRC is not allowed here");
-
- m_pTail.store( &m_Dummy, memory_model::memory_order_relaxed );
- m_pHead.store( &m_Dummy, memory_model::memory_order_relaxed );
- }
+ : m_pTail( &m_Dummy )
+ , m_pHead( &m_Dummy )
+ {}
~OptimisticQueue()
{
clear();
node_type * pHead = m_pHead.load(memory_model::memory_order_relaxed);
- CDS_DEBUG_DO( node_type * pTail = m_pTail.load(memory_model::memory_order_relaxed); )
- CDS_DEBUG_DO( assert( pHead == pTail ); )
+ CDS_DEBUG_ONLY( node_type * pTail = m_pTail.load(memory_model::memory_order_relaxed); )
+ CDS_DEBUG_ONLY( assert( pHead == pTail ); )
assert( pHead != nullptr );
m_pHead.store( nullptr, memory_model::memory_order_relaxed );
back_off bkoff;
guards.assign( 1, &val );
- node_type * pTail = guards.protect( 0, m_pTail, node_to_value() ) ; // Read the tail
+ node_type * pTail = guards.protect( 0, m_pTail, [](node_type * p) -> value_type * {return node_traits::to_value_ptr(p);} ); // Read the tail
while( true ) {
pNew->m_pNext.store( pTail, memory_model::memory_order_release );
- if ( m_pTail.compare_exchange_strong( pTail, pNew, memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ) ) { // Try to CAS the tail
- pTail->m_pPrev.store( pNew, memory_model::memory_order_release ) ; // Success, write prev
+ if ( m_pTail.compare_exchange_strong( pTail, pNew, memory_model::memory_order_release, atomics::memory_order_relaxed )) { // Try to CAS the tail
+ pTail->m_pPrev.store( pNew, memory_model::memory_order_release ); // Success, write prev
++m_ItemCounter;
m_Stat.onEnqueue();
- break ; // Enqueue done!
+ break; // Enqueue done!
}
- guards.assign( 0, node_traits::to_value_ptr( pTail ) ) ; // pTail has been changed by CAS above
+ guards.assign( 0, node_traits::to_value_ptr( pTail )); // pTail has been changed by CAS above
m_Stat.onEnqueueRace();
bkoff();
}
/// Dequeues a value from the queue
/** @anchor cds_intrusive_OptimisticQueue_dequeue
- If the queue is empty the function returns \a NULL
+ If the queue is empty the function returns \p nullptr
\par Warning
The queue algorithm has following feature: when \p dequeue is called,
| ... |
\endcode
- \p dequeue function returns Item 2, that becomes new top of queue, and calls
+ \p %dequeue() function returns Item 2, that becomes new top of queue, and calls
the disposer for Item 1, that was queue's top on function entry.
Thus, you cannot manually delete item returned because it is still included in
- item sequence and it has valuable link field that must not be zeroed.
+ the queue and it has valuable link field that must not be zeroed.
The item may be deleted only in disposer call.
*/
value_type * dequeue()
return nullptr;
}
- /// Synonym for @ref cds_intrusive_OptimisticQueue_enqueue "enqueue"
+ /// Synonym for \p enqueue()
bool push( value_type& val )
{
return enqueue( val );
}
- /// Synonym for \ref cds_intrusive_OptimisticQueue_dequeue "dequeue"
+ /// Synonym for \p dequeue()
value_type * pop()
{
return dequeue();
}
- /// Checks if queue is empty
+ /// Checks if the queue is empty
bool empty() const
{
return m_pTail.load(memory_model::memory_order_relaxed) == m_pHead.load(memory_model::memory_order_relaxed);
/// Clear the stack
/**
- The function repeatedly calls \ref dequeue until it returns NULL.
- The disposer defined in template \p Options is called for each item
+ The function repeatedly calls \ref 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()
/// Returns queue's item count
/**
- The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
- this function always returns 0.
+ The value returned depends on \p optimistic_queue::traits::item_counter.
+ For \p 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.
+ @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
{
}} // namespace cds::intrusive
-#endif // #ifndef __CDS_INTRUSIVE_OPTIMISTIC_QUEUE_H
+#endif // #ifndef CDSLIB_INTRUSIVE_OPTIMISTIC_QUEUE_H
projects / libcds.git / blobdiff