#ifndef __CDS_INTRUSIVE_ELLEN_BINTREE_RCU_H
#define __CDS_INTRUSIVE_ELLEN_BINTREE_RCU_H
+#include <memory>
#include <cds/intrusive/details/ellen_bintree_base.h>
#include <cds/opt/compare.h>
-#include <cds/ref.h>
#include <cds/details/binary_functor_wrapper.h>
#include <cds/urcu/details/check_deadlock.h>
-#include <cds/details/std/memory.h>
#include <cds/urcu/exempt_ptr.h>
namespace cds { namespace intrusive {
@warning Recall the tree is <b>unbalanced</b>. The complexity of operations is <tt>O(log N)</tt>
for uniformly distributed random keys, but in worst case the complexity is <tt>O(N)</tt>.
- @note In the current implementation we do not use helping technique described in original paper.
- So, the current implementation is near to fine-grained lock-based tree.
- Helping will be implemented in future release
+ @note In the current implementation we do not use helping technique described in the original paper.
+ In Hazard Pointer schema helping is too complicated and does not give any observable benefits.
+ Instead of helping, when a thread encounters a concurrent operation it just spins waiting for
+ the operation done. Such solution allows greatly simplify the implementation of tree.
<b>Template arguments</b> :
- \p RCU - one of \ref cds_urcu_gc "RCU type"
- \p Key - key type, a subset of \p T
- - \p T - type to be stored in tree's leaf nodes. The type must be based on ellen_bintree::node
- (for ellen_bintree::base_hook) or it must have a member of type ellen_bintree::node
- (for ellen_bintree::member_hook).
- - \p Traits - type traits. See ellen_bintree::type_traits for explanation.
-
- It is possible to declare option-based tree with cds::intrusive::ellen_bintree::make_traits metafunction
- instead of \p Traits template argument.
- Template argument list \p Options of cds::intrusive::ellen_bintree::make_traits metafunction are:
- - opt::hook - hook used. Possible values are: ellen_bintree::base_hook, ellen_bintree::member_hook, ellen_bintree::traits_hook.
- If the option is not specified, <tt>ellen_bintree::base_hook<></tt> is used.
- - ellen_bintree::key_extractor - key extracting functor, mandatory option. The functor has the following prototype:
- \code
- struct key_extractor {
- void operator ()( Key& dest, T const& src );
- };
- \endcode
- It should initialize \p dest key from \p src data. The functor is used to initialize internal nodes.
- - opt::compare - key compare functor. No default functor is provided.
- If the option is not specified, \p %opt::less is used.
- - opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
- - opt::disposer - the functor used for dispose removed nodes. Default is opt::v::empty_disposer. Due the nature
- of GC schema the disposer may be called asynchronously. The disposer is used only for leaf nodes.
- - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
- - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
- or opt::v::sequential_consistent (sequentially consisnent memory model).
- - ellen_bintree::update_desc_allocator - an allocator of \ref ellen_bintree::update_desc "update descriptors",
- default is CDS_DEFAULT_ALLOCATOR.
- Note that update descriptor is helping data structure with short lifetime and it is good candidate for pooling.
- The number of simultaneously existing descriptors is bounded and depends on the number of threads
- working with the tree and RCU buffer size (if RCU is buffered).
- Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue is good candidate
- for the free-list of update descriptors, see cds::memory::vyukov_queue_pool free-list implementation.
- Also notice that size of update descriptor is constant and not dependent on the type of data
- stored in the tree so single free-list object can be used for all \p %EllenBinTree objects.
- - opt::node_allocator - the allocator used for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
- - opt::stat - internal statistics. Available types: ellen_bintree::stat, ellen_bintree::empty_stat (the default)
- - opt::rcu_check_deadlock - a deadlock checking policy. Default is opt::v::rcu_throw_deadlock
+ - \p T - type to be stored in tree's leaf nodes. The type must be based on \p ellen_bintree::node
+ (for \p ellen_bintree::base_hook) or it must have a member of type \p ellen_bintree::node
+ (for \p ellen_bintree::member_hook).
+ - \p Traits - tree traits, default is \p ellen_bintree::traits
+ It is possible to declare option-based tree with \p ellen_bintree::make_traits metafunction
+ instead of \p Traits template argument.
@anchor cds_intrusive_EllenBinTree_rcu_less
<b>Predicate requirements</b>
- opt::less, opt::compare and other predicates using with member fuctions should accept at least parameters
+ \p Traits::less, \p Traits::compare and other predicates using with member fuctions should accept at least parameters
of type \p T and \p Key in any combination.
For example, for \p Foo struct with \p std::string key field the appropiate \p less functor is:
\code
@note Before including <tt><cds/intrusive/ellen_bintree_rcu.h></tt> you should include appropriate RCU header file,
see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
+ @anchor cds_intrusive_EllenBinTree_usage
<b>Usage</b>
Suppose we have the following Foo struct with string key type:
Such functor is necessary because the tree internal nodes store the keys.
- \p less predicate. We want our set should accept \p std::string
and <tt>char const *</tt> parameters for searching, so our \p less
- predicate should be non-trivial, see below.
+ predicate will not be trivial, see below.
- item counting feature: we want our set's \p size() member function
returns actual item count.
{ return v.m_strKey.compare(p) > 0; }
};
- // Type traits for our set
+ // Tree traits for our set
// It is necessary to specify only those typedefs that differ from
- // cds::intrusive::ellen_bintree::type_traits defaults.
- struct set_traits: public cds::intrusive::ellen_bintree::type_traits
+ // cds::intrusive::ellen_bintree::traits defaults.
+ struct set_traits: public cds::intrusive::ellen_bintree::traits
{
typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc<gpb_rcu> > > hook;
typedef my_key_extractor key_extractor;
// ...
\endcode
- Instead of declaring \p set_traits type traits we can use option-based syntax with \p %make_traits metafunction,
- for example:
+ Instead of declaring \p set_traits type traits we can use option-based syntax with
+ \p ellen_bintree::make_traits metafunction, for example:
\code
typedef cds::intrusive::EllenBinTree< gpb_rcu, std::string, Foo,
typename cds::intrusive::ellen_bintree::make_traits<
struct MyFoo
{
Foo m_foo;
- cds::intrusive:ellen_bintree::node< gpb_rcu > set_hook ; // member hook
+ cds::intrusive:ellen_bintree::node< gpb_rcu > set_hook; // member hook
};
// Key extractor functor
{ return v.m_foo.m_strKey.compare(p) > 0; }
};
- // Type traits for our member-based set
- struct member_set_traits: public cds::intrusive::ellen_bintree::type_traits
+ // Tree traits for our member-based set
+ struct member_set_traits: public cds::intrusive::ellen_bintree::traits
{
cds::intrusive::ellen_bintree::member_hook< offsetof(MyFoo, set_hook), cds::opt::gc<gpb_rcu> > > hook;
typedef member_key_extractor key_extractor;
typedef cds::urcu::gc< cds::urcu::general_buffered<> > gpb_rcu;
// Declare tag structs
- struct int_tag ; // in key tag
+ struct int_tag ; // int key tag
struct string_tag ; // string key tag
// Foo struct is derived from two ellen_bintree::node class
};
// Type traits for string-indexed set
- struct string_set_traits: public cds::intrusive::ellen_bintree::type_traits
+ struct string_set_traits: public cds::intrusive::ellen_bintree::traits
{
typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc<gpb_rcu> >, cds::opt::tag< string_tag > > hook;
typedef string_key_extractor key_extractor;
};
// Type traits for int-indexed set
- struct int_set_traits: public cds::intrusive::ellen_bintree::type_traits
+ struct int_set_traits: public cds::intrusive::ellen_bintree::traits
{
typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc<gpb_rcu> >, cds::opt::tag< int_tag > > hook;
typedef int_key_extractor key_extractor;
typename Key,
typename T,
#ifdef CDS_DOXYGEN_INVOKED
- class Traits = ellen_bintree::type_traits
+ class Traits = ellen_bintree::traits
#else
class Traits
#endif
class EllenBinTree< cds::urcu::gc<RCU>, Key, T, Traits >
{
public:
- typedef cds::urcu::gc<RCU> gc ; ///< RCU Garbage collector
- typedef Key key_type ; ///< type of a key stored in internal nodes; key is a part of \p value_type
- typedef T value_type ; ///< type of value stored in the binary tree
- typedef Traits options ; ///< Traits template parameter
+ typedef cds::urcu::gc<RCU> gc; ///< RCU Garbage collector
+ typedef Key key_type; ///< type of a key stored in internal nodes; key is a part of \p value_type
+ typedef T value_type; ///< type of value stored in the binary tree
+ typedef Traits traits; ///< Traits template parameter
- typedef typename options::hook hook ; ///< hook type
- typedef typename hook::node_type node_type ; ///< node type
+ typedef typename traits::hook hook; ///< hook type
+ typedef typename hook::node_type node_type; ///< node type
- typedef typename options::disposer disposer ; ///< leaf node disposer
+ typedef typename traits::disposer disposer; ///< leaf node disposer
+ typedef typename traits::back_off back_off; ///< back-off strategy
protected:
//@cond
- typedef ellen_bintree::base_node< gc > tree_node ; ///< Base type of tree node
- typedef node_type leaf_node ; ///< Leaf node type
- typedef ellen_bintree::internal_node< key_type, leaf_node > internal_node ; ///< Internal node type
- typedef ellen_bintree::update_desc< leaf_node, internal_node> update_desc ; ///< Update descriptor
- typedef typename update_desc::update_ptr update_ptr ; ///< Marked pointer to update descriptor
+ typedef ellen_bintree::base_node< gc > tree_node; ///< Base type of tree node
+ typedef node_type leaf_node; ///< Leaf node type
+ typedef ellen_bintree::internal_node< key_type, leaf_node > internal_node; ///< Internal node type
+ typedef ellen_bintree::update_desc< leaf_node, internal_node> update_desc; ///< Update descriptor
+ typedef typename update_desc::update_ptr update_ptr; ///< Marked pointer to update descriptor
//@endcond
public:
- typedef cds::urcu::exempt_ptr< gc, value_type, value_type, disposer, void > exempt_ptr ; ///< pointer to extracted node
+ using exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, disposer, void >; ///< pointer to extracted node
public:
# ifdef CDS_DOXYGEN_INVOKED
- typedef implementation_defined key_comparator ; ///< key compare functor based on opt::compare and opt::less option setter.
- typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< Node traits
+ typedef implementation_defined key_comparator; ///< key compare functor based on \p Traits::compare and \p Traits::less
+ typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< Node traits
# else
- typedef typename opt::details::make_comparator< value_type, options >::type key_comparator;
+ typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
struct node_traits: public get_node_traits< value_type, node_type, hook>::type
{
static internal_node const& to_internal_node( tree_node const& n )
};
# endif
- typedef typename options::item_counter item_counter; ///< Item counting policy used
- typedef typename options::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
- typedef typename options::stat stat ; ///< internal statistics type
- typedef typename options::rcu_check_deadlock rcu_check_deadlock ; ///< Deadlock checking policy
- typedef typename options::key_extractor key_extractor ; ///< key extracting functor
+ typedef typename traits::item_counter item_counter; ///< Item counting policy used
+ typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
+ typedef typename traits::stat stat; ///< internal statistics type
+ typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
+ typedef typename traits::key_extractor key_extractor; ///< key extracting functor
- typedef typename options::node_allocator node_allocator ; ///< Internal node allocator
- typedef typename options::update_desc_allocator update_desc_allocator ; ///< Update descriptor allocator
+ typedef typename traits::node_allocator node_allocator; ///< Internal node allocator
+ typedef typename traits::update_desc_allocator update_desc_allocator; ///< Update descriptor allocator
typedef typename gc::scoped_lock rcu_lock; ///< RCU scoped lock
- static CDS_CONSTEXPR_CONST bool c_bExtractLockExternal = false; ///< Group of \p extract_xxx functions do not require external locking
+ static CDS_CONSTEXPR const bool c_bExtractLockExternal = false; ///< Group of \p extract_xxx functions do not require external locking
protected:
//@cond
protected:
//@cond
- internal_node m_Root ; ///< Tree root node (key= Infinite2)
+ internal_node m_Root; ///< Tree root node (key= Infinite2)
leaf_node m_LeafInf1;
leaf_node m_LeafInf2;
//@endcond
- item_counter m_ItemCounter ; ///< item counter
- mutable stat m_Stat ; ///< internal statistics
+ item_counter m_ItemCounter; ///< item counter
+ mutable stat m_Stat; ///< internal statistics
protected:
//@cond
m_Root.m_pLeft.store( &m_LeafInf1, memory_model::memory_order_relaxed );
m_Root.m_pRight.store( &m_LeafInf2, memory_model::memory_order_release );
}
-
-# ifndef CDS_CXX11_LAMBDA_SUPPORT
- struct trivial_equal_functor {
- template <typename Q>
- bool operator()( Q const& , leaf_node const& ) const
- {
- return true;
- }
- };
-
- struct empty_insert_functor {
- void operator()( value_type& )
- {}
- };
-# endif
-# if !defined(CDS_CXX11_LAMBDA_SUPPORT) || (CDS_COMPILER == CDS_COMPILER_MSVC && CDS_COMPILER_VERSION == CDS_COMPILER_MSVC10)
- struct unlink_equal_functor {
- bool operator()( value_type const& v, leaf_node const& n ) const
- {
- return &v == node_traits::to_value_ptr( n );
- }
- };
- struct empty_erase_functor {
- void operator()( value_type const& )
- {}
- };
-# endif
//@endcond
public:
/// Default constructor
EllenBinTree()
{
- static_assert( (!std::is_same< key_extractor, opt::none >::value), "The key extractor option must be specified" );
+ static_assert( !std::is_same< key_extractor, opt::none >::value, "The key extractor option must be specified" );
make_empty_tree();
}
*/
bool insert( value_type& val )
{
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
return insert( val, []( value_type& ) {} );
-# else
- return insert( val, empty_insert_functor() );
-# endif
}
/// Inserts new node
\endcode
where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
\p val no any other changes could be made on this tree's item by concurrent threads.
- The user-defined functor is called only if the inserting is success and may be passed by reference
- using <tt>boost::ref</tt>
+ The user-defined functor is called only if the inserting is success.
RCU \p synchronize method can be called. RCU should not be locked.
*/
unique_internal_node_ptr pNewInternal;
retired_list updRetire;
+ back_off bkoff;
{
rcu_lock l;
pNewInternal.reset( alloc_internal_node() );
if ( try_insert( val, pNewInternal.get(), res, updRetire )) {
- cds::unref(f)( val );
+ f( val );
pNewInternal.release() ; // internal node is linked into the tree and should not be deleted
break;
}
}
+ bkoff();
m_Stat.onInsertRetry();
}
}
The functor can change non-key fields of the \p item; however, \p func must guarantee
that during changing no any other modifications could be made on this item by concurrent threads.
- You can pass \p func argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
-
RCU \p synchronize method can be called. RCU should not be locked.
- Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
+ Returns <tt>std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
\p second is \p true if new item has been added or \p false if the item with \p key
already is in the tree.
+
+ @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
*/
template <typename Func>
std::pair<bool, bool> ensure( value_type& val, Func func )
unique_internal_node_ptr pNewInternal;
retired_list updRetire;
+ back_off bkoff;
{
rcu_lock l;
search_result res;
for ( ;; ) {
if ( search( res, val, node_compare() )) {
- cds::unref(func)( false, *node_traits::to_value_ptr( res.pLeaf ), val );
+ func( false, *node_traits::to_value_ptr( res.pLeaf ), val );
if ( pNewInternal.get() )
m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
m_Stat.onEnsureExist();
pNewInternal.reset( alloc_internal_node() );
if ( try_insert( val, pNewInternal.get(), res, updRetire )) {
- cds::unref(func)( true, val, val );
+ func( true, val, val );
pNewInternal.release() ; // internal node is linked into the tree and should not be deleted
break;
}
}
+
+ bkoff();
m_Stat.onEnsureRetry();
}
}
*/
bool unlink( value_type& val )
{
-# if defined(CDS_CXX11_LAMBDA_SUPPORT) && !(CDS_COMPILER == CDS_COMPILER_MSVC && CDS_COMPILER_VERSION == CDS_COMPILER_MSVC10)
- // vc10 generates an error for the lambda - it sees cds::intrusive::node_traits but not class-defined node_traits
return erase_( val, node_compare(),
[]( value_type const& v, leaf_node const& n ) -> bool { return &v == node_traits::to_value_ptr( n ); },
[](value_type const&) {} );
-# else
- return erase_( val, node_compare(), unlink_equal_functor(), empty_erase_functor() );
-# endif
}
/// Deletes the item from the tree
/** \anchor cds_intrusive_EllenBinTree_rcu_erase
- The function searches an item with key equal to \p val in the tree,
+ The function searches an item with key equal to \p key in the tree,
unlinks it from the tree, and returns \p true.
- If the item with key equal to \p val is not found the function return \p false.
+ If the item with key equal to \p key is not found the function return \p false.
Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
RCU \p synchronize method can be called. RCU should not be locked.
*/
template <typename Q>
- bool erase( const Q& val )
+ bool erase( const Q& key )
{
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
- return erase_( val, node_compare(),
+ return erase_( key, node_compare(),
[]( Q const&, leaf_node const& ) -> bool { return true; },
[](value_type const&) {} );
-# else
- return erase_( val, node_compare(), trivial_equal_functor(), empty_erase_functor() );
-# endif
}
/// Delete the item from the tree with comparing functor \p pred
\p pred must imply the same element order as the comparator used for building the tree.
*/
template <typename Q, typename Less>
- bool erase_with( const Q& val, Less pred )
+ bool erase_with( const Q& key, Less pred )
{
+ CDS_UNUSED( pred );
typedef ellen_bintree::details::compare<
key_type,
value_type,
node_traits
> compare_functor;
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
- return erase_( val, compare_functor(),
+ return erase_( key, compare_functor(),
[]( Q const&, leaf_node const& ) -> bool { return true; },
[](value_type const&) {} );
-# else
- return erase_( val, compare_functor(), trivial_equal_functor(), empty_erase_functor() );
-# endif
}
/// Deletes the item from the tree
/** \anchor cds_intrusive_EllenBinTree_rcu_erase_func
- The function searches an item with key equal to \p val in the tree,
+ The function searches an item with key equal to \p key in the tree,
call \p f functor with item found, unlinks it from the tree, and returns \p true.
The \ref disposer specified in \p Traits class template parameter is called
by garbage collector \p GC asynchronously.
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 val is not found the function return \p false.
+ If the item with key equal to \p key is not found the function return \p false.
Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
RCU \p synchronize method can be called. RCU should not be locked.
*/
template <typename Q, typename Func>
- bool erase( Q const& val, Func f )
+ bool erase( Q const& key, Func f )
{
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
- return erase_( val, node_compare(),
+ return erase_( key, node_compare(),
[]( Q const&, leaf_node const& ) -> bool { return true; },
f );
-# else
- return erase_( val, node_compare(), trivial_equal_functor(), f );
-# endif
}
/// Delete the item from the tree with comparing functor \p pred
\p pred must imply the same element order as the comparator used for building the tree.
*/
template <typename Q, typename Less, typename Func>
- bool erase_with( Q const& val, Less pred, Func f )
+ bool erase_with( Q const& key, Less pred, Func f )
{
+ CDS_UNUSED( pred );
typedef ellen_bintree::details::compare<
key_type,
value_type,
node_traits
> compare_functor;
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
- return erase_( val, compare_functor(),
+ return erase_( key, compare_functor(),
[]( Q const&, leaf_node const& ) -> bool { return true; },
f );
-# else
- return erase_( val, compare_functor(), trivial_equal_functor(), f );
-# endif
}
/// Extracts an item with minimal key from the tree
/**
- The function searches an item with minimal key, unlinks it, and returns pointer to an item found in \p result parameter.
- If the tree is empty the function returns \p false.
+ The function searches an item with minimal key, unlinks it, and returns
+ \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the leftmost item.
+ If the tree is empty the function returns empty \p exempt_ptr.
@note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
It means that the function gets leftmost leaf of the tree and tries to unlink it.
RCU \p synchronize method can be called. RCU should NOT be locked.
The function does not call the disposer for the item found.
- The disposer will be implicitly invoked when \p result object is destroyed or when
- <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
- @note Before reusing \p result object you should call its \p release() method.
+ The disposer will be implicitly invoked when the returned object is destroyed or when
+ its \p release() member function is called.
*/
- bool extract_min(exempt_ptr& result)
+ exempt_ptr extract_min()
{
- return extract_min_(result);
+ return exempt_ptr( extract_min_() );
}
/// Extracts an item with maximal key from the tree
/**
- The function searches an item with maximal key, unlinks it, and returns pointer to an item found in \p result prameter.
- If the tree is empty the function returns \p false.
+ The function searches an item with maximal key, unlinks it, and returns
+ \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the rightmost item.
+ If the tree is empty the function returns empty \p exempt_ptr.
@note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
It means that the function gets rightmost leaf of the tree and tries to unlink it.
RCU \p synchronize method can be called. RCU should NOT be locked.
The function does not call the disposer for the item found.
- The disposer will be implicitly invoked when \p result object is destroyed or when
- <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
- @note Before reusing \p result object you should call its \p release() method.
+ The disposer will be implicitly invoked when the returned object is destroyed or when
+ its \p release() member function is called.
*/
- bool extract_max(exempt_ptr& result)
+ exempt_ptr extract_max()
{
- return extract_max_(result);
+ return exempt_ptr( extract_max_() );
}
/// Extracts an item from the tree
/** \anchor cds_intrusive_EllenBinTree_rcu_extract
The function searches an item with key equal to \p key in the tree,
- unlinks it, and returns pointer to an item found in \p result parameter.
- 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 an item found.
+ If the item with the key equal to \p key is not found the function returns empty \p exempt_ptr.
RCU \p synchronize method can be called. RCU should NOT be locked.
The function does not call the disposer for the item found.
- The disposer will be implicitly invoked when \p result object is destroyed or when
- <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
- @note Before reusing \p result object you should call its \p release() method.
+ The disposer will be implicitly invoked when the returned object is destroyed or when
+ its \p release() member function is called.
*/
template <typename Q>
- bool extract( exempt_ptr& result, Q const& key )
+ exempt_ptr extract( Q const& key )
{
- return extract_( result, key, node_compare() );
+ return exempt_ptr( extract_( key, node_compare() ));
}
/// Extracts an item from the set using \p pred for searching
\p pred must imply the same element order as the comparator used for building the tree.
*/
template <typename Q, typename Less>
- bool extract_with( exempt_ptr& dest, Q const& val, Less pred )
+ exempt_ptr extract_with( Q const& key, Less pred )
{
- return extract_with_( dest, val, pred );
+ return exempt_ptr( extract_with_( key, pred ));
}
- /// Finds the key \p val
+ /// Finds the key \p key
/** @anchor cds_intrusive_EllenBinTree_rcu_find_val
- The function searches the item with key equal to \p val
+ The function searches the item with key equal to \p key
and returns \p true if it is found, and \p false otherwise.
Note the hash functor specified for class \p Traits template parameter
The function applies RCU lock internally.
*/
template <typename Q>
- bool find( Q const& val ) const
+ bool find( Q const& key ) const
{
rcu_lock l;
search_result res;
- if ( search( res, val, node_compare() )) {
+ if ( search( res, key, node_compare() )) {
m_Stat.onFindSuccess();
return true;
}
return false;
}
- /// Finds the key \p val with comparing functor \p pred
+ /// Finds the key \p key with comparing functor \p pred
/**
The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_val "find(Q const&)"
but \p pred is used for key compare.
\p pred should accept arguments of type \p Q, \p key_type, \p value_type in any combination.
*/
template <typename Q, typename Less>
- bool find_with( Q const& val, Less pred ) const
+ bool find_with( Q const& key, Less pred ) const
{
+ CDS_UNUSED( pred );
typedef ellen_bintree::details::compare<
key_type,
value_type,
rcu_lock l;
search_result res;
- if ( search( res, val, compare_functor() )) {
+ if ( search( res, key, compare_functor() )) {
m_Stat.onFindSuccess();
return true;
}
return false;
}
- /// Finds the key \p val
+ /// Finds the key \p key
/** @anchor cds_intrusive_EllenBinTree_rcu_find_func
- The function searches the item with key equal to \p val and calls the functor \p f for item found.
+ The function searches the item with key equal to \p key and calls the functor \p f for item found.
The interface of \p Func functor is:
\code
struct functor {
- void operator()( value_type& item, Q& val );
+ void operator()( value_type& item, Q& key );
};
\endcode
- where \p item is the item found, \p val is the <tt>find</tt> function argument.
-
- You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
+ where \p item is the item found, \p key is the <tt>find</tt> function argument.
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 tree \p item. If such access is
possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
- The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
- can modify both arguments.
-
The function applies RCU lock internally.
- The function returns \p true if \p val is found, \p false otherwise.
+ The function returns \p true if \p key is found, \p false otherwise.
*/
template <typename Q, typename Func>
- bool find( Q& val, Func f ) const
+ bool find( Q& key, Func f ) const
{
- return find_( val, f );
+ return find_( key, f );
}
+ //@cond
+ template <typename Q, typename Func>
+ bool find( Q const& key, Func f ) const
+ {
+ return find_( key, f );
+ }
+ //@endcond
- /// Finds the key \p val with comparing functor \p pred
+ /// Finds the key \p key with comparing functor \p pred
/**
The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_func "find(Q&, Func)"
but \p pred is used for key comparison.
\p pred must imply the same element order as the comparator used for building the tree.
*/
template <typename Q, typename Less, typename Func>
- bool find_with( Q& val, Less pred, Func f ) const
+ bool find_with( Q& key, Less pred, Func f ) const
{
- return find_with_( val, pred, f );
+ return find_with_( key, pred, f );
}
-
- /// Finds the key \p val
- /** @anchor cds_intrusive_EllenBinTree_rcu_find_cfunc
- The function searches the item with key equal to \p val and calls the functor \p f for item found.
- The interface of \p Func functor is:
- \code
- struct functor {
- void operator()( value_type& item, Q const& val );
- };
- \endcode
- where \p item is the item found, \p val is the <tt>find</tt> function argument.
-
- You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::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 tree \p item. If such access is
- possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
-
- The function applies RCU lock internally.
-
- The function returns \p true if \p val is found, \p false otherwise.
- */
- template <typename Q, typename Func>
- bool find( Q const& val, Func f ) const
- {
- return find_( val, f );
- }
-
- /// Finds the key \p val with comparing functor \p pred
- /**
- The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_cfunc "find(Q const&, Func)"
- but \p pred is used for key compare.
- \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
- "Predicate requirements".
- \p pred must imply the same element order as the comparator used for building the tree.
- */
+ //@cond
template <typename Q, typename Less, typename Func>
- bool find_with( Q const& val, Less pred, Func f ) const
+ bool find_with( Q const& key, Less pred, Func f ) const
{
- return find_with_( val, pred, f );
+ return find_with_( key, pred, f );
}
+ //@endcond
/// Finds \p key and return the item found
/** \anchor cds_intrusive_EllenBinTree_rcu_get
The function searches the item with key equal to \p key and returns the pointer to item found.
- If \p key is not found it returns \p NULL.
+ If \p key is not found it returns \p nullptr.
RCU should be locked before call the function.
Returned pointer is valid while RCU is locked.
template <typename Q, typename Less>
value_type * get_with( Q const& key, Less pred ) const
{
+ CDS_UNUSED( pred );
typedef ellen_bintree::details::compare<
key_type,
value_type,
return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
}
- /// Clears the tree (thread safe, non-atomic)
+ /// Clears the tree (thread safe, not atomic)
/**
The function unlink all items from the tree.
The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
*/
void clear()
{
- exempt_ptr ep;
- while ( extract_min(ep) )
+ for ( exempt_ptr ep = extract_min(); !ep.empty(); ep = extract_min() )
ep.release();
}
Only leaf nodes containing user data are counted.
The value returned depends on item counter type provided by \p Traits template parameter.
- If it is atomicity::empty_item_counter this function always returns 0.
- Therefore, the function is not suitable for checking the tree emptiness, use \ref empty
- member function for this purpose.
+ If it is \p atomicity::empty_item_counter this function always returns 0.
+
+ The function is not suitable for checking the tree emptiness, use \p empty()
+ member function for that.
*/
size_t size() const
{
bool check_consistency( internal_node const * pRoot ) const
{
- tree_node * pLeft = pRoot->m_pLeft.load( CDS_ATOMIC::memory_order_relaxed );
- tree_node * pRight = pRoot->m_pRight.load( CDS_ATOMIC::memory_order_relaxed );
+ tree_node * pLeft = pRoot->m_pLeft.load( atomics::memory_order_relaxed );
+ tree_node * pRight = pRoot->m_pRight.load( atomics::memory_order_relaxed );
assert( pLeft );
assert( pRight );
return false;
}
- void help( update_ptr pUpdate, retired_list& rl )
+ void help( update_ptr /*pUpdate*/, retired_list& /*rl*/ )
{
/*
switch ( pUpdate.bits() ) {
tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
if ( pOp->iInfo.bRightLeaf ) {
pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
- memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed );
+ memory_model::memory_order_release, atomics::memory_order_relaxed );
}
else {
pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
- memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed );
+ memory_model::memory_order_release, atomics::memory_order_relaxed );
}
update_ptr cur( pOp, update_desc::IFlag );
pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
- memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed );
+ memory_model::memory_order_release, atomics::memory_order_relaxed );
}
bool check_delete_precondition( search_result& res )
update_ptr pUpdate( pOp->dInfo.pUpdateParent );
update_ptr pMark( pOp, update_desc::Mark );
if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark,
- memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
+ memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
{
help_marked( pOp );
retire_node( pOp->dInfo.pParent, rl );
// Undo grandparent dInfo
update_ptr pDel( pOp, update_desc::DFlag );
if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
- memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ))
+ memory_model::memory_order_release, atomics::memory_order_relaxed ))
{
retire_update_desc( pOp, rl, false );
}
pOp->dInfo.bRightLeaf
? pOp->dInfo.pParent->m_pLeft.load( memory_model::memory_order_acquire )
: pOp->dInfo.pParent->m_pRight.load( memory_model::memory_order_acquire ),
- memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed );
+ memory_model::memory_order_release, atomics::memory_order_relaxed );
}
else {
pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( p,
pOp->dInfo.bRightLeaf
? pOp->dInfo.pParent->m_pLeft.load( memory_model::memory_order_acquire )
: pOp->dInfo.pParent->m_pRight.load( memory_model::memory_order_acquire ),
- memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed );
+ memory_model::memory_order_release, atomics::memory_order_relaxed );
}
update_ptr upd( pOp, update_desc::DFlag );
pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
- memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed );
+ memory_model::memory_order_release, atomics::memory_order_relaxed );
}
template <typename KeyValue, typename Compare>
retired_list updRetire;
update_desc * pOp = nullptr;
search_result res;
+ back_off bkoff;
{
rcu_lock l;
update_ptr updGP( res.updGrandParent.ptr() );
if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
- memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
+ memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
{
if ( help_delete( pOp, updRetire )) {
// res.pLeaf is not deleted yet since RCU is blocked
- cds::unref(f)( *node_traits::to_value_ptr( res.pLeaf ));
+ f( *node_traits::to_value_ptr( res.pLeaf ));
break;
}
pOp = nullptr;
}
}
+ bkoff();
m_Stat.onEraseRetry();
}
}
return true;
}
- template <typename ExemptPtr, typename Q, typename Less>
- bool extract_with_( ExemptPtr& dest, Q const& val, Less pred )
+ template <typename Q, typename Less>
+ value_type * extract_with_( Q const& val, Less /*pred*/ )
{
+ CDS_UNUSED( pred );
typedef ellen_bintree::details::compare<
key_type,
value_type,
node_traits
> compare_functor;
- return extract_( dest, val, compare_functor() );
+ return extract_( val, compare_functor() );
}
- template <typename ExemptPtr, typename Q, typename Compare>
- bool extract_( ExemptPtr& ptr, Q const& val, Compare cmp )
+ template <typename Q, typename Compare>
+ value_type * extract_( Q const& val, Compare cmp )
{
check_deadlock_policy::check();
retired_list updRetire;
update_desc * pOp = nullptr;
search_result res;
+ back_off bkoff;
+ value_type * pResult;
{
rcu_lock l;
if ( pOp )
retire_update_desc( pOp, updRetire, false );
m_Stat.onEraseFailed();
- return false;
+ return nullptr;
}
if ( res.updGrandParent.bits() != update_desc::Clean )
update_ptr updGP( res.updGrandParent.ptr() );
if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
- memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
+ memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
{
if ( help_delete( pOp, updRetire )) {
- ptr = node_traits::to_value_ptr( res.pLeaf );
+ pResult = node_traits::to_value_ptr( res.pLeaf );
break;
}
pOp = nullptr;
}
}
+ bkoff();
m_Stat.onEraseRetry();
}
}
--m_ItemCounter;
m_Stat.onEraseSuccess();
- return true;
+ return pResult;
}
- template <typename ExemptPtr>
- bool extract_max_( ExemptPtr& result )
+ value_type * extract_max_()
{
check_deadlock_policy::check();
retired_list updRetire;
update_desc * pOp = nullptr;
search_result res;
+ back_off bkoff;
+ value_type * pResult;
{
rcu_lock l;
if ( pOp )
retire_update_desc( pOp, updRetire, false );
m_Stat.onExtractMaxFailed();
- return false;
+ return nullptr;
}
if ( res.updGrandParent.bits() != update_desc::Clean )
update_ptr updGP( res.updGrandParent.ptr() );
if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
- memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
+ memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
{
if ( help_delete( pOp, updRetire )) {
- result = node_traits::to_value_ptr( res.pLeaf );
+ pResult = node_traits::to_value_ptr( res.pLeaf );
break;
}
pOp = nullptr;
}
}
}
+
+ bkoff();
m_Stat.onExtractMaxRetry();
}
}
--m_ItemCounter;
m_Stat.onExtractMaxSuccess();
- return true;
+ return pResult;
}
- template <typename ExemptPtr>
- bool extract_min_(ExemptPtr& result)
+ value_type * extract_min_()
{
check_deadlock_policy::check();
retired_list updRetire;
update_desc * pOp = nullptr;
search_result res;
+ back_off bkoff;
+ value_type * pResult;
{
rcu_lock l;
if ( pOp )
retire_update_desc( pOp, updRetire, false );
m_Stat.onExtractMinFailed();
- return false;
+ return nullptr;
}
if ( res.updGrandParent.bits() != update_desc::Clean )
update_ptr updGP( res.updGrandParent.ptr() );
if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
- memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
+ memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
{
if ( help_delete( pOp, updRetire )) {
- result = node_traits::to_value_ptr( res.pLeaf );
+ pResult = node_traits::to_value_ptr( res.pLeaf );
break;
}
pOp = nullptr;
}
}
+ bkoff();
m_Stat.onExtractMinRetry();
}
}
--m_ItemCounter;
m_Stat.onExtractMinSuccess();
- return true;
+ return pResult;
}
template <typename Q, typename Less, typename Func>
- bool find_with_( Q& val, Less pred, Func f ) const
+ bool find_with_( Q& val, Less /*pred*/, Func f ) const
{
+ CDS_UNUSED( pred );
typedef ellen_bintree::details::compare<
key_type,
value_type,
search_result res;
if ( search( res, val, compare_functor() )) {
assert( res.pLeaf );
- cds::unref(f)( *node_traits::to_value_ptr( res.pLeaf ), val );
+ f( *node_traits::to_value_ptr( res.pLeaf ), val );
m_Stat.onFindSuccess();
return true;
search_result res;
if ( search( res, key, node_compare() )) {
assert( res.pLeaf );
- cds::unref(f)( *node_traits::to_value_ptr( res.pLeaf ), key );
+ f( *node_traits::to_value_ptr( res.pLeaf ), key );
m_Stat.onFindSuccess();
return true;
update_ptr updCur( res.updParent.ptr() );
if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
- memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
+ memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
{
// do insert
help_insert( pOp );
projects / libcds.git / blobdiff