/*
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/
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;
- atomics::atomic_thread_fence( atomics::memory_order_release );
+ m_nUnlink.store( nHeight, atomics::memory_order_release );
}
//@cond
assert( nLevel < height());
assert( nLevel == 0 || (nLevel > 0 && m_arrNext != nullptr));
- return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
+ 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)
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 (synonym for \p next() function)
&& 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_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 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 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
};
See \p skip_list::random_level_generator option setter.
*/
- typedef turbo_pascal random_level_generator;
+ typedef turbo32 random_level_generator;
/// Allocator
/**
To enable it use \p atomicity::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
projects / libcds.git / blobdiff