X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=blobdiff_plain;f=cds%2Fintrusive%2Fsplit_list_rcu.h;h=c8902d111c111df563004497fcef8ab46d82bb1c;hp=68949e600798350209a8745d68acd3d62a24899a;hb=2bb66f1d159d044d2c5dad0f0f968abcb6d53287;hpb=1b5087c99fb779e0b82efdfc9523a848fe593bb1 diff --git a/cds/intrusive/split_list_rcu.h b/cds/intrusive/split_list_rcu.h index 68949e60..c8902d11 100644 --- a/cds/intrusive/split_list_rcu.h +++ b/cds/intrusive/split_list_rcu.h @@ -1,7 +1,7 @@ /* 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/ @@ -101,14 +101,14 @@ namespace cds { namespace intrusive { protected: //@cond - typedef split_list::details::rebind_list_traits wrapped_ordered_list; + typedef split_list::details::rebind_list_traits ordered_list_adapter; //@endcond public: # ifdef CDS_DOXYGEN_INVOKED typedef OrderedList ordered_list; ///< type of ordered list used as base for split-list # else - typedef typename wrapped_ordered_list::result ordered_list; + typedef typename ordered_list_adapter::result ordered_list; # endif typedef typename ordered_list::value_type value_type; ///< type of value stored in the split-list typedef typename ordered_list::key_comparator key_comparator; ///< key compare functor @@ -141,15 +141,16 @@ namespace cds { namespace intrusive { This traits is intended for converting between underlying ordered list node type \ref list_node_type and split-list node type \ref node_type */ - typedef split_list::node_traits node_traits; + typedef typename ordered_list_adapter::node_traits node_traits; /// Bucket table implementation typedef typename split_list::details::bucket_table_selector< traits::dynamic_bucket_table , gc - , node_type + , typename ordered_list_adapter::aux_node , opt::allocator< typename traits::allocator > , opt::memory_model< memory_model > + , opt::free_list< typename traits::free_list > >::type bucket_table; typedef typename bucket_table::aux_node_type aux_node_type; ///< auxiliary node type @@ -282,7 +283,7 @@ namespace cds { namespace intrusive { */ SplitListSet() : m_nBucketCountLog2(1) - , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) ) + , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor())) { init(); } @@ -294,7 +295,7 @@ namespace cds { namespace intrusive { ) : m_Buckets( nItemCount, nLoadFactor ) , m_nBucketCountLog2(1) - , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) ) + , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor())) { init(); } @@ -449,7 +450,7 @@ namespace cds { namespace intrusive { aux_node_type * pHead = get_bucket( nHash ); assert( pHead != nullptr ); - if ( m_List.unlink_at( pHead, val ) ) { + if ( m_List.unlink_at( pHead, val )) { --m_ItemCounter; m_Stat.onEraseSuccess(); return true; @@ -476,7 +477,7 @@ namespace cds { namespace intrusive { template bool erase( Q const& key ) { - return erase_( key, key_comparator() ); + return erase_( key, key_comparator()); } /// Deletes the item from the set using \p pred for searching @@ -490,7 +491,7 @@ namespace cds { namespace intrusive { bool erase_with( Q const& key, Less pred ) { CDS_UNUSED( pred ); - return erase_( key, typename wrapped_ordered_list::template make_compare_from_less() ); + return erase_( key, typename ordered_list_adapter::template make_compare_from_less()); } /// Deletes the item from the set @@ -530,7 +531,7 @@ namespace cds { namespace intrusive { bool erase_with( Q const& key, Less pred, Func f ) { CDS_UNUSED( pred ); - return erase_( key, typename wrapped_ordered_list::template make_compare_from_less(), f ); + return erase_( key, typename ordered_list_adapter::template make_compare_from_less(), f ); } /// Extracts an item from the set @@ -573,7 +574,7 @@ namespace cds { namespace intrusive { template exempt_ptr extract( Q const& key ) { - return exempt_ptr(extract_( key, key_comparator() )); + return exempt_ptr(extract_( key, key_comparator())); } /// Extracts an item from the set using \p pred for searching @@ -638,14 +639,14 @@ namespace cds { namespace intrusive { bool find_with( Q& key, Less pred, Func f ) { CDS_UNUSED( pred ); - return find_( key, typename wrapped_ordered_list::template make_compare_from_less(), f ); + return find_( key, typename ordered_list_adapter::template make_compare_from_less(), f ); } //@cond template bool find_with( Q const& key, Less pred, Func f ) { CDS_UNUSED( pred ); - return find_( key, typename wrapped_ordered_list::template make_compare_from_less(), f ); + return find_( key, typename ordered_list_adapter::template make_compare_from_less(), f ); } //@endcond @@ -661,7 +662,7 @@ namespace cds { namespace intrusive { template bool contains( Q const& key ) { - return find_value( key, key_comparator() ); + return find_value( key, key_comparator()); } //@cond template @@ -682,7 +683,7 @@ namespace cds { namespace intrusive { bool contains( Q const& key, Less pred ) { CDS_UNUSED( pred ); - return find_value( key, typename wrapped_ordered_list::template make_compare_from_less() ); + return find_value( key, typename ordered_list_adapter::template make_compare_from_less()); } //@cond template @@ -724,7 +725,7 @@ namespace cds { namespace intrusive { template raw_ptr get( Q const& key ) { - return get_( key, key_comparator() ); + return get_( key, key_comparator()); } /// Finds the key \p key and return the item found @@ -740,7 +741,7 @@ namespace cds { namespace intrusive { raw_ptr get_with( Q const& key, Less pred ) { CDS_UNUSED( pred ); - return get_( key, typename wrapped_ordered_list::template make_compare_from_less()); + return get_( key, typename ordered_list_adapter::template make_compare_from_less()); } @@ -764,7 +765,7 @@ namespace cds { namespace intrusive { void clear() { iterator it = begin(); - while ( it != end() ) { + while ( it != end()) { iterator i(it); ++i; unlink( *it ); @@ -778,6 +779,12 @@ namespace cds { namespace intrusive { return m_Stat; } + /// Returns internal statistics for \p OrderedList + typename OrderedList::stat const& list_statistics() const + { + return m_List.statistics(); + } + protected: //@cond template @@ -828,7 +835,7 @@ namespace cds { namespace intrusive { */ iterator begin() { - return iterator( m_List.begin(), m_List.end() ); + return iterator( m_List.begin(), m_List.end()); } /// Returns an iterator that addresses the location succeeding the last element in a split-list @@ -840,7 +847,7 @@ namespace cds { namespace intrusive { */ iterator end() { - return iterator( m_List.end(), m_List.end() ); + return iterator( m_List.end(), m_List.end()); } /// Returns a forward const iterator addressing the first element in a split-list @@ -851,7 +858,7 @@ namespace cds { namespace intrusive { /// Returns a forward const iterator addressing the first element in a split-list const_iterator cbegin() const { - return const_iterator( m_List.cbegin(), m_List.cend() ); + return const_iterator( m_List.cbegin(), m_List.cend()); } /// Returns an const iterator that addresses the location succeeding the last element in a split-list @@ -862,7 +869,7 @@ namespace cds { namespace intrusive { /// Returns an const iterator that addresses the location succeeding the last element in a split-list const_iterator cend() const { - return const_iterator( m_List.cend(), m_List.cend() ); + return const_iterator( m_List.cend(), m_List.cend()); } //@} @@ -898,7 +905,7 @@ namespace cds { namespace intrusive { static size_t parent_bucket( size_t nBucket ) { assert( nBucket > 0 ); - return nBucket & ~( 1 << bitop::MSBnz( nBucket ) ); + return nBucket & ~( 1 << bitop::MSBnz( nBucket )); } aux_node_type * init_bucket( size_t const nBucket ) @@ -918,13 +925,13 @@ namespace cds { namespace intrusive { aux_node_type * pBucket = m_Buckets.bucket( nBucket ); back_off bkoff; - for ( ;; pBucket = m_Buckets.bucket( nBucket ) ) { + for ( ;; pBucket = m_Buckets.bucket( nBucket )) { if ( pBucket ) return pBucket; - pBucket = alloc_aux_node( split_list::dummy_hash( nBucket ) ); + pBucket = alloc_aux_node( split_list::dummy_hash( nBucket )); if ( pBucket ) { - if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) { + if ( m_List.insert_aux_node( pParentBucket, pBucket )) { m_Buckets.bucket( nBucket, pBucket ); m_Stat.onNewBucket(); return pBucket; @@ -943,7 +950,7 @@ namespace cds { namespace intrusive { } // Another thread set the bucket. Wait while it done - for ( pBucket = m_Buckets.bucket( nBucket ); pBucket == nullptr; pBucket = m_Buckets.bucket( nBucket ) ) { + for ( pBucket = m_Buckets.bucket( nBucket ); pBucket == nullptr; pBucket = m_Buckets.bucket( nBucket )) { bkoff(); m_Stat.onBusyWaitBucketInit(); } @@ -959,7 +966,7 @@ namespace cds { namespace intrusive { if ( pHead == nullptr ) pHead = init_bucket( nBucket ); - assert( pHead->is_dummy() ); + assert( pHead->is_dummy()); return pHead; } @@ -988,7 +995,7 @@ namespace cds { namespace intrusive { size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed); const size_t nBucketCount = static_cast(1) << sz; - if ( nBucketCount < m_Buckets.capacity() ) { + if ( nBucketCount < m_Buckets.capacity()) { // we may grow the bucket table const size_t nLoadFactor = m_Buckets.load_factor(); if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor )) @@ -1060,7 +1067,7 @@ namespace cds { namespace intrusive { value_type * extract_with_( Q const& val, Less pred ) { CDS_UNUSED( pred ); - return extract_( val, typename wrapped_ordered_list::template make_compare_from_less()); + return extract_( val, typename ordered_list_adapter::template make_compare_from_less()); } template @@ -1071,7 +1078,7 @@ namespace cds { namespace intrusive { aux_node_type * pHead = get_bucket( nHash ); assert( pHead != nullptr ); - if ( m_List.erase_at( pHead, sv, cmp ) ) { + if ( m_List.erase_at( pHead, sv, cmp )) { --m_ItemCounter; m_Stat.onEraseSuccess(); return true;