[−][src]Crate toolshed
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
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(); // We allocate first instance of `Foo` in the arena. // // Please note that the `alloc` method returns a `&mut` reference. // Since we want to share our references around, we are going to // dereference and re-reference them to immutable ones with `&*`. let child: &Foo = &*arena.alloc(Foo::Integer(42)); // Next instance of `Foo` will contain the child reference. let parent: &Foo = &*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. Once again we use the `&*` // operation to change the reference to be immutable, just to demonstrate // that our `Map` implementation is perfectly happy with internal mutability. 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); }
Modules
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. |
CopyCell | This should be identical to the |
NulTermStr | A wrapper around a |
Uninitialized | A pointer to an uninitialized region of memory. |