X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fintrusive%2Fsplit_list_nogc.h;h=966f5da3aea33bf038ab936ccaaa5431ea18da3f;hb=6924946ceeaae28bc227fe7c9d8e939963bb9d69;hp=accccd6fb6035d410015813785534dbe6f48e761;hpb=1b5087c99fb779e0b82efdfc9523a848fe593bb1;p=libcds.git diff --git a/cds/intrusive/split_list_nogc.h b/cds/intrusive/split_list_nogc.h index accccd6f..966f5da3 100644 --- a/cds/intrusive/split_list_nogc.h +++ b/cds/intrusive/split_list_nogc.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/ @@ -70,19 +70,20 @@ 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 comparison functor typedef typename ordered_list::disposer disposer; ///< Node disposer functor + typedef typename traits::bit_reversal bit_reversal; ///< Bit reversal algorithm, see \p split_list::traits::bit_reversal typedef typename traits::item_counter item_counter; ///< Item counter type typedef typename traits::back_off back_off; ///< back-off strategy typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option @@ -105,15 +106,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; ///< dummy node type @@ -189,7 +191,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(); } @@ -201,7 +203,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(); } @@ -280,7 +282,7 @@ namespace cds { namespace intrusive { value_type * contains( Q const& key ) { iterator it = find_( key ); - if ( it == end() ) + if ( it == end()) return nullptr; return &*it; } @@ -303,7 +305,7 @@ namespace cds { namespace intrusive { value_type * contains( Q const& key, Less pred ) { iterator it = find_with_( key, pred ); - if ( it == end() ) + if ( it == end()) return nullptr; return &*it; } @@ -360,14 +362,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 @@ -410,6 +412,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 @@ -457,7 +465,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 @@ -469,31 +477,31 @@ 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 const_iterator begin() const { - return const_iterator( m_List.begin(), m_List.end() ); + return const_iterator( m_List.begin(), m_List.end()); } /// 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 const_iterator end() const { - return const_iterator( m_List.end(), m_List.end() ); + return const_iterator( m_List.end(), m_List.end()); } /// 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()); } //@} @@ -505,13 +513,13 @@ namespace cds { namespace intrusive { aux_node_type * pHead = get_bucket( nHash ); assert( pHead != nullptr ); - node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash ); + node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash ); list_iterator it = m_List.insert_at_( pHead, val ); - if ( it != m_List.end() ) { + if ( it != m_List.end()) { inc_item_count(); m_Stat.onInsertSuccess(); - return iterator( it, m_List.end() ); + return iterator( it, m_List.end()); } m_Stat.onInsertFailed(); return end(); @@ -524,10 +532,10 @@ namespace cds { namespace intrusive { aux_node_type * pHead = get_bucket( nHash ); assert( pHead != nullptr ); - node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash ); + node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash ); std::pair ret = m_List.update_at_( pHead, val, func, bAllowInsert ); - if ( ret.first != m_List.end() ) { + if ( ret.first != m_List.end()) { if ( ret.second ) { inc_item_count(); m_Stat.onUpdateNew(); @@ -544,37 +552,37 @@ namespace cds { namespace intrusive { { CDS_UNUSED( pred ); size_t nHash = hash_value( val ); - split_list::details::search_value_type sv( val, split_list::regular_hash( nHash )); + split_list::details::search_value_type sv( val, split_list::regular_hash( nHash )); aux_node_type * pHead = get_bucket( nHash ); assert( pHead != nullptr ); - auto it = m_List.find_at_( pHead, sv, typename wrapped_ordered_list::template make_compare_from_less() ); - m_Stat.onFind( it != m_List.end() ); - return iterator( it, m_List.end() ); + auto it = m_List.find_at_( pHead, sv, typename ordered_list_adapter::template make_compare_from_less()); + m_Stat.onFind( it != m_List.end()); + return iterator( it, m_List.end()); } template iterator find_( Q const& val ) { size_t nHash = hash_value( val ); - split_list::details::search_value_type sv( val, split_list::regular_hash( nHash )); + split_list::details::search_value_type sv( val, split_list::regular_hash( nHash )); aux_node_type * pHead = get_bucket( nHash ); assert( pHead != nullptr ); - auto it = m_List.find_at_( pHead, sv, key_comparator() ); - m_Stat.onFind( it != m_List.end() ); - return iterator( it, m_List.end() ); + auto it = m_List.find_at_( pHead, sv, key_comparator()); + m_Stat.onFind( it != m_List.end()); + return iterator( it, m_List.end()); } template bool find_( Q& val, Compare cmp, Func f ) { size_t nHash = hash_value( val ); - split_list::details::search_value_type sv( val, split_list::regular_hash( nHash )); + split_list::details::search_value_type sv( val, split_list::regular_hash( nHash )); aux_node_type * pHead = get_bucket( nHash ); assert( pHead != nullptr ); return m_Stat.onFind( m_List.find_at( pHead, sv, cmp, - [&f](value_type& item, split_list::details::search_value_type& val){ f(item, val.val ); })); + [&f](value_type& item, split_list::details::search_value_type& v){ f(item, v.val ); })); } aux_node_type * alloc_aux_node( size_t nHash ) @@ -627,13 +635,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; @@ -652,7 +660,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(); } @@ -668,7 +676,7 @@ namespace cds { namespace intrusive { if ( pHead == nullptr ) pHead = init_bucket( nBucket ); - assert( pHead->is_dummy() ); + assert( pHead->is_dummy()); return pHead; } @@ -676,10 +684,10 @@ namespace cds { namespace intrusive { void init() { // Initialize bucket 0 - aux_node_type * pNode = alloc_aux_node( 0 /*split_list::dummy_hash(0)*/ ); + aux_node_type * pNode = alloc_aux_node( 0 /*split_list::dummy_hash(0)*/ ); // insert_aux_node cannot return false for empty list - CDS_VERIFY( m_List.insert_aux_node( pNode ) ); + CDS_VERIFY( m_List.insert_aux_node( pNode )); m_Buckets.bucket( 0, pNode ); } @@ -697,10 +705,10 @@ 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 ) ) + if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor )) return; // someone already have updated m_nBucketCountLog2, so stop here m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ), @@ -724,8 +732,8 @@ namespace cds { namespace intrusive { atomics::atomic m_nBucketCountLog2; ///< log2( current bucket count ) atomics::atomic m_nMaxItemCount; ///< number of items container can hold, before we have to resize - item_counter m_ItemCounter; ///< Item counter hash m_HashFunctor; ///< Hash functor + item_counter m_ItemCounter; ///< Item counter stat m_Stat; ///< Internal statistics //@endcond };