X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=blobdiff_plain;f=cds%2Fintrusive%2Fimpl%2Fellen_bintree.h;h=f935c13f5d9ce65dd122be34494bf050e59e4482;hp=38df2b5bda6e3c848960a6a8fa39b80ef06be740;hb=605038eef526b82e4261033a122d5951167eb6f9;hpb=61457ecabe339ff0f05bcb09b91ae3a2b0691f31 diff --git a/cds/intrusive/impl/ellen_bintree.h b/cds/intrusive/impl/ellen_bintree.h index 38df2b5b..f935c13f 100644 --- a/cds/intrusive/impl/ellen_bintree.h +++ b/cds/intrusive/impl/ellen_bintree.h @@ -1,14 +1,41 @@ -//$$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 #include #include #include #include -#include namespace cds { namespace intrusive { @@ -34,12 +61,12 @@ 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 unbalanced. The complexity of operations is O(log N) - for uniformly distributed random keys, but in worst case the complexity is O(N). + @attention Recall the tree is unbalanced. The complexity of operations is O(log N) + for uniformly distributed random keys, but in the worst case the complexity is O(N). @note Do not include header file explicitly. There are header file for each GC type: @@ -119,7 +146,7 @@ namespace cds { namespace intrusive { 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 @@ -141,13 +168,13 @@ namespace cds { namespace intrusive { { static internal_node const& to_internal_node( tree_node const& n ) { - assert( n.is_internal() ); + assert( n.is_internal()); return static_cast( n ); } static leaf_node const& to_leaf_node( tree_node const& n ) { - assert( n.is_leaf() ); + assert( n.is_leaf()); return static_cast( n ); } }; @@ -161,6 +188,8 @@ namespace cds { namespace intrusive { 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; @@ -175,9 +204,7 @@ namespace cds { namespace intrusive { Guard_Leaf, Guard_updGrandParent, Guard_updParent, - - // helping - Guard_helpLeaf, + Guard_temporary, // end of guard indices guard_count @@ -201,11 +228,6 @@ namespace cds { namespace intrusive { ,bRightLeaf( false ) ,bRightParent( false ) {} - - void clean_help_guards() - { - guards.clear( Guard_helpLeaf ); - } }; //@endcond @@ -221,9 +243,9 @@ namespace cds { namespace intrusive { protected: //@cond - static void free_leaf_node( value_type * p ) + static void free_leaf_node( void* p ) { - disposer()( p ); + disposer()( reinterpret_cast( p )); } internal_node * alloc_internal_node() const @@ -233,15 +255,15 @@ namespace cds { namespace intrusive { 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( 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 ); } }; @@ -253,14 +275,14 @@ namespace cds { namespace intrusive { 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( pDesc )); } void retire_node( tree_node * pNode ) const { - if ( pNode->is_leaf() ) { + if ( pNode->is_leaf()) { assert( static_cast( pNode ) != &m_LeafInf1 ); assert( static_cast( pNode ) != &m_LeafInf2 ); @@ -344,8 +366,8 @@ namespace cds { namespace intrusive { 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; @@ -353,8 +375,8 @@ namespace cds { namespace intrusive { 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 ); @@ -372,34 +394,36 @@ namespace cds { namespace intrusive { 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 where \p first is \p true if operation is successfull, + Returns std::pair 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 - std::pair ensure( value_type& val, Func func ) + std::pair update( value_type& val, Func func, bool bAllowInsert = true ) { typename gc::Guard guardInsert; guardInsert.assign( &val ); @@ -409,18 +433,20 @@ namespace cds { namespace intrusive { 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 ); @@ -430,13 +456,21 @@ namespace cds { namespace intrusive { } bkoff(); - m_Stat.onEnsureRetry(); + m_Stat.onUpdateRetry(); } ++m_ItemCounter; - m_Stat.onEnsureNew(); + m_Stat.onUpdateNew(); return std::make_pair( true, true ); } + //@cond + template + CDS_DEPRECATED("ensure() is deprecated, use update()") + std::pair ensure( value_type& val, Func func ) + { + return update( val, func, true ); + } + //@endcond /// Unlinks the item \p val from the tree /** @@ -465,7 +499,8 @@ namespace cds { namespace intrusive { 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 bool erase( const Q& key ) @@ -486,6 +521,7 @@ namespace cds { namespace intrusive { template bool erase_with( const Q& key, Less pred ) { + CDS_UNUSED( pred ); typedef ellen_bintree::details::compare< key_type, value_type, @@ -514,7 +550,8 @@ namespace cds { namespace intrusive { 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 bool erase( Q const& key, Func f ) @@ -535,6 +572,7 @@ namespace cds { namespace intrusive { template bool erase_with( Q const& key, Less pred, Func f ) { + CDS_UNUSED( pred ); typedef ellen_bintree::details::compare< key_type, value_type, @@ -563,9 +601,7 @@ namespace cds { namespace intrusive { */ 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 @@ -584,9 +620,7 @@ namespace cds { namespace intrusive { */ guarded_ptr extract_max() { - guarded_ptr gp; - extract_max_( gp.guard()); - return gp; + return extract_max_(); } /// Extracts an item from the tree @@ -602,9 +636,7 @@ namespace cds { namespace intrusive { template 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 @@ -618,24 +650,19 @@ namespace cds { namespace intrusive { template 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 - 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; } @@ -643,19 +670,25 @@ namespace cds { namespace intrusive { m_Stat.onFindFailed(); return false; } + //@cond + template + 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 contains( key ) 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 - 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, @@ -664,13 +697,21 @@ namespace cds { namespace intrusive { > 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 + 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 @@ -736,9 +777,7 @@ namespace cds { namespace intrusive { template 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 @@ -752,9 +791,7 @@ namespace cds { namespace intrusive { template 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 @@ -770,7 +807,7 @@ namespace cds { namespace intrusive { this sequence \code tree.clear(); - assert( tree.empty() ); + assert( tree.empty()); \endcode the assertion could be raised. @@ -797,7 +834,7 @@ namespace cds { namespace intrusive { tree_node * pLeaf = const_cast( &m_Root ); // Get leftmost leaf - while ( pLeaf->is_internal() ) { + while ( pLeaf->is_internal()) { pGrandParent = pParent; pParent = static_cast( pLeaf ); pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed ); @@ -811,10 +848,10 @@ namespace cds { namespace intrusive { // 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( pLeaf ) ) ); + free_leaf_node( node_traits::to_value_ptr( static_cast( pLeaf ))); free_internal_node( pParent ); } } @@ -863,11 +900,11 @@ namespace cds { namespace intrusive { && node_compare()( *pLeft, *pRight ) < 0 ) { bool bRet = true; - if ( pLeft->is_internal() ) - bRet = check_consistency( static_cast( pLeft ) ); + if ( pLeft->is_internal()) + bRet = check_consistency( static_cast( pLeft )); assert( bRet ); - if ( bRet && pRight->is_internal() ) + if ( bRet && pRight->is_internal()) bRet = bRet && check_consistency( static_cast( pRight )); assert( bRet ); @@ -878,14 +915,21 @@ namespace cds { namespace intrusive { 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( p )); - res.guards.assign( search_result::Guard_helpLeaf, node_traits::to_value_ptr( static_cast( 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(p);}) + : res.guards.protect( search_result::Guard_Leaf, pParent->m_pLeft, + []( tree_node * p ) -> internal_node* { return static_cast(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(p));} ) + : res.guards.protect( search_result::Guard_temporary, pParent->m_pLeft, + []( tree_node * p ) -> value_type* { return node_traits::to_value_ptr( static_cast(p));} ); // child node is guarded // See whether pParent->m_pUpdate has not been changed @@ -894,21 +938,20 @@ namespace cds { namespace intrusive { 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( p ))); + + res.guards.clear( search_result::Guard_temporary ); + return p; } - update_ptr search_protect_update( search_result& res, atomics::atomic const& src ) const + static update_ptr search_protect_update( search_result& res, atomics::atomic 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 @@ -929,7 +972,7 @@ namespace cds { namespace intrusive { updParent = nullptr; bRightLeaf = false; tree_node * pLeaf = const_cast( &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 ); @@ -940,7 +983,7 @@ namespace cds { namespace intrusive { 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(); @@ -957,8 +1000,8 @@ namespace cds { namespace intrusive { } } - assert( pLeaf->is_leaf() ); - nCmp = cmp( key, *static_cast(pLeaf) ); + assert( pLeaf->is_leaf()); + nCmp = cmp( key, *static_cast(pLeaf)); res.pGrandParent = pGrandParent; res.pParent = pParent; @@ -983,7 +1026,7 @@ namespace cds { namespace intrusive { pGrandParent = nullptr; updParent = nullptr; tree_node * pLeaf = const_cast( &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 ); @@ -993,7 +1036,7 @@ namespace cds { namespace intrusive { 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(); @@ -1012,7 +1055,7 @@ namespace cds { namespace intrusive { res.pGrandParent = pGrandParent; res.pParent = pParent; - assert( pLeaf->is_leaf() ); + assert( pLeaf->is_leaf()); res.pLeaf = static_cast( pLeaf ); res.updParent = updParent; res.updGrandParent = updGrandParent; @@ -1037,7 +1080,7 @@ namespace cds { namespace intrusive { updParent = nullptr; bRightLeaf = false; tree_node * pLeaf = const_cast( &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 ); @@ -1048,7 +1091,7 @@ namespace cds { namespace intrusive { 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(); @@ -1068,7 +1111,7 @@ namespace cds { namespace intrusive { res.pGrandParent = pGrandParent; res.pParent = pParent; - assert( pLeaf->is_leaf() ); + assert( pLeaf->is_leaf()); res.pLeaf = static_cast( pLeaf ); res.updParent = updParent; res.updGrandParent = updGrandParent; @@ -1082,18 +1125,18 @@ namespace cds { namespace intrusive { 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; } } @@ -1125,18 +1168,8 @@ namespace cds { namespace intrusive { assert( res.pGrandParent != nullptr ); - return - static_cast( - 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( - 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(res.pGrandParent->get_child( res.bRightParent, memory_model::memory_order_relaxed )) == res.pParent + && static_cast( res.pParent->get_child( res.bRightLeaf, memory_model::memory_order_relaxed )) == res.pLeaf; } bool help_delete( update_desc * pOp ) @@ -1173,21 +1206,11 @@ namespace cds { namespace intrusive { } } - tree_node * protect_sibling( typename gc::Guard& guard, atomics::atomic& sibling ) + static tree_node * protect_sibling( typename gc::Guard& guard, atomics::atomic& 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(p) ); - guardLeaf.assign( node_traits::to_value_ptr( static_cast(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(p); } ); + if ( pSibling->is_leaf()) + guard.assign( node_traits::to_value_ptr( static_cast( pSibling ))); return pSibling; } @@ -1217,18 +1240,16 @@ namespace cds { namespace intrusive { 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 )); } @@ -1240,13 +1261,13 @@ namespace cds { namespace intrusive { pNewInternal->m_pRight.store( static_cast(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(res.pLeaf), memory_model::memory_order_relaxed ); pNewInternal->m_pRight.store( static_cast(pNewLeaf), memory_model::memory_order_release ); - assert( !res.pLeaf->infinite_key() ); + assert( !res.pLeaf->infinite_key()); } typename gc::Guard guard; @@ -1258,9 +1279,9 @@ namespace cds { namespace intrusive { 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 ); @@ -1283,7 +1304,7 @@ namespace cds { namespace intrusive { 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(); @@ -1293,7 +1314,7 @@ namespace cds { namespace intrusive { 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 ); @@ -1304,12 +1325,12 @@ namespace cds { namespace intrusive { 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; @@ -1326,17 +1347,62 @@ namespace cds { namespace intrusive { return true; } + template + 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 - 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 - 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, @@ -1345,12 +1411,10 @@ namespace cds { namespace intrusive { 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; @@ -1362,13 +1426,13 @@ namespace cds { namespace intrusive { 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 ); @@ -1379,11 +1443,11 @@ namespace cds { namespace intrusive { 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; } @@ -1396,11 +1460,10 @@ namespace cds { namespace intrusive { --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; @@ -1412,13 +1475,13 @@ namespace cds { namespace intrusive { 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 ); @@ -1429,7 +1492,7 @@ namespace cds { namespace intrusive { 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 )) { @@ -1446,15 +1509,14 @@ namespace cds { namespace intrusive { --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 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 ); @@ -1467,7 +1529,7 @@ namespace cds { namespace intrusive { } template - 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, @@ -1477,7 +1539,7 @@ namespace cds { namespace intrusive { > 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 ); @@ -1490,15 +1552,41 @@ namespace cds { namespace intrusive { } template - 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 - 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, + 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 @@ -1506,4 +1594,4 @@ namespace cds { namespace intrusive { }} // namespace cds::intrusive -#endif // #ifndef __CDS_INTRUSIVE_IMPL_ELLEN_BINTREE_H +#endif // #ifndef CDSLIB_INTRUSIVE_IMPL_ELLEN_BINTREE_H