#define __CDS_INTRUSIVE_SKIP_LIST_NOGC_H
#include <type_traits>
+#include <memory>
+#include <functional> // ref
#include <cds/gc/nogc.h>
-#include <cds/intrusive/skip_list_base.h>
-#include <cds/details/std/memory.h>
+#include <cds/intrusive/details/skip_list_base.h>
#include <cds/opt/compare.h>
-#include <cds/ref.h>
#include <cds/details/binary_functor_wrapper.h>
namespace cds { namespace intrusive {
typedef cds::gc::nogc gc ; ///< Garbage collector
typedef Tag tag ; ///< tag
- typedef CDS_ATOMIC::atomic<node * > atomic_ptr;
+ typedef atomics::atomic<node * > atomic_ptr;
typedef atomic_ptr tower_item_type;
protected:
atomic_ptr m_pNext ; ///< Next item in bottom-list (list at level 0)
unsigned int m_nHeight ; ///< Node height (size of m_arrNext array). For node at level 0 the height is 1.
- atomic_ptr * m_arrNext ; ///< Array of next items for levels 1 .. m_nHeight - 1. For node at level 0 \p m_arrNext is \p NULL
+ atomic_ptr * m_arrNext ; ///< Array of next items for levels 1 .. m_nHeight - 1. For node at level 0 \p m_arrNext is \p nullptr
public:
/// Constructs a node of height 1 (a bottom-list node)
void clear()
{
assert( m_arrNext == nullptr );
- m_pNext.store( nullptr, CDS_ATOMIC::memory_order_release );
+ m_pNext.store( nullptr, atomics::memory_order_release );
}
bool is_cleared() const
{
- return m_pNext.load( CDS_ATOMIC::memory_order_relaxed ) == nullptr
+ return m_pNext.load( atomics::memory_order_relaxed ) == nullptr
&& m_arrNext == nullptr
&& m_nHeight <= 1
;
public: // for internal use only!!!
iterator( node_type& refHead )
- : m_pNode( refHead[0].load( CDS_ATOMIC::memory_order_relaxed ) )
+ : m_pNode( refHead[0].load( atomics::memory_order_relaxed ) )
{}
static iterator from_node( node_type * pNode )
iterator& operator ++()
{
if ( m_pNode )
- m_pNode = m_pNode->next(0).load( CDS_ATOMIC::memory_order_relaxed );
+ m_pNode = m_pNode->next(0).load( atomics::memory_order_relaxed );
return *this;
}
bool operator !=(iterator const& i ) const;
};
\endcode
- Note, the iterator object returned by \ref end, \p cend member functions points to \p NULL and should not be dereferenced.
+ Note, the iterator object returned by \ref end, \p cend member functions points to \p nullptr and should not be dereferenced.
<b>How to use</b>
node_type * pCur;
};
-# ifndef CDS_CXX11_LAMBDA_SUPPORT
- struct empty_insert_functor {
- void operator()( value_type& )
- {}
- };
-
- struct empty_find_functor {
- template <typename Q>
- void operator()( value_type& item, Q& val )
- {}
- };
-
- template <typename Func>
- struct insert_at_ensure_functor {
- Func m_func;
- insert_at_ensure_functor( Func f ) : m_func(f) {}
-
- void operator()( value_type& item )
- {
- cds::unref( m_func)( true, item, item );
- }
- };
-
-# endif // ifndef CDS_CXX11_LAMBDA_SUPPORT
-
class head_node: public node_type
{
typename node_type::atomic_ptr m_Tower[c_nMaxHeight];
head_node( unsigned int nHeight )
{
for ( size_t i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
- m_Tower[i].store( nullptr, CDS_ATOMIC::memory_order_relaxed );
+ m_Tower[i].store( nullptr, atomics::memory_order_relaxed );
node_type::make_tower( nHeight, m_Tower );
}
void clear()
{
for (unsigned int i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
- m_Tower[i].store( nullptr, CDS_ATOMIC::memory_order_relaxed );
- node_type::m_pNext.store( nullptr, CDS_ATOMIC::memory_order_relaxed );
+ m_Tower[i].store( nullptr, atomics::memory_order_relaxed );
+ node_type::m_pNext.store( nullptr, atomics::memory_order_relaxed );
}
};
//@endcond
item_counter m_ItemCounter ; ///< item counter
random_level_generator m_RandomLevelGen ; ///< random level generator instance
- CDS_ATOMIC::atomic<unsigned int> m_nHeight ; ///< estimated high level
+ atomics::atomic<unsigned int> m_nHeight ; ///< estimated high level
mutable stat m_Stat ; ///< internal statistics
protected:
if ( !pos.pPrev[0]->next(0).compare_exchange_strong( p, pNode, memory_model::memory_order_release, memory_model::memory_order_relaxed ) ) {
return false;
}
- cds::unref( f )( val );
+ f( val );
}
for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
if ( find_position( val, pos, cmp, true, false )) {
assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
- cds::unref(f)( *node_traits::to_value_ptr( pos.pCur ), val );
+ f( *node_traits::to_value_ptr( pos.pCur ), val );
m_Stat.onFindFastSuccess();
return pos.pCur;
void increase_height( unsigned int nHeight )
{
unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
- while ( nCur < nHeight && !m_nHeight.compare_exchange_weak( nCur, nHeight, memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ) );
+ while ( nCur < nHeight && !m_nHeight.compare_exchange_weak( nCur, nHeight, memory_model::memory_order_acquire, atomics::memory_order_relaxed ) );
}
//@endcond
static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
// Barrier for head node
- CDS_ATOMIC::atomic_thread_fence( memory_model::memory_order_release );
+ atomics::atomic_thread_fence( memory_model::memory_order_release );
}
/// Clears and destructs the skip-list
bTowerOk = true;
}
-# ifndef CDS_CXX11_LAMBDA_SUPPORT
- if ( !insert_at_position( val, pNode, pos, empty_insert_functor() ))
-# else
- if ( !insert_at_position( val, pNode, pos, []( value_type& ) {} ))
-# endif
- {
+ if ( !insert_at_position( val, pNode, pos, []( value_type& ) {} )) {
m_Stat.onInsertRetry();
continue;
}
The functor can change non-key fields of the \p item; however, \p func must guarantee
that during changing no any other modifications could be made on this item by concurrent threads.
- You can pass \p func argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
+ You can pass \p func argument by value or by reference using \p std::ref.
Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
\p second is \p true if new item has been added or \p false if the item with \p key
bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
bool bTowerMade = false;
-# ifndef CDS_CXX11_LAMBDA_SUPPORT
- insert_at_ensure_functor<Func> wrapper( func );
-# endif
-
position pos;
while ( true )
{
if ( !bTowerMade )
scp.release();
- cds::unref(func)( false, *node_traits::to_value_ptr(pos.pCur), val );
+ func( false, *node_traits::to_value_ptr(pos.pCur), val );
m_Stat.onEnsureExist();
return std::make_pair( true, false );
}
bTowerOk = true;
}
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
- if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { cds::unref(func)( true, item, item ); }))
-# else
- if ( !insert_at_position( val, pNode, pos, cds::ref(wrapper) ))
-# endif
- {
+ if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { func( true, item, item ); })) {
m_Stat.onInsertRetry();
continue;
}
\endcode
where \p item is the item found, \p val is the <tt>find</tt> function argument.
- You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
+ You can pass \p f argument by value or by reference using \p std::ref.
The functor can change non-key fields of \p item. Note that the functor is only guarantee
that \p item cannot be disposed during functor is executing.
\endcode
where \p item is the item found, \p val is the <tt>find</tt> function argument.
- You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
+ You can pass \p f argument by value or by reference using \p std::ref.
The functor can change non-key fields of \p item. Note that the functor is only guarantee
that \p item cannot be disposed during functor is executing.
template <typename Q>
value_type * find( Q const& val ) const
{
- node_type * pNode =
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
- find_with_( val, key_comparator(), [](value_type& , Q const& ) {} );
-# else
- find_with_( val, key_comparator(), empty_find_functor() );
-# endif
+ node_type * pNode = find_with_( val, key_comparator(), [](value_type& , Q const& ) {} );
if ( pNode )
return node_traits::to_value_ptr( pNode );
return nullptr;
template <typename Q, typename Less>
value_type * find_with( Q const& val, Less pred ) const
{
- node_type * pNode =
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
- find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
-# else
- find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), empty_find_functor() );
-# endif
+ node_type * pNode = find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
if ( pNode )
return node_traits::to_value_ptr( pNode );
return nullptr;
/// Gets minimum key from the set
/**
- If the set is empty the function returns \p NULL
+ If the set is empty the function returns \p nullptr
*/
value_type * get_min() const
{
/// Gets maximum key from the set
/**
- The function returns \p NULL if the set is empty
+ The function returns \p nullptr if the set is empty
*/
value_type * get_max() const
{