Struct orx_concurrent_vec::Recursive

pub struct Recursive;

Equivalent to Doubling strategy except for the following:

• enables zero-cost (no-ops) append operation:
  • we can append standard vectors, vectors of vectors, split vectors, etc., any data that implements IntoFragments trait,
  • by simply accepting it as a whole fragment,
  • according to benchmarks documented in the crate definition:
    • SplitVec<_, Recursive> is infinitely faster than other growth strategies or standard vector :)
    • since its time complexity is independent of size of the data to be appended.
• at the expense of providing slower random-access performance:
  • random access time complexity of Doubling strategy is constant time;
  • that of Recursive strategy is linear in the number of fragments;
  • according to benchmarks documented in the crate definition:
    • SplitVec<_, Doubling> or standard vector are around 4 to 7 times faster than SplitVec<_, Recursive>,
    • and 1.5 times faster when the elements get very large (16 x u64).

Note that other operations such as serial access are equivalent to Doubling strategy.

Examples

use orx_split_vec::*;

// SplitVec<usize, Recursive>
let mut vec = SplitVec::with_recursive_growth();

vec.push('a');
assert_eq!(vec, &['a']);

vec.append(vec!['b', 'c']);
assert_eq!(vec, &['a', 'b', 'c']);

vec.append(vec![vec!['d'], vec!['e', 'f']]);
assert_eq!(vec, &['a', 'b', 'c', 'd', 'e', 'f']);

let other_split_vec: SplitVec<_> = vec!['g', 'h'].into();
vec.append(other_split_vec);
assert_eq!(vec, &['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']);

Trait Implementations

impl Clone for Recursive

fn clone(&self) -> Recursive

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for Recursive

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

Formats the value using the given formatter.

impl Default for Recursive

fn default() -> Recursive

Returns the “default value” for a type.

impl Growth for Recursive

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 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.

fn required_fragments_len<T>( &self, fragments: &[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. Returns the error if it the growth strategy does not allow the required number of fragments.

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).

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

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

impl PartialEq for Recursive

fn eq(&self, other: &Recursive) -> 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 Recursive