From: khizmax <libcds.dev@gmail.com>
Date: Fri, 3 Feb 2017 20:54:07 +0000 (+0300)
Subject: BronsonAVLTreeMap: fixed extract_min/max functions
X-Git-Tag: v2.3.0~180
X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=commitdiff_plain;h=d42a1367cdc1bebc74fe74b5ac8164b76d27eb22

BronsonAVLTreeMap: fixed extract_min/max functions
---

diff --git a/cds/container/details/bronson_avltree_base.h b/cds/container/details/bronson_avltree_base.h
index c4fe4de4..9f83ba23 100644
--- a/cds/container/details/bronson_avltree_base.h
+++ b/cds/container/details/bronson_avltree_base.h
@@ -450,15 +450,15 @@ namespace cds { namespace container {
 
             /// Internal statistics
             /**
-                By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
-                To enable it use \p ellen_bintree::stat.
+                By default, internal statistics is disabled (\p bronson_avltree::empty_stat).
+                To enable it use \p bronson_avltree::stat.
             */
             typedef empty_stat                      stat;
 
             /// Back-off strategy
             typedef cds::backoff::empty             back_off;
 
-            /// RCU deadlock checking policy (only for \ref cds_container_BronsonAVLTreeMap_rcu "RCU-based BronsonAVLTree")
+            /// RCU deadlock checking policy
             /**
                 List of available options see \p opt::rcu_check_deadlock
             */
diff --git a/cds/container/impl/bronson_avltree_map_rcu.h b/cds/container/impl/bronson_avltree_map_rcu.h
index 746ffae4..a7d682fe 100644
--- a/cds/container/impl/bronson_avltree_map_rcu.h
+++ b/cds/container/impl/bronson_avltree_map_rcu.h
@@ -1339,21 +1339,36 @@ namespace cds { namespace container {
                 nVersion = stack[pos].nVersion;
 
                 while ( true ) {
-                    node_type * pChild = child( pNode, nDir, memory_model::memory_order_acquire );
+                    int iterDir = nDir;
+                    node_type * pChild = child( pNode, iterDir, memory_model::memory_order_acquire );
                     if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
                         --pos;
                         m_stat.onRemoveRetry();
                         break;
                     }
 
-                    if ( pChild == nullptr ) {
+                    if ( !pChild ) {
                         // Found min/max
-                        int result = try_remove_node( pParent, pNode, nVersion, func, disp );
-                        if ( result != update_flags::retry )
-                            return result;
-                        --pos;
-                        m_stat.onRemoveRetry();
-                        break;
+                        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 )
+                                return result;
+
+                            --pos;
+                            m_stat.onRemoveRetry();
+                            break;
+                        }
+                        else {
+                            // check right (for min) or left (for max) child node
+                            iterDir = -iterDir;
+                            pChild = child( pNode, iterDir, memory_model::memory_order_acquire );
+                            if ( !pChild ) {
+                                --pos;
+                                m_stat.onRemoveRetry();
+                                break;
+                            }
+                        }
                     }
 
                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
@@ -1362,7 +1377,7 @@ namespace cds { namespace container {
                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_acquire );
                         // retry
                     }
-                    else if ( pChild == child( pNode, nDir, memory_model::memory_order_acquire )) {
+                    else if ( pChild == child( pNode, iterDir, memory_model::memory_order_acquire )) {
                         // this second read is important, because it is protected by nChildVersion
 
                         // validate the read that our caller took to get to node
@@ -1848,13 +1863,9 @@ namespace cds { namespace container {
             if ( pLRight != nullptr )
                 pLRight->parent( pNode, memory_model::memory_order_release  );
 
-            atomics::atomic_thread_fence( memory_model::memory_order_release );
-
             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_release );
-
             if ( pParentLeft == pNode )
                 pParent->m_pLeft.store( pLeft, memory_model::memory_order_release );
             else {
@@ -1863,8 +1874,6 @@ namespace cds { namespace container {
             }
             pLeft->parent( pParent, memory_model::memory_order_release );
 
-            atomics::atomic_thread_fence( memory_model::memory_order_release );
-
             // fix up heights links
             int hNode = 1 + std::max( hLR, hR );
             set_height( pNode, hNode, memory_model::memory_order_release );
@@ -1924,13 +1933,9 @@ namespace cds { namespace container {
             if ( pRLeft != nullptr )
                 pRLeft->parent( pNode, memory_model::memory_order_release );
 
-            atomics::atomic_thread_fence( memory_model::memory_order_release );
-
             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_release );
-
             if ( pParentLeft == pNode )
                 pParent->m_pLeft.store( pRight, memory_model::memory_order_release );
             else {
@@ -1939,8 +1944,6 @@ namespace cds { namespace container {
             }
             pRight->parent( pParent, memory_model::memory_order_release );
 
-            atomics::atomic_thread_fence( memory_model::memory_order_release );
-
             // fix up heights
             int hNode = 1 + std::max( hL, hRL );
             set_height( pNode, hNode, memory_model::memory_order_release );
diff --git a/test/stress/map/map_type_bronson_avltree.h b/test/stress/map/map_type_bronson_avltree.h
index 7f6ee03a..58a55b45 100644
--- a/test/stress/map/map_type_bronson_avltree.h
+++ b/test/stress/map/map_type_bronson_avltree.h
@@ -190,7 +190,7 @@ namespace map {
             {
                 EXPECT_TRUE( false ) << "Tree violation on level=" << nLevel << ": hLeft=" << hLeft << ", hRight=" << hRight;
             });
-        EXPECT_TRUE( check_consistency_result );
+        EXPECT_TRUE( check_consistency_result ) << "Internal tree structure violation";
     }