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
//! 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.
//!
//! ```rust
//! use slab::Slab;
//! use btree_slab::generic::{Node, BTreeMap};
//!
//! # type K = u32;
//! # type V = u32;
//! 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`](https://crates.io/crates/btree-range-map) crate.
use Slab;
/// B-Tree map based on `Slab`.
pub type BTreeMap<K, V> = BTreeMap;
/// B-Tree set based on `Slab`.
pub type BTreeSet<T> = BTreeSet;