orx_split_vec/growth/linear/
linear_growth.rs

1use super::constants::FIXED_CAPACITIES;
2use crate::growth::growth_trait::{Growth, GrowthWithConstantTimeAccess};
3use crate::{Fragment, SplitVec};
4use alloc::string::String;
5use orx_pseudo_default::PseudoDefault;
6
7/// Strategy which allows the split vector to grow linearly.
8///
9/// In other words, each new fragment will have equal capacity,
10/// which is equal to the capacity of the first fragment.
11///
12/// # Examples
13///
14/// ```
15/// use orx_split_vec::*;
16///
17/// // SplitVec<usize, Linear>
18/// let mut vec = SplitVec::with_linear_growth(4);
19///
20/// assert_eq!(1, vec.fragments().len());
21/// assert_eq!(Some(16), vec.fragments().first().map(|f| f.capacity()));
22/// assert_eq!(Some(0), vec.fragments().first().map(|f| f.len()));
23///
24/// // push 160 elements
25/// for i in 0..10 * 16 {
26///     vec.push(i);
27/// }
28///
29/// assert_eq!(10, vec.fragments().len());
30/// for fragment in vec.fragments() {
31///     assert_eq!(16, fragment.len());
32///     assert_eq!(16, fragment.capacity());
33/// }
34///
35/// // push the 161-st element
36/// vec.push(42);
37/// assert_eq!(11, vec.fragments().len());
38/// assert_eq!(Some(16), vec.fragments().last().map(|f| f.capacity()));
39/// assert_eq!(Some(1), vec.fragments().last().map(|f| f.len()));
40/// ```
41#[derive(Debug, Clone, PartialEq)]
42pub struct Linear {
43    constant_fragment_capacity_exponent: usize,
44    constant_fragment_capacity: usize,
45}
46
47impl Linear {
48    /// Creates a linear growth where each fragment will have a capacity of `2 ^ constant_fragment_capacity_exponent`.
49    ///
50    /// # Panics
51    ///
52    /// Panics if `constant_fragment_capacity_exponent` is zero or `constant_fragment_capacity_exponent >= MAX_EXPONENT` where `MAX_EXPONENT` is:
53    ///
54    /// * 29 in 32-bit targets,
55    /// * 32 in 64-bit.
56    pub fn new(constant_fragment_capacity_exponent: usize) -> Self {
57        assert!(
58            constant_fragment_capacity_exponent > 0
59                && constant_fragment_capacity_exponent < FIXED_CAPACITIES.len(),
60            "constant_fragment_capacity_exponent must be within 1..32 (1..29) for 64-bit (32-bit) platforms."
61        );
62        let constant_fragment_capacity = FIXED_CAPACITIES[constant_fragment_capacity_exponent];
63        Self {
64            constant_fragment_capacity_exponent,
65            constant_fragment_capacity,
66        }
67    }
68}
69
70impl PseudoDefault for Linear {
71    fn pseudo_default() -> Self {
72        Self::new(10)
73    }
74}
75
76impl Growth for Linear {
77    #[inline(always)]
78    fn new_fragment_capacity_from(
79        &self,
80        _fragment_capacities: impl ExactSizeIterator<Item = usize>,
81    ) -> usize {
82        self.constant_fragment_capacity
83    }
84
85    #[inline(always)]
86    fn get_fragment_and_inner_indices<T>(
87        &self,
88        vec_len: usize,
89        _fragments: &[Fragment<T>],
90        element_index: usize,
91    ) -> Option<(usize, usize)> {
92        match element_index < vec_len {
93            true => Some(self.get_fragment_and_inner_indices_unchecked(element_index)),
94            false => None,
95        }
96    }
97
98    /// ***O(1)*** Returns a pointer to the `index`-th element of the split vector of the `fragments`.
99    ///
100    /// Returns `None` if `index`-th position does not belong to the split vector; i.e., if `index` is out of cumulative capacity of fragments.
101    ///
102    /// # Safety
103    ///
104    /// This method allows to write to a memory which is greater than the split vector's length.
105    /// On the other hand, it will never return a pointer to a memory location that the vector does not own.
106    #[inline(always)]
107    fn get_ptr<T>(&self, fragments: &[Fragment<T>], index: usize) -> Option<*const T> {
108        <Self as GrowthWithConstantTimeAccess>::get_ptr(self, fragments, index)
109    }
110
111    /// ***O(1)*** Returns a mutable reference to the `index`-th element of the split vector of the `fragments`.
112    ///
113    /// Returns `None` if `index`-th position does not belong to the split vector; i.e., if `index` is out of cumulative capacity of fragments.
114    ///
115    /// # Safety
116    ///
117    /// This method allows to write to a memory which is greater than the split vector's length.
118    /// On the other hand, it will never return a pointer to a memory location that the vector does not own.
119    #[inline(always)]
120    fn get_ptr_mut<T>(&self, fragments: &mut [Fragment<T>], index: usize) -> Option<*mut T> {
121        <Self as GrowthWithConstantTimeAccess>::get_ptr_mut(self, fragments, index)
122    }
123
124    /// ***O(1)*** Returns a mutable reference to the `index`-th element of the split vector of the `fragments`
125    /// together with the index of the fragment that the element belongs to
126    /// and index of the element withing the respective fragment.
127    ///
128    /// Returns `None` if `index`-th position does not belong to the split vector; i.e., if `index` is out of cumulative capacity of fragments.
129    ///
130    /// # Safety
131    ///
132    /// This method allows to write to a memory which is greater than the split vector's length.
133    /// On the other hand, it will never return a pointer to a memory location that the vector does not own.
134    fn get_ptr_mut_and_indices<T>(
135        &self,
136        fragments: &mut [Fragment<T>],
137        index: usize,
138    ) -> Option<(*mut T, usize, usize)> {
139        <Self as GrowthWithConstantTimeAccess>::get_ptr_mut_and_indices(self, fragments, index)
140    }
141
142    fn maximum_concurrent_capacity<T>(
143        &self,
144        fragments: &[Fragment<T>],
145        fragments_capacity: usize,
146    ) -> usize {
147        assert!(fragments_capacity >= fragments.len());
148
149        fragments_capacity * self.constant_fragment_capacity
150    }
151
152    fn required_fragments_len<T>(
153        &self,
154        _: &[Fragment<T>],
155        maximum_capacity: usize,
156    ) -> Result<usize, String> {
157        let num_full_fragments = maximum_capacity / self.constant_fragment_capacity;
158        let remainder = maximum_capacity % self.constant_fragment_capacity;
159        let additional_fragment = if remainder > 0 { 1 } else { 0 };
160
161        Ok(num_full_fragments + additional_fragment)
162    }
163
164    fn maximum_concurrent_capacity_bound<T>(&self, _: &[Fragment<T>], _: usize) -> usize {
165        *FIXED_CAPACITIES
166            .last()
167            .expect("fixed capacities is non-empty")
168    }
169}
170
171impl GrowthWithConstantTimeAccess for Linear {
172    #[inline(always)]
173    fn get_fragment_and_inner_indices_unchecked(&self, element_index: usize) -> (usize, usize) {
174        let f = element_index >> self.constant_fragment_capacity_exponent;
175        let i = element_index % self.constant_fragment_capacity;
176        (f, i)
177    }
178
179    fn fragment_capacity_of(&self, _: usize) -> usize {
180        self.constant_fragment_capacity
181    }
182}
183
184impl<T> SplitVec<T, Linear> {
185    /// Creates a split vector with linear growth where each fragment will have a capacity of `2 ^ constant_fragment_capacity_exponent`.
186    ///
187    /// Assuming it is the common case compared to empty vector scenarios,
188    /// it immediately allocates the first fragment to keep the `SplitVec` struct smaller.
189    ///
190    /// # Panics
191    ///
192    /// Panics if `constant_fragment_capacity_exponent` is zero or `constant_fragment_capacity_exponent >= MAX_EXPONENT` where `MAX_EXPONENT` is:
193    ///
194    /// * 29 in 32-bit targets,
195    /// * 32 in 64-bit.
196    ///
197    /// # Examples
198    ///
199    /// ```
200    /// use orx_split_vec::*;
201    ///
202    /// // SplitVec<usize, Linear>
203    /// let mut vec = SplitVec::with_linear_growth(4);
204    ///
205    /// assert_eq!(1, vec.fragments().len());
206    /// assert_eq!(Some(16), vec.fragments().first().map(|f| f.capacity()));
207    /// assert_eq!(Some(0), vec.fragments().first().map(|f| f.len()));
208    ///
209    /// // push 160 elements
210    /// for i in 0..10 * 16 {
211    ///     vec.push(i);
212    /// }
213    ///
214    /// assert_eq!(10, vec.fragments().len());
215    /// for fragment in vec.fragments() {
216    ///     assert_eq!(16, fragment.len());
217    ///     assert_eq!(16, fragment.capacity());
218    /// }
219    ///
220    /// // push the 161-st element
221    /// vec.push(42);
222    /// assert_eq!(11, vec.fragments().len());
223    /// assert_eq!(Some(16), vec.fragments().last().map(|f| f.capacity()));
224    /// assert_eq!(Some(1), vec.fragments().last().map(|f| f.len()));
225    /// ```
226    pub fn with_linear_growth(constant_fragment_capacity_exponent: usize) -> Self {
227        assert!(
228            constant_fragment_capacity_exponent > 0
229                && constant_fragment_capacity_exponent < FIXED_CAPACITIES.len(),
230            "constant_fragment_capacity_exponent must be within 1..32 (1..29) for 64-bit (32-bit) platforms."
231        );
232
233        let constant_fragment_capacity = FIXED_CAPACITIES[constant_fragment_capacity_exponent];
234        let fragments = Fragment::new(constant_fragment_capacity).into_fragments();
235        let growth = Linear::new(constant_fragment_capacity_exponent);
236        Self::from_raw_parts(0, fragments, growth)
237    }
238
239    /// Creates a new split vector with `Linear` growth and initial `fragments_capacity`.
240    ///
241    /// This method differs from [`SplitVec::with_linear_growth`] only by the pre-allocation of fragments collection.
242    /// Note that this (only) important for concurrent programs:
243    /// * SplitVec already keeps all elements pinned to their locations;
244    /// * Creating a buffer for storing the meta information is important for keeping the meta information pinned as well.
245    ///   This is relevant and important for concurrent programs.
246    ///
247    /// # Panics
248    ///
249    /// Panics if `constant_fragment_capacity_exponent` is zero or `constant_fragment_capacity_exponent >= MAX_EXPONENT` where `MAX_EXPONENT` is:
250    ///
251    /// * 29 in 32-bit targets,
252    /// * 32 in 64-bit.
253    pub fn with_linear_growth_and_fragments_capacity(
254        constant_fragment_capacity_exponent: usize,
255        fragments_capacity: usize,
256    ) -> Self {
257        assert!(
258            constant_fragment_capacity_exponent > 0
259                && constant_fragment_capacity_exponent < FIXED_CAPACITIES.len(),
260            "constant_fragment_capacity_exponent must be within 1..{}",
261            FIXED_CAPACITIES.len()
262        );
263        assert!(fragments_capacity > 0);
264
265        let constant_fragment_capacity = FIXED_CAPACITIES[constant_fragment_capacity_exponent];
266        let fragments = Fragment::new(constant_fragment_capacity)
267            .into_fragments_with_capacity(fragments_capacity);
268        let growth = Linear::new(constant_fragment_capacity_exponent);
269        Self::from_raw_parts(0, fragments, growth)
270    }
271}
272
273#[cfg(test)]
274mod tests {
275    use super::*;
276    use orx_pinned_vec::PinnedVec;
277
278    #[test]
279    fn get_fragment_and_inner_indices() {
280        let growth = Linear::new(2);
281
282        let get = |index| growth.get_fragment_and_inner_indices::<char>(usize::MAX, &[], index);
283        let get_none = |index| growth.get_fragment_and_inner_indices::<char>(index, &[], index);
284
285        assert_eq!((0, 0), growth.get_fragment_and_inner_indices_unchecked(0));
286        assert_eq!((0, 1), growth.get_fragment_and_inner_indices_unchecked(1));
287        assert_eq!((1, 0), growth.get_fragment_and_inner_indices_unchecked(4));
288        assert_eq!((2, 1), growth.get_fragment_and_inner_indices_unchecked(9));
289        assert_eq!((4, 0), growth.get_fragment_and_inner_indices_unchecked(16));
290
291        assert_eq!(Some((0, 0)), get(0));
292        assert_eq!(Some((0, 1)), get(1));
293        assert_eq!(Some((1, 0)), get(4));
294        assert_eq!(Some((2, 1)), get(9));
295        assert_eq!(Some((4, 0)), get(16));
296
297        assert_eq!(None, get_none(0));
298        assert_eq!(None, get_none(1));
299        assert_eq!(None, get_none(4));
300        assert_eq!(None, get_none(9));
301        assert_eq!(None, get_none(16));
302    }
303
304    #[test]
305    fn get_fragment_and_inner_indices_exhaustive() {
306        let growth = Linear::new(5);
307
308        let get = |index| growth.get_fragment_and_inner_indices::<char>(usize::MAX, &[], index);
309        let get_none = |index| growth.get_fragment_and_inner_indices::<char>(index, &[], index);
310
311        let curr_capacity = 32;
312
313        let mut f = 0;
314        let mut prev_cumulative_capacity = 0;
315        let mut cumulative_capacity = curr_capacity;
316
317        for index in 0..51_111 {
318            if index == cumulative_capacity {
319                prev_cumulative_capacity = cumulative_capacity;
320                cumulative_capacity += curr_capacity;
321                f += 1;
322            }
323
324            let (f, i) = (f, index - prev_cumulative_capacity);
325            assert_eq!(
326                (f, i),
327                growth.get_fragment_and_inner_indices_unchecked(index)
328            );
329            assert_eq!(Some((f, i)), get(index));
330            assert_eq!(None, get_none(index));
331        }
332    }
333
334    #[test]
335    fn maximum_concurrent_capacity() {
336        fn max_cap<T>(vec: &SplitVec<T, Linear>) -> usize {
337            vec.growth()
338                .maximum_concurrent_capacity(vec.fragments(), vec.fragments.capacity())
339        }
340
341        let mut vec: SplitVec<char, Linear> = SplitVec::with_linear_growth(5);
342        assert_eq!(max_cap(&vec), 4 * 2usize.pow(5));
343
344        let until = max_cap(&vec);
345        for _ in 0..until {
346            vec.push('x');
347            assert_eq!(max_cap(&vec), 4 * 2usize.pow(5));
348        }
349
350        // fragments allocate beyond max_cap
351        vec.push('x');
352        assert_eq!(max_cap(&vec), 8 * 2usize.pow(5));
353    }
354
355    #[test]
356    fn with_linear_growth_and_fragments_capacity_normal_growth() {
357        let mut vec: SplitVec<char, _> = SplitVec::with_linear_growth_and_fragments_capacity(10, 1);
358
359        assert_eq!(1, vec.fragments.capacity());
360
361        #[cfg(not(miri))]
362        let n = 100_000;
363        #[cfg(miri)]
364        let n = 55;
365
366        for _ in 0..n {
367            vec.push('x');
368        }
369
370        #[cfg(not(miri))]
371        assert!(vec.fragments.capacity() > 4);
372    }
373
374    #[test]
375    #[should_panic]
376    fn with_linear_growth_and_fragments_capacity_zero() {
377        let _: SplitVec<char, _> = SplitVec::with_linear_growth_and_fragments_capacity(10, 0);
378    }
379
380    #[test]
381    fn with_linear_growth_with_max_fragment_capacity() {
382        let exponent = FIXED_CAPACITIES.len() - 1;
383        let _: SplitVec<char, _> = SplitVec::with_linear_growth(exponent);
384    }
385
386    #[test]
387    #[should_panic]
388    fn with_linear_growth_with_too_large_fragment_capacity() {
389        let exponent = FIXED_CAPACITIES.len();
390        let _: SplitVec<char, _> = SplitVec::with_linear_growth(exponent);
391    }
392
393    #[test]
394    fn required_fragments_len() {
395        let vec: SplitVec<char, Linear> = SplitVec::with_linear_growth(5);
396        let num_fragments = |max_cap| {
397            vec.growth()
398                .required_fragments_len(vec.fragments(), max_cap)
399        };
400
401        assert_eq!(num_fragments(0), Ok(0));
402        assert_eq!(num_fragments(1), Ok(1));
403        assert_eq!(num_fragments(2), Ok(1));
404        assert_eq!(num_fragments(32), Ok(1));
405        assert_eq!(num_fragments(33), Ok(2));
406        assert_eq!(num_fragments(32 * 7), Ok(7));
407        assert_eq!(num_fragments(32 * 7 + 1), Ok(8));
408    }
409}
orx_split_vec/growth/linear/linear_growth.rs

orx_split_vec/growth/linear/
linear_growth.rs
