projects / libcds.git / blobdiff
? search:
summary | shortlog | log | commit | commitdiff | tree
raw | inline | side by side
formatting
[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 e3cea47c6fdca871190a88377753ce07a22a6073..f21253b5728529262d7bf252b7290dc1d3a53f49 100644 (file)
--- a/cds/container/impl/bronson_avltree_map_rcu.h
+++ b/cds/container/impl/bronson_avltree_map_rcu.h
@@ -1349,7 +1349,7 @@ namespace cds { namespace container {
 
                     if ( !pChild ) {
                         // Found min/max
-                        if ( pNode->is_valued( memory_model::memory_order_acquire ) ) {
+                        if ( pNode->is_valued( memory_model::memory_order_acquire )) {
                             int result = try_remove_node( pParent, pNode, nVersion, func, disp );
 
                             if ( result == update_flags::result_removed )
@@ -1416,7 +1416,7 @@ namespace cds { namespace container {
                 pNew->m_pValue.store( pVal, memory_model::memory_order_release );
             };
 
-            if ( c_bRelaxedInsert ) {
+            static_if ( c_bRelaxedInsert ) {
                 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion
                      || child( pNode, nDir, memory_model::memory_order_acquire ) != nullptr )
                 {
@@ -1435,7 +1435,7 @@ namespace cds { namespace container {
                 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion
                      || child( pNode, nDir, memory_model::memory_order_acquire ) != nullptr )
                 {
-                    if ( c_bRelaxedInsert ) {
+                    static_if ( c_bRelaxedInsert ) {
                         mapped_type pVal = pNew->m_pValue.load( memory_model::memory_order_relaxed );
                         pNew->m_pValue.store( nullptr, memory_model::memory_order_relaxed );
                         free_value( pVal );
@@ -1447,7 +1447,7 @@ namespace cds { namespace container {
                     return update_flags::retry;
                 }
 
-                if ( !c_bRelaxedInsert )
+                static_if ( !c_bRelaxedInsert )
                     fnCreateNode( pNew = alloc_node( key, 1, 0, pNode, nullptr, nullptr ));
 
                 pNode->child( pNew, nDir, memory_model::memory_order_release );
@@ -1785,7 +1785,7 @@ namespace cds { namespace container {
 
                     int hLRL = height_null( child( pLRight, left_child, memory_model::memory_order_relaxed ), memory_model::memory_order_acquire );
                     int balance = hLL - hLRL;
-                    if ( balance >= -1 && balance <= 1 && !( ( hLL == 0 || hLRL == 0 ) && !pLeft->is_valued( memory_model::memory_order_relaxed ) ) ) {
+                    if ( balance >= -1 && balance <= 1 && !( ( hLL == 0 || hLRL == 0 ) && !pLeft->is_valued( memory_model::memory_order_relaxed ))) {
                         // nParent.child.left won't be damaged after a double rotation
                         return rotate_right_over_left_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLRL );
                     }
@@ -1798,7 +1798,7 @@ namespace cds { namespace container {
                 // rotate right
                 return rotate_right_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLR );
             }
-            
+
             return pNode; // retry
         }
 
@@ -1840,7 +1840,7 @@ namespace cds { namespace container {
                     node_type * pRLRight = child( pRLeft, right_child, memory_model::memory_order_relaxed );
                     int hRLR = height_null( pRLRight, memory_model::memory_order_acquire );
                     int balance = hRR - hRLR;
-                    if ( balance >= -1 && balance <= 1 && !( ( hRR == 0 || hRLR == 0 ) && !pRight->is_valued( memory_model::memory_order_relaxed ) ) )
+                    if ( balance >= -1 && balance <= 1 && !( ( hRR == 0 || hRLR == 0 ) && !pRight->is_valued( memory_model::memory_order_relaxed )))
                         return rotate_left_over_right_locked( pParent, pNode, hL, pRight, pRLeft, hRR, hRLR );
                 }
 
@@ -1856,7 +1856,7 @@ namespace cds { namespace container {
         {
             assert(pNode->version(memory_model::memory_order_acquire) == version );
             assert( (version & node_type::shrinking) == 0 );
-            pNode->version( version | node_type::shrinking, memory_model::memory_order_release );
+            pNode->exchange_version( version | node_type::shrinking, memory_model::memory_order_acquire );
         }
         static void end_change( node_type * pNode, version_type version )
         {
@@ -1872,25 +1872,40 @@ namespace cds { namespace container {
             begin_change( pNode, nodeVersion );
 
             pNode->m_pLeft.store( pLRight, memory_model::memory_order_release );
+
             if ( pLRight != nullptr ) {
-                pLRight->parent( pNode, memory_model::memory_order_release );
+                atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
+                CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pLRight->m_pParent );
+                pLRight->parent( pNode, memory_model::memory_order_relaxed );
                 assert( check_node_ordering( pNode, pLRight ) > 0 );
             }
 
-            pLeft->m_pRight.store( pNode, memory_model::memory_order_release );
-            pNode->parent( pLeft, memory_model::memory_order_release );
+            atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
+            CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pLeft->m_pRight );
+            pLeft->m_pRight.store( pNode, memory_model::memory_order_relaxed );
+
+            atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
+
+            CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pNode->m_pParent );
+            pNode->parent( pLeft, memory_model::memory_order_relaxed );
             assert( check_node_ordering( pLeft, pNode ) < 0 );
 
+            atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
             if ( pParentLeft == pNode ) {
-                pParent->m_pLeft.store( pLeft, memory_model::memory_order_release );
-                assert( check_node_ordering( pParent, pLeft ) > 0 );
+                CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pParent->m_pLeft );
+                pParent->m_pLeft.store( pLeft, memory_model::memory_order_relaxed );
             }
             else {
                 assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
-                pParent->m_pRight.store( pLeft, memory_model::memory_order_release );
-                assert( check_node_ordering( pParent, pLeft ) < 0 );
+                CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pParent->m_pRight );
+                pParent->m_pRight.store( pLeft, memory_model::memory_order_relaxed );
             }
-            pLeft->parent( pParent, memory_model::memory_order_release );
+
+            atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
+            CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pLeft->m_pParent );
+            pLeft->parent( pParent, memory_model::memory_order_relaxed );
+
+            atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
 
             // fix up heights links
             int hNode = 1 + std::max( hLR, hR );
@@ -1948,23 +1963,37 @@ namespace cds { namespace container {
 
             // fix up pNode links, careful to be compatible with concurrent traversal for all but pNode
             pNode->m_pRight.store( pRLeft, memory_model::memory_order_release );
-            if ( pRLeft != nullptr )
-                pRLeft->parent( pNode, memory_model::memory_order_release );
+            if ( pRLeft != nullptr ) {
+                atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
+                CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pRLeft->m_pParent );
+                pRLeft->parent( pNode, memory_model::memory_order_relaxed );
+            }
+
+            atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
+            CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pRight->m_pLeft );
+            pRight->m_pLeft.store( pNode, memory_model::memory_order_relaxed );
 
-            pRight->m_pLeft.store( pNode, memory_model::memory_order_release );
-            pNode->parent( pRight, memory_model::memory_order_release );
+            atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
+            CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pNode->m_pParent );
+            pNode->parent( pRight, memory_model::memory_order_relaxed );
             assert( check_node_ordering( pRight, pNode ) > 0 );
 
+            atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
             if ( pParentLeft == pNode ) {
-                pParent->m_pLeft.store( pRight, memory_model::memory_order_release );
-                assert( check_node_ordering( pParent, pRight ) > 0 );
+                CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pParent->m_pLeft );
+                pParent->m_pLeft.store( pRight, memory_model::memory_order_relaxed );
             }
             else {
                 assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
-                pParent->m_pRight.store( pRight, memory_model::memory_order_release );
-                assert( check_node_ordering( pParent, pRight ) < 0 );
+                CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pParent->m_pRight );
+                pParent->m_pRight.store( pRight, memory_model::memory_order_relaxed );
             }
-            pRight->parent( pParent, memory_model::memory_order_release );
+
+            atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
+            CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pRight->m_pParent );
+            pRight->parent( pParent, memory_model::memory_order_relaxed );
+
+            atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
 
             // fix up heights
             int hNode = 1 + std::max( hL, hRL );
@@ -2014,31 +2043,56 @@ namespace cds { namespace container {
 
             // fix up pNode links, careful about the order!
             pNode->m_pLeft.store( pLRR, memory_model::memory_order_release );
-            if ( pLRR != nullptr )
-                pLRR->parent( pNode, memory_model::memory_order_release );
+            if ( pLRR != nullptr ) {
+                atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
+                CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pLRR->m_pParent );
+                pLRR->parent( pNode, memory_model::memory_order_relaxed );
+            }
+
+            atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
+            CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pLeft->m_pRight );
+            pLeft->m_pRight.store( pLRL, memory_model::memory_order_relaxed );
 
-            pLeft->m_pRight.store( pLRL, memory_model::memory_order_release );
-            if ( pLRL != nullptr )
-                pLRL->parent( pLeft, memory_model::memory_order_release );
+            if ( pLRL != nullptr ) {
+                atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
+                CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pLRL->m_pParent );
+                pLRL->parent( pLeft, memory_model::memory_order_relaxed );
+            }
+
+            atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
+            CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pLRight->m_pLeft );
+            pLRight->m_pLeft.store( pLeft, memory_model::memory_order_relaxed );
 
-            pLRight->m_pLeft.store( pLeft, memory_model::memory_order_release );
-            pLeft->parent( pLRight, memory_model::memory_order_release );
+            atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
+            CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pLeft->m_pParent );
+            pLeft->parent( pLRight, memory_model::memory_order_relaxed );
             assert( check_node_ordering( pLRight, pLeft ) > 0 );
 
-            pLRight->m_pRight.store( pNode, memory_model::memory_order_release );
-            pNode->parent( pLRight, memory_model::memory_order_release );
+            atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
+            CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pLRight->m_pRight );
+            pLRight->m_pRight.store( pNode, memory_model::memory_order_relaxed );
+
+            atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
+            CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pNode->m_pParent );
+            pNode->parent( pLRight, memory_model::memory_order_relaxed );
             assert( check_node_ordering( pLRight, pNode ) < 0 );
 
+            atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
             if ( pPL == pNode ) {
-                pParent->m_pLeft.store( pLRight, memory_model::memory_order_release );
-                assert( check_node_ordering( pParent, pLRight ) > 0 );
+                CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pParent->m_pLeft );
+                pParent->m_pLeft.store( pLRight, memory_model::memory_order_relaxed );
             }
             else {
                 assert( child( pParent, right_child, memory_model::memory_order_relaxed ) == pNode );
-                pParent->m_pRight.store( pLRight, memory_model::memory_order_release );
-                assert( check_node_ordering( pParent, pLRight ) < 0 );
+                CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pParent->m_pRight );
+                pParent->m_pRight.store( pLRight, memory_model::memory_order_relaxed );
             }
-            pLRight->parent( pParent, memory_model::memory_order_release );
+
+            atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
+            CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pLRight->m_pParent );
+            pLRight->parent( pParent, memory_model::memory_order_relaxed );
+
+            atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
 
             // fix up heights
             int hNode = 1 + std::max( hLRR, hR );
@@ -2103,31 +2157,56 @@ namespace cds { namespace container {
 
             // fix up pNode links, careful about the order!
             pNode->m_pRight.store( pRLL, memory_model::memory_order_release );
-            if ( pRLL != nullptr )
-                pRLL->parent( pNode, memory_model::memory_order_release );
+            if ( pRLL != nullptr ) {
+                atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
+                CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pRLL->m_pParent );
+                pRLL->parent( pNode, memory_model::memory_order_relaxed );
+            }
 
-            pRight->m_pLeft.store( pRLR, memory_model::memory_order_release );
-            if ( pRLR != nullptr )
-                pRLR->parent( pRight, memory_model::memory_order_release );
+            atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
+            CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pRight->m_pLeft );
+            pRight->m_pLeft.store( pRLR, memory_model::memory_order_relaxed );
 
-            pRLeft->m_pRight.store( pRight, memory_model::memory_order_release );
-            pRight->parent( pRLeft, memory_model::memory_order_release );
+            if ( pRLR != nullptr ) {
+                atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
+                CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pRLR->m_pParent );
+                pRLR->parent( pRight, memory_model::memory_order_relaxed );
+            }
+
+            atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
+            CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pRLeft->m_pRight );
+            pRLeft->m_pRight.store( pRight, memory_model::memory_order_relaxed );
+
+            atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
+            CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pRight->m_pParent );
+            pRight->parent( pRLeft, memory_model::memory_order_relaxed );
             assert( check_node_ordering( pRLeft, pRight ) < 0 );
 
