From: khizmax <libcds.dev@gmail.com>
Date: Fri, 24 Apr 2015 19:57:13 +0000 (+0300)
Subject: Fixed max bucket count error in SplitList
X-Git-Tag: v2.1.0~249^2~2
X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=commitdiff_plain;h=f0de9e874b77ebb9bd912f25063e3bab993873f5

Fixed max bucket count error in SplitList

Conflicts:
	cds/intrusive/split_list.h
---

diff --git a/cds/intrusive/split_list.h b/cds/intrusive/split_list.h
index 0288e703..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,17 +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,
-                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, 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..5eeb991f 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,
+                    atomics::memory_order_relaxed );
+                m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
+            }
         }
 
         //@endcond
diff --git a/cds/intrusive/split_list_rcu.h b/cds/intrusive/split_list_rcu.h
index 8deeb7ce..293489ff 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,
+                    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>