@note Do not include <tt><cds/intrusive/impl/ellen_bintree.h></tt> header file explicitly.
There are header file for each GC type:
- <tt><cds/intrusive/ellen_bintree_hp.h></tt> - for Hazard Pointer GC \p cds::gc::HP
- - <tt><cds/intrusive/ellen_bintree_dhp.h></tt> - for Pass-the-Buck GC \p cds::gc::DHP
+ - <tt><cds/intrusive/ellen_bintree_dhp.h></tt> - for Dynamic Hazard Pointer GC \p cds::gc::DHP
- <tt><cds/intrusive/ellen_bintree_rcu.h></tt> - for RCU (see \ref cds_intrusive_EllenBinTree_rcu "RCU-based EllenBinTree")
<b>Template arguments</b> :
typedef typename traits::hook hook; ///< hook type
typedef typename hook::node_type node_type; ///< node type
typedef typename traits::disposer disposer; ///< leaf node disposer
+ typedef typename traits::back_off back_off; ///< back-off strategy
typedef cds::gc::guarded_ptr< gc, value_type > guarded_ptr; ///< Guarded pointer
guardInsert.assign( &val );
unique_internal_node_ptr pNewInternal;
-
search_result res;
+ back_off bkoff;
+
for ( ;; ) {
if ( search( res, val, node_compare() )) {
if ( pNewInternal.get() )
}
}
+ bkoff();
m_Stat.onInsertRetry();
}
guardInsert.assign( &val );
unique_internal_node_ptr pNewInternal;
-
search_result res;
+ back_off bkoff;
+
for ( ;; ) {
if ( search( res, val, node_compare() )) {
func( false, *node_traits::to_value_ptr( res.pLeaf ), val );
break;
}
}
+
+ bkoff();
m_Stat.onEnsureRetry();
}
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.
\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 tree \p item. If such access is
{
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 key with comparing functor \p pred
/**
{
return find_with_( key, pred, f );
}
+ //@cond
+ template <typename Q, typename Less, typename Func>
+ bool find_with( Q const& key, Less pred, Func f ) const
+ {
+ return find_with_( key, pred, f );
+ }
+ //@endcond
/// Finds \p key and returns the item found
/** @anchor cds_intrusive_EllenBinTree_get
return true;
}
+ /*
void help( update_ptr pUpdate )
{
// pUpdate must be guarded!
break;
}
}
+ */
void help_insert( update_desc * pOp )
{
assert( res.pLeaf->is_leaf() );
// check search result
- if ( ( res.bRightLeaf
+ if ( (res.bRightLeaf
? res.pParent->m_pRight.load( memory_model::memory_order_acquire )
- : res.pParent->m_pLeft.load( memory_model::memory_order_acquire ) ) == res.pLeaf )
- {
+ : res.pParent->m_pLeft.load( memory_model::memory_order_acquire )) == res.pLeaf ) {
leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
- int nCmp = node_compare()( val, *res.pLeaf );
+ int nCmp = node_compare()(val, *res.pLeaf);
if ( nCmp < 0 ) {
if ( res.pGrandParent ) {
assert( !res.pLeaf->infinite_key() );
pNewInternal->infinite_key( 0 );
- key_extractor()( pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ) );
+ key_extractor()(pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ));
}
else {
assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
assert( !res.pLeaf->is_internal() );
pNewInternal->infinite_key( 0 );
- key_extractor()( pNewInternal->m_Key, val );
+ key_extractor()(pNewInternal->m_Key, val);
pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
- assert( !res.pLeaf->infinite_key());
+ assert( !res.pLeaf->infinite_key() );
}
typename gc::Guard guard;
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, atomics::memory_order_relaxed ))
- {
+ memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
// do insert
help_insert( pOp );
retire_update_desc( pOp );
free_update_desc( pOp );
}
}
+
return false;
}
{
update_desc * pOp = nullptr;
search_result res;
+ back_off bkoff;
for ( ;; ) {
if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf ) ) {
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, atomics::memory_order_relaxed ))
- {
- if ( help_delete( pOp )) {
+ memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
+ if ( help_delete( pOp ) ) {
// res.pLeaf is not deleted yet since it is guarded
- f( *node_traits::to_value_ptr( res.pLeaf ));
+ f( *node_traits::to_value_ptr( res.pLeaf ) );
break;
}
pOp = nullptr;
}
}
+ bkoff();
m_Stat.onEraseRetry();
}
{
update_desc * pOp = nullptr;
search_result res;
+ back_off bkoff;
for ( ;; ) {
if ( !search_max( res )) {
return false;
}
- if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
+ if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
if ( !pOp )
pOp = alloc_update_desc();
if ( check_delete_precondition( res ) ) {
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, atomics::memory_order_relaxed ))
+ memory_model::memory_order_acquire, atomics::memory_order_relaxed ) )
{
- if ( help_delete( pOp ))
+ if ( help_delete( pOp ) )
break;
pOp = nullptr;
}
}
}
+ bkoff();
m_Stat.onExtractMaxRetry();
}
{
update_desc * pOp = nullptr;
search_result res;
+ back_off bkoff;
for ( ;; ) {
if ( !search_min( res )) {
}
}
+ bkoff();
m_Stat.onExtractMinRetry();
}
projects / libcds.git / blobdiff