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
protected:
//@cond
//@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
unique_internal_node_ptr pNewInternal;
retired_list updRetire;
+ back_off bkoff;
{
rcu_lock l;
}
}
+ bkoff();
m_Stat.onInsertRetry();
}
}
unique_internal_node_ptr pNewInternal;
retired_list updRetire;
+ back_off bkoff;
{
rcu_lock l;
break;
}
}
+
+ bkoff();
m_Stat.onEnsureRetry();
}
}
/// 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& key, Less pred )
+ exempt_ptr extract_with( Q const& key, Less pred )
{
- return extract_with_( dest, key, pred );
+ return exempt_ptr( extract_with_( key, pred ));
}
/// Finds the key \p key
*/
void clear()
{
- exempt_ptr ep;
- while ( extract_min(ep) )
+ for ( exempt_ptr ep = extract_min(); !ep.empty(); ep = extract_min() )
ep.release();
}
retired_list updRetire;
update_desc * pOp = nullptr;
search_result res;
+ back_off bkoff;
{
rcu_lock l;
}
}
+ 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 )
{
typedef ellen_bintree::details::compare<
key_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 )
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 )
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 )
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>
projects / libcds.git / blobdiff