orx_split_vec/growth/doubling/
doubling_growth.rs

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

orx_split_vec/growth/doubling/
doubling_growth.rs
