2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
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.
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.
31 #ifndef CDSLIB_INTRUSIVE_STRIPED_SET_RESIZING_POLICY_H
32 #define CDSLIB_INTRUSIVE_STRIPED_SET_RESIZING_POLICY_H
34 #include <cds/opt/options.h>
36 namespace cds { namespace intrusive { namespace striped_set {
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.
44 This policy is stateless.
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.
49 template <size_t LoadFactor>
50 struct load_factor_resizing
52 /// Main policy operator returns \p true when resizing is needed
53 template <typename Container, typename Bucket>
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)
60 return nSize > container.bucket_count() * LoadFactor;
63 /// Resets internal state of the policy (does nothing)
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.
73 struct load_factor_resizing<0>
76 const size_t m_nLoadFactor;
79 /// Default ctor, load factor is 4
80 load_factor_resizing()
84 /// Ctor with explicitly defined \p nLoadFactor
85 explicit load_factor_resizing( size_t nLoadFactor )
86 : m_nLoadFactor( nLoadFactor )
90 load_factor_resizing( load_factor_resizing const& src )
91 : m_nLoadFactor( src.m_nLoadFactor )
95 load_factor_resizing( load_factor_resizing&& src )
96 : m_nLoadFactor( src.m_nLoadFactor )
99 /// Main policy operator returns \p true when resizing is needed
100 template <typename Container, typename Bucket>
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)
107 return nSize > container.bucket_count() * m_nLoadFactor;
110 /// Resets internal state of the policy (does nothing)
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.
121 This policy is stateless: \p Numerator and \p Denominator specifies in compile time as template arguments
123 template <size_t Numerator, size_t Denominator = 1>
124 struct rational_load_factor_resizing
126 static_assert( Denominator != 0, "Denominator must not be zero" );
128 /// Main policy operator returns \p true when resizing is needed
129 template <typename Container, typename Bucket>
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)
136 return nSize * Denominator > container.bucket_count() * Numerator;
139 /// Resets internal state of the policy (does nothing)
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.
150 This policy is stateful: \p Numerator and \p Denominator specifies in construction time.
152 template <size_t Denominator>
153 struct rational_load_factor_resizing<0, Denominator>
156 const size_t m_nNumerator;
157 const size_t m_nDenominator;
160 /// Default ctor, load factor is 1/2
161 rational_load_factor_resizing()
162 : m_nNumerator(1), m_nDenominator(2)
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 )
171 rational_load_factor_resizing( rational_load_factor_resizing const& src )
172 : m_nNumerator( src.m_nNumerator ), m_nDenominator( src.m_nDenominator )
176 rational_load_factor_resizing( rational_load_factor_resizing&& src )
177 : m_nNumerator( src.m_nNumerator ), m_nDenominator( src.m_nDenominator )
180 /// Main policy operator returns \p true when resizing is needed
181 template <typename Container, typename Bucket>
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)
188 return nSize * m_nDenominator > container.bucket_count() * m_nNumerator;
191 /// Resets internal state of the policy (does nothing)
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.
200 This policy is stateless.
202 template <size_t Threshold>
203 struct single_bucket_size_threshold
205 /// Main policy operator returns \p true when resizing is needed
206 template <typename Container, typename Bucket>
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
213 return bucket.size() > Threshold;
216 /// Resets internal state of the policy (does nothing)
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.
227 struct single_bucket_size_threshold<0>
229 size_t m_nThreshold ; ///< The bucket size threshold
231 /// Default ctor, the threshold is 4
232 single_bucket_size_threshold()
236 /// Ctor with explicitly defined \p nThreshold
237 explicit single_bucket_size_threshold( size_t nThreshold )
238 : m_nThreshold( nThreshold )
242 single_bucket_size_threshold( single_bucket_size_threshold const& src )
243 : m_nThreshold( src.m_nThreshold )
247 single_bucket_size_threshold( single_bucket_size_threshold&& src )
248 : m_nThreshold( src.m_nThreshold )
251 /// Main policy operator returns \p true when resizing is needed
252 template <typename Container, typename Bucket>
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
259 return bucket.size() > m_nThreshold;
262 /// Resets internal state of the policy (does nothing)
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.
271 This policy is stateless.
275 /// Main policy operator always returns \p false
276 template <typename Container, typename Bucket>
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)
286 /// Resets internal state of the policy (does nothing)
291 }}} // namespace cds::intrusive::striped_set
293 #endif // #define CDSLIB_INTRUSIVE_STRIPED_SET_RESIZING_POLICY_H