orx_split_vec/growth/recursive/
recursive_growth.rs1use crate::{Doubling, Fragment, Growth, SplitVec};
2use alloc::string::String;
3use orx_pseudo_default::PseudoDefault;
4
5#[derive(Debug, Default, Clone, PartialEq)]
44pub struct Recursive;
45
46impl PseudoDefault for Recursive {
47 fn pseudo_default() -> Self {
48 Default::default()
49 }
50}
51
52impl Growth for Recursive {
53 #[inline(always)]
54 fn new_fragment_capacity_from(
55 &self,
56 fragment_capacities: impl ExactSizeIterator<Item = usize>,
57 ) -> usize {
58 Doubling.new_fragment_capacity_from(fragment_capacities)
59 }
60
61 fn maximum_concurrent_capacity<T>(
62 &self,
63 fragments: &[Fragment<T>],
64 fragments_capacity: usize,
65 ) -> usize {
66 assert!(fragments_capacity >= fragments.len());
67
68 let current_capacity = fragments.iter().map(|x| x.capacity()).sum();
69 let mut last_capacity = fragments.last().map(|x| x.capacity()).unwrap_or(2);
70
71 let mut total_capacity = current_capacity;
72
73 for _ in fragments.len()..fragments_capacity {
74 last_capacity *= 2;
75 total_capacity += last_capacity;
76 }
77
78 total_capacity
79 }
80
81 fn required_fragments_len<T>(
82 &self,
83 fragments: &[Fragment<T>],
84 maximum_capacity: usize,
85 ) -> Result<usize, String> {
86 fn overflown_err() -> String {
87 alloc::format!(
88 "Maximum cumulative capacity that can be reached by the Recursive strategy is {}.",
89 usize::MAX
90 )
91 }
92
93 let current_capacity: usize = fragments.iter().map(|x| x.capacity()).sum();
94 let mut last_capacity = fragments.last().map(|x| x.capacity()).unwrap_or(2);
95
96 let mut total_capacity = current_capacity;
97 let mut f = fragments.len();
98
99 while total_capacity < maximum_capacity {
100 let (new_last_capacity, overflown) = last_capacity.overflowing_mul(2);
101 if overflown {
102 return Err(overflown_err());
103 }
104 last_capacity = new_last_capacity;
105
106 let (new_total_capacity, overflown) = total_capacity.overflowing_add(last_capacity);
107 if overflown {
108 return Err(overflown_err());
109 }
110
111 total_capacity = new_total_capacity;
112 f += 1;
113 }
114
115 Ok(f)
116 }
117
118 fn maximum_concurrent_capacity_bound<T>(
119 &self,
120 fragments: &[Fragment<T>],
121 fragments_capacity: usize,
122 ) -> usize {
123 Doubling.maximum_concurrent_capacity_bound(fragments, fragments_capacity)
124 }
125}
126
127impl<T> SplitVec<T, Recursive> {
128 pub fn with_recursive_growth() -> Self {
200 SplitVec::with_doubling_growth().into()
201 }
202
203 pub fn with_recursive_growth_and_fragments_capacity(fragments_capacity: usize) -> Self {
215 SplitVec::with_doubling_growth_and_fragments_capacity(fragments_capacity).into()
216 }
217
218 pub fn with_recursive_growth_and_max_concurrent_capacity() -> Self {
224 SplitVec::with_doubling_growth_and_max_concurrent_capacity().into()
225 }
226}
227
228#[cfg(test)]
229mod tests {
230 use crate::growth::doubling::constants::{CAPACITIES_LEN, FIRST_FRAGMENT_CAPACITY};
231
232 use super::*;
233 use alloc::vec::Vec;
234 use orx_pinned_vec::PinnedVec;
235
236 #[test]
237 fn get_fragment_and_inner_indices() {
238 let growth = Recursive;
239
240 let vecs = alloc::vec![
241 alloc::vec![0, 1, 2, 3],
242 alloc::vec![4, 5],
243 alloc::vec![6, 7, 8],
244 alloc::vec![9],
245 alloc::vec![10, 11, 12, 13, 14],
246 ];
247 let mut fragments: Vec<Fragment<_>> = vecs.clone().into_iter().map(|x| x.into()).collect();
248 let len = fragments.iter().map(|x| x.len()).sum();
249
250 let mut index = 0;
251 for (f, vec) in vecs.iter().enumerate() {
252 for (i, _) in vec.iter().enumerate() {
253 let maybe_fi = growth.get_fragment_and_inner_indices(len, &fragments, index);
254 assert_eq!(maybe_fi, Some((f, i)));
255
256 let ptr = growth.get_ptr_mut(&mut fragments, index).expect("is-some");
257 assert_eq!(unsafe { *ptr }, index);
258
259 unsafe { *ptr = 10 * index };
260 assert_eq!(unsafe { *ptr }, 10 * index);
261
262 index += 1;
263 }
264 }
265 }
266
267 #[test]
268 fn get_fragment_and_inner_indices_exhaustive() {
269 let growth = Recursive;
270
271 let mut fragments: Vec<Fragment<_>> = alloc::vec![];
272
273 #[cfg(not(miri))]
274 let lengths = [30, 1, 7, 3, 79, 147, 530];
275 #[cfg(miri)]
276 let lengths = [1, 7, 3, 30];
277
278 let mut index = 0;
279 for _ in 0..10 {
280 for &len in &lengths {
281 let mut vec = Vec::with_capacity(len);
282 for _ in 0..len {
283 vec.push(index);
284 index += 1;
285 }
286 fragments.push(vec.into());
287 }
288 }
289
290 let total_len = fragments.iter().map(|x| x.len()).sum();
291
292 let mut index = 0;
293 let mut f = 0;
294 for _ in 0..10 {
295 for &len in &lengths {
296 for i in 0..len {
297 let maybe_fi =
298 growth.get_fragment_and_inner_indices(total_len, &fragments, index);
299
300 assert_eq!(maybe_fi, Some((f, i)));
301
302 let ptr = growth.get_ptr_mut(&mut fragments, index).expect("is-some");
303 assert_eq!(unsafe { *ptr }, index);
304
305 unsafe { *ptr = 10 * index };
306 assert_eq!(unsafe { *ptr }, 10 * index);
307
308 index += 1;
309 }
310 f += 1;
311 }
312 }
313 }
314
315 #[test]
316 fn maximum_concurrent_capacity() {
317 fn max_cap<T>(vec: &SplitVec<T, Recursive>) -> usize {
318 vec.growth()
319 .maximum_concurrent_capacity(vec.fragments(), vec.fragments.capacity())
320 }
321
322 let mut vec: SplitVec<char, Recursive> = SplitVec::with_recursive_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 vec.push('x');
333 assert_eq!(max_cap(&vec), 4 + 8 + 16 + 32 + 64 + 128 + 256 + 512);
334 }
335
336 #[test]
337 fn maximum_concurrent_capacity_when_appended() {
338 fn max_cap<T>(vec: &SplitVec<T, Recursive>) -> usize {
339 vec.growth()
340 .maximum_concurrent_capacity(vec.fragments(), vec.fragments.capacity())
341 }
342
343 let mut vec: SplitVec<char, Recursive> = SplitVec::with_recursive_growth();
344 assert_eq!(max_cap(&vec), 4 + 8 + 16 + 32);
345
346 vec.append(alloc::vec!['x'; 10]);
347 assert_eq!(vec.fragments().len(), 2);
348 assert_eq!(vec.fragments()[1].capacity(), 10);
349 assert_eq!(vec.fragments()[1].len(), 10);
350
351 assert_eq!(max_cap(&vec), 4 + 10 + 20 + 40);
352 }
353
354 #[test]
355 fn with_recursive_growth_and_fragments_capacity_normal_growth() {
356 let mut vec: SplitVec<char, _> = SplitVec::with_recursive_growth_and_fragments_capacity(1);
357
358 assert_eq!(1, vec.fragments.capacity());
359
360 #[cfg(not(miri))]
361 let n = 100_000;
362 #[cfg(miri)]
363 let n = 55;
364
365 for _ in 0..n {
366 vec.push('x');
367 }
368
369 #[cfg(not(miri))]
370 assert!(vec.fragments.capacity() > 4);
371 }
372
373 #[test]
374 #[should_panic]
375 fn with_recursive_growth_and_fragments_capacity_zero() {
376 let _: SplitVec<char, _> = SplitVec::with_recursive_growth_and_fragments_capacity(0);
377 }
378
379 #[test]
380 #[should_panic]
381 fn with_recursive_growth_and_fragments_capacity_too_large_fragments_capacity() {
382 let vec: SplitVec<char, _> = SplitVec::with_recursive_growth_and_fragments_capacity(1000);
383 assert_eq!(
384 vec.maximum_concurrent_capacity(),
385 (1 << (CAPACITIES_LEN + 2)) - FIRST_FRAGMENT_CAPACITY
386 );
387 }
388
389 #[test]
390 fn with_recursive_growth_and_max_concurrent_capacity() {
391 let vec: SplitVec<char, _> = SplitVec::with_recursive_growth_and_max_concurrent_capacity();
392 assert_eq!(
393 vec.maximum_concurrent_capacity(),
394 (1 << (CAPACITIES_LEN + 2)) - FIRST_FRAGMENT_CAPACITY
395 );
396 }
397
398 #[test]
399 fn required_fragments_len() {
400 let vec: SplitVec<char, Recursive> = SplitVec::with_recursive_growth();
401 let num_fragments = |max_cap| {
402 vec.growth()
403 .required_fragments_len(vec.fragments(), max_cap)
404 };
405
406 assert_eq!(num_fragments(0), Ok(1));
408 assert_eq!(num_fragments(1), Ok(1));
409 assert_eq!(num_fragments(4), Ok(1));
410 assert_eq!(num_fragments(5), Ok(2));
411 assert_eq!(num_fragments(12), Ok(2));
412 assert_eq!(num_fragments(13), Ok(3));
413 assert_eq!(num_fragments(36), Ok(4));
414 assert_eq!(num_fragments(67), Ok(5));
415 assert_eq!(num_fragments(136), Ok(6));
416 }
417
418 #[test]
419 fn required_fragments_len_when_appended() {
420 let mut vec: SplitVec<char, Recursive> = SplitVec::with_recursive_growth();
421 for _ in 0..4 {
422 vec.push('x')
423 }
424 vec.append(alloc::vec!['x'; 10]);
425
426 let num_fragments = |max_cap| {
427 vec.growth()
428 .required_fragments_len(vec.fragments(), max_cap)
429 };
430
431 assert_eq!(num_fragments(0), Ok(2));
434 assert_eq!(num_fragments(1), Ok(2));
435 assert_eq!(num_fragments(14), Ok(2));
436 assert_eq!(num_fragments(15), Ok(3));
437 assert_eq!(num_fragments(21), Ok(3));
438 assert_eq!(num_fragments(34), Ok(3));
439 assert_eq!(num_fragments(35), Ok(4));
440 assert_eq!(num_fragments(74), Ok(4));
441 assert_eq!(num_fragments(75), Ok(5));
442 assert_eq!(num_fragments(154), Ok(5));
443 assert_eq!(num_fragments(155), Ok(6));
444 }
445}