/** @ingroup cds_intrusive_list
\anchor cds_intrusive_IterableList_hp
- This lock-free list implementation supports thread-safe iterators.
+ This non-blocking list implementation supports thread-safe iterators;
+ searching and removing are lock-free, inserting is non-blocking because it
+ uses a light-weight synchronization based on marked pointers.
+
Unlike \p cds::intrusive::MichaelList the iterable list does not require
any hook in \p T to be stored in the list.
#endif
>
class IterableList
+#ifndef CDS_DOXYGEN_INVOKED
+ : public iterable_list_tag
+#endif
{
public:
typedef T value_type; ///< type of value stored in the list
typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
- static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 2; ///< Count of hazard pointer required for the algorithm
+ static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 4; ///< Count of hazard pointer required for the algorithm
//@cond
// Rebind traits (split-list support)
//@cond
typedef atomics::atomic< node_type* > atomic_node_ptr; ///< Atomic node pointer
typedef atomic_node_ptr auxiliary_head; ///< Auxiliary head type (for split-list support)
+ typedef typename node_type::marked_data_ptr marked_data_ptr;
+
+ node_type m_Head;
+ node_type m_Tail;
- atomic_node_ptr m_pHead; ///< Head pointer
item_counter m_ItemCounter; ///< Item counter
mutable stat m_Stat; ///< Internal statistics
/// Position pointer for item search
struct position {
- atomic_node_ptr * pHead; ///< Previous node (pointer to pPrev->next or to m_pHead)
+ node_type const* pHead;
node_type * pPrev; ///< Previous node
node_type * pCur; ///< Current node
- value_type * pFound; ///< Value of \p pCur->data, valid only if data found
- typename gc::Guard guard; ///< guard for \p pFound
+ value_type * pFound; ///< Value of \p pCur->data, valid only if data found
+
+ typename gc::Guard guard; ///< guard for \p pFound
+ };
+
+ struct insert_position: public position
+ {
+ value_type * pPrevVal; ///< Value of \p pPrev->data, can be \p nullptr
+ typename gc::Guard prevGuard; ///< guard for \p pPrevVal
};
//@endcond
friend class IterableList;
protected:
- node_type* m_pNode;
+ node_type const* m_pNode;
typename gc::Guard m_Guard; // data guard
void next()
{
- while ( m_pNode ) {
- m_pNode = m_pNode->next.load( memory_model::memory_order_acquire );
- if ( !m_pNode ) {
- m_Guard.clear();
- break;
- }
- if ( m_Guard.protect( m_pNode->data ))
- break;
+ for ( node_type* p = m_pNode->next.load( memory_model::memory_order_relaxed ); p != m_pNode; p = p->next.load( memory_model::memory_order_relaxed ))
+ {
+ m_pNode = p;
+ if ( m_Guard.protect( p->data, []( marked_data_ptr p ) { return p.ptr(); }).ptr())
+ return;
}
+ m_Guard.clear();
}
- explicit iterator_type( atomic_node_ptr const& pNode )
- : m_pNode( pNode.load( memory_model::memory_order_acquire ))
+ explicit iterator_type( node_type const* pNode )
+ : m_pNode( pNode )
{
- if ( m_pNode ) {
- if ( !m_Guard.protect( m_pNode->data ))
- next();
- }
+ if ( !m_Guard.protect( pNode->data, []( marked_data_ptr p ) { return p.ptr(); }).ptr())
+ next();
}
- iterator_type( node_type* pNode, value_type* pVal )
+ iterator_type( node_type const* pNode, value_type* pVal )
: m_pNode( pNode )
{
if ( m_pNode ) {
value_ptr operator ->() const
{
- return m_Guard.get<value_type>();
+ return m_Guard.template get<value_type>();
}
value_ref operator *() const
{
assert( m_Guard.get_native() != nullptr );
- return *m_Guard.get<value_type>();
+ return *m_Guard.template get<value_type>();
}
/// Pre-increment
this code
\code
if ( it1 == it2 )
- assert( &(*it1) == &(*it2) );
+ assert( &(*it1) == &(*it2));
\endcode
can throw assertion. The point is that the iterator stores the value of element which can be modified later by other thread.
The guard inside the iterator prevents recycling that value so the iterator's value remains valid even after such changing.
*/
iterator begin()
{
- return iterator( m_pHead );
+ return iterator( &m_Head );
}
/// Returns an iterator that addresses the location succeeding the last element in a list
*/
iterator end()
{
- return iterator();
+ return iterator( &m_Tail );
}
/// Returns a forward const iterator addressing the first element in a list
const_iterator cbegin() const
{
- return const_iterator( m_pHead );
+ return const_iterator( &m_Head );
}
/// Returns a forward const iterator addressing the first element in a list
const_iterator begin() const
{
- return const_iterator( m_pHead );
+ return const_iterator( &m_Head );
}
/// Returns an const iterator that addresses the location succeeding the last element in a list
const_iterator end() const
{
- return const_iterator();
+ return const_iterator( &m_Tail );
}
/// Returns an const iterator that addresses the location succeeding the last element in a list
const_iterator cend() const
{
- return const_iterator();
+ return const_iterator( &m_Tail );
}
//@}
public:
/// Default constructor initializes empty list
IterableList()
- : m_pHead( nullptr )
- {}
+ {
+ init_list();
+ }
//@cond
template <typename Stat, typename = std::enable_if<std::is_same<stat, iterable_list::wrapped_stat<Stat>>::value >>
explicit IterableList( Stat& st )
- : m_pHead( nullptr )
- , m_Stat( st )
- {}
+ : m_Stat( st )
+ {
+ init_list();
+ }
//@endcond
/// Destroys the list object
*/
bool insert( value_type& val )
{
- return insert_at( m_pHead, val );
+ return insert_at( &m_Head, val );
}
/// Inserts new node
template <typename Func>
bool insert( value_type& val, Func f )
{
- return insert_at( m_pHead, val, f );
+ return insert_at( &m_Head, val, f );
}
/// Updates the node
template <typename Func>
std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
{
- return update_at( m_pHead, val, func, bInsert );
+ return update_at( &m_Head, val, func, bInsert );
}
/// Insert or update
*/
std::pair<bool, bool> upsert( value_type& val, bool bInsert = true )
{
- return update_at( m_pHead, val, []( value_type&, value_type* ) {}, bInsert );
+ return upsert_at( &m_Head, val, bInsert );
}
/// Unlinks the item \p val from the list
*/
bool unlink( value_type& val )
{
- return unlink_at( m_pHead, val );
+ return unlink_at( &m_Head, val );
}
/// Deletes the item from the list
template <typename Q>
bool erase( Q const& key )
{
- return erase_at( m_pHead, key, key_comparator());
+ return erase_at( &m_Head, 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_Head, key, cds::opt::details::make_comparator_from_less<Less>());
}
/// Deletes the item from the list
template <typename Q, typename Func>
bool erase( Q const& key, Func func )
{
- return erase_at( m_pHead, key, key_comparator(), func );
+ return erase_at( &m_Head, key, key_comparator(), func );
}
/// Deletes the item from the list using \p pred predicate for searching
bool erase_with( Q const& key, Less pred, Func f )
{
CDS_UNUSED( pred );
- return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
+ return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
}
/// Extracts the item from the list with specified \p key
template <typename Q>
guarded_ptr extract( Q const& key )
{
- return extract_at( m_pHead, key, key_comparator());
+ return extract_at( &m_Head, key, key_comparator());
}
/// Extracts the item using compare functor \p pred
guarded_ptr extract_with( Q const& key, Less pred )
{
CDS_UNUSED( pred );
- return extract_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
+ return extract_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
}
/// Finds \p key in the list
template <typename Q, typename Func>
bool find( Q& key, Func f ) const
{
- return find_at( m_pHead, key, key_comparator(), f );
+ return find_at( &m_Head, key, key_comparator(), f );
}
//@cond
template <typename Q, typename Func>
bool find( Q const& key, Func f ) const
{
- return find_at( m_pHead, key, key_comparator(), f );
+ return find_at( &m_Head, key, key_comparator(), f );
}
//@endcond
template <typename Q>
iterator find( Q const& key ) const
{
- return find_iterator_at( m_pHead, key, key_comparator());
+ return find_iterator_at( &m_Head, key, key_comparator());
}
/// Finds the \p key using \p pred predicate for searching
bool find_with( Q& key, Less pred, Func f ) const
{
CDS_UNUSED( pred );
- return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
+ return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
}
//@cond
template <typename Q, typename Less, typename Func>
bool find_with( Q const& key, Less pred, Func f ) const
{
CDS_UNUSED( pred );
- return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
+ return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
}
//@endcond
iterator find_with( Q const& key, Less pred ) const
{
CDS_UNUSED( pred );
- return find_iterator_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
+ return find_iterator_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
}
/// Checks whether the list contains \p key
template <typename Q>
bool contains( Q const& key ) const
{
- return find_at( m_pHead, key, key_comparator());
+ return find_at( &m_Head, key, key_comparator());
}
/// Checks whether the list contains \p key using \p pred predicate for searching
bool contains( Q const& key, Less pred ) const
{
CDS_UNUSED( pred );
- return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
+ return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
}
/// Finds the \p key and return the item found
template <typename Q>
guarded_ptr get( Q const& key ) const
{
- return get_at( m_pHead, key, key_comparator());
+ return get_at( &m_Head, key, key_comparator());
}
/// Finds the \p key and return the item found
guarded_ptr get_with( Q const& key, Less pred ) const
{
CDS_UNUSED( pred );
- return get_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
+ return get_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
}
/// Clears the list (thread safe, not atomic)
void clear()
{
position pos;
- for ( pos.pCur = m_pHead.load( memory_model::memory_order_relaxed ); pos.pCur; pos.pCur = pos.pCur->next.load( memory_model::memory_order_relaxed )) {
+ pos.pPrev = nullptr;
+ for ( pos.pCur = m_Head.next.load( memory_model::memory_order_relaxed ); pos.pCur != pos.pPrev; pos.pCur = pos.pCur->next.load( memory_model::memory_order_relaxed )) {
while ( true ) {
- pos.pFound = pos.guard.protect( pos.pCur->data );
+ pos.pFound = pos.guard.protect( pos.pCur->data, []( marked_data_ptr p ) { return p.ptr(); }).ptr();
if ( !pos.pFound )
break;
- if ( cds_likely( unlink_node( pos ))) {
+ if ( cds_likely( unlink_data( pos ))) {
--m_ItemCounter;
break;
}
}
+ pos.pPrev = pos.pCur;
}
}
protected:
//@cond
-#if 0
+
// split-list support
bool insert_aux_node( node_type * pNode )
{
- return insert_aux_node( m_pHead, pNode );
+ return insert_aux_node( &m_Head, pNode );
}
// split-list support
- bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
+ bool insert_aux_node( node_type* pHead, node_type * pNode )
{
assert( pNode != nullptr );
+ assert( pNode->data.load( memory_model::memory_order_relaxed ) != nullptr );
+
+ insert_position pos;
+
+ while ( true ) {
+ if ( inserting_search( pHead, *pNode->data.load(memory_model::memory_order_relaxed).ptr(), pos, key_comparator())) {
+ m_Stat.onInsertFailed();
+ return false;
+ }
+
+ if ( link_aux_node( pNode, pos, pHead )) {
+ ++m_ItemCounter;
+ m_Stat.onInsertSuccess();
+ return true;
+ }
- // 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 aux and regular node.
- return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
+ m_Stat.onInsertRetry();
+ }
}
-#endif
- bool insert_at( atomic_node_ptr& refHead, value_type& val )
+ bool insert_at( node_type* pHead, value_type& val )
{
- position pos;
+ insert_position pos;
while ( true ) {
- if ( search( refHead, val, pos, key_comparator() )) {
+ if ( inserting_search( pHead, val, pos, key_comparator())) {
m_Stat.onInsertFailed();
return false;
}
- if ( link_node( &val, pos ) ) {
+ if ( link_data( &val, pos, pHead )) {
++m_ItemCounter;
m_Stat.onInsertSuccess();
return true;
}
template <typename Func>
- bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
+ bool insert_at( node_type* pHead, value_type& val, Func f )
{
- position pos;
+ insert_position pos;
typename gc::Guard guard;
guard.assign( &val );
while ( true ) {
- if ( search( refHead, val, pos, key_comparator() ) ) {
+ if ( inserting_search( pHead, val, pos, key_comparator())) {
m_Stat.onInsertFailed();
return false;
}
- if ( link_node( &val, pos ) ) {
+ if ( link_data( &val, pos, pHead )) {
f( val );
++m_ItemCounter;
m_Stat.onInsertSuccess();
}
template <typename Func>
- std::pair<bool, bool> update_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert )
+ std::pair<bool, bool> update_at( node_type* pHead, value_type& val, Func func, bool bInsert )
{
- position pos;
+ insert_position pos;
typename gc::Guard guard;
guard.assign( &val );
while ( true ) {
- if ( search( refHead, val, pos, key_comparator() ) ) {
+ if ( inserting_search( pHead, val, pos, key_comparator())) {
// try to replace pCur->data with val
assert( pos.pFound != nullptr );
assert( key_comparator()(*pos.pFound, val) == 0 );
- if ( cds_likely( pos.pCur->data.compare_exchange_strong( pos.pFound, &val, memory_model::memory_order_release, atomics::memory_order_relaxed ))) {
+ marked_data_ptr pFound( pos.pFound );
+ if ( cds_likely( pos.pCur->data.compare_exchange_strong( pFound, marked_data_ptr( &val ),
+ memory_model::memory_order_release, atomics::memory_order_relaxed )))
+ {
if ( pos.pFound != &val ) {
retire_data( pos.pFound );
func( val, pos.pFound );
return std::make_pair( false, false );
}
- if ( link_node( &val, pos )) {
+ if ( link_data( &val, pos, pHead )) {
func( val, static_cast<value_type*>( nullptr ));
++m_ItemCounter;
m_Stat.onUpdateNew();
}
}
- bool unlink_at( atomic_node_ptr& refHead, value_type& val )
+ std::pair<bool, bool> upsert_at( node_type* pHead, value_type& val, bool bInsert )
+ {
+ return update_at( pHead, val, []( value_type&, value_type* ) {}, bInsert );
+ }
+
+ bool unlink_at( node_type* pHead, value_type& val )
{
position pos;
back_off bkoff;
- while ( search( refHead, val, pos, key_comparator())) {
+ while ( search( pHead, val, pos, key_comparator())) {
if ( pos.pFound == &val ) {
- if ( unlink_node( pos )) {
+ if ( unlink_data( pos )) {
--m_ItemCounter;
m_Stat.onEraseSuccess();
return true;
}
template <typename Q, typename Compare, typename Func>
- bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f, position& pos )
+ bool erase_at( node_type* pHead, const Q& val, Compare cmp, Func f, position& pos )
{
back_off bkoff;
- while ( search( refHead, val, pos, cmp )) {
- if ( unlink_node( pos )) {
+ while ( search( pHead, val, pos, cmp )) {
+ if ( unlink_data( pos )) {
f( *pos.pFound );
--m_ItemCounter;
m_Stat.onEraseSuccess();
}
template <typename Q, typename Compare, typename Func>
- bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f )
+ bool erase_at( node_type* pHead, const Q& val, Compare cmp, Func f )
{
position pos;
- return erase_at( refHead, val, cmp, f, pos );
+ return erase_at( pHead, val, cmp, f, pos );
}
template <typename Q, typename Compare>
- bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
+ bool erase_at( node_type* pHead, Q const& val, Compare cmp )
{
position pos;
- return erase_at( refHead, val, cmp, [](value_type const&){}, pos );
+ return erase_at( pHead, val, cmp, [](value_type const&){}, pos );
}
template <typename Q, typename Compare>
- guarded_ptr extract_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
+ guarded_ptr extract_at( node_type* pHead, Q const& val, Compare cmp )
{
position pos;
back_off bkoff;
- while ( search( refHead, val, pos, cmp )) {
- if ( unlink_node( pos )) {
+ while ( search( pHead, val, pos, cmp )) {
+ if ( unlink_data( pos )) {
--m_ItemCounter;
m_Stat.onEraseSuccess();
assert( pos.pFound != nullptr );
}
template <typename Q, typename Compare>
- bool find_at( atomic_node_ptr const& refHead, Q const& val, Compare cmp ) const
+ bool find_at( node_type const* pHead, Q const& val, Compare cmp ) const
{
position pos;
- if ( search( refHead, val, pos, cmp ) ) {
+ if ( search( pHead, val, pos, cmp )) {
m_Stat.onFindSuccess();
return true;
}
}
template <typename Q, typename Compare, typename Func>
- bool find_at( atomic_node_ptr const& refHead, Q& val, Compare cmp, Func f ) const
+ bool find_at( node_type const* pHead, Q& val, Compare cmp, Func f ) const
{
position pos;
- if ( search( refHead, val, pos, cmp )) {
+ if ( search( pHead, val, pos, cmp )) {
assert( pos.pFound != nullptr );
f( *pos.pFound, val );
m_Stat.onFindSuccess();
}
template <typename Q, typename Compare>
- iterator find_iterator_at( atomic_node_ptr const& refHead, Q const& val, Compare cmp ) const
+ iterator find_iterator_at( node_type const* pHead, Q const& val, Compare cmp ) const
{
position pos;
- if ( search( refHead, val, pos, cmp )) {
+ if ( search( pHead, val, pos, cmp )) {
assert( pos.pCur != nullptr );
assert( pos.pFound != nullptr );
m_Stat.onFindSuccess();
}
m_Stat.onFindFailed();
- return iterator{};
+ return iterator( &m_Tail );
}
template <typename Q, typename Compare>
- guarded_ptr get_at( atomic_node_ptr const& refHead, Q const& val, Compare cmp ) const
+ guarded_ptr get_at( node_type const* pHead, Q const& val, Compare cmp ) const
{
position pos;
- if ( search( refHead, val, pos, cmp )) {
+ if ( search( pHead, val, pos, cmp )) {
m_Stat.onFindSuccess();
return guarded_ptr( std::move( pos.guard ));
}
m_Stat.onFindFailed();
return guarded_ptr();
}
+
+ node_type* head()
+ {
+ return &m_Head;
+ }
+
+ node_type const* head() const
+ {
+ return &m_Head;
+ }
//@endcond
protected:
-
//@cond
template <typename Q, typename Compare >
- bool search( atomic_node_ptr const& refHead, const Q& val, position& pos, Compare cmp ) const
+ bool search( node_type const* pHead, Q const& val, position& pos, Compare cmp ) const
+ {
+ pos.pHead = pHead;
+ node_type* pPrev = const_cast<node_type*>( pHead );
+
+ while ( true ) {
+ node_type * pCur = pPrev->next.load( memory_model::memory_order_relaxed );
+
+ if ( pCur == pCur->next.load( memory_model::memory_order_acquire )) {
+ // end-of-list
+ pos.pPrev = pPrev;
+ pos.pCur = pCur;
+ pos.pFound = nullptr;
+ return false;
+ }
+
+ value_type * pVal = pos.guard.protect( pCur->data,
+ []( marked_data_ptr p ) -> value_type*
+ {
+ return p.ptr();
+ }).ptr();
+
+ if ( pVal ) {
+ int const nCmp = cmp( *pVal, val );
+ if ( nCmp >= 0 ) {
+ pos.pPrev = pPrev;
+ pos.pCur = pCur;
+ pos.pFound = pVal;
+ return nCmp == 0;
+ }
+ }
+
+ pPrev = pCur;
+ }
+ }
+
+ template <typename Q, typename Compare >
+ bool inserting_search( node_type const* pHead, Q const& val, insert_position& pos, Compare cmp ) const
{
- atomic_node_ptr* pHead = const_cast<atomic_node_ptr*>( &refHead );
- node_type * pPrev = nullptr;
+ pos.pHead = pHead;
+ node_type* pPrev = const_cast<node_type*>(pHead);
+ value_type* pPrevVal = pPrev->data.load( memory_model::memory_order_relaxed ).ptr();
while ( true ) {
- node_type * pCur = pHead->load( memory_model::memory_order_relaxed );
+ node_type * pCur = pPrev->next.load( memory_model::memory_order_relaxed );
- if ( pCur == nullptr ) {
+ if ( pCur == pCur->next.load( memory_model::memory_order_acquire )) {
// end-of-list
- pos.pHead = pHead;
pos.pPrev = pPrev;
- pos.pCur = nullptr;
+ pos.pCur = pCur;
pos.pFound = nullptr;
+ pos.pPrevVal = pPrevVal;
return false;
}
- value_type * pVal = pos.guard.protect( pCur->data );
+ value_type * pVal = pos.guard.protect( pCur->data,
+ []( marked_data_ptr p ) -> value_type*
+ {
+ return p.ptr();
+ } ).ptr();
if ( pVal ) {
- int nCmp = cmp( *pVal, val );
+ int const nCmp = cmp( *pVal, val );
if ( nCmp >= 0 ) {
- pos.pHead = pHead;
pos.pPrev = pPrev;
pos.pCur = pCur;
pos.pFound = pVal;
+ pos.pPrevVal = pPrevVal;
return nCmp == 0;
}
}
pPrev = pCur;
- pHead = &( pCur->next );
+ pPrevVal = pVal;
+ pos.prevGuard.copy( pos.guard );
}
}
+
+ // split-list support
+ template <typename Predicate>
+ void destroy( Predicate pred )
+ {
+ node_type * pNode = m_Head.next.load( memory_model::memory_order_relaxed );
+ while ( pNode != pNode->next.load( memory_model::memory_order_relaxed )) {
+ value_type * pVal = pNode->data.load( memory_model::memory_order_relaxed ).ptr();
+ node_type * pNext = pNode->next.load( memory_model::memory_order_relaxed );
+ bool const is_regular_node = !pVal || pred( pVal );
+ if ( is_regular_node ) {
+ if ( pVal )
+ retire_data( pVal );
+ delete_node( pNode );
+ }
+ pNode = pNext;
+ }
+
+ m_Head.next.store( &m_Tail, memory_model::memory_order_relaxed );
+ }
//@endcond
private:
//@cond
+ void init_list()
+ {
+ m_Head.next.store( &m_Tail, memory_model::memory_order_relaxed );
+ // end-of-list mark: node.next == node
+ m_Tail.next.store( &m_Tail, memory_model::memory_order_release );
+ }
+
node_type * alloc_node( value_type * pVal )
{
m_Stat.onNodeCreated();
void destroy()
{
- node_type * pNode = m_pHead.load( memory_model::memory_order_relaxed );
- while ( pNode ) {
- value_type * pVal = pNode->data.load( memory_model::memory_order_relaxed );
+ node_type * pNode = m_Head.next.load( memory_model::memory_order_relaxed );
+ while ( pNode != pNode->next.load( memory_model::memory_order_relaxed )) {
+ value_type * pVal = pNode->data.load( memory_model::memory_order_relaxed ).ptr();
if ( pVal )
retire_data( pVal );
node_type * pNext = pNode->next.load( memory_model::memory_order_relaxed );
}
}
- bool link_node( value_type * pVal, position& pos )
+ bool link_data( value_type* pVal, insert_position& pos, node_type* pHead )
{
- if ( pos.pPrev ) {
- if ( pos.pPrev->data.load( memory_model::memory_order_relaxed ) == nullptr ) {
- // reuse pPrev
- value_type * p = nullptr;
- return pos.pPrev->data.compare_exchange_strong( p, pVal, memory_model::memory_order_release, atomics::memory_order_relaxed );
+ assert( pos.pPrev != nullptr );
+ assert( pos.pCur != nullptr );
+
+ // We need pos.pCur data should be unchanged, otherwise ordering violation can be possible
+ // if current thread will be preempted and another thread will delete pos.pCur data
+ // and then set it to another.
+ // To prevent this we mark pos.pCur data as undeletable by setting LSB
+ marked_data_ptr valCur( pos.pFound );
+ if ( !pos.pCur->data.compare_exchange_strong( valCur, valCur | 1, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
+ // oops, pos.pCur data has been changed or another thread is setting pos.pPrev data
+ m_Stat.onNodeMarkFailed();
+ return false;
+ }
+
+ marked_data_ptr valPrev( pos.pPrevVal );
+ if ( !pos.pPrev->data.compare_exchange_strong( valPrev, valPrev | 1, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
+ pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
+
+ m_Stat.onNodeMarkFailed();
+ return false;
+ }
+
+ // checks if link pPrev -> pCur is broken
+ if ( pos.pPrev->next.load( memory_model::memory_order_acquire ) != pos.pCur ) {
+ // sequence pPrev - pCur is broken
+ pos.pPrev->data.store( valPrev, memory_model::memory_order_relaxed );
+ pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
+
+ m_Stat.onNodeSeqBreak();
+ return false;
+ }
+
+ if ( pos.pPrevVal == nullptr ) {
+ // Check ABA-problem for prev
+ // There is a possibility that the current thread was preempted
+ // on entry of this function. Other threads can link data to prev
+ // and then remove it. As a result, the order of items may be changed
+ if ( find_prev( pHead, *pVal ) != pos.pPrev ) {
+ pos.pPrev->data.store( valPrev, memory_model::memory_order_relaxed );
+ pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
+
+ m_Stat.onNullPrevABA();
+ return false;
}
- else {
- // insert new node between pos.pPrev and pos.pCur
- node_type * pNode = alloc_node( pVal );
- pNode->next.store( pos.pCur, memory_model::memory_order_relaxed );
+ }
- if ( cds_likely( pos.pPrev->next.compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed )))
- return true;
+ if ( pos.pPrev != pos.pHead && pos.pPrevVal == nullptr ) {
+ // reuse pPrev
- delete_node( pNode );
+ // Set pos.pPrev data if it is null
+ valPrev |= 1;
+ bool result = pos.pPrev->data.compare_exchange_strong( valPrev, marked_data_ptr( pVal ),
+ memory_model::memory_order_release, atomics::memory_order_relaxed );
+
+ // Clears data marks
+ pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
+
+ if ( result ) {
+ m_Stat.onReuseNode();
+ return result;
}
}
else {
+ // insert new node between pos.pPrev and pos.pCur
node_type * pNode = alloc_node( pVal );
pNode->next.store( pos.pCur, memory_model::memory_order_relaxed );
- if ( cds_likely( pos.pHead->compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed ) ) )
- return true;
+
+ bool result = pos.pPrev->next.compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed );
+
+ // Clears data marks
+ pos.pPrev->data.store( valPrev, memory_model::memory_order_relaxed );
+ pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
+
+ if ( result ) {
+ m_Stat.onNewNodeCreated();
+ return result;
+ }
delete_node( pNode );
}
+
return false;
}
- static bool unlink_node( position& pos )
+ // split-list support
+ bool link_aux_node( node_type * pNode, insert_position& pos, node_type* pHead )
+ {
+ assert( pos.pPrev != nullptr );
+ assert( pos.pCur != nullptr );
+
+ // We need pos.pCur data should be unchanged, otherwise ordering violation can be possible
+ // if current thread will be preempted and another thread will delete pos.pCur data
+ // and then set it to another.
+ // To prevent this we mark pos.pCur data as undeletable by setting LSB
+ marked_data_ptr valCur( pos.pFound );
+ if ( !pos.pCur->data.compare_exchange_strong( valCur, valCur | 1, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
+ // oops, pos.pCur data has been changed or another thread is setting pos.pPrev data
+ m_Stat.onNodeMarkFailed();
+ return false;
+ }
+
+ marked_data_ptr valPrev( pos.pPrevVal );
+ if ( !pos.pPrev->data.compare_exchange_strong( valPrev, valPrev | 1, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
+ pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
+ m_Stat.onNodeMarkFailed();
+ return false;
+ }
+
+ // checks if link pPrev -> pCur is broken
+ if ( pos.pPrev->next.load( memory_model::memory_order_acquire ) != pos.pCur ) {
+ // sequence pPrev - pCur is broken
+ pos.pPrev->data.store( valPrev, memory_model::memory_order_relaxed );
+ pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
+ m_Stat.onNodeSeqBreak();
+ return false;
+ }
+
+ if ( pos.pPrevVal == nullptr ) {
+ // Check ABA-problem for prev
+ // There is a possibility that the current thread was preempted
+ // on entry of this function. Other threads can insert (link) an item to prev
+ // and then remove it. As a result, the order of items may be changed
+ if ( find_prev( pHead, *pNode->data.load( memory_model::memory_order_relaxed ).ptr()) != pos.pPrev ) {
+ pos.pPrev->data.store( valPrev, memory_model::memory_order_relaxed );
+ pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
+
+ m_Stat.onNullPrevABA();
+ return false;
+ }
+ }
+
+ // insert new node between pos.pPrev and pos.pCur
+ pNode->next.store( pos.pCur, memory_model::memory_order_relaxed );
+
+ bool result = pos.pPrev->next.compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed );
+
+ // Clears data marks
+ pos.pPrev->data.store( valPrev, memory_model::memory_order_relaxed );
+ pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
+
+ return result;
+ }
+
+ static bool unlink_data( position& pos )
{
assert( pos.pCur != nullptr );
assert( pos.pFound != nullptr );
- if ( pos.pCur->data.compare_exchange_strong( pos.pFound, nullptr, memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
+ marked_data_ptr val( pos.pFound );
+ if ( pos.pCur->data.compare_exchange_strong( val, marked_data_ptr(), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
retire_data( pos.pFound );
return true;
}
return false;
}
+ template <typename Q>
+ node_type* find_prev( node_type const* pHead, Q const& val ) const
+ {
+ node_type* pPrev = const_cast<node_type*>(pHead);
+ typename gc::Guard guard;
+ key_comparator cmp;
+
+ while ( true ) {
+ node_type * pCur = pPrev->next.load( memory_model::memory_order_relaxed );
+
+ if ( pCur == pCur->next.load( memory_model::memory_order_acquire )) {
+ // end-of-list
+ return pPrev;
+ }
+
+ value_type * pVal = guard.protect( pCur->data,
+ []( marked_data_ptr p ) -> value_type*
+ {
+ return p.ptr();
+ } ).ptr();
+
+ if ( pVal && cmp( *pVal, val ) >= 0 )
+ return pPrev;
+
+ pPrev = pCur;
+ }
+ }
//@endcond
};
}} // namespace cds::intrusive
projects / libcds.git / blobdiff