From e0ce332808dd028e0c0554f52aa04e9742e29286 Mon Sep 17 00:00:00 2001
From: Mike Krinkin <krinkin.m.u@gmail.com>
Date: Sun, 26 Apr 2015 10:27:01 +0300
Subject: [PATCH] Add rational load factor resizing policy

Add separate rational load factor resizing policy so that users
don't need to pay for additional multiplication if they don't need
it. The rational load factor resizing allows to exchange memory for
a bit of performance (about 5-10 %).
---
 cds/container/striped_set/adapter.h         |  1 +
 cds/intrusive/striped_set/resizing_policy.h | 64 +++++++++++++++++++++
 2 files changed, 65 insertions(+)

diff --git a/cds/container/striped_set/adapter.h b/cds/container/striped_set/adapter.h
index f4f56b8d..72b78908 100644
--- a/cds/container/striped_set/adapter.h
+++ b/cds/container/striped_set/adapter.h
@@ -180,6 +180,7 @@ namespace cds { namespace container {
         using cds::intrusive::striped_set::adapted_container;
 
         using cds::intrusive::striped_set::load_factor_resizing;
+        using cds::intrusive::striped_set::rational_load_factor_resizing;
         using cds::intrusive::striped_set::single_bucket_size_threshold;
         using cds::intrusive::striped_set::no_resizing;
 
diff --git a/cds/intrusive/striped_set/resizing_policy.h b/cds/intrusive/striped_set/resizing_policy.h
index 15cb293d..43cb3f3c 100644
--- a/cds/intrusive/striped_set/resizing_policy.h
+++ b/cds/intrusive/striped_set/resizing_policy.h
@@ -84,6 +84,70 @@ namespace cds { namespace intrusive { namespace striped_set {
         {}
     };
 
+    template <size_t Numerator, size_t Denominator = 1>
+    struct rational_load_factor_resizing
+    {
+        static_assert( Denominator != 0, "Denominator must not be zero" );
+
+        /// Main policy operator returns \p true when resizing is needed
+        template <typename Container, typename Bucket>
+        bool operator ()(
+            size_t nSize,                   ///< Current item count of \p container
+            Container const& container,     ///< Container
+            Bucket const& /*bucket*/        ///< reference to a container's bucket (not used)
+        ) const
+        {
+            return nSize * Denominator > container.bucket_count() * Numerator;
+        }
+
+        /// Resets internal state of the policy (does nothing)
+        void reset()
+        {}
+    };
+
+    template <size_t Denominator>
+    struct rational_load_factor_resizing<0, Denominator>
+    {
+        ///@cond
+        const size_t m_nNumerator;
+        const size_t m_nDenominator;
+        //@endcond
+    public:
+        /// Default ctor, load factor is 1/2
+        rational_load_factor_resizing()
+            : m_nNumerator(1), m_nDenominator(2)
+        {}
+
+        /// Ctor with explicitly defined \p nLoadFactor
+        rational_load_factor_resizing( size_t nNumerator, size_t nDenominator )
+            : m_nNumerator( nNumerator ), m_nDenominator( nDenominator )
+        {}
+
+        /// Copy ctor
+        rational_load_factor_resizing( rational_load_factor_resizing const& src )
+            : m_nNumerator( src.m_nNumerator ), m_nDenominator( src.m_nDenominator )
+        {}
+
+        /// Move ctor
+        rational_load_factor_resizing( rational_load_factor_resizing&& src )
+            : m_nNumerator( src.m_nNumerator ), m_nDenominator( src.m_nDenominator )
+        {}
+
+        /// Main policy operator returns \p true when resizing is needed
+        template <typename Container, typename Bucket>
+        bool operator ()(
+            size_t nSize,                   ///< Current item count of \p container
+            Container const& container,     ///< Container
+            Bucket const& /*bucket*/        ///< reference to a container's bucket (not used)
+        )
+        {
+            return nSize * m_nDenominator > container.bucket_count() * m_nNumerator;
+        }
+
+        /// Resets internal state of the policy (does nothing)
+        void reset()
+        {}
+    };
 
     /// Single bucket threshold resizing policy
     /** @ingroup cds_striped_resizing_policy
-- 
2.34.1