SkipList: added a statistical measure

[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..97d30e3058646f675a19e1e31977fdc78bfbdb7c 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; ///< How many levels has been unlinked
             //@endcond
 
         public:
@@ -83,7 +78,7 @@ namespace cds { namespace intrusive {
                 : m_pNext( nullptr )
                 , m_nHeight( 1 )
                 , m_arrNext( nullptr )
-                , m_state( clean )
+                , m_nUnlink( 0 )
             {}
 
 
@@ -171,14 +166,9 @@ 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 );
-            }
-
-            void clear_state( atomics::memory_order order )
-            {
-                m_state.store( clean, order );
+                return m_nUnlink.fetch_add( nCount, std::memory_order_relaxed ) + 1 == height();
             }
             //@endcond
         };
@@ -412,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
@@ -429,7 +422,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 )
@@ -461,9 +455,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;    }
@@ -475,8 +472,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
         };
 
@@ -503,9 +500,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 {}
@@ -517,7 +517,8 @@ namespace cds { namespace intrusive {
             void onExtractMaxSuccess()      const {}
             void onExtractMaxFailed()       const {}
             void onExtractMaxRetry()        const {}
-            void onNodeHandOffFailed()      const {}
+            void onMarkFailed()             const {}
+            void onEraseContention()        const {}
             //@endcond
         };