Reformatted SkipList, added memory barrier after tower initialization
authorkhizmax <libcds.dev@gmail.com>
Sat, 19 Nov 2016 17:01:02 +0000 (20:01 +0300)
committerkhizmax <libcds.dev@gmail.com>
Sat, 19 Nov 2016 17:01:02 +0000 (20:01 +0300)
cds/container/details/make_skip_list_map.h
cds/container/details/make_skip_list_set.h
cds/intrusive/details/skip_list_base.h
cds/intrusive/impl/skip_list.h

index cc34b39..8e456fe 100644 (file)
@@ -83,8 +83,11 @@ namespace cds { namespace container { namespace details {
             void init_tower( unsigned int nHeight, atomic_marked_ptr * pTower )
             {
                 if ( nHeight > 1 ) {
+                    // TSan: make_tower() issues atomic_thread_fence( release )
+                    CDS_TSAN_ANNOTATE_IGNORE_WRITES_BEGIN;
                     new (pTower) atomic_marked_ptr[ nHeight - 1 ];
                     base_class::make_tower( nHeight, pTower );
+                    CDS_TSAN_ANNOTATE_IGNORE_WRITES_END;
                 }
             }
         };
index d65cd13..e63bbe8 100644 (file)
@@ -59,8 +59,11 @@ namespace cds { namespace container { namespace details {
                 : m_Value(v)
             {
                 if ( nHeight > 1 ) {
+                    // TSan: make_tower() issues atomic_thread_fence( release )
+                    CDS_TSAN_ANNOTATE_IGNORE_WRITES_BEGIN;
                     new (pTower) atomic_marked_ptr[ nHeight - 1 ];
                     base_class::make_tower( nHeight, pTower );
+                    CDS_TSAN_ANNOTATE_IGNORE_WRITES_END;
                 }
             }
 
index a3c0ea2..00ddad2 100644 (file)
@@ -87,6 +87,7 @@ namespace cds { namespace intrusive {
 
                 m_arrNext = nextTower;
                 m_nHeight = nHeight;
+                atomics::atomic_thread_fence( atomics::memory_order_release );
             }
 
             //@cond
@@ -102,6 +103,11 @@ namespace cds { namespace intrusive {
             {
                 return m_arrNext;
             }
+
+            bool has_tower() const
+            {
+                return m_nHeight > 1;
+            }
             //@endcond
 
             /// Access to element of next pointer array
@@ -110,15 +116,7 @@ namespace cds { namespace intrusive {
                 assert( nLevel < height());
                 assert( nLevel == 0 || (nLevel > 0 && m_arrNext != nullptr));
 
-#           ifdef CDS_THREAD_SANITIZER_ENABLED
-                // TSan false positive: m_arrNext is read-only array
-                CDS_TSAN_ANNOTATE_IGNORE_READS_BEGIN;
-                atomic_marked_ptr& r = nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
-                CDS_TSAN_ANNOTATE_IGNORE_READS_END;
-                return r;
-#           else
                 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
-#           endif
             }
 
             /// Access to element of next pointer array (const version)
@@ -127,24 +125,16 @@ namespace cds { namespace intrusive {
                 assert( nLevel < height());
                 assert( nLevel == 0 || nLevel > 0 && m_arrNext != nullptr );
 
-#           ifdef CDS_THREAD_SANITIZER_ENABLED
-                // TSan false positive: m_arrNext is read-only array
-                CDS_TSAN_ANNOTATE_IGNORE_READS_BEGIN;
-                atomic_marked_ptr const& r = nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
-                CDS_TSAN_ANNOTATE_IGNORE_READS_END;
-                return r;
-#           else
                 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
-#           endif
             }
 
-            /// Access to element of next pointer array (same as \ref next function)
+            /// Access to element of next pointer array (synonym for \p next() function)
             atomic_marked_ptr& operator[]( unsigned int nLevel )
             {
                 return next( nLevel );
             }
 
-            /// Access to element of next pointer array (same as \ref next function)
+            /// Access to element of next pointer array (synonym for \p next() function)
             atomic_marked_ptr const& operator[]( unsigned int nLevel ) const
             {
                 return next( nLevel );
index 27023f4..4f7d1ea 100644 (file)
@@ -417,1256 +417,1257 @@ namespace cds { namespace intrusive {
             node_type *   pSucc[ c_nMaxHeight ];
 
             typename gc::template GuardArray< c_nMaxHeight * 2 > guards;   ///< Guards array for pPrev/pSucc
-            node_type *   pCur;   // guarded by guards; needed only for \p update()
+            node_type *   pCur;   // guarded by one of guards
         };
         //@endcond
 
-    protected:
-        skip_list::details::head_node< node_type > m_Head;   ///< head tower (max height)
+    public:
+        /// Default constructor
+        /**
+            The constructor checks whether the count of guards is enough
+            for skip-list and may raise an exception if not.
+        */
+        SkipListSet()
+            : m_Head( c_nMaxHeight )
+            , m_nHeight( c_nMinHeight )
+        {
+            static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
 
-        item_counter                m_ItemCounter;    ///< item counter
-        random_level_generator      m_RandomLevelGen; ///< random level generator instance
-        atomics::atomic<unsigned int> m_nHeight;      ///< estimated high level
-        mutable stat                m_Stat;           ///< internal statistics
+            gc::check_available_guards( c_nHazardPtrCount );
 
-    protected:
-        //@cond
-        unsigned int random_level()
-        {
-            // Random generator produces a number from range [0..31]
-            // We need a number from range [1..32]
-            return m_RandomLevelGen() + 1;
+            // Barrier for head node
+            atomics::atomic_thread_fence( memory_model::memory_order_release );
         }
 
-        template <typename Q>
-        node_type * build_node( Q v )
+        /// Clears and destructs the skip-list
+        ~SkipListSet()
         {
-            return node_builder::make_tower( v, m_RandomLevelGen );
+            clear();
         }
 
-        static value_type * gc_protect( marked_node_ptr p )
-        {
-            return node_traits::to_value_ptr( p.ptr());
-        }
+    public:
+    ///@name Forward iterators (only for debugging purpose)
+    //@{
+        /// Iterator type
+        /**
+            The forward iterator has some features:
+            - it has no post-increment operator
+            - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
+              For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
+              may be thrown if the limit of guard count per thread is exceeded.
+            - The iterator cannot be moved across thread boundary because it contains thread-private GC's guard.
+            - Iterator ensures thread-safety even if you delete the item the iterator points to. However, in case of concurrent
+              deleting operations there is no guarantee that you iterate all item in the list.
+              Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
 
-        static void dispose_node( value_type * pVal )
-        {
-            assert( pVal != nullptr );
-            typename node_builder::node_disposer()( node_traits::to_node_ptr(pVal));
-            disposer()( pVal );
-        }
+            @warning Use this iterator on the concurrent container for debugging purpose only.
 
-        template <typename Q, typename Compare >
-        bool find_position( Q const& val, position& pos, Compare cmp, bool bStopIfFound )
-        {
-            node_type * pPred;
-            marked_node_ptr pSucc;
-            marked_node_ptr pCur;
+            The iterator interface:
+            \code
+            class iterator {
+            public:
+                // Default constructor
+                iterator();
 
-            // Hazard pointer array:
-            //  pPred: [nLevel * 2]
-            //  pSucc: [nLevel * 2 + 1]
+                // Copy construtor
+                iterator( iterator const& src );
 
-        retry:
-            pPred = m_Head.head();
-            int nCmp = 1;
+                // Dereference operator
+                value_type * operator ->() const;
 
-            for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
-                pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
-                while ( true ) {
-                    pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
-                    if ( pCur.bits()) {
-                        // pCur.bits() means that pPred is logically deleted
-                        goto retry;
-                    }
+                // Dereference operator
+                value_type& operator *() const;
 
-                    if ( pCur.ptr() == nullptr ) {
-                        // end of the list at level nLevel - goto next level
-                        break;
-                    }
+                // Preincrement operator
+                iterator& operator ++();
 
-                    // pSucc contains deletion mark for pCur
-                    pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
+                // Assignment operator
+                iterator& operator = (iterator const& src);
 
-                    if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr())
-                        goto retry;
+                // Equality operators
+                bool operator ==(iterator const& i ) const;
+                bool operator !=(iterator const& i ) const;
+            };
+            \endcode
+        */
+        typedef skip_list::details::iterator< gc, node_traits, back_off, false >  iterator;
 
-                    if ( pSucc.bits()) {
-                        // pCur is marked, i.e. logically deleted.
-                        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 ))
-                        {
-                            if ( nLevel == 0 ) {
-                                gc::retire( node_traits::to_value_ptr( pCur.ptr()), dispose_node );
-                                m_Stat.onEraseWhileFind();
-                            }
-                        }
-                        goto retry;
-                    }
-                    else {
-                        nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
-                        if ( nCmp < 0 ) {
-                            pPred = pCur.ptr();
-                            pos.guards.copy( nLevel * 2, nLevel * 2 + 1 ) ;   // pPrev guard := cur guard
-                        }
-                        else if ( nCmp == 0 && bStopIfFound )
-                            goto found;
-                        else
-                            break;
-                    }
-                }
+        /// Const iterator type
+        typedef skip_list::details::iterator< gc, node_traits, back_off, true >   const_iterator;
 
-                // Next level
-                pos.pPrev[ nLevel ] = pPred;
-                pos.pSucc[ nLevel ] = pCur.ptr();
-            }
+        /// Returns a forward iterator addressing the first element in a set
+        iterator begin()
+        {
+            return iterator( *m_Head.head());
+        }
 
-            if ( nCmp != 0 )
-                return false;
+        /// Returns a forward const iterator addressing the first element in a set
+        const_iterator begin() const
+        {
+            return const_iterator( *m_Head.head());
+        }
+        /// Returns a forward const iterator addressing the first element in a set
+        const_iterator cbegin() const
+        {
+            return const_iterator( *m_Head.head());
+        }
 
-        found:
-            pos.pCur = pCur.ptr();
-            return pCur.ptr() && nCmp == 0;
+        /// Returns a forward iterator that addresses the location succeeding the last element in a set.
+        iterator end()
+        {
+            return iterator();
         }
 
-        bool find_min_position( position& pos )
+        /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
+        const_iterator end() const
         {
-            node_type * pPred;
-            marked_node_ptr pSucc;
-            marked_node_ptr pCur;
+            return const_iterator();
+        }
+        /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
+        const_iterator cend() const
+        {
+            return const_iterator();
+        }
+    //@}
 
-            // Hazard pointer array:
-            //  pPred: [nLevel * 2]
-            //  pSucc: [nLevel * 2 + 1]
+    public:
+        /// Inserts new node
+        /**
+            The function inserts \p val in the set if it does not contain
+            an item with key equal to \p val.
 
-        retry:
-            pPred = m_Head.head();
+            Returns \p true if \p val is placed into the set, \p false otherwise.
+        */
+        bool insert( value_type& val )
+        {
+            return insert( val, []( value_type& ) {} );
+        }
 
-            for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
-                pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
-                pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
+        /// Inserts new node
+        /**
+            This function is intended for derived non-intrusive containers.
 
-                // pCur.bits() means that pPred is logically deleted
-                // head cannot be deleted
-                assert( pCur.bits() == 0 );
+            The function allows to split creating of new item into two part:
+            - create item with key only
+            - insert new item into the set
+            - if inserting is success, calls  \p f functor to initialize value-field of \p val.
 
-                if ( pCur.ptr()) {
+            The functor signature is:
+            \code
+                void func( value_type& val );
+            \endcode
+            where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
+            \p val no any other changes could be made on this set's item by concurrent threads.
+            The user-defined functor is called only if the inserting is success.
+        */
+        template <typename Func>
+        bool insert( value_type& val, Func f )
+        {
+            typename gc::Guard gNew;
+            gNew.assign( &val );
 
-                    // pSucc contains deletion mark for pCur
-                    pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
+            node_type * pNode = node_traits::to_node_ptr( val );
+            scoped_node_ptr scp( pNode );
+            unsigned int nHeight = pNode->height();
+            bool bTowerOk = pNode->has_tower(); // nHeight > 1 && pNode->get_tower() != nullptr;
+            bool bTowerMade = false;
 
-                    if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr())
-                        goto retry;
+            position pos;
+            while ( true )
+            {
+                if ( find_position( val, pos, key_comparator(), true )) {
+                    // scoped_node_ptr deletes the node tower if we create it
+                    if ( !bTowerMade )
+                        scp.release();
 
-                    if ( pSucc.bits()) {
-                        // pCur is marked, i.e. logically deleted.
-                        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 ))
-                        {
-                            if ( nLevel == 0 ) {
-                                gc::retire( node_traits::to_value_ptr( pCur.ptr()), dispose_node );
-                                m_Stat.onEraseWhileFind();
-                            }
-                        }
-                        goto retry;
-                    }
+                    m_Stat.onInsertFailed();
+                    return false;
                 }
 
-                // Next level
-                pos.pPrev[ nLevel ] = pPred;
-                pos.pSucc[ nLevel ] = pCur.ptr();
-            }
+                if ( !bTowerOk ) {
+                    build_node( pNode );
+                    nHeight = pNode->height();
+                    bTowerMade = pNode->has_tower();
+                    bTowerOk = true;
+                }
+
+                if ( !insert_at_position( val, pNode, pos, f )) {
+                    m_Stat.onInsertRetry();
+                    continue;
+                }
 
-            return (pos.pCur = pCur.ptr()) != nullptr;
+                increase_height( nHeight );
+                ++m_ItemCounter;
+                m_Stat.onAddNode( nHeight );
+                m_Stat.onInsertSuccess();
+                scp.release();
+                return true;
+            }
         }
 
-        bool find_max_position( position& pos )
-        {
-            node_type * pPred;
-            marked_node_ptr pSucc;
-            marked_node_ptr pCur;
+        /// Updates the node
+        /**
+            The operation performs inserting or changing data with lock-free manner.
 
-            // Hazard pointer array:
-            //  pPred: [nLevel * 2]
-            //  pSucc: [nLevel * 2 + 1]
+            If the item \p val is not found in the set, then \p val is inserted into the set
+            iff \p bInsert is \p true.
+            Otherwise, the functor \p func is called with item found.
+            The functor \p func signature is:
+            \code
+                void func( bool bNew, value_type& item, value_type& val );
+            \endcode
+            with arguments:
+            - \p bNew - \p true if the item has been inserted, \p false otherwise
+            - \p item - item of the set
+            - \p val - argument \p val passed into the \p %update() function
+            If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
+            refer to the same thing.
 
-        retry:
-            pPred = m_Head.head();
+            Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
+            i.e. the node has been inserted or updated,
+            \p second is \p true if new item has been added or \p false if the item with \p key
+            already exists.
 
-            for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
-                pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
-                while ( true ) {
-                    pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
-                    if ( pCur.bits()) {
-                        // pCur.bits() means that pPred is logically deleted
-                        goto retry;
-                    }
+            @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
+        */
+        template <typename Func>
+        std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
+        {
+            typename gc::Guard gNew;
+            gNew.assign( &val );
 
-                    if ( pCur.ptr() == nullptr ) {
-                        // end of the list at level nLevel - goto next level
-                        break;
-                    }
+            node_type * pNode = node_traits::to_node_ptr( val );
+            scoped_node_ptr scp( pNode );
+            unsigned int nHeight = pNode->height();
+            bool bTowerOk = pNode->has_tower(); // nHeight > 1 && pNode->get_tower() != nullptr;
+            bool bTowerMade = false;
 
-                    // pSucc contains deletion mark for pCur
-                    pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
+            position pos;
+            while ( true )
+            {
+                bool bFound = find_position( val, pos, key_comparator(), true );
+                if ( bFound ) {
+                    // scoped_node_ptr deletes the node tower if we create it before
+                    if ( !bTowerMade )
+                        scp.release();
 
-                    if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr())
-                        goto retry;
+                    func( false, *node_traits::to_value_ptr(pos.pCur), val );
+                    m_Stat.onUpdateExist();
+                    return std::make_pair( true, false );
+                }
 
-                    if ( pSucc.bits()) {
-                        // pCur is marked, i.e. logically deleted.
-                        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 ))
-                        {
-                            if ( nLevel == 0 ) {
-                                gc::retire( node_traits::to_value_ptr( pCur.ptr()), dispose_node );
-                                m_Stat.onEraseWhileFind();
-                            }
-                        }
-                        goto retry;
-                    }
-                    else {
-                        if ( !pSucc.ptr())
-                            break;
+                if ( !bInsert ) {
+                    scp.release();
+                    return std::make_pair( false, false );
+                }
 
-                        pPred = pCur.ptr();
-                        pos.guards.copy( nLevel * 2, nLevel * 2 + 1 ); // pPrev guard := cur guard
-                        //pos.guards.copy( nLevel * 2, gCur ) ;   // pPrev guard := gCur
-                    }
+                if ( !bTowerOk ) {
+                    build_node( pNode );
+                    nHeight = pNode->height();
+                    bTowerMade = pNode->has_tower();
+                    bTowerOk = true;
                 }
 
-                // Next level
-                pos.pPrev[ nLevel ] = pPred;
-                pos.pSucc[ nLevel ] = pCur.ptr();
-            }
+                if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { func( true, item, item ); })) {
+                    m_Stat.onInsertRetry();
+                    continue;
+                }
 
-            return (pos.pCur = pCur.ptr()) != nullptr;
+                increase_height( nHeight );
+                ++m_ItemCounter;
+                scp.release();
+                m_Stat.onAddNode( nHeight );
+                m_Stat.onUpdateNew();
+                return std::make_pair( true, true );
+            }
         }
