From c99bcbf0ccccc3ac60238eb64d7be1518d12051f Mon Sep 17 00:00:00 2001 From: khizmax Date: Sun, 26 Jul 2015 14:03:59 +0300 Subject: [PATCH] intrusive MichaelList: replaced ensure() with update() --- cds/intrusive/impl/michael_list.h | 29 +++++++++++++++---- cds/intrusive/michael_list_rcu.h | 48 +++++++++++++++++++++++-------- 2 files changed, 60 insertions(+), 17 deletions(-) diff --git a/cds/intrusive/impl/michael_list.h b/cds/intrusive/impl/michael_list.h index cbb402f5..590476aa 100644 --- a/cds/intrusive/impl/michael_list.h +++ b/cds/intrusive/impl/michael_list.h @@ -525,11 +525,12 @@ namespace cds { namespace intrusive { return insert_at( m_pHead, val, f ); } - /// Ensures that the \p val exists in the list + /// Updates the node /** The operation performs inserting or changing data with lock-free manner. - If the item \p val is not found in the list, then \p val is inserted. + If the item \p val is not found in the list, then \p val is inserted + iff \p bInsert is \p true. Otherwise, the functor \p func is called with item found. The functor signature is: \code @@ -538,7 +539,7 @@ namespace cds { namespace intrusive { with arguments: - \p bNew - \p true if the item has been inserted, \p false otherwise - \p item - item of the list - - \p val - argument \p val passed into the \p ensure function + - \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 refers to the same thing. @@ -552,10 +553,19 @@ namespace cds { namespace intrusive { @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template + std::pair update( value_type& val, Func func, bool bInsert = true ) + { + return update_at( m_pHead, val, func, bInsert ); + } + + //@cond + // Deprecated, use update() + template std::pair ensure( value_type& val, Func func ) { - return ensure_at( m_pHead, val, func ); + return update( val, func, true ); } + //@endcond /// Unlinks the item \p val from the list /** @@ -925,7 +935,7 @@ namespace cds { namespace intrusive { } template - std::pair ensure_at( atomic_node_ptr& refHead, value_type& val, Func func ) + std::pair update_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert ) { position pos; @@ -942,6 +952,9 @@ namespace cds { namespace intrusive { return std::make_pair( true, false ); } else { + if ( !bInsert ) + return std::make_pair( false, false ); + typename gc::Guard guard; guard.assign( &val ); if ( link_node( pNode, pos ) ) { @@ -955,6 +968,12 @@ namespace cds { namespace intrusive { } } + template + std::pair ensure_at( atomic_node_ptr& refHead, value_type& val, Func func ) + { + return update_at( refHead, val, func, true ); + } + bool unlink_at( atomic_node_ptr& refHead, value_type& val ) { position pos; diff --git a/cds/intrusive/michael_list_rcu.h b/cds/intrusive/michael_list_rcu.h index 85d3542b..8b4adbf3 100644 --- a/cds/intrusive/michael_list_rcu.h +++ b/cds/intrusive/michael_list_rcu.h @@ -447,11 +447,12 @@ namespace cds { namespace intrusive { return insert_at( m_pHead, val, f ); } - /// Ensures that the \p item exists in the list + /// Updates the item /** The operation performs inserting or changing data with lock-free manner. - If the item \p val not found in the list, then \p val is inserted into the list. + If the item \p val not found in the list, then \p val is inserted into the list + iff \p bInsert is \p true. Otherwise, the functor \p func is called with item found. The functor signature is: \code @@ -462,15 +463,15 @@ namespace cds { namespace intrusive { with arguments: - \p bNew - \p true if the item has been inserted, \p false otherwise - \p item - item of the list - - \p val - argument \p val passed into the \p ensure function + - \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 may 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 true if operation is successfull, - \p second is true if new item has been added or \p false if the item with \p key + Returns std::pair where \p first is \p true if operation is successfull, + \p second is \p true if new item has been added or \p false if the item with \p key already is in the list. The function makes RCU lock internally. @@ -478,9 +479,17 @@ namespace cds { namespace intrusive { @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template + std::pair update( value_type& val, Func func, bool bInsert = true ) + { + return update_at( m_pHead, val, func, bInsert ); + } + + //@cond + // Deprecated, use update() + template std::pair ensure( value_type& val, Func func ) { - return ensure_at( m_pHead, val, func ); + return update( val, func, true ); } /// Unlinks the item \p val from the list @@ -886,26 +895,38 @@ namespace cds { namespace intrusive { } template - std::pair ensure_at_( atomic_node_ptr& refHead, value_type& val, Func func ) + std::pair update_at_( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert ) { position pos( refHead ); { rcu_lock l; - return ensure_at_locked( pos, val, func ); + return update_at_locked( pos, val, func, bInsert ); } } template - std::pair ensure_at( atomic_node_ptr& refHead, value_type& val, Func func ) + std::pair ensure_at_( atomic_node_ptr& refHead, value_type& val, Func func ) + { + return update_at_( refHead, val, func, true ); + } + + template + std::pair update_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert ) { position pos( refHead ); { rcu_lock l; - std::pair ret = ensure_at_locked( pos, val, func ); + std::pair ret = update_at_locked( pos, val, func, bInsert ); return std::make_pair( ret.first != end(), ret.second ); } } + template + std::pair ensure_at( atomic_node_ptr& refHead, value_type& val, Func func ) + { + return update_at( refHead, val, func, true ); + } + bool unlink_at( atomic_node_ptr& refHead, value_type& val ) { position pos( refHead ); @@ -987,7 +1008,7 @@ namespace cds { namespace intrusive { --m_ItemCounter; value_type * pRet = node_traits::to_value_ptr( pExtracted ); - assert( pRet->m_pDelChain == nullptr ); + assert( pExtracted->m_pDelChain == nullptr ); return pRet; } } @@ -1117,7 +1138,7 @@ namespace cds { namespace intrusive { } template - std::pair ensure_at_locked( position& pos, value_type& val, Func func ) + std::pair update_at_locked( position& pos, value_type& val, Func func, bool bInsert ) { // RCU lock should be locked!!! assert( gc::is_locked() ); @@ -1130,6 +1151,9 @@ namespace cds { namespace intrusive { return std::make_pair( iterator( pos.pCur ), false ); } else { + if ( !bInsert ) + return std::make_pair( end(), false ); + link_checker::is_empty( node_traits::to_node_ptr( val ) ); if ( link_node( node_traits::to_node_ptr( val ), pos ) ) { -- 2.34.1