SkipList: fixed erase() and find_fastpath() bugs

[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 42772bbb02c2483638a7ee90b421e1db06b9ed89..dbc3a272fedfa21ae47fdffca67c20c2c5aa12e7 100644 (file)
--- a/cds/intrusive/details/skip_list_base.h
+++ b/cds/intrusive/details/skip_list_base.h
@@ -70,6 +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<unsigned int> m_nUnlink; ///< How many levels has been unlinked
             //@endcond
 
         public:
@@ -77,6 +78,7 @@ namespace cds { namespace intrusive {
                 : m_pNext( nullptr )
                 , m_nHeight( 1 )
                 , m_arrNext( nullptr )
+                , m_nUnlink( 0 )
             {}
 
 
@@ -163,6 +165,11 @@ namespace cds { namespace intrusive {
                     && m_arrNext == nullptr
                     && m_nHeight <= 1;
             }
+
+            bool level_unlinked( unsigned nCount = 1 )
+            {
+                return m_nUnlink.fetch_add( nCount, std::memory_order_relaxed ) + 1 == height();
+            }
             //@endcond
         };
 
@@ -395,10 +402,13 @@ 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_nEraseWhileInsert     ; ///< Count of events "The node has been disposed 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_nFastEraseHelped      ; ///< Fast erase with helping of other thread
             event_counter   m_nFastExtract          ; ///< Fast extract event counter
+            event_counter   m_nFastExtractHelped    ; ///< Fast extract with helping of other thread
             event_counter   m_nSlowErase            ; ///< Slow erase event counter
             event_counter   m_nSlowExtract          ; ///< Slow extract event counter
             event_counter   m_nExtractSuccess       ; ///< Count of successful call of \p extract
@@ -412,6 +422,7 @@ 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_nMarkFailed           ; ///< Count of failed node marking (logical deletion mark)
 
             //@cond
             void onAddNode( unsigned int nHeight )
@@ -443,9 +454,12 @@ namespace cds { namespace intrusive {
             void onExtractWhileFind()       { ++m_nExtractWhileFind ; }
             void onRenewInsertPosition()    { ++m_nRenewInsertPosition; }
             void onLogicDeleteWhileInsert() { ++m_nLogicDeleteWhileInsert; }
+            void onEraseWhileInsert()       { ++m_nEraseWhileInsert;  }
             void onNotFoundWhileInsert()    { ++m_nNotFoundWhileInsert; }
             void onFastErase()              { ++m_nFastErase;         }
+            void onFastEraseHelped()        { ++m_nFastEraseHelped;   }
             void onFastExtract()            { ++m_nFastExtract;       }
+            void onFastExtractHelped()      { ++m_nFastExtractHelped; }
             void onSlowErase()              { ++m_nSlowErase;         }
             void onSlowExtract()            { ++m_nSlowExtract;       }
             void onExtractSuccess()         { ++m_nExtractSuccess;    }
@@ -457,6 +471,7 @@ namespace cds { namespace intrusive {
             void onExtractMaxSuccess()      { ++m_nExtractMaxSuccess; }
             void onExtractMaxFailed()       { ++m_nExtractMaxFailed;  }
             void onExtractMaxRetry()        { ++m_nExtractMaxRetries; }
+            void onMarkFailed()             { ++m_nMarkFailed;        }
             //@endcond
         };
 
@@ -483,9 +498,12 @@ namespace cds { namespace intrusive {
             void onExtractWhileFind()       const {}
             void onRenewInsertPosition()    const {}
             void onLogicDeleteWhileInsert() const {}
+            void onEraseWhileInsert()       const {}
             void onNotFoundWhileInsert()    const {}
             void onFastErase()              const {}
+            void onFastEraseHelped()        const {}
             void onFastExtract()            const {}
+            void onFastExtractHelped()      const {}
             void onSlowErase()              const {}
             void onSlowExtract()            const {}
             void onExtractSuccess()         const {}
@@ -497,6 +515,7 @@ namespace cds { namespace intrusive {
             void onExtractMaxSuccess()      const {}
             void onExtractMaxFailed()       const {}
             void onExtractMaxRetry()        const {}
+            void onMarkFailed()             const {}
             //@endcond
         };