#define CDSLIB_CXX11_ATOMIC_H
#include <cds/details/defs.h>
+#include <cds/user_setup/cache_line.h>
namespace cds {
/// Atomic item counter
/**
This class is simplified interface around \p std::atomic_size_t.
- The class supports getting of current value of the counter and increment/decrement its value.
+ The class supports getting current value of the counter and increment/decrement its value.
+
+ See alûo improved version that eliminates false sharing: \p cache_friendly_item_counter.
*/
class item_counter
{
private:
//@cond
- atomic_type m_Counter ; ///< Atomic item counter
+ atomic_type m_Counter; ///< Atomic item counter
//@endcond
public:
}
};
+ /// Atomic cache-friendly item counter
+ /**
+ Atomic item counter with cache-line padding to avoid false sharing.
+ Adding cache-line padding before and after atomic counter eliminates the contention
+ in read path of many containers and can notably improve search operations in sets/maps.
+ */
+ class cache_friendly_item_counter
+ {
+ public:
+ typedef atomics::atomic_size_t atomic_type; ///< atomic type used
+ typedef size_t counter_type; ///< Integral item counter type (size_t)
+
+ private:
+ //@cond
+ char pad1_[cds::c_nCacheLineSize];
+ atomic_type m_Counter; ///< Atomic item counter
+ char pad2_[cds::c_nCacheLineSize - sizeof( atomic_type )];
+ //@endcond
+
+ public:
+ /// Default ctor initializes the counter to zero.
+ cache_friendly_item_counter()
+ : m_Counter(counter_type(0))
+ {}
+
+ /// Returns current value of the counter
+ counter_type value(atomics::memory_order order = atomics::memory_order_relaxed) const
+ {
+ return m_Counter.load( order );
+ }
+
+ /// Same as \ref value() with relaxed memory ordering
+ operator counter_type() const
+ {
+ return value();
+ }
+
+ /// Returns underlying atomic interface
+ atomic_type& getAtomic()
+ {
+ return m_Counter;
+ }
+
+ /// Returns underlying atomic interface (const)
+ const atomic_type& getAtomic() const
+ {
+ return m_Counter;
+ }
+
+ /// Increments the counter. Semantics: postincrement
+ counter_type inc(atomics::memory_order order = atomics::memory_order_relaxed )
+ {
+ return m_Counter.fetch_add( 1, order );
+ }
+
+ /// Increments the counter. Semantics: postincrement
+ counter_type inc( counter_type count, atomics::memory_order order = atomics::memory_order_relaxed )
+ {
+ return m_Counter.fetch_add( count, order );
+ }
+
+ /// Decrements the counter. Semantics: postdecrement
+ counter_type dec(atomics::memory_order order = atomics::memory_order_relaxed)
+ {
+ return m_Counter.fetch_sub( 1, order );
+ }
+
+ /// Decrements the counter. Semantics: postdecrement
+ counter_type dec( counter_type count, atomics::memory_order order = atomics::memory_order_relaxed )
+ {
+ return m_Counter.fetch_sub( count, order );
+ }
+
+ /// Preincrement
+ counter_type operator ++()
+ {
+ return inc() + 1;
+ }
+ /// Postincrement
+ counter_type operator ++(int)
+ {
+ return inc();
+ }
+
+ /// Predecrement
+ counter_type operator --()
+ {
+ return dec() - 1;
+ }
+ /// Postdecrement
+ counter_type operator --(int)
+ {
+ return dec();
+ }
+
+ /// Increment by \p count
+ counter_type operator +=( counter_type count )
+ {
+ return inc( count ) + count;
+ }
+
+ /// Decrement by \p count
+ counter_type operator -=( counter_type count )
+ {
+ return dec( count ) - count;
+ }
+
+ /// Resets count to 0
+ void reset(atomics::memory_order order = atomics::memory_order_relaxed)
+ {
+ m_Counter.store( 0, order );
+ }
+ };
+
+
/// Empty item counter
/**
This class may be used instead of \ref item_counter when you do not need full \ref item_counter interface.
/// Item counter
/**
The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
- To enable it use \p atomicity::item_counter
+ To enable it use \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter.
*/
typedef atomicity::empty_item_counter item_counter;
- \p bronson_avltree::relaxed_insert - enable (\p true) or disable (\p false, the default)
@ref bronson_avltree::relaxed_insert "relaxed insertion"
- \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
- To enable it use \p atomicity::item_counter
+ To enable it use \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter
- \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).
- \p opt::stat - internal statistics, by default it is disabled (\p bronson_avltree::empty_stat)
/// Item counter
/**
The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
- To enable it use \p atomicity::item_counter
+ To enable it use \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter
*/
typedef atomicity::empty_item_counter item_counter;
If the option is not specified, \p %opt::less is used.
- \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
- \p opt::item_counter - the type of item counter, default is disabled (\p atomicity::empty_item_counter).
- To enable it use \p atomicity::item_counter
+ To enable it use \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter
- \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).
- \p opt::allocator - the allocator for \ref ellen_bintree::node "leaf nodes" which contains data.
If the option is not specified, \p %opt::less is used.
- \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
- \p opt::item_counter - the type of item counter, default is disabled (\p atomicity::empty_item_counter).
- To enable it use \p atomicity::item_counter
+ To enable it use \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter
- 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).
- \p opt::allocator - the allocator used for \ref ellen_bintree::map_node "leaf nodes" which contains data.
/// Back-off strategy
typedef intrusive::iterable_list::traits::back_off back_off;
- /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
+ /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter or \p atomicity::cache_friendly_item_counter to enable item counting
typedef intrusive::iterable_list::traits::item_counter item_counter;
/// Internal statistics
- \p opt::node_allocator - node allocator, default is \p std::allocator.
- \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
- \p opt::item_counter - the type of item counting feature. Default is disabled (\p atomicity::empty_item_counter).
- To enable item counting use \p atomicity::item_counter.
+ To enable item counting use \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter.
- \p opt::stat - internal statistics. By default, it is disabled (\p iterable_list::empty_stat).
To enable it use \p iterable_list::stat
- \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
Note: unordering feature is not fully supported yet.
- \p opt::back_off - back-off strategy used. If the option is not specified, \p cds::backoff::Default is used.
- \p opt::item_counter - the type of item counting feature. Default is disabled (\p atomicity::empty_item_counter).
- To enable item counting use \p atomicity::item_counter.
+ To enable item counting use \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter
- \p opt::stat - internal statistics. By default, it is disabled (\p lazy_list::empty_stat).
To enable it use \p lazy_list::stat
- \p opt::allocator - the allocator used for creating and freeing list's item. Default is \ref CDS_DEFAULT_ALLOCATOR macro.
/// 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
+ /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter or \p atomicity::cache_friendly_item_counter to enable item counting
typedef atomicity::empty_item_counter item_counter;
/// Internal statistics
- \p opt::allocator - an allocator, default is \p CDS_DEFAULT_ALLOCATOR
- \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
- \p opt::item_counter - the type of item counting feature. Default is disabled (\p atomicity::empty_item_counter).
- To enable item counting use \p atomicity::item_counter.
+ To enable item counting use \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter
- \p opt::stat - internal statistics. By default, it is disabled (\p michael_list::empty_stat).
To enable it use \p michael_list::stat
- \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
// GC and OrderedList::gc must be the same
static_assert( std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
- // atomicity::empty_item_counter is not allowed as a item counter
- static_assert( !std::is_same<item_counter, atomicity::empty_item_counter>::value,
- "atomicity::empty_item_counter is not allowed as a item counter");
-
static CDS_CONSTEXPR const size_t c_nHazardPtrCount = ordered_list::c_nHazardPtrCount; ///< Count of hazard pointer required
//@cond
//@cond
const size_t m_nHashBitmask;
internal_bucket_type* m_Buckets; ///< bucket table
- item_counter m_ItemCounter; ///< Item counter
hash m_HashFunctor; ///< Hash functor
+ item_counter m_ItemCounter; ///< Item counter
stat m_Stat; ///< Internal statistics
//@endcond
/// Checks if the map is empty
/**
- Emptiness is checked by item counting: if item count is zero then the map is empty.
- Thus, the correct item counting is an important part of the map implementation.
+ @warning If you use \p atomicity::empty_item_counter in \p traits::item_counter,
+ the function always returns \p true.
*/
bool empty() const
{
}
/// Returns item count in the map
+ /**
+ If you use \p atomicity::empty_item_counter in \p traits::item_counter,
+ the function always returns 0.
+ */
size_t size() const
{
return m_ItemCounter;
// GC and OrderedList::gc must be the same
static_assert(std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
- // atomicity::empty_item_counter is not allowed as a item counter
- static_assert(!std::is_same<item_counter, atomicity::empty_item_counter>::value,
- "cds::atomicity::empty_item_counter is not allowed as a item counter");
-
protected:
//@cond
typedef typename ordered_list::template select_stat_wrapper< typename ordered_list::stat > bucket_stat;
protected:
//@cond
const size_t m_nHashBitmask;
- item_counter m_ItemCounter; ///< Item counter
- hash m_HashFunctor; ///< Hash functor
+ hash m_HashFunctor; ///< Hash functor
internal_bucket_type* m_Buckets; ///< bucket table
- stat m_Stat; ///< Internal statistics
+ item_counter m_ItemCounter; ///< Item counter
+ stat m_Stat; ///< Internal statistics
//@endcond
protected:
/// Checks whether the map is empty
/**
- Emptiness is checked by item counting: if item count is zero then the map is empty.
- Thus, the correct item counting feature is an important part of Michael's map implementation.
+ @warning If you use \p atomicity::empty_item_counter in \p traits::item_counter,
+ the function always returns \p true.
*/
bool empty() const
{
}
/// Returns item count in the map
+ /**
+ If you use \p atomicity::empty_item_counter in \p traits::item_counter,
+ the function always returns 0.
+ */
size_t size() const
{
return m_ItemCounter;
// GC and OrderedList::gc must be the same
static_assert(std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
- // atomicity::empty_item_counter is not allowed as a item counter
- static_assert(!std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
- "cds::atomicity::empty_item_counter is not allowed as a item counter");
-
protected:
//@cond
typedef typename ordered_list::template select_stat_wrapper< typename ordered_list::stat > bucket_stat;
protected:
//@cond
const size_t m_nHashBitmask;
- item_counter m_ItemCounter; ///< Item counter
- hash m_HashFunctor; ///< Hash functor
- internal_bucket_type * m_Buckets; ///< bucket table
- stat m_Stat; ///< Internal statistics
+ hash m_HashFunctor; ///< Hash functor
+ internal_bucket_type* m_Buckets; ///< bucket table
+ item_counter m_ItemCounter; ///< Item counter
+ stat m_Stat; ///< Internal statistics
//@endcond
protected:
/// Checks if the map is empty
/**
- Emptiness is checked by item counting: if item count is zero then the map is empty.
- Thus, the correct item counting is an important part of the map implementation.
+ @warning If you use \p atomicity::empty_item_counter in \p traits::item_counter,
+ the function always returns \p true.
*/
bool empty() const
{
}
/// Returns item count in the map
+ /**
+ @warning If you use \p atomicity::empty_item_counter in \p traits::item_counter,
+ the function always returns 0.
+ */
size_t size() const
{
return m_ItemCounter;
// GC and OrderedList::gc must be the same
static_assert( std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
- // atomicity::empty_item_counter is not allowed as a item counter
- static_assert( !std::is_same<item_counter, atomicity::empty_item_counter>::value,
- "cds::atomicity::empty_item_counter is not allowed as a item counter");
-
//@cond
typedef typename ordered_list::template select_stat_wrapper< typename ordered_list::stat > bucket_stat;
//@cond
size_t const m_nHashBitmask;
internal_bucket_type * m_Buckets; ///< bucket table
- item_counter m_ItemCounter; ///< Item counter
hash m_HashFunctor; ///< Hash functor
+ item_counter m_ItemCounter; ///< Item counter
stat m_Stat; ///< Internal statistics
//@endcond
/// Checks if the set is empty
/**
- Emptiness is checked by item counting: if item count is zero then the set is empty.
- Thus, the correct item counting feature is an important part of Michael's set implementation.
+ @warning If you use \p atomicity::empty_item_counter in \p traits::item_counter,
+ the function always returns \p true.
*/
bool empty() const
{
}
/// Returns item count in the set
+ /**
+ @warning If you use \p atomicity::empty_item_counter in \p traits::item_counter,
+ the function always returns 0.
+ */
size_t size() const
{
return m_ItemCounter;
// GC and OrderedList::gc must be the same
static_assert(std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
- // atomicity::empty_item_counter is not allowed as a item counter
- static_assert(!std::is_same<item_counter, atomicity::empty_item_counter>::value,
- "cds::atomicity::empty_item_counter is not allowed as a item counter");
-
protected:
//@cond
typedef typename ordered_list::template select_stat_wrapper< typename ordered_list::stat > bucket_stat;
protected:
//@cond
const size_t m_nHashBitmask;
- item_counter m_ItemCounter; ///< Item counter
hash m_HashFunctor; ///< Hash functor
internal_bucket_type* m_Buckets; ///< bucket table
- stat m_Stat; ///< Internal statistics
+ item_counter m_ItemCounter; ///< Item counter
+ stat m_Stat; ///< Internal statistics
//@endcond
public:
/// Checks if the set is empty
/**
- The emptiness is checked by the item counting: if item count is zero then the set is empty.
- Thus, the correct item counting feature is an important part of Michael's set implementation.
+ @warning If you use \p atomicity::empty_item_counter in \p traits::item_counter,
+ the function always returns \p true.
*/
bool empty() const
{
}
/// Returns item count in the set
+ /**
+ @warning If you use \p atomicity::empty_item_counter in \p traits::item_counter,
+ the function always returns 0.
+ */
size_t size() const
{
return m_ItemCounter;
// GC and OrderedList::gc must be the same
static_assert(std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
- static_assert(!std::is_same<item_counter, atomicity::empty_item_counter>::value,
- "atomicity::empty_item_counter is not allowed as a item counter");
-
//@cond
typedef typename ordered_list::template select_stat_wrapper< typename ordered_list::stat > bucket_stat;
typedef typename allocator::template rebind< internal_bucket_type >::other bucket_table_allocator;
const size_t m_nHashBitmask;
- item_counter m_ItemCounter; ///< Item counter
hash m_HashFunctor; ///< Hash functor
internal_bucket_type* m_Buckets; ///< bucket table
+ item_counter m_ItemCounter; ///< Item counter
stat m_Stat; ///< Internal statistics
//@endcond
/// Checks if the set is empty
/**
- Emptiness is checked by item counting: if item count is zero then the set is empty.
- Thus, the correct item counting feature is an important part of Michael's set implementation.
+ @warning If you use \p atomicity::empty_item_counter in \p traits::item_counter,
+ the function always returns \p true.
*/
bool empty() const
{
}
/// Returns item count in the set
+ /**
+ @warning If you use \p atomicity::empty_item_counter in \p traits::item_counter,
+ the function always returns 0.
+ */
size_t size() const
{
return m_ItemCounter;
/// Item counter
/**
The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
- To enable it use \p atomicity::item_counter
+ To enable it use \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter
*/
typedef atomicity::empty_item_counter item_counter;
- \p opt::disposer - the functor used for dispose removed nodes. Default is \p opt::v::empty_disposer. Due the nature
of GC schema the disposer may be called asynchronously. The disposer is used only for leaf nodes.
- \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
- To enable it use \p atomicity::item_counter
+ To enable it use \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter
- \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).
- \p ellen_bintree::update_desc_allocator - an allocator of \ref ellen_bintree::update_desc "update descriptors",
the \p empty() member function depends on correct item counting.
Therefore, \p atomicity::empty_item_counter is not allowed as a type of the option.
- Default is \p atomicity::item_counter.
+ Default is \p atomicity::item_counter. To avoid false sharing you can aldo use \p atomicity::cache_friendly_item_counter
*/
typedef cds::atomicity::item_counter item_counter;
The item counting is an important part of \p FeldmanHashSet algorithm:
the \p empty() member function depends on correct item counting.
Therefore, \p atomicity::empty_item_counter is not allowed as a type of the option.
- Default is \p atomicity::item_counter.
+ Default is \p atomicity::item_counter. To avoid false sharing you can use or \p atomicity::cache_friendly_item_counter
- \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).
- \p opt::stat - internal statistics. By default, it is disabled (\p feldman_hashset::empty_stat).
*/
typedef empty_stat stat;
- /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
+ /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter or \p atomicity::cache_friendly_item_counter to enable item counting
typedef atomicity::empty_item_counter item_counter;
/// C++ memory ordering model
- \p opt::disposer - the functor used for disposing removed items. Default is \p opt::v::empty_disposer. Due the nature
of GC schema the disposer may be called asynchronously.
- \p opt::item_counter - the type of item counting feature. Default is disabled (\p atomicity::empty_item_counter).
- To enable item counting use \p atomicity::item_counter.
+ To enable item counting use \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter
- \p opt::stat - internal statistics. By default, it is disabled (\p iterable_list::empty_stat).
To enable it use \p iterable_list::stat
- \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
/// Disposer for removing items
typedef opt::v::empty_disposer disposer;
- /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
+ /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter or \p atomicity::cache_friendly_item_counter to enable item counting
typedef atomicity::empty_item_counter item_counter;
/// Internal statistics
of GC schema the disposer may be called asynchronously.
- \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 disabled (\p atomicity::empty_item_counter).
- To enable item counting use \p atomicity::item_counter.
+ To enable item counting use \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter
- \p opt::stat - internal statistics. By default, it is disabled (\p lazy_list::empty_stat).
To enable it use \p lazy_list::stat
- \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
/// Disposer for removing items
typedef opt::v::empty_disposer disposer;
- /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
+ /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter or \p atomicity::cache_friendly_item_counter to enable item counting
typedef atomicity::empty_item_counter item_counter;
/// Internal statistics
of GC schema the disposer may be called asynchronously.
- \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 disabled (\p atomicity::empty_item_counter).
- To enable item counting use \p atomicity::item_counter.
+ To enable item counting use \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter
- \p opt::stat - internal statistics. By default, it is disabled (\p michael_list::empty_stat).
To enable it use \p michael_list::stat
- \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
/**
The item counting is an important part of \p MichaelHashSet algorithm:
the \p empty() member function depends on correct item counting.
- Therefore, \p atomicity::empty_item_counter is not allowed as a type of the option.
+ You may use \p atomicity::empty_item_counter if don't need \p empty() and \p size()
+ member functions.
- Default is \p atomicity::item_counter.
+ Default is \p atomicity::item_counter; to avoid false sharing you may use \p atomicity::cache_friendly_item_counter
*/
typedef cds::atomicity::item_counter item_counter;
/**
The type for item counting feature.
By default, item counting is disabled (\p atomicity::empty_item_counter),
- \p atomicity::item_counter enables it.
+ \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter enables it.
*/
typedef atomicity::empty_item_counter item_counter;
- \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. Due the nature
of GC schema the disposer may be called asynchronously.
- \p opt::item_counter - the type of item counting feature. Default is disabled, i.e. \p atomicity::empty_item_counter.
- To enable it use \p atomicity::item_counter
+ To enable it use \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter
- \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).
- \p skip_list::random_level_generator - random level generator. Can be \p skip_list::xor_shift,
the <tt>empty()</tt> member function depends on correct item counting.
Therefore, \p cds::atomicity::empty_item_counter is not allowed as a type of the option.
- Default is \p cds::atomicity::item_counter.
+ Default is \p cds::atomicity::item_counter; to avoid false sharing you may use \p atomicity::cache_friendly_item_counter
*/
typedef cds::atomicity::item_counter item_counter;
//@cond
skip_list::details::head_node< node_type > m_Head; ///< head tower (max height)
- item_counter m_ItemCounter; ///< item counter
random_level_generator m_RandomLevelGen; ///< random level generator instance
atomics::atomic<unsigned int> m_nHeight; ///< estimated high level
+ item_counter m_ItemCounter; ///< item counter
mutable stat m_Stat; ///< internal statistics
//@endcond
};
// GC and OrderedList::gc must be the same
static_assert(std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
- // atomicity::empty_item_counter is not allowed as a item counter
- static_assert(!std::is_same<item_counter, atomicity::empty_item_counter>::value,
- "cds::atomicity::empty_item_counter is not allowed as a item counter");
-
protected:
//@cond
typedef typename ordered_list::template select_stat_wrapper< typename ordered_list::stat > bucket_stat;
/// Checks if the set is empty
/**
- Emptiness is checked by item counting: if item count is zero then the set is empty.
- Thus, the correct item counting feature is an important part of Michael's set implementation.
+ @warning If you use \p atomicity::empty_item_counter in \p traits::item_counter,
+ the function always returns \p true.
*/
bool empty() const
{
}
/// Returns item count in the set
+ /**
+ If you use \p atomicity::empty_item_counter in \p traits::item_counter,
+ the function always returns 0.
+ */
size_t size() const
{
return m_ItemCounter;
// GC and OrderedList::gc must be the same
static_assert(std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
- // atomicity::empty_item_counter is not allowed as a item counter
- static_assert(!std::is_same<item_counter, atomicity::empty_item_counter>::value,
- "atomicity::empty_item_counter is not allowed as a item counter");
-
protected:
//@cond
typedef typename ordered_list::template select_stat_wrapper< typename ordered_list::stat > bucket_stat;
/// Checks if the set is empty
/**
- Emptiness is checked by item counting: if item count is zero then the set is empty.
- Thus, the correct item counting feature is an important part of Michael's set implementation.
+ @warning If you use \p atomicity::empty_item_counter in \p traits::item_counter,
+ the function always returns \p true.
*/
bool empty() const
{
}
/// Returns item count in the set
+ /**
+ If you use \p atomicity::empty_item_counter in \p traits::item_counter,
+ the function always returns 0.
+ */
size_t size() const
{
return m_ItemCounter;
// GC and OrderedList::gc must be the same
static_assert(std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
- // atomicity::empty_item_counter is not allowed as a item counter
- static_assert(!std::is_same<item_counter, atomicity::empty_item_counter>::value,
- "atomicity::empty_item_counter is not allowed as a item counter");
-
protected:
//@cond
typedef typename ordered_list::template select_stat_wrapper< typename ordered_list::stat > bucket_stat;
/// Checks if the set is empty
/**
- Emptiness is checked by item counting: if item count is zero then the set is empty.
- Thus, the correct item counting feature is an important part of Michael's set implementation.
+ @warning If you use \p atomicity::empty_item_counter in \p traits::item_counter,
+ the function always returns \p true.
*/
bool empty() const
{
}
/// Returns item count in the set
+ /**
+ If you use \p atomicity::empty_item_counter in \p traits::item_counter,
+ the function always returns 0.
+ */
size_t size() const
{
return m_ItemCounter;
protected:
head_node m_Head; ///< head tower (max height)
- item_counter m_ItemCounter; ///< item counter
random_level_generator m_RandomLevelGen; ///< random level generator instance
atomics::atomic<unsigned int> m_nHeight; ///< estimated high level
+ item_counter m_ItemCounter; ///< item counter
mutable stat m_Stat; ///< internal statistics
protected:
protected:
skip_list::details::head_node< node_type > m_Head; ///< head tower (max height)
- item_counter m_ItemCounter; ///< item counter
random_level_generator m_RandomLevelGen; ///< random level generator instance
atomics::atomic<unsigned int> m_nHeight; ///< estimated high level
atomics::atomic<node_type *> m_pDeferredDelChain ; ///< Deferred deleted node chain
+ item_counter m_ItemCounter; ///< item counter
mutable stat m_Stat; ///< internal statistics
protected:
atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
atomics::atomic<size_t> m_nMaxItemCount; ///< number of items container can hold, before we have to resize
- item_counter m_ItemCounter; ///< Item counter
hash m_HashFunctor; ///< Hash functor
+ item_counter m_ItemCounter; ///< Item counter
stat m_Stat; ///< Internal statistics
//@endcond
};
atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
atomics::atomic<size_t> m_nMaxItemCount; ///< number of items container can hold, before we have to resize
- item_counter m_ItemCounter; ///< Item counter
hash m_HashFunctor; ///< Hash functor
+ item_counter m_ItemCounter; ///< Item counter
stat m_Stat; ///< Internal statistics
//@endcond
};
atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
atomics::atomic<size_t> m_nMaxItemCount; ///< number of items container can hold, before we have to resize
- item_counter m_ItemCounter; ///< Item counter
hash m_HashFunctor; ///< Hash functor
+ item_counter m_ItemCounter; ///< Item counter
stat m_Stat; ///< Internal statistics accumulator
//@endcond
};
Predefined option \p Type:
- \p atomicity::empty_item_counter - no item counting performed. It is default policy for many
containers
- - \p atomicity::item_counter - the class that provides atomically item counting
- - \p opt::v::sequential_item_counter - simple non-atomic item counter. This item counter is not intended for
+ - \p atomicity::item_counter - the class that provides atomic item counting
+ - \p atomicity::cache_friendly_item_counter - cache-friendly atomic item counter
+ - \p opt::v::sequential_item_counter - simple non-atomic item counter. This counter is not intended for
concurrent containers and may be used only if it is explicitly noted.
You may provide other implementation of \p atomicity::item_counter interface for your needs.
Note, the item counting in lock-free containers cannot be exact; for example, if
item counter for a container returns zero it is not mean that the container is empty.
- Thus, the item counter may be used for statistical purposes only.
+ So, the item counter may be used for statistical purposes only.
*/
template <typename Type>
struct item_counter {
cc::bronson_avltree::make_traits<
co::less< less >
,cc::bronson_avltree::relaxed_insert< false >
- ,co::item_counter< cds::atomicity::item_counter >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef BronsonAVLTreeMap< rcu_gpi, Key, Value, BronsonAVLTreeMap_less > BronsonAVLTreeMap_rcu_gpi_less;
cc::bronson_avltree::make_traits<
co::compare< compare >
,cc::bronson_avltree::relaxed_insert< false >
- ,co::item_counter< cds::atomicity::item_counter >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
,co::stat< cc::bronson_avltree::stat<>>
>::type
{};
struct traits_EllenBinTreeMap: public cc::ellen_bintree::make_set_traits<
co::less< less >
,co::node_allocator< ellen_bintree_pool::internal_node_allocator< int > >
- ,co::item_counter< cds::atomicity::item_counter >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
struct traits_EllenBinTreeMap_hp : traits_EllenBinTreeMap {
>
,co::node_allocator< ellen_bintree_pool::internal_node_allocator< int > >
,co::stat< cc::ellen_bintree::stat<> >
- ,co::item_counter< cds::atomicity::item_counter >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
{
typedef std::hash< Key > hash;
typedef std::less<size_t> less;
+ typedef cds::atomicity::cache_friendly_item_counter item_counter;
};
typedef FeldmanHashMap< cds::gc::HP, Key, Value, traits_FeldmanHashMap_stdhash > FeldmanHashMap_hp_stdhash;
{
typedef ::cds_test::city64 hash;
typedef ::cds_test::city64::less less;
+ typedef cds::atomicity::cache_friendly_item_counter item_counter;
};
typedef FeldmanHashMap< cds::gc::HP, Key, Value, traits_FeldmanHashMap_city64 > FeldmanHashMap_hp_city64;
typedef FeldmanHashMap< cds::gc::DHP, Key, Value, traits_FeldmanHashMap_city64 > FeldmanHashMap_dhp_city64;
{
typedef ::cds_test::city128 hash;
typedef ::cds_test::city128::less less;
+ typedef cds::atomicity::cache_friendly_item_counter item_counter;
};
typedef FeldmanHashMap< cds::gc::HP, Key, Value, traits_FeldmanHashMap_city128 > FeldmanHashMap_hp_city128;
typedef FeldmanHashMap< cds::gc::DHP, Key, Value, traits_FeldmanHashMap_city128 > FeldmanHashMap_dhp_city128;
struct traits_FeldmanHashMap_fixed: public cc::feldman_hashmap::traits
{
typedef map::cmp<Key> compare;
+ typedef cds::atomicity::cache_friendly_item_counter item_counter;
};
typedef FeldmanHashMap< cds::gc::HP, Key, Value, traits_FeldmanHashMap_fixed > FeldmanHashMap_hp_fixed;
struct traits_MichaelMap_hash :
public cc::michael_map::make_traits<
co::hash< hash >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
class traits_SkipListMap_less_turbo32: public cc::skip_list::make_traits <
co::less< less >
,cc::skip_list::random_level_generator< cc::skip_list::turbo32 >
- ,co::item_counter< cds::atomicity::item_counter >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_less_turbo32 > SkipListMap_hp_less_turbo32;
class traits_SkipListMap_less_turbo24: public cc::skip_list::make_traits <
co::less< less >
, cc::skip_list::random_level_generator< cc::skip_list::turbo24 >
- , co::item_counter< cds::atomicity::item_counter >
+ , co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_less_turbo24 > SkipListMap_hp_less_turbo24;
class traits_SkipListMap_less_turbo16: public cc::skip_list::make_traits <
co::less< less >
, cc::skip_list::random_level_generator< cc::skip_list::turbo16 >
- , co::item_counter< cds::atomicity::item_counter >
+ , co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_less_turbo16 > SkipListMap_hp_less_turbo16;
co::less< less >
,cc::skip_list::random_level_generator< cc::skip_list::turbo32 >
,co::memory_model< co::v::sequential_consistent >
- ,co::item_counter< cds::atomicity::item_counter >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_less_turbo32_seqcst > SkipListMap_hp_less_turbo32_seqcst;
co::less< less >
,cc::skip_list::random_level_generator< cc::skip_list::turbo32 >
,co::stat< cc::skip_list::stat<> >
- ,co::item_counter< cds::atomicity::item_counter >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_less_turbo32_stat > SkipListMap_hp_less_turbo32_stat;
co::less< less >
, cc::skip_list::random_level_generator< cc::skip_list::turbo24 >
, co::stat< cc::skip_list::stat<> >
- , co::item_counter< cds::atomicity::item_counter >
+ , co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_less_turbo24_stat > SkipListMap_hp_less_turbo24_stat;
co::less< less >
, cc::skip_list::random_level_generator< cc::skip_list::turbo16 >
, co::stat< cc::skip_list::stat<> >
- , co::item_counter< cds::atomicity::item_counter >
+ , co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_less_turbo16_stat > SkipListMap_hp_less_turbo16_stat;
class traits_SkipListMap_cmp_turbo32: public cc::skip_list::make_traits <
co::compare< compare >
,cc::skip_list::random_level_generator< cc::skip_list::turbo32 >
- ,co::item_counter< cds::atomicity::item_counter >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_cmp_turbo32 > SkipListMap_hp_cmp_turbo32;
co::compare< compare >
,cc::skip_list::random_level_generator< cc::skip_list::turbo32 >
,co::stat< cc::skip_list::stat<> >
- ,co::item_counter< cds::atomicity::item_counter >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_cmp_turbo32_stat > SkipListMap_hp_cmp_turbo32_stat;
class traits_SkipListMap_less_xorshift32: public cc::skip_list::make_traits <
co::less< less >
,cc::skip_list::random_level_generator< cc::skip_list::xorshift32 >
- ,co::item_counter< cds::atomicity::item_counter >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_less_xorshift32 > SkipListMap_hp_less_xorshift32;
class traits_SkipListMap_less_xorshift24: public cc::skip_list::make_traits <
co::less< less >
, cc::skip_list::random_level_generator< cc::skip_list::xorshift24 >
- , co::item_counter< cds::atomicity::item_counter >
+ , co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_less_xorshift24 > SkipListMap_hp_less_xorshift24;
class traits_SkipListMap_less_xorshift16: public cc::skip_list::make_traits <
co::less< less >
, cc::skip_list::random_level_generator< cc::skip_list::xorshift16 >
- , co::item_counter< cds::atomicity::item_counter >
+ , co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_less_xorshift16 > SkipListMap_hp_less_xorshift16;
co::less< less >
,cc::skip_list::random_level_generator< cc::skip_list::xorshift32 >
,co::stat< cc::skip_list::stat<> >
- ,co::item_counter< cds::atomicity::item_counter >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_less_xorshift32_stat > SkipListMap_hp_less_xorshift32_stat;
co::less< less >
, cc::skip_list::random_level_generator< cc::skip_list::xorshift24 >
, co::stat< cc::skip_list::stat<> >
- , co::item_counter< cds::atomicity::item_counter >
+ , co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_less_xorshift24_stat > SkipListMap_hp_less_xorshift24_stat;
co::less< less >
, cc::skip_list::random_level_generator< cc::skip_list::xorshift16 >
, co::stat< cc::skip_list::stat<> >
- , co::item_counter< cds::atomicity::item_counter >
+ , co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_less_xorshift16_stat > SkipListMap_hp_less_xorshift16_stat;
class traits_SkipListMap_cmp_xorshift32: public cc::skip_list::make_traits <
co::compare< compare >
,cc::skip_list::random_level_generator< cc::skip_list::xorshift32 >
- ,co::item_counter< cds::atomicity::item_counter >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_cmp_xorshift32 > SkipListMap_hp_cmp_xorshift32;
co::compare< compare >
,cc::skip_list::random_level_generator< cc::skip_list::xorshift32 >
,co::stat< cc::skip_list::stat<> >
- ,co::item_counter< cds::atomicity::item_counter >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_cmp_xorshift32_stat > SkipListMap_hp_cmp_xorshift32_stat;
struct traits_SplitList_Michael_dyn_cmp: public cc::split_list::make_traits<
cc::split_list::ordered_list<cc::michael_list_tag>
,co::hash< hash >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
,cc::split_list::ordered_list_traits<
typename cc::michael_list::make_traits<
co::compare< compare >
struct traits_SplitList_Michael_dyn_cmp_seqcst: public cc::split_list::make_traits<
cc::split_list::ordered_list<cc::michael_list_tag>
,co::hash< hash >
+ , co::item_counter< cds::atomicity::cache_friendly_item_counter >
,co::memory_model< co::v::sequential_consistent >
,cc::split_list::ordered_list_traits<
typename cc::michael_list::make_traits<
cc::split_list::ordered_list<cc::michael_list_tag>
,cc::split_list::dynamic_bucket_table< false >
,co::hash< hash >
+ , co::item_counter< cds::atomicity::cache_friendly_item_counter >
,cc::split_list::ordered_list_traits<
typename cc::michael_list::make_traits<
co::compare< compare >
struct traits_SplitList_Michael_dyn_less: public cc::split_list::make_traits<
cc::split_list::ordered_list<cc::michael_list_tag>
,co::hash< hash >
+ , co::item_counter< cds::atomicity::cache_friendly_item_counter >
,cc::split_list::ordered_list_traits<
typename cc::michael_list::make_traits<
co::less< less >
cc::split_list::ordered_list<cc::michael_list_tag>
,cc::split_list::dynamic_bucket_table< false >
,co::hash< hash >
+ , co::item_counter< cds::atomicity::cache_friendly_item_counter >
,cc::split_list::ordered_list_traits<
typename cc::michael_list::make_traits<
co::less< less >
public cc::split_list::make_traits<
cc::split_list::ordered_list<cc::lazy_list_tag>
,co::hash< hash >
+ , co::item_counter< cds::atomicity::cache_friendly_item_counter >
,cc::split_list::ordered_list_traits<
typename cc::lazy_list::make_traits<
co::compare< compare >
public cc::split_list::make_traits<
cc::split_list::ordered_list<cc::lazy_list_tag>
,co::hash< hash >
+ , co::item_counter< cds::atomicity::cache_friendly_item_counter >
,co::memory_model< co::v::sequential_consistent >
,cc::split_list::ordered_list_traits<
typename cc::lazy_list::make_traits<
cc::split_list::ordered_list<cc::lazy_list_tag>
,cc::split_list::dynamic_bucket_table< false >
,co::hash< hash >
+ , co::item_counter< cds::atomicity::cache_friendly_item_counter >
,cc::split_list::ordered_list_traits<
typename cc::lazy_list::make_traits<
co::compare< compare >
public cc::split_list::make_traits<
cc::split_list::ordered_list<cc::lazy_list_tag>
,co::hash< hash >
+ , co::item_counter< cds::atomicity::cache_friendly_item_counter >
,cc::split_list::ordered_list_traits<
typename cc::lazy_list::make_traits<
co::less< less >
cc::split_list::ordered_list<cc::lazy_list_tag>
,cc::split_list::dynamic_bucket_table< false >
,co::hash< hash >
+ , co::item_counter< cds::atomicity::cache_friendly_item_counter >
,cc::split_list::ordered_list_traits<
typename cc::lazy_list::make_traits<
co::less< less >
struct traits_SplitList_Iterable_dyn_cmp: public cc::split_list::make_traits<
cc::split_list::ordered_list<cc::iterable_list_tag>
,co::hash< hash >
+ , co::item_counter< cds::atomicity::cache_friendly_item_counter >
,cc::split_list::ordered_list_traits<
typename cc::iterable_list::make_traits<
co::compare< compare >
struct traits_SplitList_Iterable_dyn_cmp_seqcst: public cc::split_list::make_traits<
cc::split_list::ordered_list<cc::iterable_list_tag>
,co::hash< hash >
+ , co::item_counter< cds::atomicity::cache_friendly_item_counter >
,co::memory_model< co::v::sequential_consistent >
,cc::split_list::ordered_list_traits<
typename cc::iterable_list::make_traits<
cc::split_list::ordered_list<cc::iterable_list_tag>
,cc::split_list::dynamic_bucket_table< false >
,co::hash< hash >
+ , co::item_counter< cds::atomicity::cache_friendly_item_counter >
,cc::split_list::ordered_list_traits<
typename cc::iterable_list::make_traits<
co::compare< compare >
struct traits_SplitList_Iterable_dyn_less: public cc::split_list::make_traits<
cc::split_list::ordered_list<cc::iterable_list_tag>
,co::hash< hash >
+ , co::item_counter< cds::atomicity::cache_friendly_item_counter >
,cc::split_list::ordered_list_traits<
typename cc::iterable_list::make_traits<
co::less< less >
cc::split_list::ordered_list<cc::iterable_list_tag>
,cc::split_list::dynamic_bucket_table< false >
,co::hash< hash >
+ , co::item_counter< cds::atomicity::cache_friendly_item_counter >
,cc::split_list::ordered_list_traits<
typename cc::iterable_list::make_traits<
co::less< less >
cc::ellen_bintree::key_extractor< typename ellen_bintree_props::key_extractor >
,co::less< typename ellen_bintree_props::less >
,co::node_allocator< ellen_bintree_pool::internal_node_allocator< int > >
+ ,co::item_counter<cds::atomicity::cache_friendly_item_counter >
>::type
{};
,co::less< typename ellen_bintree_props::less >
,co::node_allocator< ellen_bintree_pool::internal_node_allocator< int > >
,co::stat< cc::ellen_bintree::stat<> >
+ ,co::item_counter<cds::atomicity::cache_friendly_item_counter >
>::type
{};
return kv.hash;
}
};
+ typedef cds::atomicity::cache_friendly_item_counter item_counter;
};
typedef FeldmanHashSet< cds::gc::HP, key_val<std::hash<key_type>>, default_traits > FeldmanHashSet_hp_stdhash;
};
typedef set::cmp<Key> compare;
+ typedef cds::atomicity::cache_friendly_item_counter item_counter;
};
struct traits_stat : public traits
struct traits_MichaelSet :
public cc::michael_set::make_traits<
co::hash< hash >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef MichaelHashSet< cds::gc::HP, typename ml::MichaelList_HP_cmp, traits_MichaelSet > MichaelSet_HP_cmp;
class traits_SkipListSet_less_turbo32: public cc::skip_list::make_traits <
co::less< less >
,cc::skip_list::random_level_generator< cc::skip_list::turbo32 >
- ,co::item_counter< cds::atomicity::item_counter >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListSet< cds::gc::HP, key_val, traits_SkipListSet_less_turbo32 > SkipListSet_hp_less_turbo32;
class traits_SkipListSet_less_turbo24: public cc::skip_list::make_traits <
co::less< less >
,cc::skip_list::random_level_generator< cc::skip_list::turbo24 >
- ,co::item_counter< cds::atomicity::item_counter >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListSet< cds::gc::HP, key_val, traits_SkipListSet_less_turbo24 > SkipListSet_hp_less_turbo24;
class traits_SkipListSet_less_turbo16: public cc::skip_list::make_traits <
co::less< less >
,cc::skip_list::random_level_generator< cc::skip_list::turbo16 >
- ,co::item_counter< cds::atomicity::item_counter >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListSet< cds::gc::HP, key_val, traits_SkipListSet_less_turbo16 > SkipListSet_hp_less_turbo16;
co::less< less >
,cc::skip_list::random_level_generator< cc::skip_list::turbo32 >
,co::memory_model< co::v::sequential_consistent >
- ,co::item_counter< cds::atomicity::item_counter >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListSet< cds::gc::HP, key_val, traits_SkipListSet_less_turbo32_seqcst > SkipListSet_hp_less_turbo32_seqcst;
co::less< less >
,cc::skip_list::random_level_generator< cc::skip_list::turbo32 >
,co::stat< cc::skip_list::stat<> >
- ,co::item_counter< cds::atomicity::item_counter >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListSet< cds::gc::HP, key_val, traits_SkipListSet_less_turbo32_stat > SkipListSet_hp_less_turbo32_stat;
co::less< less >
,cc::skip_list::random_level_generator< cc::skip_list::turbo24 >
,co::stat< cc::skip_list::stat<> >
- ,co::item_counter< cds::atomicity::item_counter >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListSet< cds::gc::HP, key_val, traits_SkipListSet_less_turbo24_stat > SkipListSet_hp_less_turbo24_stat;
co::less< less >
,cc::skip_list::random_level_generator< cc::skip_list::turbo16 >
,co::stat< cc::skip_list::stat<> >
- ,co::item_counter< cds::atomicity::item_counter >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListSet< cds::gc::HP, key_val, traits_SkipListSet_less_turbo16_stat > SkipListSet_hp_less_turbo16_stat;
class traits_SkipListSet_cmp_turbo32: public cc::skip_list::make_traits <
co::compare< compare >
,cc::skip_list::random_level_generator< cc::skip_list::turbo32 >
- ,co::item_counter< cds::atomicity::item_counter >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListSet< cds::gc::HP, key_val, traits_SkipListSet_cmp_turbo32 > SkipListSet_hp_cmp_turbo32;
co::compare< compare >
,cc::skip_list::random_level_generator< cc::skip_list::turbo32 >
,co::stat< cc::skip_list::stat<> >
- ,co::item_counter< cds::atomicity::item_counter >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListSet< cds::gc::HP, key_val, traits_SkipListSet_cmp_turbo32_stat > SkipListSet_hp_cmp_turbo32_stat;
class traits_SkipListSet_less_xorshift32: public cc::skip_list::make_traits <
co::less< less >
,cc::skip_list::random_level_generator< cc::skip_list::xorshift32 >
- ,co::item_counter< cds::atomicity::item_counter >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListSet< cds::gc::HP, key_val, traits_SkipListSet_less_xorshift32 > SkipListSet_hp_less_xorshift32;
class traits_SkipListSet_less_xorshift24: public cc::skip_list::make_traits <
co::less< less >
,cc::skip_list::random_level_generator< cc::skip_list::xorshift24 >
- ,co::item_counter< cds::atomicity::item_counter >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListSet< cds::gc::HP, key_val, traits_SkipListSet_less_xorshift24 > SkipListSet_hp_less_xorshift24;
class traits_SkipListSet_less_xorshift16: public cc::skip_list::make_traits <
co::less< less >
, cc::skip_list::random_level_generator< cc::skip_list::xorshift16 >
- , co::item_counter< cds::atomicity::item_counter >
+ , co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListSet< cds::gc::HP, key_val, traits_SkipListSet_less_xorshift16 > SkipListSet_hp_less_xorshift16;
co::less< less >
,cc::skip_list::random_level_generator< cc::skip_list::xorshift32 >
,co::stat< cc::skip_list::stat<> >
- ,co::item_counter< cds::atomicity::item_counter >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListSet< cds::gc::HP, key_val, traits_SkipListSet_less_xorshift32_stat > SkipListSet_hp_less_xorshift32_stat;
co::less< less >
, cc::skip_list::random_level_generator< cc::skip_list::xorshift24 >
, co::stat< cc::skip_list::stat<> >
- , co::item_counter< cds::atomicity::item_counter >
+ , co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListSet< cds::gc::HP, key_val, traits_SkipListSet_less_xorshift24_stat > SkipListSet_hp_less_xorshift24_stat;
co::less< less >
, cc::skip_list::random_level_generator< cc::skip_list::xorshift16 >
, co::stat< cc::skip_list::stat<> >
- , co::item_counter< cds::atomicity::item_counter >
+ , co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListSet< cds::gc::HP, key_val, traits_SkipListSet_less_xorshift16_stat > SkipListSet_hp_less_xorshift16_stat;
class traits_SkipListSet_cmp_xorshift32: public cc::skip_list::make_traits <
co::compare< compare >
,cc::skip_list::random_level_generator< cc::skip_list::xorshift32 >
- ,co::item_counter< cds::atomicity::item_counter >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListSet< cds::gc::HP, key_val, traits_SkipListSet_cmp_xorshift32 > SkipListSet_hp_cmp_xorshift32;
co::compare< compare >
,cc::skip_list::random_level_generator< cc::skip_list::xorshift32 >
,co::stat< cc::skip_list::stat<> >
- ,co::item_counter< cds::atomicity::item_counter >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef SkipListSet< cds::gc::HP, key_val, traits_SkipListSet_cmp_xorshift32_stat > SkipListSet_hp_cmp_xorshift32_stat;
public cc::split_list::make_traits<
cc::split_list::ordered_list<cc::michael_list_tag>
,co::hash< hash >
+ ,co::item_counter<cds::atomicity::cache_friendly_item_counter >
,cc::split_list::ordered_list_traits<
typename cc::michael_list::make_traits<
co::compare< compare >
public cc::split_list::make_traits<
cc::split_list::ordered_list<cc::michael_list_tag>
,co::hash< hash >
+ , co::item_counter<cds::atomicity::cache_friendly_item_counter >
,co::stat< cc::split_list::stat<> >
,cc::split_list::ordered_list_traits<
typename cc::michael_list::make_traits<
public cc::split_list::make_traits<
cc::split_list::ordered_list<cc::michael_list_tag>
,co::hash< hash >
+ ,co::item_counter<cds::atomicity::cache_friendly_item_counter >
,co::memory_model< co::v::sequential_consistent >
,cc::split_list::ordered_list_traits<
typename cc::michael_list::make_traits<
cc::split_list::ordered_list<cc::michael_list_tag>
,cc::split_list::dynamic_bucket_table< false >
,co::hash< hash >
+ ,co::item_counter<cds::atomicity::cache_friendly_item_counter >
,cc::split_list::ordered_list_traits<
typename cc::michael_list::make_traits<
co::compare< compare >
public cc::split_list::make_traits<
cc::split_list::ordered_list<cc::michael_list_tag>
,co::hash< hash >
+ , co::item_counter<cds::atomicity::cache_friendly_item_counter >
,cc::split_list::ordered_list_traits<
typename cc::michael_list::make_traits<
co::less< less >
cc::split_list::ordered_list<cc::michael_list_tag>
,cc::split_list::dynamic_bucket_table< false >
,co::hash< hash >
+ , co::item_counter<cds::atomicity::cache_friendly_item_counter >
,cc::split_list::ordered_list_traits<
typename cc::michael_list::make_traits<
co::less< less >
cc::split_list::ordered_list<cc::michael_list_tag>
,cc::split_list::dynamic_bucket_table< false >
,co::hash< hash >
+ , co::item_counter<cds::atomicity::cache_friendly_item_counter >
,co::stat< cc::split_list::stat<>>
,cc::split_list::ordered_list_traits<
typename cc::michael_list::make_traits<
public cc::split_list::make_traits<
cc::split_list::ordered_list<cc::lazy_list_tag>
,co::hash< hash >
+ , co::item_counter<cds::atomicity::cache_friendly_item_counter >
,cc::split_list::ordered_list_traits<
typename cc::lazy_list::make_traits<
co::compare< compare >
public cc::split_list::make_traits<
cc::split_list::ordered_list<cc::lazy_list_tag>
,co::hash< hash >
+ , co::item_counter<cds::atomicity::cache_friendly_item_counter >
,co::memory_model< co::v::sequential_consistent >
,cc::split_list::ordered_list_traits<
typename cc::lazy_list::make_traits<
cc::split_list::ordered_list<cc::lazy_list_tag>
,cc::split_list::dynamic_bucket_table< false >
,co::hash< hash >
+ , co::item_counter<cds::atomicity::cache_friendly_item_counter >
,cc::split_list::ordered_list_traits<
typename cc::lazy_list::make_traits<
co::compare< compare >
public cc::split_list::make_traits<
cc::split_list::ordered_list<cc::lazy_list_tag>
,co::hash< hash >
+ , co::item_counter<cds::atomicity::cache_friendly_item_counter >
,cc::split_list::ordered_list_traits<
typename cc::lazy_list::make_traits<
co::less< less >
cc::split_list::ordered_list<cc::lazy_list_tag>
,cc::split_list::dynamic_bucket_table< false >
,co::hash< hash >
+ , co::item_counter<cds::atomicity::cache_friendly_item_counter >
,cc::split_list::ordered_list_traits<
typename cc::lazy_list::make_traits<
co::less< less >
public cc::split_list::make_traits<
cc::split_list::ordered_list<cc::iterable_list_tag>
,co::hash< hash >
+ , co::item_counter<cds::atomicity::cache_friendly_item_counter >
,cc::split_list::ordered_list_traits<
typename cc::iterable_list::make_traits<
co::compare< compare >
public cc::split_list::make_traits<
cc::split_list::ordered_list<cc::iterable_list_tag>
,co::hash< hash >
+ , co::item_counter<cds::atomicity::cache_friendly_item_counter >
,co::stat< cc::split_list::stat<> >
,cc::split_list::ordered_list_traits<
typename cc::iterable_list::make_traits<
public cc::split_list::make_traits<
cc::split_list::ordered_list<cc::iterable_list_tag>
,co::hash< hash >
+ , co::item_counter<cds::atomicity::cache_friendly_item_counter >
,co::memory_model< co::v::sequential_consistent >
,cc::split_list::ordered_list_traits<
typename cc::iterable_list::make_traits<
cc::split_list::ordered_list<cc::iterable_list_tag>
,cc::split_list::dynamic_bucket_table< false >
,co::hash< hash >
+ , co::item_counter<cds::atomicity::cache_friendly_item_counter >
,cc::split_list::ordered_list_traits<
typename cc::iterable_list::make_traits<
co::compare< compare >
public cc::split_list::make_traits<
cc::split_list::ordered_list<cc::iterable_list_tag>
,co::hash< hash >
+ , co::item_counter<cds::atomicity::cache_friendly_item_counter >
,cc::split_list::ordered_list_traits<
typename cc::iterable_list::make_traits<
co::less< less >
cc::split_list::ordered_list<cc::iterable_list_tag>
,cc::split_list::dynamic_bucket_table< false >
,co::hash< hash >
+ , co::item_counter<cds::atomicity::cache_friendly_item_counter >
,cc::split_list::ordered_list_traits<
typename cc::iterable_list::make_traits<
co::less< less >
cc::split_list::ordered_list<cc::iterable_list_tag>
,cc::split_list::dynamic_bucket_table< false >
,co::hash< hash >
+ , co::item_counter<cds::atomicity::cache_friendly_item_counter >
,co::stat< cc::split_list::stat<>>
,cc::split_list::ordered_list_traits<
typename cc::iterable_list::make_traits<
test_hp( l );
}
+ TEST_F( IntrusiveMichaelList_DHP, member_hook_cache_friendly_item_counting )
+ {
+ struct traits: public ci::michael_list::traits {
+ typedef ci::michael_list::member_hook< offsetof( member_item, hMember ), cds::opt::gc< gc_type >> hook;
+ typedef mock_disposer disposer;
+ typedef cmp< member_item > compare;
+ typedef intrusive_list_common::less< member_item > less;
+ typedef cds::atomicity::cache_friendly_item_counter item_counter;
+ };
+ typedef ci::MichaelList< gc_type, member_item, traits > list_type;
+
+ list_type l;
+ test_common( l );
+ test_ordered_iterator( l );
+ test_hp( l );
+ }
+
TEST_F( IntrusiveMichaelList_DHP, member_hook_seqcst )
{
struct traits : public ci::michael_list::traits {
test_hp( l );
}
+ TEST_F( IntrusiveMichaelList_HP, base_hook_cache_friendly_item_counting )
+ {
+ struct traits: public ci::michael_list::traits {
+ typedef ci::michael_list::base_hook< cds::opt::gc< gc_type >> hook;
+ typedef mock_disposer disposer;
+ typedef cmp< base_item > compare;
+ typedef intrusive_list_common::less< base_item > less;
+ typedef cds::atomicity::cache_friendly_item_counter item_counter;
+ };
+ typedef ci::MichaelList< gc_type, base_item, traits > list_type;
+
+ list_type l;
+ test_common( l );
+ test_ordered_iterator( l );
+ test_hp( l );
+ }
+
TEST_F( IntrusiveMichaelList_HP, base_hook_backoff )
{
struct traits : public ci::michael_list::traits {
projects / libcds.git / commitdiff