cds/intrusive/striped_set/resizing_policy.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_INTRUSIVE_STRIPED_SET_RESIZING_POLICY_H
  32 #define CDSLIB_INTRUSIVE_STRIPED_SET_RESIZING_POLICY_H
  33
  34 #include <cds/opt/options.h>
  35
  36 namespace cds { namespace intrusive { namespace striped_set {
  37
  38     /// Load factor based resizing policy
  39     /** @ingroup cds_striped_resizing_policy
  40         When total item count in a container exceeds
  41         <tt>container.bucket_count() * LoadFactor</tt>
  42         then resizing is needed.
  43
  44         This policy is stateless.
  45
  46         The <tt>reset()</tt> function is called after the resizing is done.
  47         The function is intended for resetting internal state of the policy.
  48     */
  49     template <size_t LoadFactor>
  50     struct load_factor_resizing
  51     {
  52         /// Main policy operator returns \p true when resizing is needed
  53         template <typename Container, typename Bucket>
  54         bool operator ()(
  55             size_t nSize,                   ///< Current item count of \p container
  56             Container const& container,     ///< Container
  57             Bucket const& /*bucket*/        ///< reference to a container's bucket (not used)
  58         ) const
  59         {
  60             return nSize > container.bucket_count() * LoadFactor;
  61         }
  62
  63         /// Resets internal state of the policy (does nothing)
  64         void reset()
  65         {}
  66     };
  67
  68     /// Load factor based resizing policy, stateful specialization
  69     /** @ingroup cds_striped_resizing_policy
  70         This specialization allows to specify a load factor at runtime.
  71     */
  72     template <>
  73     struct load_factor_resizing<0>
  74     {
  75         ///@cond
  76         const size_t m_nLoadFactor;
  77         //@endcond
  78     public:
  79         /// Default ctor, load factor is 4
  80         load_factor_resizing()
  81             : m_nLoadFactor(4)
  82         {}
  83
  84         /// Ctor with explicitly defined \p nLoadFactor
  85         explicit load_factor_resizing( size_t nLoadFactor )
  86             : m_nLoadFactor( nLoadFactor )
  87         {}
  88
  89         /// Copy ctor
  90         load_factor_resizing( load_factor_resizing const& src )
  91             : m_nLoadFactor( src.m_nLoadFactor )
  92         {}
  93
  94         /// Move ctor
  95         load_factor_resizing( load_factor_resizing&& src )
  96             : m_nLoadFactor( src.m_nLoadFactor )
  97         {}
  98
  99         /// Main policy operator returns \p true when resizing is needed
 100         template <typename Container, typename Bucket>
 101         bool operator ()(
 102             size_t nSize,                   ///< Current item count of \p container
 103             Container const& container,     ///< Container
 104             Bucket const& /*bucket*/        ///< reference to a container's bucket (not used)
 105         )
 106         {
 107             return nSize > container.bucket_count() * m_nLoadFactor;
 108         }
 109
 110         /// Resets internal state of the policy (does nothing)
 111         void reset()
 112         {}
 113     };
 114
 115     /// Rational load factor resizing policy
 116     /** @ingroup cds_striped_resizing_policy
 117         When total item count in a container exceeds
 118         <tt>container.bucket_count() * Numerator / Denominator</tt>
 119         then resizing is needed.
 120
 121         This policy is stateless: \p Numerator and \p Denominator specifies in compile time as template arguments
 122     */
 123     template <size_t Numerator, size_t Denominator = 1>
 124     struct rational_load_factor_resizing
 125     {
 126         static_assert( Denominator != 0, "Denominator must not be zero" );
 127
 128         /// Main policy operator returns \p true when resizing is needed
 129         template <typename Container, typename Bucket>
 130         bool operator ()(
 131             size_t nSize,                   ///< Current item count of \p container
 132             Container const& container,     ///< Container
 133             Bucket const& /*bucket*/        ///< reference to a container's bucket (not used)
 134         ) const
 135         {
 136             return nSize * Denominator > container.bucket_count() * Numerator;
 137         }
 138
 139         /// Resets internal state of the policy (does nothing)
 140         void reset()
 141         {}
 142     };
 143
 144     /// Rational load factor resizing policy
 145     /** @ingroup cds_striped_resizing_policy
 146         When total item count in a container exceeds
 147         <tt>container.bucket_count() * Numerator / Denominator</tt>
 148         then resizing is needed.
 149
 150         This policy is stateful: \p Numerator and \p Denominator specifies in construction time.
 151     */
 152     template <size_t Denominator>
 153     struct rational_load_factor_resizing<0, Denominator>
 154     {
 155         ///@cond
 156         const size_t m_nNumerator;
 157         const size_t m_nDenominator;
 158         //@endcond
 159     public:
 160         /// Default ctor, load factor is 1/2
 161         rational_load_factor_resizing()
 162             : m_nNumerator(1), m_nDenominator(2)
 163         {}
 164
 165         /// Ctor with explicitly defined \p nLoadFactor
 166         rational_load_factor_resizing( size_t nNumerator, size_t nDenominator )
 167             : m_nNumerator( nNumerator ), m_nDenominator( nDenominator )
 168         {}
 169
 170         /// Copy ctor
 171         rational_load_factor_resizing( rational_load_factor_resizing const& src )
 172             : m_nNumerator( src.m_nNumerator ), m_nDenominator( src.m_nDenominator )
 173         {}
 174
 175         /// Move ctor
 176         rational_load_factor_resizing( rational_load_factor_resizing&& src )
 177             : m_nNumerator( src.m_nNumerator ), m_nDenominator( src.m_nDenominator )
 178         {}
 179
 180         /// Main policy operator returns \p true when resizing is needed
 181         template <typename Container, typename Bucket>
 182         bool operator ()(
 183             size_t nSize,                   ///< Current item count of \p container
 184             Container const& container,     ///< Container
 185             Bucket const& /*bucket*/        ///< reference to a container's bucket (not used)
 186         )
 187         {
 188             return nSize * m_nDenominator > container.bucket_count() * m_nNumerator;
 189         }
 190
 191         /// Resets internal state of the policy (does nothing)
 192         void reset()
 193         {}
 194     };
 195
 196     /// Single bucket threshold resizing policy
 197     /** @ingroup cds_striped_resizing_policy
 198         If any single bucket size exceeds the global \p Threshold then resizing is needed.
 199
 200         This policy is stateless.
 201     */
 202     template <size_t Threshold>
 203     struct single_bucket_size_threshold
 204     {
 205         /// Main policy operator returns \p true when resizing is needed
 206         template <typename Container, typename Bucket>
 207         bool operator ()(
 208             size_t /*nSize*/,                   ///< Current item count of \p container (not used)
 209             Container const& /*container*/,     ///< Container (not used)
 210             Bucket const& bucket                ///< reference to a container's bucket
 211             ) const
 212         {
 213             return bucket.size() > Threshold;
 214         }
 215
 216         /// Resets internal state of the policy (does nothing)
 217         void reset()
 218         {}
 219     };
 220
 221
 222     /// Single bucket threshold resizing policy, stateful specialization
 223     /** @ingroup cds_striped_resizing_policy
 224         This specialization allows to specify and modify a threshold at runtime.
 225     */
 226     template <>
 227     struct single_bucket_size_threshold<0>
 228     {
 229         size_t  m_nThreshold    ;   ///< The bucket size threshold
 230
 231         /// Default ctor, the threshold is 4
 232         single_bucket_size_threshold()
 233             : m_nThreshold(4)
 234         {}
 235
 236         /// Ctor with explicitly defined \p nThreshold
 237         explicit single_bucket_size_threshold( size_t nThreshold )
 238             : m_nThreshold( nThreshold )
 239         {}
 240
 241         /// Copy ctor
 242         single_bucket_size_threshold( single_bucket_size_threshold const& src )
 243             : m_nThreshold( src.m_nThreshold )
 244         {}
 245
 246         /// Move ctor
 247         single_bucket_size_threshold( single_bucket_size_threshold&& src )
 248             : m_nThreshold( src.m_nThreshold )
 249         {}
 250
 251         /// Main policy operator returns \p true when resizing is needed
 252         template <typename Container, typename Bucket>
 253         bool operator ()(
 254             size_t /*nSize*/,                   ///< Current item count of \p container (not used)
 255             Container const& /*container*/,     ///< Container (not used)
 256             Bucket const& bucket                ///< reference to a container's bucket
 257             ) const
 258         {
 259             return bucket.size() > m_nThreshold;
 260         }
 261
 262         /// Resets internal state of the policy (does nothing)
 263         void reset()
 264         {}
 265     };
 266
 267     /// Dummy resizing policy
 268     /** @ingroup cds_striped_resizing_policy
 269         This policy is dummy and always returns \p false that means no resizing is needed.
 270
 271         This policy is stateless.
 272     */
 273     struct no_resizing
 274     {
 275         /// Main policy operator always returns \p false
 276         template <typename Container, typename Bucket>
 277         bool operator ()(
 278             size_t /*nSize*/,                   ///< Current item count of \p container (not used)
 279             Container const& /*container*/,     ///< Container (not used)
 280             Bucket const& /*bucket*/            ///< reference to a container's bucket (not used)
 281         ) const
 282         {
 283             return false;
 284         }
 285
 286         /// Resets internal state of the policy (does nothing)
 287         void reset()
 288         {}
 289     };
 290
 291 }}} // namespace cds::intrusive::striped_set
 292
 293 #endif // #define CDSLIB_INTRUSIVE_STRIPED_SET_RESIZING_POLICY_H