the priority value plus some uniformly distributed random value.
@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.
+ In Hazard Pointer schema the 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.
+ the operation done. Such solution allows greatly simplify implementation of the tree.
- @warning Recall the tree is <b>unbalanced</b>. The complexity of operations is <tt>O(log N)</tt>
+ @attention 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 Do not include <tt><cds/intrusive/impl/ellen_bintree.h></tt> header file explicitly.
typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
- //@cond
- typedef cds::intrusive::ellen_bintree::implementation_tag implementation_tag;
- //@endcond
-
protected:
//@cond
typedef ellen_bintree::base_node< gc > tree_node; ///< Base type of tree node
typedef typename traits::node_allocator node_allocator; ///< Allocator for internal node
typedef typename traits::update_desc_allocator update_desc_allocator; ///< Update descriptor allocator
- static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 8; ///< Count of hazard pointer required for the algorithm
+ static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 9; ///< Count of hazard pointer required for the algorithm
protected:
//@cond
Guard_Leaf,
Guard_updGrandParent,
Guard_updParent,
+ Guard_temporary,
// end of guard indices
guard_count
return std::make_pair( true, true );
}
//@cond
- // Deprecated, us update()
template <typename Func>
+ CDS_DEPRECATED("ensure() is deprecated, use update()")
std::pair<bool, bool> ensure( value_type& val, Func func )
{
return update( val, func, true );
return false;
}
//@cond
- // Deprecated, use contains()
template <typename Q>
+ CDS_DEPRECATED("deprecated, use contains()")
bool find( Q const& key ) const
{
return contains( key );
return false;
}
//@cond
- // Deprecated, use contains()
template <typename Q, typename Less>
+ CDS_DEPRECATED("deprecated, use contains()")
bool find_with( Q const& key, Less pred ) const
{
return contains( key, pred );
return false;
}
- static tree_node * protect_child_node( search_result& res, internal_node * pParent, bool bRight, update_ptr updParent )
+ tree_node * protect_child_node( search_result& res, internal_node * pParent, bool bRight, update_ptr updParent ) const
{
+ retry:
tree_node * p = bRight
? res.guards.protect( search_result::Guard_Leaf, pParent->m_pRight,
- []( tree_node * p ) -> internal_node* { return static_cast<internal_node *>(p);})
+ []( tree_node * p ) -> internal_node* { return static_cast<internal_node *>(p);})
: res.guards.protect( search_result::Guard_Leaf, pParent->m_pLeft,
- []( tree_node * p ) -> internal_node* { return static_cast<internal_node *>(p);});
- if ( p && p->is_leaf() )
- res.guards.assign( search_result::Guard_Leaf, node_traits::to_value_ptr( static_cast<leaf_node *>( p )));
+ []( tree_node * p ) -> internal_node* { return static_cast<internal_node *>(p);});
+
+ // If we use member hook, data node pointer != internal node pointer
+ // So, we need protect the child twice: as internal node and as data node
+ // and then analyze what kind of node we have
+ tree_node * pVal = bRight
+ ? res.guards.protect( search_result::Guard_temporary, pParent->m_pRight,
+ []( tree_node * p ) -> value_type* { return node_traits::to_value_ptr( static_cast<leaf_node *>(p));} )
+ : res.guards.protect( search_result::Guard_temporary, pParent->m_pLeft,
+ []( tree_node * p ) -> value_type* { return node_traits::to_value_ptr( static_cast<leaf_node *>(p));} );
// child node is guarded
// See whether pParent->m_pUpdate has not been changed
// update has been changed - returns nullptr as a flag to search retry
return nullptr;
}
+
+ if ( p != pVal )
+ goto retry;
+
+ if ( p && p->is_leaf())
+ res.guards.assign( search_result::Guard_Leaf, node_traits::to_value_ptr( static_cast<leaf_node *>( p )));
+
+ res.guards.clear( search_result::Guard_temporary );
+
return p;
}
assert( res.pGrandParent != nullptr );
- return
- static_cast<internal_node *>(
- res.bRightParent
- ? res.pGrandParent->m_pRight.load(memory_model::memory_order_relaxed)
- : res.pGrandParent->m_pLeft.load(memory_model::memory_order_relaxed)
- ) == res.pParent
- &&
- static_cast<leaf_node *>(
- res.bRightLeaf
- ? res.pParent->m_pRight.load(memory_model::memory_order_relaxed)
- : res.pParent->m_pLeft.load(memory_model::memory_order_relaxed)
- ) == res.pLeaf;
+ return static_cast<internal_node *>(res.pGrandParent->get_child( res.bRightParent, memory_model::memory_order_relaxed )) == res.pParent
+ && static_cast<leaf_node *>( res.pParent->get_child( res.bRightLeaf, memory_model::memory_order_relaxed )) == res.pLeaf;
}
bool help_delete( update_desc * pOp )
assert( res.pLeaf->is_leaf() );
// check search result
- 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 ) {
+ if ( res.pParent->get_child( res.bRightLeaf, memory_model::memory_order_acquire ) == res.pLeaf ) {
leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
int nCmp = node_compare()(val, *res.pLeaf);
projects / libcds.git / blobdiff