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.

IntoIter

An iterator yielding the elements of a bucket vector by value.

Iter

An iterator yielding shared references to the elements of a bucket vector.

IterMut

An iterator yielding exclusive references to the elements of a bucket vector.

Enums

DefaultConfig

The default configuration for bucket vectors.

Traits

BucketVecConfig

Basic configs of a bucket vector.