Struct bucket_vec::BucketVec

pub struct BucketVec<T, C = DefaultConfig> { /* fields omitted */ }

A vector-like data structure that never moves its contained elements.

This is solved by using internal fixed-capacity buckets instead of boxing all elements in isolation.

Formulas

Definitions

In the following we define

• N := START_CAPACITY and
• a := GROWTH_RATE

Bucket Capacity

For a != 1:

The total capacity of all buckets until bucket i (not including i) is expressed as:

capacity_until(i) := N * (a^i - 1) / (a-1)

The capacity of the ith bucket is then calculated by:

capacity(i) := floor(capacity_until(i+1)) - floor(capacity_until(i))

Where floor: f64 -> f64 rounds the f64 down to the next even f64 for positive f64.

Note that capacity(i) is approximately capacity(i)' := N * a^i.

For a == 1:

This case is trivial and all buckets are equally sized to have a capacity of N.

Accessing Elements by Index

Accessing the ith element of a BucketVec can be expressed by the following formulas:

For a != 1:

First we define the inverted capacity function for which 1 == capacity(i) * inv_capacity(i) forall i.

inv_capacity(i) = ceil(log(1 + (i + 1) * (a - 1) / N, a)) - 1

Where ceil: f64 -> f64 rounds the f64 up to the next even f64 for positive f64.

Having this the bucket_index and the entry_index inside the bucket indexed by bucket_index is expressed as:

bucket_index(i) = inv_capacity(i)
entry_index(i) = i - floor(capacity_until(bucket_index(i)))

For a == 1:

This case is very easy and we can simply calculate the bucket_index and entry_index by:

bucket_index(i) = i / N
entry_index(i) = i % N

Methods

impl<T, C> BucketVec<T, C>

pub fn new() -> Self

Creates a new empty bucket vector.

Note

This does not allocate any heap memory.

pub fn len(&self) -> usize

Returns the number of elements stored in the bucket vector.

pub fn is_empty(&self) -> bool

Returns true if the bucket vector is empty.

Important traits for Iter<'a, T>

impl<'a, T> Iterator for Iter<'a, T> type Item = &'a T;

pub fn iter(&self) -> Iter<T>

Returns an iterator that yields shared references to the elements of the bucket vector.

Important traits for IterMut<'a, T>

impl<'a, T> Iterator for IterMut<'a, T> type Item = &'a mut T;

pub fn iter_mut(&mut self) -> IterMut<T>

Returns an iterator that yields exclusive reference to the elements of the bucket vector.

pub fn first(&self) -> Option<&T>

Returns a shared reference to the first element of the bucket vector.

pub fn first_mut(&mut self) -> Option<&mut T>

Returns an exclusive reference to the first element of the bucket vector.

pub fn last(&self) -> Option<&T>

Returns a shared reference to the last element of the bucket vector.

pub fn last_mut(&mut self) -> Option<&mut T>

Returns an exclusive reference to the last element of the bucket vector.

impl<T, C> BucketVec<T, C> where
    C: BucketVecConfig, 

pub fn get(&self, index: usize) -> Option<&T>

Returns a shared reference to the element at the given index if any.

pub fn get_mut(&mut self, index: usize) -> Option<&mut T>

Returns an exclusive reference to the element at the given index if any.

pub fn push(&mut self, new_value: T)

Pushes a new element onto the bucket vector.

Note

This operation will never move other elements, reallocates or otherwise invalidate pointers of elements contained by the bucket vector.

pub fn push_get(&mut self, new_value: T) -> Access<T>

Pushes a new element onto the bucket vector and returns access to it.

Note

This operation will never move other elements, reallocates or otherwise invalidate pointers of elements contained by the bucket vector.

Trait Implementations

impl<T, C> Clone for BucketVec<T, C> where
    T: Clone, 

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug, C: Debug> Debug for BucketVec<T, C>

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<T, C> Decode for BucketVec<T, C> where
    C: BucketVecConfig,
    T: Decode, 

fn decode<I: Input>(input: &mut I) -> Result<Self, Error>

Attempt to deserialise the value from input.

impl<T> Default for BucketVec<T, DefaultConfig>

fn default() -> Self

Returns the "default value" for a type.

impl<T, C> Encode for BucketVec<T, C> where
    T: Encode, 

fn encode_to<O: Output>(&self, output: &mut O)

Convert self to a slice and append it to the destination.

fn size_hint(&self) -> usize

If possible give a hint of expected size of the encoding.

fn encode(&self) -> Vec<u8>

Convert self to an owned vector.

fn using_encoded<R, F>(&self, f: F) -> R where
    F: FnOnce(&[u8]) -> R, 

Convert self to a slice and then invoke the given closure with it.

impl<T, C> Eq for BucketVec<T, C> where
    T: Eq, 

impl<T, C> Extend<T> for BucketVec<T, C> where
    C: BucketVecConfig, 

fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

impl<T, C> FromIterator<T> for BucketVec<T, C> where
    C: BucketVecConfig, 

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

Creates a value from an iterator.

impl<T, C> Hash for BucketVec<T, C> where
    T: Hash, 

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given [Hasher].

fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given [Hasher].

impl<T, C> IntoIterator for BucketVec<T, C>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, T, C> IntoIterator for &'a BucketVec<T, C>

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, T, C> IntoIterator for &'a mut BucketVec<T, C>

type Item = &'a mut T

The type of the elements being iterated over.

type IntoIter = IterMut<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T, C> Ord for BucketVec<T, C> where
    T: Ord, 

fn cmp(&self, other: &Self) -> Ordering

This method returns an [Ordering] between self and other.

#[must_use] fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

#[must_use] fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

#[must_use] fn clamp(self, min: Self, max: Self) -> Self

🔬 This is a nightly-only experimental API. (clamp)

Restrict a value to a certain interval.

impl<T, C> PartialEq<BucketVec<T, C>> for BucketVec<T, C> where
    T: PartialEq, 

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

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

#[must_use] fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl<T, C> PartialOrd<BucketVec<T, C>> for BucketVec<T, C> where
    T: PartialOrd, 

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

#[must_use] fn lt(&self, other: &Rhs) -> bool

This method tests less than (for self and other) and is used by the < operator.

#[must_use] fn le(&self, other: &Rhs) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

#[must_use] fn gt(&self, other: &Rhs) -> bool

This method tests greater than (for self and other) and is used by the > operator.

#[must_use] fn ge(&self, other: &Rhs) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.