-//$$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_IMPL_BRONSON_AVLTREE_MAP_RCU_H
#define CDSLIB_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H
disposer()(pVal);
}
- static node_type * child( node_type * pNode, int nDir, atomics::memory_order order = memory_model::memory_order_relaxed )
+ static node_type * child( node_type * pNode, int nDir, atomics::memory_order order )
{
- return pNode->child( nDir ).load( order );
+ return pNode->child( nDir, order );
}
- static node_type * parent( node_type * pNode, atomics::memory_order order = memory_model::memory_order_relaxed )
+ static node_type * parent( node_type * pNode, atomics::memory_order order )
{
return pNode->parent( order );
}
return std::make_pair( result != 0, (result & update_flags::result_inserted) != 0 );
}
- //@cond
- template <typename K>
- std::pair<bool, bool> ensure( K const& key, mapped_type pVal )
- {
- return update( key, pVal, true );
- }
-
//@endcond
/// Delete \p key from the map
return exempt_ptr(do_extract_min( []( key_type const& ) {}));
}
- /// Extracts minimal key key and corresponding value
+ /// Extracts minimal key and corresponding value
/**
Returns \p exempt_ptr to the leftmost item.
If the tree is empty, returns empty \p exempt_ptr.
return exempt_ptr(do_extract_min( [&f]( key_type const& key ) { f(key); }));
}
- /// Extracts minimal key key and corresponding value
+ /// Extracts minimal key and corresponding value
/**
This function is a shortcut for the following call:
\code
);
}
- /// Find the key \p key
+ /// Checks whether the map contains \p key
/**
The function searches the item with key equal to \p key
and returns \p true if it is found, and \p false otherwise.
The function applies RCU lock internally.
*/
template <typename K>
- bool find( K const& key )
+ bool contains( K const& key )
{
return do_find( key, key_comparator(), []( node_type * ) -> bool { return true; });
}
- /// Finds the key \p val using \p pred predicate for searching
+ /// Checks whether the map contains \p key using \p pred predicate for searching
/**
- The function is an analog of \p find(K const&)
- but \p pred is used for key comparing.
+ The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
\p Less functor has the interface like \p std::less.
- \p Less must imply the same element order as the comparator used for building the map.
+ \p Less must imply the same element order as the comparator used for building the set.
*/
template <typename K, typename Less>
- bool find_with( K const& key, Less pred )
+ bool contains( K const& key, Less pred )
{
CDS_UNUSED( pred );
return do_find( key, cds::opt::details::make_comparator_from_less<Less>(), []( node_type * ) -> bool { return true; } );
template <typename Func>
bool check_consistency( Func f ) const
{
- node_type * pChild = child( m_pRoot, right_child );
+ node_type * pChild = child( m_pRoot, right_child, memory_model::memory_order_acquire );
if ( pChild ) {
size_t nErrors = 0;
do_check_consistency( pChild, 1, f, nErrors );
{
if ( pNode ) {
key_comparator cmp;
- node_type * pLeft = child( pNode, left_child );
- node_type * pRight = child( pNode, right_child );
+ node_type * pLeft = child( pNode, left_child, memory_model::memory_order_acquire );
+ node_type * pRight = child( pNode, right_child, memory_model::memory_order_acquire );
if ( pLeft && cmp( pLeft->m_key, pNode->m_key ) > 0 )
++nErrors;
if ( pRight && cmp( pNode->m_key, pRight->m_key ) > 0 )
version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
if ( nChildVersion & node_type::shrinking ) {
m_stat.onRemoveRootWaitShrinking();
- pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
+ pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_acquire );
result = update_flags::retry;
}
else if ( pChild == child( m_pRoot, right_child, memory_model::memory_order_acquire )) {
private:
//@cond
- static int height( node_type * pNode, atomics::memory_order order = memory_model::memory_order_relaxed )
+ static int height( node_type * pNode, atomics::memory_order order )
{
assert( pNode );
return pNode->m_nHeight.load( order );
}
- static void set_height( node_type * pNode, int h, atomics::memory_order order = memory_model::memory_order_relaxed )
+ static void set_height( node_type * pNode, int h, atomics::memory_order order )
{
assert( pNode );
pNode->m_nHeight.store( h, order );
}
- static int height_null( node_type * pNode, atomics::memory_order order = memory_model::memory_order_relaxed )
+ static int height_null( node_type * pNode, atomics::memory_order order )
{
return pNode ? height( pNode, order ) : 0;
}
nDir = stack[pos].nDir;
while ( true ) {
- node_type * pChild = child( pNode, nDir );
+ node_type * pChild = child( pNode, nDir, memory_model::memory_order_acquire );
if ( !pChild ) {
if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
--pos;
int nCmp = cmp( key, pChild->m_key );
if ( nCmp == 0 ) {
- if ( pChild->is_valued( memory_model::memory_order_relaxed ) ) {
+ if ( pChild->is_valued( memory_model::memory_order_acquire ) ) {
// key found
node_scoped_lock l( m_Monitor, *pChild );
- if ( child(pNode, nDir) == pChild ) {
+ if ( child(pNode, nDir, memory_model::memory_order_acquire) == pChild ) {
if ( pChild->is_valued( memory_model::memory_order_relaxed )) {
if ( f( pChild ) ) {
m_stat.onFindSuccess();
version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
if ( nChildVersion & node_type::shrinking ) {
m_stat.onFindWaitShrinking();
- pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
+ pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_acquire );
if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
--pos;
break; // retry
}
}
- else if ( nChildVersion != node_type::unlinked && child( pNode, nDir ) == pChild )
+ else if ( nChildVersion != node_type::unlinked && child( pNode, nDir, memory_model::memory_order_acquire ) == pChild )
{
if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
--pos;
return find_result::retry;
}
-#if 0
- template <typename Q, typename Compare, typename Func>
- find_result try_find( Q const& key, Compare cmp, Func f, node_type * pNode, int nDir, version_type nVersion ) const
- {
- assert( gc::is_locked() );
- assert( pNode );
-
- while ( true ) {
- node_type * pChild = child( pNode, nDir );
- if ( !pChild ) {
- if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
- return find_result::retry;
-
- m_stat.onFindFailed();
- return find_result::not_found;
- }
-
- int nCmp = cmp( key, pChild->m_key );
- if ( nCmp == 0 ) {
- if ( pChild->is_valued( memory_model::memory_order_relaxed ) ) {
- // key found
- node_scoped_lock l( m_Monitor, *pChild );
- if ( pChild->is_valued( memory_model::memory_order_relaxed )) {
- if ( f( pChild ) ) {
- m_stat.onFindSuccess();
- return find_result::found;
- }
- }
- }
-
- m_stat.onFindFailed();
- return find_result::not_found;
- }
-
- version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
- if ( nChildVersion & node_type::shrinking ) {
- m_stat.onFindWaitShrinking();
- pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
-
- if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
- return find_result::retry;
- }
- else if ( nChildVersion != node_type::unlinked && child( pNode, nDir ) == pChild )
- {
- if ( pNode->version(memory_model::memory_order_acquire) != nVersion )
- return find_result::retry;
-
- find_result found = try_find( key, cmp, f, pChild, nCmp, nChildVersion );
- if ( found != find_result::retry )
- return found;
- }
-
- if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
- return find_result::retry;
-
- m_stat.onFindRetry();
- }
- }
-#endif
-
template <typename K, typename Compare, typename Func>
int try_update_root( K const& key, Compare cmp, int nFlags, Func funcUpdate, rcu_disposer& disp )
{
version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
if ( nChildVersion & node_type::shrinking ) {
m_stat.onUpdateRootWaitShrinking();
- pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
+ pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_acquire );
result = update_flags::retry;
}
else if ( pChild == child( m_pRoot, right_child, memory_model::memory_order_acquire ))
assert( pVal != nullptr );
pNew->m_pValue.store( pVal, memory_model::memory_order_release );
- m_pRoot->child( pNew, right_child, memory_model::memory_order_relaxed );
- set_height( m_pRoot, 2 );
+ m_pRoot->child( pNew, right_child, memory_model::memory_order_release);
+ set_height( m_pRoot, 2, memory_model::memory_order_release );
}
++m_ItemCounter;
version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
if ( nChildVersion & node_type::shrinking ) {
m_stat.onRemoveRootWaitShrinking();
- pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
+ pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_acquire );
result = update_flags::retry;
}
else if ( pChild == child( m_pRoot, right_child, memory_model::memory_order_acquire )) {
}
while ( true ) {
- node_type * pChild = child( pNode, nCmp );
+ node_type * pChild = child( pNode, nCmp, memory_model::memory_order_acquire );
if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
--pos;
m_stat.onUpdateRetry();
version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
if ( nChildVersion & node_type::shrinking ) {
m_stat.onUpdateWaitShrinking();
- pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
+ pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_acquire );
// retry
}
- else if ( pChild == child( pNode, nCmp )) {
+ else if ( pChild == child( pNode, nCmp, memory_model::memory_order_acquire )) {
// this second read is important, because it is protected by nChildVersion
// validate the read that our caller took to get to node
return update_flags::retry;
}
-#if 0
- template <typename K, typename Compare, typename Func>
- int try_update( K const& key, Compare cmp, int nFlags, Func funcUpdate, node_type * pNode, version_type nVersion, rcu_disposer& disp )
- {
- assert( gc::is_locked() );
- assert( nVersion != node_type::unlinked );
-
- int nCmp = cmp( key, pNode->m_key );
- if ( nCmp == 0 )
- return try_update_node( nFlags, funcUpdate, pNode, nVersion, disp );
-
- while ( true ) {
- int result;
- node_type * pChild = child( pNode, nCmp );
- if ( pNode->version(memory_model::memory_order_acquire) != nVersion )
- return update_flags::retry;
-
- if ( pChild == nullptr ) {
- // insert new node
- if ( nFlags & update_flags::allow_insert )
- result = try_insert_node( key, funcUpdate, pNode, nCmp, nVersion, disp );
- else
- result = update_flags::failed;
- }
- else {
- // update child
- version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
- if ( nChildVersion & node_type::shrinking ) {
- m_stat.onUpdateWaitShrinking();
- pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
- // retry
- result = update_flags::retry;
- }
- else if ( pChild == child( pNode, nCmp )) {
- // this second read is important, because it is protected by nChildVersion
-
- // validate the read that our caller took to get to node
- if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
- return update_flags::retry;
-
- // At this point we know that the traversal our parent took to get to node is still valid.
- // The recursive implementation will validate the traversal from node to
- // child, so just prior to the node nVersion validation both traversals were definitely okay.
- // This means that we are no longer vulnerable to node shrinks, and we don't need
- // to validate node version any more.
- result = try_update( key, cmp, nFlags, funcUpdate, pChild, nChildVersion, disp );
- }
- else
- result = update_flags::retry;
- }
-
- if ( result == update_flags::retry ) {
- if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
- return update_flags::retry;
- m_stat.onUpdateRetry();
- }
- else
- return result;
- }
- }
-#endif
-
template <typename K, typename Compare, typename Func>
int try_remove( K const& key, Compare cmp, Func func, node_type * pParent, node_type * pNode, version_type nVersion, rcu_disposer& disp )
{
}
while ( true ) {
- node_type * pChild = child( pNode, nCmp );
+ node_type * pChild = child( pNode, nCmp, memory_model::memory_order_acquire );
if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
--pos;
m_stat.onRemoveRetry();
version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
if ( nChildVersion & node_type::shrinking ) {
m_stat.onRemoveWaitShrinking();
- pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
+ pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_acquire );
// retry
}
- else if ( pChild == child( pNode, nCmp )) {
+ else if ( pChild == child( pNode, nCmp, memory_model::memory_order_acquire )) {
// this second read is important, because it is protected by nChildVersion
// validate the read that our caller took to get to node
return update_flags::retry;
}
-#if 0
- template <typename K, typename Compare, typename Func>
- int try_remove( K const& key, Compare cmp, Func func, node_type * pParent, node_type * pNode, version_type nVersion, rcu_disposer& disp )
- {
- assert( gc::is_locked() );
- assert( nVersion != node_type::unlinked );
-
- int nCmp = cmp( key, pNode->m_key );
- if ( nCmp == 0 )
- return try_remove_node( pParent, pNode, nVersion, func, disp );
-
- while ( true ) {
- int result;
-
- node_type * pChild = child( pNode, nCmp );
- if ( pNode->version(memory_model::memory_order_acquire) != nVersion )
- return update_flags::retry;
-
- if ( pChild == nullptr )
- return update_flags::failed;
- else {
- // update child
- result = update_flags::retry;
- version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
- if ( nChildVersion & node_type::shrinking ) {
- m_stat.onRemoveWaitShrinking();
- pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
- // retry
- }
- else if ( pChild == child( pNode, nCmp )) {
- // this second read is important, because it is protected by nChildVersion
-
- // validate the read that our caller took to get to node
- if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
- return update_flags::retry;
-
- // At this point we know that the traversal our parent took to get to node is still valid.
- // The recursive implementation will validate the traversal from node to
- // child, so just prior to the node nVersion validation both traversals were definitely okay.
- // This means that we are no longer vulnerable to node shrinks, and we don't need
- // to validate node version any more.
- result = try_remove( key, cmp, func, pNode, pChild, nChildVersion, disp );
- }
- else
- result = update_flags::retry;
- }
-
- if ( result == update_flags::retry ) {
- if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
- return update_flags::retry;
- m_stat.onRemoveRetry();
- }
- else
- return result;
- }
- }
-#endif
-
template <typename Func>
int try_extract_minmax( int nDir, Func func, node_type * pParent, node_type * pNode, version_type nVersion, rcu_disposer& disp )
{
nVersion = stack[pos].nVersion;
while ( true ) {
- node_type * pChild = child( pNode, nDir );
+ node_type * pChild = child( pNode, nDir, memory_model::memory_order_acquire );
if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
--pos;
m_stat.onRemoveRetry();
if ( pChild == nullptr ) {
// Found min/max
- assert(pNode->is_valued( memory_model::memory_order_relaxed ));
+ assert(pNode->is_valued( memory_model::memory_order_acquire ));
int result = try_remove_node( pParent, pNode, nVersion, func, disp );
if ( result != update_flags::retry )
return result;
version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
if ( nChildVersion & node_type::shrinking ) {
m_stat.onRemoveWaitShrinking();
- pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
+ pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_acquire );
// retry
}
- else if ( pChild == child( pNode, nDir )) {
+ else if ( pChild == child( pNode, nDir, memory_model::memory_order_acquire )) {
// this second read is important, because it is protected by nChildVersion
// validate the read that our caller took to get to node
return update_flags::retry;
}
-#if 0
- template <typename Func>
- int try_extract_minmax( int nDir, Func func, node_type * pParent, node_type * pNode, version_type nVersion, rcu_disposer& disp )
- {
- assert( gc::is_locked() );
- assert( nVersion != node_type::unlinked );
-
- while ( true ) {
- int result;
- node_type * pChild = child( pNode, nDir );
- if ( pNode->version(memory_model::memory_order_acquire) != nVersion )
- return update_flags::retry;
-
- if ( pChild == nullptr ) {
- // Found min/max
- assert(pNode->is_valued( memory_model::memory_order_relaxed ));
- return try_remove_node( pParent, pNode, nVersion, func, disp );
- }
- else {
- //result = update_flags::retry;
- version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
- if ( nChildVersion & node_type::shrinking ) {
- m_stat.onRemoveWaitShrinking();
- pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
- // retry
- result = update_flags::retry;
- }
- else if ( pChild == child( pNode, nDir )) {
- // this second read is important, because it is protected by nChildVersion
-
- // validate the read that our caller took to get to node
- if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
- return update_flags::retry;
-
- // At this point we know that the traversal our parent took to get to node is still valid.
- // The recursive implementation will validate the traversal from node to
- // child, so just prior to the node nVersion validation both traversals were definitely okay.
- // This means that we are no longer vulnerable to node shrinks, and we don't need
- // to validate node version any more.
- result = try_extract_minmax( nDir, func, pNode, pChild, nChildVersion, disp );
- }
- else
- result = update_flags::retry;
- }
-
- if ( result == update_flags::retry ) {
- if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
- return update_flags::retry;
- m_stat.onRemoveRetry();
- }
- else
- return result;
- }
- }
-#endif
-
template <typename K, typename Func>
int try_insert_node( K const& key, Func funcUpdate, node_type * pNode, int nDir, version_type nVersion, rcu_disposer& disp )
{
auto fnCreateNode = [&funcUpdate]( node_type * pNew ) {
mapped_type pVal = funcUpdate( pNew );
assert( pVal != nullptr );
- pNew->m_pValue.store( pVal, memory_model::memory_order_relaxed );
+ pNew->m_pValue.store( pVal, memory_model::memory_order_release );
};
if ( c_bRelaxedInsert ) {
if ( pNode->version( memory_model::memory_order_acquire ) != nVersion
- || child( pNode, nDir ) != nullptr )
+ || child( pNode, nDir, memory_model::memory_order_acquire ) != nullptr )
{
m_stat.onInsertRetry();
return update_flags::retry;
node_scoped_lock l( m_Monitor, *pNode );
if ( pNode->version( memory_model::memory_order_acquire ) != nVersion
- || child( pNode, nDir ) != nullptr )
+ || child( pNode, nDir, memory_model::memory_order_acquire ) != nullptr )
{
if ( c_bRelaxedInsert ) {
mapped_type pVal = pNew->m_pValue.load( memory_model::memory_order_relaxed );
if ( !c_bRelaxedInsert )
fnCreateNode( pNew = alloc_node( key, 1, 0, pNode, nullptr, nullptr ));
- pNode->child( pNew, nDir, memory_model::memory_order_relaxed );
+ pNode->child( pNew, nDir, memory_model::memory_order_release );
pDamaged = fix_height_locked( pNode );
}
if ( pNode->version(memory_model::memory_order_acquire) != nVersion )
return update_flags::retry;
- if ( pNode->is_unlinked( memory_model::memory_order_relaxed )) {
+ if ( pNode->is_unlinked( memory_model::memory_order_acquire )) {
m_stat.onUpdateUnlinked();
return update_flags::retry;
}
pOld = nullptr;
else {
assert( pVal != nullptr );
- pNode->m_pValue.store( pVal, memory_model::memory_order_relaxed );
+ pNode->m_pValue.store( pVal, memory_model::memory_order_release );
}
}
}
if ( bInserted ) {
+ ++m_ItemCounter;
m_stat.onInsertSuccess();
return update_flags::result_inserted;
}
assert( pParent != nullptr );
assert( pNode != nullptr );
- if ( !pNode->is_valued( memory_model::memory_order_relaxed ) )
+ if ( !pNode->is_valued( memory_model::memory_order_acquire ) )
return update_flags::failed;
- if ( child( pNode, left_child ) == nullptr || child( pNode, right_child ) == nullptr ) {
+ if ( child( pNode, left_child, memory_model::memory_order_acquire ) == nullptr
+ || child( pNode, right_child, memory_model::memory_order_acquire ) == nullptr )
+ {
// pNode can be replaced with its child
node_type * pDamaged;
mapped_type pOld;
{
node_scoped_lock lp( m_Monitor, *pParent );
- if ( pParent->is_unlinked( memory_model::memory_order_relaxed ) || parent( pNode ) != pParent )
+ if ( pParent->is_unlinked( memory_model::memory_order_acquire ) || parent( pNode, memory_model::memory_order_acquire ) != pParent )
return update_flags::retry;
{
{
node_scoped_lock ln( m_Monitor, *pNode );
pOld = pNode->value( memory_model::memory_order_relaxed );
- if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
+ if ( pNode->version( memory_model::memory_order_relaxed ) != nVersion )
return update_flags::retry;
if ( !pOld )
return update_flags::failed;
- pNode->m_pValue.store( nullptr, memory_model::memory_order_relaxed );
+ pNode->m_pValue.store( nullptr, memory_model::memory_order_release );
m_stat.onMakeRoutingNode();
}
// pParent and pNode must be locked
assert( !pParent->is_unlinked(memory_model::memory_order_relaxed) );
- node_type * pParentLeft = child( pParent, left_child );
- node_type * pParentRight = child( pParent, right_child );
+ node_type * pParentLeft = child( pParent, left_child, memory_model::memory_order_relaxed );
+ node_type * pParentRight = child( pParent, right_child, memory_model::memory_order_relaxed );
if ( pNode != pParentLeft && pNode != pParentRight ) {
// node is no longer a child of parent
return false;
}
assert( !pNode->is_unlinked( memory_model::memory_order_relaxed ));
- assert( pParent == parent( pNode ));
+ assert( pParent == parent( pNode, memory_model::memory_order_relaxed ));
- node_type * pLeft = child( pNode, left_child );
- node_type * pRight = child( pNode, right_child );
+ node_type * pLeft = child( pNode, left_child, memory_model::memory_order_relaxed );
+ node_type * pRight = child( pNode, right_child, memory_model::memory_order_relaxed );
if ( pLeft != nullptr && pRight != nullptr ) {
// splicing is no longer possible
return false;
node_type * pSplice = pLeft ? pLeft : pRight;
if ( pParentLeft == pNode )
- pParent->m_pLeft.store( pSplice, memory_model::memory_order_relaxed );
+ pParent->m_pLeft.store( pSplice, memory_model::memory_order_release );
else
- pParent->m_pRight.store( pSplice, memory_model::memory_order_relaxed );
+ pParent->m_pRight.store( pSplice, memory_model::memory_order_release );
if ( pSplice )
- pSplice->parent( pParent, memory_model::memory_order_relaxed );
+ pSplice->parent( pParent, memory_model::memory_order_release );
// Mark the node as unlinked
pNode->version( node_type::unlinked, memory_model::memory_order_release );
// The value will be disposed by calling function
- pNode->m_pValue.store( nullptr, memory_model::memory_order_relaxed );
+ pNode->m_pValue.store( nullptr, memory_model::memory_order_release );
disp.dispose( pNode );
m_stat.onDisposeNode();
//@cond
int estimate_node_condition( node_type * pNode )
{
- node_type * pLeft = child( pNode, left_child );
- node_type * pRight = child( pNode, right_child );
+ node_type * pLeft = child( pNode, left_child, memory_model::memory_order_acquire );
+ node_type * pRight = child( pNode, right_child, memory_model::memory_order_acquire );
- if ( (pLeft == nullptr || pRight == nullptr) && !pNode->is_valued( memory_model::memory_order_relaxed ))
+ if ( (pLeft == nullptr || pRight == nullptr) && !pNode->is_valued( memory_model::memory_order_acquire ))
return unlink_required;
- int h = height( pNode );
- int hL = height_null( pLeft );
- int hR = height_null( pRight );
+ int h = height( pNode, memory_model::memory_order_acquire );
+ int hL = height_null( pLeft, memory_model::memory_order_acquire );
+ int hR = height_null( pRight, memory_model::memory_order_acquire );
int hNew = 1 + std::max( hL, hR );
int nBalance = hL - hR;
case nothing_required:
return nullptr;
default:
- set_height( pNode, h );
- return parent( pNode );
+ set_height( pNode, h, memory_model::memory_order_release );
+ return parent( pNode, memory_model::memory_order_relaxed );
}
}
void fix_height_and_rebalance( node_type * pNode, rcu_disposer& disp )
{
- while ( pNode && parent( pNode )) {
+ while ( pNode && parent( pNode, memory_model::memory_order_acquire )) {
int nCond = estimate_node_condition( pNode );
- if ( nCond == nothing_required || pNode->is_unlinked( memory_model::memory_order_relaxed ) )
+ if ( nCond == nothing_required || pNode->is_unlinked( memory_model::memory_order_acquire ) )
return;
if ( nCond != unlink_required && nCond != rebalance_required )
pNode = fix_height( pNode );
else {
- node_type * pParent = parent( pNode );
+ node_type * pParent = parent( pNode, memory_model::memory_order_acquire );
assert( pParent != nullptr );
{
node_scoped_lock lp( m_Monitor, *pParent );
- if ( !pParent->is_unlinked( memory_model::memory_order_relaxed ) && parent( pNode ) == pParent ) {
+ if ( !pParent->is_unlinked( memory_model::memory_order_relaxed ) && parent( pNode, memory_model::memory_order_acquire ) == pParent ) {
node_scoped_lock ln( m_Monitor, *pNode );
pNode = rebalance_locked( pParent, pNode, disp );
}
{
// pParent and pNode should be locked.
// Returns a damaged node, or nullptr if no more rebalancing is necessary
- assert( parent( pNode ) == pParent );
+ assert( parent( pNode, memory_model::memory_order_relaxed ) == pParent );
- node_type * pLeft = child( pNode, left_child );
- node_type * pRight = child( pNode, right_child );
+ node_type * pLeft = child( pNode, left_child, memory_model::memory_order_relaxed );
+ node_type * pRight = child( pNode, right_child, memory_model::memory_order_relaxed );
if ( (pLeft == nullptr || pRight == nullptr) && !pNode->is_valued( memory_model::memory_order_relaxed )) {
if ( try_unlink_locked( pParent, pNode, disp ))
}
}
- assert( child( pParent, left_child ) == pNode || child( pParent, right_child ) == pNode );
+ assert( child( pParent, left_child, memory_model::memory_order_relaxed ) == pNode
+ || child( pParent, right_child, memory_model::memory_order_relaxed ) == pNode );
- int h = height( pNode );
- int hL = height_null( pLeft );
- int hR = height_null( pRight );
+ int h = height( pNode, memory_model::memory_order_acquire );
+ int hL = height_null( pLeft, memory_model::memory_order_acquire );
+ int hR = height_null( pRight, memory_model::memory_order_acquire );
int hNew = 1 + std::max( hL, hR );
int balance = hL - hR;
else if ( balance < -1 )
return rebalance_to_left_locked( pParent, pNode, pRight, hL );
else if ( hNew != h ) {
- set_height( pNode, hNew );
+ set_height( pNode, hNew, memory_model::memory_order_release );
// pParent is already locked
return fix_height_locked( pParent );
node_type * rebalance_to_right_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR )
{
- assert( parent( pNode ) == pParent );
- assert( child( pParent, left_child ) == pNode || child( pParent, right_child ) == pNode );
+ assert( parent( pNode, memory_model::memory_order_relaxed ) == pParent );
+ assert( child( pParent, left_child, memory_model::memory_order_relaxed ) == pNode
+ || child( pParent, right_child, memory_model::memory_order_relaxed ) == pNode );
// pParent and pNode is locked yet
// pNode->pLeft is too large, we will rotate-right.
if ( pNode->m_pLeft.load( memory_model::memory_order_relaxed ) != pLeft )
return pNode; // retry for pNode
- int hL = height( pLeft );
+ int hL = height( pLeft, memory_model::memory_order_acquire );
if ( hL - hR <= 1 )
return pNode; // retry
- node_type * pLRight = child( pLeft, right_child );
- int hLR = height_null( pLRight );
- node_type * pLLeft = child( pLeft, left_child );
- int hLL = height_null( pLLeft );
+ node_type * pLRight = child( pLeft, right_child, memory_model::memory_order_relaxed );
+ int hLR = height_null( pLRight, memory_model::memory_order_acquire );
+ node_type * pLLeft = child( pLeft, left_child, memory_model::memory_order_relaxed );
+ int hLL = height_null( pLLeft, memory_model::memory_order_acquire );
if ( hLL > hLR ) {
// rotate right
return rotate_right_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLR );
}
else {
- assert( pLRight != nullptr );
- {
+ if ( pLRight ) {
node_scoped_lock lr( m_Monitor, *pLRight );
- if ( pLeft->m_pRight.load( memory_model::memory_order_relaxed ) != pLRight )
+ if ( pLeft->m_pRight.load( memory_model::memory_order_acquire ) != pLRight )
return pNode; // retry
- hLR = height( pLRight );
+ hLR = height( pLRight, memory_model::memory_order_acquire );
if ( hLL > hLR )
return rotate_right_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLR );
- int hLRL = height_null( child( pLRight, left_child ));
+ int hLRL = height_null( child( pLRight, left_child, memory_model::memory_order_relaxed ), memory_model::memory_order_acquire);
int balance = hLL - hLRL;
if ( balance >= -1 && balance <= 1 && !((hLL == 0 || hLRL == 0) && !pLeft->is_valued(memory_model::memory_order_relaxed))) {
// nParent.child.left won't be damaged after a double rotation
return rotate_right_over_left_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLRL );
}
}
+ else
+ return pNode; // retry
// focus on pLeft, if necessary pNode will be balanced later
return rebalance_to_left_locked( pNode, pLeft, pLRight, hLL );
node_type * rebalance_to_left_locked( node_type * pParent, node_type * pNode, node_type * pRight, int hL )
{
- assert( parent( pNode ) == pParent );
- assert( child( pParent, left_child ) == pNode || child( pParent, right_child ) == pNode );
+ assert( parent( pNode, memory_model::memory_order_relaxed ) == pParent );
+ assert( child( pParent, left_child, memory_model::memory_order_relaxed ) == pNode
+ || child( pParent, right_child, memory_model::memory_order_relaxed ) == pNode );
// pParent and pNode is locked yet
{
if ( pNode->m_pRight.load( memory_model::memory_order_relaxed ) != pRight )
return pNode; // retry for pNode
- int hR = height( pRight );
+ int hR = height( pRight, memory_model::memory_order_acquire );
if ( hL - hR >= -1 )
return pNode; // retry
- node_type * pRLeft = child( pRight, left_child );
- int hRL = height_null( pRLeft );
- node_type * pRRight = child( pRight, right_child );
- int hRR = height_null( pRRight );
+ node_type * pRLeft = child( pRight, left_child, memory_model::memory_order_relaxed );
+ int hRL = height_null( pRLeft, memory_model::memory_order_acquire );
+ node_type * pRRight = child( pRight, right_child, memory_model::memory_order_relaxed );
+ int hRR = height_null( pRRight, memory_model::memory_order_acquire );
if ( hRR > hRL )
return rotate_left_locked( pParent, pNode, hL, pRight, pRLeft, hRL, hRR );
- {
- assert( pRLeft != nullptr );
+ if ( pRLeft ) {
node_scoped_lock lrl( m_Monitor, *pRLeft );
- if ( pRight->m_pLeft.load( memory_model::memory_order_relaxed ) != pRLeft )
+ if ( pRight->m_pLeft.load( memory_model::memory_order_acquire ) != pRLeft )
return pNode; // retry
- hRL = height( pRLeft );
+ hRL = height( pRLeft, memory_model::memory_order_acquire );
if ( hRR >= hRL )
return rotate_left_locked( pParent, pNode, hL, pRight, pRLeft, hRL, hRR );
- node_type * pRLRight = child( pRLeft, right_child );
- int hRLR = height_null( pRLRight );
+ node_type * pRLRight = child( pRLeft, right_child, memory_model::memory_order_relaxed );
+ int hRLR = height_null( pRLRight, memory_model::memory_order_acquire );
int balance = hRR - hRLR;
if ( balance >= -1 && balance <= 1 && !((hRR == 0 || hRLR == 0) && !pRight->is_valued( memory_model::memory_order_relaxed )))
return rotate_left_over_right_locked( pParent, pNode, hL, pRight, pRLeft, hRR, hRLR );
}
+ else
+ return pNode; // retry
return rebalance_to_right_locked( pNode, pRight, pRLeft, hRR );
}
}
node_type * rotate_right_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR, int hLL, node_type * pLRight, int hLR )
{
- version_type nodeVersion = pNode->version( memory_model::memory_order_acquire );
- node_type * pParentLeft = child( pParent, left_child );
+ version_type nodeVersion = pNode->version( memory_model::memory_order_relaxed );
+ node_type * pParentLeft = child( pParent, left_child, memory_model::memory_order_relaxed );
begin_change( pNode, nodeVersion );
- pNode->m_pLeft.store( pLRight, memory_model::memory_order_relaxed );
+ pNode->m_pLeft.store( pLRight, memory_model::memory_order_release );
if ( pLRight != nullptr )
- pLRight->parent( pNode, memory_model::memory_order_relaxed );
+ pLRight->parent( pNode, memory_model::memory_order_release );
atomics::atomic_thread_fence( memory_model::memory_order_release );
- pLeft->m_pRight.store( pNode, memory_model::memory_order_relaxed );
- pNode->parent( pLeft, memory_model::memory_order_relaxed );
+ pLeft->m_pRight.store( pNode, memory_model::memory_order_release );
+ pNode->parent( pLeft, memory_model::memory_order_release );
atomics::atomic_thread_fence( memory_model::memory_order_release );
if ( pParentLeft == pNode )
- pParent->m_pLeft.store( pLeft, memory_model::memory_order_relaxed );
+ pParent->m_pLeft.store( pLeft, memory_model::memory_order_release );
else {
assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
- pParent->m_pRight.store( pLeft, memory_model::memory_order_relaxed );
+ pParent->m_pRight.store( pLeft, memory_model::memory_order_release );
}
- pLeft->parent( pParent, memory_model::memory_order_relaxed );
+ pLeft->parent( pParent, memory_model::memory_order_release );
atomics::atomic_thread_fence( memory_model::memory_order_release );
// fix up heights links
int hNode = 1 + std::max( hLR, hR );
- set_height( pNode, hNode );
- set_height( pLeft, 1 + std::max( hLL, hNode ));
+ set_height( pNode, hNode, memory_model::memory_order_release );
+ set_height( pLeft, 1 + std::max( hLL, hNode ), memory_model::memory_order_release);
end_change( pNode, nodeVersion );
m_stat.onRotateRight();
}
// pLeft might also have routing node damage (if pLeft.left was null)
- if ( hLL == 0 && !pLeft->is_valued(memory_model::memory_order_relaxed) ) {
+ if ( hLL == 0 && !pLeft->is_valued(memory_model::memory_order_acquire) ) {
m_stat.onDamageAfterRightRotation();
return pLeft;
}
node_type * rotate_left_locked( node_type * pParent, node_type * pNode, int hL, node_type * pRight, node_type * pRLeft, int hRL, int hRR )
{
- version_type nodeVersion = pNode->version( memory_model::memory_order_acquire );
- node_type * pParentLeft = child( pParent, left_child );
+ version_type nodeVersion = pNode->version( memory_model::memory_order_relaxed );
+ node_type * pParentLeft = child( pParent, left_child, memory_model::memory_order_relaxed );
begin_change( pNode, nodeVersion );
// fix up pNode links, careful to be compatible with concurrent traversal for all but pNode
- pNode->m_pRight.store( pRLeft, memory_model::memory_order_relaxed );
+ pNode->m_pRight.store( pRLeft, memory_model::memory_order_release );
if ( pRLeft != nullptr )
- pRLeft->parent( pNode, memory_model::memory_order_relaxed );
+ pRLeft->parent( pNode, memory_model::memory_order_release );
atomics::atomic_thread_fence( memory_model::memory_order_release );
- pRight->m_pLeft.store( pNode, memory_model::memory_order_relaxed );
- pNode->parent( pRight, memory_model::memory_order_relaxed );
+ pRight->m_pLeft.store( pNode, memory_model::memory_order_release );
+ pNode->parent( pRight, memory_model::memory_order_release );
atomics::atomic_thread_fence( memory_model::memory_order_release );
if ( pParentLeft == pNode )
- pParent->m_pLeft.store( pRight, memory_model::memory_order_relaxed );
+ pParent->m_pLeft.store( pRight, memory_model::memory_order_release );
else {
assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
- pParent->m_pRight.store( pRight, memory_model::memory_order_relaxed );
+ pParent->m_pRight.store( pRight, memory_model::memory_order_release );
}
- pRight->parent( pParent, memory_model::memory_order_relaxed );
+ pRight->parent( pParent, memory_model::memory_order_release );
atomics::atomic_thread_fence( memory_model::memory_order_release );
// fix up heights
int hNode = 1 + std::max( hL, hRL );
- set_height( pNode, hNode );
- set_height( pRight, 1 + std::max( hNode, hRR ));
+ set_height( pNode, hNode, memory_model::memory_order_release );
+ set_height( pRight, 1 + std::max( hNode, hRR ), memory_model::memory_order_release);
end_change( pNode, nodeVersion );
m_stat.onRotateLeft();
return pRight;
}
- if ( hRR == 0 && !pRight->is_valued(memory_model::memory_order_relaxed) ) {
+ if ( hRR == 0 && !pRight->is_valued(memory_model::memory_order_acquire) ) {
m_stat.onDamageAfterLeftRotation();
return pRight;
}
node_type * rotate_right_over_left_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR, int hLL, node_type * pLRight, int hLRL )
{
- version_type nodeVersion = pNode->version( memory_model::memory_order_acquire );
+ version_type nodeVersion = pNode->version( memory_model::memory_order_relaxed );
version_type leftVersion = pLeft->version( memory_model::memory_order_acquire );
- node_type * pPL = child( pParent, left_child );
- node_type * pLRL = child( pLRight, left_child );
- node_type * pLRR = child( pLRight, right_child );
- int hLRR = height_null( pLRR );
+ node_type * pPL = child( pParent, left_child, memory_model::memory_order_relaxed );
+ node_type * pLRL = child( pLRight, left_child, memory_model::memory_order_acquire );
+ node_type * pLRR = child( pLRight, right_child, memory_model::memory_order_acquire );
+ int hLRR = height_null( pLRR, memory_model::memory_order_acquire );
begin_change( pNode, nodeVersion );
begin_change( pLeft, leftVersion );
// fix up pNode links, careful about the order!
- pNode->m_pLeft.store( pLRR, memory_model::memory_order_relaxed );
+ pNode->m_pLeft.store( pLRR, memory_model::memory_order_release );
if ( pLRR != nullptr )
- pLRR->parent( pNode, memory_model::memory_order_relaxed );
- atomics::atomic_thread_fence( memory_model::memory_order_release );
+ pLRR->parent( pNode, memory_model::memory_order_release );
- pLeft->m_pRight.store( pLRL, memory_model::memory_order_relaxed );
+ pLeft->m_pRight.store( pLRL, memory_model::memory_order_release );
if ( pLRL != nullptr )
- pLRL->parent( pLeft, memory_model::memory_order_relaxed );
- atomics::atomic_thread_fence( memory_model::memory_order_release );
+ pLRL->parent( pLeft, memory_model::memory_order_release );
- pLRight->m_pLeft.store( pLeft, memory_model::memory_order_relaxed );
- pLeft->parent( pLRight, memory_model::memory_order_relaxed );
- atomics::atomic_thread_fence( memory_model::memory_order_release );
+ pLRight->m_pLeft.store( pLeft, memory_model::memory_order_release );
+ pLeft->parent( pLRight, memory_model::memory_order_release );
- pLRight->m_pRight.store( pNode, memory_model::memory_order_relaxed );
- pNode->parent( pLRight, memory_model::memory_order_relaxed );
- atomics::atomic_thread_fence( memory_model::memory_order_release );
+ pLRight->m_pRight.store( pNode, memory_model::memory_order_release );
+ pNode->parent( pLRight, memory_model::memory_order_release );
if ( pPL == pNode )
- pParent->m_pLeft.store( pLRight, memory_model::memory_order_relaxed );
+ pParent->m_pLeft.store( pLRight, memory_model::memory_order_release );
else {
- assert( child( pParent, right_child ) == pNode );
- pParent->m_pRight.store( pLRight, memory_model::memory_order_relaxed );
+ assert( child( pParent, right_child, memory_model::memory_order_relaxed ) == pNode );
+ pParent->m_pRight.store( pLRight, memory_model::memory_order_release );
}
- pLRight->parent( pParent, memory_model::memory_order_relaxed );
- atomics::atomic_thread_fence( memory_model::memory_order_release );
+ pLRight->parent( pParent, memory_model::memory_order_release );
// fix up heights
int hNode = 1 + std::max( hLRR, hR );
- set_height( pNode, hNode );
+ set_height( pNode, hNode, memory_model::memory_order_release );
int hLeft = 1 + std::max( hLL, hLRL );
- set_height( pLeft, hLeft );
- set_height( pLRight, 1 + std::max( hLeft, hNode ));
+ set_height( pLeft, hLeft, memory_model::memory_order_release );
+ set_height( pLRight, 1 + std::max( hLeft, hNode ), memory_model::memory_order_release);
end_change( pNode, nodeVersion );
end_change( pLeft, leftVersion );
// caller should have performed only a single rotation if pLeft was going
// to end up damaged
assert( hLL - hLRL <= 1 && hLRL - hLL <= 1 );
- assert( !((hLL == 0 || pLRL == nullptr) && !pLeft->is_valued( memory_model::memory_order_relaxed )));
+ assert( !((hLL == 0 || pLRL == nullptr) && !pLeft->is_valued( memory_model::memory_order_acquire )));
// We have damaged pParent, pLR (now parent.child), and pNode (now
// parent.child.right). pNode is the deepest. Perform as many fixes as we
node_type * rotate_left_over_right_locked( node_type * pParent, node_type * pNode, int hL, node_type * pRight, node_type * pRLeft, int hRR, int hRLR )
{
- version_type nodeVersion = pNode->version( memory_model::memory_order_acquire );
+ version_type nodeVersion = pNode->version( memory_model::memory_order_relaxed );
version_type rightVersion = pRight->version( memory_model::memory_order_acquire );
- node_type * pPL = child( pParent, left_child );
- node_type * pRLL = child( pRLeft, left_child );
- node_type * pRLR = child( pRLeft, right_child );
- int hRLL = height_null( pRLL );
+ node_type * pPL = child( pParent, left_child, memory_model::memory_order_relaxed );
+ node_type * pRLL = child( pRLeft, left_child, memory_model::memory_order_acquire );
+ node_type * pRLR = child( pRLeft, right_child, memory_model::memory_order_acquire );
+ int hRLL = height_null( pRLL, memory_model::memory_order_acquire );
begin_change( pNode, nodeVersion );
begin_change( pRight, rightVersion );
// fix up pNode links, careful about the order!
- pNode->m_pRight.store( pRLL, memory_model::memory_order_relaxed );
+ pNode->m_pRight.store( pRLL, memory_model::memory_order_release );
if ( pRLL != nullptr )
- pRLL->parent( pNode, memory_model::memory_order_relaxed );
- atomics::atomic_thread_fence( memory_model::memory_order_release );
+ pRLL->parent( pNode, memory_model::memory_order_release );
- pRight->m_pLeft.store( pRLR, memory_model::memory_order_relaxed );
+ pRight->m_pLeft.store( pRLR, memory_model::memory_order_release );
if ( pRLR != nullptr )
- pRLR->parent( pRight, memory_model::memory_order_relaxed );
- atomics::atomic_thread_fence( memory_model::memory_order_release );
+ pRLR->parent( pRight, memory_model::memory_order_release );
- pRLeft->m_pRight.store( pRight, memory_model::memory_order_relaxed );
- pRight->parent( pRLeft, memory_model::memory_order_relaxed );
- atomics::atomic_thread_fence( memory_model::memory_order_release );
+ pRLeft->m_pRight.store( pRight, memory_model::memory_order_release );
+ pRight->parent( pRLeft, memory_model::memory_order_release );
- pRLeft->m_pLeft.store( pNode, memory_model::memory_order_relaxed );
- pNode->parent( pRLeft, memory_model::memory_order_relaxed );
- atomics::atomic_thread_fence( memory_model::memory_order_release );
+ pRLeft->m_pLeft.store( pNode, memory_model::memory_order_release );
+ pNode->parent( pRLeft, memory_model::memory_order_release );
if ( pPL == pNode )
- pParent->m_pLeft.store( pRLeft, memory_model::memory_order_relaxed );
+ pParent->m_pLeft.store( pRLeft, memory_model::memory_order_release );
else {
assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
- pParent->m_pRight.store( pRLeft, memory_model::memory_order_relaxed );
+ pParent->m_pRight.store( pRLeft, memory_model::memory_order_release );
}
- pRLeft->parent( pParent, memory_model::memory_order_relaxed );
- atomics::atomic_thread_fence( memory_model::memory_order_release );
+ pRLeft->parent( pParent, memory_model::memory_order_release );
// fix up heights
int hNode = 1 + std::max( hL, hRLL );
- set_height( pNode, hNode );
+ set_height( pNode, hNode, memory_model::memory_order_release );
int hRight = 1 + std::max( hRLR, hRR );
- set_height( pRight, hRight );
- set_height( pRLeft, 1 + std::max( hNode, hRight ));
+ set_height( pRight, hRight, memory_model::memory_order_release );
+ set_height( pRLeft, 1 + std::max( hNode, hRight ), memory_model::memory_order_release);
end_change( pNode, nodeVersion );
end_change( pRight, rightVersion );
projects / libcds.git / blobdiff