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;