-//$$CDS-header$$
+/*
+ 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_SPLIT_LIST_RCU_H
#define CDSLIB_INTRUSIVE_SPLIT_LIST_RCU_H
- \p Traits - set traits, default isd \p split_list::traits.
Instead of defining \p Traits struct you may use option-based syntax with \p split_list::make_traits metafunction.
- @note About reqired features of hash functor see \ref cds_SplitList_hash_functor "SplitList general description".
+ @note About required features of hash functor see \ref cds_SplitList_hash_functor "SplitList general description".
\par How to use
Before including <tt><cds/intrusive/split_list_rcu.h></tt> you should include appropriate RCU header file,
/// 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;
protected:
typedef typename ordered_list::node_type list_node_type; ///< Node type as declared in ordered list
typedef split_list::node<list_node_type> node_type; ///< split-list node type
- typedef node_type dummy_node_type; ///< dummy node type
+ typedef node_type aux_node_type; ///< dummy node type
/// Split-list node traits
/**
typedef typename split_list::details::bucket_table_selector<
traits::dynamic_bucket_table
, gc
- , dummy_node_type
+ , aux_node_type
, opt::allocator< typename traits::allocator >
, opt::memory_model< memory_model >
>::type bucket_table;
class ordered_list_wrapper: public ordered_list
{
typedef ordered_list base_class;
- typedef typename base_class::auxiliary_head bucket_head_type;
+ typedef typename base_class::auxiliary_head bucket_head_type;
public:
- bool insert_at( dummy_node_type * pHead, value_type& val )
+ bool insert_at( aux_node_type * pHead, value_type& val )
{
assert( pHead != nullptr );
bucket_head_type h(pHead);
}
template <typename Func>
- bool insert_at( dummy_node_type * pHead, value_type& val, Func f )
+ bool insert_at( aux_node_type * pHead, value_type& val, Func f )
{
assert( pHead != nullptr );
bucket_head_type h(pHead);
}
template <typename Func>
- std::pair<bool, bool> ensure_at( dummy_node_type * pHead, value_type& val, Func func )
+ std::pair<bool, bool> update_at( aux_node_type * pHead, value_type& val, Func func, bool bAllowInsert )
{
assert( pHead != nullptr );
bucket_head_type h(pHead);
- return base_class::ensure_at( h, val, func );
+ return base_class::update_at( h, val, func, bAllowInsert );
}
- bool unlink_at( dummy_node_type * pHead, value_type& val )
+ bool unlink_at( aux_node_type * pHead, value_type& val )
{
assert( pHead != nullptr );
bucket_head_type h(pHead);
}
template <typename Q, typename Compare, typename Func>
- bool erase_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp, Func f )
+ bool erase_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp, Func f )
{
assert( pHead != nullptr );
bucket_head_type h(pHead);
}
template <typename Q, typename Compare>
- bool erase_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
+ bool erase_at( aux_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 * extract_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp )
+ value_type * extract_at( aux_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp )
{
assert( pHead != nullptr );
bucket_head_type h(pHead);
}
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 )
+ bool find_at( aux_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 )
+ bool find_at( aux_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>
- raw_ptr get_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp )
+ raw_ptr get_at( aux_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp )
{
assert( pHead != nullptr );
bucket_head_type h(pHead);
return base_class::get_at( h, val, cmp );
}
- bool insert_aux_node( dummy_node_type * pNode )
+ bool insert_aux_node( aux_node_type * pNode )
{
return base_class::insert_aux_node( pNode );
}
- bool insert_aux_node( dummy_node_type * pHead, dummy_node_type * pNode )
+ bool insert_aux_node( aux_node_type * pHead, aux_node_type * pNode )
{
bucket_head_type h(pHead);
return base_class::insert_aux_node( h, pNode );
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
+ stat m_Stat; ///< Internal statistics accumulator
protected:
//@cond
- typedef cds::details::Allocator< dummy_node_type, typename traits::allocator > dummy_node_allocator;
+ typedef cds::details::Allocator< aux_node_type, typename traits::allocator > aux_node_allocator;
- dummy_node_type * alloc_dummy_node( size_t nHash )
+ aux_node_type * alloc_aux_node( size_t nHash )
{
m_Stat.onHeadNodeAllocated();
- return dummy_node_allocator().New( nHash );
+ return aux_node_allocator().New( nHash );
}
- void free_dummy_node( dummy_node_type * p )
+ void free_aux_node( aux_node_type * p )
{
- dummy_node_allocator().Delete( p );
+ aux_node_allocator().Delete( p );
m_Stat.onHeadNodeFreed();
}
return nBucket & ~( 1 << bitop::MSBnz( nBucket ) );
}
- dummy_node_type * init_bucket( size_t nBucket )
+ aux_node_type * init_bucket( size_t nBucket )
{
assert( nBucket > 0 );
size_t nParent = parent_bucket( nBucket );
- dummy_node_type * pParentBucket = m_Buckets.bucket( nParent );
+ aux_node_type * pParentBucket = m_Buckets.bucket( nParent );
if ( pParentBucket == nullptr ) {
pParentBucket = init_bucket( nParent );
m_Stat.onRecursiveInitBucket();
// Allocate a dummy node for new bucket
{
- dummy_node_type * pBucket = alloc_dummy_node( split_list::dummy_hash( nBucket ) );
+ aux_node_type * pBucket = alloc_aux_node( split_list::dummy_hash( nBucket ) );
if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
m_Buckets.bucket( nBucket, pBucket );
m_Stat.onNewBucket();
return pBucket;
}
- free_dummy_node( pBucket );
+ free_aux_node( pBucket );
}
// Another thread set the bucket. Wait while it done
m_Stat.onBucketInitContenton();
back_off bkoff;
while ( true ) {
- dummy_node_type volatile * p = m_Buckets.bucket( nBucket );
+ aux_node_type volatile * p = m_Buckets.bucket( nBucket );
if ( p != nullptr )
- return const_cast<dummy_node_type *>( p );
+ return const_cast<aux_node_type *>( p );
bkoff();
m_Stat.onBusyWaitBucketInit();
}
}
- dummy_node_type * get_bucket( size_t nHash )
+ aux_node_type * get_bucket( size_t nHash )
{
size_t nBucket = bucket_no( nHash );
- dummy_node_type * pHead = m_Buckets.bucket( nBucket );
+ aux_node_type * pHead = m_Buckets.bucket( nBucket );
if ( pHead == nullptr )
pHead = init_bucket( nBucket );
"cds::atomicity::empty_item_counter is not allowed as a item counter");
// Initialize bucket 0
- dummy_node_type * pNode = alloc_dummy_node( 0 /*split_list::dummy_hash(0)*/ );
+ aux_node_type * pNode = alloc_aux_node( 0 /*split_list::dummy_hash(0)*/ );
// insert_aux_node cannot return false for empty list
CDS_VERIFY( m_List.insert_aux_node( pNode ));
{
size_t nHash = hash_value( val );
split_list::details::search_value_type<Q> sv( val, split_list::regular_hash( nHash ));
- dummy_node_type * pHead = get_bucket( nHash );
+ aux_node_type * pHead = get_bucket( nHash );
assert( pHead != nullptr );
return m_Stat.onFind( m_List.find_at( pHead, sv, 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 );
+ aux_node_type * pHead = get_bucket( nHash );
assert( pHead != nullptr );
return m_Stat.onFind( m_List.find_at( pHead, sv, 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 );
+ aux_node_type * pHead = get_bucket( nHash );
assert( pHead != nullptr );
raw_ptr p = m_List.get_at( pHead, sv, 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 );
+ aux_node_type * pHead = get_bucket( nHash );
assert( pHead != nullptr );
value_type * pNode = m_List.extract_at( pHead, sv, 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 );
+ aux_node_type * pHead = get_bucket( nHash );
assert( pHead != nullptr );
if ( m_List.erase_at( pHead, sv, 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 );
+ aux_node_type * pHead = get_bucket( nHash );
assert( pHead != nullptr );
if ( m_List.erase_at( pHead, sv, cmp, f )) {
bool insert( value_type& val )
{
size_t nHash = hash_value( val );
- dummy_node_type * pHead = get_bucket( nHash );
+ aux_node_type * pHead = get_bucket( nHash );
assert( pHead != nullptr );
node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
bool insert( value_type& val, Func f )
{
size_t nHash = hash_value( val );
- dummy_node_type * pHead = get_bucket( nHash );
+ aux_node_type * pHead = get_bucket( nHash );
assert( pHead != nullptr );
node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
return false;
}
- /// Ensures that the \p val exists in the set
+ /// Updates the node
/**
The operation performs inserting or changing data with lock-free manner.
- If the item \p val is not found in the set, then \p val is inserted into the set.
+ If the item \p val is not found in the set, then \p val is inserted
+ iff \p bAllowInsert is \p true.
Otherwise, the functor \p func is called with item found.
The functor signature is:
\code
with arguments:
- \p bNew - \p true if the item has been inserted, \p false otherwise
- \p item - item of the set
- - \p val - argument \p val passed into the \p ensure function
+ - \p val - argument \p val passed into the \p update() function
If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
- refers to the same thing.
+ refers to the same stuff.
- The function makes RCU lock internally.
+ The functor may change non-key fields of the \p item.
+
+ The function applies RCU lock internally.
- Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
+ Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
\p second is \p true if new item has been added or \p false if the item with \p key
- already is in the set.
+ already is in the list.
@warning For \ref cds_intrusive_MichaelList_rcu "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
\ref cds_intrusive_LazyList_rcu "LazyList" provides exclusive access to inserted item and does not require any node-level
synchronization.
- */
+ */
template <typename Func>
- std::pair<bool, bool> ensure( value_type& val, Func func )
+ std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
{
size_t nHash = hash_value( val );
- dummy_node_type * pHead = get_bucket( nHash );
+ aux_node_type * pHead = get_bucket( nHash );
assert( pHead != nullptr );
node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
- std::pair<bool, bool> bRet = m_List.ensure_at( pHead, val, func );
+ std::pair<bool, bool> bRet = m_List.update_at( pHead, val, func, bAllowInsert );
if ( bRet.first && bRet.second ) {
inc_item_count();
- m_Stat.onEnsureNew();
+ m_Stat.onUpdateNew();
}
else
- m_Stat.onEnsureExist();
+ m_Stat.onUpdateExist();
return bRet;
}
+ //@cond
+ template <typename Func>
+ CDS_DEPRECATED("ensure() is deprecated, use update()")
+ std::pair<bool, bool> ensure( value_type& val, Func func )
+ {
+ return update( val, func, true );
+ }
+ //@endcond
/// Unlinks the item \p val from the set
/**
bool unlink( value_type& val )
{
size_t nHash = hash_value( val );
- dummy_node_type * pHead = get_bucket( nHash );
+ aux_node_type * pHead = get_bucket( nHash );
assert( pHead != nullptr );
if ( m_List.unlink_at( pHead, val ) ) {
}
//@endcond
- /// Finds the key \p key
- /** \anchor cds_intrusive_SplitListSet_rcu_find_val
+ /// Checks whether the set contains \p key
+ /**
The function searches the item with key equal to \p key
- and returns \p true if \p key found or \p false otherwise.
+ and returns \p true if it is found, and \p false otherwise.
+
+ Note the hash functor specified for class \p Traits template parameter
+ should accept a parameter of type \p Q that can be not the same as \p value_type.
+ Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing.
*/
template <typename Q>
- bool find( Q const& key )
+ bool contains( Q const& key )
{
return find_value( key, key_comparator() );
}
+ //@cond
+ template <typename Q>
+ CDS_DEPRECATED("deprecated, use contains()")
+ bool find( Q const& key )
+ {
+ return contains( key );
+ }
+ //@endcond
- /// Finds the key \p key with \p pred predicate for comparing
+ /// Checks whether the set contains \p key using \p pred predicate for searching
/**
- The function is an analog of \ref cds_intrusive_SplitListSet_rcu_find_val "find(Q const&)"
- but \p cmp is used for key compare.
- \p Less has the interface like \p std::less.
- \p pred must imply the same element order as the comparator used for building the set.
+ The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
+ \p Less functor has the interface like \p std::less.
+ \p Less must imply the same element order as the comparator used for building the list.
*/
template <typename Q, typename Less>
- bool find_with( Q const& key, Less pred )
+ bool contains( Q const& key, Less pred )
{
CDS_UNUSED( pred );
return find_value( key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
}
+ //@cond
+ template <typename Q, typename Less>
+ CDS_DEPRECATED("deprecated, use contains()")
+ bool find_with( Q const& key, Less pred )
+ {
+ return contains( key, pred );
+ }
+ //@endcond
/// Finds the key \p key and return the item found
/** \anchor cds_intrusive_SplitListSet_rcu_get
{}
};
//@endcond
+
public:
+ ///@name Forward iterators (thread-safe under RCU lock)
+ //@{
/// Forward iterator
/**
The forward iterator for a split-list has some features:
- it has no post-increment operator
- it depends on iterator of underlying \p OrderedList
- - The iterator cannot be moved across thread boundary since it may contain GC's guard that is thread-private GC data.
- - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
- deleting operations it is no guarantee that you iterate all item in the split-list.
- Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
- for debug purpose only.
+ You may safely use iterators in multi-threaded environment only under RCU lock.
+ Otherwise, a crash is possible if another thread deletes the element the iterator points to.
*/
typedef iterator_type<false> iterator;
+
/// Const forward iterator
/**
For iterator's features and requirements see \ref iterator
{
return const_iterator( m_List.cend(), m_List.cend() );
}
-
+ //@}
};
}} // namespace cds::intrusive
projects / libcds.git / blobdiff