X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fintrusive%2Fimpl%2Fellen_bintree.h;h=6efca113f425066c7827391ea5004ce4db99802a;hb=744211978eaf0cbcd9139d07b8dfd6f72651b39f;hp=dbcafc1170e143c3357481cc3756b9181c38b359;hpb=f4d56635f899073e5dd2b83c208aabf793031861;p=libcds.git diff --git a/cds/intrusive/impl/ellen_bintree.h b/cds/intrusive/impl/ellen_bintree.h index dbcafc11..6efca113 100644 --- a/cds/intrusive/impl/ellen_bintree.h +++ b/cds/intrusive/impl/ellen_bintree.h @@ -1,7 +1,35 @@ -//$$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-2016 + + 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 @@ -33,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: @@ -160,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; @@ -174,9 +204,7 @@ namespace cds { namespace intrusive { Guard_Leaf, Guard_updGrandParent, Guard_updParent, - - // helping - Guard_helpLeaf, + Guard_temporary, // end of guard indices guard_count @@ -200,11 +228,6 @@ namespace cds { namespace intrusive { ,bRightLeaf( false ) ,bRightParent( false ) {} - - void clean_help_guards() - { - guards.clear( Guard_helpLeaf ); - } }; //@endcond @@ -371,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 ); @@ -412,11 +437,13 @@ namespace cds { namespace intrusive { func( false, *node_traits::to_value_ptr( res.pLeaf ), val ); 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() ); @@ -429,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 /** @@ -464,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 ) @@ -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 ) @@ -564,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 @@ -585,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 @@ -603,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 @@ -619,21 +650,16 @@ 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() )) { @@ -644,18 +670,23 @@ 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< @@ -673,6 +704,14 @@ namespace cds { namespace intrusive { 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 @@ -738,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 @@ -754,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 @@ -880,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 @@ -896,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 @@ -1127,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 ) @@ -1175,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 )) ); - + tree_node * pSibling = guard.protect( sibling, [](tree_node * p) -> internal_node* { return static_cast(p); } ); if ( pSibling->is_leaf() ) - guard.copy( guardLeaf ); - + guard.assign( node_traits::to_value_ptr( static_cast( pSibling ))); return pSibling; } @@ -1222,9 +1243,7 @@ namespace cds { namespace intrusive { 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); @@ -1243,8 +1262,8 @@ namespace cds { namespace intrusive { } else { assert( !res.pLeaf->is_internal() ); - pNewInternal->infinite_key( 0 ); + 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 ); @@ -1328,18 +1347,63 @@ 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 guarded_ptr::native_guard& guard, Q const& key ) + guarded_ptr extract_( Q const& key ) { - return erase_( key, node_compare(), - []( Q const&, leaf_node const& ) -> bool { return true; }, - [&guard]( value_type& found ) { guard.set( &found ); } ); + return extract_item( key, node_compare()); } template - bool extract_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less pred ) + guarded_ptr extract_with_( Q const& key, Less /*pred*/ ) { - CDS_UNUSED( pred ); typedef ellen_bintree::details::compare< key_type, value_type, @@ -1347,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.set( &found ); } ); + return extract_item( key, compare_functor()); } - bool extract_max_( typename guarded_ptr::native_guard& gp ) + guarded_ptr extract_max_() { update_desc * pOp = nullptr; search_result res; @@ -1364,7 +1426,7 @@ 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 ) { @@ -1383,7 +1445,7 @@ namespace cds { namespace intrusive { 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 ) ) break; @@ -1398,11 +1460,10 @@ namespace cds { namespace intrusive { --m_ItemCounter; m_Stat.onExtractMaxSuccess(); - gp.set( node_traits::to_value_ptr( res.pLeaf )); - return true; + return guarded_ptr( res.guards.release( search_result::Guard_Leaf )); } - bool extract_min_( typename guarded_ptr::native_guard& gp ) + guarded_ptr extract_min_() { update_desc * pOp = nullptr; search_result res; @@ -1414,7 +1475,7 @@ 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 ) { @@ -1448,8 +1509,7 @@ namespace cds { namespace intrusive { --m_ItemCounter; m_Stat.onExtractMinSuccess(); - gp.set( node_traits::to_value_ptr( res.pLeaf )); - return true; + return guarded_ptr( res.guards.release( search_result::Guard_Leaf )); } template @@ -1469,9 +1529,8 @@ 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 { - CDS_UNUSED( pred ); typedef ellen_bintree::details::compare< key_type, value_type, @@ -1493,15 +1552,41 @@ namespace cds { namespace intrusive { } template - bool get_( typename guarded_ptr::native_guard& guard, Q const& val ) const + guarded_ptr get_( Q const& val ) const { - return find_( val, [&guard]( value_type& found, Q const& ) { guard.set( &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 guarded_ptr::native_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.set( &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 @@ -1509,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