-
+        //@cond
         template <typename Func>
-        bool insert_at_position( value_type& val, node_type * pNode, position& pos, Func f )
+        CDS_DEPRECATED("ensure() is deprecated, use update()")
+        std::pair<bool, bool> ensure( value_type& val, Func func )
         {
-            unsigned int nHeight = pNode->height();
+            return update( val, func, true );
+        }
+        //@endcond
 
-            for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel )
-                pNode->next(nLevel).store( marked_node_ptr(), memory_model::memory_order_relaxed );
+        /// Unlinks the item \p val from the set
+        /**
+            The function searches the item \p val in the set and unlink it from the set
+            if it is found and is equal to \p val.
 
-            // Insert at level 0
-            {
-                marked_node_ptr p( pos.pSucc[0] );
-                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 ))
-                    return false;
+            Difference between \p erase() and \p %unlink() functions: \p %erase() finds <i>a key</i>
+            and deletes the item found. \p %unlink() finds an item by key and deletes it
+            only if \p val is an item of that set, i.e. the pointer to item found
+            is equal to <tt> &val </tt>.
 
-                f( val );
-            }
+            The \p disposer specified in \p Traits class template parameter is called
+            by garbage collector \p GC asynchronously.
 
-            // Insert at level 1..max
-            for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
-                marked_node_ptr p;
-                while ( true ) {
-                    marked_node_ptr q( pos.pSucc[ nLevel ]);
-                    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;
-                    if ( pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( q, marked_node_ptr( pNode ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
-                        break;
+            The function returns \p true if success and \p false otherwise.
+        */
+        bool unlink( value_type& val )
+        {
+            position pos;
 
-                    // Renew insert position
-                    m_Stat.onRenewInsertPosition();
-                    if ( !find_position( val, pos, key_comparator(), false )) {
-                        // The node has been deleted while we are inserting it
-                        m_Stat.onNotFoundWhileInsert();
-                        return true;
-                    }
-                }
+            if ( !find_position( val, pos, key_comparator(), false )) {
+                m_Stat.onUnlinkFailed();
+                return false;
             }
