/// BronsonAVLTree related declarations
namespace bronson_avltree {
- template <typename Key, typename T>
+ template <typename Key, typename T, typename SyncMonitor >
struct node;
//@cond
- template <typename Key, typename T>
- struct link
+ template <typename Node, typename T, typename SyncMonitor>
+ struct link_node
{
- typedef node<Key, T> node_type;
- typedef uint32_t version_type;
+ typedef Node node_type;
+ typedef T mapped_type;
+ typedef uint32_t version_type; ///< version type (internal)
enum
{
atomics::atomic<node_type *> m_pParent; ///< Parent node
atomics::atomic<node_type *> m_pLeft; ///< Left child
atomics::atomic<node_type *> m_pRight; ///< Right child
+ typename SyncMonitor::node_injection m_SyncMonitorInjection; ///< @ref cds_sync_monitor "synchronization monitor" injected data
+ atomics::atomic<mapped_type *> m_pValue; ///< Value
- node_type * m_pNextRemoved; ///< thread-local list o removed node
-
- link()
+ public:
+ //@cond
+ link_node()
: m_nHeight( 0 )
, m_nVersion( 0 )
, m_pParent( nullptr )
, m_pLeft( nullptr )
, m_pRight( nullptr )
- , m_pNextRemoved( nullptr )
+ , m_pValue( nullptr )
{}
- link( int nHeight, version_type version, node_type * pParent, node_type * pLeft, node_type * pRight )
+ link_node( int nHeight, version_type version, node_type * pParent, node_type * pLeft, node_type * pRight )
: m_nHeight( nHeight )
, m_nVersion( version )
, m_pParent( pParent )
, m_pLeft( pLeft )
, m_pRight( pRight )
- , m_pNextRemoved( nullptr )
+ , m_pValue( nullptr )
{}
- atomics::atomic<node_type *>& child( int nDirection ) const
+ atomics::atomic<node_type *>& child( int nDirection )
{
assert( nDirection != 0 );
return nDirection < 0 ? m_pLeft : m_pRight;
void wait_until_shrink_completed( atomics::memory_order order ) const
{
BackOff bkoff;
- while ( is_shrinking( order ))
+ while ( is_shrinking( order ) )
bkoff();
}
{
return (m_nVersion.load( order ) & shrinking) != 0;
}
+
+ mapped_type * value( atomics::memory_order order ) const
+ {
+ return m_pValue.load( order );
+ }
+
+ bool is_valued( atomics::memory_order order ) const
+ {
+ return value( order ) != nullptr;
+ }
+
+ //@endcond
};
+ //@endcond
- template <typename Key, typename T>
- struct node : public link< Key, T >
+ /// BronsonAVLTree internal node
+ template <typename Key, typename T, typename SyncMonitor >
+ struct node<Key, T*, SyncMonitor>: public link_node< node<Key, T*, SyncMonitor>, T, SyncMonitor >
{
- typedef Key key_type;
- typedef T mapped_type;
- typedef link< key_type, mapped_type > base_class;
+ //@cond
+ typedef link_node< node<Key, T*, SyncMonitor>, T, SyncMonitor > base_class;
+ //@endcond
+
+ typedef Key key_type; ///< key type
+ typedef T mapped_type; ///< value type
+ typedef typename base_class::version_type version_type;
- key_type const m_key;
- atomics::atomic<mapped_type *> m_pValue;
+ key_type const m_key; ///< Key
+ node * m_pNextRemoved; ///< thread-local list of removed node
+ public:
+ //@cond
template <typename Q>
node( Q&& key )
- : m_key( std::forward<Q>(key) )
- , m_pValue( nullptr )
+ : base_class()
+ , m_key( std::forward<Q>( key ) )
+ , m_pNextRemoved( nullptr )
{}
template <typename Q>
- node( Q&& key, int nHeight, version_type version, node_type * pParent, node_type * pLeft, node_type * pRight )
+ node( Q&& key, int nHeight, version_type version, node * pParent, node * pLeft, node * pRight )
: base_class( nHeight, version, pParent, pLeft, pRight )
, m_key( std::forward<Q>( key ) )
- , m_pValue( nullptr )
+ , m_pNextRemoved( nullptr )
{}
-
- T * value( atomics::memory_order order ) const
- {
- return m_pValue.load( order );
- }
-
- bool is_valued( atomics::memory_order order ) const
- {
- return value( order ) != nullptr;
- }
+ //@endcond
};
- //@endcond
/// BronsonAVLTreeMap internal statistics
template <typename Counter = cds::atomicity::event_counter>
event_counter m_nInsertSuccess; ///< Count of inserting data node
event_counter m_nRelaxedInsertFailed; ///< Count of false creating of data nodes (only if @ref bronson_avltree::relaxed_insert "relaxed insertion" is enabled)
event_counter m_nInsertRetry; ///< Count of insert retries via concurrent operations
- event_counter m_nUpdateWaitShrinking; ///< Count of waiting until shrinking completed duting \p update() call
+ event_counter m_nUpdateWaitShrinking; ///< Count of waiting until shrinking completed during \p update() call
event_counter m_nUpdateRetry; ///< Count of update retries via concurrent operations
event_counter m_nUpdateRootWaitShrinking; ///< Count of waiting until root shrinking completed duting \p update() call
event_counter m_nUpdateSuccess; ///< Count of updating data node
- event_counter m_nUpdateUnlinked; ///< Count of updating of unlinked node attempts
+ event_counter m_nUpdateUnlinked; ///< Count of attempts to update unlinked node
+ event_counter m_nDisposedNode; ///< Count of disposed node
event_counter m_nDisposedValue; ///< Count of disposed value
+ event_counter m_nExtractedValue; ///< Count of extracted value
+ event_counter m_nRemoveRetry; ///< Count o erase/extract retries
+ event_counter m_nRemoveWaitShrinking; ///< ount of waiting until shrinking completed during \p erase() or \p extract() call
+ event_counter m_nRemoveRootWaitShrinking; ///< Count of waiting until root shrinking completed duting \p erase() or \p extract() call
+
+ event_counter m_nRightRotation; ///< Count of single right rotation
+ event_counter m_nLeftRotation; ///< Count of single left rotation
+ event_counter m_nLeftRightRotation; ///< Count of double left-over-right rotation
+ event_counter m_nRightLeftRotation; ///< Count of double right-over-left rotation
//@cond
void onFindSuccess() { ++m_nFindSuccess ; }
void onUpdateRootWaitShrinking() { ++m_nUpdateRootWaitShrinking; }
void onUpdateSuccess() { ++m_nUpdateSuccess; }
void onUpdateUnlinked() { ++m_nUpdateUnlinked; }
+ void onDisposeNode() { ++m_nDisposedNode; }
void onDisposeValue() { ++m_nDisposedValue; }
-
+ void onExtractValue() { ++m_nExtractedValue; }
+ void onRemoveRetry() { ++m_nRemoveRetry; }
+ void onRemoveWaitShrinking() { ++m_nRemoveWaitShrinking; }
+ void onRemoveRootWaitShrinking() { ++m_nRemoveRootWaitShrinking; }
+
+ void onRotateRight() { ++m_nRightRotation; }
+ void onRotateLeft() { ++m_nLeftRotation; }
+ void onRotateRightOverLeft() { ++m_nRightLeftRotation; }
+ void onRotateLeftOverRight() { ++m_nLeftRightRotation; }
//@endcond
};
void onUpdateRootWaitShrinking() const {}
void onUpdateSuccess() const {}
void onUpdateUnlinked() const {}
+ void onDisposeNode() const {}
void onDisposeValue() const {}
-
+ void onExtractValue() const {}
+ void onRemoveRetry() const {}
+ void onRemoveWaitShrinking() const {}
+ void onRemoveRootWaitShrinking() const {}
+
+ void onRotateRight() const {}
+ void onRotateLeft() const {}
+ void onRotateRightOverLeft() const {}
+ void onRotateLeftOverRight() const {}
//@endcond
};
that can lead to lock contention.
When this option is enabled, the new node is created before locking the parent node.
- After that, the parent is locked and checked whether the new node can be attached to the parent.
+ After that, the parent is locked and checked whether the new node may be attached to the parent.
In this case, false node creating can be performed, but locked section can be significantly small.
*/
template <bool Enable>
/// Allocator for internal node
typedef CDS_DEFAULT_ALLOCATOR node_allocator;
+ /// Allocator for node's value (not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation)
+ typedef CDS_DEFAULT_ALLOCATOR allocator;
+
/// Disposer (only for pointer-oriented tree specialization)
/**
The functor used for dispose removed values.
If the option is not specified, \p %opt::less is used.
- \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
- \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
+ - \p opt::allocator - the allocator for node's value. Default is \ref CDS_DEFAULT_ALLOCATOR.
+ This option is not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation
- \ref cds::intrusive::opt::disposer "container::opt::disposer" - the functor used for dispose removed values.
The user-provided disposer is used only for pointer-oriented tree specialization
like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting node without value,
Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
Due the nature of GC schema the disposer may be called asynchronously.
- \p opt::sync_monitor - @ref cds_sync_monitor "synchronization monitor" type for node-level locking,
- default is cds::sync::injecting_monitor<cds::sync::spin>
+ default is \p cds::sync::injecting_monitor<cds::sync::spin>
- \p bronson_avltree::relaxed_insert - enable (\p true) or disable (\p false, the default)
@ref bronson_avltree::relaxed_insert "relaxed insertion"
- \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
projects / libcds.git / blobdiff