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:
typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock> check_deadlock_policy;
- static void clear_links( node_type * pNode )
- {
- pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_release );
- pNode->m_pDelChain = nullptr;
- }
-
struct clear_and_dispose {
void operator()( value_type * p )
{
}
};
- static void dispose_node( node_type * pNode )
- {
- assert( pNode );
- assert( !gc::is_locked() );
-
- gc::template retire_ptr<clear_and_dispose>( node_traits::to_value_ptr( *pNode ) );
- }
-
- static void dispose_chain( node_type * pChain )
- {
- if ( pChain ) {
- assert( !gc::is_locked() );
-
- auto f = [&pChain]() -> cds::urcu::retired_ptr {
- node_type * p = pChain;
- if ( p ) {
- pChain = p->m_pDelChain;
- return cds::urcu::make_retired_ptr<clear_and_dispose>( node_traits::to_value_ptr( p ));
- }
- return cds::urcu::make_retired_ptr<clear_and_dispose>( static_cast<value_type *>(nullptr));
- };
- gc::batch_retire(std::ref(f));
- }
- }
-
/// Position pointer for item search
struct position {
atomic_node_ptr * pPrev ; ///< Previous node
dispose_chain( pDelChain );
}
};
-
//@endcond
public:
/// Result of \p get(), \p get_with() functions - pointer to the node found
typedef cds::urcu::raw_ptr< gc, value_type, raw_ptr_disposer > raw_ptr;
- protected:
- //@cond
-
- bool link_node( node_type * pNode, position& pos )
- {
- assert( pNode != nullptr );
- link_checker::is_empty( pNode );
-
- marked_node_ptr p( pos.pCur );
- pNode->m_pNext.store( p, memory_model::memory_order_release );
- if ( cds_likely( pos.pPrev->compare_exchange_strong( p, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed )))
- return true;
-
- pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
- return false;
- }
-
- static void link_to_remove_chain( position& pos, node_type * pDel )
- {
- assert( pDel->m_pDelChain == nullptr );
-
- pDel->m_pDelChain = pos.pDelChain;
- pos.pDelChain = pDel;
- }
-
- bool unlink_node( position& pos, erase_node_mask nMask )
- {
- assert(gc::is_locked() );
-
- // Mark the node (logical deletion)
- marked_node_ptr next(pos.pNext, 0);
-
- if ( cds_likely( pos.pCur->m_pNext.compare_exchange_strong( next, next | nMask, memory_model::memory_order_release, atomics::memory_order_relaxed ))) {
-
- // Try physical removal - fast path
- marked_node_ptr cur(pos.pCur);
- if ( cds_likely( pos.pPrev->compare_exchange_strong(cur, marked_node_ptr(pos.pNext), memory_model::memory_order_acquire, atomics::memory_order_relaxed ))) {
- if ( nMask == erase_mask )
- link_to_remove_chain( pos, pos.pCur );
- }
- else {
- // Slow path
- search( pos.refHead, *node_traits::to_value_ptr( pos.pCur ), pos, key_comparator() );
- }
- return true;
- }
- return false;
- }
- //@endcond
-
protected:
//@cond
template <bool IsConst>
template <typename Q>
bool erase( Q const& key )
{
- return erase_at( m_pHead, key, key_comparator() );
+ return erase_at( m_pHead, key, key_comparator());
}
/// Deletes the item from the list using \p pred predicate for searching
bool erase_with( Q const& key, Less pred )
{
CDS_UNUSED( pred );
- return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
+ return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
}
/// Deletes the item from the list
rcu_michael_list::exempt_ptr p1;
// The RCU should NOT be locked when extract() is called!
- assert( !rcu::is_locked() );
+ assert( !rcu::is_locked());
// You can call extract() function
p1 = theList.extract( 10 );
template <typename Q>
exempt_ptr extract( Q const& key )
{
- return exempt_ptr( extract_at( m_pHead, key, key_comparator() ));
+ return exempt_ptr( extract_at( m_pHead, key, key_comparator()));
}
/// Extracts an item from the list using \p pred predicate for searching
exempt_ptr extract_with( Q const& key, Less pred )
{
CDS_UNUSED( pred );
- return exempt_ptr( extract_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() ));
+ return exempt_ptr( extract_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>()));
}
/// Find the key \p val
template <typename Q>
bool contains( Q const& key )
{
- return find_at( m_pHead, key, key_comparator() );
+ return find_at( m_pHead, key, key_comparator());
}
//@cond
template <typename Q>
bool contains( Q const& key, Less pred )
{
CDS_UNUSED( pred );
- return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
+ return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
}
//@cond
template <typename Q, typename Less>
*/
void clear()
{
- if( !empty() ) {
+ if( !empty()) {
check_deadlock_policy::check();
marked_node_ptr pHead;
{
rcu_lock l;
pHead = m_pHead.load(memory_model::memory_order_acquire);
- if ( !pHead.ptr() )
+ if ( !pHead.ptr())
break;
- marked_node_ptr pNext( pHead->m_pNext.load(memory_model::memory_order_relaxed) );
+ marked_node_ptr pNext( pHead->m_pNext.load(memory_model::memory_order_relaxed));
if ( cds_unlikely( !pHead->m_pNext.compare_exchange_weak( pNext, pNext | 1, memory_model::memory_order_acquire, memory_model::memory_order_relaxed )))
continue;
if ( cds_unlikely( !m_pHead.compare_exchange_weak( pHead, marked_node_ptr(pNext.ptr()), memory_model::memory_order_release, memory_model::memory_order_relaxed )))
}
--m_ItemCounter;
- dispose_node( pHead.ptr() );
+ dispose_node( pHead.ptr());
}
}
}
{
return m_Stat;
}
+
protected:
//@cond
+ static void clear_links( node_type * pNode )
+ {
+ pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_release );
+ pNode->m_pDelChain = nullptr;
+ }
+
+ static void dispose_node( node_type * pNode )
+ {
+ assert( pNode );
+ assert( !gc::is_locked());
+
+ gc::template retire_ptr<clear_and_dispose>( node_traits::to_value_ptr( *pNode ));
+ }
+
+ static void dispose_chain( node_type * pChain )
+ {
+ if ( pChain ) {
+ assert( !gc::is_locked());
+
+ auto f = [&pChain]() -> cds::urcu::retired_ptr {
+ node_type * p = pChain;
+ if ( p ) {
+ pChain = p->m_pDelChain;
+ return cds::urcu::make_retired_ptr<clear_and_dispose>( node_traits::to_value_ptr( p ));
+ }
+ return cds::urcu::make_retired_ptr<clear_and_dispose>( static_cast<value_type *>(nullptr));
+ };
+ gc::batch_retire( std::ref( f ));
+ }
+ }
+
+ bool link_node( node_type * pNode, position& pos )
+ {
+ assert( pNode != nullptr );
+ link_checker::is_empty( pNode );
+
+ marked_node_ptr p( pos.pCur );
+ pNode->m_pNext.store( p, memory_model::memory_order_release );
+ if ( cds_likely( pos.pPrev->compare_exchange_strong( p, marked_node_ptr( pNode ), memory_model::memory_order_release, atomics::memory_order_relaxed )))
+ return true;
+
+ pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
+ return false;
+ }
+
+ static void link_to_remove_chain( position& pos, node_type * pDel )
+ {
+ assert( pDel->m_pDelChain == nullptr );
+
+ pDel->m_pDelChain = pos.pDelChain;
+ pos.pDelChain = pDel;
+ }
+
+ bool unlink_node( position& pos, erase_node_mask nMask )
+ {
+ assert( gc::is_locked());
+
+ // Mark the node (logical deletion)
+ marked_node_ptr next( pos.pNext, 0 );
+
+ if ( cds_likely( pos.pCur->m_pNext.compare_exchange_strong( next, next | nMask, memory_model::memory_order_release, atomics::memory_order_relaxed ))) {
+
+ // Try physical removal - fast path
+ marked_node_ptr cur( pos.pCur );
+ if ( cds_likely( pos.pPrev->compare_exchange_strong( cur, marked_node_ptr( pos.pNext ), memory_model::memory_order_acquire, atomics::memory_order_relaxed ))) {
+ if ( nMask == erase_mask )
+ link_to_remove_chain( pos, pos.pCur );
+ }
+ else {
+ // Slow path
+ search( pos.refHead, *node_traits::to_value_ptr( pos.pCur ), pos, key_comparator());
+ }
+ return true;
+ }
+ return false;
+ }
+
// split-list support
bool insert_aux_node( node_type * pNode )
{
// Hack: convert node_type to value_type.
// In principle, auxiliary node can be non-reducible to value_type
// We assume that comparator can correctly distinguish between aux and regular node.
- return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
+ return insert_at( refHead, *node_traits::to_value_ptr( pNode ));
}
bool insert_at( atomic_node_ptr& refHead, value_type& val )
return false;
}
- if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
+ if ( link_node( node_traits::to_node_ptr( val ), pos )) {
f( val );
++m_ItemCounter;
m_Stat.onInsertSuccess();
for (;;) {
{
rcu_lock l;
- if ( !search( refHead, val, pos, key_comparator() ) || node_traits::to_value_ptr( *pos.pCur ) != &val ) {
+ if ( !search( refHead, val, pos, key_comparator()) || node_traits::to_value_ptr( *pos.pCur ) != &val ) {
m_Stat.onEraseFailed();
return false;
}
for (;;) {
{
rcu_lock l;
- if ( !search( pos.refHead, val, pos, cmp ) ) {
+ if ( !search( pos.refHead, val, pos, cmp )) {
m_Stat.onEraseFailed();
return false;
}
}
}
assert( pDel );
- f( *node_traits::to_value_ptr( pDel ) );
+ f( *node_traits::to_value_ptr( pDel ));
--m_ItemCounter;
m_Stat.onEraseSuccess();
return true;
{
position pos( refHead );
back_off bkoff;
- assert( !gc::is_locked() ) ; // RCU must not be locked!!!
+ assert( !gc::is_locked()) ; // RCU must not be locked!!!
node_type * pExtracted;
{
{
rcu_lock l;
- if ( search( refHead, val, pos, cmp ) ) {
+ if ( search( refHead, val, pos, cmp )) {
assert( pos.pCur != nullptr );
f( *node_traits::to_value_ptr( *pos.pCur ), val );
m_Stat.onFindSuccess();
raw_ptr get_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
{
// RCU should be locked!
- assert(gc::is_locked() );
+ assert(gc::is_locked());
position pos( refHead );
bool search( atomic_node_ptr& refHead, const Q& val, position& pos, Compare cmp )
{
// RCU lock should be locked!!!
- assert( gc::is_locked() );
+ assert( gc::is_locked());
atomic_node_ptr * pPrev;
marked_node_ptr pNext;
pNext = nullptr;
while ( true ) {
- if ( !pCur.ptr() ) {
+ if ( !pCur.ptr()) {
pos.pPrev = pPrev;
pos.pCur = nullptr;
pos.pNext = nullptr;
goto try_again;
}
- if ( pNext.bits() ) {
+ if ( pNext.bits()) {
// pCur is marked as deleted. Try to unlink it from the list
- if ( cds_likely( pPrev->compare_exchange_weak( pCur, marked_node_ptr( pNext.ptr() ), memory_model::memory_order_acquire, atomics::memory_order_relaxed ))) {
+ if ( cds_likely( pPrev->compare_exchange_weak( pCur, marked_node_ptr( pNext.ptr()), memory_model::memory_order_acquire, atomics::memory_order_relaxed ))) {
if ( pNext.bits() == erase_mask )
- link_to_remove_chain( pos, pCur.ptr() );
+ link_to_remove_chain( pos, pCur.ptr());
m_Stat.onHelpingSuccess();
}
}
assert( pCur.ptr() != nullptr );
- int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
+ int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
if ( nCmp >= 0 ) {
pos.pPrev = pPrev;
pos.pCur = pCur.ptr();
bool insert_at_locked( position& pos, value_type& val )
{
// RCU lock should be locked!!!
- assert( gc::is_locked() );
+ assert( gc::is_locked());
while ( true ) {
- if ( search( pos.refHead, val, pos, key_comparator() )) {
+ if ( search( pos.refHead, val, pos, key_comparator())) {
m_Stat.onInsertFailed();
return false;
}
- if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
+ if ( link_node( node_traits::to_node_ptr( val ), pos )) {
++m_ItemCounter;
m_Stat.onInsertSuccess();
return true;
std::pair<iterator, bool> update_at_locked( position& pos, value_type& val, Func func, bool bInsert )
{
// RCU should be locked!!!
- assert( gc::is_locked() );
+ assert( gc::is_locked());
while ( true ) {
- if ( search( pos.refHead, val, pos, key_comparator() ) ) {
- assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
+ if ( search( pos.refHead, val, pos, key_comparator())) {
+ assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur )) == 0 );
func( false, *node_traits::to_value_ptr( *pos.pCur ), val );
m_Stat.onUpdateExisting();
return std::make_pair( end(), false );
}
- if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
+ if ( link_node( node_traits::to_node_ptr( val ), pos )) {
++m_ItemCounter;
func( true, val , val );
m_Stat.onUpdateNew();
template <typename Q, typename Compare>
const_iterator find_at_locked( position& pos, Q const& val, Compare cmp )
{
- assert( gc::is_locked() );
+ assert( gc::is_locked());
- if ( search( pos.refHead, val, pos, cmp ) ) {
+ if ( search( pos.refHead, val, pos, cmp )) {
assert( pos.pCur != nullptr );
m_Stat.onFindSuccess();
return const_iterator( pos.pCur );
projects / libcds.git / blobdiff