-            return true;
-        }
 
-        template <typename Func>
-        bool try_remove_at( node_type * pDel, position& pos, Func f )
-        {
-            assert( pDel != nullptr );
+            node_type * pDel = pos.pCur;
+            assert( key_comparator()( *node_traits::to_value_ptr( pDel ), val ) == 0 );
 
-            marked_node_ptr pSucc;
+            unsigned int nHeight = pDel->height();
+            typename gc::Guard gDel;
+            gDel.assign( node_traits::to_value_ptr(pDel));
 
-            // logical deletion (marking)
-            for ( unsigned int nLevel = pDel->height() - 1; nLevel > 0; --nLevel ) {
-                while ( true ) {
-                    pSucc = pDel->next(nLevel);
-                    if ( pSucc.bits() || pDel->next(nLevel).compare_exchange_weak( pSucc, pSucc | 1,
-                         memory_model::memory_order_release, atomics::memory_order_relaxed ))
-                    {
-                        break;
-                    }
-                }
+            if ( node_traits::to_value_ptr( pDel ) == &val && try_remove_at( pDel, pos, [](value_type const&) {} )) {
+                --m_ItemCounter;
+                m_Stat.onRemoveNode( nHeight );
+                m_Stat.onUnlinkSuccess();
+                return true;
             }
 
-            while ( true ) {
-                marked_node_ptr p( pDel->next(0).load(memory_model::memory_order_relaxed).ptr());
-                if ( pDel->next(0).compare_exchange_strong( p, p | 1, memory_model::memory_order_release, atomics::memory_order_relaxed ))
-                {
-                    f( *node_traits::to_value_ptr( pDel ));
+            m_Stat.onUnlinkFailed();
+            return false;
+        }
 
-                    // Physical deletion
-                    // try fast erase
-                    p = pDel;
-                    for ( int nLevel = static_cast<int>( pDel->height() - 1 ); nLevel >= 0; --nLevel ) {
-                        pSucc = pDel->next(nLevel).load(memory_model::memory_order_relaxed);
-                        if ( !pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( p, marked_node_ptr(pSucc.ptr()),
-                            memory_model::memory_order_acquire, atomics::memory_order_relaxed))
-                        {
-                            // Make slow erase
-                            find_position( *node_traits::to_value_ptr( pDel ), pos, key_comparator(), false );
-                            m_Stat.onSlowErase();
-                            return true;
-                        }
-                    }
+        /// Extracts the item from the set with specified \p key
+        /** \anchor cds_intrusive_SkipListSet_hp_extract
+            The function searches an item with key equal to \p key in the set,
+            unlinks it from the set, and returns it as \p guarded_ptr object.
+            If \p key is not found the function returns an empty guarded pointer.
 
-                    // Fast erasing success
-                    gc::retire( node_traits::to_value_ptr( pDel ), dispose_node );
-                    m_Stat.onFastErase();
-                    return true;
-                }
-                else {
-                    if ( p.bits()) {
-                        // Another thread is deleting pDel right now
-                        return false;
-                    }
+            Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
+
+            The \p disposer specified in \p Traits class template parameter is called automatically
+            by garbage collector \p GC specified in class' template parameters when returned \p guarded_ptr object
+            will be destroyed or released.
+            @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
+
+            Usage:
+            \code
+            typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
+            skip_list theList;
+            // ...
+            {
+                skip_list::guarded_ptr gp(theList.extract( 5 ));
+                if ( gp ) {
+                    // Deal with gp
+                    // ...
                 }
-                m_Stat.onEraseRetry();
+                // Destructor of gp releases internal HP guard
             }
+            \endcode
+        */
+        template <typename Q>
+        guarded_ptr extract( Q const& key )
+        {
+            return extract_( key, key_comparator());
         }
 
-        enum finsd_fastpath_result {
-            find_fastpath_found,
-            find_fastpath_not_found,
-            find_fastpath_abort
-        };
-        template <typename Q, typename Compare, typename Func>
-        finsd_fastpath_result find_fastpath( Q& val, Compare cmp, Func f )
-        {
-            node_type * pPred;
-            typename gc::template GuardArray<2>  guards;
-            marked_node_ptr pCur;
-            marked_node_ptr pNull;
+        /// Extracts the item from the set with comparing functor \p pred
+        /**
+            The function is an analog of \ref cds_intrusive_SkipListSet_hp_extract "extract(Q const&)"
+            but \p pred predicate is used for key comparing.
 
-            back_off bkoff;
+            \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
+            in any order.
+            \p pred must imply the same element order as the comparator used for building the set.
+        */
+        template <typename Q, typename Less>
+        guarded_ptr extract_with( Q const& key, Less pred )
+        {
+            CDS_UNUSED( pred );
+            return extract_( key, cds::opt::details::make_comparator_from_less<Less>());
+        }
 
-            pPred = m_Head.head();
-            for ( int nLevel = static_cast<int>( m_nHeight.load(memory_model::memory_order_relaxed) - 1 ); nLevel >= 0; --nLevel ) {
-                pCur = guards.protect( 1, pPred->next(nLevel), gc_protect );
-                if ( pCur == pNull )
-                    continue;
+        /// Extracts an item with minimal key from the list
+        /**
+            The function searches an item with minimal key, unlinks it, and returns it as \p guarded_ptr object.
+            If the skip-list is empty the function returns an empty guarded pointer.
 
-                while ( pCur != pNull ) {
-                    if ( pCur.bits()) {
-                        unsigned int nAttempt = 0;
-                        while ( pCur.bits() && nAttempt++ < 16 ) {
-                            bkoff();
-                            pCur = guards.protect( 1, pPred->next(nLevel), gc_protect );
-                        }
-                        bkoff.reset();
+            @note Due the concurrent nature of the list, the function extracts <i>nearly</i> minimum key.
+            It means that the function gets leftmost item and tries to unlink it.
+            During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
+            So, the function returns the item with minimum key at the moment of list traversing.
 
-                        if ( pCur.bits()) {
-                            // Maybe, we are on deleted node sequence
-                            // Abort searching, try slow-path
-                            return find_fastpath_abort;
-                        }
-                    }
+            The \p disposer specified in \p Traits class template parameter is called
+            by garbage collector \p GC automatically when returned \p guarded_ptr object
+            will be destroyed or released.
+            @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 
-                    if ( pCur.ptr()) {
-                        int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
-                        if ( nCmp < 0 ) {
-                            guards.copy( 0, 1 );
-                            pPred = pCur.ptr();
-                            pCur = guards.protect( 1, pCur->next(nLevel), gc_protect );
-                        }
-                        else if ( nCmp == 0 ) {
-                            // found
-                            f( *node_traits::to_value_ptr( pCur.ptr()), val );
-                            return find_fastpath_found;
-                        }
-                        else // pCur > val - go down
-                            break;
-                    }
+            Usage:
+            \code
+            typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
+            skip_list theList;
+            // ...
+            {
+                skip_list::guarded_ptr gp(theList.extract_min());
+                if ( gp ) {
+                    // Deal with gp
+                    //...
                 }
+                // Destructor of gp releases internal HP guard
             }
-
-            return find_fastpath_not_found;
-        }
-
-        template <typename Q, typename Compare, typename Func>
-        bool find_slowpath( Q& val, Compare cmp, Func f )
+            \endcode
+        */
+        guarded_ptr extract_min()
         {
-            position pos;
-            if ( find_position( val, pos, cmp, true )) {
-                assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
-
-                f( *node_traits::to_value_ptr( pos.pCur ), val );
-                return true;
-            }
-            else
-                return false;
+            return extract_min_();
         }
 
-        template <typename Q, typename Compare, typename Func>
-        bool find_with_( Q& val, Compare cmp, Func f )
-        {
-            switch ( find_fastpath( val, cmp, f )) {
-            case find_fastpath_found:
-                m_Stat.onFindFastSuccess();
-                return true;
-            case find_fastpath_not_found:
-                m_Stat.onFindFastFailed();
-                return false;
-            default:
-                break;
-            }
+        /// Extracts an item with maximal key from the list
+        /**
+            The function searches an item with maximal key, unlinks it, and returns the pointer to item
+            as \p guarded_ptr object.
+            If the skip-list is empty the function returns an empty \p guarded_ptr.
 
-            if ( find_slowpath( val, cmp, f )) {
-                m_Stat.onFindSlowSuccess();
-                return true;
-            }
+            @note Due the concurrent nature of the list, the function extracts <i>nearly</i> maximal key.
+            It means that the function gets rightmost item and tries to unlink it.
+            During unlinking, a concurrent thread may insert an item with key greater than rightmost item's key.
+            So, the function returns the item with maximum key at the moment of list traversing.
 
-            m_Stat.onFindSlowFailed();
-            return false;
-        }
+            The \p disposer specified in \p Traits class template parameter is called
+            by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
+            will be destroyed or released.
+            @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 
-        template <typename Q, typename Compare>
-        guarded_ptr get_with_( Q const& val, Compare cmp )
+            Usage:
+            \code
+            typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
+            skip_list theList;
+            // ...
+            {
+                skip_list::guarded_ptr gp( theList.extract_max( gp ));
+                if ( gp ) {
+                    // Deal with gp
+                    //...
+                }
+                // Destructor of gp releases internal HP guard
+            }
+            \endcode
+        */
+        guarded_ptr extract_max()
         {
-            guarded_ptr gp;
-            if ( find_with_( val, cmp, [&gp](value_type& found, Q const& ) { gp.reset(&found); } ))
-                return gp;
-            return guarded_ptr();
+            return extract_max_();
         }
 
-        template <typename Q, typename Compare, typename Func>
-        bool erase_( Q const& val, Compare cmp, Func f )
-        {
-            position pos;
-
-            if ( !find_position( val, pos, cmp, false )) {
-                m_Stat.onEraseFailed();
-                return false;
-            }
+        /// Deletes the item from the set
+        /** \anchor cds_intrusive_SkipListSet_hp_erase
+            The function searches an item with key equal to \p key in the set,
+            unlinks it from the set, and returns \p true.
+            If the item with key equal to \p key is not found the function return \p false.
 
-            node_type * pDel = pos.pCur;
-            typename gc::Guard gDel;
-            gDel.assign( node_traits::to_value_ptr(pDel));
-            assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
+            Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
+        */
+        template <typename Q>
+        bool erase( Q const& key )
+        {
+            return erase_( key, key_comparator(), [](value_type const&) {} );
+        }
 
-            unsigned int nHeight = pDel->height();
-            if ( try_remove_at( pDel, pos, f )) {
-                --m_ItemCounter;
-                m_Stat.onRemoveNode( nHeight );
-                m_Stat.onEraseSuccess();
-                return true;
-            }
+        /// Deletes the item from the set with comparing functor \p pred
+        /**
+            The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase "erase(Q const&)"
+            but \p pred predicate is used for key comparing.
 
-            m_Stat.onEraseFailed();
-            return false;
+            \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
+            in any order.
+            \p pred must imply the same element order as the comparator used for building the set.
+        */
+        template <typename Q, typename Less>
+        bool erase_with( Q const& key, Less pred )
+        {
+            CDS_UNUSED( pred );
+            return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type const&) {} );
         }
 
-        template <typename Q, typename Compare>
-        guarded_ptr extract_( Q const& val, Compare cmp )
-        {
-            position pos;
+        /// Deletes the item from the set
+        /** \anchor cds_intrusive_SkipListSet_hp_erase_func
+            The function searches an item with key equal to \p key in the set,
+            call \p f functor with item found, unlinks it from the set, and returns \p true.
+            The \ref disposer specified in \p Traits class template parameter is called
+            by garbage collector \p GC asynchronously.
 
-            guarded_ptr gp;
-            for (;;) {
-                if ( !find_position( val, pos, cmp, false )) {
-                    m_Stat.onExtractFailed();
-                    return guarded_ptr();
-                }
+            The \p Func interface is
+            \code
+            struct functor {
+                void operator()( value_type const& item );
+            };
+            \endcode
 
-                node_type * pDel = pos.pCur;
-                gp.reset( node_traits::to_value_ptr( pDel ));
-                assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
+            If the item with key equal to \p key is not found the function return \p false.
 
-                unsigned int nHeight = pDel->height();
-                if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
-                    --m_ItemCounter;
-                    m_Stat.onRemoveNode( nHeight );
-                    m_Stat.onExtractSuccess();
-                    return gp;
-                }
-                m_Stat.onExtractRetry();
-            }
+            Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
+        */
+        template <typename Q, typename Func>
+        bool erase( Q const& key, Func f )
+        {
+            return erase_( key, key_comparator(), f );
         }
 
-        guarded_ptr extract_min_()
-        {
-            position pos;
+        /// Deletes the item from the set with comparing functor \p pred
+        /**
+            The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase_func "erase(Q const&, Func)"
+            but \p pred predicate is used for key comparing.
 
-            guarded_ptr gp;
-            for (;;) {
-                if ( !find_min_position( pos )) {
-                    // The list is empty
-                    m_Stat.onExtractMinFailed();
-                    return guarded_ptr();
-                }
+            \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
+            in any order.
+            \p pred must imply the same element order as the comparator used for building the set.
+        */
+        template <typename Q, typename Less, typename Func>
+        bool erase_with( Q const& key, Less pred, Func f )
+        {
+            CDS_UNUSED( pred );
+            return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
+        }
 
-                node_type * pDel = pos.pCur;
+        /// Finds \p key
+        /** \anchor cds_intrusive_SkipListSet_hp_find_func
+            The function searches the item with key equal to \p key and calls the functor \p f for item found.
+            The interface of \p Func functor is:
+            \code
+            struct functor {
+                void operator()( value_type& item, Q& key );
+            };
+            \endcode
+            where \p item is the item found, \p key is the <tt>find</tt> function argument.
 
-                unsigned int nHeight = pDel->height();
-                gp.reset( node_traits::to_value_ptr(pDel));
+            The functor can change non-key fields of \p item. Note that the functor is only guarantee
+            that \p item cannot be disposed during functor is executing.
+            The functor does not serialize simultaneous access to the set \p item. If such access is
+            possible you must provide your own synchronization on item level to exclude unsafe item modifications.
 
-                if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
-                    --m_ItemCounter;
-                    m_Stat.onRemoveNode( nHeight );
-                    m_Stat.onExtractMinSuccess();
-                    return gp;
-                }
+            Note the compare functor specified for class \p Traits template parameter
+            should accept a parameter of type \p Q that can be not the same as \p value_type.
 
-                m_Stat.onExtractMinRetry();
-            }
+            The function returns \p true if \p key is found, \p false otherwise.
+        */
+        template <typename Q, typename Func>
+        bool find( Q& key, Func f )
+        {
+            return find_with_( key, key_comparator(), f );
         }
-
-        guarded_ptr extract_max_()
+        //@cond
+        template <typename Q, typename Func>
+        bool find( Q const& key, Func f )
         {
-            position pos;
+            return find_with_( key, key_comparator(), f );
+        }
+        //@endcond
 
-            guarded_ptr gp;
-            for (;;) {
-                if ( !find_max_position( pos )) {
-                    // The list is empty
-                    m_Stat.onExtractMaxFailed();
-                    return guarded_ptr();
-                }
-
-                node_type * pDel = pos.pCur;
-
-                unsigned int nHeight = pDel->height();
-                gp.reset( node_traits::to_value_ptr(pDel));
-
-                if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
-                    --m_ItemCounter;
-                    m_Stat.onRemoveNode( nHeight );
-                    m_Stat.onExtractMaxSuccess();
-                    return gp;
-                }
+        /// Finds the key \p key with \p pred predicate for comparing
+        /**
+            The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_func "find(Q&, Func)"
+            but \p pred is used for key compare.
 
-                m_Stat.onExtractMaxRetry();
-            }
+            \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
+            in any order.
+            \p pred must imply the same element order as the comparator used for building the set.
+        */
+        template <typename Q, typename Less, typename Func>
+        bool find_with( Q& key, Less pred, Func f )
+        {
+            CDS_UNUSED( pred );
+            return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
         }
-
-        void increase_height( unsigned int nHeight )
+        //@cond
+        template <typename Q, typename Less, typename Func>
+        bool find_with( Q const& key, Less pred, Func f )
         {
-            unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
-            if ( nCur < nHeight )
-                m_nHeight.compare_exchange_strong( nCur, nHeight, memory_model::memory_order_release, atomics::memory_order_relaxed );
+            CDS_UNUSED( pred );
+            return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
         }
         //@endcond
 
-    public:
-        /// Default constructor
+        /// Checks whether the set contains \p key
         /**
-            The constructor checks whether the count of guards is enough
-            for skip-list and may raise an exception if not.
+            The function searches the item with key equal to \p key
+            and returns \p true if it is found, and \p false otherwise.
         */
-        SkipListSet()
-            : m_Head( c_nMaxHeight )
-            , m_nHeight( c_nMinHeight )
+        template <typename Q>
+        bool contains( Q const& key )
         {
-            static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
-
-            gc::check_available_guards( c_nHazardPtrCount );
-
-            // Barrier for head node
-            atomics::atomic_thread_fence( memory_model::memory_order_release );
+            return find_with_( key, key_comparator(), [](value_type& , Q const& ) {} );
         }
-
-        /// Clears and destructs the skip-list
-        ~SkipListSet()
+        //@cond
+        template <typename Q>
+        CDS_DEPRECATED("deprecated, use contains()")
+        bool find( Q const& key )
         {
-            clear();
+            return contains( key );
         }
+        //@endcond
 
-    public:
-    ///@name Forward iterators (only for debugging purpose)
-    //@{
-        /// Iterator type
+        /// Checks whether the set contains \p key using \p pred predicate for searching
         /**
-            The forward iterator has some features:
-            - it has no post-increment operator
-            - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
-              For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
-              may be thrown if the limit of guard count per thread is exceeded.
-            - The iterator cannot be moved across thread boundary because it contains thread-private GC's guard.
-            - Iterator ensures thread-safety even if you delete the item the iterator points to. However, in case of concurrent
-              deleting operations there is no guarantee that you iterate all item in the list.
-              Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
+            The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
+            \p Less functor has the interface like \p std::less.
+            \p Less must imply the same element order as the comparator used for building the set.
+        */
+        template <typename Q, typename Less>
+        bool contains( Q const& key, Less pred )
+        {
+            CDS_UNUSED( pred );
+            return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
+        }
+        //@cond
+        template <typename Q, typename Less>
+        CDS_DEPRECATED("deprecated, use contains()")
+        bool find_with( Q const& key, Less pred )
+        {
+            return contains( key, pred );
+        }
+        //@endcond
 
-            @warning Use this iterator on the concurrent container for debugging purpose only.
+        /// Finds \p key and return the item found
+        /** \anchor cds_intrusive_SkipListSet_hp_get
+            The function searches the item with key equal to \p key
+            and returns the pointer to the item found as \p guarded_ptr.
+            If \p key is not found the function returns an empt guarded pointer.
 
-            The iterator interface:
+            The \p disposer specified in \p Traits class template parameter is called
+            by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
+            will be destroyed or released.
+            @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
+
+            Usage:
             \code
-            class iterator {
-            public:
-                // Default constructor
-                iterator();
+            typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
+            skip_list theList;
+            // ...
+            {
+                skip_list::guarded_ptr gp(theList.get( 5 ));
+                if ( gp ) {
+                    // Deal with gp
+                    //...
+                }
+                // Destructor of guarded_ptr releases internal HP guard
+            }
+            \endcode
 
-                // Copy construtor
-                iterator( iterator const& src );
+            Note the compare functor specified for class \p Traits template parameter
+            should accept a parameter of type \p Q that can be not the same as \p value_type.
+        */
+        template <typename Q>
+        guarded_ptr get( Q const& key )
+        {
+            return get_with_( key, key_comparator());
+        }
 
-                // Dereference operator
-                value_type * operator ->() const;
+        /// Finds \p key and return the item found
+        /**
+            The function is an analog of \ref cds_intrusive_SkipListSet_hp_get "get( Q const&)"
+            but \p pred is used for comparing the keys.
 
-                // Dereference operator
-                value_type& operator *() const;
+            \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
+            in any order.
+            \p pred must imply the same element order as the comparator used for building the set.
+        */
+        template <typename Q, typename Less>
+        guarded_ptr get_with( Q const& key, Less pred )
+        {
+            CDS_UNUSED( pred );
+            return get_with_( key, cds::opt::details::make_comparator_from_less<Less>());
+        }
 
-                // Preincrement operator
-                iterator& operator ++();
+        /// Returns item count in the set
+        /**
+            The value returned depends on item counter type provided by \p Traits template parameter.
+            If it is \p atomicity::empty_item_counter this function always returns 0.
+            Therefore, the function is not suitable for checking the set emptiness, use \p empty()
+            for this purpose.
+        */
+        size_t size() const
+        {
+            return m_ItemCounter;
+        }
 
-                // Assignment operator
-                iterator& operator = (iterator const& src);
+        /// Checks if the set is empty
+        bool empty() const
+        {
+            return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
+        }
 
-                // Equality operators
-                bool operator ==(iterator const& i ) const;
-                bool operator !=(iterator const& i ) const;
-            };
+        /// Clears the set (not atomic)
+        /**
+            The function unlink all items from the set.
+            The function is not atomic, i.e., in multi-threaded environment with parallel insertions
+            this sequence
+            \code
+            set.clear();
+            assert( set.empty());
             \endcode
-        */
-        typedef skip_list::details::iterator< gc, node_traits, back_off, false >  iterator;
-
-        /// Const iterator type
-        typedef skip_list::details::iterator< gc, node_traits, back_off, true >   const_iterator;
+            the assertion could be raised.
 
-        /// Returns a forward iterator addressing the first element in a set
-        iterator begin()
+            For each item the \ref disposer will be called after unlinking.
+        */
+        void clear()
         {
-            return iterator( *m_Head.head());
+            while ( extract_min_());
         }
 
-        /// Returns a forward const iterator addressing the first element in a set
-        const_iterator begin() const
+        /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
+        static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
         {
-            return const_iterator( *m_Head.head());
+            return c_nMaxHeight;
         }
-        /// Returns a forward const iterator addressing the first element in a set
-        const_iterator cbegin() const
+
+        /// Returns const reference to internal statistics
+        stat const& statistics() const
         {
-            return const_iterator( *m_Head.head());
+            return m_Stat;
         }
 
-        /// Returns a forward iterator that addresses the location succeeding the last element in a set.
-        iterator end()
+    protected:
+        //@cond
+        unsigned int random_level()
         {
-            return iterator();
+            // Random generator produces a number from range [0..31]
+            // We need a number from range [1..32]
+            return m_RandomLevelGen() + 1;
         }
 
-        /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
-        const_iterator end() const
+        template <typename Q>
+        node_type * build_node( Q v )
         {
-            return const_iterator();
+            return node_builder::make_tower( v, m_RandomLevelGen );
         }
-        /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
-        const_iterator cend() const
+
+        static value_type * gc_protect( marked_node_ptr p )
         {
-            return const_iterator();
+            return node_traits::to_value_ptr( p.ptr() );
         }
-    //@}
-
-    public:
-        /// Inserts new node
-        /**
-            The function inserts \p val in the set if it does not contain
-            an item with key equal to \p val.
 
-            Returns \p true if \p val is placed into the set, \p false otherwise.
-        */
-        bool insert( value_type& val )
+        static void dispose_node( value_type * pVal )
         {
-            return insert( val, []( value_type& ) {} );
+            assert( pVal != nullptr );
+            typename node_builder::node_disposer()( node_traits::to_node_ptr( pVal ) );
+            disposer()( pVal );
         }
 
-        /// Inserts new node
-        /**
-            This function is intended for derived non-intrusive containers.
-
-            The function allows to split creating of new item into two part:
-            - create item with key only
-            - insert new item into the set
-            - if inserting is success, calls  \p f functor to initialize value-field of \p val.
-
-            The functor signature is:
-            \code
-                void func( value_type& val );
-            \endcode
-            where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
-            \p val no any other changes could be made on this set's item by concurrent threads.
-            The user-defined functor is called only if the inserting is success.
-        */
-        template <typename Func>
-        bool insert( value_type& val, Func f )
+        template <typename Q, typename Compare >
+        bool find_position( Q const& val, position& pos, Compare cmp, bool bStopIfFound )
         {
-            typename gc::Guard gNew;
-            gNew.assign( &val );
+            node_type * pPred;
+            marked_node_ptr pSucc;
+            marked_node_ptr pCur;
 
-            node_type * pNode = node_traits::to_node_ptr( val );
-            scoped_node_ptr scp( pNode );
-            unsigned int nHeight = pNode->height();
-            bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
-            bool bTowerMade = false;
+            // Hazard pointer array:
+            //  pPred: [nLevel * 2]
+            //  pSucc: [nLevel * 2 + 1]
 
-            position pos;
-            while ( true )
-            {
-                if ( find_position( val, pos, key_comparator(), true )) {
-                    // scoped_node_ptr deletes the node tower if we create it
-                    if ( !bTowerMade )
-                        scp.release();
+        retry:
+            pPred = m_Head.head();
+            int nCmp = 1;
 
-                    m_Stat.onInsertFailed();
-                    return false;
-                }
+            for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
+                pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ) );
+                while ( true ) {
+                    pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
+                    if ( pCur.bits() ) {
+                        // pCur.bits() means that pPred is logically deleted
+                        goto retry;
+                    }
 
-                if ( !bTowerOk ) {
-                    build_node( pNode );
-                    nHeight = pNode->height();
-                    bTowerMade =
-                        bTowerOk = true;
-                }
+                    if ( pCur.ptr() == nullptr ) {
+                        // end of list at level nLevel - goto next level
+                        break;
+                    }
 
-                if ( !insert_at_position( val, pNode, pos, f )) {
-                    m_Stat.onInsertRetry();
-                    continue;
+                    // pSucc contains deletion mark for pCur
+                    pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
+
+                    if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr() )
+                        goto retry;
+
+                    if ( pSucc.bits() ) {
+                        // pCur is marked, i.e. logically deleted.
+                        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 ) )
+                        {
+                            if ( nLevel == 0 ) {
+                                gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
+                                m_Stat.onEraseWhileFind();
+                            }
+                        }
+                        goto retry;
+                    }
+                    else {
+                        nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
+                        if ( nCmp < 0 ) {
+                            pPred = pCur.ptr();
+                            pos.guards.copy( nLevel * 2, nLevel * 2 + 1 );   // pPrev guard := cur guard
+                        }
+                        else if ( nCmp == 0 && bStopIfFound )
+                            goto found;
+                        else
+                            break;
+                    }
                 }
 
-                increase_height( nHeight );
-                ++m_ItemCounter;
-                m_Stat.onAddNode( nHeight );
-                m_Stat.onInsertSuccess();
-                scp.release();
-                return true;
+                // Next level
+                pos.pPrev[nLevel] = pPred;
+                pos.pSucc[nLevel] = pCur.ptr();
             }
-        }
-
-        /// Updates the node
-        /**
-            The operation performs inserting or changing data with lock-free manner.
 
-            If the item \p val is not found in the set, then \p val is inserted into the set
-            iff \p bInsert is \p true.
-            Otherwise, the functor \p func is called with item found.
-            The functor \p func signature is:
-            \code
-                void func( bool bNew, value_type& item, value_type& val );
-            \endcode
-            with arguments:
-            - \p bNew - \p true if the item has been inserted, \p false otherwise
-            - \p item - item of the set
-            - \p val - argument \p val passed into the \p %update() function
-            If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
-            refer to the same thing.
+            if ( nCmp != 0 )
+                return false;
 
-            Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
-            i.e. the node has been inserted or updated,
-            \p second is \p true if new item has been added or \p false if the item with \p key
-            already exists.
+        found:
+            pos.pCur = pCur.ptr();
+            return pCur.ptr() && nCmp == 0;
+        }
 
-            @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
-        */
-        template <typename Func>
-        std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
+        bool find_min_position( position& pos )
         {
-            typename gc::Guard gNew;
-            gNew.assign( &val );
+            node_type * pPred;
+            marked_node_ptr pSucc;
+            marked_node_ptr pCur;
 
-            node_type * pNode = node_traits::to_node_ptr( val );
-            scoped_node_ptr scp( pNode );
-            unsigned int nHeight = pNode->height();
-            bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
-            bool bTowerMade = false;
+            // Hazard pointer array:
+            //  pPred: [nLevel * 2]
+            //  pSucc: [nLevel * 2 + 1]
 
-            position pos;
-            while ( true )
-            {
-                bool bFound = find_position( val, pos, key_comparator(), true );
-                if ( bFound ) {
-                    // scoped_node_ptr deletes the node tower if we create it before
-                    if ( !bTowerMade )
-                        scp.release();
+        retry:
+            pPred = m_Head.head();
 
-                    func( false, *node_traits::to_value_ptr(pos.pCur), val );
-                    m_Stat.onUpdateExist();
-                    return std::make_pair( true, false );
-                }
+            for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
+                pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ) );
+                pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
 
-                if ( !bInsert ) {
-                    scp.release();
-                    return std::make_pair( false, false );
-                }
+                // pCur.bits() means that pPred is logically deleted
+                // head cannot be deleted
+                assert( pCur.bits() == 0 );
 
-                if ( !bTowerOk ) {
-                    build_node( pNode );
-                    nHeight = pNode->height();
-                    bTowerMade =
-                        bTowerOk = true;
-                }
+                if ( pCur.ptr() ) {
 
-                if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { func( true, item, item ); })) {
-                    m_Stat.onInsertRetry();
-                    continue;
+                    // pSucc contains deletion mark for pCur
+                    pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
+
+                    if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr() )
+                        goto retry;
+
+                    if ( pSucc.bits() ) {
+                        // pCur is marked, i.e. logically deleted.
+                        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 ) )
+                        {
+                            if ( nLevel == 0 ) {
+                                gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
+                                m_Stat.onEraseWhileFind();
+                            }
+                        }
+                        goto retry;
+                    }
                 }
 
