/*
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 );
- 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
- }
-
//@endcond
public:
}
//@}
- 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()
{
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 )
{
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());
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 );
+ }
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