cds/intrusive/striped_set/resizing_policy.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_INTRUSIVE_STRIPED_SET_RESIZING_POLICY_H
   4 #define CDSLIB_INTRUSIVE_STRIPED_SET_RESIZING_POLICY_H
   5
   6 #include <cds/opt/options.h>
   7
   8 namespace cds { namespace intrusive { namespace striped_set {
   9
  10     /// Load factor based resizing policy
  11     /** @ingroup cds_striped_resizing_policy
  12         When total item count in a container exceeds
  13         <tt>container.bucket_count() * LoadFactor</tt>
  14         then resizing is needed.
  15
  16         This policy is stateless.
  17
  18         The <tt>reset()</tt> function is called after the resizing is done.
  19         The function is intended for resetting internal state of the policy.
  20     */
  21     template <size_t LoadFactor>
  22     struct load_factor_resizing
  23     {
  24         /// Main policy operator returns \p true when resizing is needed
  25         template <typename Container, typename Bucket>
  26         bool operator ()(
  27             size_t nSize,                   ///< Current item count of \p container
  28             Container const& container,     ///< Container
  29             Bucket const& /*bucket*/        ///< reference to a container's bucket (not used)
  30         ) const
  31         {
  32             return nSize > container.bucket_count() * LoadFactor;
  33         }
  34
  35         /// Resets internal state of the policy (does nothing)
  36         void reset()
  37         {}
  38     };
  39
  40     /// Load factor based resizing policy, stateful specialization
  41     /** @ingroup cds_striped_resizing_policy
  42         This specialization allows to specify a load factor at runtime.
  43     */
  44     template <>
  45     struct load_factor_resizing<0>
  46     {
  47         ///@cond
  48         const size_t m_nLoadFactor;
  49         //@endcond
  50     public:
  51         /// Default ctor, load factor is 4
  52         load_factor_resizing()
  53             : m_nLoadFactor(4)
  54         {}
  55
  56         /// Ctor with explicitly defined \p nLoadFactor
  57         explicit load_factor_resizing( size_t nLoadFactor )
  58             : m_nLoadFactor( nLoadFactor )
  59         {}
  60
  61         /// Copy ctor
  62         load_factor_resizing( load_factor_resizing const& src )
  63             : m_nLoadFactor( src.m_nLoadFactor )
  64         {}
  65
  66         /// Move ctor
  67         load_factor_resizing( load_factor_resizing&& src )
  68             : m_nLoadFactor( src.m_nLoadFactor )
  69         {}
  70
  71         /// Main policy operator returns \p true when resizing is needed
  72         template <typename Container, typename Bucket>
  73         bool operator ()(
  74             size_t nSize,                   ///< Current item count of \p container
  75             Container const& container,     ///< Container
  76             Bucket const& /*bucket*/        ///< reference to a container's bucket (not used)
  77         )
  78         {
  79             return nSize > container.bucket_count() * m_nLoadFactor;
  80         }
  81
  82         /// Resets internal state of the policy (does nothing)
  83         void reset()
  84         {}
  85     };
  86
  87     /// Rational load factor resizing policy
  88     /** @ingroup cds_striped_resizing_policy
  89         When total item count in a container exceeds
  90         <tt>container.bucket_count() * Numerator / Denominator</tt>
  91         then resizing is needed.
  92
  93         This policy is stateless: \p Numerator and \p Denominator specifies in compile time as template arguments
  94     */
  95     template <size_t Numerator, size_t Denominator = 1>
  96     struct rational_load_factor_resizing
  97     {
  98         static_assert( Denominator != 0, "Denominator must not be zero" );
  99
 100         /// Main policy operator returns \p true when resizing is needed
 101         template <typename Container, typename Bucket>
 102         bool operator ()(
 103             size_t nSize,                   ///< Current item count of \p container
 104             Container const& container,     ///< Container
 105             Bucket const& /*bucket*/        ///< reference to a container's bucket (not used)
 106         ) const
 107         {
 108             return nSize * Denominator > container.bucket_count() * Numerator;
 109         }
 110
 111         /// Resets internal state of the policy (does nothing)
 112         void reset()
 113         {}
 114     };
 115
 116     /// Rational load factor resizing policy
 117     /** @ingroup cds_striped_resizing_policy
 118         When total item count in a container exceeds
 119         <tt>container.bucket_count() * Numerator / Denominator</tt>
 120         then resizing is needed.
 121
 122         This policy is stateful: \p Numerator and \p Denominator specifies in construction time.
 123     */
 124     template <size_t Denominator>
 125     struct rational_load_factor_resizing<0, Denominator>
 126     {
 127         ///@cond
 128         const size_t m_nNumerator;
 129         const size_t m_nDenominator;
 130         //@endcond
 131     public:
 132         /// Default ctor, load factor is 1/2
 133         rational_load_factor_resizing()
 134             : m_nNumerator(1), m_nDenominator(2)
 135         {}
 136
 137         /// Ctor with explicitly defined \p nLoadFactor
 138         rational_load_factor_resizing( size_t nNumerator, size_t nDenominator )
 139             : m_nNumerator( nNumerator ), m_nDenominator( nDenominator )
 140         {}
 141
 142         /// Copy ctor
 143         rational_load_factor_resizing( rational_load_factor_resizing const& src )
 144             : m_nNumerator( src.m_nNumerator ), m_nDenominator( src.m_nDenominator )
 145         {}
 146
 147         /// Move ctor
 148         rational_load_factor_resizing( rational_load_factor_resizing&& src )
 149             : m_nNumerator( src.m_nNumerator ), m_nDenominator( src.m_nDenominator )
 150         {}
 151
 152         /// Main policy operator returns \p true when resizing is needed
 153         template <typename Container, typename Bucket>
 154         bool operator ()(
 155             size_t nSize,                   ///< Current item count of \p container
 156             Container const& container,     ///< Container
 157             Bucket const& /*bucket*/        ///< reference to a container's bucket (not used)
 158         )
 159         {
 160             return nSize * m_nDenominator > container.bucket_count() * m_nNumerator;
 161         }
 162
 163         /// Resets internal state of the policy (does nothing)
 164         void reset()
 165         {}
 166     };
 167
 168     /// Single bucket threshold resizing policy
 169     /** @ingroup cds_striped_resizing_policy
 170         If any single bucket size exceeds the global \p Threshold then resizing is needed.
 171
 172         This policy is stateless.
 173     */
 174     template <size_t Threshold>
 175     struct single_bucket_size_threshold
 176     {
 177         /// Main policy operator returns \p true when resizing is needed
 178         template <typename Container, typename Bucket>
 179         bool operator ()(
 180             size_t /*nSize*/,                   ///< Current item count of \p container (not used)
 181             Container const& /*container*/,     ///< Container (not used)
 182             Bucket const& bucket                ///< reference to a container's bucket
 183             ) const
 184         {
 185             return bucket.size() > Threshold;
 186         }
 187
 188         /// Resets internal state of the policy (does nothing)
 189         void reset()
 190         {}
 191     };
 192
 193
 194     /// Single bucket threshold resizing policy, stateful specialization
 195     /** @ingroup cds_striped_resizing_policy
 196         This specialization allows to specify and modify a threshold at runtime.
 197     */
 198     template <>
 199     struct single_bucket_size_threshold<0>
 200     {
 201         size_t  m_nThreshold    ;   ///< The bucket size threshold
 202
 203         /// Default ctor, the threshold is 4
 204         single_bucket_size_threshold()
 205             : m_nThreshold(4)
 206         {}
 207
 208         /// Ctor with explicitly defined \p nThreshold
 209         explicit single_bucket_size_threshold( size_t nThreshold )
 210             : m_nThreshold( nThreshold )
 211         {}
 212
 213         /// Copy ctor
 214         single_bucket_size_threshold( single_bucket_size_threshold const& src )
 215             : m_nThreshold( src.m_nThreshold )
 216         {}
 217
 218         /// Move ctor
 219         single_bucket_size_threshold( single_bucket_size_threshold&& src )
 220             : m_nThreshold( src.m_nThreshold )
 221         {}
 222
 223         /// Main policy operator returns \p true when resizing is needed
 224         template <typename Container, typename Bucket>
 225         bool operator ()(
 226             size_t /*nSize*/,                   ///< Current item count of \p container (not used)
 227             Container const& /*container*/,     ///< Container (not used)
 228             Bucket const& bucket                ///< reference to a container's bucket
 229             ) const
 230         {
 231             return bucket.size() > m_nThreshold;
 232         }
 233
 234         /// Resets internal state of the policy (does nothing)
 235         void reset()
 236         {}
 237     };
 238
 239     /// Dummy resizing policy
 240     /** @ingroup cds_striped_resizing_policy
 241         This policy is dummy and always returns \p false that means no resizing is needed.
 242
 243         This policy is stateless.
 244     */
 245     struct no_resizing
 246     {
 247         /// Main policy operator always returns \p false
 248         template <typename Container, typename Bucket>
 249         bool operator ()(
 250             size_t /*nSize*/,                   ///< Current item count of \p container (not used)
 251             Container const& /*container*/,     ///< Container (not used)
 252             Bucket const& /*bucket*/            ///< reference to a container's bucket (not used)
 253         ) const
 254         {
 255             return false;
 256         }
 257
 258         /// Resets internal state of the policy (does nothing)
 259         void reset()
 260         {}
 261     };
 262
 263 }}} // namespace cds::intrusive::striped_set
 264
 265 #endif // #define CDSLIB_INTRUSIVE_STRIPED_SET_RESIZING_POLICY_H