Struct orx_concurrent_vec::Doubling

pub struct Doubling;

Strategy which allows creates a fragment with double the capacity of the prior fragment every time the split vector needs to expand.

Assuming it is the common case compared to empty vector scenarios, it immediately allocates the first fragment to keep the SplitVec struct smaller.

Examples

use orx_split_vec::*;

// SplitVec<usize, Doubling>
let mut vec = SplitVec::with_doubling_growth();

assert_eq!(1, vec.fragments().len());
assert_eq!(Some(4), vec.fragments().first().map(|f| f.capacity()));
assert_eq!(Some(0), vec.fragments().first().map(|f| f.len()));

// fill the first 5 fragments
let expected_fragment_capacities = vec![4, 8, 16, 32];
let num_items: usize = expected_fragment_capacities.iter().sum();
for i in 0..num_items {
    vec.push(i);
}

assert_eq!(
    expected_fragment_capacities,
    vec.fragments()
    .iter()
    .map(|f| f.capacity())
    .collect::<Vec<_>>()
);
assert_eq!(
    expected_fragment_capacities,
    vec.fragments().iter().map(|f| f.len()).collect::<Vec<_>>()
);

// create the 6-th fragment doubling the capacity
vec.push(42);
assert_eq!(
    vec.fragments().len(),
    expected_fragment_capacities.len() + 1
);

assert_eq!(vec.fragments().last().map(|f| f.capacity()), Some(32 * 2));
assert_eq!(vec.fragments().last().map(|f| f.len()), Some(1));

Trait Implementations

impl Clone for Doubling

fn clone(&self) -> Doubling

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Doubling

fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter.

impl Default for Doubling

fn default() -> Doubling

Returns the “default value” for a type.

impl Growth for Doubling

unsafe fn get_ptr_mut<T>( &self, fragments: &mut [Fragment<T>], index: usize ) -> Option<*mut T>

O(1) Returns a mutable reference to the index-th element of the split vector of the fragments.

Returns None if index-th position does not belong to the split vector; i.e., if index is out of cumulative capacity of fragments.

Safety

This method allows to write to a memory which is greater than the split vector’s length. On the other hand, it will never return a pointer to a memory location that the vector does not own.

fn required_fragments_len<T>( &self, _: &[Fragment<T>], maximum_capacity: usize ) -> Result<usize, String>

Returns the number of fragments with this growth strategy in order to be able to reach a capacity of maximum_capacity of elements.

This method is relevant and useful for concurrent programs, which helps in avoiding the fragments to allocate.

Panics

Panics if maximum_capacity is greater than sum { 2^f | for f in 2..34 }.

fn new_fragment_capacity<T>(&self, fragments: &[Fragment<T>]) -> usize

Given that the split vector contains the given fragments, returns the capacity of the next fragment.

fn get_fragment_and_inner_indices<T>( &self, vec_len: usize, _fragments: &[Fragment<T>], element_index: usize ) -> Option<(usize, usize)>

O(fragments.len()) Returns the location of the element with the given element_index on the split vector as a tuple of (fragment-index, index-within-fragment).

fn maximum_concurrent_capacity<T>( &self, fragments: &[Fragment<T>], fragments_capacity: usize ) -> usize

Returns the maximum number of elements that can safely be stored in a concurrent program.

impl GrowthWithConstantTimeAccess for Doubling

fn get_fragment_and_inner_indices_unchecked( &self, element_index: usize ) -> (usize, usize)

O(1) Returns the location of the element with the given element_index on the split vector as a tuple of (fragment-index, index-within-fragment).

unsafe fn get_ptr_mut<T>( &self, fragments: &mut [Fragment<T>], index: usize ) -> Option<*mut T>

O(1) Returns a mutable reference to the index-th element of the split vector of the fragments.

impl PartialEq for Doubling

fn eq(&self, other: &Doubling) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl StructuralPartialEq for Doubling