-//$$CDS-header$$
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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/
+
+ 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_DETAILS_SKIP_LIST_BASE_H
#define CDSLIB_INTRUSIVE_DETAILS_SKIP_LIST_BASE_H
/** @ingroup cds_intrusive_helper
*/
namespace skip_list {
-
/// The maximum possible height of any skip-list
static unsigned int const c_nHeightLimit = 32;
typedef typename gc::template atomic_marked_ptr< marked_ptr> atomic_marked_ptr; ///< atomic marked pointer specific for GC
//@cond
typedef atomic_marked_ptr tower_item_type;
+
//@endcond
protected:
- atomic_marked_ptr m_pNext; ///< Next item in bottom-list (list at level 0)
- unsigned int m_nHeight; ///< Node height (size of m_arrNext array). For node at level 0 the height is 1.
- atomic_marked_ptr * m_arrNext; ///< Array of next items for levels 1 .. m_nHeight - 1. For node at level 0 \p m_arrNext is \p nullptr
+ //@cond
+ atomic_marked_ptr m_pNext; ///< Next item in bottom-list (list at level 0)
+ unsigned int m_nHeight; ///< Node height (size of \p m_arrNext array). For node at level 0 the height is 1.
+ atomic_marked_ptr * m_arrNext; ///< Array of next items for levels 1 .. m_nHeight - 1. For node at level 0 \p m_arrNext is \p nullptr
+ atomics::atomic<unsigned int> m_nUnlink; ///< Unlink helper
+ //@endcond
public:
- /// Constructs a node of height 1 (a bottom-list node)
node()
: m_pNext( nullptr )
- , m_nHeight(1)
+ , m_nHeight( 1 )
, m_arrNext( nullptr )
+ , m_nUnlink( 1 )
{}
- /// Constructs a node of height \p nHeight
+
+ /// Constructs a node's tower of height \p nHeight
void make_tower( unsigned int nHeight, atomic_marked_ptr * nextTower )
{
assert( nHeight > 0 );
- assert( (nHeight == 1 && nextTower == nullptr) // bottom-list node
- || (nHeight > 1 && nextTower != nullptr) // node at level of more than 0
+ assert( (nHeight == 1 && nextTower == nullptr) // bottom-list node
+ || (nHeight > 1 && nextTower != nullptr) // node at level of more than 0
);
m_arrNext = nextTower;
m_nHeight = nHeight;
+ m_nUnlink.store( nHeight, atomics::memory_order_relaxed );
}
//@cond
{
return m_arrNext;
}
+
+ bool has_tower() const
+ {
+ return m_nHeight > 1;
+ }
//@endcond
/// Access to element of next pointer array
atomic_marked_ptr& next( unsigned int nLevel )
{
- assert( nLevel < height() );
- assert( nLevel == 0 || (nLevel > 0 && m_arrNext != nullptr) );
+ assert( nLevel < height());
+ assert( nLevel == 0 || (nLevel > 0 && m_arrNext != nullptr));
return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
}
/// Access to element of next pointer array (const version)
atomic_marked_ptr const& next( unsigned int nLevel ) const
{
- assert( nLevel < height() );
+ assert( nLevel < height());
assert( nLevel == 0 || nLevel > 0 && m_arrNext != nullptr );
return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
}
- /// Access to element of next pointer array (same as \ref next function)
+ /// Access to element of next pointer array (synonym for \p next() function)
atomic_marked_ptr& operator[]( unsigned int nLevel )
{
return next( nLevel );
}
- /// Access to element of next pointer array (same as \ref next function)
+ /// Access to element of next pointer array (synonym for \p next() function)
atomic_marked_ptr const& operator[]( unsigned int nLevel ) const
{
return next( nLevel );
&& m_arrNext == nullptr
&& m_nHeight <= 1;
}
+
+ bool level_unlinked( unsigned nCount = 1 )
+ {
+ return m_nUnlink.fetch_sub( nCount, atomics::memory_order_relaxed ) == 1;
+ }
+
+ bool is_upper_level( unsigned nLevel ) const
+ {
+ return m_nUnlink.load( atomics::memory_order_relaxed ) == nLevel + 1;
+ }
//@endcond
};
event_counter m_nInsertSuccess ; ///< Count of success insertion
event_counter m_nInsertFailed ; ///< Count of failed insertion
event_counter m_nInsertRetries ; ///< Count of unsuccessful retries of insertion
- event_counter m_nEnsureExist ; ///< Count of \p ensure call for existed node
- event_counter m_nEnsureNew ; ///< Count of \p ensure call for new node
+ event_counter m_nUpdateExist ; ///< Count of \p update() call for existed node
+ event_counter m_nUpdateNew ; ///< Count of \p update() call for new node
event_counter m_nUnlinkSuccess ; ///< Count of successful call of \p unlink
event_counter m_nUnlinkFailed ; ///< Count of failed call of \p unlink
event_counter m_nEraseSuccess ; ///< Count of successful call of \p erase
event_counter m_nEraseFailed ; ///< Count of failed call of \p erase
+ event_counter m_nEraseRetry ; ///< Count of retries while erasing node
event_counter m_nFindFastSuccess ; ///< Count of successful call of \p find and all derivatives (via fast-path)
event_counter m_nFindFastFailed ; ///< Count of failed call of \p find and all derivatives (via fast-path)
event_counter m_nFindSlowSuccess ; ///< Count of successful call of \p find and all derivatives (via slow-path)
event_counter m_nFindSlowFailed ; ///< Count of failed call of \p find and all derivatives (via slow-path)
event_counter m_nRenewInsertPosition ; ///< Count of renewing position events while inserting
- event_counter m_nLogicDeleteWhileInsert ; ///< Count of events "The node has been logically deleted while inserting"
+ event_counter m_nLogicDeleteWhileInsert; ///< Count of events "The node has been logically deleted while inserting"
event_counter m_nNotFoundWhileInsert ; ///< Count of events "Inserting node is not found"
event_counter m_nFastErase ; ///< Fast erase event counter
event_counter m_nFastExtract ; ///< Fast extract event counter
event_counter m_nExtractMaxRetries ; ///< Count of retries of \p extract_max call
event_counter m_nEraseWhileFind ; ///< Count of erased item while searching
event_counter m_nExtractWhileFind ; ///< Count of extracted item while searching (RCU only)
+ event_counter m_nMarkFailed ; ///< Count of failed node marking (logical deletion mark)
+ event_counter m_nEraseContention ; ///< Count of key erasing contention encountered
//@cond
void onAddNode( unsigned int nHeight )
void onInsertSuccess() { ++m_nInsertSuccess ; }
void onInsertFailed() { ++m_nInsertFailed ; }
void onInsertRetry() { ++m_nInsertRetries ; }
- void onEnsureExist() { ++m_nEnsureExist ; }
- void onEnsureNew() { ++m_nEnsureNew ; }
+ void onUpdateExist() { ++m_nUpdateExist ; }
+ void onUpdateNew() { ++m_nUpdateNew ; }
void onUnlinkSuccess() { ++m_nUnlinkSuccess ; }
void onUnlinkFailed() { ++m_nUnlinkFailed ; }
void onEraseSuccess() { ++m_nEraseSuccess ; }
void onEraseFailed() { ++m_nEraseFailed ; }
+ void onEraseRetry() { ++m_nEraseRetry; }
void onFindFastSuccess() { ++m_nFindFastSuccess ; }
void onFindFastFailed() { ++m_nFindFastFailed ; }
void onFindSlowSuccess() { ++m_nFindSlowSuccess ; }
void onExtractMaxSuccess() { ++m_nExtractMaxSuccess; }
void onExtractMaxFailed() { ++m_nExtractMaxFailed; }
void onExtractMaxRetry() { ++m_nExtractMaxRetries; }
-
+ void onMarkFailed() { ++m_nMarkFailed; }
+ void onEraseContention() { ++m_nEraseContention; }
//@endcond
};
void onInsertSuccess() const {}
void onInsertFailed() const {}
void onInsertRetry() const {}
- void onEnsureExist() const {}
- void onEnsureNew() const {}
+ void onUpdateExist() const {}
+ void onUpdateNew() const {}
void onUnlinkSuccess() const {}
void onUnlinkFailed() const {}
void onEraseSuccess() const {}
void onEraseFailed() const {}
+ void onEraseRetry() const {}
void onFindFastSuccess() const {}
void onFindFastFailed() const {}
void onFindSlowSuccess() const {}
void onExtractMaxSuccess() const {}
void onExtractMaxFailed() const {}
void onExtractMaxRetry() const {}
-
+ void onMarkFailed() const {}
+ void onEraseContention() const {}
//@endcond
};
/// Item counter
/**
The type for item counting feature.
- By default, item counting is disabled (\p atomicity::empty_item_counter)
+ By default, item counting is disabled (\p atomicity::empty_item_counter),
\p atomicity::item_counter enables it.
*/
typedef atomicity::empty_item_counter item_counter;
an allocator should be provided to maintain variable randomly-calculated height of the node
since the node can contain up to 32 next pointers. The allocator option is used to allocate an array of next pointers
for nodes which height is more than 1. Default is \ref CDS_DEFAULT_ALLOCATOR.
- - \p opt::back_off - back-off strategy, default is \รง cds::backoff::Default.
+ - \p opt::back_off - back-off strategy, default is \p cds::backoff::Default.
- \p opt::stat - internal statistics. By default, it is disabled (\p skip_list::empty_stat).
To enable it use \p skip_list::stat
*/
static node_type * make_tower( node_type * pNode, unsigned int nHeight )
{
if ( nHeight > 1 )
- pNode->make_tower( nHeight, tower_allocator().NewArray( nHeight - 1, nullptr ) );
+ pNode->make_tower( nHeight, tower_allocator().NewArray( nHeight - 1, nullptr ));
return pNode;
}
projects / libcds.git / blobdiff