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. Memory location of an item added to the split vector will never change unless it is removed from the vector or the vector is dropped.

Why - Actually

The main feature of SplitVec is that it guarantees that the memory locations of its elements will never change.

Together with rust's ownership model, this turns out to be a useful property and makes SplitVec the underlying model of other useful data structures.

See orx-imp-vec for an example.

Pinned elements

```rust use orxsplitvec::SplitVec;

fn main() { let mut vec = SplitVec::withlineargrowth(10);

// split vec with 1 item in 1 fragment
vec.push(42usize);
assert_eq!(&[42], &vec);
assert_eq!(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.into_iter().enumerate() {
    assert_eq!(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);

} ```

Why - Also

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

It is useful, however, for building a collection where:

• there is a large uncertainty in the expected ultimate 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.

Flexible growth strategies without copies

```rust fn main() { use orxsplitvec::{Fragment, SplitVec, SplitVecGrowth}; use std::rc::Rc;

fn custom_growth_fun<T>(fragments: &[Fragment<T>]) -> usize {
    if fragments.len() < 4 {
        4
    } else {
        8
    }
}
fn get_fragment_capacities<T, G: SplitVecGrowth<T>>(vec: &SplitVec<T, G>) -> Vec<usize> {
    vec.fragments().iter().map(|f| f.capacity()).collect()
}
fn get_fragment_lengths<T, G: SplitVecGrowth<T>>(vec: &SplitVec<T, G>) -> Vec<usize> {
    vec.fragments().iter().map(|f| f.len()).collect()
}

// let's create 4 vectors with different growth strategies
let mut vec_lin = SplitVec::with_linear_growth(10);
let mut vec_dbl = SplitVec::with_doubling_growth(4);
let mut vec_exp = SplitVec::with_exponential_growth(4, 1.5);
let mut vec_custom = SplitVec::with_custom_growth_function(Rc::new(custom_growth_fun));

// and push 35 elements to all vectors
for i in 0..35 {
    vec_lin.push(i);
    vec_dbl.push(i);
    vec_exp.push(i);
    vec_custom.push(i);
}

// # linear: fragments of equal capacities
assert_eq!(vec![10, 10, 10, 10], get_fragment_capacities(&vec_lin));
assert_eq!(vec![10, 10, 10, 5], get_fragment_lengths(&vec_lin));

// # doubling: fragment capacities keep doubling
assert_eq!(vec![4, 8, 16, 32], get_fragment_capacities(&vec_dbl));
assert_eq!(vec![4, 8, 16, 7], get_fragment_lengths(&vec_dbl));

// # exponential: fragment capacities grow exponentially with given growth factor
assert_eq!(vec![4, 6, 9, 13, 19], get_fragment_capacities(&vec_exp));
assert_eq!(vec![4, 6, 9, 13, 3], get_fragment_lengths(&vec_exp));

// # custom: pretty much any growth strategy
assert_eq!(
    vec![4, 4, 4, 4, 8, 8, 8],
    get_fragment_capacities(&vec_custom)
);
assert_eq!(vec![4, 4, 4, 4, 8, 8, 3], get_fragment_lengths(&vec_custom));

} ```