9 releases (5 breaking)
0.6.1 | Oct 5, 2023 |
---|---|
0.6.0 | Jul 2, 2023 |
0.5.1 | Nov 7, 2022 |
0.5.0 | Jul 21, 2022 |
0.2.0 | Mar 1, 2021 |
#162 in Data structures
5,555 downloads per month
Used in 80 crates
(2 directly)
200KB
4.5K
SLoC
Slab-based B-Tree implementation
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 instantiated by any data structure 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.
Usage
From the user point of view, the collection provided by this crate can be
used just like the standard BTreeMap
and BTreeSet
collections.
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.
movie_reviews.insert("Office Space", "Deals with real issues in the workplace.");
movie_reviews.insert("Pulp Fiction", "Masterpiece.");
movie_reviews.insert("The Godfather", "Very enjoyable.");
movie_reviews.insert("The Blues Brothers", "Eye lyked it a lot.");
// check for a specific one.
if !movie_reviews.contains_key("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 to_find = ["Up!", "Office Space"];
for movie in &to_find {
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);
}
Custom node allocation
One can use btree_slab::generic::BTreeMap
to
use a custom slab type to handle nodes allocation.
use slab::Slab;
use btree_slab::generic::BTreeMap;
let mut map: BTreeMap<K, V, Slab<Node<K, V>>> = BTreeMap::new();
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.
Extended API & Addressing
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
btree-range-map
crate.
License
Licensed under either of
- Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)
at your option.
Contribution
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.
Dependencies
~145KB