Fixed split-list inc_item_count()

[libcds.git] / cds / intrusive / split_list.h

diff --git a/cds/intrusive/split_list.h b/cds/intrusive/split_list.h
index 7a923dc8600e8ac4845637490b421d49f089d1ee..0be790d30c339525ee8fe3d00b6ef6a2810b5af9 100644 (file)
--- a/cds/intrusive/split_list.h
+++ b/cds/intrusive/split_list.h
@@ -3,6 +3,7 @@
 #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_H
 #define CDSLIB_INTRUSIVE_SPLIT_LIST_H
 
+#include <limits>
 #include <cds/intrusive/details/split_list_base.h>
 
 namespace cds { namespace intrusive {
@@ -349,6 +350,7 @@ namespace cds { namespace intrusive {
         ordered_list_wrapper    m_List;             ///< Ordered list containing split-list items
         bucket_table            m_Buckets;          ///< bucket table
         atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
+        atomics::atomic<size_t> m_nMaxItemCount;    ///< number of items container can hold, before we have to resize
         item_counter            m_ItemCounter;      ///< Item counter
         hash                    m_HashFunctor;      ///< Hash functor
         stat                    m_Stat;             ///< Internal statistics
@@ -457,13 +459,31 @@ namespace cds { namespace intrusive {
             m_Buckets.bucket( 0, pNode );
         }
 
+        static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
+        {
+            return nBucketCount * nLoadFactor;
+        }
+
         void inc_item_count()
         {
-            size_t sz = m_nBucketCountLog2.load(atomics::memory_order_relaxed);
-            if ( ( ++m_ItemCounter >> sz ) > m_Buckets.load_factor() && (static_cast<size_t>(1) << sz ) < m_Buckets.capacity() )
-            {
+            size_t nMaxCount = m_nMaxItemCount.load(memory_model::memory_order_relaxed);
+            if ( ++m_ItemCounter <= nMaxCount )
+                return;
+
+            size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed);
+            const size_t nBucketCount = static_cast<size_t>(1) << sz;
+            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 ))
+                    return; // someone already have updated m_nBucketCountLog2, so stop here
+
+                m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ), 
+                                                         memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
                 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
             }
+            else
+                m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
         }
 
         template <typename Q, typename Compare, typename Func>
@@ -587,6 +607,7 @@ namespace cds { namespace intrusive {
         */
         SplitListSet()
             : m_nBucketCountLog2(1)
+            , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
         {
             init();
         }
@@ -598,6 +619,7 @@ namespace cds { namespace intrusive {
             )
             : m_Buckets( nItemCount, nLoadFactor )
             , m_nBucketCountLog2(1)
+            , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
         {
             init();
         }