//$$CDS-header$$
-#ifndef __CDS_INTRUSIVE_SPLIT_LIST_RCU_H
-#define __CDS_INTRUSIVE_SPLIT_LIST_RCU_H
+#ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_RCU_H
+#define CDSLIB_INTRUSIVE_SPLIT_LIST_RCU_H
+
+#include <limits>
#include <cds/intrusive/details/split_list_base.h>
#include <cds/details/binary_functor_wrapper.h>
/// Hash functor for \ref value_type and all its derivatives that you use
typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
+ //@cond
+ typedef cds::intrusive::split_list::implementation_tag implementation_tag;
+ //@endcond
+
protected:
//@cond
typedef split_list::details::rebind_list_traits<OrderedList, traits> wrapped_ordered_list;
typedef typename ordered_list::disposer disposer; ///< Node disposer functor
typedef typename ordered_list::rcu_lock rcu_lock; ///< RCU scoped lock
typedef typename ordered_list::exempt_ptr exempt_ptr; ///< pointer to extracted node
+ typedef typename ordered_list::raw_ptr raw_ptr; ///< pointer to the node for \p get() function
/// Group of \p extract_xxx functions require external locking if underlying ordered list requires that
static CDS_CONSTEXPR const bool c_bExtractLockExternal = ordered_list::c_bExtractLockExternal;
}
template <typename Q, typename Compare, typename Func>
- bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f ) const
+ bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
{
assert( pHead != nullptr );
bucket_head_type h(pHead);
}
template <typename Q, typename Compare>
- bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const & val, Compare cmp ) const
+ bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const & val, Compare cmp )
{
assert( pHead != nullptr );
bucket_head_type h(pHead);
}
template <typename Q, typename Compare>
- value_type * get_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp ) const
+ raw_ptr get_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp )
{
assert( pHead != nullptr );
bucket_head_type h(pHead);
ordered_list_wrapper m_List; ///< Ordered list containing split-list items
bucket_table m_Buckets; ///< bucket table
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
stat m_Stat; ///< Internal stattistics accumulator
size_t bucket_no( size_t nHash ) const
{
- return nHash & ( (1 << m_nBucketCountLog2.load(atomics::memory_order_relaxed)) - 1 );
+ return nHash & ( (1 << m_nBucketCountLog2.load(memory_model::memory_order_relaxed)) - 1 );
}
static size_t parent_bucket( size_t nBucket )
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,
+ 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");
// Initialize bucket 0
m_Buckets.bucket( 0, pNode );
}
- void inc_item_count()
+ static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
{
- size_t sz = m_nBucketCountLog2.load(atomics::memory_order_relaxed);
- if ( ( ++m_ItemCounter >> sz ) > m_Buckets.load_factor() && ((size_t)(1 << sz )) < m_Buckets.capacity() )
- {
- m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, atomics::memory_order_seq_cst, atomics::memory_order_relaxed );
+ return nBucketCount * nLoadFactor;
+ }
+
+ void inc_item_count()
+ {
+ size_t nMaxCount = m_nMaxItemCount.load(memory_model::memory_order_relaxed);
+ if ( ++m_ItemCounter <= nMaxCount )
+ return;
+
+ size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed);
+ const size_t nBucketCount = static_cast<size_t>(1) << sz;
+ if ( nBucketCount < m_Buckets.capacity() ) {
+ // we may grow the bucket table
+ const size_t nLoadFactor = m_Buckets.load_factor();
+ if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
+ return; // someone already have updated m_nBucketCountLog2, so stop here
+
+ m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
+ memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
+ m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
}
+ else
+ m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
}
template <typename Q, typename Compare, typename Func>
}
template <typename Q, typename Compare>
- value_type * get_( Q const& val, Compare cmp )
+ raw_ptr get_( Q const& val, Compare cmp )
{
size_t nHash = hash_value( val );
split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
dummy_node_type * pHead = get_bucket( nHash );
assert( pHead != nullptr );
- value_type * p = m_List.get_at( pHead, sv, cmp );
- m_Stat.onFind( p != nullptr );
+ raw_ptr p = m_List.get_at( pHead, sv, cmp );
+ m_Stat.onFind( !!p );
return p;
}
template <typename Q, typename Less>
value_type * extract_with_( Q const& val, Less pred )
{
+ CDS_UNUSED( pred );
return extract_( val, typename wrapped_ordered_list::template make_compare_from_less<Less>());
}
*/
SplitListSet()
: m_nBucketCountLog2(1)
+ , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
{
init();
}
)
: m_Buckets( nItemCount, nLoadFactor )
, m_nBucketCountLog2(1)
+ , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
{
init();
}
template <typename Q, typename Less>
bool erase_with( Q const& key, Less pred )
{
+ CDS_UNUSED( pred );
return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
}
void operator()( value_type const& item );
};
\endcode
- The functor can be passed by reference with <tt>boost:ref</tt>
If the item with key equal to \p key is not found the function return \p false.
template <typename Q, typename Less, typename Func>
bool erase_with( Q const& key, Less pred, Func f )
{
+ CDS_UNUSED( pred );
return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
}
/// Extracts an item from the set
/** \anchor cds_intrusive_SplitListSet_rcu_extract
The function searches an item with key equal to \p key in the set,
- unlinks it, and returns pointer to an item found in \p dest argument.
- If the item with the key equal to \p key is not found the function returns \p false.
+ unlinks it, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
+ If the item with the key equal to \p key is not found the function returns an empty \p exempt_ptr.
- @note The function does NOT call RCU read-side lock or synchronization,
- and does NOT dispose the item found. It just excludes the item from the set
- and returns a pointer to item found.
- You should lock RCU before calling of the function, and you should synchronize RCU
- outside the RCU lock before reusing returned pointer.
+ Depends on \p bucket_type you should or should not lock RCU before calling of this function:
+ - for the set based on \ref cds_intrusive_MichaelList_rcu "MichaelList" RCU should not be locked
+ - for the set based on \ref cds_intrusive_LazyList_rcu "LazyList" RCU should be locked
+ See ordered list implementation for details.
\code
typedef cds::urcu::gc< general_buffered<> > rcu;
// ...
rcu_splitlist_set::exempt_ptr p;
- {
- // first, we should lock RCU
- rcu_splitlist_set::rcu_lock lock;
-
- // Now, you can apply extract function
- // Note that you must not delete the item found inside the RCU lock
- if ( theList.extract( p, 10 )) {
- // do something with p
- ...
- }
+
+ // For MichaelList we should not lock RCU
+
+ // Now, you can apply extract function
+ // Note that you must not delete the item found inside the RCU lock
+ p = theList.extract( 10 );
+ if ( p ) {
+ // do something with p
+ ...
}
// We may safely release p here
\endcode
*/
template <typename Q>
- bool extract( exempt_ptr& dest, Q const& key )
+ exempt_ptr extract( Q const& key )
{
- value_type * pNode = extract_( key, key_comparator() );
- if ( pNode ) {
- dest = pNode;
- return true;
- }
- return false;
+ return exempt_ptr(extract_( key, key_comparator() ));
}
/// Extracts an item from the set using \p pred for searching
/**
- The function is an analog of \ref cds_intrusive_SplitListSet_rcu_extract "extract(exempt_ptr&, Q const&)"
- but \p pred is used for key compare.
+ The function is an analog of \p extract(Q const&) but \p pred is used for key compare.
\p Less functor has the interface like \p std::less.
\p pred must imply the same element order as the comparator used for building the set.
*/
template <typename Q, typename Less>
- bool extract_with( exempt_ptr& dest, Q const& key, Less pred )
+ exempt_ptr extract_with( Q const& key, Less pred )
{
- value_type * pNode = extract_with_( key, pred );
- if ( pNode ) {
- dest = pNode;
- return true;
- }
- return false;
+ return exempt_ptr( extract_with_( key, pred ));
}
/// Finds the key \p key
\endcode
where \p item is the item found, \p key is the <tt>find</tt> function argument.
- You can pass \p f argument by value or by reference using \p std::ref.
-
The functor can change non-key fields of \p item. Note that the functor is only guarantee
that \p item cannot be disposed during functor is executing.
The functor does not serialize simultaneous access to the set \p item. If such access is
{
return find_( key, key_comparator(), f );
}
+ //@cond
+ template <typename Q, typename Func>
+ bool find( Q const& key, Func f )
+ {
+ return find_( key, key_comparator(), f );
+ }
+ //@endcond
/// Finds the key \p key with \p pred predicate for comparing
/**
template <typename Q, typename Less, typename Func>
bool find_with( Q& key, Less pred, Func f )
{
+ CDS_UNUSED( pred );
return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
}
-
+ //@cond
+ template <typename Q, typename Less, typename Func>
+ bool find_with( Q const& key, Less pred, Func f )
+ {
+ CDS_UNUSED( pred );
+ return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
+ }
+ //@endcond
/// Finds the key \p key
/** \anchor cds_intrusive_SplitListSet_rcu_find_val
template <typename Q, typename Less>
bool find_with( Q const& key, Less pred )
{
+ CDS_UNUSED( pred );
return find_value( key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
}
RCU should be locked before call of this function.
Returned item is valid only while RCU is locked:
\code
- cds::intrusive::SplitListSet< your_template_parameters > theSet;
+ typedef cds::intrusive::SplitListSet< your_template_parameters > set_class;
+ set_class theSet;
// ...
+ typename set_class::raw_ptr rp;
{
// Lock RCU
hash_set::rcu_lock lock;
- foo * pVal = theSet.get( 5 );
- if ( pVal ) {
- // Deal with pVal
+ rp = theSet.get( 5 );
+ if ( rp ) {
+ // Deal with rp
//...
}
// Unlock RCU by rcu_lock destructor
- // pVal can be retired by disposer at any time after RCU has been unlocked
+ // rp can be retired by disposer at any time after RCU has been unlocked
}
\endcode
*/
template <typename Q>
- value_type * get( Q const& key )
+ raw_ptr get( Q const& key )
{
return get_( key, key_comparator() );
}
\p pred must imply the same element order as the comparator used for building the set.
*/
template <typename Q, typename Less>
- value_type * get_with( Q const& key, Less pred )
+ raw_ptr get_with( Q const& key, Less pred )
{
+ CDS_UNUSED( pred );
return get_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
}
/// Returns a forward const iterator addressing the first element in a split-list
const_iterator begin() const
{
- return const_iterator( m_List.begin(), m_List.end() );
+ return cbegin();
+ }
+ /// Returns a forward const iterator addressing the first element in a split-list
+ const_iterator cbegin() const
+ {
+ return const_iterator( m_List.cbegin(), m_List.cend() );
}
/// Returns an const iterator that addresses the location succeeding the last element in a split-list
const_iterator end() const
{
- return const_iterator( m_List.end(), m_List.end() );
+ return cend();
+ }
+ /// Returns an const iterator that addresses the location succeeding the last element in a split-list
+ const_iterator cend() const
+ {
+ return const_iterator( m_List.cend(), m_List.cend() );
}
};
}} // namespace cds::intrusive
-#endif // #ifndef __CDS_INTRUSIVE_SPLIT_LIST_RCU_H
+#endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_RCU_H
projects / libcds.git / blobdiff