template <typename Counter = cds::atomicity::event_counter >
struct stat
{
- typedef Counter counter_type ; ///< Counter type
+ typedef Counter counter_type; ///< Counter type
counter_type m_EnqueueCount ; ///< Enqueue call count
counter_type m_DequeueCount ; ///< Dequeue call count
};
/// Dummy queue statistics - no counting is performed, no overhead. Support interface like \p msqueue::stat
- /** @ingroup cds_intrusive_helper
- */
struct empty_stat
{
//@cond
typedef opt::v::relaxed_ordering memory_model;
/// Link checking, see \p cds::opt::link_checker
- static const opt::link_check_type link_checker = opt::debug_check_link;
+ static CDS_CONSTEXPR const opt::link_check_type link_checker = opt::debug_check_link;
- /// Alignment of internal queue data. Default is \p opt::cache_line_alignment
+ /// Alignment for internal queue data. Default is \p opt::cache_line_alignment
enum { alignment = opt::cache_line_alignment };
};
/// Metafunction converting option list to \p msqueue::traits
/**
- This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
Supported \p Options are:
- opt::hook - hook used. Possible hooks are: \p msqueue::base_hook, \p msqueue::member_hook, \p msqueue::traits_hook.
To enable item counting use \p cds::atomicity::item_counter
- opt::stat - the type to gather internal statistics.
Possible statistics types are: \p msqueue::stat, \p msqueue::empty_stat, user-provided class that supports \p %msqueue::stat interface.
- Default is \p msqueue::empty_stat.
+ Default is \p %msqueue::empty_stat (internal statistics disabled).
- opt::alignment - the alignment for internal queue data. Default is \p opt::cache_line_alignment
- 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).
\code
typedef cds::intrusive::MSQueue< cds::gc::HP, Foo,
typename cds::intrusive::msqueue::make_traits<
+ cds::intrusive::opt:hook< cds::intrusive::msqueue::base_hook< cds::opt::gc<cds:gc::HP> >>,
cds::opt::item_counte< cds::atomicity::item_counter >,
cds::opt::stat< cds::intrusive::msqueue::stat<> >
>::type
>::type type;
# endif
};
-
-
} // namespace msqueue
/// Michael & Scott's intrusive lock-free queue
Template arguments:
- \p GC - garbage collector type: \p gc::HP, \p gc::DHP
- - \p T - type to be stored in the queue. A value of type \p T must be derived from \p msqueue::node for \p msqueue::base_hook,
+ - \p T - type of value to be stored in the queue. A value of type \p T must be derived from \p msqueue::node for \p msqueue::base_hook,
or it should have a member of type \p %msqueue::node for \p msqueue::member_hook,
or it should be convertible to \p %msqueue::node for \p msqueue::traits_hook.
- - \p Traits - queue traits, default is \p queue::traits. You can use \p queue::make_traits
- metafunction to make your traits or just derive your traits from \p %queue::traits:
+ - \p Traits - queue traits, default is \p msqueue::traits. You can use \p msqueue::make_traits
+ metafunction to make your traits or just derive your traits from \p %msqueue::traits:
\code
- struct myTraits: public cds::intrusive::queue::traits {
+ struct myTraits: public cds::intrusive::msqueue::traits {
typedef cds::intrusive::msqueue::stat<> stat;
typedef cds::atomicity::item_counter item_counter;
};
{
public:
typedef GC gc; ///< Garbage collector
- typedef T value_type; ///< type of value stored in the queue
+ 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 MSQueue< GC2, T2, Traits2 > other; ///< Rebinding result
};
+ static CDS_CONSTEXPR const size_t m_nHazardPtrCount = 2; ///< Count of hazard pointer required for the algorithm
+
protected:
//@cond
// 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");
- struct internal_disposer
- {
- void operator()( value_type * p )
- {
- assert( p != nullptr );
-
- MSQueue::clear_links( node_traits::to_node_ptr(p) );
- disposer()( p );
- }
- };
-
typedef intrusive::node_to_value<MSQueue> node_to_value;
typedef typename opt::details::alignment_setter< typename node_type::atomic_node_ptr, traits::alignment >::type aligned_node_ptr;
-
typedef typename opt::details::alignment_setter< node_type, traits::alignment >::type dummy_node_type;
- aligned_node_ptr m_pHead ; ///< Queue's head pointer (cache-line aligned)
- aligned_node_ptr m_pTail ; ///< Queue's tail pointer (cache-line aligned)
+ aligned_node_ptr m_pHead ; ///< Queue's head pointer
+ aligned_node_ptr m_pTail ; ///< Queue's tail pointer
dummy_node_type m_Dummy ; ///< dummy node
item_counter m_ItemCounter ; ///< Item counter
stat m_Stat ; ///< Internal statistics
void dispose_node( node_type * p )
{
- // Note for he dummy node:
+ // Note about the dummy node:
// We cannot clear m_Dummy here since it leads to ABA.
// On the other hand, we cannot use deferred clear_links( &m_Dummy ) call via
// HP retiring cycle since m_Dummy is member of MSQueue and may be destroyed
// before HP retiring cycle invocation.
// So, we will never clear m_Dummy
- if ( p != &m_Dummy ) {
- gc::template retire<internal_disposer>( node_traits::to_value_ptr(p) );
- }
+
+ struct disposer_thunk {
+ void operator()( value_type * p ) const
+ {
+ assert( p != nullptr );
+ MSQueue::clear_links( node_traits::to_node_ptr( p ) );
+ disposer()(p);
+ }
+ };
+
+ if ( p != &m_Dummy )
+ gc::template retire<disposer_thunk>( node_traits::to_value_ptr( p ) );
}
//@endcond
dispose_node( pHead );
}
- /// Returns queue's item count
- /**
- The value returned depends on \p msqueue::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
- stat const& statistics() const
- {
- return m_Stat;
- }
-
/// Enqueues \p val value into the queue.
/** @anchor cds_intrusive_MSQueue_enqueue
The function always returns \p true.
{
while ( dequeue() );
}
+
+ /// Returns queue's item count
+ /**
+ The value returned depends on \p msqueue::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
+ stat const& statistics() const
+ {
+ return m_Stat;
+ }
};
}} // namespace cds::intrusive