-//$$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-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
#include <cds/intrusive/details/base.h>
#include <cds/details/marked_ptr.h>
#include <cds/os/timer.h>
#include <cds/urcu/options.h>
-
namespace cds { namespace intrusive {
/// SkipListSet related definitions
/** @ingroup cds_intrusive_helper
*/
namespace skip_list {
-
/// The maximum possible height of any skip-list
static unsigned int const c_nHeightLimit = 32;
/// Skip list node
/**
Template parameters:
- - GC - garbage collector
- - Tag - a tag used to distinguish between different implementation. An incomplete type may be used as a tag.
+ - \p GC - garbage collector
+ - \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 Tag tag ; ///< tag
+ typedef GC gc; ///< Garbage collector
+ typedef Tag tag; ///< tag
- typedef cds::details::marked_ptr<node, 1> marked_ptr ; ///< marked pointer
- typedef typename gc::template atomic_marked_ptr< marked_ptr> atomic_marked_ptr ; ///< atomic marked pointer specific for GC
+ typedef cds::details::marked_ptr<node, 1> marked_ptr; ///< marked pointer
+ 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 );
{
return m_pNext == atomic_marked_ptr()
&& m_arrNext == nullptr
- && m_nHeight <= 1
-;
+ && 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
};
/// Base hook
/**
\p Options are:
- - opt::gc - garbage collector used.
- - opt::tag - a tag
+ - \p opt::gc - garbage collector
+ - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
*/
template < typename... Options >
struct base_hook: public hook< opt::base_hook_tag, Options... >
Use \p offsetof macro to define \p MemberOffset
\p Options are:
- - opt::gc - garbage collector used.
- - opt::tag - a tag
+ - \p opt::gc - garbage collector
+ - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
*/
template < size_t MemberOffset, typename... Options >
struct member_hook: public hook< opt::member_hook_tag, Options... >
See \ref node_traits for \p NodeTraits interface description
\p Options are:
- - opt::gc - garbage collector used.
- - opt::tag - a tag
+ - \p opt::gc - garbage collector
+ - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
*/
template <typename NodeTraits, typename... Options >
struct traits_hook: public hook< opt::traits_hook_tag, Options... >
Stateful generators are supported.
Available \p Type implementations:
- - \ref xorshift
- - \ref turbo_pascal
+ - \p skip_list::xorshift
+ - \p skip_list::turbo_pascal
*/
template <typename Type>
struct random_level_generator {
}
};
- /// SkipListSet internal statistics
+ /// \p SkipListSet internal statistics
template <typename EventCounter = cds::atomicity::event_counter>
struct stat {
typedef EventCounter event_counter ; ///< Event counter type
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
};
- /// SkipListSet empty internal statistics
+ /// \p SkipListSet empty internal statistics
struct empty_stat {
//@cond
- void onAddNode( unsigned int nHeight ) const {}
- void onRemoveNode( unsigned int nHeight ) const {}
+ void onAddNode( unsigned int /*nHeight*/ ) const {}
+ void onRemoveNode( unsigned int /*nHeight*/ ) const {}
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
};
};
//@endcond
- /// Type traits for SkipListSet class
- struct type_traits
+ /// \p SkipListSet traits
+ struct traits
{
/// Hook used
/**
- Possible values are: skip_list::base_hook, skip_list::member_hook, skip_list::traits_hook.
+ Possible values are: \p skip_list::base_hook, \p skip_list::member_hook, \p skip_list::traits_hook.
*/
typedef base_hook<> hook;
/// Disposer
/**
- The functor used for dispose removed items. Default is opt::v::empty_disposer.
+ The functor used for dispose removed items. Default is \p opt::v::empty_disposer.
*/
typedef opt::v::empty_disposer disposer;
/// Item counter
/**
The type for item counting feature.
- Default is no item counter (\ref 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;
/// C++ memory ordering model
/**
- List of available memory ordering see opt::memory_model
+ List of available memory ordering see \p opt::memory_model
*/
typedef opt::v::relaxed_ordering memory_model;
where half of the nodes that have level \p i pointers also have level <tt>i+1</tt> pointers
(i = 0..30). So, the height of a node is in range [0..31].
- See skip_list::random_level_generator option setter.
+ See \p skip_list::random_level_generator option setter.
*/
typedef turbo_pascal random_level_generator;
*/
typedef CDS_DEFAULT_ALLOCATOR allocator;
- /// back-off strategy used
+ /// back-off strategy
/**
- If the option is not specified, the cds::backoff::Default is used.
+ If the option is not specified, the \p cds::backoff::Default is used.
*/
typedef cds::backoff::Default back_off;
/// Internal statistics
+ /**
+ By default, internal statistics is disabled (\p skip_list::empty_stat).
+ Use \p skip_list::stat to enable it.
+ */
typedef empty_stat stat;
/// RCU deadlock checking policy (only for \ref cds_intrusive_SkipListSet_rcu "RCU-based SkipListSet")
/**
- List of available options see opt::rcu_check_deadlock
+ List of available options see \p opt::rcu_check_deadlock
*/
typedef opt::v::rcu_throw_deadlock rcu_check_deadlock;
//@endcond
};
- /// Metafunction converting option list to SkipListSet traits
+ /// Metafunction converting option list to \p SkipListSet traits
/**
- This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
- \p Options list see \ref SkipListSet.
+ \p Options are:
+ - \p opt::hook - hook used. Possible values are: \p skip_list::base_hook, \p skip_list::member_hook, \p skip_list::traits_hook.
+ If the option is not specified, <tt>skip_list::base_hook<></tt> and \p gc::HP is used.
+ - \p opt::compare - key comparison functor. No default functor is provided.
+ If the option is not specified, the \p opt::less is used.
+ - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
+ - \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
+ - \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 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 \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
*/
template <typename... Options>
struct make_traits {
typedef implementation_defined type ; ///< Metafunction result
# else
typedef typename cds::opt::make_options<
- typename cds::opt::find_type_traits< type_traits, Options... >::type
+ typename cds::opt::find_type_traits< traits, Options... >::type
,Options...
>::type type;
# endif
class head_node: public Node
{
typedef Node node_type;
-
typename node_type::atomic_marked_ptr m_Tower[skip_list::c_nHeightLimit];
public:
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 skip_list
// Forward declaration
- template <class GC, typename T, typename Traits = skip_list::type_traits >
+ template <class GC, typename T, typename Traits = skip_list::traits >
class SkipListSet;
}} // namespace cds::intrusive
-#endif // #ifndef __CDS_INTRUSIVE_DETAILS_SKIP_LIST_BASE_H
+#endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_SKIP_LIST_BASE_H
projects / libcds.git / blobdiff