From 6f0946bd77c5fecad9004805b1b9974f5f446d52 Mon Sep 17 00:00:00 2001 From: khizmax Date: Sat, 4 Apr 2015 13:17:20 +0300 Subject: [PATCH] BronsonAVLTreeMap: fixed remove algorithm --- cds/container/impl/bronson_avltree_map_rcu.h | 41 +++++++++++--------- 1 file changed, 22 insertions(+), 19 deletions(-) diff --git a/cds/container/impl/bronson_avltree_map_rcu.h b/cds/container/impl/bronson_avltree_map_rcu.h index d5252e66..bbc93ffa 100644 --- a/cds/container/impl/bronson_avltree_map_rcu.h +++ b/cds/container/impl/bronson_avltree_map_rcu.h @@ -1358,6 +1358,8 @@ namespace cds { namespace container { return update_flags::failed; if ( child( pNode, left_child ) == nullptr || child( pNode, right_child ) == nullptr ) { + // pNode can be replaced with its child + node_type * pDamaged; mapped_type pOld; { @@ -1367,13 +1369,15 @@ namespace cds { namespace container { { node_scoped_lock ln( m_Monitor, *pNode ); + if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) + return update_flags::retry; + pOld = pNode->value( memory_model::memory_order_relaxed ); - if ( !( pNode->version( memory_model::memory_order_acquire ) == nVersion - && pOld - && try_unlink_locked( pParent, pNode, disp ))) - { + if ( !pOld ) + return update_flags::failed; + + if ( !try_unlink_locked( pParent, pNode, disp )) return update_flags::retry; - } } pDamaged = fix_height_locked( pParent ); } @@ -1388,30 +1392,29 @@ namespace cds { namespace container { fix_height_and_rebalance( pDamaged, disp ); m_stat.onRemoveRebalanceRequired(); } - return update_flags::result_removed; } else { - int result = update_flags::retry; + // pNode is an internal with two children + mapped_type pOld; { node_scoped_lock ln( m_Monitor, *pNode ); pOld = pNode->value( memory_model::memory_order_relaxed ); - if ( pNode->version( memory_model::memory_order_acquire ) == nVersion && pOld ) { - pNode->m_pValue.store( nullptr, memory_model::memory_order_relaxed ); - result = update_flags::result_removed; - } - } + if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) + return update_flags::retry; + if ( !pOld ) + return update_flags::failed; - if ( result == update_flags::result_removed ) { - --m_ItemCounter; - if ( func( pNode->m_key, pOld, disp )) // calls pOld disposer inside - m_stat.onDisposeValue(); - else - m_stat.onExtractValue(); + pNode->m_pValue.store( nullptr, memory_model::memory_order_relaxed ); } - return result; + --m_ItemCounter; + if ( func( pNode->m_key, pOld, disp )) // calls pOld disposer inside + m_stat.onDisposeValue(); + else + m_stat.onExtractValue(); } + return update_flags::result_removed; } bool try_unlink_locked( node_type * pParent, node_type * pNode, rcu_disposer& disp ) -- 2.34.1