static node_type * parent( node_type * pNode, atomics::memory_order order = memory_model::memory_order_relaxed )
{
- return pNode->m_pParent.load( order );
+ return pNode->parent( order );
}
- // RCU safe disposer
+ // RCU safe disposer
class rcu_disposer
{
node_type * m_pRetiredList; ///< head of retired node list
pNode->m_pNextRemoved = m_pRetiredList;
m_pRetiredList = pNode;
}
-
+
void dispose_value( mapped_type pVal )
{
assert( m_pRetiredValue == nullptr );
m_pRetiredValue = pVal;
}
-
+
private:
struct internal_disposer
{
void clean()
{
assert( !gc::is_locked() );
-
+
// TODO: use RCU::batch_retire
// Dispose nodes
assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr );
CDS_UNUSED( pNode );
return pVal;
- },
+ },
update_flags::allow_insert
) == update_flags::result_inserted;
}
std::pair<bool, bool> update( K const& key, mapped_type pVal, bool bInsert = true )
{
int result = do_update( key, key_comparator(),
- [pVal]( node_type * ) -> mapped_type
+ [pVal]( node_type * ) -> mapped_type
{
return pVal;
},
- update_flags::allow_update | (bInsert ? update_flags::allow_insert : 0)
+ update_flags::allow_update | (bInsert ? update_flags::allow_insert : 0)
);
return std::make_pair( result != 0, (result & update_flags::result_inserted) != 0 );
}
bool erase_with( K const& key, Less pred )
{
CDS_UNUSED( pred );
- return do_remove(
- key,
+ return do_remove(
+ key,
cds::opt::details::make_comparator_from_less<Less>(),
[]( key_type const&, mapped_type pVal, rcu_disposer& disp ) -> bool { disp.dispose_value( pVal ); return true; }
);
template <typename K, typename Func>
bool erase( K const& key, Func f )
{
- return do_remove(
- key,
- key_comparator(),
- [&f]( key_type const& key, mapped_type pVal, rcu_disposer& disp ) -> bool {
+ return do_remove(
+ key,
+ key_comparator(),
+ [&f]( key_type const& key, mapped_type pVal, rcu_disposer& disp ) -> bool {
assert( pVal );
- f( key, *pVal );
- disp.dispose_value(pVal);
+ f( key, *pVal );
+ disp.dispose_value(pVal);
return true;
}
);
bool erase_with( K const& key, Less pred, Func f )
{
CDS_UNUSED( pred );
- return do_remove(
- key,
+ return do_remove(
+ key,
cds::opt::details::make_comparator_from_less<Less>(),
- [&f]( key_type const& key, mapped_type pVal, rcu_disposer& disp ) -> bool {
+ [&f]( key_type const& key, mapped_type pVal, rcu_disposer& disp ) -> bool {
assert( pVal );
- f( key, *pVal );
- disp.dispose_value(pVal);
+ f( key, *pVal );
+ disp.dispose_value(pVal);
return true;
}
);
template <typename K, typename Func>
bool find( K const& key, Func f )
{
- return do_find( key, key_comparator(),
+ return do_find( key, key_comparator(),
[&f]( node_type * pNode ) -> bool {
assert( pNode != nullptr );
mapped_type pVal = pNode->m_pValue.load( memory_model::memory_order_relaxed );
bool find_with( K const& key, Less pred, Func f )
{
CDS_UNUSED( pred );
- return do_find( key, cds::opt::details::make_comparator_from_less<Less>(),
+ return do_find( key, cds::opt::details::make_comparator_from_less<Less>(),
[&f]( node_type * pNode ) -> bool {
assert( pNode != nullptr );
mapped_type pVal = pNode->m_pValue.load( memory_model::memory_order_relaxed );
return true;
}
return false;
- }
+ }
);
}
void operator()( size_t nLevel, size_t hLeft, size_t hRight );
};
\endcode
- where
+ where
- \p nLevel - the level where the violation is found
- \p hLeft - the height of left subtree
- \p hRight - the height of right subtree
find_result result;
{
rcu_lock l;
- result = try_find( key, cmp, f, m_pRoot, 1, 0 );
+ result = try_find( key, cmp, f, m_pRoot, right_child, 0 );
}
assert( result != find_result::retry );
return result == find_result::found;
{
rcu_lock l;
- int result = update_flags::failed;
- do {
+ while ( true ) {
+ int result;
+
// get right child of root
node_type * pChild = child( m_pRoot, right_child, memory_model::memory_order_acquire );
if ( pChild ) {
else if ( pChild == child( m_pRoot, right_child, memory_model::memory_order_acquire )) {
result = try_extract_minmax( nDir, func, m_pRoot, pChild, nChildVersion, removed_list );
}
+ else
+ result = update_flags::retry;
}
- } while ( result == update_flags::retry );
+ else
+ return;
+
+ if ( result == update_flags::retry )
+ m_stat.onRemoveRetry();
+ }
}
}
while ( true ) {
node_type * pChild = child( pNode, nDir );
if ( !pChild ) {
- if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
- m_stat.onFindRetry();
+ if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
return find_result::retry;
- }
m_stat.onFindFailed();
return find_result::not_found;
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 ) {
- m_stat.onFindRetry();
+ if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
return find_result::retry;
- }
}
- else if ( nChildVersion != node_type::unlinked ) {
- if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
- m_stat.onFindRetry();
+ 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 ) {
- m_stat.onFindRetry();
+ if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
return find_result::retry;
- }
+
+ m_stat.onFindRetry();
}
}
{
assert( gc::is_locked() );
- int result;
- do {
+ while ( true ) {
+ int result;
+
// get right child of root
node_type * pChild = child( m_pRoot, right_child, memory_model::memory_order_acquire );
if ( pChild ) {
pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
result = update_flags::retry;
}
- else if ( pChild == child( m_pRoot, right_child, memory_model::memory_order_acquire )) {
+ else if ( pChild == child( m_pRoot, right_child, memory_model::memory_order_acquire ))
result = try_update( key, cmp, nFlags, funcUpdate, pChild, nChildVersion, disp );
- }
else
result = update_flags::retry;
- }
+ }
else {
// the tree is empty
if ( nFlags & update_flags::allow_insert ) {
return update_flags::failed;
}
- } while ( result == update_flags::retry );
- return result;
+
+ if ( result == update_flags::retry )
+ m_stat.onUpdateRetry();
+ else
+ return result;
+ }
}
template <typename K, typename Compare, typename Func>
{
assert( gc::is_locked() );
- int result;
- do {
+ while ( true ) {
+ int result;
+
// get right child of root
node_type * pChild = child( m_pRoot, right_child, memory_model::memory_order_acquire );
if ( pChild ) {
}
else
return false;
- } while ( result == update_flags::retry );
- return result == update_flags::result_removed;
+ if ( result == update_flags::retry )
+ m_stat.onRemoveRetry();
+ else
+ return result == update_flags::result_removed;
+ }
}
template <typename K, typename Compare, typename Func>
int nCmp = cmp( key, pNode->m_key );
if ( nCmp == 0 ) {
- if ( nFlags & update_flags::allow_update ) {
+ if ( nFlags & update_flags::allow_update )
return try_update_node( funcUpdate, pNode, nVersion, disp );
- }
return update_flags::failed;
}
- int result;
- do {
+ while ( true ) {
+ int result;
node_type * pChild = child( pNode, nCmp );
- if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
- m_stat.onUpdateRetry();
+ if ( pNode->version(memory_model::memory_order_acquire) != nVersion )
return update_flags::retry;
- }
if ( pChild == nullptr ) {
// insert new node
}
else {
// update child
- result = update_flags::retry;
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 ) {
- m_stat.onUpdateRetry();
+ 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
// 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 && pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
+ if ( result == update_flags::retry ) {
+ if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
+ return update_flags::retry;
m_stat.onUpdateRetry();
- return update_flags::retry;
}
- } while ( result == update_flags::retry );
- return result;
+ else
+ return result;
+ }
}
template <typename K, typename Compare, typename Func>
if ( nCmp == 0 )
return try_remove_node( pParent, pNode, nVersion, func, disp );
- int result;
- do {
+ while ( true ) {
+ int result;
+
node_type * pChild = child( pNode, nCmp );
- if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
- m_stat.onRemoveRetry();
+ if ( pNode->version(memory_model::memory_order_acquire) != nVersion )
return update_flags::retry;
- }
- if ( pChild == nullptr ) {
+ if ( pChild == nullptr )
return update_flags::failed;
- }
else {
// update child
result = update_flags::retry;
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, 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 ) {
- m_stat.onRemoveRetry();
+ 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
// 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 && pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
+ if ( result == update_flags::retry ) {
+ if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
+ return update_flags::retry;
m_stat.onRemoveRetry();
- return update_flags::retry;
}
- } while ( result == update_flags::retry );
- return result;
+ else
+ return result;
+ }
}
template <typename Func>
assert( gc::is_locked() );
assert( nVersion != node_type::unlinked );
- int result;
- do {
+ while ( true ) {
+ int result;
node_type * pChild = child( pNode, nDir );
- if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
- m_stat.onRemoveRetry();
+ if ( pNode->version(memory_model::memory_order_acquire) != nVersion )
return update_flags::retry;
- }
if ( pChild == nullptr ) {
// Found min/max
return try_remove_node( pParent, pNode, nVersion, func, disp );
}
else {
- result = update_flags::retry;
+ //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 ) {
- m_stat.onRemoveRetry();
+ 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
// 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 && pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
+ if ( result == update_flags::retry ) {
+ if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
+ return update_flags::retry;
m_stat.onRemoveRetry();
- return update_flags::retry;
}
- } while ( result == update_flags::retry );
- return result;
+ else
+ return result;
+ }
}
template <typename K, typename Func>
if ( c_bRelaxedInsert ) {
if ( pNode->version( memory_model::memory_order_acquire ) != nVersion
- || child( pNode, nDir ) != nullptr )
+ || child( pNode, nDir ) != 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 ) != nullptr )
{
if ( c_bRelaxedInsert ) {
mapped_type pVal = pNew->m_pValue.load( memory_model::memory_order_relaxed );
{
node_scoped_lock l( m_Monitor, *pNode );
- if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
- m_stat.onUpdateRetry();
+ if ( pNode->version(memory_model::memory_order_acquire) != nVersion )
return update_flags::retry;
- }
if ( pNode->is_unlinked( memory_model::memory_order_relaxed )) {
m_stat.onUpdateUnlinked();
if ( !pNode->is_valued( atomics::memory_order_relaxed ) )
return update_flags::failed;
- if ( child( pNode, left_child ) == nullptr || child( pNode, right_child ) == nullptr ) {
+ if ( child( pNode, left_child ) == nullptr || child( pNode, right_child ) == nullptr ) {
node_type * pDamaged;
mapped_type pOld;
{
node_scoped_lock ln( m_Monitor, *pNode );
pOld = pNode->value( memory_model::memory_order_relaxed );
if ( !( pNode->version( memory_model::memory_order_acquire ) == nVersion
- && pOld
+ && pOld
&& try_unlink_locked( pParent, pNode, disp )))
{
return update_flags::retry;
pParent->m_pRight.store( pSplice, memory_model::memory_order_relaxed );
if ( pSplice )
- pSplice->m_pParent.store( pParent, memory_model::memory_order_release );
+ pSplice->parent( pParent, memory_model::memory_order_relaxed );
// Mark the node as unlinked
pNode->version( node_type::unlinked, memory_model::memory_order_release );
pNode->m_pLeft.store( pLRight, memory_model::memory_order_relaxed );
if ( pLRight != nullptr )
- pLRight->m_pParent.store( pNode, memory_model::memory_order_relaxed );
+ pLRight->parent( pNode, memory_model::memory_order_relaxed );
atomics::atomic_thread_fence( memory_model::memory_order_release );
pLeft->m_pRight.store( pNode, memory_model::memory_order_relaxed );
- pNode->m_pParent.store( pLeft, memory_model::memory_order_relaxed );
+ pNode->parent( pLeft, memory_model::memory_order_relaxed );
atomics::atomic_thread_fence( memory_model::memory_order_release );
assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
pParent->m_pRight.store( pLeft, memory_model::memory_order_relaxed );
}
- pLeft->m_pParent.store( pParent, memory_model::memory_order_relaxed );
+ pLeft->parent( pParent, memory_model::memory_order_relaxed );
atomics::atomic_thread_fence( memory_model::memory_order_release );
// 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 );
if ( pRLeft != nullptr )
- pRLeft->m_pParent.store( pNode, memory_model::memory_order_relaxed );
+ pRLeft->parent( pNode, memory_model::memory_order_relaxed );
atomics::atomic_thread_fence( memory_model::memory_order_release );
pRight->m_pLeft.store( pNode, memory_model::memory_order_relaxed );
- pNode->m_pParent.store( pRight, memory_model::memory_order_relaxed );
+ pNode->parent( pRight, memory_model::memory_order_relaxed );
atomics::atomic_thread_fence( memory_model::memory_order_release );
assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
pParent->m_pRight.store( pRight, memory_model::memory_order_relaxed );
}
- pRight->m_pParent.store( pParent, memory_model::memory_order_relaxed );
+ pRight->parent( pParent, memory_model::memory_order_relaxed );
atomics::atomic_thread_fence( memory_model::memory_order_release );
// fix up pNode links, careful about the order!
pNode->m_pLeft.store( pLRR, memory_model::memory_order_relaxed );
if ( pLRR != nullptr )
- pLRR->m_pParent.store( pNode, memory_model::memory_order_relaxed );
+ pLRR->parent( pNode, memory_model::memory_order_relaxed );
atomics::atomic_thread_fence( memory_model::memory_order_release );
pLeft->m_pRight.store( pLRL, memory_model::memory_order_relaxed );
if ( pLRL != nullptr )
- pLRL->m_pParent.store( pLeft, memory_model::memory_order_relaxed );
+ pLRL->parent( pLeft, memory_model::memory_order_relaxed );
atomics::atomic_thread_fence( memory_model::memory_order_release );
pLRight->m_pLeft.store( pLeft, memory_model::memory_order_relaxed );
- pLeft->m_pParent.store( pLRight, memory_model::memory_order_relaxed );
+ pLeft->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_relaxed );
- pNode->m_pParent.store( pLRight, memory_model::memory_order_relaxed );
+ pNode->parent( pLRight, memory_model::memory_order_relaxed );
atomics::atomic_thread_fence( memory_model::memory_order_release );
if ( pPL == pNode )
assert( child( pParent, right_child ) == pNode );
pParent->m_pRight.store( pLRight, memory_model::memory_order_relaxed );
}
- pLRight->m_pParent.store( pParent, memory_model::memory_order_relaxed );
+ pLRight->parent( pParent, memory_model::memory_order_relaxed );
atomics::atomic_thread_fence( memory_model::memory_order_release );
// fix up heights
// fix up pNode links, careful about the order!
pNode->m_pRight.store( pRLL, memory_model::memory_order_relaxed );
if ( pRLL != nullptr )
- pRLL->m_pParent.store( pNode, memory_model::memory_order_relaxed );
+ pRLL->parent( pNode, memory_model::memory_order_relaxed );
atomics::atomic_thread_fence( memory_model::memory_order_release );
pRight->m_pLeft.store( pRLR, memory_model::memory_order_relaxed );
if ( pRLR != nullptr )
- pRLR->m_pParent.store( pRight, memory_model::memory_order_relaxed );
+ pRLR->parent( pRight, memory_model::memory_order_relaxed );
atomics::atomic_thread_fence( memory_model::memory_order_release );
pRLeft->m_pRight.store( pRight, memory_model::memory_order_relaxed );
- pRight->m_pParent.store( pRLeft, memory_model::memory_order_relaxed );
+ pRight->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_relaxed );
- pNode->m_pParent.store( pRLeft, memory_model::memory_order_relaxed );
+ pNode->parent( pRLeft, memory_model::memory_order_relaxed );
atomics::atomic_thread_fence( memory_model::memory_order_release );
if ( pPL == pNode )
assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
pParent->m_pRight.store( pRLeft, memory_model::memory_order_relaxed );
}
- pRLeft->m_pParent.store( pParent, memory_model::memory_order_relaxed );
+ pRLeft->parent( pParent, memory_model::memory_order_relaxed );
atomics::atomic_thread_fence( memory_model::memory_order_release );
// fix up heights
projects / libcds.git / blobdiff