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 enums and find yourself in pain having to put everything in Boxes all the time.

Features

• Paginated Arena: internally preallocates 64KiB pages on the heap and allows Copy types to be put on that heap.

• CopyCell: virtually identical to std::cell::Cell but requires that internal types implement Copy, and implements Copy itself.

• List, Map and Set: your basic data structures that allocate on the Arena and use internal mutability via CopyCell. Never worry about sharing pointers again!

• BloomMap and BloomSet: special variants of Map and Set 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 regular Map or Set is also minimal.

• All data structures implement expected traits, such as Debug or PartialEq.

• 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 Copy types.
list	A linked list and auxiliary types that can be used with the Arena.
map	Maps of keys to values that can be used with the Arena.
set	Sets of values that can be used with the Arena.

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.