Granite

Crates.io Docs.rs Checks and tests Minimal Supported Rust Version

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.

Public dependencies

PRs are welcome from those interested in those version numbers being modified.

Feature flags