-//$$CDS-header$$
+/*
+ This file is a part of libcds - Concurrent Data Structures library
-#ifndef __CDS_INTRUSIVE_DETAILS_SKIP_LIST_BASE_H
-#define __CDS_INTRUSIVE_DETAILS_SKIP_LIST_BASE_H
+ (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
#include <cds/intrusive/details/base.h>
#include <cds/details/marked_ptr.h>
/** @ingroup cds_intrusive_helper
*/
namespace skip_list {
-
/// The maximum possible height of any skip-list
static unsigned int const c_nHeightLimit = 32;
- \p Tag - a \ref cds_intrusive_hook_tag "tag"
*/
template <class GC, typename Tag = opt::none>
- class node
+ class node
{
public:
typedef GC gc; ///< Garbage collector
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.store( 1, atomics::memory_order_release );
+ }
- /// 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_release );
}
//@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) );
-
- return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
+ assert( nLevel < height());
+ assert( nLevel == 0 || (nLevel > 0 && m_arrNext != nullptr));
+
+ if ( nLevel ) {
+ // TSan: data race between m_arrNext[ nLevel - 1 ] and make_tower()
+ // In fact, m_arrNext is a const array that is never changed
+ CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &m_arrNext[ nLevel - 1 ] );
+ return m_arrNext[nLevel - 1];
+ }
+ return 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;
+ if ( nLevel ) {
+ CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &m_arrNext[nLevel - 1] );
+ return m_arrNext[nLevel - 1];
+ }
+ return 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
};
The generator produces a number from range <tt>[0 .. c_nUpperBound)</tt> (upper bound excluded).
\p c_nUpperBound must be no more than 32.
- <tt>random_generator()</tt> - the constructor of generator object initialises the generator instance (its internal state).
- - <tt>unsigned int operator()()</tt> - the main generating function. Returns random level from range 0..31.
+ - <tt>unsigned int operator()()</tt> - the main generating function. Returns random level from range <tt>[0 .. c_nUpperBound - 1]</tt>
+
Stateful generators are supported.
Available \p Type implementations:
- - \p skip_list::xorshift
- - \p skip_list::turbo_pascal
+ - \p skip_list::xor_shift
+ - \p skip_list::turbo
*/
template <typename Type>
struct random_level_generator {
/// Xor-shift random level generator
/**
- The simplest of the generators described in George
- Marsaglia's "Xorshift RNGs" paper. This is not a high-quality
- generator but is acceptable for skip-list.
+ The simplest of the generators described in George Marsaglia's "Xorshift RNGs" paper.
+ This is not a high-quality generator but is acceptable for skip-list.
- The random generator should return numbers from range [0..31].
+ The random generator should return numbers from range [0 .. MaxHeight - 1].
From Doug Lea's ConcurrentSkipListMap.java.
*/
- class xorshift {
+ template <unsigned MaxHeight>
+ class xor_shift {
//@cond
atomics::atomic<unsigned int> m_nSeed;
+
+ static_assert( MaxHeight > 1, "MaxHeight" );
+ static_assert( MaxHeight <= c_nHeightLimit, "MaxHeight is too large" );
+ static unsigned int const c_nBitMask = (1u << ( MaxHeight - 1 )) - 1;
//@endcond
+
public:
/// The upper bound of generator's return value. The generator produces random number in range <tt>[0..c_nUpperBound)</tt>
- static unsigned int const c_nUpperBound = c_nHeightLimit;
+ static unsigned int const c_nUpperBound = MaxHeight;
/// Initializes the generator instance
- xorshift()
+ xor_shift()
{
m_nSeed.store( (unsigned int) cds::OS::Timer::random_seed(), atomics::memory_order_relaxed );
}
x ^= x >> 17;
x ^= x << 5;
m_nSeed.store( x, atomics::memory_order_relaxed );
- unsigned int nLevel = ((x & 0x00000001) != 0) ? 0 : cds::bitop::LSB( (~(x >> 1)) & 0x7FFFFFFF );
+ unsigned int nLevel = ((x & 0x00000001) != 0) ? 0 : cds::bitop::LSB( (~(x >> 1)) & c_nBitMask );
+
assert( nLevel < c_nUpperBound );
return nLevel;
}
};
+ /// Xor-shift random level generator, max height 32
+ typedef xor_shift<c_nHeightLimit> xorshift32;
+
+ //@cond
+ // For backward compatibility
+ typedef xorshift32 xorshift;
+ //@endcond
+
+ /// \ref xor_shift generator, max height 24
+ typedef xor_shift< 24 > xorshift24;
+
+ /// \ref xor_shift generator, max height = 16
+ typedef xor_shift< 16 > xorshift16;
+
/// Turbo-pascal random level generator
/**
This uses a cheap pseudo-random function that was used in Turbo Pascal.
From Doug Lea's ConcurrentSkipListMap.java.
*/
- class turbo_pascal
+ template <unsigned MaxHeight>
+ class turbo
{
//@cond
atomics::atomic<unsigned int> m_nSeed;
+
+ static_assert( MaxHeight > 1, "MaxHeight" );
+ static_assert( MaxHeight <= c_nHeightLimit, "MaxHeight is too large" );
+ static unsigned int const c_nBitMask = (1u << ( MaxHeight - 1 )) - 1;
//@endcond
public:
/// The upper bound of generator's return value. The generator produces random number in range <tt>[0..c_nUpperBound)</tt>
- static unsigned int const c_nUpperBound = c_nHeightLimit;
+ static unsigned int const c_nUpperBound = MaxHeight;
/// Initializes the generator instance
- turbo_pascal()
+ turbo()
{
m_nSeed.store( (unsigned int) cds::OS::Timer::random_seed(), atomics::memory_order_relaxed );
}
*/
unsigned int x = m_nSeed.load( atomics::memory_order_relaxed ) * 134775813 + 1;
m_nSeed.store( x, atomics::memory_order_relaxed );
- unsigned int nLevel = ( x & 0x80000000 ) ? (31 - cds::bitop::MSBnz( (x & 0x7FFFFFFF) | 1 )) : 0;
+ unsigned int nLevel = ( x & 0x80000000 ) ? ( c_nUpperBound - 1 - cds::bitop::MSBnz( (x & c_nBitMask ) | 1 )) : 0;
+
assert( nLevel < c_nUpperBound );
return nLevel;
}
};
+ /// Turbo-Pascal random level generator, max height 32
+ typedef turbo<c_nHeightLimit> turbo32;
+
+ //@cond
+ // For backward compatibility
+ typedef turbo32 turbo_pascal;
+ //@endcond
+
+ /// Turbo-Pascal generator, max height 24
+ typedef turbo< 24 > turbo24;
+
+ /// Turbo-Pascal generator, max height 16
+ typedef turbo< 16 > turbo16;
+
/// \p SkipListSet internal statistics
template <typename EventCounter = cds::atomicity::event_counter>
struct stat {
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_nNotFoundWhileInsert ; ///< Count of events "Inserting node is not found"
+ event_counter m_nLogicDeleteWhileInsert; ///< Count of events "The node has been logically deleted while inserting"
+ event_counter m_nRemoveWhileInsert ; ///< Count of evnts "The node is removing while inserting"
event_counter m_nFastErase ; ///< Fast erase event counter
event_counter m_nFastExtract ; ///< Fast extract event counter
event_counter m_nSlowErase ; ///< Slow erase 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 onExtractWhileFind() { ++m_nExtractWhileFind ; }
void onRenewInsertPosition() { ++m_nRenewInsertPosition; }
void onLogicDeleteWhileInsert() { ++m_nLogicDeleteWhileInsert; }
- void onNotFoundWhileInsert() { ++m_nNotFoundWhileInsert; }
+ void onRemoveWhileInsert() { ++m_nRemoveWhileInsert; }
void onFastErase() { ++m_nFastErase; }
void onFastExtract() { ++m_nFastExtract; }
void onSlowErase() { ++m_nSlowErase; }
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 onExtractWhileFind() const {}
void onRenewInsertPosition() const {}
void onLogicDeleteWhileInsert() const {}
- void onNotFoundWhileInsert() const {}
+ void onRemoveWhileInsert() const {}
void onFastErase() const {}
void onFastExtract() const {}
void onSlowErase() 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)
- \p atomicity::item_counter enables it.
+ By default, item counting is disabled (\p atomicity::empty_item_counter),
+ \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter enables it.
*/
typedef atomicity::empty_item_counter item_counter;
See \p skip_list::random_level_generator option setter.
*/
- typedef turbo_pascal random_level_generator;
+ typedef turbo32 random_level_generator;
/// Allocator
/**
- \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. Due the nature
of GC schema the disposer may be called asynchronously.
- \p opt::item_counter - the type of item counting feature. Default is disabled, i.e. \p atomicity::empty_item_counter.
- To enable it use \p atomicity::item_counter
+ To enable it use \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter
- \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
or \p opt::v::sequential_consistent (sequentially consisnent memory model).
- - \p skip_list::random_level_generator - random level generator. Can be \p skip_list::xorshift,
- \p skip_list::turbo_pascal (the default) or
- user-provided one. See \p skip_list::random_level_generator option description for explanation.
+ - \p skip_list::random_level_generator - random level generator. Can be \p skip_list::xor_shift,
+ \p skip_list::turbo32 (the default) or user-provided one.
+ See \p skip_list::random_level_generator option description for explanation.
- \p opt::allocator - although the skip-list is an intrusive container,
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;
}
}} // namespace cds::intrusive
-#endif // #ifndef __CDS_INTRUSIVE_DETAILS_SKIP_LIST_BASE_H
+#endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_SKIP_LIST_BASE_H