#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,
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 );
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,
\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
/// 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