[−][src]Struct bucket_vec::BucketVec
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
anda := 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 i
th 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 i
th 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>
[src]
pub fn new() -> Self
[src]
pub fn len(&self) -> usize
[src]
Returns the number of elements stored in the bucket vector.
pub fn is_empty(&self) -> bool
[src]
Returns true
if the bucket vector is empty.
ⓘImportant traits for Iter<'a, T>pub fn iter(&self) -> Iter<T>
[src]
Returns an iterator that yields shared references to the elements of the bucket vector.
ⓘImportant traits for IterMut<'a, T>pub fn iter_mut(&mut self) -> IterMut<T>
[src]
Returns an iterator that yields exclusive reference to the elements of the bucket vector.
pub fn first(&self) -> Option<&T>
[src]
Returns a shared reference to the first element of the bucket vector.
pub fn first_mut(&mut self) -> Option<&mut T>
[src]
Returns an exclusive reference to the first element of the bucket vector.
pub fn last(&self) -> Option<&T>
[src]
Returns a shared reference to the last element of the bucket vector.
pub fn last_mut(&mut self) -> Option<&mut T>
[src]
Returns an exclusive reference to the last element of the bucket vector.
impl<T, C> BucketVec<T, C> where
C: BucketVecConfig,
[src]
C: BucketVecConfig,
pub fn get(&self, index: usize) -> Option<&T>
[src]
Returns a shared reference to the element at the given index if any.
pub fn get_mut(&mut self, index: usize) -> Option<&mut T>
[src]
Returns an exclusive reference to the element at the given index if any.
pub fn push(&mut self, new_value: T)
[src]
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>
[src]
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,
[src]
T: Clone,
fn clone(&self) -> Self
[src]
fn clone_from(&mut self, source: &Self)
1.0.0[src]
impl<T: Debug, C: Debug> Debug for BucketVec<T, C>
[src]
impl<T, C> Decode for BucketVec<T, C> where
C: BucketVecConfig,
T: Decode,
[src]
C: BucketVecConfig,
T: Decode,
impl<T> Default for BucketVec<T, DefaultConfig>
[src]
impl<T, C> Encode for BucketVec<T, C> where
T: Encode,
[src]
T: Encode,
fn encode_to<O: Output>(&self, output: &mut O)
[src]
fn size_hint(&self) -> usize
[src]
fn encode(&self) -> Vec<u8>
[src]
fn using_encoded<R, F>(&self, f: F) -> R where
F: FnOnce(&[u8]) -> R,
[src]
F: FnOnce(&[u8]) -> R,
impl<T, C> Eq for BucketVec<T, C> where
T: Eq,
[src]
T: Eq,
impl<T, C> Extend<T> for BucketVec<T, C> where
C: BucketVecConfig,
[src]
C: BucketVecConfig,
fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)
[src]
impl<T, C> FromIterator<T> for BucketVec<T, C> where
C: BucketVecConfig,
[src]
C: BucketVecConfig,
fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self
[src]
impl<T, C> Hash for BucketVec<T, C> where
T: Hash,
[src]
T: Hash,
fn hash<H: Hasher>(&self, state: &mut H)
[src]
fn hash_slice<H>(data: &[Self], state: &mut H) where
H: Hasher,
1.3.0[src]
H: Hasher,
impl<T, C> IntoIterator for BucketVec<T, C>
[src]
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
[src]
impl<'a, T, C> IntoIterator for &'a BucketVec<T, C>
[src]
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
[src]
impl<'a, T, C> IntoIterator for &'a mut BucketVec<T, C>
[src]
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
[src]
impl<T, C> Ord for BucketVec<T, C> where
T: Ord,
[src]
T: Ord,
fn cmp(&self, other: &Self) -> Ordering
[src]
#[must_use]
fn max(self, other: Self) -> Self
1.21.0[src]
#[must_use]
fn min(self, other: Self) -> Self
1.21.0[src]
#[must_use]
fn clamp(self, min: Self, max: Self) -> Self
[src]
impl<T, C> PartialEq<BucketVec<T, C>> for BucketVec<T, C> where
T: PartialEq,
[src]
T: PartialEq,
impl<T, C> PartialOrd<BucketVec<T, C>> for BucketVec<T, C> where
T: PartialOrd,
[src]
T: PartialOrd,
Auto Trait Implementations
impl<T, C> RefUnwindSafe for BucketVec<T, C> where
T: RefUnwindSafe,
T: RefUnwindSafe,
impl<T, C> Send for BucketVec<T, C> where
T: Send,
T: Send,
impl<T, C> Sync for BucketVec<T, C> where
T: Sync,
T: Sync,
impl<T, C> Unpin for BucketVec<T, C> where
T: Unpin,
T: Unpin,
impl<T, C> UnwindSafe for BucketVec<T, C> where
T: UnwindSafe,
T: UnwindSafe,
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<S> Codec for S where
S: Encode + Decode,
[src]
S: Encode + Decode,
impl<T, X> Decode for X where
T: Decode + Into<X>,
X: WrapperTypeDecode<Wrapped = T>,
[src]
T: Decode + Into<X>,
X: WrapperTypeDecode<Wrapped = T>,
impl<T> DecodeAll for T where
T: Decode,
[src]
T: Decode,
impl<T, X> Encode for X where
T: Encode + ?Sized,
X: WrapperTypeEncode<Target = T>,
[src]
T: Encode + ?Sized,
X: WrapperTypeEncode<Target = T>,
fn size_hint(&self) -> usize
[src]
fn using_encoded<R, F>(&self, f: F) -> R where
F: FnOnce(&[u8]) -> R,
[src]
F: FnOnce(&[u8]) -> R,
fn encode(&self) -> Vec<u8>
[src]
fn encode_to<W>(&self, dest: &mut W) where
W: Output,
[src]
W: Output,
impl<'_, '_, T> EncodeLike<&'_ &'_ T> for T where
T: Encode,
[src]
T: Encode,
impl<'_, T> EncodeLike<&'_ T> for T where
T: Encode,
[src]
T: Encode,
impl<'_, T> EncodeLike<&'_ mut T> for T where
T: Encode,
[src]
T: Encode,
impl<T> EncodeLike<Arc<T>> for T where
T: Encode,
[src]
T: Encode,
impl<T> EncodeLike<Box<T>> for T where
T: Encode,
[src]
T: Encode,
impl<'a, T> EncodeLike<Cow<'a, T>> for T where
T: Encode + ToOwned,
[src]
T: Encode + ToOwned,
impl<T> EncodeLike<Rc<T>> for T where
T: Encode,
[src]
T: Encode,
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<I> IntoIterator for I where
I: Iterator,
[src]
I: Iterator,
type Item = <I as Iterator>::Item
The type of the elements being iterated over.
type IntoIter = I
Which kind of iterator are we turning this into?
fn into_iter(self) -> I
[src]
impl<T> KeyedVec for T where
T: Codec,
[src]
T: Codec,
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
fn to_owned(&self) -> T
[src]
fn clone_into(&self, target: &mut T)
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,