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    fn maximum_concurrent_capacity_bound<T>(&self, _: &[Fragment<T>], _: usize) -> usize {
165        *CUMULATIVE_CAPACITIES
166            .last()
167            .expect("cumulative capacities is not empty")
168    }
169}
170
171impl GrowthWithConstantTimeAccess for Doubling {
172    #[inline(always)]
173    fn get_fragment_and_inner_indices_unchecked(&self, element_index: usize) -> (usize, usize) {
174        let element_index_offset = element_index + FIRST_FRAGMENT_CAPACITY;
175        let leading_zeros = usize::leading_zeros(element_index_offset) as usize;
176        let f = OFFSET_FRAGMENT_IDX - leading_zeros;
177        (f, element_index - CUMULATIVE_CAPACITIES[f])
178    }
179
180    fn fragment_capacity_of(&self, fragment_index: usize) -> usize {
181        CAPACITIES[fragment_index]
182    }
183}
184
185impl<T> SplitVec<T, Doubling> {
186    /// Strategy which allows to create a fragment with double the capacity
187    /// of the prior fragment every time the split vector needs to expand.
188    ///
189    /// Assuming it is the common case compared to empty vector scenarios,
190    /// it immediately allocates the first fragment to keep the `SplitVec` struct smaller.
191    ///
192    /// # Panics
193    /// Panics if `first_fragment_capacity` is zero.
194    ///
195    /// # Examples
196    ///
197    /// ```
198    /// use orx_split_vec::*;
199    ///
200    /// // SplitVec<usize, Doubling>
201    /// let mut vec = SplitVec::with_doubling_growth();
202    ///
203    /// assert_eq!(1, vec.fragments().len());
204    /// assert_eq!(Some(4), vec.fragments().first().map(|f| f.capacity()));
205    /// assert_eq!(Some(0), vec.fragments().first().map(|f| f.len()));
206    ///
207    /// // fill the first 5 fragments
208    /// let expected_fragment_capacities = vec![4, 8, 16, 32];
209    /// let num_items: usize = expected_fragment_capacities.iter().sum();
210    /// for i in 0..num_items {
211    ///     vec.push(i);
212    /// }
213    ///
214    /// assert_eq!(
215    ///     expected_fragment_capacities,
216    ///     vec.fragments()
217    ///     .iter()
218    ///     .map(|f| f.capacity())
219    ///     .collect::<Vec<_>>()
220    /// );
221    /// assert_eq!(
222    ///     expected_fragment_capacities,
223    ///     vec.fragments().iter().map(|f| f.len()).collect::<Vec<_>>()
224    /// );
225    ///
226    /// // create the 6-th fragment doubling the capacity
227    /// vec.push(42);
228    /// assert_eq!(
229    ///     vec.fragments().len(),
230    ///     expected_fragment_capacities.len() + 1
231    /// );
232    ///
233    /// assert_eq!(vec.fragments().last().map(|f| f.capacity()), Some(32 * 2));
234    /// assert_eq!(vec.fragments().last().map(|f| f.len()), Some(1));
235    /// ```
236    pub fn with_doubling_growth() -> Self {
237        let fragments = Fragment::new(FIRST_FRAGMENT_CAPACITY).into_fragments();
238        Self::from_raw_parts(0, fragments, Doubling)
239    }
240
241    /// Creates a new split vector with `Doubling` growth and initial `fragments_capacity`.
242    ///
243    /// This method differs from [`SplitVec::with_doubling_growth`] only by the pre-allocation of fragments collection.
244    /// Note that this (only) important for concurrent programs:
245    /// * SplitVec already keeps all elements pinned to their locations;
246    /// * Creating a buffer for storing the meta information is important for keeping the meta information pinned as well.
247    ///   This is relevant and important for concurrent programs.
248    ///
249    /// # Panics
250    ///
251    /// Panics if `fragments_capacity == 0`.
252    ///
253    /// # Panics
254    ///
255    /// Panics if `fragments_capacity` is zero or `fragments_capacity > MAX_FRAGMENTS_CAPACITY` where `MAX_FRAGMENTS_CAPACITY` is:
256    ///
257    /// * 29 in 32-bit targets,
258    /// * 32 in 64-bit.
259    pub fn with_doubling_growth_and_fragments_capacity(fragments_capacity: usize) -> Self {
260        assert!(
261            fragments_capacity > 0 && fragments_capacity <= CAPACITIES_LEN,
262            "fragments_capacity must be within 1..{CAPACITIES_LEN}; however, {fragments_capacity} is provided."
263        );
264        assert!(fragments_capacity > 0);
265        let fragments =
266            Fragment::new(FIRST_FRAGMENT_CAPACITY).into_fragments_with_capacity(fragments_capacity);
267        Self::from_raw_parts(0, fragments, Doubling)
268    }
269
270    /// Creates a new split vector with `Doubling` growth and maximum concurrent capacity which depends
271    /// on the pointer size of the target architecture.
272    ///
273    /// This method differs from [`SplitVec::with_doubling_growth`] only by the pre-allocation of fragments collection,
274    /// which never contains more elements than 33.
275    pub fn with_doubling_growth_and_max_concurrent_capacity() -> Self {
276        let fragments =
277            Fragment::new(FIRST_FRAGMENT_CAPACITY).into_fragments_with_capacity(CAPACITIES_LEN);
278        Self::from_raw_parts(0, fragments, Doubling)
279    }
280}
281
282#[cfg(test)]
283mod tests {
284    use super::*;
285    use orx_pinned_vec::PinnedVec;
286
287    #[test]
288    fn get_fragment_and_inner_indices() {
289        let growth = Doubling;
290
291        let get = |index| growth.get_fragment_and_inner_indices::<char>(usize::MAX, &[], index);
292        let get_none = |index| growth.get_fragment_and_inner_indices::<char>(index, &[], index);
293
294        assert_eq!((0, 0), growth.get_fragment_and_inner_indices_unchecked(0));
295        assert_eq!((0, 1), growth.get_fragment_and_inner_indices_unchecked(1));
296        assert_eq!((1, 0), growth.get_fragment_and_inner_indices_unchecked(4));
297        assert_eq!((1, 5), growth.get_fragment_and_inner_indices_unchecked(9));
298        assert_eq!((2, 0), growth.get_fragment_and_inner_indices_unchecked(12));
299
300        assert_eq!(Some((0, 0)), get(0));
301        assert_eq!(Some((0, 1)), get(1));
302        assert_eq!(Some((1, 0)), get(4));
303        assert_eq!(Some((1, 5)), get(9));
304        assert_eq!(Some((2, 0)), get(12));
305
306        assert_eq!(None, get_none(0));
307        assert_eq!(None, get_none(1));
308        assert_eq!(None, get_none(4));
309        assert_eq!(None, get_none(9));
310        assert_eq!(None, get_none(12));
311    }
312
313    #[test]
314    fn get_fragment_and_inner_indices_exhaustive() {
315        let growth = Doubling;
316
317        let get = |index| growth.get_fragment_and_inner_indices::<char>(usize::MAX, &[], index);
318        let get_none = |index| growth.get_fragment_and_inner_indices::<char>(index, &[], index);
319
320        let mut f = 0;
321        let mut prev_cumulative_capacity = 0;
322        let mut curr_capacity = 4;
323        let mut cumulative_capacity = 4;
324
325        for index in 0..51_111 {
326            if index == cumulative_capacity {
327                prev_cumulative_capacity = cumulative_capacity;
328                curr_capacity *= 2;
329                cumulative_capacity += curr_capacity;
330                f += 1;
331            }
332
333            let (f, i) = (f, index - prev_cumulative_capacity);
334            assert_eq!(
335                (f, i),
336                growth.get_fragment_and_inner_indices_unchecked(index)
337            );
338            assert_eq!(Some((f, i)), get(index));
339            assert_eq!(None, get_none(index));
340        }
341    }
342
343    #[test]
344    fn maximum_concurrent_capacity() {
345        fn max_cap<T>(vec: &SplitVec<T, Doubling>) -> usize {
346            vec.growth()
347                .maximum_concurrent_capacity(vec.fragments(), vec.fragments.capacity())
348        }
349
350        let mut vec: SplitVec<char, Doubling> = SplitVec::with_doubling_growth();
351        assert_eq!(max_cap(&vec), 4 + 8 + 16 + 32);
352
353        let until = max_cap(&vec);
354        for _ in 0..until {
355            vec.push('x');
356            assert_eq!(max_cap(&vec), 4 + 8 + 16 + 32);
357        }
358
359        // fragments allocate beyond max_cap
360        vec.push('x');
361        assert_eq!(max_cap(&vec), 4 + 8 + 16 + 32 + 64 + 128 + 256 + 512);
362    }
363
364    #[test]
365    fn with_doubling_growth_and_fragments_capacity_normal_growth() {
366        let mut vec: SplitVec<char, _> = SplitVec::with_doubling_growth_and_fragments_capacity(1);
367
368        assert_eq!(1, vec.fragments.capacity());
369
370        #[cfg(not(miri))]
371        let n = 100_000;
372        #[cfg(miri)]
373        let n = 44;
374
375        for _ in 0..n {
376            vec.push('x');
377        }
378
379        #[cfg(not(miri))]
380        assert!(vec.fragments.capacity() > 4);
381    }
382
383    #[test]
384    #[should_panic]
385    fn with_doubling_growth_and_fragments_capacity_zero() {
386        let _: SplitVec<char, _> = SplitVec::with_doubling_growth_and_fragments_capacity(0);
387    }
388
389    #[test]
390    fn with_doubling_growth_and_fragments_capacity_with_max_fragments_capacity() {
391        let vec: SplitVec<char, _> =
392            SplitVec::with_doubling_growth_and_fragments_capacity(CAPACITIES_LEN);
393        assert_eq!(
394            vec.maximum_concurrent_capacity(),
395            (1 << (CAPACITIES_LEN + 2)) - FIRST_FRAGMENT_CAPACITY
396        );
397    }
398
399    #[test]
400    #[should_panic]
401    fn with_doubling_growth_and_fragments_capacity_too_large_fragments_capacity() {
402        let _: SplitVec<char, _> =
403            SplitVec::with_doubling_growth_and_fragments_capacity(CAPACITIES_LEN + 1);
404    }
405
406    #[test]
407    fn with_doubling_growth_and_max_concurrent_capacity() {
408        let vec: SplitVec<char, _> = SplitVec::with_doubling_growth_and_max_concurrent_capacity();
409        assert_eq!(
410            vec.maximum_concurrent_capacity(),
411            (1 << (CAPACITIES_LEN + 2)) - FIRST_FRAGMENT_CAPACITY
412        );
413    }
414
415    #[test]
416    fn required_fragments_len() {
417        let vec: SplitVec<char, Doubling> = SplitVec::with_doubling_growth();
418        let num_fragments = |max_cap| {
419            vec.growth()
420                .required_fragments_len(vec.fragments(), max_cap)
421        };
422
423        // 4 - 12 - 28 - 60 - 124
424        assert_eq!(num_fragments(0), Ok(0));
425        assert_eq!(num_fragments(1), Ok(1));
426        assert_eq!(num_fragments(4), Ok(1));
427        assert_eq!(num_fragments(5), Ok(2));
428        assert_eq!(num_fragments(12), Ok(2));
429        assert_eq!(num_fragments(13), Ok(3));
430        assert_eq!(num_fragments(36), Ok(4));
431        assert_eq!(num_fragments(67), Ok(5));
432        assert_eq!(num_fragments(136), Ok(6));
433    }
434
435    #[test]
436    fn required_fragments_len_at_max() {
437        let vec: SplitVec<char, Doubling> = SplitVec::with_doubling_growth();
438        let num_fragments = |max_cap| {
439            vec.growth()
440                .required_fragments_len(vec.fragments(), max_cap)
441        };
442
443        let maximum_possible_capacity = *CUMULATIVE_CAPACITIES.last().expect("is not empty");
444        #[cfg(target_pointer_width = "32")]
445        assert_eq!(num_fragments(maximum_possible_capacity), Ok(29));
446        #[cfg(target_pointer_width = "64")]
447        assert_eq!(num_fragments(maximum_possible_capacity), Ok(32));
448    }
449
450    #[test]
451    fn required_fragments_len_more_than_max() {
452        let vec: SplitVec<char, Doubling> = SplitVec::with_doubling_growth();
453        let num_fragments = |max_cap| {
454            vec.growth()
455                .required_fragments_len(vec.fragments(), max_cap)
456        };
457
458        let more_than_max_possible_capacity =
459            *CUMULATIVE_CAPACITIES.last().expect("is not empty") + 1;
460        assert!(num_fragments(more_than_max_possible_capacity).is_err());
461    }
462}
orx_split_vec/growth/doubling/doubling_growth.rs

orx_split_vec/growth/doubling/
doubling_growth.rs
