Struct orx_split_vec::FragmentGrowth

source ·

pub struct FragmentGrowth { /* private fields */ }

Expand description

Growth policy of fragments in a split vector.

A policy can be defined by one of the three constructors.

FragmentGrowth::exponential(initial_capacity, capacity_multiplier)
- capacity of the f-th fragment will be computed as initial_capacity * capacity_multiplier^f.
FragmentGrowth::constant(constant_fragment_length)
- capacity of all fragments will be equal to constant_fragment_length, leading to a linear growth.
FragmentGrowth::by_function(get_capacity_of_fragment)
- capacity of the f-th fragment will be computed as get_capacity_of_fragment(f);
- any custom growth policy can be represented by this functional form.

Implementations§

source §

impl FragmentGrowth

source

pub fn exponential(initial_capacity: usize, capacity_multiplier: f32) -> Self

Creates an exponential growth policy with the given positive coefficients.

The capacity of the f-th fragment will be computed as:

initial_capacity * capacity_multiplier^f

Panics

Panics when:

initial_capacity is nonpositive, or
capacity_multiplier is nonpositive;

as either of these cases would lead to zero capacity allocations for growth.

Examples

Below example demonstrates an exponential growth with a multiplier of 1.5.

use orx_split_vec::{FragmentGrowth, SplitVec};

let growth = FragmentGrowth::exponential(4, 1.5);
let mut vec = SplitVec::with_growth(growth);

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

vec.extend_from_slice(&[0, 1, 2, 3, 4]);
assert_eq!(5, vec.len());
assert_eq!(4 + 6, vec.capacity());

vec.extend_from_slice(&[0, 1, 2, 3, 4]);
assert_eq!(10, vec.len());
assert_eq!(4 + 6, vec.capacity());

vec.push(42);
assert_eq!(11, vec.len());
assert_eq!(4 + 6 + 9, vec.capacity());
assert_eq!(4, vec.fragments()[0].capacity());
assert_eq!(6, vec.fragments()[1].capacity());
assert_eq!(9, vec.fragments()[2].capacity());

One can also allocate the same amount of memory every time new capacity is required.

use orx_split_vec::{FragmentGrowth, SplitVec};

let growth = FragmentGrowth::exponential(10, 1.0);
let mut vec = SplitVec::with_growth(growth);

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

for x in 0..10 {
    vec.push(x);
}

assert_eq!(10, vec.len());
assert_eq!(10, vec.capacity());

vec.push(42);
assert_eq!(11, vec.len());
assert_eq!(20, vec.capacity());
for fragment in vec.fragments() {
    assert_eq!(10, fragment.capacity());
}

source

pub fn constant(constant_fragment_length: usize) -> Self

Creates a constant growth policy where every fragment will have the same length; i.e., constant_fragment_length.

Note that FragmentGrowth::constant(10) is a shorthand for FragmentGrowth::exponential(10, 1.0).

Panics

Panics when:

constant_fragment_length is nonpositive

as ot would lead to zero capacity allocations for growth.

Examples

use orx_split_vec::{FragmentGrowth, SplitVec};

let growth = FragmentGrowth::constant(10);
let mut vec = SplitVec::with_growth(growth);

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

for x in 0..10 {
    vec.push(x);
}

assert_eq!(10, vec.len());
assert_eq!(10, vec.capacity());

vec.push(42);
assert_eq!(11, vec.len());
assert_eq!(20, vec.capacity());
for fragment in vec.fragments() {
    assert_eq!(10, fragment.capacity());
}

source

pub fn by_function(get_capacity_of_fragment: Rc<dyn Fn(usize) -> usize>) -> Self

Creates a growth policy function where the capacities are computed by the given function.

The capacity of the f-th fragment will be computed as:

get_capacity_by_fragment(f)

Examples

One interesting policy could be to increase the fragment lengths until it reaches a particular level. Then, each expansion could be a constant expansion.

use orx_split_vec::{FragmentGrowth, SplitVec};
use std::rc::Rc;

fn get_fragment_capacity(fragment: usize) -> usize {
    let exp = (4.0 * f32::powf(1.5, fragment as f32)) as usize;
    exp.min(10)
}
let growth = FragmentGrowth::by_function(Rc::new(get_fragment_capacity));
let mut vec = SplitVec::with_growth(growth);

for i in 0..1000 {
    vec.push(i);
}

assert_eq!(4, vec.fragments()[0].capacity());
assert_eq!(6, vec.fragments()[1].capacity());
assert_eq!(9, vec.fragments()[2].capacity());
assert_eq!(10, vec.fragments()[3].capacity());
for fragment in vec.fragments().iter().skip(4) {
    assert_eq!(10, fragment.capacity());
}