X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fintrusive%2Fsplit_list_nogc.h;h=966f5da3aea33bf038ab936ccaaa5431ea18da3f;hb=6924946ceeaae28bc227fe7c9d8e939963bb9d69;hp=8e2c44d7ef86340ceab546194f29b6d1dde4ffee;hpb=377b2499eb0d14cd5814df70f144aaf1e132b4bd;p=libcds.git diff --git a/cds/intrusive/split_list_nogc.h b/cds/intrusive/split_list_nogc.h index 8e2c44d7..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/ @@ -83,6 +83,7 @@ namespace cds { namespace intrusive { 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 @@ -190,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(); } @@ -202,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(); } @@ -281,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; } @@ -304,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; } @@ -411,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 @@ -458,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 @@ -470,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()); } //@} @@ -506,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(); @@ -525,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(); @@ -545,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 ordered_list_adapter::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 ) @@ -628,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; @@ -653,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(); } @@ -669,7 +676,7 @@ namespace cds { namespace intrusive { if ( pHead == nullptr ) pHead = init_bucket( nBucket ); - assert( pHead->is_dummy() ); + assert( pHead->is_dummy()); return pHead; } @@ -677,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 ); } @@ -698,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 ), @@ -725,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 };