-                increase_height( nHeight );
-                ++m_ItemCounter;
-                scp.release();
-                m_Stat.onAddNode( nHeight );
-                m_Stat.onUpdateNew();
-                return std::make_pair( true, true );
+                // Next level
+                pos.pPrev[nLevel] = pPred;
+                pos.pSucc[nLevel] = pCur.ptr();
             }
+
+            return ( pos.pCur = pCur.ptr() ) != nullptr;
         }
-        //@cond
-        template <typename Func>
-        CDS_DEPRECATED("ensure() is deprecated, use update()")
-        std::pair<bool, bool> ensure( value_type& val, Func func )
+
+        bool find_max_position( position& pos )
         {
-            return update( val, func, true );
-        }
-        //@endcond
+            node_type * pPred;
+            marked_node_ptr pSucc;
+            marked_node_ptr pCur;
 
-        /// Unlinks the item \p val from the set
-        /**
-            The function searches the item \p val in the set and unlink it from the set
-            if it is found and is equal to \p val.
+            // Hazard pointer array:
+            //  pPred: [nLevel * 2]
+            //  pSucc: [nLevel * 2 + 1]
 
-            Difference between \p erase() and \p %unlink() functions: \p %erase() finds <i>a key</i>
-            and deletes the item found. \p %unlink() finds an item by key and deletes it
-            only if \p val is an item of that set, i.e. the pointer to item found
-            is equal to <tt> &val </tt>.
+        retry:
+            pPred = m_Head.head();
 
-            The \p disposer specified in \p Traits class template parameter is called
-            by garbage collector \p GC asynchronously.
+            for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
+                pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ) );
+                while ( true ) {
+                    pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
+                    if ( pCur.bits() ) {
+                        // pCur.bits() means that pPred is logically deleted
+                        goto retry;
+                    }
 
-            The function returns \p true if success and \p false otherwise.
-        */
-        bool unlink( value_type& val )
-        {
-            position pos;
+                    if ( pCur.ptr() == nullptr ) {
+                        // end of the list at level nLevel - goto next level
+                        break;
+                    }
 
-            if ( !find_position( val, pos, key_comparator(), false )) {
-                m_Stat.onUnlinkFailed();
-                return false;
-            }
+                    // pSucc contains deletion mark for pCur
+                    pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
 
-            node_type * pDel = pos.pCur;
-            assert( key_comparator()( *node_traits::to_value_ptr( pDel ), val ) == 0 );
+                    if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr() )
+                        goto retry;
 
