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     template <size_t Numerator, size_t Denominator = 1>
  88     struct rational_load_factor_resizing
  89     {
  90         static_assert( Denominator != 0, "Denominator must not be zero" );
  91
  92         /// Main policy operator returns \p true when resizing is needed
  93         template <typename Container, typename Bucket>
  94         bool operator ()(
  95             size_t nSize,                   ///< Current item count of \p container
  96             Container const& container,     ///< Container
  97             Bucket const& /*bucket*/        ///< reference to a container's bucket (not used)
  98         ) const
  99         {
 100             return nSize * Denominator > container.bucket_count() * Numerator;
 101         }
 102
 103         /// Resets internal state of the policy (does nothing)
 104         void reset()
 105         {}
 106     };
 107
 108     template <size_t Denominator>
 109     struct rational_load_factor_resizing<0, Denominator>
 110     {
 111         ///@cond
 112         const size_t m_nNumerator;
 113         const size_t m_nDenominator;
 114         //@endcond
 115     public:
 116         /// Default ctor, load factor is 1/2
 117         rational_load_factor_resizing()
 118             : m_nNumerator(1), m_nDenominator(2)
 119         {}
 120
 121         /// Ctor with explicitly defined \p nLoadFactor
 122         rational_load_factor_resizing( size_t nNumerator, size_t nDenominator )
 123             : m_nNumerator( nNumerator ), m_nDenominator( nDenominator )
 124         {}
 125
 126         /// Copy ctor
 127         rational_load_factor_resizing( rational_load_factor_resizing const& src )
 128             : m_nNumerator( src.m_nNumerator ), m_nDenominator( src.m_nDenominator )
 129         {}
 130
 131         /// Move ctor
 132         rational_load_factor_resizing( rational_load_factor_resizing&& src )
 133             : m_nNumerator( src.m_nNumerator ), m_nDenominator( src.m_nDenominator )
 134         {}
 135
 136         /// Main policy operator returns \p true when resizing is needed
 137         template <typename Container, typename Bucket>
 138         bool operator ()(
 139             size_t nSize,                   ///< Current item count of \p container
 140             Container const& container,     ///< Container
 141             Bucket const& /*bucket*/        ///< reference to a container's bucket (not used)
 142         )
 143         {
 144             return nSize * m_nDenominator > container.bucket_count() * m_nNumerator;
 145         }
 146
 147         /// Resets internal state of the policy (does nothing)
 148         void reset()
 149         {}
 150     };
 151
 152     /// Single bucket threshold resizing policy
 153     /** @ingroup cds_striped_resizing_policy
 154         If any single bucket size exceeds the global \p Threshold then resizing is needed.
 155
 156         This policy is stateless.
 157     */
 158     template <size_t Threshold>
 159     struct single_bucket_size_threshold
 160     {
 161         /// Main policy operator returns \p true when resizing is needed
 162         template <typename Container, typename Bucket>
 163         bool operator ()(
 164             size_t /*nSize*/,                   ///< Current item count of \p container (not used)
 165             Container const& /*container*/,     ///< Container (not used)
 166             Bucket const& bucket                ///< reference to a container's bucket
 167             ) const
 168         {
 169             return bucket.size() > Threshold;
 170         }
 171
 172         /// Resets internal state of the policy (does nothing)
 173         void reset()
 174         {}
 175     };
 176
 177
 178     /// Single bucket threshold resizing policy, stateful specialization
 179     /** @ingroup cds_striped_resizing_policy
 180         This specialization allows to specify and modify a threshold at runtime.
 181     */
 182     template <>
 183     struct single_bucket_size_threshold<0>
 184     {
 185         size_t  m_nThreshold    ;   ///< The bucket size threshold
 186
 187         /// Default ctor, the threshold is 4
 188         single_bucket_size_threshold()
 189             : m_nThreshold(4)
 190         {}
 191
 192         /// Ctor with explicitly defined \p nThreshold
 193         explicit single_bucket_size_threshold( size_t nThreshold )
 194             : m_nThreshold( nThreshold )
 195         {}
 196
 197         /// Copy ctor
 198         single_bucket_size_threshold( single_bucket_size_threshold const& src )
 199             : m_nThreshold( src.m_nThreshold )
 200         {}
 201
 202         /// Move ctor
 203         single_bucket_size_threshold( single_bucket_size_threshold&& src )
 204             : m_nThreshold( src.m_nThreshold )
 205         {}
 206
 207         /// Main policy operator returns \p true when resizing is needed
 208         template <typename Container, typename Bucket>
 209         bool operator ()(
 210             size_t /*nSize*/,                   ///< Current item count of \p container (not used)
 211             Container const& /*container*/,     ///< Container (not used)
 212             Bucket const& bucket                ///< reference to a container's bucket
 213             ) const
 214         {
 215             return bucket.size() > m_nThreshold;
 216         }
 217
 218         /// Resets internal state of the policy (does nothing)
 219         void reset()
 220         {}
 221     };
 222
 223     /// Dummy resizing policy
 224     /** @ingroup cds_striped_resizing_policy
 225         This policy is dummy and always returns \p false that means no resizing is needed.
 226
 227         This policy is stateless.
 228     */
 229     struct no_resizing
 230     {
 231         /// Main policy operator always returns \p false
 232         template <typename Container, typename Bucket>
 233         bool operator ()(
 234             size_t /*nSize*/,                   ///< Current item count of \p container (not used)
 235             Container const& /*container*/,     ///< Container (not used)
 236             Bucket const& /*bucket*/            ///< reference to a container's bucket (not used)
 237         ) const
 238         {
 239             return false;
 240         }
 241
 242         /// Resets internal state of the policy (does nothing)
 243         void reset()
 244         {}
 245     };
 246
 247 }}} // namespace cds::intrusive::striped_set
 248
 249 #endif // #define CDSLIB_INTRUSIVE_STRIPED_SET_RESIZING_POLICY_H