-            pRLeft->m_pLeft.store( pNode, memory_model::memory_order_release );
-            pNode->parent( pRLeft, memory_model::memory_order_release );
+            atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
+            CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pRLeft->m_pLeft );
+            pRLeft->m_pLeft.store( pNode, memory_model::memory_order_relaxed );
+
+            atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
+            CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pNode->m_pParent );
+            pNode->parent( pRLeft, memory_model::memory_order_relaxed );
             assert( check_node_ordering( pRLeft, pNode ) > 0 );
 
+            atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
             if ( pPL == pNode ) {
-                pParent->m_pLeft.store( pRLeft, memory_model::memory_order_release );
-                assert( check_node_ordering( pParent, pRLeft ) > 0 );
+                CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pParent->m_pLeft );
+                pParent->m_pLeft.store( pRLeft, memory_model::memory_order_relaxed );
             }
             else {
                 assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
-                pParent->m_pRight.store( pRLeft, memory_model::memory_order_release );
-                assert( check_node_ordering( pParent, pRLeft ) < 0 );
+                CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pParent->m_pRight );
+                pParent->m_pRight.store( pRLeft, memory_model::memory_order_relaxed );
             }
-            pRLeft->parent( pParent, memory_model::memory_order_release );
+
+            atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
+            CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &pRLeft->m_pParent );
+            pRLeft->parent( pParent, memory_model::memory_order_relaxed );
+
+            atomics::atomic_thread_fence( memory_model::memory_order_acq_rel );
 
             // fix up heights
             int hNode = 1 + std::max( hL, hRLL );
Unnamed repository; edit this file 'description' to name the repository.