-//$$CDS-header$$
+/*
+ This file is a part of libcds - Concurrent Data Structures library
-#ifndef __CDS_INTRUSIVE_IMPL_ELLEN_BINTREE_H
-#define __CDS_INTRUSIVE_IMPL_ELLEN_BINTREE_H
+ (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
+
+ Source code repo: http://github.com/khizmax/libcds/
+ Download: http://sourceforge.net/projects/libcds/files/
+
+ Redistribution and use in source and binary forms, with or without
+ modification, are permitted provided that the following conditions are met:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#ifndef CDSLIB_INTRUSIVE_IMPL_ELLEN_BINTREE_H
+#define CDSLIB_INTRUSIVE_IMPL_ELLEN_BINTREE_H
#include <memory>
#include <cds/intrusive/details/ellen_bintree_base.h>
#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 {
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>
- for uniformly distributed random keys, but in worst case the complexity is <tt>O(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 the worst case the complexity is <tt>O(N)</tt>.
@note Do not include <tt><cds/intrusive/impl/ellen_bintree.h></tt> header file explicitly.
There are header file for each GC 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
{
static internal_node const& to_internal_node( tree_node const& n )
{
- assert( n.is_internal() );
+ assert( n.is_internal());
return static_cast<internal_node const&>( n );
}
static leaf_node const& to_leaf_node( tree_node const& n )
{
- assert( n.is_leaf() );
+ assert( n.is_leaf());
return static_cast<leaf_node const&>( n );
}
};
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 = 9; ///< Count of hazard pointer required for the algorithm
+
protected:
//@cond
typedef ellen_bintree::details::compare< key_type, value_type, key_comparator, node_traits > node_compare;
Guard_Leaf,
Guard_updGrandParent,
Guard_updParent,
-
- // helping
- Guard_helpLeaf,
+ Guard_temporary,
// end of guard indices
guard_count
,bRightLeaf( false )
,bRightParent( false )
{}
-
- void clean_help_guards()
- {
- guards.clear( Guard_helpLeaf );
- }
};
//@endcond
protected:
//@cond
- static void free_leaf_node( value_type * p )
+ static void free_leaf_node( void* p )
{
- disposer()( p );
+ disposer()( reinterpret_cast<value_type*>( p ));
}
internal_node * alloc_internal_node() const
return pNode;
}
- static void free_internal_node( internal_node * pNode )
+ static void free_internal_node( void* pNode )
{
- cxx_node_allocator().Delete( pNode );
+ cxx_node_allocator().Delete( reinterpret_cast<internal_node*>( pNode ));
}
struct internal_node_deleter {
- void operator()( internal_node * p) const
+ void operator()( internal_node* p) const
{
- free_internal_node( p );
+ cxx_node_allocator().Delete( p );
}
};
return cxx_update_desc_allocator().New();
}
- static void free_update_desc( update_desc * pDesc )
+ static void free_update_desc( void* pDesc )
{
- cxx_update_desc_allocator().Delete( pDesc );
+ cxx_update_desc_allocator().Delete( reinterpret_cast<update_desc*>( pDesc ));
}
void retire_node( tree_node * pNode ) const
{
- if ( pNode->is_leaf() ) {
+ if ( pNode->is_leaf()) {
assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf1 );
assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf2 );
back_off bkoff;
for ( ;; ) {
- if ( search( res, val, node_compare() )) {
- if ( pNewInternal.get() )
+ if ( search( res, val, node_compare())) {
+ if ( pNewInternal.get())
m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
m_Stat.onInsertFailed();
return false;
if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
- if ( !pNewInternal.get() )
- pNewInternal.reset( alloc_internal_node() );
+ if ( !pNewInternal.get())
+ pNewInternal.reset( alloc_internal_node());
if ( try_insert( val, pNewInternal.get(), res )) {
f( val );
return true;
}
- /// Ensures that the \p val exists in the tree
+ /// Updates the node
/**
The operation performs inserting or changing data with lock-free manner.
- If the item \p val is not found in the tree, then \p val is inserted into the tree.
+ If the item \p val is not found in the set, then \p val is inserted into the set
+ iff \p bAllowInsert is \p true.
Otherwise, the functor \p func is called with item found.
- The functor signature is:
+ The functor \p func signature is:
\code
void func( bool bNew, value_type& item, value_type& val );
\endcode
with arguments:
- \p bNew - \p true if the item has been inserted, \p false otherwise
- - \p item - an item of the tree
- - \p val - the argument \p val passed to the \p ensure function
+ - \p item - item of the set
+ - \p val - argument \p val passed into the \p %update() function
If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
refer to the same thing.
The functor can change non-key fields of the \p item; however, \p func must guarantee
that during changing no any other modifications could be made on this item by concurrent threads.
- Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
+ Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
+ i.e. the node has been inserted or updated,
\p second is \p true if new item has been added or \p false if the item with \p key
- already is in the tree.
+ already exists.
@warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
*/
template <typename Func>
- std::pair<bool, bool> ensure( value_type& val, Func func )
+ std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
{
typename gc::Guard guardInsert;
guardInsert.assign( &val );
back_off bkoff;
for ( ;; ) {
- if ( search( res, val, node_compare() )) {
+ if ( search( res, val, node_compare())) {
func( false, *node_traits::to_value_ptr( res.pLeaf ), val );
- if ( pNewInternal.get() )
+ if ( pNewInternal.get())
m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
- m_Stat.onEnsureExist();
+ m_Stat.onUpdateExist();
return std::make_pair( true, false );
}
if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
+ if ( !bAllowInsert )
+ return std::make_pair( false, false );
- if ( !pNewInternal.get() )
- pNewInternal.reset( alloc_internal_node() );
+ if ( !pNewInternal.get())
+ pNewInternal.reset( alloc_internal_node());
if ( try_insert( val, pNewInternal.get(), res )) {
func( true, val, val );
}
bkoff();
- m_Stat.onEnsureRetry();
+ m_Stat.onUpdateRetry();
}
++m_ItemCounter;
- m_Stat.onEnsureNew();
+ m_Stat.onUpdateNew();
return std::make_pair( true, true );
}
+ //@cond
+ 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 );
+ }
+ //@endcond
/// Unlinks the item \p val from the tree
/**
unlinks it from the tree, and returns \p true.
If the item with key equal to \p key is not found the function return \p false.
- Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
+ Note the \p Traits::less and/or \p Traits::compare predicate should accept a parameter of type \p Q
+ that can be not the same as \p value_type.
*/
template <typename Q>
bool erase( const Q& key )
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,
If the item with key equal to \p key is not found the function return \p false.
- Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
+ Note the \p Traits::less and/or \p Traits::compare predicate should accept a parameter of type \p Q
+ that can be not the same as \p value_type.
*/
template <typename Q, typename Func>
bool erase( Q const& key, Func f )
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,
*/
guarded_ptr extract_min()
{
- guarded_ptr gp;
- extract_min_( gp.guard() );
- return gp;
+ return extract_min_();
}
/// Extracts an item with maximal key from the tree
*/
guarded_ptr extract_max()
{
- guarded_ptr gp;
- extract_max_( gp.guard());
- return gp;
+ return extract_max_();
}
/// Extracts an item from the tree
template <typename Q>
guarded_ptr extract( Q const& key )
{
- guarded_ptr gp;
- extract_( gp.guard(), key );
- return gp;
+ return extract_( key );
}
/// Extracts an item from the tree using \p pred for searching
template <typename Q, typename Less>
guarded_ptr extract_with( Q const& key, Less pred )
{
- guarded_ptr gp;
- extract_with_( gp.guard(), key, pred );
- return gp;
+ return extract_with_( key, pred );
}
- /// Finds the key \p key
- /** @anchor cds_intrusive_EllenBinTree_find_val
+ /// Checks whether the set contains \p key
+ /**
The function searches the item with key equal to \p key
and returns \p true if it is found, and \p false otherwise.
-
- Note the hash functor specified for class \p Traits template parameter
- should accept a parameter of type \p Q that can be not the same as \p value_type.
*/
template <typename Q>
- bool find( Q const& key ) const
+ bool contains( Q const& key ) const
{
search_result res;
- if ( search( res, key, node_compare() )) {
+ if ( search( res, key, node_compare())) {
m_Stat.onFindSuccess();
return true;
}
m_Stat.onFindFailed();
return false;
}
+ //@cond
+ template <typename Q>
+ CDS_DEPRECATED("deprecated, use contains()")
+ bool find( Q const& key ) const
+ {
+ return contains( key );
+ }
+ //@endcond
- /// Finds the key \p key with comparing functor \p pred
+ /// Checks whether the set contains \p key using \p pred predicate for searching
/**
- The function is an analog of \ref cds_intrusive_EllenBinTree_find_val "find(Q const&)"
- but \p pred is used for key compare.
- \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.
- \p pred should accept arguments of type \p Q, \p key_type, \p value_type in any combination.
+ The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
+ \p Less functor has the interface like \p std::less.
+ \p Less must imply the same element order as the comparator used for building the set.
*/
template <typename Q, typename Less>
- bool find_with( Q const& key, Less pred ) const
+ bool contains( Q const& key, Less pred ) const
{
+ CDS_UNUSED( pred );
typedef ellen_bintree::details::compare<
key_type,
value_type,
> compare_functor;
search_result res;
- if ( search( res, key, compare_functor() )) {
+ if ( search( res, key, compare_functor())) {
m_Stat.onFindSuccess();
return true;
}
m_Stat.onFindFailed();
return false;
}
+ //@cond
+ template <typename Q, typename Less>
+ CDS_DEPRECATED("deprecated, use contains()")
+ bool find_with( Q const& key, Less pred ) const
+ {
+ return contains( key, pred );
+ }
+ //@endcond
/// Finds the key \p key
/** @anchor cds_intrusive_EllenBinTree_find_func
template <typename Q>
guarded_ptr get( Q const& key ) const
{
- guarded_ptr gp;
- get_( gp.guard(), key );
- return gp;
+ return get_( key );
}
/// Finds \p key with predicate \p pred and returns the item found
template <typename Q, typename Less>
guarded_ptr get_with( Q const& key, Less pred ) const
{
- guarded_ptr gp;
- get_with_( gp.guard(), key, pred );
- return gp;
+ return get_with_( key, pred );
}
/// Checks if the tree is empty
this sequence
\code
tree.clear();
- assert( tree.empty() );
+ assert( tree.empty());
\endcode
the assertion could be raised.
tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
// Get leftmost leaf
- while ( pLeaf->is_internal() ) {
+ while ( pLeaf->is_internal()) {
pGrandParent = pParent;
pParent = static_cast<internal_node *>( pLeaf );
pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
// Remove leftmost leaf and its parent node
assert( pGrandParent );
assert( pParent );
- assert( pLeaf->is_leaf() );
+ assert( pLeaf->is_leaf());
pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
- free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf ) ) );
+ free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf )));
free_internal_node( pParent );
}
}
&& node_compare()( *pLeft, *pRight ) < 0 )
{
bool bRet = true;
- if ( pLeft->is_internal() )
- bRet = check_consistency( static_cast<internal_node *>( pLeft ) );
+ if ( pLeft->is_internal())
+ bRet = check_consistency( static_cast<internal_node *>( pLeft ));
assert( bRet );
- if ( bRet && pRight->is_internal() )
+ if ( bRet && pRight->is_internal())
bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
assert( bRet );
tree_node * protect_child_node( search_result& res, internal_node * pParent, bool bRight, update_ptr updParent ) const
{
- tree_node * p;
- tree_node * pn = bRight ? pParent->m_pRight.load( memory_model::memory_order_relaxed ) : pParent->m_pLeft.load( memory_model::memory_order_relaxed );
- do {
- p = pn;
- res.guards.assign( search_result::Guard_Leaf, static_cast<internal_node *>( p ));
- res.guards.assign( search_result::Guard_helpLeaf, node_traits::to_value_ptr( static_cast<leaf_node *>( p ) ));
- pn = bRight ? pParent->m_pRight.load( memory_model::memory_order_acquire ) : pParent->m_pLeft.load( memory_model::memory_order_acquire );
- } while ( p != pn );
+ 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);})
+ : res.guards.protect( search_result::Guard_Leaf, pParent->m_pLeft,
+ []( 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
return nullptr;
}
- if ( p && p->is_leaf() )
- res.guards.copy( search_result::Guard_Leaf, search_result::Guard_helpLeaf );
- res.guards.clear( search_result::Guard_helpLeaf );
+ 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;
}
- update_ptr search_protect_update( search_result& res, atomics::atomic<update_ptr> const& src ) const
+ static update_ptr search_protect_update( search_result& res, atomics::atomic<update_ptr> const& src )
{
- update_ptr ret;
- update_ptr upd( src.load( memory_model::memory_order_relaxed ) );
- do {
- ret = upd;
- res.guards.assign( search_result::Guard_updParent, upd );
- } while ( ret != (upd = src.load( memory_model::memory_order_acquire )) );
- return ret;
+ return res.guards.protect( search_result::Guard_updParent, src, [](update_ptr p) -> update_desc* { return p.ptr(); });
}
template <typename KeyValue, typename Compare>
updParent = nullptr;
bRightLeaf = false;
tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
- while ( pLeaf->is_internal() ) {
+ while ( pLeaf->is_internal()) {
res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
pGrandParent = pParent;
res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
updParent = search_protect_update( res, pParent->m_pUpdate );
- switch ( updParent.bits() ) {
+ switch ( updParent.bits()) {
case update_desc::DFlag:
case update_desc::Mark:
m_Stat.onSearchRetry();
}
}
- assert( pLeaf->is_leaf() );
- nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf) );
+ assert( pLeaf->is_leaf());
+ nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf));
res.pGrandParent = pGrandParent;
res.pParent = pParent;
pGrandParent = nullptr;
updParent = nullptr;
tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
- while ( pLeaf->is_internal() ) {
+ while ( pLeaf->is_internal()) {
res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
pGrandParent = pParent;
res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
updParent = search_protect_update( res, pParent->m_pUpdate );
- switch ( updParent.bits() ) {
+ switch ( updParent.bits()) {
case update_desc::DFlag:
case update_desc::Mark:
m_Stat.onSearchRetry();
res.pGrandParent = pGrandParent;
res.pParent = pParent;
- assert( pLeaf->is_leaf() );
+ assert( pLeaf->is_leaf());
res.pLeaf = static_cast<leaf_node *>( pLeaf );
res.updParent = updParent;
res.updGrandParent = updGrandParent;
updParent = nullptr;
bRightLeaf = false;
tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
- while ( pLeaf->is_internal() ) {
+ while ( pLeaf->is_internal()) {
res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
pGrandParent = pParent;
res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
updParent = search_protect_update( res, pParent->m_pUpdate );
- switch ( updParent.bits() ) {
+ switch ( updParent.bits()) {
case update_desc::DFlag:
case update_desc::Mark:
m_Stat.onSearchRetry();
res.pGrandParent = pGrandParent;
res.pParent = pParent;
- assert( pLeaf->is_leaf() );
+ assert( pLeaf->is_leaf());
res.pLeaf = static_cast<leaf_node *>( pLeaf );
res.updParent = updParent;
res.updGrandParent = updGrandParent;
void help( update_ptr pUpdate )
{
// pUpdate must be guarded!
- switch ( pUpdate.bits() ) {
+ switch ( pUpdate.bits()) {
case update_desc::IFlag:
- help_insert( pUpdate.ptr() );
+ help_insert( pUpdate.ptr());
m_Stat.onHelpInsert();
break;
case update_desc::DFlag:
- help_delete( pUpdate.ptr() );
+ help_delete( pUpdate.ptr());
m_Stat.onHelpDelete();
break;
case update_desc::Mark:
//m_Stat.onHelpMark();
- //help_marked( pUpdate.ptr() );
+ //help_marked( pUpdate.ptr());
break;
}
}
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 )
}
}
- tree_node * protect_sibling( typename gc::Guard& guard, atomics::atomic<tree_node *>& sibling )
+ static tree_node * protect_sibling( typename gc::Guard& guard, atomics::atomic<tree_node *>& sibling )
{
- typename gc::Guard guardLeaf;
-
- tree_node * pSibling;
- tree_node * p = sibling.load( memory_model::memory_order_relaxed );
- do {
- pSibling = p;
- guard.assign( static_cast<internal_node *>(p) );
- guardLeaf.assign( node_traits::to_value_ptr( static_cast<leaf_node *>(p)));
- } while ( pSibling != ( p = sibling.load( memory_model::memory_order_acquire )) );
-
- if ( pSibling->is_leaf() )
- guard.copy( guardLeaf );
-
+ tree_node * pSibling = guard.protect( sibling, [](tree_node * p) -> internal_node* { return static_cast<internal_node *>(p); } );
+ if ( pSibling->is_leaf())
+ guard.assign( node_traits::to_value_ptr( static_cast<leaf_node *>( pSibling )));
return pSibling;
}
bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res )
{
assert( res.updParent.bits() == update_desc::Clean );
- assert( res.pLeaf->is_leaf() );
+ 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);
if ( nCmp < 0 ) {
if ( res.pGrandParent ) {
- assert( !res.pLeaf->infinite_key() );
+ assert( !res.pLeaf->infinite_key());
pNewInternal->infinite_key( 0 );
key_extractor()(pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ));
}
pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
}
else {
- assert( !res.pLeaf->is_internal() );
- pNewInternal->infinite_key( 0 );
+ assert( !res.pLeaf->is_internal());
+ pNewInternal->infinite_key( 0 );
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;
pOp->iInfo.pLeaf = res.pLeaf;
pOp->iInfo.bRightLeaf = res.bRightLeaf;
- update_ptr updCur( res.updParent.ptr() );
+ 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 );
back_off bkoff;
for ( ;; ) {
- if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf ) ) {
+ if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf )) {
if ( pOp )
retire_update_desc( pOp );
m_Stat.onEraseFailed();
if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
if ( !pOp )
pOp = alloc_update_desc();
- if ( check_delete_precondition( res ) ) {
+ if ( check_delete_precondition( res )) {
typename gc::Guard guard;
guard.assign( pOp );
pOp->dInfo.bRightParent = res.bRightParent;
pOp->dInfo.bRightLeaf = res.bRightLeaf;
- update_ptr updGP( res.updGrandParent.ptr() );
+ 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;
return true;
}
+ template <typename Q, typename Compare>
+ guarded_ptr extract_item( Q const& key, Compare cmp )
+ {
+ update_desc * pOp = nullptr;
+ search_result res;
+ back_off bkoff;
+
+ for ( ;; ) {
+ if ( !search( res, key, cmp )) {
+ if ( pOp )
+ retire_update_desc( pOp );
+ m_Stat.onEraseFailed();
+ return guarded_ptr();
+ }
+
+ if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
+ if ( !pOp )
+ pOp = alloc_update_desc();
+ if ( check_delete_precondition( res )) {
+ typename gc::Guard guard;
+ guard.assign( pOp );
+
+ pOp->dInfo.pGrandParent = res.pGrandParent;
+ pOp->dInfo.pParent = res.pParent;
+ pOp->dInfo.pLeaf = res.pLeaf;
+ pOp->dInfo.pUpdateParent = res.updParent.ptr();
+ pOp->dInfo.bRightParent = res.bRightParent;
+ pOp->dInfo.bRightLeaf = res.bRightLeaf;
+
+ 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 ))
+ break;
+ pOp = nullptr;
+ }
+ }
+ }
+
+ bkoff();
+ m_Stat.onEraseRetry();
+ }
+
+ --m_ItemCounter;
+ m_Stat.onEraseSuccess();
+ return guarded_ptr( res.guards.release( search_result::Guard_Leaf ));
+ }
+
template <typename Q>
- bool extract_( typename gc::Guard& guard, Q const& key )
+ guarded_ptr extract_( Q const& key )
{
- guarded_ptr gp;
- return erase_( key, node_compare(),
- []( Q const&, leaf_node const& ) -> bool { return true; },
- [&guard]( value_type& found ) { guard.assign( &found ); } );
+ return extract_item( key, node_compare());
}
template <typename Q, typename Less>
- bool extract_with_( typename gc::Guard& guard, Q const& key, Less pred )
+ guarded_ptr extract_with_( Q const& key, Less /*pred*/ )
{
typedef ellen_bintree::details::compare<
key_type,
node_traits
> compare_functor;
- return erase_( key, compare_functor(),
- []( Q const&, leaf_node const& ) -> bool { return true; },
- [&guard]( value_type& found ) { guard.assign( &found ); } );
+ return extract_item( key, compare_functor());
}
- bool extract_max_( typename gc::Guard& gp )
+ guarded_ptr extract_max_()
{
update_desc * pOp = nullptr;
search_result res;
if ( pOp )
retire_update_desc( pOp );
m_Stat.onExtractMaxFailed();
- return false;
+ return guarded_ptr();
}
if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
if ( !pOp )
pOp = alloc_update_desc();
- if ( check_delete_precondition( res ) ) {
+ if ( check_delete_precondition( res )) {
typename gc::Guard guard;
guard.assign( pOp );
pOp->dInfo.bRightParent = res.bRightParent;
pOp->dInfo.bRightLeaf = res.bRightLeaf;
- update_ptr updGP( res.updGrandParent.ptr() );
+ 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;
}
--m_ItemCounter;
m_Stat.onExtractMaxSuccess();
- gp.assign( node_traits::to_value_ptr( res.pLeaf ));
- return true;
+ return guarded_ptr( res.guards.release( search_result::Guard_Leaf ));
}
- bool extract_min_( typename gc::Guard& gp )
+ guarded_ptr extract_min_()
{
update_desc * pOp = nullptr;
search_result res;
if ( pOp )
retire_update_desc( pOp );
m_Stat.onExtractMinFailed();
- return false;
+ return guarded_ptr();
}
if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
if ( !pOp )
pOp = alloc_update_desc();
- if ( check_delete_precondition( res ) ) {
+ if ( check_delete_precondition( res )) {
typename gc::Guard guard;
guard.assign( pOp );
pOp->dInfo.bRightParent = res.bRightParent;
pOp->dInfo.bRightLeaf = res.bRightLeaf;
- update_ptr updGP( res.updGrandParent.ptr() );
+ 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 ))
{
--m_ItemCounter;
m_Stat.onExtractMinSuccess();
- gp.assign( node_traits::to_value_ptr( res.pLeaf ));
- return true;
+ return guarded_ptr( res.guards.release( search_result::Guard_Leaf ));
}
template <typename Q, typename Func>
bool find_( Q& val, Func f ) const
{
search_result res;
- if ( search( res, val, node_compare() )) {
+ if ( search( res, val, node_compare())) {
assert( res.pLeaf );
f( *node_traits::to_value_ptr( res.pLeaf ), val );
}
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,
> compare_functor;
search_result res;
- if ( search( res, val, compare_functor() )) {
+ if ( search( res, val, compare_functor())) {
assert( res.pLeaf );
f( *node_traits::to_value_ptr( res.pLeaf ), val );
}
template <typename Q>
- bool get_( typename gc::Guard& guard, Q const& val ) const
+ guarded_ptr get_( Q const& val ) const
{
- return find_( val, [&guard]( value_type& found, Q const& ) { guard.assign( &found ); } );
+ search_result res;
+ if ( search( res, val, node_compare())) {
+ assert( res.pLeaf );
+ m_Stat.onFindSuccess();
+ return guarded_ptr( res.guards.release( search_result::Guard_Leaf ));
+ }
+
+ m_Stat.onFindFailed();
+ return guarded_ptr();
}
template <typename Q, typename Less>
- bool get_with_( typename gc::Guard& guard, Q const& val, Less pred ) const
+ guarded_ptr get_with_( Q const& val, Less pred ) const
{
- return find_with_( val, pred, [&guard]( value_type& found, Q const& ) { guard.assign( &found ); } );
+ CDS_UNUSED( pred );
+
+ typedef ellen_bintree::details::compare<
+ key_type,
+ value_type,
+ opt::details::make_comparator_from_less<Less>,
+ node_traits
+ > compare_functor;
+
+ search_result res;
+ if ( search( res, val, compare_functor())) {
+ assert( res.pLeaf );
+ m_Stat.onFindSuccess();
+ return guarded_ptr( res.guards.release( search_result::Guard_Leaf ));
+ }
+
+ m_Stat.onFindFailed();
+ return guarded_ptr();
+
}
//@endcond
}} // namespace cds::intrusive
-#endif // #ifndef __CDS_INTRUSIVE_IMPL_ELLEN_BINTREE_H
+#endif // #ifndef CDSLIB_INTRUSIVE_IMPL_ELLEN_BINTREE_H
projects / libcds.git / blobdiff