On dev: SkipList: remove node state
authorkhizmax <libcds.dev@gmail.com>
Sat, 17 Dec 2016 08:27:51 +0000 (11:27 +0300)
committerkhizmax <libcds.dev@gmail.com>
Sat, 17 Dec 2016 08:27:51 +0000 (11:27 +0300)
1  2 
cds/intrusive/details/skip_list_base.h
cds/intrusive/impl/skip_list.h
test/include/cds_test/stat_skiplist_out.h

@@@ -63,11 -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 -75,7 +70,6 @@@
              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;
              //@endcond
  
          public:
@@@ -83,7 -83,7 +77,6 @@@
                  : m_pNext( nullptr )
                  , m_nHeight( 1 )
                  , m_arrNext( nullptr )
--                , m_state( clean )
              {}
  
  
                      && m_arrNext == nullptr
                      && m_nHeight <= 1;
              }
--
--            bool set_state( state& cur_state, state new_state, atomics::memory_order order )
--            {
--                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 );
--            }
              //@endcond
          };
  
              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
  
              //@cond
              void onAddNode( unsigned int nHeight )
              void onExtractMaxSuccess()      { ++m_nExtractMaxSuccess; }
              void onExtractMaxFailed()       { ++m_nExtractMaxFailed;  }
              void onExtractMaxRetry()        { ++m_nExtractMaxRetries; }
--            void onNodeHandOffFailed()      { ++m_nNodeHandOffFailed; }
--
              //@endcond
          };
  
              void onExtractMaxSuccess()      const {}
              void onExtractMaxFailed()       const {}
              void onExtractMaxRetry()        const {}
--            void onNodeHandOffFailed()      const {}
              //@endcond
          };
  
@@@ -394,8 -394,8 +394,7 @@@ namespace cds { namespace intrusive 
          // c_nMaxHeight * 2 - pPred/pSucc guards
          // + 1 - for erase, unlink
          // + 1 - for clear
--        // + 1 - for help_remove
--        static size_t const c_nHazardPtrCount = c_nMaxHeight * 2 + 3; ///< Count of hazard pointer required for the skip-list
++        static size_t const c_nHazardPtrCount = c_nMaxHeight * 2 + 2; ///< Count of hazard pointer required for the skip-list
  
      protected:
          typedef typename node_type::atomic_marked_ptr   atomic_node_ptr;   ///< Atomic marked node pointer
  
          void help_remove( int nLevel, node_type* pPred, marked_node_ptr pCur, marked_node_ptr pSucc )
          {
--            typename gc::Guard succ_guard;
--            marked_node_ptr succ = succ_guard.protect( pCur->next( nLevel ), gc_protect );
--
--            typename node_type::state state = node_type::clean;
--            if ( succ == pSucc && ( succ.ptr() == nullptr ||
--                succ.ptr()->set_state( state, node_type::hand_off, memory_model::memory_order_acquire )))
++            marked_node_ptr p( pCur.ptr() );
++            if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr()),
++                memory_model::memory_order_acquire, atomics::memory_order_relaxed ) )
              {
--                marked_node_ptr p( pCur.ptr() );
--                if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( succ.ptr()),
--                    memory_model::memory_order_acquire, atomics::memory_order_relaxed ) )
--                {
--                    if ( nLevel == 0 ) {
--                        gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
--                        m_Stat.onEraseWhileFind();
--                    }
++                if ( nLevel == 0 ) {
++                    gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
++                    m_Stat.onEraseWhileFind();
                  }
--
--                if ( succ.ptr() )
--                    succ.ptr()->clear_state( memory_model::memory_order_release );
              }
--            else if ( succ.ptr() != nullptr )
--                m_Stat.onNodeHandOffFailed();
          }
  
          template <typename Q, typename Compare >
              // Insert at level 0
              {
                  node_type* succ = pos.pSucc[0];
--                typename node_type::state state = node_type::clean;
--                if ( succ != nullptr && !succ->set_state( state, node_type::hand_off, memory_model::memory_order_acquire ) )
--                    return false;
  
                  marked_node_ptr p( succ );
                  pNode->next( 0 ).store( p, memory_model::memory_order_release );
--                if ( !pos.pPrev[0]->next( 0 ).compare_exchange_strong( p, marked_node_ptr( pNode ), memory_model::memory_order_release, atomics::memory_order_relaxed ) ) {
--                    if ( succ )
--                        succ->clear_state( memory_model::memory_order_release );
++                if ( !pos.pPrev[0]->next( 0 ).compare_exchange_strong( p, marked_node_ptr( pNode ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
                      return false;
--                }
  
--                if ( succ )
--                    succ->clear_state( memory_model::memory_order_release );
                  f( val );
              }
  
              for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
                  marked_node_ptr p;
                  while ( true ) {
--                    typename node_type::state state = node_type::clean;
--                    node_type* succ = pos.pSucc[nLevel];
--                    if ( succ == nullptr ||
--                        succ->set_state( state, node_type::hand_off, memory_model::memory_order_acquire ) ) 
--                    {
--                        marked_node_ptr q( succ );
--                        if ( !pNode->next( nLevel ).compare_exchange_strong( p, q, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
--                            // pNode has been marked as removed while we are inserting it
--                            // Stop inserting
--                            if ( succ )
--                                succ->clear_state( memory_model::memory_order_release );
--                            assert( p.bits() );
--                            m_Stat.onLogicDeleteWhileInsert();
--                            return true;
--                        }
++                    marked_node_ptr q( pos.pSucc[nLevel] );
  
--                        p = q;
--                        bool const result = pos.pPrev[nLevel]->next( nLevel ).compare_exchange_strong( q, marked_node_ptr( pNode ),
--                            memory_model::memory_order_release, atomics::memory_order_relaxed );
--                        if ( succ )
--                            succ->clear_state( memory_model::memory_order_release );
--                        if ( result )
--                            break;
++                    if ( !pNode->next( nLevel ).compare_exchange_strong( p, q, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
++                        // pNode has been marked as removed while we are inserting it
++                        // Stop inserting
++                        assert( p.bits() );
++                        m_Stat.onLogicDeleteWhileInsert();
++                        return true;
                      }
  
++                    p = q;
++                    bool const result = pos.pPrev[nLevel]->next( nLevel ).compare_exchange_strong( q, marked_node_ptr( pNode ),
++                        memory_model::memory_order_release, atomics::memory_order_relaxed );
++                    if ( result )
++                        break;
++
                      // Renew insert position
                      m_Stat.onRenewInsertPosition();
                      if ( !find_position( val, pos, key_comparator(), false ) ) {
          {
              assert( pDel != nullptr );
  
--            // set "removed" node state
--            {
--                back_off bkoff;
--                typename node_type::state state = node_type::clean;
--                while ( !( pDel->set_state( state, node_type::removed, memory_model::memory_order_release )
--                    || state == node_type::removed ))
--                {
--                    bkoff();
--                }
--            }
--
              marked_node_ptr pSucc;
  
              // logical deletion (marking)
@@@ -81,8 -81,8 +81,7 @@@ namespace cds_test 
              << CDSSTRESS_STAT_OUT( s, m_nFastExtract )
              << CDSSTRESS_STAT_OUT( s, m_nSlowExtract )
              << CDSSTRESS_STAT_OUT( s, m_nEraseWhileFind )
--            << CDSSTRESS_STAT_OUT( s, m_nExtractWhileFind )
--            << CDSSTRESS_STAT_OUT( s, m_nNodeHandOffFailed );
++            << CDSSTRESS_STAT_OUT( s, m_nExtractWhileFind );
      }
  
  } // namespace cds_test