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)]
20 extern crate alloc;
21 
22 #[macro_use]
23 extern crate cranelift_entity as entity;
24 use crate::entity::packed_option;
25 
26 use core::borrow::BorrowMut;
27 use core::cmp::Ordering;
28 
29 mod map;
30 mod node;
31 mod path;
32 mod pool;
33 mod set;
34 
35 pub use self::map::{Map, MapCursor, MapForest, MapIter};
36 pub use self::set::{Set, SetCursor, SetForest, SetIter};
37 
38 use self::node::NodeData;
39 use self::path::Path;
40 use 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`.
44 const 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`.
49 const 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.
55 pub trait Comparator<K>
56 where
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.
76 impl<K> Comparator<K> for ()
77 where
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.
86 trait 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)]
108 struct Node(u32);
109 entity_impl!(Node, "node");
110 
111 /// Empty type to be used as the "value" in B-trees representing sets.
112 #[derive(Clone, Copy)]
113 struct SetValue();
114 
115 /// Insert `x` into `s` at position `i`, pushing out the last element.
116 fn 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.
124 fn 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)]
131 mod 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 }
184