-            unsigned int nHeight = pDel->height();
-            typename gc::Guard gDel;
-            gDel.assign( node_traits::to_value_ptr(pDel));
+                    if ( pSucc.bits() ) {
+                        // pCur is marked, i.e. logically deleted.
+                        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 ) )
+                        {
+                            if ( nLevel == 0 ) {
+                                gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
+                                m_Stat.onEraseWhileFind();
+                            }
+                        }
+                        goto retry;
+                    }
+                    else {
+                        if ( !pSucc.ptr() )
+                            break;
 
-            if ( node_traits::to_value_ptr( pDel ) == &val && try_remove_at( pDel, pos, [](value_type const&) {} )) {
-                --m_ItemCounter;
-                m_Stat.onRemoveNode( nHeight );
-                m_Stat.onUnlinkSuccess();
-                return true;
+                        pPred = pCur.ptr();
+                        pos.guards.copy( nLevel * 2, nLevel * 2 + 1 ); 
+                    }
+                }
+
+                // Next level
+                pos.pPrev[nLevel] = pPred;
+                pos.pSucc[nLevel] = pCur.ptr();
             }
 
-            m_Stat.onUnlinkFailed();
-            return false;
-        }
-
-        /// Extracts the item from the set with specified \p key
-        /** \anchor cds_intrusive_SkipListSet_hp_extract
-            The function searches an item with key equal to \p key in the set,
-            unlinks it from the set, and returns it as \p guarded_ptr object.
-            If \p key is not found the function returns an empty guarded pointer.
-
-            Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
-
-            The \p disposer specified in \p Traits class template parameter is called automatically
-            by garbage collector \p GC specified in class' template parameters when returned \p guarded_ptr object
-            will be destroyed or released.
-            @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
-
-            Usage:
-            \code
-            typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
-            skip_list theList;
-            // ...
-            {
-                skip_list::guarded_ptr gp(theList.extract( 5 ));
-                if ( gp ) {
-                    // Deal with gp
-                    // ...
-                }
-                // Destructor of gp releases internal HP guard
-            }
-            \endcode
-        */
-        template <typename Q>
-        guarded_ptr extract( Q const& key )
-        {
-            return extract_( key, key_comparator());
+            return ( pos.pCur = pCur.ptr() ) != nullptr;
         }
 
