Crate granite[][src]

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

  • tinyvec — ^1.2
  • arrayvec^0.5
  • smallvec^1.4
  • slab^0.4
  • slotmap^0.4

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

Feature flags

  • alloc (enabled by default) — enables support for Vec and VecDeque from the standard library, while keeping the crate no_std. Requires a functional global allocator, though only at runtime and not at compile time.
  • tinyvec — enables support for ArrayVec, SliceVec and TinyVec from the tinyvec crate, often preferred over arrayvec and smallvec.
  • arrayvec — enables support for ArrayVec. You probably should use tinyvec instead.
  • smallvec — enables support for SmallVec. You probably should use tinyvec instead.
  • slab — enables support for Slab.
  • slotmap — enables support for SlotMap, HopSlotMap and DenseSlotMap. Slab will likely be faster because it’s not versioned; this feature is largely here for compatibility.
  • union_optimizations — forwarded to Granite, adds some layout optimizations by using untagged unions, decreasing memory usage in SparseStorage. Requires a nightly compiler (see tracking issue for RFC 2514) and thus is disabled by default.

Modules

chain

A list data structure wrapping a list of lists used to prevent lag spikes when dealing with huge numbers of elements.

Structs

Chain

A list data structure wrapping a list of lists used to prevent lag spikes when dealing with huge numbers of elements.

DummyMoveFix

Wrapper around a type which implements MoveFix by doing nothing when notified.

SparseStorage

A wrapper around a list-like storage type which considerably improves performance when removing elements.

SparseStorageSlot

A slot inside a sparse storage.

Traits

IntoMutIterator

Types which have corresponding mutably borrowing iterators.

IntoRefIterator

Types which have corresponding immutably borrowing iterators.

List

Trait alias for list-like containers which support indexing, addition and removal of elements and iteration.

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.

SparseVecalloc

A Vec wrapped in SparseStorage.

SparseVecDequealloc

A VecDeque wrapped in SparseStorage.