Template arguments:
- \p RCU - one of \ref cds_urcu_gc "RCU type".
- \p T - type to be stored in the list.
- - \p Traits - type traits. See skip_list::type_traits for explanation.
+ - \p Traits - set traits, default is skip_list::traits for explanation.
It is possible to declare option-based list with cds::container::skip_list::make_traits metafunction istead of \p Traits template
argument.
// Traits for your skip-list.
// At least, you should define cds::opt::less or cds::opt::compare for Foo struct
- struct my_traits: public cds::continer::skip_list::type_traits
+ struct my_traits: public cds::continer::skip_list::traits
{
// ...
};
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.
*/
template <
typename RCU,
typename T,
#ifdef CDS_DOXYGEN_INVOKED
- typename Traits = skip_list::type_traits
+ typename Traits = skip_list::traits
#else
typename Traits
#endif
public:
typedef typename base_class::gc gc ; ///< Garbage collector used
typedef T value_type ; ///< Value type stored in the set
- typedef Traits options ; ///< Options specified
+ typedef Traits traits ; ///< Options specified
typedef typename base_class::back_off back_off ; ///< Back-off strategy used
- typedef typename options::allocator allocator_type ; ///< Allocator type used for allocate/deallocate the skip-list nodes
+ typedef typename traits::allocator allocator_type ; ///< Allocator type used for allocate/deallocate the skip-list nodes
typedef typename base_class::item_counter item_counter ; ///< Item counting policy used
typedef typename maker::key_comparator key_comparator ; ///< key compare functor
typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
- typedef typename options::random_level_generator random_level_generator ; ///< random level generator
- typedef typename options::stat stat ; ///< internal statistics type
- typedef typename options::rcu_check_deadlock rcu_check_deadlock ; ///< Deadlock checking policy
+ typedef typename traits::random_level_generator random_level_generator ; ///< random level generator
+ typedef typename traits::stat stat ; ///< internal statistics type
+ typedef typename traits::rcu_check_deadlock rcu_check_deadlock ; ///< Deadlock checking policy
protected:
//@cond
public:
typedef typename base_class::rcu_lock rcu_lock; ///< RCU scoped lock
/// Group of \p extract_xxx functions do not require external locking
- static CDS_CONSTEXPR_CONST bool c_bExtractLockExternal = base_class::c_bExtractLockExternal;
+ static CDS_CONSTEXPR const bool c_bExtractLockExternal = base_class::c_bExtractLockExternal;
/// pointer to extracted node
- typedef cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_type_traits::disposer > exempt_ptr;
+ using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_traits::disposer >;
protected:
//@cond
value_type * to_value_ptr( node_type * pNode ) const CDS_NOEXCEPT
{
- return pNode ? &pNode->m_Value : null_ptr<value_type *>();
+ return pNode ? &pNode->m_Value : nullptr;
}
//@endcond
- protected:
- //@cond
-# ifndef CDS_CXX11_LAMBDA_SUPPORT
- template <typename Func>
- struct insert_functor
- {
- Func m_func;
-
- insert_functor ( Func f )
- : m_func(f)
- {}
-
- void operator()( node_type& node )
- {
- cds::unref(m_func)( node.m_Value );
- }
- };
-
- template <typename Q, typename Func>
- struct ensure_functor
- {
- Func m_func;
- Q const& m_arg;
-
- ensure_functor( Q const& arg, Func f )
- : m_func(f)
- , m_arg( arg )
- {}
-
- void operator ()( bool bNew, node_type& node, node_type& )
- {
- cds::unref(m_func)( bNew, node.m_Value, m_arg );
- }
- };
-
- template <typename Func>
- struct find_functor
- {
- Func m_func;
-
- find_functor( Func f )
- : m_func(f)
- {}
-
- template <typename Q>
- void operator ()( node_type& node, Q& val )
- {
- cds::unref(m_func)( node.m_Value, val );
- }
- };
-
- template <typename Func>
- struct erase_functor
- {
- Func m_func;
-
- erase_functor( Func f )
- : m_func(f)
- {}
-
- void operator()( node_type const& node )
- {
- cds::unref(m_func)( node.m_Value );
- }
- };
-
- template <typename Func>
- struct extract_copy_wrapper
- {
- Func m_func;
- extract_copy_wrapper( Func f )
- : m_func(f)
- {}
-
- template <typename Q>
- void operator()( Q& dest, node_type& src )
- {
- cds::unref(m_func)(dest, src.m_Value);
- }
- };
-
- struct extract_assign_wrapper
- {
- template <typename Q>
- void operator()( Q& dest, node_type& src ) const
- {
- dest = src.m_Value;
- }
- };
-# endif // ifndef CDS_CXX11_LAMBDA_SUPPORT
-
- //@endcond
-
public:
/// Default ctor
SkipListSet()
{
return const_iterator( base_class::begin() );
}
- const_iterator cbegin()
+ const_iterator cbegin() const
{
return const_iterator( base_class::cbegin() );
}
{
return const_iterator( base_class::end() );
}
- const_iterator cend()
+ const_iterator cend() const
{
return const_iterator( base_class::cend() );
}
\endcode
where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
\p val no any other changes could be made on this set's item by concurrent threads.
- The user-defined functor is called only if the inserting is success. It may be passed by reference
- using <tt>boost::ref</tt>
+ The user-defined functor is called only if the inserting is success.
RCU \p synchronize method can be called. RCU should not be locked.
*/
bool insert( Q const& val, Func f )
{
scoped_node_ptr sp( node_allocator().New( random_level(), val ));
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
- if ( base_class::insert( *sp.get(), [&f]( node_type& val ) { cds::unref(f)( val.m_Value ); } ))
-# else
- insert_functor<Func> wrapper(f);
- if ( base_class::insert( *sp, cds::ref(wrapper) ))
-# endif
- {
+ if ( base_class::insert( *sp.get(), [&f]( node_type& val ) { f( val.m_Value ); } )) {
sp.release();
return true;
}
The functor may 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 may pass \p func argument by reference using <tt>boost::ref</tt>.
-
RCU \p synchronize method can be called. RCU should not be locked.
Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
std::pair<bool, bool> ensure( const Q& val, Func func )
{
scoped_node_ptr sp( node_allocator().New( random_level(), val ));
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
std::pair<bool, bool> bRes = base_class::ensure( *sp,
- [&func, &val](bool bNew, node_type& node, node_type&){ cds::unref(func)( bNew, node.m_Value, val ); });
-# else
- ensure_functor<Q, Func> wrapper( val, func );
- std::pair<bool, bool> bRes = base_class::ensure( *sp, cds::ref(wrapper));
-# endif
+ [&func, &val](bool bNew, node_type& node, node_type&){ func( bNew, node.m_Value, val ); });
if ( bRes.first && bRes.second )
sp.release();
return bRes;
}
-# ifdef CDS_EMPLACE_SUPPORT
/// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
/**
Returns \p true if inserting successful, \p false otherwise.
RCU \p synchronize method can be called. RCU should not be locked.
-
- @note This function is available only for compiler that supports
- variadic template and move semantics
*/
template <typename... Args>
bool emplace( Args&&... args )
}
return false;
}
-# endif
/// Delete \p key from the set
/** \anchor cds_nonintrusive_SkipListSet_rcu_erase_val
template <typename Q, typename Less>
bool erase_with( Q const& key, Less pred )
{
+ CDS_UNUSED( pred );
return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >());
}
void operator()(value_type const& val);
};
\endcode
- The functor may be passed by reference using <tt>boost:ref</tt>
Since the key of MichaelHashSet's \p value_type is not explicitly specified,
template parameter \p Q defines the key type searching in the list.
template <typename Q, typename Func>
bool erase( Q const& key, Func f )
{
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
- return base_class::erase( key, [&f]( node_type const& node) { cds::unref(f)( node.m_Value ); } );
-# else
- erase_functor<Func> wrapper(f);
- return base_class::erase( key, cds::ref(wrapper));
-# endif
+ return base_class::erase( key, [&f]( node_type const& node) { f( node.m_Value ); } );
}
/// Deletes the item from the set using \p pred predicate for searching
template <typename Q, typename Less, typename Func>
bool erase_with( Q const& key, Less pred, Func f )
{
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
+ CDS_UNUSED( pred );
return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >(),
- [&f]( node_type const& node) { cds::unref(f)( node.m_Value ); } );
-# else
- erase_functor<Func> wrapper(f);
- return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >(), cds::ref(wrapper));
-# endif
+ [&f]( node_type const& node) { f( node.m_Value ); } );
}
/// Extracts the item from the set with specified \p key
/** \anchor cds_nonintrusive_SkipListSet_rcu_extract
The function searches an item with key equal to \p key in the set,
- unlinks it from the set, and returns it in \p result parameter.
- If the item with key equal to \p key is not found the function returns \p false.
+ unlinks it from the set, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
+ If the item is not found the function returns an empty \p exempt_ptr
Note the compare functor from \p Traits class' template argument
should accept a parameter of type \p Q that can be not the same as \p value_type.
RCU \p synchronize method can be called. RCU should NOT be locked.
+
The function does not free the item found.
- The item will be implicitly freed when \p result object is destroyed or when
- <tt>result.release()</tt> is called, see \p cds::urcu::exempt_ptr for explanation.
- @note Before reusing \p result object you should call its \p release() method.
+ The item will be implicitly freed when the returned object is destroyed or when
+ its \p release() member function is called.
*/
template <typename Q>
- bool extract( exempt_ptr& result, Q const& key )
+ exempt_ptr extract( Q const& key )
{
- return base_class::do_extract( result, key );
+ return exempt_ptr( base_class::do_extract( key ));
}
/// Extracts the item from the set with comparing functor \p pred
\p pred must imply the same element order as the comparator used for building the set.
*/
template <typename Q, typename Less>
- bool extract_with( exempt_ptr& result, Q const& key, Less pred )
+ exempt_ptr extract_with( Q const& key, Less pred )
{
- return base_class::do_extract_with( result, key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >());
+ CDS_UNUSED( pred );
+ return exempt_ptr( base_class::do_extract_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >()));
}
/// Extracts an item with minimal key from the set
/**
- The function searches an item with minimal key, unlinks it, and returns the item found in \p result parameter.
- If the skip-list is empty the function returns \p false.
+ The function searches an item with minimal key, unlinks it,
+ and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item.
+ If the skip-list is empty the function returns an empty \p exempt_ptr.
RCU \p synchronize method can be called. RCU should NOT be locked.
+
The function does not free the item found.
- The item will be implicitly freed when \p result object is destroyed or when
- <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
- @note Before reusing \p result object you should call its \p release() method.
+ The item will be implicitly freed when the returned object is destroyed or when
+ its \p release() member function is called.
*/
- bool extract_min( exempt_ptr& result )
+ exempt_ptr extract_min()
{
- return base_class::do_extract_min(result);
+ return exempt_ptr( base_class::do_extract_min());
}
/// Extracts an item with maximal key from the set
/**
- The function searches an item with maximal key, unlinks it from the set, and returns the item found
- in \p result parameter. If the skip-list is empty the function returns \p false.
+ The function searches an item with maximal key, unlinks it from the set,
+ and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item.
+ If the skip-list is empty the function returns an empty \p exempt_ptr.
RCU \p synchronize method can be called. RCU should NOT be locked.
+
The function does not free the item found.
- The item will be implicitly freed when \p result object is destroyed or when
- <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
- @note Before reusing \p result object you should call its \p release() method.
+ The item will be implicitly freed when the returned object is destroyed or when
+ its \p release() member function is called.
*/
- bool extract_max(exempt_ptr& result)
+ exempt_ptr extract_max()
{
- return base_class::do_extract_max(result);
+ return exempt_ptr( base_class::do_extract_max());
}
/// Find the key \p val
\endcode
where \p item is the item found, \p val is the <tt>find</tt> function argument.
- You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
-
The functor may change non-key fields of \p item. Note that the functor is only guarantee
that \p item cannot be disposed during functor is executing.
The functor does not serialize simultaneous access to the set's \p item. If such access is
template <typename Q, typename Func>
bool find( Q& val, Func f )
{
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
- return base_class::find( val, [&f]( node_type& node, Q& v ) { cds::unref(f)( node.m_Value, v ); });
-# else
- find_functor<Func> wrapper(f);
- return base_class::find( val, cds::ref(wrapper));
-# endif
+ return base_class::find( val, [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); });
+ }
+ //@cond
+ template <typename Q, typename Func>
+ bool find( Q const& val, Func f )
+ {
+ return base_class::find( val, [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); } );
}
+ //@endcond
/// Finds the key \p val using \p pred predicate for searching
/**
template <typename Q, typename Less, typename Func>
bool find_with( Q& val, Less pred, Func f )
{
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
+ CDS_UNUSED( pred );
return base_class::find_with( val, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >(),
- [&f]( node_type& node, Q& v ) { cds::unref(f)( node.m_Value, v ); } );
-# else
- find_functor<Func> wrapper(f);
- return base_class::find_with( val, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >(),
- cds::ref(wrapper));
-# endif
+ [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); } );
}
-
- /// Find the key \p val
- /** @anchor cds_nonintrusive_SkipListSet_rcu_find_cfunc
-
- The function searches the item with key equal to \p val and calls the functor \p f for item found.
- The interface of \p Func functor is:
- \code
- struct functor {
- void operator()( value_type& item, Q const& val );
- };
- \endcode
- where \p item is the item found, \p val is the <tt>find</tt> function argument.
-
- You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
-
- The functor may change non-key fields of \p item. Note that the functor is only guarantee
- that \p item cannot be disposed during functor is executing.
- The functor does not serialize simultaneous access to the set's \p item. If such access is
- possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
-
- Note the hash functor specified for class \p Traits template parameter
- should accept a parameter of type \p Q that may be not the same as \p value_type.
-
- The function applies RCU lock internally.
-
- The function returns \p true if \p val is found, \p false otherwise.
- */
- template <typename Q, typename Func>
- bool find( Q const& val, Func f )
- {
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
- return base_class::find( val, [&f]( node_type& node, Q const& v ) { cds::unref(f)( node.m_Value, v ); });
-# else
- find_functor<Func> wrapper(f);
- return base_class::find( val, cds::ref(wrapper));
-# endif
- }
-
- /// Finds the key \p val using \p pred predicate for searching
- /**
- The function is an analog of \ref cds_nonintrusive_SkipListSet_rcu_find_cfunc "find(Q const&, Func)"
- but \p pred is used for key comparing.
- \p Less functor has the semantics like \p std::less.
- \p Less must imply the same element order as the comparator used for building the set.
- */
+ //@cond
template <typename Q, typename Less, typename Func>
bool find_with( Q const& val, Less pred, Func f )
{
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
+ CDS_UNUSED( pred );
return base_class::find_with( val, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >(),
- [&f]( node_type& node, Q const& v ) { cds::unref(f)( node.m_Value, v ); } );
-# else
- find_functor<Func> wrapper(f);
- return base_class::find_with( val, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >(),
- cds::ref(wrapper));
-# endif
+ [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); } );
}
+ //@endcond
/// Find the key \p val
/** @anchor cds_nonintrusive_SkipListSet_rcu_find_val
template <typename Q, typename Less>
bool find_with( Q const& val, Less pred )
{
+ CDS_UNUSED( pred );
return base_class::find_with( val, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >());
}
/// Finds \p key and return the item found
/** \anchor cds_nonintrusive_SkipListSet_rcu_get
The function searches the item with key equal to \p key and returns the pointer to item found.
- If \p key is not found it returns \p NULL.
+ If \p key is not found it returns \p nullptr.
Note the compare functor in \p Traits class' template argument
should accept a parameter of type \p Q that can be not the same as \p value_type.
template <typename Q, typename Less>
value_type * get_with( Q const& val, Less pred )
{
+ CDS_UNUSED( pred );
return to_value_ptr( base_class::get_with( val, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >() ));
}
projects / libcds.git / blobdiff