-        /// Extracts the item from the set with comparing functor \p pred
-        /**
-            The function is an analog of \ref cds_intrusive_SkipListSet_hp_extract "extract(Q const&)"
-            but \p pred predicate is used for key comparing.
-
-            \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
-            in any order.
-            \p pred must imply the same element order as the comparator used for building the set.
-        */
-        template <typename Q, typename Less>
-        guarded_ptr extract_with( Q const& key, Less pred )
+        template <typename Func>
+        bool insert_at_position( value_type& val, node_type * pNode, position& pos, Func f )
         {
-            CDS_UNUSED( pred );
-            return extract_( key, cds::opt::details::make_comparator_from_less<Less>());
-        }
-
-        /// Extracts an item with minimal key from the list
-        /**
-            The function searches an item with minimal key, unlinks it, and returns it as \p guarded_ptr object.
-            If the skip-list is empty the function returns an empty guarded pointer.
-
-            @note Due the concurrent nature of the list, the function extracts <i>nearly</i> minimum key.
-            It means that the function gets leftmost item and tries to unlink it.
-            During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
-            So, the function returns the item with minimum key at the moment of list traversing.
+            unsigned int nHeight = pNode->height();
 
-            The \p disposer specified in \p Traits class template parameter is called
-            by garbage collector \p GC automatically when returned \p guarded_ptr object
-            will be destroyed or released.
-            @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
+            for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel )
+                pNode->next( nLevel ).store( marked_node_ptr(), memory_model::memory_order_relaxed );
 
-            Usage:
-            \code
-            typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
-            skip_list theList;
-            // ...
+            // Insert at level 0
             {
-                skip_list::guarded_ptr gp(theList.extract_min());
-                if ( gp ) {
-                    // Deal with gp
-                    //...
-                }
-                // Destructor of gp releases internal HP guard
-            }
-            \endcode
-        */
-        guarded_ptr extract_min()
-        {
-            return extract_min_();
-        }
-
-        /// Extracts an item with maximal key from the list
-        /**
-            The function searches an item with maximal key, unlinks it, and returns the pointer to item
-            as \p guarded_ptr object.
-            If the skip-list is empty the function returns an empty \p guarded_ptr.
+                marked_node_ptr p( pos.pSucc[0] );
+                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 ) )
+                    return false;
 
-            @note Due the concurrent nature of the list, the function extracts <i>nearly</i> maximal key.
-            It means that the function gets rightmost item and tries to unlink it.
-            During unlinking, a concurrent thread may insert an item with key greater than rightmost item's key.
-            So, the function returns the item with maximum key at the moment of list traversing.
+                f( val );
+            }
 
-            The \p disposer specified in \p Traits class template parameter is called
-            by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
-            will be destroyed or released.
-            @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
+            // Insert at level 1..max
+            for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
+                marked_node_ptr p;
+                while ( true ) {
+                    marked_node_ptr q( pos.pSucc[nLevel] );
+                    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;
+                    if ( pos.pPrev[nLevel]->next( nLevel ).compare_exchange_strong( q, marked_node_ptr( pNode ), memory_model::memory_order_release, atomics::memory_order_relaxed ) )
+                        break;
 
-            Usage:
-            \code
-            typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
-            skip_list theList;
-            // ...
-            {
-                skip_list::guarded_ptr gp( theList.extract_max( gp ));
-                if ( gp ) {
-                    // Deal with gp
-                    //...
+                    // Renew insert position
+                    m_Stat.onRenewInsertPosition();
+                    if ( !find_position( val, pos, key_comparator(), false ) ) {
+                        // The node has been deleted while we are inserting it
+                        m_Stat.onNotFoundWhileInsert();
+                        return true;
+                    }
                 }
-                // Destructor of gp releases internal HP guard
             }
-            \endcode
-        */
-        guarded_ptr extract_max()
-        {
-            return extract_max_();
+            return true;
         }
 
