bitmac/
grow_strategy.rs

1use crate::ResizeError;
2
3/// Determines strategy of bitmap container growth.
4pub trait GrowStrategy {
5    /// Will be called when the bitmap needs to extend its container.
6    /// New length always >= minimal required length of container.
7    ///
8    /// If returns `Err(_)` then container is not resized.
9    fn try_grow(
10        &mut self,
11        min_req_len: MinimumRequiredLength,
12        old_len: usize,
13        bit_idx: usize,
14    ) -> Result<FinalLength, ResizeError>;
15
16    /// Checks if the container should grow if the changing bit is exceeding container's length
17    /// and its new state is `0` (`false`)
18    ///
19    /// For performance reasons, all bits outside of the container access are
20    /// considered to be `0`. The default behavior is to return `false`.
21    fn is_force_grow(&self) -> bool {
22        false
23    }
24}
25
26/// Increases the size of the container to the minimum required size.
27///
28/// Example:
29/// ```
30/// use bitmac::grow_strategy::{GrowStrategy, MinimumRequiredStrategy, MinimumRequiredLength};
31/// let mut s = MinimumRequiredStrategy;
32/// assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(1), 0, 0).unwrap().value(), 1);
33/// assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(2), 0, 10).unwrap().value(), 2);
34/// assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(3), 0, 23).unwrap().value(), 3);
35/// assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(4), 3, 24).unwrap().value(), 4);
36/// assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(5), 3, 35).unwrap().value(), 5);
37/// assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(6), 3, 47).unwrap().value(), 6);
38/// assert!(!s.is_force_grow());
39/// ```
40#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, Hash)]
41pub struct MinimumRequiredStrategy;
42
43impl GrowStrategy for MinimumRequiredStrategy {
44    fn try_grow(
45        &mut self,
46        min_req_len: MinimumRequiredLength,
47        _old_len: usize,
48        _bit_idx: usize,
49    ) -> Result<FinalLength, ResizeError> {
50        Ok(min_req_len.finalize())
51    }
52}
53
54/// Increases the size of the container by a fixed increment.
55///
56/// Example:
57/// ```
58/// use bitmac::grow_strategy::{GrowStrategy, FixedStrategy, MinimumRequiredLength};
59/// let mut s = FixedStrategy(3);
60/// assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(1), 0, 0).unwrap().value(), 3);
61/// assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(2), 0, 10).unwrap().value(), 3);
62/// assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(3), 0, 23).unwrap().value(), 3);
63/// assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(4), 3, 24).unwrap().value(), 6);
64/// assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(5), 3, 35).unwrap().value(), 6);
65/// assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(6), 3, 47).unwrap().value(), 6);
66/// assert!(!s.is_force_grow());
67/// ```
68#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
69#[repr(transparent)]
70pub struct FixedStrategy(pub usize);
71
72impl GrowStrategy for FixedStrategy {
73    fn try_grow(
74        &mut self,
75        min_req_len: MinimumRequiredLength,
76        _old_len: usize,
77        _bit_idx: usize,
78    ) -> Result<FinalLength, ResizeError> {
79        if min_req_len.value() % self.0 == 0 {
80            Ok(min_req_len.finalize())
81        } else {
82            let rest = (min_req_len.value() / self.0 + 1) * self.0 - min_req_len.value();
83            Ok(min_req_len.advance_by(rest))
84        }
85    }
86}
87
88/// Increases the size of the container until the limit is reached.
89///
90/// Example:
91/// ```
92/// use bitmac::grow_strategy::{GrowStrategy, MinimumRequiredStrategy, LimitStrategy, MinimumRequiredLength};
93/// let mut s = LimitStrategy{
94///     strategy: MinimumRequiredStrategy,
95///     limit: 5,
96/// };
97/// assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(1), 0, 0).unwrap().value(), 1);
98/// assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(2), 0, 10).unwrap().value(), 2);
99/// assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(3), 0, 23).unwrap().value(), 3);
100/// assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(4), 3, 24).unwrap().value(), 4);
101/// assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(5), 3, 35).unwrap().value(), 5);
102/// assert!(s.try_grow(MinimumRequiredLength::new_unchecked(6), 3, 47).is_err());
103/// assert!(!s.is_force_grow());
104/// ```
105#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
106pub struct LimitStrategy<S> {
107    pub strategy: S,
108    pub limit: usize,
109}
110
111impl<S> GrowStrategy for LimitStrategy<S>
112where
113    S: GrowStrategy,
114{
115    fn try_grow(
116        &mut self,
117        min_req_len: MinimumRequiredLength,
118        old_len: usize,
119        bit_idx: usize,
120    ) -> Result<FinalLength, ResizeError> {
121        let final_length = self.strategy.try_grow(min_req_len, old_len, bit_idx)?;
122        if final_length.value() <= self.limit {
123            Ok(final_length)
124        } else {
125            Err(ResizeError::new(format!(
126                "the new size {} is over the limit {}",
127                final_length.value(),
128                self.limit
129            )))
130        }
131    }
132}
133
134/// Increases the size of the container despite new bit state is `0` (`false`).
135/// In other words `is_force_grow()` always returns `true`.
136///
137/// Example:
138/// ```
139/// use bitmac::grow_strategy::{GrowStrategy, MinimumRequiredStrategy, ForceGrowStrategy, MinimumRequiredLength};
140/// let mut s = ForceGrowStrategy(MinimumRequiredStrategy);
141/// assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(1), 0, 0).unwrap().value(), 1);
142/// assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(2), 0, 10).unwrap().value(), 2);
143/// assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(3), 0, 23).unwrap().value(), 3);
144/// assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(4), 3, 24).unwrap().value(), 4);
145/// assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(5), 3, 35).unwrap().value(), 5);
146/// assert!(s.is_force_grow());
147/// ```
148#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
149pub struct ForceGrowStrategy<S>(pub S);
150
151impl<S> GrowStrategy for ForceGrowStrategy<S>
152where
153    S: GrowStrategy,
154{
155    fn try_grow(
156        &mut self,
157        min_req_len: MinimumRequiredLength,
158        old_len: usize,
159        bit_idx: usize,
160    ) -> Result<FinalLength, ResizeError> {
161        self.0.try_grow(min_req_len, old_len, bit_idx)
162    }
163
164    fn is_force_grow(&self) -> bool {
165        true
166    }
167}
168
169/// Minimum required length of bitmap container for storing Nth bit.
170#[derive(Debug, Clone, Eq, PartialEq, Hash)]
171#[repr(transparent)]
172pub struct MinimumRequiredLength(pub(crate) usize);
173
174impl MinimumRequiredLength {
175    /// Increases length by `v` and finalizes it.
176    #[inline]
177    pub fn advance_by(self, v: usize) -> FinalLength {
178        FinalLength(self.0 + v)
179    }
180
181    /// Finalizes length and convert it to `FinalLength`.
182    #[inline]
183    pub fn finalize(self) -> FinalLength {
184        FinalLength(self.0)
185    }
186
187    /// Returns inner value.
188    #[inline]
189    pub fn value(&self) -> usize {
190        self.0
191    }
192
193    /// Creates `MinimumRequiredLength`. For testing and document purposes only.
194    #[doc(hidden)]
195    pub fn new_unchecked(v: usize) -> Self {
196        Self(v)
197    }
198}
199
200/// New bitmap container length.
201#[derive(Debug, Clone, Copy, Eq, PartialEq, Hash)]
202#[repr(transparent)]
203pub struct FinalLength(pub(crate) usize);
204
205impl FinalLength {
206    /// Returns inner value.
207    #[inline]
208    pub fn value(&self) -> usize {
209        self.0
210    }
211}
212
213#[cfg(test)]
214mod tests {
215    use super::*;
216
217    #[test]
218    #[rustfmt::skip]
219    fn test_minimal() {
220        let mut s = MinimumRequiredStrategy::default();
221        
222        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(1), 1, 0).unwrap().value(), 1);
223        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(1), 2, 0).unwrap().value(), 1);
224        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(1), 3, 0).unwrap().value(), 1);
225        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(1), 4, 0).unwrap().value(), 1);
226        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(1), 5, 0).unwrap().value(), 1);
227
228        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(2), 1, 0).unwrap().value(), 2);
229        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(2), 2, 0).unwrap().value(), 2);
230        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(2), 3, 0).unwrap().value(), 2);
231        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(2), 4, 0).unwrap().value(), 2);
232        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(2), 5, 0).unwrap().value(), 2);
233
234        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(3), 1, 0).unwrap().value(), 3);
235        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(3), 2, 0).unwrap().value(), 3);
236        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(3), 3, 0).unwrap().value(), 3);
237        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(3), 4, 0).unwrap().value(), 3);
238        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(3), 5, 0).unwrap().value(), 3);
239
240        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(21), 5, 0).unwrap().value(), 21);
241        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(25), 5, 0).unwrap().value(), 25);
242    }
243
244    #[test]
245    #[rustfmt::skip]
246    fn test_fixed() {
247        let mut s = FixedStrategy(3);
248
249        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(1), 1, 0).unwrap().value(), 3);
250        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(1), 2, 0).unwrap().value(), 3);
251        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(1), 3, 0).unwrap().value(), 3);
252        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(1), 4, 0).unwrap().value(), 3);
253        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(1), 5, 0).unwrap().value(), 3);
254
255        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(2), 1, 0).unwrap().value(), 3);
256        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(2), 2, 0).unwrap().value(), 3);
257        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(2), 3, 0).unwrap().value(), 3);
258        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(2), 4, 0).unwrap().value(), 3);
259        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(2), 5, 0).unwrap().value(), 3);
260
261        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(3), 1, 0).unwrap().value(), 3);
262        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(3), 2, 0).unwrap().value(), 3);
263        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(3), 3, 0).unwrap().value(), 3);
264        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(3), 4, 0).unwrap().value(), 3);
265        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(3), 5, 0).unwrap().value(), 3);
266
267        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(4), 1, 0).unwrap().value(), 6);
268        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(4), 2, 0).unwrap().value(), 6);
269        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(4), 3, 0).unwrap().value(), 6);
270        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(4), 4, 0).unwrap().value(), 6);
271        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(4), 5, 0).unwrap().value(), 6);
272
273        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(21), 5, 0).unwrap().value(), 21);
274        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(25), 5, 0).unwrap().value(), 27);
275    }
276
277    #[test]
278    #[rustfmt::skip]
279    fn test_limit() {
280        let mut s = LimitStrategy{ strategy: MinimumRequiredStrategy, limit: 3 };
281
282        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(1), 1, 0).unwrap().value(), 1);
283        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(1), 2, 0).unwrap().value(), 1);
284        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(1), 3, 0).unwrap().value(), 1);
285        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(1), 4, 0).unwrap().value(), 1);
286        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(1), 5, 0).unwrap().value(), 1);
287
288        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(2), 1, 0).unwrap().value(), 2);
289        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(2), 2, 0).unwrap().value(), 2);
290        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(2), 3, 0).unwrap().value(), 2);
291        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(2), 4, 0).unwrap().value(), 2);
292        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(2), 5, 0).unwrap().value(), 2);
293
294        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(3), 1, 0).unwrap().value(), 3);
295        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(3), 2, 0).unwrap().value(), 3);
296        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(3), 3, 0).unwrap().value(), 3);
297        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(3), 4, 0).unwrap().value(), 3);
298        assert_eq!(s.try_grow(MinimumRequiredLength::new_unchecked(3), 5, 0).unwrap().value(), 3);
299
300        assert!(s.try_grow(MinimumRequiredLength::new_unchecked(4), 1, 0).is_err());
301        assert!(s.try_grow(MinimumRequiredLength::new_unchecked(4), 2, 0).is_err());
302        assert!(s.try_grow(MinimumRequiredLength::new_unchecked(4), 3, 0).is_err());
303        assert!(s.try_grow(MinimumRequiredLength::new_unchecked(4), 4, 0).is_err());
304        assert!(s.try_grow(MinimumRequiredLength::new_unchecked(4), 5, 0).is_err());
305
306        assert!(s.try_grow(MinimumRequiredLength::new_unchecked(21), 5, 0).is_err());
307        assert!(s.try_grow(MinimumRequiredLength::new_unchecked(25), 5, 0).is_err());
308    }
309}
bitmac/grow_strategy.rs

bitmac/
grow_strategy.rs
