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

cranelift_bforest/
lib.rs
