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