Crate sized_chunks
source · [−]Expand description
Sized Chunks
This crate contains three fixed size low level array like data structures, primarily intended for use in immutable.rs, but fully supported as a standalone crate.
Their sizing information is encoded in the type using the
typenum crate, which you may want to take a look at before
reading on, but usually all you need to know about it is that it provides
types U1 to U128 to represent numbers, which the data types take as type
parameters, eg. SparseChunk<A, U32> would give you a sparse array with
room for 32 elements of type A. You can also omit the size, as they all
default to a size of 64, so SparseChunk<A> would be a sparse array with a
capacity of 64.
All data structures always allocate the same amount of space, as determined by their capacity, regardless of how many elements they contain, and when they run out of space, they will panic.
Data Structures
| Type | Description | Push | Pop | Deref to &[A] |
|---|---|---|---|---|
Chunk | Contiguous array | O(1)/O(n) | O(1) | Yes |
RingBuffer | Non-contiguous array | O(1) | O(1) | No |
SparseChunk | Sparse array | N/A | N/A | No |
The Chunk and RingBuffer are very similar in
practice, in that they both work like a plain array, except that you can
push to either end with some expectation of performance. The difference is
that RingBuffer always allows you to do this in constant
time, but in order to give that guarantee, it doesn’t lay out its elements
contiguously in memory, which means that you can’t dereference it to a slice
&[A].
Chunk, on the other hand, will shift its contents around when
necessary to accommodate a push to a full side, but is able to guarantee a
contiguous memory layout in this way, so it can always be dereferenced into
a slice. Performance wise, repeated pushes to the same side will always run
in constant time, but a push to one side followed by a push to the other
side will cause the latter to run in linear time if there’s no room (which
there would only be if you’ve popped from that side).
To choose between them, you can use the following rules:
- I only ever want to push to the back: you don’t need this crate, try
ArrayVec. - I need to push to either side but probably not both on the same array: use
Chunk. - I need to push to both sides and I don’t need slices: use
RingBuffer. - I need to push to both sides but I do need slices: use
Chunk.
Finally, SparseChunk is a more efficient version of
Vec<Option<A>>: each index is either inhabited or not, but instead of
using the Option discriminant to decide which is which, it uses a compact
bitmap. You can also think of SparseChunk<A, N> as a BTreeMap<usize, A>
where the usize must be less than N, but without the performance
overhead. Its API is also more consistent with a map than an array - there’s
no push, pop, append, etc, just insert, remove and lookup.
InlineArray
Finally, there’s InlineArray, which is a simple vector that’s
sized to fit inside any Sized type that’s big enough to hold a size counter
and at least one instance of the array element type. This can be a useful
optimisation when implementing a list like data structure with a nontrivial
set of pointers in its full form, where you could plausibly fit several
elements inside the space allocated for the pointers. im::Vector is a
good example of that, and the use case for which InlineArray
was implemented.
Feature Flags
The following feature flags are available:
| Feature | Description |
|---|---|
arbitrary | Provides Arbitrary implementations from the arbitrary crate. Requires the std flag. |
refpool | Provides PoolDefault and PoolClone implemetations from the refpool crate. |
ringbuffer | Enables the RingBuffer data structure. |
std | Without this flag (enabled by default), the crate will be no_std, and absent traits relating to std::collections and std::io. |
Re-exports
pub use crate::inline_array::InlineArray;pub use crate::sized_chunk::Chunk;pub use crate::sparse_chunk::SparseChunk;pub use crate::ring_buffer::RingBuffer;Modules
A fixed capacity array sized to match some other type T.
A fixed capacity ring buffer.
A fixed capacity smart array.
A fixed capacity sparse array.