Trove
A cloneable and mergeable, thread local arena allocator.
Trove is designed as a flexible allocator and dynamic borrow checker for immutable datastructures.
The arena keeps every appended value in a fixed memory location, and only deallocates them all at once. This is achieved by using an array of multiple backing vectors, arranged in increasing length, like so:
Cloning and Merging
Arenas can be cloned and merged, this is accopmlished by the top-level Arena
type being a VecMap
mapping increasing ids to sub-arenas. When an arena is cloned, two new sub arenas are created, and given two new ids.
If a mutable borrow is requested through a reference to the old arena, from either of the cloned arenas, it is cloned and put in the new sub-arena, so that the old reference stays valid.
Memory Layout
Each sub-arena has its memory layout arranged like this:
[0, 1]
[2, 3, 4, 5]
[6, 7, 8, 9, 10, 11, 12, 13]
This implementation uses a first row vector size of 32, and the doubling vectors arranged in 32 rows.
This makes sure no re-allocation and moving of entries is possible, and allows us to safely create a RefMut
from an immutable borrow of the arena.