-        /// Deletes the item from the set
-        /** \anchor cds_intrusive_SkipListSet_hp_erase
-            The function searches an item with key equal to \p key in the set,
-            unlinks it from the set, and returns \p true.
-            If the item with key equal to \p key is not found the function return \p false.
-
-            Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
-        */
-        template <typename Q>
-        bool erase( Q const& key )
+        template <typename Func>
+        bool try_remove_at( node_type * pDel, position& pos, Func f )
         {
-            return erase_( key, key_comparator(), [](value_type const&) {} );
-        }
-
-        /// Deletes the item from the set with comparing functor \p pred
-        /**
-            The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase "erase(Q const&)"
-            but \p pred predicate is used for key comparing.
+            assert( pDel != nullptr );
 
-            \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
-            in any order.
-            \p pred must imply the same element order as the comparator used for building the set.
-        */
-        template <typename Q, typename Less>
-        bool erase_with( Q const& key, Less pred )
-        {
-            CDS_UNUSED( pred );
-            return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type const&) {} );
-        }
+            marked_node_ptr pSucc;
 
-        /// Deletes the item from the set
-        /** \anchor cds_intrusive_SkipListSet_hp_erase_func
-            The function searches an item with key equal to \p key in the set,
-            call \p f functor with item found, unlinks it from the set, and returns \p true.
-            The \ref disposer specified in \p Traits class template parameter is called
-            by garbage collector \p GC asynchronously.
+            // logical deletion (marking)
+            for ( unsigned int nLevel = pDel->height() - 1; nLevel > 0; --nLevel ) {
+                while ( true ) {
+                    pSucc = pDel->next( nLevel );
+                    if ( pSucc.bits() || pDel->next( nLevel ).compare_exchange_weak( pSucc, pSucc | 1,
+                        memory_model::memory_order_release, atomics::memory_order_relaxed ) )
+                    {
+                        break;
+                    }
+                }
+            }
 
-            The \p Func interface is
-            \code
-            struct functor {
-                void operator()( value_type const& item );
-            };
-            \endcode
+            while ( true ) {
+                marked_node_ptr p( pDel->next( 0 ).load( memory_model::memory_order_relaxed ).ptr() );
+                if ( pDel->next( 0 ).compare_exchange_strong( p, p | 1, memory_model::memory_order_release, atomics::memory_order_relaxed ) )
+                {
+                    f( *node_traits::to_value_ptr( pDel ) );
 
-            If the item with key equal to \p key is not found the function return \p false.
+                    // Physical deletion
+                    // try fast erase
+                    p = pDel;
+                    for ( int nLevel = static_cast<int>( pDel->height() - 1 ); nLevel >= 0; --nLevel ) {
+                        pSucc = pDel->next( nLevel ).load( memory_model::memory_order_relaxed );
+                        if ( !pos.pPrev[nLevel]->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
+                            memory_model::memory_order_acquire, atomics::memory_order_relaxed ) )
+                        {
+                            // Make slow erase
+                            find_position( *node_traits::to_value_ptr( pDel ), pos, key_comparator(), false );
+                            m_Stat.onSlowErase();
+                            return true;
+                        }
+                    }
 
-            Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
-        */
-        template <typename Q, typename Func>
-        bool erase( Q const& key, Func f )
-        {
-            return erase_( key, key_comparator(), f );
+                    // Fast erasing success
+                    gc::retire( node_traits::to_value_ptr( pDel ), dispose_node );
+                    m_Stat.onFastErase();
+                    return true;
+                }
+                else {
+                    if ( p.bits() ) {
+                        // Another thread is deleting pDel right now
+                        return false;
+                    }
+                }
+                m_Stat.onEraseRetry();
+            }
         }
 
-        /// Deletes the item from the set with comparing functor \p pred
-        /**
-            The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase_func "erase(Q const&, Func)"
-            but \p pred predicate is used for key comparing.
-
-            \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
-            in any order.
-            \p pred must imply the same element order as the comparator used for building the set.
-        */
-        template <typename Q, typename Less, typename Func>
-        bool erase_with( Q const& key, Less pred, Func f )
+        enum finsd_fastpath_result {
+            find_fastpath_found,
+            find_fastpath_not_found,
+            find_fastpath_abort
+        };
+        template <typename Q, typename Compare, typename Func>
+        finsd_fastpath_result find_fastpath( Q& val, Compare cmp, Func f )
         {
-            CDS_UNUSED( pred );
-            return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
-        }
+            node_type * pPred;
+            typename gc::template GuardArray<2>  guards;
+            marked_node_ptr pCur;
+            marked_node_ptr pNull;
 
-        /// Finds \p key
-        /** \anchor cds_intrusive_SkipListSet_hp_find_func
-            The function searches the item with key equal to \p key and calls the functor \p f for item found.
-            The interface of \p Func functor is:
-            \code
-            struct functor {
-                void operator()( value_type& item, Q& key );
-            };
-            \endcode
-            where \p item is the item found, \p key is the <tt>find</tt> function argument.
+            back_off bkoff;
 
-            The functor can change non-key fields of \p item. Note that the functor is only guarantee
-            that \p item cannot be disposed during functor is executing.
-            The functor does not serialize simultaneous access to the set \p item. If such access is
-            possible you must provide your own synchronization on item level to exclude unsafe item modifications.
+            pPred = m_Head.head();
+            for ( int nLevel = static_cast<int>( m_nHeight.load( memory_model::memory_order_relaxed ) - 1 ); nLevel >= 0; --nLevel ) {
+                pCur = guards.protect( 1, pPred->next( nLevel ), gc_protect );
+                if ( pCur == pNull )
+                    continue;
 
-            Note the compare functor specified for class \p Traits template parameter
-            should accept a parameter of type \p Q that can be not the same as \p value_type.
+                while ( pCur != pNull ) {
+                    if ( pCur.bits() ) {
+                        unsigned int nAttempt = 0;
+                        bkoff.reset();
+                        while ( pCur.bits() && nAttempt++ < 16 ) {
+                            bkoff();
+                            pCur = guards.protect( 1, pPred->next( nLevel ), gc_protect );
+                        }
 
-            The function returns \p true if \p key is found, \p false otherwise.
-        */
-        template <typename Q, typename Func>
-        bool find( Q& key, Func f )
-        {
-            return find_with_( key, key_comparator(), f );
-        }
-        //@cond
-        template <typename Q, typename Func>
-        bool find( Q const& key, Func f )
-        {
-            return find_with_( key, key_comparator(), f );
-        }
-        //@endcond
+                        if ( pCur.bits() ) {
+                            // Maybe, we are on deleted node sequence
+                            // Abort searching, try slow-path
+                            return find_fastpath_abort;
+                        }
+                    }
 
-        /// Finds the key \p key with \p pred predicate for comparing
-        /**
-            The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_func "find(Q&, Func)"
-            but \p pred is used for key compare.
+                    if ( pCur.ptr() ) {
+                        int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
+                        if ( nCmp < 0 ) {
+                            guards.copy( 0, 1 );
+                            pPred = pCur.ptr();
+                            pCur = guards.protect( 1, pCur->next( nLevel ), gc_protect );
+                        }
+                        else if ( nCmp == 0 ) {
+                            // found
+                            f( *node_traits::to_value_ptr( pCur.ptr() ), val );
+                            return find_fastpath_found;
+                        }
+                        else // pCur > val - go down
+                            break;
+                    }
+                }
+            }
 
-            \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
-            in any order.
-            \p pred must imply the same element order as the comparator used for building the set.
-        */
-        template <typename Q, typename Less, typename Func>
-        bool find_with( Q& key, Less pred, Func f )
-        {
-            CDS_UNUSED( pred );
-            return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
+            return find_fastpath_not_found;
         }
