SkipList: fixed memory leaks

[libcds.git] / cds / intrusive / details / skip_list_base.h

diff --git a/cds/intrusive/details/skip_list_base.h b/cds/intrusive/details/skip_list_base.h
index eccb765d2676d1965b3e74d2d2d7f4be70c7e53f..d304e5ecd2f08706ccfc700bbf94576c67d91710 100644 (file)
--- a/cds/intrusive/details/skip_list_base.h
+++ b/cds/intrusive/details/skip_list_base.h
@@ -63,11 +63,6 @@ namespace cds { namespace intrusive {
             //@cond
             typedef atomic_marked_ptr tower_item_type;
 
-            enum state {
-                clean,      // initial state
-                removed,    // final state
-                hand_off    // temp state
-            };
             //@endcond
 
         protected:
@@ -75,7 +70,7 @@ namespace cds { namespace intrusive {
             atomic_marked_ptr           m_pNext;     ///< Next item in bottom-list (list at level 0)
             unsigned int                m_nHeight;   ///< Node height (size of \p m_arrNext array). For node at level 0 the height is 1.
             atomic_marked_ptr *         m_arrNext;   ///< Array of next items for levels 1 .. m_nHeight - 1. For node at level 0 \p m_arrNext is \p nullptr
-            atomics::atomic< state >    m_state;
+            atomics::atomic<unsigned int> m_nUnlink; ///< Unlink helper
             //@endcond
 
         public:
@@ -83,7 +78,7 @@ namespace cds { namespace intrusive {
                 : m_pNext( nullptr )
                 , m_nHeight( 1 )
                 , m_arrNext( nullptr )
-                , m_state( clean )
+                , m_nUnlink( 1 )
             {}
 
 
@@ -97,7 +92,7 @@ namespace cds { namespace intrusive {
 
                 m_arrNext = nextTower;
                 m_nHeight = nHeight;
-                atomics::atomic_thread_fence( atomics::memory_order_release );
+                m_nUnlink.store( nHeight, atomics::memory_order_relaxed );
             }
 
             //@cond
@@ -171,14 +166,14 @@ namespace cds { namespace intrusive {
                     && m_nHeight <= 1;
             }
 
-            bool set_state( state& cur_state, state new_state, atomics::memory_order order )
+            bool level_unlinked( unsigned nCount = 1 )
             {
-                return m_state.compare_exchange_strong( cur_state, new_state, order, atomics::memory_order_relaxed );
+                return m_nUnlink.fetch_sub( nCount, atomics::memory_order_relaxed ) == 1;
             }
 
-            void clear_state( atomics::memory_order order )
+            bool is_upper_level( unsigned nLevel ) const
             {
-                m_state.store( clean, order );
+                return m_nUnlink.load( atomics::memory_order_relaxed ) == nLevel + 1;
             }
             //@endcond
         };
@@ -412,7 +407,7 @@ namespace cds { namespace intrusive {
             event_counter   m_nFindSlowSuccess      ; ///< Count of successful call of \p find and all derivatives (via slow-path)
             event_counter   m_nFindSlowFailed       ; ///< Count of failed call of \p find and all derivatives (via slow-path)
             event_counter   m_nRenewInsertPosition  ; ///< Count of renewing position events while inserting
-            event_counter   m_nLogicDeleteWhileInsert   ;   ///< Count of events "The node has been logically deleted while inserting"
+            event_counter   m_nLogicDeleteWhileInsert; ///< Count of events "The node has been logically deleted while inserting"
             event_counter   m_nNotFoundWhileInsert  ; ///< Count of events "Inserting node is not found"
             event_counter   m_nFastErase            ; ///< Fast erase event counter
             event_counter   m_nFastExtract          ; ///< Fast extract event counter
@@ -429,7 +424,8 @@ namespace cds { namespace intrusive {
             event_counter   m_nExtractMaxRetries    ; ///< Count of retries of \p extract_max call
             event_counter   m_nEraseWhileFind       ; ///< Count of erased item while searching
             event_counter   m_nExtractWhileFind     ; ///< Count of extracted item while searching (RCU only)
-            event_counter   m_nNodeHandOffFailed    ; ///< Cannot set "hand-off" node state
+            event_counter   m_nMarkFailed           ; ///< Count of failed node marking (logical deletion mark)
+            event_counter   m_nEraseContention      ; ///< Count of key erasing contention encountered
 
             //@cond
             void onAddNode( unsigned int nHeight )
@@ -475,8 +471,8 @@ namespace cds { namespace intrusive {
             void onExtractMaxSuccess()      { ++m_nExtractMaxSuccess; }
             void onExtractMaxFailed()       { ++m_nExtractMaxFailed;  }
             void onExtractMaxRetry()        { ++m_nExtractMaxRetries; }
-            void onNodeHandOffFailed()      { ++m_nNodeHandOffFailed; }
-
+            void onMarkFailed()             { ++m_nMarkFailed;        }
+            void onEraseContention()        { ++m_nEraseContention;   }
             //@endcond
         };
 
@@ -517,7 +513,8 @@ namespace cds { namespace intrusive {
             void onExtractMaxSuccess()      const {}
             void onExtractMaxFailed()       const {}
             void onExtractMaxRetry()        const {}
-            void onNodeHandOffFailed()      const {}
+            void onMarkFailed()             const {}
+            void onEraseContention()        const {}
             //@endcond
         };