Forked from btree-slab.
You have many b-trees, some of which are very tiny, and want to reduce allocations and increase localization by storing them all in the same memory region.
BTreeMap and BTreeSet with an interface almost identical to standard library (with some additional features), but constructed via new_in(&'a BTreeStore).
BTreeStore is internally an arena allocator, in that it allocates nodes in large fixed-sized regions; but it's also a slab allocator, in that it maintains a linked list of allocated and discarded nodes. This means we get the locality benefits of arena allocation but can also reuse storage by dropped b-trees in new b-trees, although the memory won't get reclaimed (usable outside of b-trees) until the arena is destroyed.
```rust use btreeplusstore::{BTreeSet, BTreeStore};
fn main() { let store = BTreeStore::new(); let mut foobars: BTreeSet<', &'static str> = BTreeSet::newin(&store); let mut alphabeticals: BTreeSet<', &'static str> = BTreeSet::new_in(&store);
foobars.insert("foo"); alphabeticals.insert("abc"); foobars.insert("bar"); alphabeticals.insert("def"); foobars.insert("baz"); foobars.insert("qux"); alphabeticals.insert("xyz"); foobars.remove(&"baz"); alphabeticals.remove(&"def"); for elem in &foobars { println!("Iterate {}", elem); } // TODO: retain, drainfilter, intersect, union, difference, and symmetricdifference // for elem in alphabeticals.drainfilter(|a| a.startswith('a')) { // println!("Drain {}", elem); // } for elem in alphabeticals { println!("Consume {}", elem) } } ```
This library makes heavy use of unsafe, although the tests do pass with MIRI. There are tests for most operations and edge cases, but it's still in the early phase. And since with std::collections::BTreeMap and std::collections::BTreeSet are available and better in most cases, it shouldn't be used in production.
Benchmarks are run for a sequence of operations including insertion, retrieval, iteration, and removal. We vary the # and size of maps and sets.
This library performs slightly faster than std on very small maps and sets, but slower otherwise.
Licensed under either of
at your option.
Forked from btree-slab, which is also dual licensed under Apache 2.0 "or" MIT.
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.