From cad63bb1872fe65225735d0035fd68469971a761 Mon Sep 17 00:00:00 2001 From: khizmax Date: Thu, 23 Oct 2014 23:37:29 +0400 Subject: [PATCH] LazyList refactoring --- cds/intrusive/details/lazy_list_base.h | 124 ++++++++-------------- cds/intrusive/details/michael_list_base.h | 8 +- cds/intrusive/impl/lazy_list.h | 111 ++++++++----------- 3 files changed, 89 insertions(+), 154 deletions(-) diff --git a/cds/intrusive/details/lazy_list_base.h b/cds/intrusive/details/lazy_list_base.h index 340d8027..136ce817 100644 --- a/cds/intrusive/details/lazy_list_base.h +++ b/cds/intrusive/details/lazy_list_base.h @@ -3,12 +3,10 @@ #ifndef __CDS_INTRUSIVE_DETAILS_LAZY_LIST_BASE_H #define __CDS_INTRUSIVE_DETAILS_LAZY_LIST_BASE_H -#include // ref #include #include #include #include -#include #include #include @@ -22,8 +20,8 @@ namespace cds { namespace intrusive { /** Template parameters: - GC - garbage collector - - Lock - lock type. Default is cds::lock::Spin - - Tag - a tag used to distinguish between different implementation. An incomplete type can be used as a tag. + - Lock - lock type. Default is \p cds::lock::Spin + - Tag - a \ref cds_intrusive_hook_tag "tag" */ template < class GC @@ -39,8 +37,8 @@ namespace cds { namespace intrusive { typedef cds::details::marked_ptr marked_ptr ; ///< marked pointer typedef typename gc::template atomic_marked_ptr< marked_ptr> atomic_marked_ptr ; ///< atomic marked pointer specific for GC - atomic_marked_ptr m_pNext ; ///< pointer to the next node in the list + logical deletion mark - mutable lock_type m_Lock ; ///< Node lock + atomic_marked_ptr m_pNext; ///< pointer to the next node in the list + logical deletion mark + mutable lock_type m_Lock; ///< Node lock /// Checks if node is marked bool is_marked() const @@ -54,35 +52,6 @@ namespace cds { namespace intrusive { {} }; - //@cond - template - class boundary_nodes - { - typedef NodeType node_type; - - node_type m_Head; - node_type m_Tail; - - public: - node_type * head() - { - return &m_Head; - } - node_type const * head() const - { - return &m_Head; - } - node_type * tail() - { - return &m_Tail; - } - node_type const * tail() const - { - return &m_Tail; - } - }; - //@endcond - //@cond template struct node_cleaner { @@ -119,9 +88,9 @@ namespace cds { namespace intrusive { /// Base hook /** \p Options are: - - opt::gc - garbage collector used. + - opt::gc - garbage collector - opt::lock_type - lock type used for node locking. Default is lock::Spin - - opt::tag - tag + - opt::tag - a \ref cds_intrusive_hook_tag "tag" */ template < typename... Options > struct base_hook: public hook< opt::base_hook_tag, Options... > @@ -133,9 +102,9 @@ namespace cds { namespace intrusive { Use \p offsetof macro to define \p MemberOffset \p Options are: - - opt::gc - garbage collector used. + - opt::gc - garbage collector - opt::lock_type - lock type used for node locking. Default is lock::Spin - - opt::tag - tag + - opt::tag - a \ref cds_intrusive_hook_tag "tag" */ template < size_t MemberOffset, typename... Options > struct member_hook: public hook< opt::member_hook_tag, Options... > @@ -153,7 +122,7 @@ namespace cds { namespace intrusive { \p Options are: - opt::gc - garbage collector used. - opt::lock_type - lock type used for node locking. Default is lock::Spin - - opt::tag - tag + - opt::tag - a \ref cds_intrusive_hook_tag "tag" */ template struct traits_hook: public hook< opt::traits_hook_tag, Options... > @@ -217,82 +186,74 @@ namespace cds { namespace intrusive { //@endcond }; - /// Type traits for LazyList class - struct type_traits + /// LazyList traits + struct traits { /// Hook used /** - Possible values are: lazy_list::base_hook, lazy_list::member_hook, lazy_list::traits_hook. + Possible values are: \p lazy_list::base_hook, \p lazy_list::member_hook, \p lazy_list::traits_hook. */ typedef base_hook<> hook; - /// Key comparison functor + /// Key comparing functor /** - No default functor is provided. If the option is not specified, the \p less is used. + No default functor is provided. If the functor is not specified, the \p less is used. */ typedef opt::none compare; - /// specifies binary predicate used for key comparison. + /// Specifies binary predicate used for comparing keys /** Default is \p std::less. */ typedef opt::none less; - /// back-off strategy used - /** - If the option is not specified, the cds::backoff::Default is used. - */ + /// Back-off strategy typedef cds::backoff::Default back_off; - /// Disposer - /** - the functor used for dispose removed items. Default is opt::v::empty_disposer. - */ + /// Disposer for removing items typedef opt::v::empty_disposer disposer; - /// Item counter - /** - The type for item counting feature. - Default is no item counter (\ref atomicity::empty_item_counter) - */ + /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting typedef atomicity::empty_item_counter item_counter; /// Link fields checking feature /** - Default is \ref opt::debug_check_link + Default is \p opt::debug_check_link */ static const opt::link_check_type link_checker = opt::debug_check_link; - /// Allocator - /** - For intrusive lazy list an allocator is needed for dummy tail node allocation. - */ - typedef CDS_DEFAULT_ALLOCATOR allocator; - /// C++ memory ordering model - /** - List of available memory ordering see opt::memory_model + /** + Can be \p opt::v::relaxed_ordering (relaxed memory model, the default) + or \p opt::v::sequential_consistent (sequentially consisnent memory model). */ typedef opt::v::relaxed_ordering memory_model; /// RCU deadlock checking policy (only for \ref cds_intrusive_LazyList_rcu "RCU-based LazyList") /** - List of available options see opt::rcu_check_deadlock + List of available options see \p opt::rcu_check_deadlock */ typedef opt::v::rcu_throw_deadlock rcu_check_deadlock; - - //@cond - // for internal use only!!! - typedef opt::none boundary_node_type; - //@endcond }; - /// Metafunction converting option list to traits + /// Metafunction converting option list to \p lazy_list::traits /** - This is a wrapper for cds::opt::make_options< type_traits, Options...> - - See \ref LazyList, \ref type_traits, \ref cds::opt::make_options. - + Supported \p Options are: + - \p opt::hook - hook used. Possible values are: \p lazy_list::base_hook, \p lazy_list::member_hook, \p lazy_list::traits_hook. + If the option is not specified, \p %lazy_list::base_hook and \p gc::HP is used. + - \p opt::compare - key comparison functor. No default functor is provided. + If the option is not specified, the \p opt::less is used. + - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less. + - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used. + - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. Due the nature + of GC schema the disposer may be called asynchronously. + - \p opt::link_checker - the type of node's link fields checking. Default is \p opt::debug_check_link + - \p opt::item_counter - the type of item counting feature. Default is disabled (\p atomicity::empty_item_counter). + To enable item counting use \p atomicity::item_counter. + - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default) + or \p opt::v::sequential_consistent (sequentially consisnent memory model). + - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList" + Default is \p opt::v::rcu_throw_deadlock */ template struct make_traits { @@ -300,7 +261,7 @@ namespace cds { namespace intrusive { typedef implementation_defined type ; ///< Metafunction result # else typedef typename cds::opt::make_options< - typename cds::opt::find_type_traits< type_traits, Options... >::type + typename cds::opt::find_type_traits< traits, Options... >::type ,Options... >::type type; # endif @@ -310,11 +271,10 @@ namespace cds { namespace intrusive { //@cond // Forward declaration - template < class GC, typename T, class Traits = lazy_list::type_traits > + template < class GC, typename T, class Traits = lazy_list::traits > class LazyList; //@endcond - }} // namespace cds::intrusive #endif // #ifndef __CDS_INTRUSIVE_DETAILS_LAZY_LIST_BASE_H diff --git a/cds/intrusive/details/michael_list_base.h b/cds/intrusive/details/michael_list_base.h index 89f57198..caaa6502 100644 --- a/cds/intrusive/details/michael_list_base.h +++ b/cds/intrusive/details/michael_list_base.h @@ -20,7 +20,7 @@ namespace cds { namespace intrusive { /** Template parameters: - GC - garbage collector - - Tag - a tag used to distinguish between different implementation + - Tag - a \ref cds_intrusive_hook_tag "tag" */ template struct node @@ -73,7 +73,7 @@ namespace cds { namespace intrusive { /** \p Options are: - opt::gc - garbage collector used. - - opt::tag - tag + - opt::tag - a \ref cds_intrusive_hook_tag "tag" */ template < typename... Options > struct base_hook: public hook< opt::base_hook_tag, Options... > @@ -86,7 +86,7 @@ namespace cds { namespace intrusive { \p Options are: - opt::gc - garbage collector used. - - opt::tag - tag + - opt::tag - a \ref cds_intrusive_hook_tag "tag" */ template < size_t MemberOffset, typename... Options > struct member_hook: public hook< opt::member_hook_tag, Options... > @@ -103,7 +103,7 @@ namespace cds { namespace intrusive { \p Options are: - opt::gc - garbage collector used. - - opt::tag - tag + - opt::tag - a \ref cds_intrusive_hook_tag "tag" */ template struct traits_hook: public hook< opt::traits_hook_tag, Options... > diff --git a/cds/intrusive/impl/lazy_list.h b/cds/intrusive/impl/lazy_list.h index 13df8049..273a14c8 100644 --- a/cds/intrusive/impl/lazy_list.h +++ b/cds/intrusive/impl/lazy_list.h @@ -7,7 +7,6 @@ #include #include - namespace cds { namespace intrusive { /// Lazy ordered single-linked list @@ -218,30 +217,8 @@ namespace cds { namespace intrusive { protected: //@cond - typedef lazy_list::boundary_nodes< - gc - ,typename opt::select_default< typename options::boundary_node_type, node_type >::type - ,typename options::allocator - > boundary_nodes; - boundary_nodes m_Boundary ; ///< Head & tail dummy nodes - - node_type * head() - { - return m_Boundary.head(); - } - node_type const * head() const - { - return m_Boundary.head(); - } - node_type * tail() - { - return m_Boundary.tail(); - } - node_type const * tail() const - { - return m_Boundary.tail(); - } - //@endcond + node_type m_Head; + node_type m_Tail; item_counter m_ItemCounter ; ///< Item counter @@ -462,7 +439,7 @@ namespace cds { namespace intrusive { */ iterator begin() { - iterator it( head() ); + iterator it( &m_Head ); ++it ; // skip dummy head return it; } @@ -476,7 +453,7 @@ namespace cds { namespace intrusive { */ iterator end() { - return iterator( tail() ); + return iterator( &m_Tail ); } /// Returns a forward const iterator addressing the first element in a list @@ -507,13 +484,13 @@ namespace cds { namespace intrusive { //@cond const_iterator get_const_begin() const { - const_iterator it( const_cast( head() )); + const_iterator it( const_cast( &m_Head )); ++it ; // skip dummy head return it; } const_iterator get_const_end() const { - return const_iterator( const_cast( tail() )); + return const_iterator( const_cast(&m_Tail) ); } //@endcond @@ -522,17 +499,15 @@ namespace cds { namespace intrusive { LazyList() { static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" ); - - //m_pTail = cxx_allocator().New(); - head()->m_pNext.store( marked_node_ptr( tail() ), memory_model::memory_order_relaxed ); + m_Head.m_pNext.store( marked_node_ptr( &m_Tail ), memory_model::memory_order_relaxed ); } /// Destroys the list object ~LazyList() { clear(); - assert( head()->m_pNext.load(memory_model::memory_order_relaxed).ptr() == tail() ); - head()->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed ); + assert( m_Head.m_pNext.load( memory_model::memory_order_relaxed ).ptr() == &m_Tail ); + m_Head.m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed ); } /// Inserts new node @@ -544,7 +519,7 @@ namespace cds { namespace intrusive { */ bool insert( value_type& val ) { - return insert_at( head(), val ); + return insert_at( &m_Head, val ); } /// Inserts new node @@ -568,7 +543,7 @@ namespace cds { namespace intrusive { template bool insert( value_type& val, Func f ) { - return insert_at( head(), val, f ); + return insert_at( &m_Head, val, f ); } /// Ensures that the \p item exists in the list @@ -600,7 +575,7 @@ namespace cds { namespace intrusive { template std::pair ensure( value_type& val, Func func ) { - return ensure_at( head(), val, func ); + return ensure_at( &m_Head, val, func ); } /// Unlinks the item \p val from the list @@ -617,7 +592,7 @@ namespace cds { namespace intrusive { */ bool unlink( value_type& val ) { - return unlink_at( head(), val ); + return unlink_at( &m_Head, val ); } /// Deletes the item from the list @@ -629,7 +604,7 @@ namespace cds { namespace intrusive { template bool erase( Q const& val ) { - return erase_at( head(), val, key_comparator() ); + return erase_at( &m_Head, val, key_comparator() ); } /// Deletes the item from the list using \p pred predicate for searching @@ -642,7 +617,7 @@ namespace cds { namespace intrusive { template bool erase_with( Q const& val, Less pred ) { - return erase_at( head(), val, cds::opt::details::make_comparator_from_less() ); + return erase_at( &m_Head, val, cds::opt::details::make_comparator_from_less() ); } /// Deletes the item from the list @@ -662,7 +637,7 @@ namespace cds { namespace intrusive { template bool erase( const Q& val, Func func ) { - return erase_at( head(), val, key_comparator(), func ); + return erase_at( &m_Head, val, key_comparator(), func ); } /// Deletes the item from the list using \p pred predicate for searching @@ -675,7 +650,7 @@ namespace cds { namespace intrusive { template bool erase_with( const Q& val, Less pred, Func func ) { - return erase_at( head(), val, cds::opt::details::make_comparator_from_less(), func ); + return erase_at( &m_Head, val, cds::opt::details::make_comparator_from_less(), func ); } /// Extracts the item from the list with specified \p key @@ -709,7 +684,7 @@ namespace cds { namespace intrusive { template bool extract( guarded_ptr& dest, Q const& key ) { - return extract_at( head(), dest.guard(), key, key_comparator() ); + return extract_at( &m_Head, dest.guard(), key, key_comparator() ); } /// Extracts the item from the list with comparing functor \p pred @@ -724,7 +699,7 @@ namespace cds { namespace intrusive { template bool extract_with( guarded_ptr& dest, Q const& key, Less pred ) { - return extract_at( head(), dest.guard(), key, cds::opt::details::make_comparator_from_less() ); + return extract_at( &m_Head, dest.guard(), key, cds::opt::details::make_comparator_from_less() ); } /// Finds the key \p val @@ -751,7 +726,7 @@ namespace cds { namespace intrusive { template bool find( Q& val, Func f ) { - return find_at( head(), val, key_comparator(), f ); + return find_at( &m_Head, val, key_comparator(), f ); } /// Finds the key \p val using \p pred predicate for searching @@ -764,7 +739,7 @@ namespace cds { namespace intrusive { template bool find_with( Q& val, Less pred, Func f ) { - return find_at( head(), val, cds::opt::details::make_comparator_from_less(), f ); + return find_at( &m_Head, val, cds::opt::details::make_comparator_from_less(), f ); } /// Finds the key \p val @@ -788,7 +763,7 @@ namespace cds { namespace intrusive { template bool find( Q const& val, Func f ) { - return find_at( head(), val, key_comparator(), f ); + return find_at( &m_Head, val, key_comparator(), f ); } /// Finds the key \p val using \p pred predicate for searching @@ -801,7 +776,7 @@ namespace cds { namespace intrusive { template bool find_with( Q const& val, Less pred, Func f ) { - return find_at( head(), val, cds::opt::details::make_comparator_from_less(), f ); + return find_at( &m_Head, val, cds::opt::details::make_comparator_from_less(), f ); } /// Finds the key \p val @@ -812,7 +787,7 @@ namespace cds { namespace intrusive { template bool find( Q const & val ) { - return find_at( head(), val, key_comparator() ); + return find_at( &m_Head, val, key_comparator() ); } /// Finds the key \p val using \p pred predicate for searching @@ -825,7 +800,7 @@ namespace cds { namespace intrusive { template bool find_with( Q const& val, Less pred ) { - return find_at( head(), val, cds::opt::details::make_comparator_from_less() ); + return find_at( &m_Head, val, cds::opt::details::make_comparator_from_less() ); } /// Finds the key \p val and return the item found @@ -861,7 +836,7 @@ namespace cds { namespace intrusive { template bool get( guarded_ptr& ptr, Q const& val ) { - return get_at( head(), ptr.guard(), val, key_comparator() ); + return get_at( &m_Head, ptr.guard(), val, key_comparator() ); } /// Finds the key \p val and return the item found @@ -876,7 +851,7 @@ namespace cds { namespace intrusive { template bool get_with( guarded_ptr& ptr, Q const& val, Less pred ) { - return get_at( head(), ptr.guard(), val, cds::opt::details::make_comparator_from_less() ); + return get_at( &m_Head, ptr.guard(), val, cds::opt::details::make_comparator_from_less() ); } /// Clears the list @@ -888,16 +863,16 @@ namespace cds { namespace intrusive { typename gc::Guard guard; marked_node_ptr h; while ( !empty() ) { - h = head()->m_pNext.load(memory_model::memory_order_relaxed); + h = m_Head.m_pNext.load( memory_model::memory_order_relaxed ); guard.assign( node_traits::to_value_ptr( h.ptr() )); - if ( head()->m_pNext.load(memory_model::memory_order_acquire) == h ) { - head()->m_Lock.lock(); + if ( m_Head.m_pNext.load(memory_model::memory_order_acquire) == h ) { + m_Head.m_Lock.lock(); h->m_Lock.lock(); - unlink_node( head(), h.ptr(), head() ); + unlink_node( &m_Head, h.ptr(), &m_Head ); h->m_Lock.unlock(); - head()->m_Lock.unlock(); + m_Head.m_Lock.unlock(); retire_node( h.ptr() ) ; // free node } @@ -907,7 +882,7 @@ namespace cds { namespace intrusive { /// Checks if the list is empty bool empty() const { - return head()->m_pNext.load(memory_model::memory_order_relaxed).ptr() == tail(); + return m_Head.m_pNext.load( memory_model::memory_order_relaxed ).ptr() == &m_Tail; } /// Returns list's item count @@ -928,7 +903,7 @@ namespace cds { namespace intrusive { // split-list support bool insert_aux_node( node_type * pNode ) { - return insert_aux_node( head(), pNode ); + return insert_aux_node( &m_Head, pNode ); } // split-list support @@ -953,7 +928,7 @@ namespace cds { namespace intrusive { { auto_lock_position alp( pos ); if ( validate( pos.pPred, pos.pCur )) { - if ( pos.pCur != tail() && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) { + if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) { // failed: key already in list return false; } @@ -979,7 +954,7 @@ namespace cds { namespace intrusive { { auto_lock_position alp( pos ); if ( validate( pos.pPred, pos.pCur )) { - if ( pos.pCur != tail() && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) { + if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) { // failed: key already in list return false; } @@ -1005,7 +980,7 @@ namespace cds { namespace intrusive { { auto_lock_position alp( pos ); if ( validate( pos.pPred, pos.pCur )) { - if ( pos.pCur != tail() && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) { + if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) { // key already in the list func( false, *node_traits::to_value_ptr( *pos.pCur ) , val ); @@ -1037,7 +1012,7 @@ namespace cds { namespace intrusive { { auto_lock_position alp( pos ); if ( validate( pos.pPred, pos.pCur ) ) { - if ( pos.pCur != tail() + if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 && node_traits::to_value_ptr( pos.pCur ) == &val ) { @@ -1071,7 +1046,7 @@ namespace cds { namespace intrusive { { auto_lock_position alp( pos ); if ( validate( pos.pPred, pos.pCur )) { - if ( pos.pCur != tail() && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) { + if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) { // key found unlink_node( pos.pPred, pos.pCur, pHead ); f( *node_traits::to_value_ptr( *pos.pCur ) ); @@ -1125,7 +1100,7 @@ namespace cds { namespace intrusive { position pos; search( pHead, val, pos, cmp ); - if ( pos.pCur != tail() ) { + if ( pos.pCur != &m_Tail ) { std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock ); if ( !pos.pCur->is_marked() && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) @@ -1143,7 +1118,7 @@ namespace cds { namespace intrusive { position pos; search( pHead, val, pos, cmp ); - return pos.pCur != tail() + return pos.pCur != &m_Tail && !pos.pCur->is_marked() && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0; } @@ -1154,7 +1129,7 @@ namespace cds { namespace intrusive { position pos; search( pHead, val, pos, cmp ); - if ( pos.pCur != tail() + if ( pos.pCur != &m_Tail && !pos.pCur->is_marked() && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) { @@ -1171,7 +1146,7 @@ namespace cds { namespace intrusive { template void search( node_type * pHead, const Q& key, position& pos, Compare cmp ) { - const node_type * pTail = tail(); + const node_type * pTail = &m_Tail; marked_node_ptr pCur( pHead ); marked_node_ptr pPrev( pHead ); -- 2.34.1