/*
This file is a part of libcds - Concurrent Data Structures library
- (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+ (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
Source code repo: http://github.com/khizmax/libcds/
Download: http://sourceforge.net/projects/libcds/files/
// c_nMaxHeight * 2 - pPred/pSucc guards
// + 1 - for erase, unlink
// + 1 - for clear
- static size_t const c_nHazardPtrCount = c_nMaxHeight * 2 + 2; ///< Count of hazard pointer required for the skip-list
+ // + 1 - for help_remove()
+ static size_t const c_nHazardPtrCount = c_nMaxHeight * 2 + 3; ///< Count of hazard pointer required for the skip-list
protected:
typedef typename node_type::atomic_marked_ptr atomic_node_ptr; ///< Atomic marked node pointer
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 );
+ destroy();
}
- 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;
+ }
- return (pos.pCur = pCur.ptr()) != nullptr;
- }
+ if ( !insert_at_position( val, pNode, pos, f )) {
+ m_Stat.onInsertRetry();
+ continue;
+ }
- bool find_max_position( position& pos )
- {
- node_type * pPred;
- marked_node_ptr pSucc;
- marked_node_ptr pCur;
+ increase_height( nHeight );
+ ++m_ItemCounter;
+ m_Stat.onAddNode( nHeight );
+ m_Stat.onInsertSuccess();
+ scp.release();
+ return true;
+ }
+ }
- // Hazard pointer array:
- // pPred: [nLevel * 2]
- // pSucc: [nLevel * 2 + 1]
+ /// Updates the node
+ /**
+ The operation performs inserting or changing data with lock-free manner.
- retry:
- pPred = m_Head.head();
+ 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.
- 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;
- }
+ 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.
- if ( pCur.ptr() == nullptr ) {
- // end of the list at level nLevel - goto next level
- break;
- }
+ @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 );
- // 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();
+ bool bTowerMade = false;
- if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr())
- goto retry;
+ 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 ( 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;
+ func( false, *node_traits::to_value_ptr(pos.pCur), val );
+ m_Stat.onUpdateExist();
+ return std::make_pair( true, 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 ( !bInsert ) {
+ scp.release();
+ return std::make_pair( false, 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;
+ }
- return (pos.pCur = pCur.ptr()) != nullptr;
- }
+ if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { func( true, item, item ); })) {
+ m_Stat.onInsertRetry();
+ continue;
+ }
+ 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;
+ \endcode
+ */
+ guarded_ptr extract_min()
+ {
+ return extract_min_();
}
- template <typename Q, typename Compare, typename Func>
- bool find_slowpath( Q& val, Compare cmp, Func f )
- {
- position pos;
- if ( find_position( val, pos, cmp, true )) {
- assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
+ /// 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.
- f( *node_traits::to_value_ptr( pos.pCur ), val );
- return true;
- }
- else
- 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.
- 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;
- }
+ 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.
- if ( find_slowpath( val, cmp, f )) {
- m_Stat.onFindSlowSuccess();
- return true;
+ 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
}
-
- m_Stat.onFindSlowFailed();
- return false;
+ \endcode
+ */
+ guarded_ptr extract_max()
+ {
+ return extract_max_();
}
- template <typename Q, typename Compare>
- guarded_ptr get_with_( Q const& val, Compare cmp )
+ /// 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 )
{
- guarded_ptr gp;
- if ( find_with_( val, cmp, [&gp](value_type& found, Q const& ) { gp.reset(&found); } ))
- return gp;
- return guarded_ptr();
+ return erase_( key, key_comparator(), [](value_type const&) {} );
}
- template <typename Q, typename Compare, typename Func>
- bool erase_( Q const& val, Compare cmp, Func f )
+ /// 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.
+
+ \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 )
{
- position pos;
+ CDS_UNUSED( pred );
+ return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type const&) {} );
+ }
- if ( !find_position( val, pos, cmp, false )) {
- m_Stat.onEraseFailed();
- return false;
- }
+ /// 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.
- 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 );
+ The \p Func interface is
+ \code
+ struct functor {
+ void operator()( value_type const& item );
+ };
+ \endcode
- unsigned int nHeight = pDel->height();
- if ( try_remove_at( pDel, pos, f )) {
- --m_ItemCounter;
- m_Stat.onRemoveNode( nHeight );
- m_Stat.onEraseSuccess();
- return true;
- }
+ If the item with key equal to \p key is not found the function return \p false.
- m_Stat.onEraseFailed();
- return 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, typename Func>
+ bool erase( Q const& key, Func f )
+ {
+ return erase_( key, key_comparator(), f );
}
- template <typename Q, typename Compare>
- guarded_ptr extract_( Q const& val, Compare cmp )
+ /// 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 )
{
- position pos;
+ CDS_UNUSED( pred );
+ return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
+ }
- guarded_ptr gp;
- for (;;) {
- if ( !find_position( val, pos, cmp, false )) {
- m_Stat.onExtractFailed();
- return guarded_ptr();
- }
+ /// 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.
- node_type * pDel = pos.pCur;
- gp.reset( node_traits::to_value_ptr( pDel ));
- assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
+ 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.
- 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 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.
- guarded_ptr extract_min_()
+ The function returns \p true if \p key is found, \p false otherwise.
+ */
+ template <typename Q, typename Func>
+ bool find( Q& key, Func f )
{
- position pos;
-
- guarded_ptr gp;
- for (;;) {
- if ( !find_min_position( pos )) {
- // The list is empty
- m_Stat.onExtractMinFailed();
- return guarded_ptr();
- }
-
- node_type * pDel = pos.pCur;
+ 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
- unsigned int nHeight = pDel->height();
- gp.reset( node_traits::to_value_ptr(pDel));
+ /// 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 ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
- --m_ItemCounter;
- m_Stat.onRemoveNode( nHeight );
- m_Stat.onExtractMinSuccess();
- return gp;
- }
-
- m_Stat.onExtractMinRetry();
- }
+ \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 );
}
-
- guarded_ptr extract_max_()
+ //@cond
+ template <typename Q, typename Less, typename Func>
+ bool find_with( Q const& key, Less pred, Func f )
{
- position pos;
-
- 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;
- }
-
- m_Stat.onExtractMaxRetry();
- }
+ CDS_UNUSED( pred );
+ return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
}
+ //@endcond
- void increase_height( unsigned int nHeight )
+ /// 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 )
{
- 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 );
+ return find_with_( key, key_comparator(), [](value_type& , Q const& ) {} );
+ }
+ //@cond
+ template <typename Q>
+ CDS_DEPRECATED("deprecated, use contains()")
+ bool find( Q const& key )
+ {
+ return contains( key );
}
//@endcond
- public:
- /// Default constructor
+ /// Checks whether the set contains \p key using \p pred predicate for searching
/**
- The constructor checks whether the count of guards is enough
- for skip-list and may raise an exception if not.
+ 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.
*/
- SkipListSet()
- : m_Head( c_nMaxHeight )
- , m_nHeight( c_nMinHeight )
+ template <typename Q, typename Less>
+ bool contains( Q const& key, Less pred )
{
- 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 );
+ CDS_UNUSED( pred );
+ return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
}
-
- /// Clears and destructs the skip-list
- ~SkipListSet()
+ //@cond
+ template <typename Q, typename Less>
+ CDS_DEPRECATED("deprecated, use contains()")
+ bool find_with( Q const& key, Less pred )
{
- clear();
+ return contains( key, pred );
}
+ //@endcond
- 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.
+ /// 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.
- @warning Use this iterator on the concurrent container for debugging purpose only.
+ 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.
- The iterator interface:
+ 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
+ the assertion could be raised.
+
+ For each item the \ref disposer will be called after unlinking.
*/
- typedef skip_list::details::iterator< gc, node_traits, back_off, false > iterator;
+ void clear()
+ {
+ while ( extract_min_());
+ }
- /// Const iterator type
- typedef skip_list::details::iterator< gc, node_traits, back_off, true > const_iterator;
+ /// 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;
+ }
- /// Returns a forward iterator addressing the first element in a set
- iterator begin()
+ /// Returns const reference to internal statistics
+ stat const& statistics() const
{
- return iterator( *m_Head.head());
+ return m_Stat;
}
- /// Returns a forward const iterator addressing the first element in a set
- const_iterator begin() const
+ protected:
+ //@cond
+ unsigned int random_level()
{
- return const_iterator( *m_Head.head());
+ // 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 addressing the first element in a set
- const_iterator cbegin() const
+
+ template <typename Q>
+ node_type * build_node( Q v )
{
- return const_iterator( *m_Head.head());
+ return node_builder::make_tower( v, m_RandomLevelGen );
}
- /// Returns a forward iterator that addresses the location succeeding the last element in a set.
- iterator end()
+ static value_type * gc_protect( marked_node_ptr p )
{
- return iterator();
+ return node_traits::to_value_ptr( p.ptr());
}
- /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
- const_iterator end() const
+ static void dispose_node( value_type * pVal )
{
- return const_iterator();
+ assert( pVal != nullptr );
+ typename node_builder::node_disposer()( node_traits::to_node_ptr( pVal ));
+ disposer()( pVal );
}
- /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
- const_iterator cend() const
+
+ void help_remove( int nLevel, node_type* pPred, marked_node_ptr pCur )
{
- return const_iterator();
+ if ( pCur->is_upper_level( nLevel )) {
+ marked_node_ptr p( pCur.ptr());
+ typename gc::Guard hp;
+ marked_node_ptr pSucc = hp.protect( pCur->next( nLevel ), gc_protect );
+
+ if ( pSucc.bits() &&
+ pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr()),
+ memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
+ {
+ if ( pCur->level_unlinked()) {
+ gc::retire( node_traits::to_value_ptr( pCur.ptr()), dispose_node );
+ m_Stat.onEraseWhileFind();
+ }
+ }
+ }
}
- //@}
- 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 )
+ template <typename Q, typename Compare >
+ bool find_position( Q const& val, position& pos, Compare cmp, bool bStopIfFound )
{
- return insert( val, []( value_type& ) {} );
- }
-
- /// Inserts new node
- /**
- This function is intended for derived non-intrusive containers.
+ node_type * pPred;
+ marked_node_ptr pSucc;
+ marked_node_ptr pCur;
- 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.
+ // Hazard pointer array:
+ // pPred: [nLevel * 2]
+ // pSucc: [nLevel * 2 + 1]
- 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 );
+ retry:
+ pPred = m_Head.head();
+ int nCmp = 1;
- 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;
+ 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;
+ }
- 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 ( pCur.ptr() == nullptr ) {
+ // end of list at level nLevel - goto next level
+ break;
+ }
- m_Stat.onInsertFailed();
- return false;
- }
+ // pSucc contains deletion mark for pCur
+ pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
- if ( !bTowerOk ) {
- build_node( pNode );
- nHeight = pNode->height();
- bTowerMade =
- bTowerOk = true;
- }
+ if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr())
+ goto retry;
- if ( !insert_at_position( val, pNode, pos, f )) {
- m_Stat.onInsertRetry();
- continue;
+ if ( pSucc.bits()) {
+ // pCur is marked, i.e. logically deleted
+ // try to help deleting pCur
+ help_remove( nLevel, pPred, pCur );
+ 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.
+ // try to help deleting pCur
+ help_remove( nLevel, pPred, pCur );
+ 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.
+ // try to help deleting pCur
+ help_remove( nLevel, pPred, pCur );
+ 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;
+ return ( pos.pCur = pCur.ptr()) != nullptr;
}
- /// 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.
+ bool renew_insert_position( value_type& val, node_type * pNode, position& pos )
+ {
+ node_type * pPred;
+ marked_node_ptr pSucc;
+ marked_node_ptr pCur;
+ key_comparator cmp;
- Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
+ // Hazard pointer array:
+ // pPred: [nLevel * 2]
+ // pSucc: [nLevel * 2 + 1]
- 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.
+ retry:
+ pPred = m_Head.head();
+ int nCmp = 1;
- 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
- // ...
+ 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 ( pCur.ptr() == nullptr ) {
+ // end of list at level nLevel - goto next level
+ break;
+ }
+
+ // 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
+ if ( pCur.ptr() == pNode ) {
+ // Node is removing while we are inserting it
+ return false;
+ }
+ // try to help deleting pCur
+ help_remove( nLevel, pPred, pCur );
+ 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
+ break;
+ }
}
- // Destructor of gp releases internal HP guard
- }
- \endcode
- */
- template <typename Q>
- guarded_ptr extract( Q const& key )
- {
- return extract_( key, key_comparator());
- }
- /// 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.
+ // Next level
+ pos.pPrev[nLevel] = pPred;
+ pos.pSucc[nLevel] = pCur.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 extract_with( Q const& key, Less pred )
- {
- CDS_UNUSED( pred );
- return extract_( key, cds::opt::details::make_comparator_from_less<Less>());
+ return nCmp == 0;
}
- /// 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.
+ template <typename Func>
+ bool insert_at_position( value_type& val, node_type * pNode, position& pos, Func f )
+ {
+ unsigned int const 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
+ marked_node_ptr p( pos.pSucc[0] );
+ pNode->next( 0 ).store( p, memory_model::memory_order_relaxed );
+ 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;
+
+ f( val );
}
- \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.
+ // Insert at level 1..max
+ for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
+ marked_node_ptr p;
+ while ( true ) {
+ marked_node_ptr pSucc( pos.pSucc[nLevel] );
- @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.
+ // Set pNode->next
+ // pNode->next can have "logical deleted" flag if another thread is removing pNode right now
+ if ( !pNode->next( nLevel ).compare_exchange_strong( p, pSucc,
+ memory_model::memory_order_acq_rel, atomics::memory_order_acquire ))
+ {
+ // pNode has been marked as removed while we are inserting it
+ // Stop inserting
+ assert( p.bits() != 0 );
- 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.
+ // Here pNode is linked at least level 0 so level_unlinked() cannot returns true
+ CDS_VERIFY_FALSE( pNode->level_unlinked( nHeight - nLevel ));
- 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
- //...
+ // pNode is linked up to nLevel - 1
+ // Remove it via find_position()
+ find_position( val, pos, key_comparator(), false );
+
+ m_Stat.onLogicDeleteWhileInsert();
+ return true;
+ }
+ p = pSucc;
+
+ // Link pNode into the list at nLevel
+ if ( pos.pPrev[nLevel]->next( nLevel ).compare_exchange_strong( pSucc, marked_node_ptr( pNode ),
+ memory_model::memory_order_release, atomics::memory_order_relaxed ))
+ {
+ // go to next level
+ break;
+ }
+
+ // Renew insert position
+ m_Stat.onRenewInsertPosition();
+
+ if ( !renew_insert_position( val, pNode, pos )) {
+ // The node has been deleted while we are inserting it
+ // Update current height for concurent removing
+ CDS_VERIFY_FALSE( pNode->level_unlinked( nHeight - nLevel ));
+
+ m_Stat.onRemoveWhileInsert();
+
+ // help to removing val
+ find_position( val, pos, key_comparator(), false );
+ 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;
+ back_off bkoff;
- /// 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 ) {
+ pSucc = pDel->next( nLevel ).load( memory_model::memory_order_relaxed );
+ if ( pSucc.bits() == 0 ) {
+ bkoff.reset();
+ while ( !( pDel->next( nLevel ).compare_exchange_weak( pSucc, pSucc | 1,
+ memory_model::memory_order_release, atomics::memory_order_acquire )
+ || pSucc.bits() != 0 ))
+ {
+ bkoff();
+ m_Stat.onMarkFailed();
+ }
+ }
+ }
- The \p Func interface is
- \code
- struct functor {
- void operator()( value_type const& item );
- };
- \endcode
+ marked_node_ptr p( pDel->next( 0 ).load( memory_model::memory_order_relaxed ).ptr());
+ while ( true ) {
+ if ( pDel->next( 0 ).compare_exchange_strong( p, p | 1, memory_model::memory_order_release, atomics::memory_order_acquire ))
+ {
+ 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;
- 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 );
- }
+ for ( int nLevel = static_cast<int>( pDel->height() - 1 ); nLevel >= 0; --nLevel ) {
- /// 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.
+ pSucc = pDel->next( nLevel ).load( memory_model::memory_order_acquire );
+ if ( pos.pPrev[nLevel]->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr()),
+ memory_model::memory_order_acq_rel, atomics::memory_order_relaxed ))
+ {
+ pDel->level_unlinked();
+ }
+ else {
+ // Make slow erase
+# ifdef CDS_DEBUG
+ if ( find_position( *node_traits::to_value_ptr( pDel ), pos, key_comparator(), false ))
+ assert( pDel != pos.pCur );
+# else
+ find_position( *node_traits::to_value_ptr( pDel ), pos, key_comparator(), false );
+# endif
+ m_Stat.onSlowErase();
+ return true;
+ }
+ }
- \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 );
+ // 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
+ m_Stat.onEraseContention();
+ return false;
+ }
+ m_Stat.onEraseRetry();
+ bkoff();
+ }
}
- /// 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.
+ 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;
+ marked_node_ptr pCur;
+ marked_node_ptr pNull;
- 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.
+ // guard array:
+ // 0 - pPred on level N
+ // 1 - pCur on level N
+ typename gc::template GuardArray<2> guards;
+ back_off bkoff;
+ unsigned attempt = 0;
- 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.
+ try_again:
+ 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 );
- 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
+ while ( pCur != pNull ) {
+ if ( pCur.bits()) {
+ // pPred is being removed
+ if ( ++attempt < 4 ) {
+ bkoff();
+ goto try_again;
+ }
- /// 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.
+ return find_fastpath_abort;
+ }
- \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 );
+ 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;
+ }
+ }
+ }
+ }
+
+ 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;
+
+ 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 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
+ void increase_height( unsigned int nHeight )
{
- return c_nMaxHeight;
+ 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_relaxed, atomics::memory_order_relaxed );
}
- /// Returns const reference to internal statistics
- stat const& statistics() const
+ void destroy()
{
- return m_Stat;
+ node_type* p = m_Head.head()->next( 0 ).load( atomics::memory_order_relaxed ).ptr();
+ while ( p ) {
+ node_type* pNext = p->next( 0 ).load( atomics::memory_order_relaxed ).ptr();
+ dispose_node( node_traits::to_value_ptr( p ));
+ p = pNext;
+ }
}
+
+ //@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
projects / libcds.git / blobdiff