From 80add1442dc4332f27a2488bbcd915abf077bf8d Mon Sep 17 00:00:00 2001
From: khizmax <libcds.dev@gmail.com>
Date: Fri, 24 Apr 2015 22:57:13 +0300
Subject: [PATCH] Fixed max bucket count error in SplitList

---
 cds/intrusive/split_list.h      | 21 ++++++++++++---------
 cds/intrusive/split_list_nogc.h | 25 ++++++++++++++-----------
 cds/intrusive/split_list_rcu.h  | 24 ++++++++++++++----------
 3 files changed, 40 insertions(+), 30 deletions(-)

diff --git a/cds/intrusive/split_list.h b/cds/intrusive/split_list.h
index e28cdf93..3f154110 100644
--- a/cds/intrusive/split_list.h
+++ b/cds/intrusive/split_list.h
@@ -3,8 +3,8 @@
 #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_H
 #define CDSLIB_INTRUSIVE_SPLIT_LIST_H
 
-#include <cds/intrusive/details/split_list_base.h>
 #include <limits>
+#include <cds/intrusive/details/split_list_base.h>
 
 namespace cds { namespace intrusive {
 
@@ -470,16 +470,19 @@ namespace cds { namespace intrusive {
             if ( ++m_ItemCounter <= nMaxCount )
                 return;
 
-            const size_t nLoadFactor = m_Buckets.load_factor();
             size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed);
             const size_t nBucketCount = static_cast<size_t>(1) << sz;
-            if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
-                return; // someone already have updated m_nBucketCountLog2, so stop here
-
-            const size_t nNewMaxCount = (nBucketCount < m_Buckets.capacity()) ? max_item_count( nBucketCount << 1, nLoadFactor )
-                                                                              : std::numeric_limits<size_t>::max();
-            m_nMaxItemCount.compare_exchange_strong( nMaxCount, nNewMaxCount, 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 );
+            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
+
+                const size_t nNewMaxCount = (nBucketCount < m_Buckets.capacity()) ? max_item_count( nBucketCount << 1, nLoadFactor )
+                                                                                  : std::numeric_limits<size_t>::max();
+                m_nMaxItemCount.compare_exchange_strong( nMaxCount, nNewMaxCount, 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 );
+            }
         }
 
         template <typename Q, typename Compare, typename Func>
diff --git a/cds/intrusive/split_list_nogc.h b/cds/intrusive/split_list_nogc.h
index 5bf894ba..cdf9c5e0 100644
--- a/cds/intrusive/split_list_nogc.h
+++ b/cds/intrusive/split_list_nogc.h
@@ -3,11 +3,11 @@
 #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_NOGC_H
 #define CDSLIB_INTRUSIVE_SPLIT_LIST_NOGC_H
 
+#include <limits>
+
 #include <cds/intrusive/details/split_list_base.h>
 #include <cds/gc/nogc.h>
 
-#include <limits>
-
 namespace cds { namespace intrusive {
 
     /// Split-ordered list (template specialization for gc::nogc)
@@ -267,17 +267,20 @@ namespace cds { namespace intrusive {
             if ( ++m_ItemCounter <= nMaxCount )
                 return;
 
-            const size_t nLoadFactor = m_Buckets.load_factor();
             size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed);
             const size_t nBucketCount = static_cast<size_t>(1) << sz;
-            if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
-                return; // someone already have updated m_nBucketCountLog2, so stop here
-
-            const size_t nNewMaxCount = (nBucketCount < m_Buckets.capacity()) ? max_item_count( nBucketCount << 1, nLoadFactor )
-                                                                              : std::numeric_limits<size_t>::max();
-            m_nMaxItemCount.compare_exchange_strong( nMaxCount, nNewMaxCount, memory_model::memory_order_relaxed,
-                memory_model::memory_order_relaxed );
-            m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, memory_model::memory_order_relaxed );
+            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
+
+                const size_t nNewMaxCount = (nBucketCount < m_Buckets.capacity()) ? max_item_count( nBucketCount << 1, nLoadFactor )
+                                                                                  : std::numeric_limits<size_t>::max();
+                m_nMaxItemCount.compare_exchange_strong( nMaxCount, nNewMaxCount, memory_model::memory_order_relaxed,
+                    memory_model::memory_order_relaxed );
+                m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, memory_model::memory_order_relaxed );
+            }
         }
 
         //@endcond
diff --git a/cds/intrusive/split_list_rcu.h b/cds/intrusive/split_list_rcu.h
index 8deeb7ce..7774dfda 100644
--- a/cds/intrusive/split_list_rcu.h
+++ b/cds/intrusive/split_list_rcu.h
@@ -3,9 +3,10 @@
 #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_RCU_H
 #define CDSLIB_INTRUSIVE_SPLIT_LIST_RCU_H
 
+#include <limits>
+
 #include <cds/intrusive/details/split_list_base.h>
 #include <cds/details/binary_functor_wrapper.h>
-#include <limits>
 
 namespace cds { namespace intrusive {
 
@@ -363,17 +364,20 @@ namespace cds { namespace intrusive {
             if ( ++m_ItemCounter <= nMaxCount )
                 return;
 
-            const size_t nLoadFactor = m_Buckets.load_factor();
             size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed);
             const size_t nBucketCount = static_cast<size_t>(1) << sz;
-            if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
-                return; // someone already have updated m_nBucketCountLog2, so stop here
-
-            const size_t nNewMaxCount = (nBucketCount < m_Buckets.capacity()) ? max_item_count( nBucketCount << 1, nLoadFactor )
-                                                                              : std::numeric_limits<size_t>::max();
-            m_nMaxItemCount.compare_exchange_strong( nMaxCount, nNewMaxCount, memory_model::memory_order_relaxed,
-                memory_model::memory_order_relaxed );
-            m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, memory_model::memory_order_relaxed );
+            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
+
+                const size_t nNewMaxCount = (nBucketCount < m_Buckets.capacity()) ? max_item_count( nBucketCount << 1, nLoadFactor )
+                                                                                  : std::numeric_limits<size_t>::max();
+                m_nMaxItemCount.compare_exchange_strong( nMaxCount, nNewMaxCount, memory_model::memory_order_relaxed,
+                    memory_model::memory_order_relaxed );
+                m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, memory_model::memory_order_relaxed );
+            }
         }
 
         template <typename Q, typename Compare, typename Func>
-- 
2.34.1