orx-split-vec

A split vector, SplitVec, is a vector represented as a sequence of multiple contagious data fragments.

It provides the following features:

• Flexible in growth strategies; custom strategies can be defined.
• Growth does not cause any memory copies.
• Capacity of an already created fragment is never changed.
• The above feature allows the data to stay pinned in place.
  • SplitVec<T> implements PinnedVec<T> for any T;
  • SplitVec<T> implements PinnedVecSimple<T> for T: NotSelfRefVecItem;
  • Memory location of an item added to the split vector will never change unless the vector is dropped or cleared.
  • This allows the split vec to be converted into an ImpVec to enable immutable-push operations which allows for convenient, efficient and safe implementations of self-referencing data structures.

Pinned elements

```rust use orxsplitvec::prelude::*;

let mut vec = SplitVec::withlineargrowth(10);

// split vec with 1 item in 1 fragment vec.push(42usize); asserteq!(&[42], &vec); asserteq!(1, vec.fragments().len()); assert_eq!(&[42], &vec.fragments()[0]);

// let's get a pointer to the first element let addr42 = &vec[0] as *const usize;

// let's push 100 new elements for i in 1..101 { vec.push(i); }

for (i, elem) in vec.intoiter().enumerate() { asserteq!(if i == 0 { 42 } else { i }, *elem); }

// now the split vector is composed of 11 fragments each with a capacity of 10 assert_eq!(11, vec.fragments().len());

// the memory location of the first element remains intact assert_eq!(addr42, &vec[0] as *const usize);

// we can safely (using unsafe!) dereference it and read the correct value assert_eq!(unsafe { *addr42 }, 42); ```

Vector with self referencing elements

SplitVec is not meant to be a replacement for std::vec::Vec, and not preferable over it in most of the cases since it adds one level of abstraction.

However, it is useful and convenient in defining data structures, child structures of which hold references to each other. This is a very common and useful property for trees, graphs, etc. SplitVec allows to store children of such structures in a vector with the following features:

• holding children close to each other allows for better cache locality,
• reduces heap allocations and utilizes thin references rather than wide pointers,
• while still guaranteeing that the references will remain valid.

SplitVec receives this feature due to the following:

• SplitVec implements PinnedVec; and hence, it can be wrapped by an ImpVec,
• ImpVec allows safely building the vector where items are referencing each other,
• ImpVec can then be converted back to the underlying SplitVec having the abovementioned features and safety guarantees.

Flexible growth strategies without copies

In addition, SplitVec is useful for building collections when:

• there is high uncertainty in the expected length, and
• copies are expensive.

In this case, SplitVec provides a detailed control on how the memory should grow. Further, it avoids copies while growing. Instead, every time the vector needs to grow, it allocates a new chunk of memory as a separate fragment.

```rust use orxsplitvec::prelude::*; use std::rc::Rc;

fn customgrowthfun(fragments: &[Fragment]) -> usize { if fragments.len() < 4 { 4 } else { 8 } } fn getfragmentcapacities>(vec: &SplitVec) -> Vec { vec.fragments().iter().map(|f| f.capacity()).collect() } fn getfragmentlengths>(vec: &SplitVec) -> Vec { vec.fragments().iter().map(|f| f.len()).collect() }

// let's create 4 vectors with different growth strategies let mut veclin = SplitVec::withlineargrowth(10); let mut vecdbl = SplitVec::withdoublinggrowth(4); let mut vecexp = SplitVec::withexponentialgrowth(4, 1.5); let mut veccustom = SplitVec::withcustomgrowthfunction(Rc::new(customgrowth_fun));

// and push 35 elements to all vectors for i in 0..35 { veclin.push(i); vecdbl.push(i); vecexp.push(i); veccustom.push(i); }

// # linear: fragments of equal capacities asserteq!(vec![10, 10, 10, 10], getfragmentcapacities(&veclin)); asserteq!(vec![10, 10, 10, 5], getfragmentlengths(&veclin));

// # doubling: fragment capacities keep doubling asserteq!(vec![4, 8, 16, 32], getfragmentcapacities(&vecdbl)); asserteq!(vec![4, 8, 16, 7], getfragmentlengths(&vecdbl));

// # exponential: fragment capacities grow exponentially with given growth factor asserteq!(vec![4, 6, 9, 13, 19], getfragmentcapacities(&vecexp)); asserteq!(vec![4, 6, 9, 13, 3], getfragmentlengths(&vecexp));

// # custom: pretty much any growth strategy asserteq!( vec![4, 4, 4, 4, 8, 8, 8], getfragmentcapacities(&veccustom) ); asserteq!(vec![4, 4, 4, 4, 8, 8, 3], getfragmentlengths(&veccustom)); ```