[−][src]Crate granite
Generic backing storage framework for building arena-allocated data structures.
Overview
Unlike many other languages, Rust is not very friendly to naive implementations of data structures based on smart pointers. The most you can represent with Rc
/Arc
is a directed acyclic graph (DAG), and the second word in that somewhat cryptic abbreviation hints why: you'll be running into cycles between the pointers, which will prevent the whole structure from ever being dropped, leaking both the memory for the nodes and their user-defined contents. The only way you can solve this is by using garbage collection, or by dropping every single element manually, while keeping track of the collection's not-yet-dropped nodes, which would require an elaborate algorithm and runtime overhead to match.
Also, performing separate memory allocations for every single element is horribly slow and unfriendly to cache locality, not unlike the universally despised LinkedList
. So much for the zero-cost abstraction that Rust strives to achieve.
Enter arena-allocated data structures: a way to have data structures backed by Vec
, which provides excellent cache locality and performs bulk allocations.
Unlike smart pointer data structures, arena allocated data structures do not store any pointers. Instead, they store keys. A key is an identifier of an element within the backing storage, unique in the scope of one instance of the backing storage. Keys may overlap between multiple storages and between an element which existed at some point but has been removed, but they may not overlap among elements coexisting in one point of time in one collection.
Feature flags
alloc
(enabled by default) — enables support forVec
andVecDeque
from the standard library, while keeping the crateno_std
. Requires a functional global allocator.arrayvec
(enabled by default) — enables support forArrayVec
.smallvec
(enabled by default) — enables support forSmallVec
.slab
(enabled by default) — enables support for [Slab
].slotmap
— enables support for [SlotMap
]. [Slab
] will likely be faster because it's not versioned, so this is disabled by default.
Structs
DummyMoveFix | Wrapper around a type which implements |
SparseStorage | A wrapper around a list-like storage type which considerably improves performance when removing elements. |
SparseStorageSlot | A slot inside a sparse storage. |
Traits
ListStorage | Trait for list-like containers which can be the backing storage for data structures. |
MoveFix | Trait for data structure element types to be able to correct indices towards other elements when they are moved around in the collection. |
Storage | Trait for various kinds of containers which can be the backing storage for data structures. |
Type Definitions
DefaultStorage | The default storage type used by data structures when a storage type is not provided. |
SparseVec | alloc A |
SparseVecDeque | alloc A |