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..{}; however, {} is provided.",
263            CAPACITIES_LEN,
264            fragments_capacity
265        );
266        assert!(fragments_capacity > 0);
267        let fragments =
268            Fragment::new(FIRST_FRAGMENT_CAPACITY).into_fragments_with_capacity(fragments_capacity);
269        Self::from_raw_parts(0, fragments, Doubling)
270    }
271
272    /// Creates a new split vector with `Doubling` growth and maximum concurrent capacity which depends
273    /// on the pointer size of the target architecture.
274    ///
275    /// This method differs from [`SplitVec::with_doubling_growth`] only by the pre-allocation of fragments collection,
276    /// which never contains more elements than 33.
277    pub fn with_doubling_growth_and_max_concurrent_capacity() -> Self {
278        let fragments =
279            Fragment::new(FIRST_FRAGMENT_CAPACITY).into_fragments_with_capacity(CAPACITIES_LEN);
280        Self::from_raw_parts(0, fragments, Doubling)
281    }
282}
283
284#[cfg(test)]
285mod tests {
286    use super::*;
287    use orx_pinned_vec::PinnedVec;
288
289    #[test]
290    fn get_fragment_and_inner_indices() {
291        let growth = Doubling;
292
293        let get = |index| growth.get_fragment_and_inner_indices::<char>(usize::MAX, &[], index);
294        let get_none = |index| growth.get_fragment_and_inner_indices::<char>(index, &[], index);
295
296        assert_eq!((0, 0), growth.get_fragment_and_inner_indices_unchecked(0));
297        assert_eq!((0, 1), growth.get_fragment_and_inner_indices_unchecked(1));
298        assert_eq!((1, 0), growth.get_fragment_and_inner_indices_unchecked(4));
299        assert_eq!((1, 5), growth.get_fragment_and_inner_indices_unchecked(9));
300        assert_eq!((2, 0), growth.get_fragment_and_inner_indices_unchecked(12));
301
302        assert_eq!(Some((0, 0)), get(0));
303        assert_eq!(Some((0, 1)), get(1));
304        assert_eq!(Some((1, 0)), get(4));
305        assert_eq!(Some((1, 5)), get(9));
306        assert_eq!(Some((2, 0)), get(12));
307
308        assert_eq!(None, get_none(0));
309        assert_eq!(None, get_none(1));
310        assert_eq!(None, get_none(4));
311        assert_eq!(None, get_none(9));
312        assert_eq!(None, get_none(12));
313    }
314
315    #[test]
316    fn get_fragment_and_inner_indices_exhaustive() {
317        let growth = Doubling;
318
319        let get = |index| growth.get_fragment_and_inner_indices::<char>(usize::MAX, &[], index);
320        let get_none = |index| growth.get_fragment_and_inner_indices::<char>(index, &[], index);
321
322        let mut f = 0;
323        let mut prev_cumulative_capacity = 0;
324        let mut curr_capacity = 4;
325        let mut cumulative_capacity = 4;
326
327        for index in 0..51_111 {
328            if index == cumulative_capacity {
329                prev_cumulative_capacity = cumulative_capacity;
330                curr_capacity *= 2;
331                cumulative_capacity += curr_capacity;
332                f += 1;
333            }
334
335            let (f, i) = (f, index - prev_cumulative_capacity);
336            assert_eq!(
337                (f, i),
338                growth.get_fragment_and_inner_indices_unchecked(index)
339            );
340            assert_eq!(Some((f, i)), get(index));
341            assert_eq!(None, get_none(index));
342        }
343    }
344
345    #[test]
346    fn maximum_concurrent_capacity() {
347        fn max_cap<T>(vec: &SplitVec<T, Doubling>) -> usize {
348            vec.growth()
349                .maximum_concurrent_capacity(vec.fragments(), vec.fragments.capacity())
350        }
351
352        let mut vec: SplitVec<char, Doubling> = SplitVec::with_doubling_growth();
353        assert_eq!(max_cap(&vec), 4 + 8 + 16 + 32);
354
355        let until = max_cap(&vec);
356        for _ in 0..until {
357            vec.push('x');
358            assert_eq!(max_cap(&vec), 4 + 8 + 16 + 32);
359        }
360
361        // fragments allocate beyond max_cap
362        vec.push('x');
363        assert_eq!(max_cap(&vec), 4 + 8 + 16 + 32 + 64 + 128 + 256 + 512);
364    }
365
366    #[test]
367    fn with_doubling_growth_and_fragments_capacity_normal_growth() {
368        let mut vec: SplitVec<char, _> = SplitVec::with_doubling_growth_and_fragments_capacity(1);
369
370        assert_eq!(1, vec.fragments.capacity());
371
372        #[cfg(not(miri))]
373        let n = 100_000;
374        #[cfg(miri)]
375        let n = 44;
376
377        for _ in 0..n {
378            vec.push('x');
379        }
380
381        #[cfg(not(miri))]
382        assert!(vec.fragments.capacity() > 4);
383    }
384
385    #[test]
386    #[should_panic]
387    fn with_doubling_growth_and_fragments_capacity_zero() {
388        let _: SplitVec<char, _> = SplitVec::with_doubling_growth_and_fragments_capacity(0);
389    }
390
391    #[test]
392    fn with_doubling_growth_and_fragments_capacity_with_max_fragments_capacity() {
393        let vec: SplitVec<char, _> =
394            SplitVec::with_doubling_growth_and_fragments_capacity(CAPACITIES_LEN);
395        assert_eq!(
396            vec.maximum_concurrent_capacity(),
397            (1 << (CAPACITIES_LEN + 2)) - FIRST_FRAGMENT_CAPACITY
398        );
399    }
400
401    #[test]
402    #[should_panic]
403    fn with_doubling_growth_and_fragments_capacity_too_large_fragments_capacity() {
404        let _: SplitVec<char, _> =
405            SplitVec::with_doubling_growth_and_fragments_capacity(CAPACITIES_LEN + 1);
406    }
407
408    #[test]
409    fn with_doubling_growth_and_max_concurrent_capacity() {
410        let vec: SplitVec<char, _> = SplitVec::with_doubling_growth_and_max_concurrent_capacity();
411        assert_eq!(
412            vec.maximum_concurrent_capacity(),
413            (1 << (CAPACITIES_LEN + 2)) - FIRST_FRAGMENT_CAPACITY
414        );
415    }
416
417    #[test]
418    fn required_fragments_len() {
419        let vec: SplitVec<char, Doubling> = SplitVec::with_doubling_growth();
420        let num_fragments = |max_cap| {
421            vec.growth()
422                .required_fragments_len(vec.fragments(), max_cap)
423        };
424
425        // 4 - 12 - 28 - 60 - 124
426        assert_eq!(num_fragments(0), Ok(0));
427        assert_eq!(num_fragments(1), Ok(1));
428        assert_eq!(num_fragments(4), Ok(1));
429        assert_eq!(num_fragments(5), Ok(2));
430        assert_eq!(num_fragments(12), Ok(2));
431        assert_eq!(num_fragments(13), Ok(3));
432        assert_eq!(num_fragments(36), Ok(4));
433        assert_eq!(num_fragments(67), Ok(5));
434        assert_eq!(num_fragments(136), Ok(6));
435    }
436
437    #[test]
438    fn required_fragments_len_at_max() {
439        let vec: SplitVec<char, Doubling> = SplitVec::with_doubling_growth();
440        let num_fragments = |max_cap| {
441            vec.growth()
442                .required_fragments_len(vec.fragments(), max_cap)
443        };
444
445        let maximum_possible_capacity = *CUMULATIVE_CAPACITIES.last().expect("is not empty");
446        #[cfg(target_pointer_width = "32")]
447        assert_eq!(num_fragments(maximum_possible_capacity), Ok(29));
448        #[cfg(target_pointer_width = "64")]
449        assert_eq!(num_fragments(maximum_possible_capacity), Ok(32));
450    }
451
452    #[test]
453    fn required_fragments_len_more_than_max() {
454        let vec: SplitVec<char, Doubling> = SplitVec::with_doubling_growth();
455        let num_fragments = |max_cap| {
456            vec.growth()
457                .required_fragments_len(vec.fragments(), max_cap)
458        };
459
460        let more_than_max_possible_capacity =
461            *CUMULATIVE_CAPACITIES.last().expect("is not empty") + 1;
462        assert!(num_fragments(more_than_max_possible_capacity).is_err());
463    }
464}
orx_split_vec/growth/doubling/doubling_growth.rs

orx_split_vec/growth/doubling/
doubling_growth.rs
