cranelift_bforest/
lib.rs

1//! A forest of B+-trees.
2//!
3//! This crate provides a data structures representing a set of small ordered sets or maps.
4//! It is implemented as a forest of B+-trees all allocating nodes out of the same pool.
5//!
6//! **These are not general purpose data structures that are somehow magically faster that the
7//! standard library's `BTreeSet` and `BTreeMap` types.**
8//!
9//! The tradeoffs are different:
10//!
11//! - Keys and values are expected to be small and copyable. We optimize for 32-bit types.
12//! - A comparator object is used to compare keys, allowing smaller "context free" keys.
13//! - Empty trees have a very small 32-bit footprint.
14//! - All the trees in a forest can be cleared in constant time.
15
16#![deny(missing_docs, trivial_numeric_casts, unused_extern_crates)]
17#![warn(unused_import_braces)]
18#![cfg_attr(feature = "clippy", plugin(clippy(conf_file = "../../clippy.toml")))]
19#![cfg_attr(feature = "cargo-clippy", allow(clippy::new_without_default))]
20#![cfg_attr(
21    feature = "cargo-clippy",
22    warn(
23        clippy::float_arithmetic,
24        clippy::mut_mut,
25        clippy::nonminimal_bool,
26        clippy::map_unwrap_or,
27        clippy::print_stdout,
28        clippy::unicode_not_nfc,
29        clippy::use_self
30    )
31)]
32#![no_std]
33
34#[cfg(test)]
35extern crate alloc;
36
37#[macro_use]
38extern crate cranelift_entity as entity;
39use crate::entity::packed_option;
40
41use core::borrow::BorrowMut;
42use core::cmp::Ordering;
43
44mod map;
45mod node;
46mod path;
47mod pool;
48mod set;
49
50pub use self::map::{Map, MapCursor, MapForest, MapIter};
51pub use self::set::{Set, SetCursor, SetForest, SetIter};
52
53use self::node::NodeData;
54use self::path::Path;
55use self::pool::NodePool;
56
57/// The maximum branching factor of an inner node in a B+-tree.
58/// The minimum number of outgoing edges is `INNER_SIZE/2`.
59const INNER_SIZE: usize = 8;
60
61/// Given the worst case branching factor of `INNER_SIZE/2` = 4, this is the
62/// worst case path length from the root node to a leaf node in a tree with 2^32
63/// entries. We would run out of node references before we hit `MAX_PATH`.
64const MAX_PATH: usize = 16;
65
66/// Key comparator.
67///
68/// Keys don't need to implement `Ord`. They are compared using a comparator object which
69/// provides a context for comparison.
70pub trait Comparator<K>
71where
72    K: Copy,
73{
74    /// Compare keys `a` and `b`.
75    ///
76    /// This relation must provide a total ordering or the key space.
77    fn cmp(&self, a: K, b: K) -> Ordering;
78
79    /// Binary search for `k` in an ordered slice.
80    ///
81    /// Assume that `s` is already sorted according to this ordering, search for the key `k`.
82    ///
83    /// Returns `Ok(idx)` if `k` was found in the slice or `Err(idx)` with the position where it
84    /// should be inserted to preserve the ordering.
85    fn search(&self, k: K, s: &[K]) -> Result<usize, usize> {
86        s.binary_search_by(|x| self.cmp(*x, k))
87    }
88}
89
90/// Trivial comparator that doesn't actually provide any context.
91impl<K> Comparator<K> for ()
92where
93    K: Copy + Ord,
94{
95    fn cmp(&self, a: K, b: K) -> Ordering {
96        a.cmp(&b)
97    }
98}
99
100/// Family of types shared by the map and set forest implementations.
101trait Forest {
102    /// The key type is present for both sets and maps.
103    type Key: Copy;
104
105    /// The value type is `()` for sets.
106    type Value: Copy;
107
108    /// An array of keys for the leaf nodes.
109    type LeafKeys: Copy + BorrowMut<[Self::Key]>;
110
111    /// An array of values for the leaf nodes.
112    type LeafValues: Copy + BorrowMut<[Self::Value]>;
113
114    /// Splat a single key into a whole array.
115    fn splat_key(key: Self::Key) -> Self::LeafKeys;
116
117    /// Splat a single value inst a whole array
118    fn splat_value(value: Self::Value) -> Self::LeafValues;
119}
120
121/// A reference to a B+-tree node.
122#[derive(Clone, Copy, PartialEq, Eq)]
123struct Node(u32);
124entity_impl!(Node, "node");
125
126/// Empty type to be used as the "value" in B-trees representing sets.
127#[derive(Clone, Copy)]
128struct SetValue();
129
130/// Insert `x` into `s` at position `i`, pushing out the last element.
131fn slice_insert<T: Copy>(s: &mut [T], i: usize, x: T) {
132    for j in (i + 1..s.len()).rev() {
133        s[j] = s[j - 1];
134    }
135    s[i] = x;
136}
137
138/// Shift elements in `s` to the left by `n` positions.
139fn slice_shift<T: Copy>(s: &mut [T], n: usize) {
140    for j in 0..s.len() - n {
141        s[j] = s[j + n];
142    }
143}
144
145#[cfg(test)]
146mod tests {
147    use super::*;
148    use crate::entity::EntityRef;
149
150    /// An opaque reference to a basic block in a function.
151    #[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
152    pub struct Block(u32);
153    entity_impl!(Block, "block");
154
155    #[test]
156    fn comparator() {
157        let block1 = Block::new(1);
158        let block2 = Block::new(2);
159        let block3 = Block::new(3);
160        let block4 = Block::new(4);
161        let vals = [block1, block2, block4];
162        let comp = ();
163        assert_eq!(comp.search(block1, &vals), Ok(0));
164        assert_eq!(comp.search(block3, &vals), Err(2));
165        assert_eq!(comp.search(block4, &vals), Ok(2));
166    }
167
168    #[test]
169    fn slice_insertion() {
170        let mut a = ['a', 'b', 'c', 'd'];
171
172        slice_insert(&mut a[0..1], 0, 'e');
173        assert_eq!(a, ['e', 'b', 'c', 'd']);
174
175        slice_insert(&mut a, 0, 'a');
176        assert_eq!(a, ['a', 'e', 'b', 'c']);
177
178        slice_insert(&mut a, 3, 'g');
179        assert_eq!(a, ['a', 'e', 'b', 'g']);
180
181        slice_insert(&mut a, 1, 'h');
182        assert_eq!(a, ['a', 'h', 'e', 'b']);
183    }
184
185    #[test]
186    fn slice_shifting() {
187        let mut a = ['a', 'b', 'c', 'd'];
188
189        slice_shift(&mut a[0..1], 1);
190        assert_eq!(a, ['a', 'b', 'c', 'd']);
191
192        slice_shift(&mut a[1..], 1);
193        assert_eq!(a, ['a', 'c', 'd', 'd']);
194
195        slice_shift(&mut a, 2);
196        assert_eq!(a, ['d', 'd', 'd', 'd']);
197    }
198}
cranelift_bforest/lib.rs

cranelift_bforest/
lib.rs
