[−][src]Crate bucket_vec
Bucket Vector
100% unsafe
Rust free!
Description
A vector-like data structure that organizes its elements into a set of buckets of fixed-capacity in order to guarantee that mutations to the bucket vector never moves elements and thus invalidates references to them.
This is comparable to a Vec<Box<T>>
but a lot more efficient.
Under the Hood
The BucketVec
is really just a vector of Bucket
instances.
Whenever an element is pushed to the BucketVec
the element is pushed onto
the last Bucket
if it isn't filled, yet.
If the last Bucket
is filled a new Bucket
is pushed onto the BucketVec
with a new capacity determined by the used bucket vector configuration.
This way the BucketVec
never moves elements around upon inserting new elements
in order to preserve references. When a normal Vec
is modified it can potentially
invalidate references because of reallocation of the internal buffer which
might cause severe bugs if references to the internal elements are stored
outside the Vec
. Note that normally Rust prevents such situations so the
BucketVec
is mainly used in the area of unsafe
Rust where a developer
actively decides that they want or need pinned references into another data
structure.
For the same reasons as stated above the BucketVec
does not allow to remove
or swap elements.
Example
Looking at an example BucketVec<i32>
with the following configuration:
start_capacity := 1
growth_rate := 2
We have already pushed the elements A
,.., K
onto it.
[ [A], [B, C], [D, E, F, G], [H, I, J, K, _, _, _, _] ]
Where _
refers to a vacant bucket entry.
Pushing another L
,.., O
onto the same BucketVec
results in:
[ [A], [B, C], [D, E, F, G], [H, I, J, K, L, M, N, O] ]
So we are full on capacity for all buckets.
The next time we push another element onto the BucketVec
it will create a new Bucket
with a capacity of 16
since growth_rate == 2
and our current latest bucket already has a capacity of 8
.
[ [A], [B, C], [D, E, F, G], [H, I, J, K, L, M, N, O], [P, 15 x _] ]
Where 15 x _
denotes 15 consecutive vacant entries.
Structs
Access | Accessor into a recently pushed element. |
BucketVec | A vector-like data structure that never moves its contained elements. |
Iter | An iterator over the elements of a bucket vector. |
Enums
DefaultConfig | The default configuration for bucket vectors. |
Traits
BucketVecConfig | Basic configs of a bucket vector. |