-        //@cond
-        template <typename Q, typename Less, typename Func>
-        bool find_with( Q const& key, Less pred, Func f )
+
+        template <typename Q, typename Compare, typename Func>
+        bool find_slowpath( Q& val, Compare cmp, Func f )
         {
-            CDS_UNUSED( pred );
-            return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
+            position pos;
+            if ( find_position( val, pos, cmp, true ) ) {
+                assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
+
+                f( *node_traits::to_value_ptr( pos.pCur ), val );
+                return true;
+            }
+            else
+                return false;
         }
-        //@endcond
 
-        /// Checks whether the set contains \p key
-        /**
-            The function searches the item with key equal to \p key
-            and returns \p true if it is found, and \p false otherwise.
-        */
-        template <typename Q>
-        bool contains( Q const& key )
+        template <typename Q, typename Compare, typename Func>
+        bool find_with_( Q& val, Compare cmp, Func f )
         {
-            return find_with_( key, key_comparator(), [](value_type& , Q const& ) {} );
+            switch ( find_fastpath( val, cmp, f ) ) {
+            case find_fastpath_found:
+                m_Stat.onFindFastSuccess();
+                return true;
+            case find_fastpath_not_found:
+                m_Stat.onFindFastFailed();
+                return false;
+            default:
+                break;
+            }
+
+            if ( find_slowpath( val, cmp, f ) ) {
+                m_Stat.onFindSlowSuccess();
+                return true;
+            }
+
+            m_Stat.onFindSlowFailed();
+            return false;
         }
-        //@cond
-        template <typename Q>
-        CDS_DEPRECATED("deprecated, use contains()")
-        bool find( Q const& key )
+
+        template <typename Q, typename Compare>
+        guarded_ptr get_with_( Q const& val, Compare cmp )
         {
-            return contains( key );
+            guarded_ptr gp;
+            if ( find_with_( val, cmp, [&gp]( value_type& found, Q const& ) { gp.reset( &found ); } ) )
+                return gp;
+            return guarded_ptr();
         }
-        //@endcond
 
-        /// Checks whether the set contains \p key using \p pred predicate for searching
-        /**
-            The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
-            \p Less functor has the interface like \p std::less.
-            \p Less must imply the same element order as the comparator used for building the set.
-        */
-        template <typename Q, typename Less>
-        bool contains( Q const& key, Less pred )
+        template <typename Q, typename Compare, typename Func>
+        bool erase_( Q const& val, Compare cmp, Func f )
         {
-            CDS_UNUSED( pred );
-            return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
+            position pos;
+
+            if ( !find_position( val, pos, cmp, false ) ) {
+                m_Stat.onEraseFailed();
+                return false;
+            }
+
+            node_type * pDel = pos.pCur;
+            typename gc::Guard gDel;
+            gDel.assign( node_traits::to_value_ptr( pDel ) );
+            assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
+
+            unsigned int nHeight = pDel->height();
+            if ( try_remove_at( pDel, pos, f ) ) {
+                --m_ItemCounter;
+                m_Stat.onRemoveNode( nHeight );
+                m_Stat.onEraseSuccess();
+                return true;
+            }
+
+            m_Stat.onEraseFailed();
+            return false;
         }
-        //@cond
-        template <typename Q, typename Less>
-        CDS_DEPRECATED("deprecated, use contains()")
-        bool find_with( Q const& key, Less pred )
+
+        template <typename Q, typename Compare>
+        guarded_ptr extract_( Q const& val, Compare cmp )
         {
-            return contains( key, pred );
-        }
-        //@endcond
+            position pos;
 
-        /// Finds \p key and return the item found
-        /** \anchor cds_intrusive_SkipListSet_hp_get
-            The function searches the item with key equal to \p key
-            and returns the pointer to the item found as \p guarded_ptr.
-            If \p key is not found the function returns an empt guarded pointer.
+            guarded_ptr gp;
+            for ( ;;) {
+                if ( !find_position( val, pos, cmp, false ) ) {
+                    m_Stat.onExtractFailed();
+                    return guarded_ptr();
+                }
 
-            The \p disposer specified in \p Traits class template parameter is called
-            by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
-            will be destroyed or released.
-            @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
+                node_type * pDel = pos.pCur;
+                gp.reset( node_traits::to_value_ptr( pDel ) );
+                assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
 
-            Usage:
-            \code
-            typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
-            skip_list theList;
-            // ...
-            {
-                skip_list::guarded_ptr gp(theList.get( 5 ));
-                if ( gp ) {
-                    // Deal with gp
-                    //...
+                unsigned int nHeight = pDel->height();
+                if ( try_remove_at( pDel, pos, []( value_type const& ) {} ) ) {
+                    --m_ItemCounter;
+                    m_Stat.onRemoveNode( nHeight );
+                    m_Stat.onExtractSuccess();
+                    return gp;
                 }
-                // Destructor of guarded_ptr releases internal HP guard
+                m_Stat.onExtractRetry();
             }
-            \endcode
+        }
 
-            Note the compare functor specified for class \p Traits template parameter
-            should accept a parameter of type \p Q that can be not the same as \p value_type.
-        */
-        template <typename Q>
-        guarded_ptr get( Q const& key )
+        guarded_ptr extract_min_()
         {
-            return get_with_( key, key_comparator());
-        }
+            position pos;
 
-        /// Finds \p key and return the item found
-        /**
-            The function is an analog of \ref cds_intrusive_SkipListSet_hp_get "get( Q const&)"
-            but \p pred is used for comparing the keys.
+            guarded_ptr gp;
+            for ( ;;) {
+                if ( !find_min_position( pos ) ) {
+                    // The list is empty
+                    m_Stat.onExtractMinFailed();
+                    return guarded_ptr();
+                }
 
-            \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
-            in any order.
-            \p pred must imply the same element order as the comparator used for building the set.
-        */
-        template <typename Q, typename Less>
-        guarded_ptr get_with( Q const& key, Less pred )
-        {
-            CDS_UNUSED( pred );
-            return get_with_( key, cds::opt::details::make_comparator_from_less<Less>());
-        }
+                node_type * pDel = pos.pCur;
 
-        /// Returns item count in the set
-        /**
-            The value returned depends on item counter type provided by \p Traits template parameter.
-            If it is \p atomicity::empty_item_counter this function always returns 0.
-            Therefore, the function is not suitable for checking the set emptiness, use \p empty()
-            for this purpose.
-        */
-        size_t size() const
-        {
-            return m_ItemCounter;
+                unsigned int nHeight = pDel->height();
+                gp.reset( node_traits::to_value_ptr( pDel ) );
+
+                if ( try_remove_at( pDel, pos, []( value_type const& ) {} ) ) {
+                    --m_ItemCounter;
+                    m_Stat.onRemoveNode( nHeight );
+                    m_Stat.onExtractMinSuccess();
+                    return gp;
+                }
+
+                m_Stat.onExtractMinRetry();
+            }
         }
 
-        /// Checks if the set is empty
-        bool empty() const
+        guarded_ptr extract_max_()
         {
-            return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
-        }
+            position pos;
 
-        /// Clears the set (not atomic)
-        /**
-            The function unlink all items from the set.
-            The function is not atomic, i.e., in multi-threaded environment with parallel insertions
-            this sequence
-            \code
-            set.clear();
-            assert( set.empty());
-            \endcode
-            the assertion could be raised.
+            guarded_ptr gp;
+            for ( ;;) {
+                if ( !find_max_position( pos ) ) {
+                    // The list is empty
+                    m_Stat.onExtractMaxFailed();
+                    return guarded_ptr();
+                }
 
-            For each item the \ref disposer will be called after unlinking.
-        */
-        void clear()
-        {
-            while ( extract_min_());
-        }
+                node_type * pDel = pos.pCur;
 
-        /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
-        static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
-        {
-            return c_nMaxHeight;
+                unsigned int nHeight = pDel->height();
+                gp.reset( node_traits::to_value_ptr( pDel ) );
+
+                if ( try_remove_at( pDel, pos, []( value_type const& ) {} ) ) {
+                    --m_ItemCounter;
+                    m_Stat.onRemoveNode( nHeight );
+                    m_Stat.onExtractMaxSuccess();
+                    return gp;
+                }
+
+                m_Stat.onExtractMaxRetry();
+            }
         }
 
-        /// Returns const reference to internal statistics
-        stat const& statistics() const
+        void increase_height( unsigned int nHeight )
         {
-            return m_Stat;
+            unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
+            if ( nCur < nHeight )
+                m_nHeight.compare_exchange_strong( nCur, nHeight, memory_model::memory_order_release, atomics::memory_order_relaxed );
         }
+        //@endcond
+
+    private:
+        //@cond
+        skip_list::details::head_node< node_type > m_Head;   ///< head tower (max height)
+
+        item_counter                m_ItemCounter;    ///< item counter
+        random_level_generator      m_RandomLevelGen; ///< random level generator instance
+        atomics::atomic<unsigned int> m_nHeight;      ///< estimated high level
+        mutable stat                m_Stat;           ///< internal statistics
+        //@endcond
     };
 
 }} // namespace cds::intrusive