/*
This file is a part of libcds - Concurrent Data Structures library
- (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+ (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
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:
SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#ifndef CDSLIB_INTRUSIVE_LAZY_LIST_RCU_H
#define CDSLIB_INTRUSIVE_LAZY_LIST_RCU_H
-#include <mutex> // unique_lock
+#include <mutex> // unique_lock
#include <cds/intrusive/details/lazy_list_base.h>
#include <cds/urcu/details/check_deadlock.h>
#include <cds/details/binary_functor_wrapper.h>
- \p RCU - one of \ref cds_urcu_gc "RCU type"
- \p T - type to be stored in the list
- \p Traits - type traits. See \p lazy_list::traits for explanation.
-
- It is possible to declare option-based list with \p %cds::intrusive::lazy_list::make_traits metafunction istead of \p Traits template
- argument. Template argument list \p Options of cds::intrusive::lazy_list::make_traits metafunction are:
- - opt::hook - hook used. Possible values are: lazy_list::base_hook, lazy_list::member_hook, lazy_list::traits_hook.
- If the option is not specified, <tt>lazy_list::base_hook<></tt> is used.
- - opt::compare - key comparison functor. No default functor is provided.
- If the option is not specified, the opt::less is used.
- - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
- - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used.
- - opt::disposer - the functor used for dispose removed items. Default is opt::v::empty_disposer
- - opt::rcu_check_deadlock - a deadlock checking policy. Default is opt::v::rcu_throw_deadlock
- - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter
- - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
- or opt::v::sequential_consistent (sequentially consisnent memory model).
+ It is possible to declare option-based list with \p %cds::intrusive::lazy_list::make_traits metafunction instead of \p Traits template
+ argument.
\par Usage
Before including <tt><cds/intrusive/lazy_list_rcu.h></tt> you should include appropriate RCU header file,
typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
typedef typename lazy_list::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
- typedef typename traits::back_off back_off; ///< back-off strategy (not used)
- typedef typename traits::item_counter item_counter; ///< Item counting policy used
- typedef typename traits::memory_model memory_model; ///< C++ memory ordering (see \p lazy_list::traits::memory_model)
- typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
+ typedef typename traits::back_off back_off; ///< back-off strategy (not used)
+ typedef typename traits::item_counter item_counter; ///< Item counting policy used
+ typedef typename traits::memory_model memory_model; ///< C++ memory ordering (see \p lazy_list::traits::memory_model)
+ typedef typename traits::stat stat; ///< Internal statistics
+ typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock
static CDS_CONSTEXPR const bool c_bExtractLockExternal = true; ///< Group of \p extract_xxx functions require external locking
+ static_assert((std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type");
+
//@cond
// Rebind traits (split-list support)
template <typename... Options>
, typename cds::opt::make_options< traits, Options...>::type
> type;
};
- //@endcond
- protected:
- typedef typename node_type::marked_ptr marked_node_ptr; ///< Node marked pointer
- typedef node_type * auxiliary_head; ///< Auxiliary head type (for split-list support)
+ // Stat selector
+ template <typename Stat>
+ using select_stat_wrapper = lazy_list::select_stat_wrapper< Stat >;
+ //@endcond
protected:
node_type m_Head; ///< List head (dummy node)
node_type m_Tail; ///< List tail (dummy node)
item_counter m_ItemCounter; ///< Item counter
+ mutable stat m_Stat; ///< Internal statistics
//@cond
+ typedef typename node_type::marked_ptr marked_node_ptr; ///< Node marked pointer
+ typedef node_type * auxiliary_head; ///< Auxiliary head type (for split-list support)
/// Position pointer for item search
struct position {
typedef std::unique_lock< position > scoped_position_lock;
typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock> deadlock_policy;
- //@endcond
-
- protected:
- //@cond
- static void clear_links( node_type * pNode )
- {
- pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
- }
struct clear_and_dispose {
void operator()( value_type * p )
disposer()( 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 link_node( node_type * pNode, node_type * pPred, node_type * pCur )
- {
- assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
-
- pNode->m_pNext.store( marked_node_ptr(pCur), memory_model::memory_order_relaxed );
- pPred->m_pNext.store( marked_node_ptr(pNode), memory_model::memory_order_release );
- }
-
- void unlink_node( node_type * pPred, node_type * pCur, node_type * pHead )
- {
- assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
- assert( pCur != &m_Tail );
-
- node_type * pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr();
- pCur->m_pNext.store( marked_node_ptr( pHead, 1 ), memory_model::memory_order_relaxed ); // logical deletion + back-link for search
- pPred->m_pNext.store( marked_node_ptr( pNext ), memory_model::memory_order_release); // physically deleting
- }
-
//@endcond
public:
//@endcond
public:
+ ///@name Forward iterators (thread-safe only under RCU lock)
+ //@{
/// Forward iterator
+ /**
+ You may safely use iterators in multi-threaded environment only under RCU lock.
+ Otherwise, a crash is possible if another thread deletes the item the iterator points to.
+ */
typedef iterator_type<false> iterator;
+
/// Const forward iterator
typedef iterator_type<true> const_iterator;
}
/// Returns a forward const iterator addressing the first element in a list
- //@{
const_iterator begin() const
{
return get_const_begin();
}
+
+ /// Returns a forward const iterator addressing the first element in a list
const_iterator cbegin() const
{
return get_const_begin();
}
- //@}
/// Returns an const iterator that addresses the location succeeding the last element in a list
- //@{
const_iterator end() const
{
return get_const_end();
}
+
+ /// Returns an const iterator that addresses the location succeeding the last element in a list
const_iterator cend() const
{
return get_const_end();
}
- //@}
-
- private:
- //@cond
- const_iterator get_const_begin() const
- {
- const_iterator it( const_cast<node_type *>( &m_Head ));
- ++it ; // skip dummy head
- return it;
- }
- const_iterator get_const_end() const
- {
- return const_iterator( const_cast<node_type *>( &m_Tail ));
- }
- //@endcond
+ //@}
public:
/// Default constructor initializes empty list
LazyList()
{
- static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
m_Head.m_pNext.store( marked_node_ptr( &m_Tail ), memory_model::memory_order_relaxed );
}
+ //@cond
+ template <typename Stat, typename = std::enable_if<std::is_same<stat, lazy_list::wrapped_stat<Stat>>::value >>
+ explicit LazyList( Stat& st )
+ : m_Stat( st )
+ {
+ m_Head.m_pNext.store( marked_node_ptr( &m_Tail ), memory_model::memory_order_relaxed );
+ }
+ //@endcond
+
/// Destroys the list object
~LazyList()
{
The functor may change non-key fields of the \p item.
While the functor \p f is calling the item \p item is locked.
- Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
+ Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
\p second is \p true if new item has been added or \p false if the item with \p key
already is in the list.
{
return update( val, func, true );
}
- //@cond
+ //@endcond
/// Unlinks the item \p val from the list
/**
}
/// Deletes the item from the list
- /** \anchor cds_intrusive_LazyList_rcu_find_erase
+ /**
The function searches an item with key equal to \p key in the list,
unlinks it from the list, and returns \p true.
If the item with the key equal to \p key is not found the function return \p false.
/// Deletes the item from the list using \p pred predicate for searching
/**
- The function is an analog of \ref cds_intrusive_LazyList_rcu_find_erase "erase(Q const&)"
+ The function is an analog of \p erase(Q const&)
but \p pred is used for key comparing.
\p Less functor has the interface like \p std::less.
\p pred must imply the same element order as the comparator used for building the list.
}
/// Deletes the item from the list
- /** \anchor cds_intrusive_LazyList_rcu_find_erase_func
+ /**
The function searches an item with key equal to \p key in the list,
call \p func functor with item found, unlinks it from the list, and returns \p true.
The \p Func interface is
/// Deletes the item from the list using \p pred predicate for searching
/**
- The function is an analog of \ref cds_intrusive_LazyList_rcu_find_erase_func "erase(Q const&, Func)"
+ The function is an analog of \p erase(Q const&, Func)
but \p pred is used for key comparing.
\p Less functor has the interface like \p std::less.
\p pred must imply the same element order as the comparator used for building the list.
/// Extracts an item from the list
/**
- \anchor cds_intrusive_LazyList_rcu_extract
The function searches an item with key equal to \p key in the list,
unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to an item found.
If the item is not found the function returns empty \p exempt_ptr.
@note The function does NOT call RCU read-side lock or synchronization,
and does NOT dispose the item found. It just unlinks the item from the list
and returns a pointer to it.
- You should manually lock RCU before calling this function, and you should manually synchronize RCU
- outside the RCU lock region before reusing returned pointer.
+ You should manually lock RCU before calling this function, and you should manually release
+ the returned exempt pointer outside the RCU lock region before reusing returned pointer.
\code
#include <cds/urcu/general_buffered.h>
}
/// Finds the key \p key
- /** \anchor cds_intrusive_LazyList_rcu_find_func
+ /**
The function searches the item with key equal to \p key
and calls the functor \p f for item found.
The interface of \p Func functor is:
/// Finds the key \p key using \p pred predicate for searching
/**
- The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
+ The function is an analog of \p find( Q&, Func ) but \p pred is used for key comparing.
\p Less functor has the interface like \p std::less.
\p pred must imply the same element order as the comparator used for building the list.
*/
/// Checks whether the map contains \p key using \p pred predicate for searching
/**
- The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
+ The function is an analog of \p contains( Q const& ) but \p pred is used for key comparing.
\p Less functor has the interface like \p std::less.
\p Less must imply the same element order as the comparator used for building the list.
*/
this function always returns 0.
<b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
- is empty. To check list emptyness use \ref empty() method.
+ is empty. To check list emptiness use \ref empty() method.
*/
size_t size() const
{
return m_ItemCounter.value();
}
+ /// Returns const reference to internal statistics
+ stat const& statistics() const
+ {
+ return m_Stat;
+ }
+
protected:
//@cond
+ static void clear_links( node_type * pNode )
+ {
+ pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
+ }
+
+ 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 link_node( node_type * pNode, node_type * pPred, node_type * pCur )
+ {
+ assert( pPred->m_pNext.load( memory_model::memory_order_relaxed ).ptr() == pCur );
+ link_checker::is_empty( pNode );
+
+ pNode->m_pNext.store( marked_node_ptr( pCur ), memory_model::memory_order_relaxed );
+ pPred->m_pNext.store( marked_node_ptr( pNode ), memory_model::memory_order_release );
+ }
+
+ void unlink_node( node_type * pPred, node_type * pCur, node_type * pHead )
+ {
+ assert( pPred->m_pNext.load( memory_model::memory_order_relaxed ).ptr() == pCur );
+ assert( pCur != &m_Tail );
+
+ node_type * pNext = pCur->m_pNext.load( memory_model::memory_order_relaxed ).ptr();
+ pCur->m_pNext.store( marked_node_ptr( pHead, 1 ), memory_model::memory_order_relaxed ); // logical deletion + back-link for search
+ pPred->m_pNext.store( marked_node_ptr( pNext ), memory_model::memory_order_release ); // physically deleting
+ }
+
// split-list support
bool insert_aux_node( node_type * pNode )
{
template <typename Func>
bool insert_at( node_type * pHead, value_type& val, Func f )
{
- link_checker::is_empty( node_traits::to_node_ptr( val ));
position pos;
key_comparator cmp;
if ( validate( pos.pPred, pos.pCur )) {
if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
// failed: key already in list
+ m_Stat.onInsertFailed();
return false;
}
f( val );
link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
- ++m_ItemCounter;
- return true;
+ break;
}
}
+
+ m_Stat.onInsertRetry();
}
+
+ ++m_ItemCounter;
+ m_Stat.onInsertSuccess();
+ return true;
}
iterator insert_at_( node_type * pHead, value_type& val )
{
// item found
unlink_node( pos.pPred, pos.pCur, pHead );
- --m_ItemCounter;
nResult = 1;
}
else
if ( nResult ) {
if ( nResult > 0 ) {
+ --m_ItemCounter;
dispose_node( pos.pCur );
+ m_Stat.onEraseSuccess();
return true;
}
+
+ m_Stat.onEraseFailed();
return false;
}
+
+ m_Stat.onEraseRetry();
}
}
// key found
unlink_node( pos.pPred, pos.pCur, pHead );
f( *node_traits::to_value_ptr( *pos.pCur ));
- --m_ItemCounter;
nResult = 1;
}
else
if ( nResult ) {
if ( nResult > 0 ) {
+ --m_ItemCounter;
dispose_node( pos.pCur );
+ m_Stat.onEraseSuccess();
return true;
}
+
+ m_Stat.onEraseFailed();
return false;
}
+
+ m_Stat.onEraseRetry();
}
}
if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
// key found
unlink_node( pos.pPred, pos.pCur, pHead );
- --m_ItemCounter;
nResult = 1;
}
else {
}
if ( nResult ) {
- if ( nResult > 0 )
+ if ( nResult > 0 ) {
+ --m_ItemCounter;
+ m_Stat.onEraseSuccess();
return node_traits::to_value_ptr( pos.pCur );
+ }
+
+ m_Stat.onEraseFailed();
return nullptr;
}
+
+ m_Stat.onEraseRetry();
}
}
search( pHead, val, pos, cmp );
if ( pos.pCur != &m_Tail ) {
std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
- if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
- {
+ if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
f( *node_traits::to_value_ptr( *pos.pCur ), val );
+ m_Stat.onFindSuccess();
return true;
}
}
+
+ m_Stat.onFindFailed();
return false;
}
search( pHead, val, pos, cmp );
if ( pos.pCur != &m_Tail ) {
- if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
+ if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
+ m_Stat.onFindSuccess();
return const_iterator( pos.pCur );
+ }
}
+
+ m_Stat.onFindFailed();
return end();
}
pos.pPred = pPrev.ptr();
}
- static bool validate( node_type * pPred, node_type * pCur ) CDS_NOEXCEPT
+ bool validate( node_type * pPred, node_type * pCur ) CDS_NOEXCEPT
+ {
+ if ( validate_link( pPred, pCur )) {
+ m_Stat.onValidationSuccess();
+ return true;
+ }
+
+ m_Stat.onValidationFailed();
+ return false;
+ }
+
+ static bool validate_link( node_type * pPred, node_type * pCur ) CDS_NOEXCEPT
{
// RCU lock should be locked
assert( gc::is_locked());
// RCU lock should be locked
assert( gc::is_locked());
- link_checker::is_empty( node_traits::to_node_ptr( val ));
position pos;
key_comparator cmp;
if ( validate( pos.pPred, pos.pCur )) {
if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
// failed: key already in list
+ m_Stat.onInsertFailed();
return false;
}
link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
- ++m_ItemCounter;
- return true;
+ break;
}
}
+
+ m_Stat.onInsertRetry();
}
+
+ ++m_ItemCounter;
+ m_Stat.onInsertSuccess();
+ return true;
+
}
template <typename Func>
// key already in the list
func( false, *node_traits::to_value_ptr( *pos.pCur ), val );
+ m_Stat.onUpdateExisting();
return std::make_pair( iterator( pos.pCur ), false );
}
else {
// new key
- if ( !bAllowInsert )
+ if ( !bAllowInsert ) {
+ m_Stat.onUpdateFailed();
return std::make_pair( end(), false );
-
- link_checker::is_empty( node_traits::to_node_ptr( val ));
+ }
func( true, val, val );
link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
- ++m_ItemCounter;
- return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
+ break;
}
}
}
+
+ m_Stat.onUpdateRetry();
}
+
+ ++m_ItemCounter;
+ m_Stat.onUpdateNew();
+ return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
+ }
+ //@endcond
+
+ private:
+ //@cond
+ const_iterator get_const_begin() const
+ {
+ const_iterator it( const_cast<node_type *>(&m_Head));
+ ++it; // skip dummy head
+ return it;
+ }
+ const_iterator get_const_end() const
+ {
+ return const_iterator( const_cast<node_type *>(&m_Tail));
}
//@endcond
};
projects / libcds.git / blobdiff