Improved checking of internal consistency for BronsonAVLTree

[libcds.git] / cds / container / impl / bronson_avltree_map_rcu.h

diff --git a/cds/container/impl/bronson_avltree_map_rcu.h b/cds/container/impl/bronson_avltree_map_rcu.h
index 94fe48ade5847ed76f4414229b0f6e6c8ffaf577..775f63196174fd8feb676e501c2ca33884473549 100644 (file)
--- a/cds/container/impl/bronson_avltree_map_rcu.h
+++ b/cds/container/impl/bronson_avltree_map_rcu.h
@@ -143,6 +143,7 @@ namespace cds { namespace container {
         {
             // Free node without disposer
             assert( !pNode->is_valued( memory_model::memory_order_relaxed ));
+            assert( pNode->m_SyncMonitorInjection.check_free());
             cxx_allocator().Delete( pNode );
         }
 
@@ -761,8 +762,16 @@ namespace cds { namespace container {
         size_t do_check_consistency( node_type * pNode, size_t nLevel, Func f, size_t& nErrors ) const
         {
             if ( pNode ) {
-                size_t hLeft = do_check_consistency( child( pNode, left_child, memory_model::memory_order_relaxed ), nLevel + 1, f, nErrors );
-                size_t hRight = do_check_consistency( child( pNode, right_child, memory_model::memory_order_relaxed ), nLevel + 1, f, nErrors );
+                key_comparator cmp;
+                node_type * pLeft = child( pNode, left_child, memory_model::memory_order_relaxed );
+                node_type * pRight = child( pNode, right_child, memory_model::memory_order_relaxed );
+                if ( pLeft && cmp( pLeft->m_key, pNode->m_key ) > 0 )
+                    ++nErrors;
+                if (  pRight && cmp( pNode->m_key, pRight->m_key ) > 0 )
+                    ++nErrors;
+
+                size_t hLeft = do_check_consistency( pLeft, nLevel + 1, f, nErrors );
+                size_t hRight = do_check_consistency( pRight, nLevel + 1, f, nErrors );
 
                 if ( hLeft >= hRight ) {
                     if ( hLeft - hRight > 1 ) {
@@ -946,7 +955,6 @@ namespace cds { namespace container {
                     }
                 }
                 else if ( nChildVersion != node_type::unlinked ) {
-
                     if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
                         m_stat.onFindRetry();
                         return find_result::retry;
@@ -956,6 +964,11 @@ namespace cds { namespace container {
                     if ( found != find_result::retry )
                         return found;
                 }
+
+                if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
+                    m_stat.onFindRetry();
+                    return find_result::retry;
+                }
             }
         }
 
@@ -1097,6 +1110,11 @@ namespace cds { namespace container {
                         result = try_update( key, cmp, nFlags, funcUpdate, pNode, pChild, nChildVersion, disp );
                     }
                 }
+
+                if ( result == update_flags::retry && pNode->version( memory_model::memory_order_relaxed ) != nVersion ) {
+                    m_stat.onUpdateRetry();
+                    return update_flags::retry;
+                }
             } while ( result == update_flags::retry );
             return result;
         }
@@ -1148,6 +1166,11 @@ namespace cds { namespace container {
                         result = try_remove( key, cmp, func, pNode, pChild, nChildVersion, disp );
                     }
                 }
+
+                if ( result == update_flags::retry && pNode->version( memory_model::memory_order_relaxed ) != nVersion ) {
+                    m_stat.onRemoveRetry();
+                    return update_flags::retry;
+                }
             } while ( result == update_flags::retry );
             return result;
         }
@@ -1195,6 +1218,11 @@ namespace cds { namespace container {
                         result = try_extract_minmax( nDir, func, pNode, pChild, nChildVersion, disp );
                     }
                 }
+
+                if ( result == update_flags::retry && pNode->version( memory_model::memory_order_relaxed ) != nVersion ) {
+                    m_stat.onRemoveRetry();
+                    return update_flags::retry;
+                }
             } while ( result == update_flags::retry );
             return result;
         }
@@ -1251,7 +1279,10 @@ namespace cds { namespace container {
             ++m_ItemCounter;
             m_stat.onInsertSuccess();
 
-            fix_height_and_rebalance( pDamaged, disp );
+            if ( pDamaged ) {
+                fix_height_and_rebalance( pDamaged, disp );
+                m_stat.onInsertRebalanceRequired();
+            }
 
             return update_flags::result_inserted;
         }
@@ -1326,7 +1357,10 @@ namespace cds { namespace container {
                 else
                     m_stat.onExtractValue();
 
-                fix_height_and_rebalance( pDamaged, disp );
+                if ( pDamaged ) {
+                    fix_height_and_rebalance( pDamaged, disp );
+                    m_stat.onRemoveRebalanceRequired();
+                }
                 return update_flags::result_removed;
             }
             else {