Crate orx_fixed_vec

Expand description

§orx-fixed-vec

An efficient fixed capacity vector with pinned element guarantees.

A FixedVec implements PinnedVec; you may read the detailed information about pinned element guarantees and why they are useful in the motivation-and-examples section. In brief, a pinned vector does not allow implicit changes in memory locations of its elements; such as moving the entire vector to another memory location due to additional capacity requirement.

This is no-std crate.

§Fixed Vector

A FixedVec is simply a wrapper around the standard vector with the following two key differences:

It is always created with an initial fixed capacity which cannot implicitly change.
If we add more elements than the fixed capacity, the vector panics.

This leads to the following properties:

Its implementation is uninteresting as it does nothing but exposes standard vector methods.
For the very same reason, it is as performant as the standard vector; details can be found at the benches folder.
It satisfies the pinned element guarantees, and hence, it implements PinnedVec unlike the standard vector.

Using a fixed capacity vector has limited use cases as this information is usually not available in situations where we use a vector. Therefore, we more frequently use the SplitVec as a dynamic capacity vector with pinned element guarantees. FixedVec, on the other hand, must be used only when we have the perfect knowledge on the upper bound of vector length.

In order to illustrate, consider an operation where we compute n outputs from n inputs; i.e., we map each element to a new element. Further, we want to collect or write the results in a new vector. In this case, we could safely use a FixedVec created with a capacity of n elements. This is exactly the parallel iterator Par does under the hood when the length of the output is known with certainty. In other situations, SplitVec is used as the pinned vector.

§Parallelization

FixedVec implements ConcurrentCollection.

Therefore, when orx_parallel crate is included, FixedVec also automatically implements ParallelizableCollection.

This means that computations over the fixed vector can be efficiently parallelized:

fixed_vec.par() returns a parallel iterator over references to its elements, and
fixed_vec.into_par() consumes the vector and returns a parallel iterator of the owned elements.

You may find demonstrations in demo_parallelization and bench_parallelization examples.

§Examples

FixedVec api resembles and aims to cover as much as possible the standard vector’s api.

use orx_fixed_vec::prelude::*;

// capacity is not optional
let mut vec = FixedVec::new(4);

assert_eq!(4, vec.capacity());

vec.push(0);
assert!(!vec.is_full());
assert_eq!(3, vec.room());

vec.extend_from_slice(&[1, 2, 3]);
assert_eq!(vec, &[0, 1, 2, 3]);
assert!(vec.is_full());

// vec.push(42); // push would've panicked when vec.is_full()

vec[0] = 10;
assert_eq!(10, vec[0]);

vec.remove(0);
vec.insert(0, 0);

assert_eq!(6, vec.iter().sum());

assert_eq!(vec.clone(), vec);

assert_eq!(&vec, &[0, 1, 2, 3]);

// allows zero-cost conversion into and from std Vec
let _std_vec: Vec<_> = vec.into();

Its main difference and objective is to provide pinned element guarantees as demonstrated in the example below.

use orx_fixed_vec::prelude::*;

let mut vec = FixedVec::new(100);

// push the first element
vec.push(42usize);
assert_eq!(vec, &[42]);

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

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

for i in 0..100 {
    assert_eq!(if i == 0 { 42 } else { i }, vec[i]);
}

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

// we can safely dereference it and read the correct value
// dereferencing is still unsafe for FixedVec,
// but the underlying guarantee will be used by wrappers such as ImpVec or SelfRefCol
assert_eq!(unsafe { *addr42 }, 42);

// the next push when `vec.is_full()` panics!
// vec.push(0);

§Contributing

Contributions are welcome! If you notice an error, have a question or think something could be improved, please open an issue or create a PR.

§License

Dual-licensed under Apache 2.0 or MIT.

Modules§

prelude: Common relevant traits, structs, enums.

Structs§

ConcurrentFixedVec: Concurrent wrapper (orx_pinned_vec::ConcurrentPinnedVec) for the FixedVec.
FixedVec: A fixed vector, FixedVec, is a vector with a strict predetermined capacity (see SplitVec for dynamic capacity version).

Enums§

PinnedVecGrowthError: Error occurred during an attempt to increase capacity of the pinned vector.

Traits§

Collection: A collection providing the iter method which returns an iterator over shared references of elements of the collection.
CollectionMut: A mutable collection providing the iter_mut method which returns an iterator over mutable references of elements of the collection.
ConcurrentPinnedVec: A wrapper for a pinned vector which provides additional guarantees for concurrent programs.
IntoConcurrentPinnedVec: A pinned vector which can be wrapped into a concurrent pinned vector.
Iterable: An Iterable is any type which can return a new iterator that yields elements of the associated type Item every time iter method is called.
PinnedVec: Trait for vector representations differing from std::vec::Vec by the following:

Crate orx_fixed_vecCopy item path