@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"
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();
}
}
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 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
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,
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,
*/
void clear()
{
- exempt_ptr ep;
- while ( extract_min(ep) )
+ for ( exempt_ptr ep = extract_min(); !ep.empty(); ep = extract_min() )
ep.release();
}
return false;
}
- void help( update_ptr pUpdate, retired_list& rl )
+ void help( update_ptr /*pUpdate*/, retired_list& /*rl*/ )
{
/*
switch ( pUpdate.bits() ) {
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*/ )
{
+ 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 )
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>
- 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,
projects / libcds.git / blobdiff