-//$$CDS-header$$
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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_DETAILS_SKIP_LIST_BASE_H
#define CDSLIB_INTRUSIVE_DETAILS_SKIP_LIST_BASE_H
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; ///< How many levels has been unlinked
+ //@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( 0 )
{}
- /// 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 );
}
//@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) );
-
-# ifdef CDS_THREAD_SANITIZER_ENABLED
- // TSan false positive: m_arrNext is read-only array
- CDS_TSAN_ANNOTATE_IGNORE_READS_BEGIN;
- atomic_marked_ptr& r = nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
- CDS_TSAN_ANNOTATE_IGNORE_READS_END;
- return r;
-# else
+ assert( nLevel < height());
+ assert( nLevel == 0 || (nLevel > 0 && m_arrNext != nullptr));
+
return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
-# endif
}
/// 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 );
-# ifdef CDS_THREAD_SANITIZER_ENABLED
- // TSan false positive: m_arrNext is read-only array
- CDS_TSAN_ANNOTATE_IGNORE_READS_BEGIN;
- atomic_marked_ptr const& r = nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
- CDS_TSAN_ANNOTATE_IGNORE_READS_END;
- return r;
-# else
return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
-# endif
}
- /// 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_add( nCount, std::memory_order_relaxed ) + 1 == height();
+ }
//@endcond
};
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_nEraseWhileInsert ; ///< Count of events "The node has been disposed 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_nFastEraseHelped ; ///< Fast erase with helping of other thread
event_counter m_nFastExtract ; ///< Fast extract event counter
+ event_counter m_nFastExtractHelped ; ///< Fast extract with helping of other thread
event_counter m_nSlowErase ; ///< Slow erase event counter
event_counter m_nSlowExtract ; ///< Slow extract event counter
event_counter m_nExtractSuccess ; ///< Count of successful call of \p extract
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 onEraseWhileInsert() { ++m_nEraseWhileInsert; }
void onNotFoundWhileInsert() { ++m_nNotFoundWhileInsert; }
void onFastErase() { ++m_nFastErase; }
+ void onFastEraseHelped() { ++m_nFastEraseHelped; }
void onFastExtract() { ++m_nFastExtract; }
+ void onFastExtractHelped() { ++m_nFastExtractHelped; }
void onSlowErase() { ++m_nSlowErase; }
void onSlowExtract() { ++m_nSlowExtract; }
void onExtractSuccess() { ++m_nExtractSuccess; }
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 onEraseWhileInsert() const {}
void onNotFoundWhileInsert() const {}
void onFastErase() const {}
+ void onFastEraseHelped() const {}
void onFastExtract() const {}
+ void onFastExtractHelped() const {}
void onSlowErase() const {}
void onSlowExtract() const {}
void onExtractSuccess() 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