| Documentation | Crate informations | Repository |
This crate provides an alternative implementation to
the standard BTreeMap and BTreeSet data structures
based on a slab data-structure.
In principle,
this implementation is more flexible and more memory efficient.
It is more flexible by providing an extended set of
low-level operations on B-Trees through the BTreeExt trait which can be used
to further extend the functionalities of the BTreeMap collection.
In addition,
the underlying node allocation scheme is abstracted by a type parameter
that can be instanciated by any data strucutre
implementing slab-like operations.
By default,
the Slab type (from the slab crate) is used,
which means that every node of the tree are allocated in a contiguous memory region,
reducing the number of allocations needed.
In theory, another type could be used to store the entire B-Tree on the stack.
From the user point of view,
the collection provided by this crate can be used just like
the standard BTreeMap and BTreeSet collections.
```rust
use btree_slab::BTreeMap;
// type inference lets us omit an explicit type signature (which
// would be BTreeMap<&str, &str> in this example).
let mut movie_reviews = BTreeMap::new();
// review some movies. moviereviews.insert("Office Space", "Deals with real issues in the workplace."); moviereviews.insert("Pulp Fiction", "Masterpiece."); moviereviews.insert("The Godfather", "Very enjoyable."); moviereviews.insert("The Blues Brothers", "Eye lyked it a lot.");
// check for a specific one. if !moviereviews.containskey("Les Misérables") { println!("We've got {} reviews, but Les Misérables ain't one.", movie_reviews.len()); }
// oops, this review has a lot of spelling mistakes, let's delete it. movie_reviews.remove("The Blues Brothers");
// look up the values associated with some keys. let tofind = ["Up!", "Office Space"]; for movie in &tofind { match movie_reviews.get(movie) { Some(review) => println!("{}: {}", movie, review), None => println!("{} is unreviewed.", movie) } }
// Look up the value for a key (will panic if the key is not found). println!("Movie review: {}", movie_reviews["Office Space"]);
// iterate over everything. for (movie, review) in &movie_reviews { println!("{}: \"{}\"", movie, review); } ```
One can use btree_slab::generic::BTreeMap to
use a custom slab type to handle nodes allocation.
```rust use slab::Slab; use btree_slab::generic::BTreeMap;
let mut map: BTreeMap
In this example,
the Slab<Node<_, _>> type is a slab-like data structure responsible for the nodes allocation.
It must implement all the traits defining the cc_traits::Slab trait alias.
In this implementation of B-Trees, each node of a tree is addressed
by the Address type.
The extended API, visible through the BTreeExt trait,
allows the caller to explore, access and modify the
internal structure of the tree using this addressing system.
This can be used to further extend the functionalities of the BTreeMap collection,
for example in the range-map crate.
Licensed under either of
at your option.
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.