1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
//! # 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
//!     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
//!
//! ```rust
//! 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);
//! }
//!
//! ```

#![warn(missing_docs)]

// Pull in serde if `impl_serialize` is enabled
#[cfg(feature = "impl_serialize")]
use serde;

// Pull in serde_json for testing if `impl_serialize` is enabled
#[cfg(all(test, feature = "impl_serialize"))]
use serde_json;

mod cell;
pub mod map;
pub mod set;
pub mod list;
mod arena;
mod bloom;
mod impl_partial_eq;
mod impl_debug;

#[cfg(feature = "impl_serialize")]
mod impl_serialize;

pub use self::arena::{Arena, Uninitialized, NulTermStr};
pub use self::cell::CopyCell;