projects / libcds.git / blobdiff
? search:
summary | shortlog | log | commit | commitdiff | tree
raw | inline | side by side
BronsonAVLTreeMap: fixed extract_min/max functions
[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 55423a9d2e417a735cafae68c2f042f089560b7a..a7d682fefc6b8d87b0ee9ded2725831806dee58c 100644 (file)
--- a/cds/container/impl/bronson_avltree_map_rcu.h
+++ b/cds/container/impl/bronson_avltree_map_rcu.h
@@ -1,11 +1,11 @@
 /*
     This file is a part of libcds - Concurrent Data Structures library
 
-    (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+    (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
-    
+
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
@@ -25,7 +25,7 @@
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #ifndef CDSLIB_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H
@@ -231,7 +231,7 @@ namespace cds { namespace container {
 
             void clean()
             {
-                assert( !gc::is_locked() );
+                assert( !gc::is_locked());
 
                 // TODO: use RCU::batch_retire
 
@@ -675,7 +675,7 @@ namespace cds { namespace container {
             this sequence
             \code
             set.clear();
-            assert( set.empty() );
+            assert( set.empty());
             \endcode
             the assertion could be raised.
 
@@ -685,7 +685,7 @@ namespace cds { namespace container {
         */
         void clear()
         {
-            while ( extract_min() );
+            while ( extract_min());
         }
 
         /// Clears the tree (not thread safe)
@@ -962,7 +962,7 @@ namespace cds { namespace container {
         template <typename Q, typename Compare, typename Func>
         find_result try_find( Q const& key, Compare cmp, Func f, node_type * pNode, int nDir, version_type nVersion ) const
         {
-            assert( gc::is_locked() );
+            assert( gc::is_locked());
             assert( pNode );
 
             struct stack_record
@@ -997,12 +997,12 @@ namespace cds { namespace container {
 
                     int nCmp = cmp( key, pChild->m_key );
                     if ( nCmp == 0 ) {
-                        if ( pChild->is_valued( memory_model::memory_order_acquire ) ) {
+                        if ( pChild->is_valued( memory_model::memory_order_acquire )) {
                             // key found
                             node_scoped_lock l( m_Monitor, *pChild );
                             if ( child(pNode, nDir, memory_model::memory_order_acquire) == pChild ) {
                                 if ( pChild->is_valued( memory_model::memory_order_relaxed )) {
-                                    if ( f( pChild ) ) {
+                                    if ( f( pChild )) {
                                         m_stat.onFindSuccess();
                                         return find_result::found;
                                     }
@@ -1059,7 +1059,7 @@ namespace cds { namespace container {
         template <typename K, typename Compare, typename Func>
         int try_update_root( K const& key, Compare cmp, int nFlags, Func funcUpdate, rcu_disposer& disp )
         {
-            assert( gc::is_locked() );
+            assert( gc::is_locked());
 
             while ( true ) {
                 int result;
@@ -1114,7 +1114,7 @@ namespace cds { namespace container {
         template <typename K, typename Compare, typename Func>
         bool try_remove_root( K const& key, Compare cmp, Func func, rcu_disposer& disp )
         {
-            assert( gc::is_locked() );
+            assert( gc::is_locked());
 
             while ( true ) {
                 int result;
@@ -1149,7 +1149,7 @@ namespace cds { namespace container {
         template <typename K, typename Compare, typename Func>
         int try_update( K const& key, Compare cmp, int nFlags, Func funcUpdate, node_type * pNode, version_type nVersion, rcu_disposer& disp )
         {
-            assert( gc::is_locked() );
+            assert( gc::is_locked());
             assert( nVersion != node_type::unlinked );
 
             struct stack_record
@@ -1237,7 +1237,7 @@ namespace cds { namespace container {
         template <typename K, typename Compare, typename Func>
         int try_remove( K const& key, Compare cmp, Func func, node_type * pParent, node_type * pNode, version_type nVersion, rcu_disposer& disp )
         {
-            assert( gc::is_locked() );
+            assert( gc::is_locked());
             assert( nVersion != node_type::unlinked );
 
             struct stack_record
@@ -1317,7 +1317,7 @@ namespace cds { namespace container {
         template <typename Func>
         int try_extract_minmax( int nDir, Func func, node_type * pParent, node_type * pNode, version_type nVersion, rcu_disposer& disp )
         {
-            assert( gc::is_locked() );
+            assert( gc::is_locked());
             assert( nVersion != node_type::unlinked );
 
             struct stack_record
@@ -1339,22 +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
-                        assert(pNode->is_valued( memory_model::memory_order_acquire ));
-                        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 );
@@ -1363,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
@@ -1468,7 +1482,7 @@ namespace cds { namespace container {
                     return update_flags::retry;
                 }
 
-                if ( pNode->is_valued( memory_model::memory_order_relaxed ) && !(nFlags & update_flags::allow_update) ) {
+                if ( pNode->is_valued( memory_model::memory_order_relaxed ) && !(nFlags & update_flags::allow_update)) {
                     m_stat.onInsertFailed();
                     return update_flags::failed;
                 }
@@ -1505,7 +1519,7 @@ namespace cds { namespace container {
             assert( pParent != nullptr );
             assert( pNode != nullptr );
 
-            if ( !pNode->is_valued( memory_model::memory_order_acquire ) )
+            if ( !pNode->is_valued( memory_model::memory_order_acquire ))
                 return update_flags::failed;
 
             if ( child( pNode, left_child, memory_model::memory_order_acquire ) == nullptr
@@ -1574,7 +1588,7 @@ namespace cds { namespace container {
         bool try_unlink_locked( node_type * pParent, node_type * pNode, rcu_disposer& disp )
         {
             // pParent and pNode must be locked
-            assert( !pParent->is_unlinked(memory_model::memory_order_relaxed) );
+            assert( !pParent->is_unlinked(memory_model::memory_order_relaxed));
 
             node_type * pParentLeft = child( pParent, left_child, memory_model::memory_order_relaxed );
             node_type * pParentRight = child( pParent, right_child, memory_model::memory_order_relaxed );
@@ -1666,7 +1680,7 @@ namespace cds { namespace container {
         {
             while ( pNode && parent( pNode, memory_model::memory_order_acquire )) {
                 int nCond = estimate_node_condition( pNode );
-                if ( nCond == nothing_required || pNode->is_unlinked( memory_model::memory_order_acquire ) )
+                if ( nCond == nothing_required || pNode->is_unlinked( memory_model::memory_order_acquire ))
                     return;
 
                 if ( nCond != unlink_required && nCond != rebalance_required )
@@ -1849,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 {
@@ -1864,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 );
@@ -1904,7 +1912,7 @@ namespace cds { namespace container {
             }
 
             // pLeft might also have routing node damage (if pLeft.left was null)
-            if ( hLL == 0 && !pLeft->is_valued(memory_model::memory_order_acquire) ) {
+            if ( hLL == 0 && !pLeft->is_valued(memory_model::memory_order_acquire)) {
                 m_stat.onDamageAfterRightRotation();
                 return pLeft;
             }
@@ -1925,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 {
@@ -1940,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 );
@@ -1956,7 +1958,7 @@ namespace cds { namespace container {
                 return pNode;
             }
 
-            if ( (pRLeft == nullptr || hL == 0) && !pNode->is_valued(memory_model::memory_order_relaxed) ) {
+            if ( (pRLeft == nullptr || hL == 0) && !pNode->is_valued(memory_model::memory_order_relaxed)) {
                 m_stat.onRemoveAfterLeftRotation();
                 return pNode;
             }
@@ -1967,7 +1969,7 @@ namespace cds { namespace container {
                 return pRight;
             }
 
-            if ( hRR == 0 && !pRight->is_valued(memory_model::memory_order_acquire) ) {
+            if ( hRR == 0 && !pRight->is_valued(memory_model::memory_order_acquire)) {
                 m_stat.onDamageAfterLeftRotation();
                 return pRight;
             }
@@ -2114,7 +2116,7 @@ namespace cds { namespace container {
                 return pNode;
             }
 
-            if ( (pRLL == nullptr || hL == 0) && !pNode->is_valued(memory_model::memory_order_relaxed) ) {
+            if ( (pRLL == nullptr || hL == 0) && !pNode->is_valued(memory_model::memory_order_relaxed)) {
                 m_stat.onRemoveAfterLRRotation();
                 return pNode;
             }
Unnamed repository; edit this file 'description' to name the repository.