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 Arena;
use Map;
// Only `Copy` types can be allocated on the `Arena`!
Benches
Here is a very biased benchmark of the different sets:
running 8 tests
test bloom_set_create ... bench: 49 ns/iter (+/- 0)
test bloom_set_read ... bench: 181 ns/iter (+/- 10)
test fxhash_set_create ... bench: 86 ns/iter (+/- 1)
test fxhash_set_read ... bench: 312 ns/iter (+/- 4)
test hash_set_create ... bench: 152 ns/iter (+/- 94)
test hash_set_read ... bench: 1,105 ns/iter (+/- 1)
test set_create ... bench: 37 ns/iter (+/- 0)
test set_read ... bench: 440 ns/iter (+/- 1)
set
andbloom_set
are benchmarks ofSet
andBloomSet
from this crate.hash_set
is the default stdlibHashSet
.fxhash_set
is aHashSet
using thefxhash
crate hash.
License
This crate is distributed under the terms of both the MIT license and the Apache License (Version 2.0). Choose whichever one works best for you.
See LICENSE-APACHE and LICENSE-MIT for details.