#include <cds/opt/compare.h>
#include <cds/details/binary_functor_wrapper.h>
#include <cds/urcu/details/check_deadlock.h>
-#include <cds/gc/guarded_ptr.h>
namespace cds { namespace intrusive {
@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
+ typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
protected:
//@cond
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();
}
template <typename Q, typename Less>
bool erase_with( const Q& key, Less pred )
{
+ CDS_UNUSED( pred );
typedef ellen_bintree::details::compare<
key_type,
value_type,
template <typename Q, typename Less, typename Func>
bool erase_with( Q const& key, Less pred, Func f )
{
+ CDS_UNUSED( pred );
typedef ellen_bintree::details::compare<
key_type,
value_type,
/// 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 dest parameter.
- If the tree is empty the function returns \p false.
+ The function searches an item with minimal key, unlinks it, and returns a guarded pointer to an item found.
+ If the tree is empty the function returns an empty guarded pointer.
@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.
During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
So, the function returns the item with minimum key at the moment of tree traversing.
- The guarded pointer \p dest prevents disposer invocation for returned item,
- see cds::gc::guarded_ptr for explanation.
+ The returned \p guarded_ptr prevents disposer invocation for returned item,
+ see \p cds::gc::guarded_ptr for explanation.
@note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
*/
- bool extract_min( guarded_ptr& dest )
+ guarded_ptr extract_min()
{
- return extract_min_( dest.guard());
+ guarded_ptr gp;
+ extract_min_( gp.guard() );
+ return gp;
}
/// 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 dest parameter.
- If the tree is empty the function returns \p false.
+ The function searches an item with maximal key, unlinks it, and returns a guarded pointer to an item found.
+ If the tree is empty the function returns an empty \p guarded_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.
During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
So, the function returns the item with maximal key at the moment of tree traversing.
- The guarded pointer \p dest prevents disposer invocation for returned item,
+ The returned \p guarded_ptr prevents disposer invocation for returned item,
see cds::gc::guarded_ptr for explanation.
@note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
*/
- bool extract_max( guarded_ptr& dest )
+ guarded_ptr extract_max()
{
- return extract_max_( dest.guard() );
+ guarded_ptr gp;
+ extract_max_( gp.guard());
+ return gp;
}
/// Extracts an item from the tree
/** \anchor cds_intrusive_EllenBinTree_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 dest parameter.
- If the item is not found the function returns \p false.
+ unlinks it, and returns a guarded pointer to an item found.
+ If the item is not found the function returns an empty \p guarded_ptr.
- The guarded pointer \p dest prevents disposer invocation for returned item,
+ \p guarded_ptr prevents disposer invocation for returned item,
see cds::gc::guarded_ptr for explanation.
@note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
*/
template <typename Q>
- bool extract( guarded_ptr& dest, Q const& key )
+ guarded_ptr extract( Q const& key )
{
- return extract_( dest.guard(), key );
+ guarded_ptr gp;
+ extract_( gp.guard(), key );
+ return gp;
}
/// Extracts an item from the tree using \p pred for searching
/**
- The function is an analog of \ref cds_intrusive_EllenBinTree_extract "extract(guarded_ptr& dest, Q const&)"
+ The function is an analog of \ref cds_intrusive_EllenBinTree_extract "extract(Q const&)"
but \p pred is used for key compare.
\p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
"Predicate requirements".
\p pred must imply the same element order as the comparator used for building the tree.
*/
template <typename Q, typename Less>
- bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
+ guarded_ptr extract_with( Q const& key, Less pred )
{
- return extract_with_( dest.guard(), key, pred );
+ guarded_ptr gp;
+ extract_with_( gp.guard(), key, pred );
+ return gp;
}
/// Finds the key \p key
template <typename Q, typename Less>
bool find_with( Q const& key, Less pred ) const
{
+ CDS_UNUSED( pred );
typedef ellen_bintree::details::compare<
key_type,
value_type,
/// Finds \p key and returns the item found
/** @anchor cds_intrusive_EllenBinTree_get
- The function searches the item with key equal to \p key and returns the item found in \p dest parameter.
- The function returns \p true if \p key is found, \p false otherwise.
+ The function searches the item with key equal to \p key and returns the item found as \p guarded_ptr object.
+ The function returns an empty guarded pointer is \p key is not found.
- The guarded pointer \p dest prevents disposer invocation for returned item,
- see cds::gc::guarded_ptr for explanation.
+ \p guarded_ptr prevents disposer invocation for returned item,
+ see \p cds::gc::guarded_ptr for explanation.
@note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
*/
template <typename Q>
- bool get( guarded_ptr& dest, Q const& key ) const
+ guarded_ptr get( Q const& key ) const
{
- return get_( dest.guard(), key );
+ guarded_ptr gp;
+ get_( gp.guard(), key );
+ return gp;
}
/// Finds \p key with predicate \p pred and returns the item found
/**
- The function is an analog of \ref cds_intrusive_EllenBinTree_get "get(guarded_ptr&, Q const&)"
+ The function is an analog of \ref cds_intrusive_EllenBinTree_get "get(Q const&)"
but \p pred is used for key comparing.
\p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
"Predicate requirements".
\p pred must imply the same element order as the comparator used for building the tree.
*/
template <typename Q, typename Less>
- bool get_with( guarded_ptr& dest, Q const& key, Less pred ) const
+ guarded_ptr get_with( Q const& key, Less pred ) const
{
- return get_with_( dest.guard(), key, pred );
+ guarded_ptr gp;
+ get_with_( gp.guard(), key, pred );
+ return gp;
}
/// Checks if the tree is empty
void clear()
{
guarded_ptr gp;
- while ( extract_min(gp));
+ do {
+ gp = extract_min();
+ } while ( gp );
}
/// Clears the tree (not thread safe)
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();
}
}
template <typename Q>
- bool extract_( typename gc::Guard& guard, Q const& key )
+ bool extract_( typename guarded_ptr::native_guard& guard, Q const& key )
{
return erase_( key, node_compare(),
[]( Q const&, leaf_node const& ) -> bool { return true; },
- [&guard]( value_type& found ) { guard.assign( &found ); } );
+ [&guard]( value_type& found ) { guard.set( &found ); } );
}
template <typename Q, typename Less>
- bool extract_with_( typename gc::Guard& guard, Q const& key, Less pred )
+ bool extract_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less /*pred*/ )
{
typedef ellen_bintree::details::compare<
key_type,
return erase_( key, compare_functor(),
[]( Q const&, leaf_node const& ) -> bool { return true; },
- [&guard]( value_type& found ) { guard.assign( &found ); } );
+ [&guard]( value_type& found ) { guard.set( &found ); } );
}
- bool extract_max_( typename gc::Guard& guard )
+ bool extract_max_( typename guarded_ptr::native_guard& gp )
{
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();
}
--m_ItemCounter;
m_Stat.onExtractMaxSuccess();
- guard.assign( node_traits::to_value_ptr( res.pLeaf ) );
+ gp.set( node_traits::to_value_ptr( res.pLeaf ));
return true;
}
- bool extract_min_( typename gc::Guard& guard )
+ bool extract_min_( typename guarded_ptr::native_guard& gp )
{
update_desc * pOp = nullptr;
search_result res;
+ back_off bkoff;
for ( ;; ) {
if ( !search_min( res )) {
}
}
+ bkoff();
m_Stat.onExtractMinRetry();
}
--m_ItemCounter;
m_Stat.onExtractMinSuccess();
- guard.assign( node_traits::to_value_ptr( res.pLeaf ));
+ gp.set( node_traits::to_value_ptr( res.pLeaf ));
return true;
}
}
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
{
typedef ellen_bintree::details::compare<
key_type,
}
template <typename Q>
- bool get_( typename gc::Guard& guard, Q const& val ) const
+ bool get_( typename guarded_ptr::native_guard& guard, Q const& val ) const
{
- return find_( val, [&guard]( value_type& found, Q const& ) { guard.assign( &found ); } );
+ return find_( val, [&guard]( value_type& found, Q const& ) { guard.set( &found ); } );
}
template <typename Q, typename Less>
- bool get_with_( typename gc::Guard& guard, Q const& val, Less pred ) const
+ bool get_with_( typename guarded_ptr::native_guard& guard, Q const& val, Less pred ) const
{
- return find_with_( val, pred, [&guard]( value_type& found, Q const& ) { guard.assign( &found ); } );
+ return find_with_( val, pred, [&guard]( value_type& found, Q const& ) { guard.set( &found ); } );
}
//@endcond
projects / libcds.git / blobdiff