-//$$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_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H
#define CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H
, m_pValue( nullptr )
{}
- atomics::atomic<node_type *>& child( int nDirection )
+ node_type * parent( atomics::memory_order order ) const
+ {
+ return m_pParent.load( order );
+ }
+
+ void parent( node_type * p, atomics::memory_order order )
+ {
+ m_pParent.store( p, order );
+ }
+
+ node_type * child( int nDirection, atomics::memory_order order ) const
{
assert( nDirection != 0 );
- return nDirection < 0 ? m_pLeft : m_pRight;
+ return nDirection < 0 ? m_pLeft.load( order ) : m_pRight.load( order );
}
void child( node_type * pChild, int nDirection, atomics::memory_order order )
void wait_until_shrink_completed( atomics::memory_order order ) const
{
BackOff bkoff;
- while ( is_shrinking( order ) )
+ while ( is_shrinking( order ))
bkoff();
}
template <typename Q>
node( Q&& key )
: base_class()
- , m_key( std::forward<Q>( key ) )
+ , m_key( std::forward<Q>( key ))
, m_pNextRemoved( nullptr )
{}
template <typename Q>
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_key( std::forward<Q>( key ))
, m_pNextRemoved( nullptr )
{}
//@endcond
event_counter m_nFindWaitShrinking; ///< Count of waiting until shrinking completed duting \p find() call
event_counter m_nInsertSuccess; ///< Count of inserting data node
+ event_counter m_nInsertFailed; ///< Count of insert failures
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 during \p update() call
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_nRemoveSuccess; ///< Count of successfully \p erase() call
+ event_counter m_nRemoveFailed; ///< Count of failed \p erase() call
event_counter m_nRemoveRetry; ///< Count o erase/extract retries
+ event_counter m_nExtractSuccess; ///< Count of successfully \p extract() call
+ event_counter m_nExtractFailed; ///< Count of failed \p extract() call
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_nMakeRoutingNode; ///< How many nodes were converted to routing (valueless) nodes
event_counter m_nRightRotation; ///< Count of single right rotation
event_counter m_nLeftRotation; ///< Count of single left rotation
void onFindRetry() { ++m_nFindRetry ; }
void onFindWaitShrinking() { ++m_nFindWaitShrinking; }
- void onInsertSuccess() { ++m_nInsertSuccess ; }
+ void onInsertSuccess() { ++m_nInsertSuccess; }
+ void onInsertFailed() { ++m_nInsertFailed; }
void onRelaxedInsertFailed() { ++m_nRelaxedInsertFailed; }
void onInsertRetry() { ++m_nInsertRetry ; }
void onUpdateWaitShrinking() { ++m_nUpdateWaitShrinking; }
void onDisposeNode() { ++m_nDisposedNode; }
void onDisposeValue() { ++m_nDisposedValue; }
void onExtractValue() { ++m_nExtractedValue; }
+ void onRemove(bool bSuccess)
+ {
+ if ( bSuccess )
+ ++m_nRemoveSuccess;
+ else
+ ++m_nRemoveFailed;
+ }
+ void onExtract( bool bSuccess )
+ {
+ if ( bSuccess )
+ ++m_nExtractSuccess;
+ else
+ ++m_nExtractFailed;
+ }
void onRemoveRetry() { ++m_nRemoveRetry; }
void onRemoveWaitShrinking() { ++m_nRemoveWaitShrinking; }
void onRemoveRootWaitShrinking() { ++m_nRemoveRootWaitShrinking; }
+ void onMakeRoutingNode() { ++m_nMakeRoutingNode; }
void onRotateRight() { ++m_nRightRotation; }
void onRotateLeft() { ++m_nLeftRotation; }
void onFindWaitShrinking() const {}
void onInsertSuccess() const {}
+ void onInsertFailed() const {}
void onRelaxedInsertFailed() const {}
void onInsertRetry() const {}
void onUpdateWaitShrinking() const {}
void onDisposeNode() const {}
void onDisposeValue() const {}
void onExtractValue() const {}
+ void onRemove(bool /*bSuccess*/) const {}
+ void onExtract(bool /*bSuccess*/) const {}
void onRemoveRetry() const {}
void onRemoveWaitShrinking() const {}
void onRemoveRootWaitShrinking() const {}
+ void onMakeRoutingNode() const {}
void onRotateRight() const {}
void onRotateLeft() const {}
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 may be attached to the parent.
+ After that, the parent is locked and checked whether the new node can be attached to the parent.
In this case, false node creating can be performed, but locked section can be significantly small.
*/
template <bool Enable>
- \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.
+ - \p cds::intrusive::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,
the disposer will be called to signal that the memory for the value can be safely freed.
- Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
+ Default is \p cds::intrusive::opt::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 \p cds::sync::injecting_monitor<cds::sync::spin>
- - \p bronson_avltree::relaxed_insert - enable (\p true) or disable (\p false, the default)
+ - \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)
To enable it use \p atomicity::item_counter
}} // namespace cds::container
-
#endif // #ifndef CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H
projects / libcds.git / blobdiff