-//$$CDS-header$$
+/*
+ This file is a part of libcds - Concurrent Data Structures library
-#ifndef __CDS_INTRUSIVE_IMPL_SKIP_LIST_H
-#define __CDS_INTRUSIVE_IMPL_SKIP_LIST_H
+ (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+
+ Source code repo: http://github.com/khizmax/libcds/
+ Download: http://sourceforge.net/projects/libcds/files/
+
+ Redistribution and use in source and binary forms, with or without
+ modification, are permitted provided that the following conditions are met:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#ifndef CDSLIB_INTRUSIVE_IMPL_SKIP_LIST_H
+#define CDSLIB_INTRUSIVE_IMPL_SKIP_LIST_H
#include <type_traits>
#include <memory>
#include <cds/intrusive/details/skip_list_base.h>
#include <cds/opt/compare.h>
#include <cds/details/binary_functor_wrapper.h>
-#include <cds/gc/guarded_ptr.h>
namespace cds { namespace intrusive {
protected:
static value_type * gc_protect( marked_ptr p )
{
- return node_traits::to_value_ptr( p.ptr() );
+ return node_traits::to_value_ptr( p.ptr());
}
void next()
back_off bkoff;
for (;;) {
- if ( m_pNode->next( m_pNode->height() - 1 ).load( atomics::memory_order_acquire ).bits() ) {
+ if ( m_pNode->next( m_pNode->height() - 1 ).load( atomics::memory_order_acquire ).bits()) {
// Current node is marked as deleted. So, its next pointer can point to anything
// In this case we interrupt our iteration and returns end() iterator.
*this = iterator();
marked_ptr p = m_guard.protect( (*m_pNode)[0], gc_protect );
node_type * pp = p.ptr();
- if ( p.bits() ) {
+ if ( p.bits()) {
// p is marked as deleted. Spin waiting for physical removal
bkoff();
continue;
}
- else if ( pp && pp->next( pp->height() - 1 ).load( atomics::memory_order_relaxed ).bits() ) {
+ else if ( pp && pp->next( pp->height() - 1 ).load( atomics::memory_order_relaxed ).bits()) {
// p is marked as deleted. Spin waiting for physical removal
bkoff();
continue;
for (;;) {
marked_ptr p = m_guard.protect( refHead[0], gc_protect );
- if ( !p.ptr() ) {
+ if ( !p.ptr()) {
// empty skip-list
m_guard.clear();
break;
node_type * pp = p.ptr();
// Logically deleted node is marked from highest level
- if ( !pp->next( pp->height() - 1 ).load( atomics::memory_order_acquire ).bits() ) {
+ if ( !pp->next( pp->height() - 1 ).load( atomics::memory_order_acquire ).bits()) {
m_pNode = pp;
break;
}
iterator( iterator const& s)
: m_pNode( s.m_pNode )
{
- m_guard.assign( node_traits::to_value_ptr(m_pNode) );
+ m_guard.assign( node_traits::to_value_ptr(m_pNode));
}
value_type * operator ->() const
- \p T - type to be stored in the list. The type must be based on \p skip_list::node (for \p skip_list::base_hook)
or it must have a member of type \p skip_list::node (for \p skip_list::member_hook).
- \p Traits - skip-list traits, default is \p skip_list::traits.
- It is possible to declare option-based list with \p cds::intrusive::skip_list::make_traits metafunction istead of \p Traits
+ It is possible to declare option-based list with \p cds::intrusive::skip_list::make_traits metafunction istead of \p Traits
template argument.
@warning The skip-list requires up to 67 hazard pointers that may be critical for some GCs for which
typedef typename traits::stat stat; ///< internal statistics type
public:
- typedef cds::gc::guarded_ptr< gc, value_type > guarded_ptr; ///< Guarded pointer
+ typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
/// Max node height. The actual node height should be in range <tt>[0 .. c_nMaxHeight)</tt>
/**
static unsigned int const c_nMinHeight = 5;
//@endcond
+ // 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
+
protected:
typedef typename node_type::atomic_marked_ptr atomic_node_ptr; ///< Atomic marked node pointer
typedef typename node_type::marked_ptr marked_node_ptr; ///< Node marked pointer
typedef std::unique_ptr< node_type, typename node_builder::node_disposer > scoped_node_ptr;
- // c_nMaxHeight * 2 - pPred/pSucc guards
- // + 1 - for erase, unlink
- // + 1 - for clear
- static size_t const c_nHazardPtrCount = c_nMaxHeight * 2 + 2;
struct position {
node_type * pPrev[ c_nMaxHeight ];
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 ensure()
+ node_type * pCur; // guarded by guards; needed only for \p update()
};
//@endcond
static value_type * gc_protect( marked_node_ptr p )
{
- return node_traits::to_value_ptr( p.ptr() );
+ return node_traits::to_value_ptr( p.ptr());
}
static void dispose_node( value_type * pVal )
{
assert( pVal != nullptr );
- typename node_builder::node_disposer()( node_traits::to_node_ptr(pVal) );
+ typename node_builder::node_disposer()( node_traits::to_node_ptr(pVal));
disposer()( pVal );
}
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() ) {
+ if ( pCur.bits()) {
// pCur.bits() means that pPred is logically deleted
goto retry;
}
}
// pSucc contains deletion mark for pCur
- pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
+ pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
- if ( pPred->next( nLevel ).load( memory_model::memory_order_relaxed ).all() != pCur.ptr() )
+ if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr())
goto retry;
- if ( pSucc.bits() ) {
+ 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_release, atomics::memory_order_relaxed ))
+ 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 );
+ gc::retire( node_traits::to_value_ptr( pCur.ptr()), dispose_node );
m_Stat.onEraseWhileFind();
}
}
// head cannot be deleted
assert( pCur.bits() == 0 );
- if ( pCur.ptr() ) {
+ if ( pCur.ptr()) {
// pSucc contains deletion mark for pCur
- pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
+ pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
- if ( pPred->next( nLevel ).load( memory_model::memory_order_relaxed ).all() != pCur.ptr() )
+ if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr())
goto retry;
- if ( pSucc.bits() ) {
+ 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_release, atomics::memory_order_relaxed ))
+ 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 );
+ if ( nLevel == 0 ) {
+ gc::retire( node_traits::to_value_ptr( pCur.ptr()), dispose_node );
+ m_Stat.onEraseWhileFind();
+ }
}
goto retry;
}
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() ) {
+ if ( pCur.bits()) {
// pCur.bits() means that pPred is logically deleted
goto retry;
}
}
// pSucc contains deletion mark for pCur
- pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
+ pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
- if ( pPred->next( nLevel ).load( memory_model::memory_order_relaxed ).all() != pCur.ptr() )
+ if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr())
goto retry;
- if ( pSucc.bits() ) {
+ 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_release, atomics::memory_order_relaxed ))
+ 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 );
+ if ( nLevel == 0 ) {
+ gc::retire( node_traits::to_value_ptr( pCur.ptr()), dispose_node );
+ m_Stat.onEraseWhileFind();
+ }
}
goto retry;
}
else {
- if ( !pSucc.ptr() )
+ if ( !pSucc.ptr())
break;
pPred = pCur.ptr();
for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel )
pNode->next(nLevel).store( marked_node_ptr(), memory_model::memory_order_relaxed );
+ // 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 ) ) {
+ 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 );
}
+ // Insert at level 1..max
for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
marked_node_ptr p;
while ( true ) {
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() );
+ 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 ) )
+ if ( pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( q, marked_node_ptr( pNode ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
break;
// Renew insert position
assert( pDel != nullptr );
marked_node_ptr pSucc;
- typename gc::Guard gSucc;
// logical deletion (marking)
for ( unsigned int nLevel = pDel->height() - 1; nLevel > 0; --nLevel ) {
while ( true ) {
- pSucc = gSucc.protect( pDel->next(nLevel), gc_protect );
+ pSucc = pDel->next(nLevel);
if ( pSucc.bits() || pDel->next(nLevel).compare_exchange_weak( pSucc, pSucc | 1,
- memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
+ memory_model::memory_order_release, atomics::memory_order_relaxed ))
{
break;
}
}
while ( true ) {
- pSucc = gSucc.protect( pDel->next(0), gc_protect );
- marked_node_ptr p( pSucc.ptr() );
- if ( pDel->next(0).compare_exchange_strong( p, marked_node_ptr(p.ptr(), 1),
- memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
+ 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 ));
// try fast erase
p = pDel;
for ( int nLevel = static_cast<int>( pDel->height() - 1 ); nLevel >= 0; --nLevel ) {
- pSucc = gSucc.protect( pDel->next(nLevel), gc_protect );
+ 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_release, atomics::memory_order_relaxed) )
+ memory_model::memory_order_acquire, atomics::memory_order_relaxed))
{
// Make slow erase
find_position( *node_traits::to_value_ptr( pDel ), pos, key_comparator(), false );
return true;
}
else {
- if ( p.bits() ) {
+ if ( p.bits()) {
+ // Another thread is deleting pDel right now
return false;
}
}
+ m_Stat.onEraseRetry();
}
}
continue;
while ( pCur != pNull ) {
- if ( pCur.bits() ) {
+ if ( pCur.bits()) {
unsigned int nAttempt = 0;
while ( pCur.bits() && nAttempt++ < 16 ) {
bkoff();
}
bkoff.reset();
- if ( pCur.bits() ) {
+ if ( pCur.bits()) {
// Maybe, we are on deleted node sequence
// Abort searching, try slow-path
return find_fastpath_abort;
}
}
- if ( pCur.ptr() ) {
- int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
+ if ( pCur.ptr()) {
+ int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
if ( nCmp < 0 ) {
guards.copy( 0, 1 );
pPred = pCur.ptr();
}
else if ( nCmp == 0 ) {
// found
- f( *node_traits::to_value_ptr( pCur.ptr() ), val );
+ f( *node_traits::to_value_ptr( pCur.ptr()), val );
return find_fastpath_found;
}
else // pCur > val - go down
}
template <typename Q, typename Compare>
- bool get_with_( typename gc::Guard& guard, Q const& val, Compare cmp )
+ guarded_ptr get_with_( Q const& val, Compare cmp )
{
- return find_with_( val, cmp, [&guard](value_type& found, Q const& ) { guard.assign(&found); } );
+ guarded_ptr gp;
+ if ( find_with_( val, cmp, [&gp](value_type& found, Q const& ) { gp.reset(&found); } ))
+ return gp;
+ return guarded_ptr();
}
template <typename Q, typename Compare, typename Func>
{
position pos;
- if ( !find_position( val, pos, cmp, false ) ) {
+ 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) );
+ gDel.assign( node_traits::to_value_ptr(pDel));
assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
unsigned int nHeight = pDel->height();
}
template <typename Q, typename Compare>
- bool extract_( typename gc::Guard& guard, Q const& val, Compare cmp )
+ guarded_ptr extract_( Q const& val, Compare cmp )
{
position pos;
+ guarded_ptr gp;
for (;;) {
- if ( !find_position( val, pos, cmp, false ) ) {
+ if ( !find_position( val, pos, cmp, false )) {
m_Stat.onExtractFailed();
- return false;
+ return guarded_ptr();
}
node_type * pDel = pos.pCur;
- guard.assign( node_traits::to_value_ptr(pDel));
+ gp.reset( node_traits::to_value_ptr( pDel ));
assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
unsigned int nHeight = pDel->height();
--m_ItemCounter;
m_Stat.onRemoveNode( nHeight );
m_Stat.onExtractSuccess();
- return true;
+ return gp;
}
-
m_Stat.onExtractRetry();
}
}
- bool extract_min_( typename gc::Guard& gDel )
+ guarded_ptr extract_min_()
{
position pos;
+ guarded_ptr gp;
for (;;) {
- if ( !find_min_position( pos ) ) {
+ if ( !find_min_position( pos )) {
// The list is empty
m_Stat.onExtractMinFailed();
- return false;
+ return guarded_ptr();
}
node_type * pDel = pos.pCur;
unsigned int nHeight = pDel->height();
- gDel.assign( node_traits::to_value_ptr(pDel) );
+ 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 true;
+ return gp;
}
m_Stat.onExtractMinRetry();
}
}
- bool extract_max_( typename gc::Guard& gDel )
+ guarded_ptr extract_max_()
{
position pos;
+ guarded_ptr gp;
for (;;) {
- if ( !find_max_position( pos ) ) {
+ if ( !find_max_position( pos )) {
// The list is empty
m_Stat.onExtractMaxFailed();
- return false;
+ return guarded_ptr();
}
node_type * pDel = pos.pCur;
unsigned int nHeight = pDel->height();
- gDel.assign( node_traits::to_value_ptr(pDel) );
+ 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 true;
+ return gp;
}
m_Stat.onExtractMaxRetry();
}
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.
+
+ @warning Use this iterator on the concurrent container for debugging purpose only.
+
+ The iterator interface:
+ \code
+ class iterator {
+ public:
+ // Default constructor
+ iterator();
+
+ // Copy construtor
+ iterator( iterator const& src );
+
+ // Dereference operator
+ value_type * operator ->() const;
+
+ // Dereference operator
+ value_type& operator *() const;
+
+ // Preincrement operator
+ iterator& operator ++();
+
+ // Assignment operator
+ iterator& operator = (iterator const& src);
+
+ // 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;
/// Const iterator type
/// Returns a forward iterator addressing the first element in a set
iterator begin()
{
- return iterator( *m_Head.head() );
+ return iterator( *m_Head.head());
}
/// Returns a forward const iterator addressing the first element in a set
const_iterator begin() const
{
- return const_iterator( *m_Head.head() );
+ 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() );
+ return const_iterator( *m_Head.head());
}
/// Returns a forward iterator that addresses the location succeeding the last element in a set.
{
return const_iterator();
}
+ //@}
public:
/// Inserts new node
position pos;
while ( true )
{
- bool bFound = find_position( val, pos, key_comparator(), true );
- if ( bFound ) {
+ if ( find_position( val, pos, key_comparator(), true )) {
// scoped_node_ptr deletes the node tower if we create it
if ( !bTowerMade )
scp.release();
}
}
- /// Ensures that the \p val exists in the set
+ /// 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.
+ 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 signature is:
+ 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 ensure function
+ - \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.
- Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
+ 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 is in the set.
+ already exists.
@warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
*/
template <typename Func>
- std::pair<bool, bool> ensure( value_type& val, Func func )
+ std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
{
typename gc::Guard gNew;
gNew.assign( &val );
scp.release();
func( false, *node_traits::to_value_ptr(pos.pCur), val );
- m_Stat.onEnsureExist();
+ m_Stat.onUpdateExist();
return std::make_pair( true, false );
}
+ if ( !bInsert ) {
+ scp.release();
+ return std::make_pair( false, false );
+ }
+
if ( !bTowerOk ) {
build_node( pNode );
nHeight = pNode->height();
++m_ItemCounter;
scp.release();
m_Stat.onAddNode( nHeight );
- m_Stat.onEnsureNew();
+ m_Stat.onUpdateNew();
return std::make_pair( true, true );
}
}
+ //@cond
+ template <typename Func>
+ CDS_DEPRECATED("ensure() is deprecated, use update()")
+ std::pair<bool, bool> ensure( value_type& val, Func func )
+ {
+ return update( val, func, true );
+ }
+ //@endcond
/// Unlinks the item \p val from the set
/**
{
position pos;
- if ( !find_position( val, pos, key_comparator(), false ) ) {
+ if ( !find_position( val, pos, key_comparator(), false )) {
m_Stat.onUnlinkFailed();
return false;
}
unsigned int nHeight = pDel->height();
typename gc::Guard gDel;
- gDel.assign( node_traits::to_value_ptr(pDel) );
+ gDel.assign( node_traits::to_value_ptr(pDel));
if ( node_traits::to_value_ptr( pDel ) == &val && try_remove_at( pDel, pos, [](value_type const&) {} )) {
--m_ItemCounter;
/// 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 in \p dest parameter.
- If the item with key equal to \p key is not found the function returns \p false.
+ 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 \ref disposer specified in \p Traits class template parameter is called automatically
+ 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.
skip_list theList;
// ...
{
- skip_list::guarded_ptr gp;
- theList.extract( gp, 5 );
- // Deal with gp
- // ...
-
+ skip_list::guarded_ptr gp(theList.extract( 5 ));
+ if ( gp ) {
+ // Deal with gp
+ // ...
+ }
// Destructor of gp releases internal HP guard
}
\endcode
*/
template <typename Q>
- bool extract( guarded_ptr& dest, Q const& key )
+ guarded_ptr extract( Q const& key )
{
- return extract_( dest.guard(), key, key_comparator() );
+ return extract_( key, key_comparator());
}
/// Extracts the item from the set with comparing functor \p pred
\p pred must imply the same element order as the comparator used for building the set.
*/
template <typename Q, typename Less>
- bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
+ guarded_ptr extract_with( Q const& key, Less pred )
{
- return extract_( dest.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
+ 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 the item found in \p dest parameter.
- If the skip-list is empty the function returns \p false.
+ 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.
skip_list theList;
// ...
{
- skip_list::guarded_ptr gp;
- if ( theList.extract_min( gp )) {
+ skip_list::guarded_ptr gp(theList.extract_min());
+ if ( gp ) {
// Deal with gp
//...
}
}
\endcode
*/
- bool extract_min( guarded_ptr& dest)
+ guarded_ptr extract_min()
{
- return extract_min_( dest.guard() );
+ 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 found in \p dest parameter.
- If the skip-list is empty the function returns empty \p guarded_ptr.
+ 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.
@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.
skip_list theList;
// ...
{
- skip_list::guarded_ptr gp;
- if ( theList.extract_max( gp )) {
+ skip_list::guarded_ptr gp( theList.extract_max( gp ));
+ if ( gp ) {
// Deal with gp
//...
}
}
\endcode
*/
- bool extract_max( guarded_ptr& dest )
+ guarded_ptr extract_max()
{
- return extract_max_( dest.guard() );
+ return extract_max_();
}
/// Deletes the item from 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 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 );
}
{
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
/// Finds the key \p key with \p pred predicate for comparing
/**
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 );
+ }
+ //@cond
+ template <typename Q, typename Less, typename Func>
+ bool find_with( Q const& key, Less pred, Func f )
+ {
+ CDS_UNUSED( pred );
return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
}
+ //@endcond
- /// Finds \p key
- /** \anchor cds_intrusive_SkipListSet_hp_find_val
+ /// 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.
-
- 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>
- bool find( Q const& key )
+ bool contains( Q const& key )
{
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
- /// Finds \p key with comparing functor \p pred
+ /// Checks whether the set contains \p key using \p pred predicate for searching
/**
- The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_val "find(Q const&)"
- but \p pred is used for comparing the keys.
- \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.
+ 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 find_with( Q const& key, Less pred )
+ 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
/// 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 assigns the item found to guarded pointer \p ptr.
- The function returns \p true if \p key is found, and \p false otherwise.
- If \p key is not found the \p ptr parameter is not changed.
+ 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 \ref disposer specified in \p Traits class template parameter is called
+ 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.
skip_list theList;
// ...
{
- skip_list::guarded_ptr gp;
- if ( theList.get( gp, 5 )) {
+ skip_list::guarded_ptr gp(theList.get( 5 ));
+ if ( gp ) {
// Deal with gp
//...
}
should accept a parameter of type \p Q that can be not the same as \p value_type.
*/
template <typename Q>
- bool get( guarded_ptr& ptr, Q const& key )
+ guarded_ptr get( Q const& key )
{
- return get_with_( ptr.guard(), key, key_comparator() );
+ return get_with_( key, key_comparator());
}
/// Finds \p key and return the item found
/**
- The function is an analog of \ref cds_intrusive_SkipListSet_hp_get "get( guarded_ptr& ptr, Q const&)"
+ The function is an analog of \ref cds_intrusive_SkipListSet_hp_get "get( Q const&)"
but \p pred is used for comparing the keys.
\p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
\p pred must imply the same element order as the comparator used for building the set.
*/
template <typename Q, typename Less>
- bool get_with( guarded_ptr& ptr, Q const& key, Less pred )
+ guarded_ptr get_with( Q const& key, Less pred )
{
- return get_with_( ptr.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
+ CDS_UNUSED( pred );
+ return get_with_( key, cds::opt::details::make_comparator_from_less<Less>());
}
/// Returns item count in the set
this sequence
\code
set.clear();
- assert( set.empty() );
+ assert( set.empty());
\endcode
the assertion could be raised.
*/
void clear()
{
- guarded_ptr gp;
- while ( extract_min( gp ));
+ while ( extract_min_());
}
/// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
}} // namespace cds::intrusive
-#endif // #ifndef __CDS_INTRUSIVE_IMPL_SKIP_LIST_H
+#endif // #ifndef CDSLIB_INTRUSIVE_IMPL_SKIP_LIST_H
projects / libcds.git / blobdiff