Crate toolshed [−] [src]
Toolshed
This crate contains an Arena
allocator, along with a few common data
structures that can be used in tandem with it.
For all those times when you need to create a recursively nested tree
of enum
s and find yourself in pain having to put everything in
Box
es all the time.
Features
Paginated
Arena
: internally preallocates 64KiB pages on the heap and allowsCopy
types to be put on that heap.CopyCell
: virtually identical tostd::cell::Cell
but requires that internal types implementCopy
, and implementsCopy
itself.List
,Map
andSet
: your basic data structures that allocate on theArena
and use internal mutability viaCopyCell
. Never worry about sharing pointers again!BloomMap
andBloomSet
: special variants ofMap
andSet
with a very simple but very fast bloom filter. If a map / set is often queried for keys / elements it doesn't contain, the bloom filter check will reduce the need to do a full tree lookup, greatly increasing performance. The overhead compared to a regularMap
orSet
is also minimal.All data structures implement expected traits, such as
Debug
orPartialEq
.Optional serde
Serialize
support behind a feature flag.
Example
extern crate toolshed; use toolshed::Arena; use toolshed::map::Map; // Only `Copy` types can be allocated on the `Arena`! #[derive(Debug, PartialEq, Clone, Copy)] enum Foo<'arena> { Integer(u64), // Recursive enum without `Box`es! Nested(&'arena Foo<'arena>), } fn main() { // Create a new arena let arena = Arena::new(); // The reference will live until `arena` goes out of scope let child = arena.alloc(Foo::Integer(42)); let parent = arena.alloc(Foo::Nested(child)); // Empty map does not allocate let map = Map::new(); // Inserting stuff in the map requires a reference to the `Arena`. // The reference can be shared, since `Arena` uses interior mutability. map.insert(&arena, "child", child); // We can put our `map` on the arena as well. let map: &Map<&str, &Foo> = arena.alloc(map); // Each insert allocates a small chunk of data on the arena. Since arena is // preallocated on the heap, these inserts are very, very fast. // // We only have a non-mutable reference to `map` now, however `Map` is also // using interior mutability on references to allow exactly this kind of // behavior in a safe manner. map.insert(&arena, "parent", parent); assert_eq!(map.get("child"), Some(&Foo::Integer(42))); assert_eq!(map.get("parent"), Some(&Foo::Nested(&Foo::Integer(42)))); assert_eq!(map.get("heh"), None); }
Reexports
pub use cell::CopyCell; |
Modules
cell |
A mutable memory location for |
list |
A linked list and auxiliary types that can be used with the |
map |
Maps of keys to values that can be used with the |
set |
Sets of values that can be used with the |
Structs
Arena |
An arena implementation that uses preallocated 64KiB pages for all allocations. If a new allocation were to be pushed over the the boundaries of the page, a new page is internally allocated first, thus this version of the arena can never run out of memory unless the process runs out of heap altogether. |