cranelift_bforest/
map.rs

1//! Forest of maps.
2
3use super::{Comparator, Forest, Node, NodeData, NodePool, Path, INNER_SIZE};
4use crate::packed_option::PackedOption;
5#[cfg(test)]
6use alloc::string::String;
7#[cfg(test)]
8use core::fmt;
9use core::marker::PhantomData;
10
11/// Tag type defining forest types for a map.
12struct MapTypes<K, V>(PhantomData<(K, V)>);
13
14impl<K, V> Forest for MapTypes<K, V>
15where
16    K: Copy,
17    V: Copy,
18{
19    type Key = K;
20    type Value = V;
21    type LeafKeys = [K; INNER_SIZE - 1];
22    type LeafValues = [V; INNER_SIZE - 1];
23
24    fn splat_key(key: Self::Key) -> Self::LeafKeys {
25        [key; INNER_SIZE - 1]
26    }
27
28    fn splat_value(value: Self::Value) -> Self::LeafValues {
29        [value; INNER_SIZE - 1]
30    }
31}
32
33/// Memory pool for a forest of `Map` instances.
34pub struct MapForest<K, V>
35where
36    K: Copy,
37    V: Copy,
38{
39    nodes: NodePool<MapTypes<K, V>>,
40}
41
42impl<K, V> MapForest<K, V>
43where
44    K: Copy,
45    V: Copy,
46{
47    /// Create a new empty forest.
48    pub fn new() -> Self {
49        Self {
50            nodes: NodePool::new(),
51        }
52    }
53
54    /// Clear all maps in the forest.
55    ///
56    /// All `Map` instances belong to this forest are invalidated and should no longer be used.
57    pub fn clear(&mut self) {
58        self.nodes.clear();
59    }
60}
61
62/// B-tree mapping from `K` to `V`.
63///
64/// This is not a general-purpose replacement for `BTreeMap`. See the [module
65/// documentation](index.html) for more information about design tradeoffs.
66///
67/// Maps can be cloned, but that operation should only be used as part of cloning the whole forest
68/// they belong to. *Cloning a map does not allocate new memory for the clone*. It creates an alias
69/// of the same memory.
70#[derive(Clone)]
71pub struct Map<K, V>
72where
73    K: Copy,
74    V: Copy,
75{
76    root: PackedOption<Node>,
77    unused: PhantomData<(K, V)>,
78}
79
80impl<K, V> Map<K, V>
81where
82    K: Copy,
83    V: Copy,
84{
85    /// Make an empty map.
86    pub fn new() -> Self {
87        Self {
88            root: None.into(),
89            unused: PhantomData,
90        }
91    }
92
93    /// Is this an empty map?
94    pub fn is_empty(&self) -> bool {
95        self.root.is_none()
96    }
97
98    /// Get the value stored for `key`.
99    pub fn get<C: Comparator<K>>(&self, key: K, forest: &MapForest<K, V>, comp: &C) -> Option<V> {
100        self.root
101            .expand()
102            .and_then(|root| Path::default().find(key, root, &forest.nodes, comp))
103    }
104
105    /// Look up the value stored for `key`.
106    ///
107    /// If it exists, return the stored key-value pair.
108    ///
109    /// Otherwise, return the last key-value pair with a key that is less than or equal to `key`.
110    ///
111    /// If no stored keys are less than or equal to `key`, return `None`.
112    pub fn get_or_less<C: Comparator<K>>(
113        &self,
114        key: K,
115        forest: &MapForest<K, V>,
116        comp: &C,
117    ) -> Option<(K, V)> {
118        self.root.expand().and_then(|root| {
119            let mut path = Path::default();
120            match path.find(key, root, &forest.nodes, comp) {
121                Some(v) => Some((key, v)),
122                None => path.prev(root, &forest.nodes),
123            }
124        })
125    }
126
127    /// Insert `key, value` into the map and return the old value stored for `key`, if any.
128    pub fn insert<C: Comparator<K>>(
129        &mut self,
130        key: K,
131        value: V,
132        forest: &mut MapForest<K, V>,
133        comp: &C,
134    ) -> Option<V> {
135        self.cursor(forest, comp).insert(key, value)
136    }
137
138    /// Remove `key` from the map and return the removed value for `key`, if any.
139    pub fn remove<C: Comparator<K>>(
140        &mut self,
141        key: K,
142        forest: &mut MapForest<K, V>,
143        comp: &C,
144    ) -> Option<V> {
145        let mut c = self.cursor(forest, comp);
146        if c.goto(key).is_some() {
147            c.remove()
148        } else {
149            None
150        }
151    }
152
153    /// Remove all entries.
154    pub fn clear(&mut self, forest: &mut MapForest<K, V>) {
155        if let Some(root) = self.root.take() {
156            forest.nodes.free_tree(root);
157        }
158    }
159
160    /// Retains only the elements specified by the predicate.
161    ///
162    /// Remove all key-value pairs where the predicate returns false.
163    ///
164    /// The predicate is allowed to update the values stored in the map.
165    pub fn retain<F>(&mut self, forest: &mut MapForest<K, V>, mut predicate: F)
166    where
167        F: FnMut(K, &mut V) -> bool,
168    {
169        let mut path = Path::default();
170        if let Some(root) = self.root.expand() {
171            path.first(root, &forest.nodes);
172        }
173        while let Some((node, entry)) = path.leaf_pos() {
174            let keep = {
175                let (ks, vs) = forest.nodes[node].unwrap_leaf_mut();
176                predicate(ks[entry], &mut vs[entry])
177            };
178            if keep {
179                path.next(&forest.nodes);
180            } else {
181                self.root = path.remove(&mut forest.nodes).into();
182            }
183        }
184    }
185
186    /// Create a cursor for navigating this map. The cursor is initially positioned off the end of
187    /// the map.
188    pub fn cursor<'a, C: Comparator<K>>(
189        &'a mut self,
190        forest: &'a mut MapForest<K, V>,
191        comp: &'a C,
192    ) -> MapCursor<'a, K, V, C> {
193        MapCursor::new(self, forest, comp)
194    }
195
196    /// Create an iterator traversing this map. The iterator type is `(K, V)`.
197    pub fn iter<'a>(&'a self, forest: &'a MapForest<K, V>) -> MapIter<'a, K, V> {
198        MapIter {
199            root: self.root,
200            pool: &forest.nodes,
201            path: Path::default(),
202        }
203    }
204}
205
206impl<K, V> Default for Map<K, V>
207where
208    K: Copy,
209    V: Copy,
210{
211    fn default() -> Self {
212        Self::new()
213    }
214}
215
216#[cfg(test)]
217impl<K, V> Map<K, V>
218where
219    K: Copy + fmt::Display,
220    V: Copy,
221{
222    /// Verify consistency.
223    fn verify<C: Comparator<K>>(&self, forest: &MapForest<K, V>, comp: &C)
224    where
225        NodeData<MapTypes<K, V>>: fmt::Display,
226    {
227        if let Some(root) = self.root.expand() {
228            forest.nodes.verify_tree(root, comp);
229        }
230    }
231
232    /// Get a text version of the path to `key`.
233    fn tpath<C: Comparator<K>>(&self, key: K, forest: &MapForest<K, V>, comp: &C) -> String {
234        use alloc::string::ToString;
235        match self.root.expand() {
236            None => "map(empty)".to_string(),
237            Some(root) => {
238                let mut path = Path::default();
239                path.find(key, root, &forest.nodes, comp);
240                path.to_string()
241            }
242        }
243    }
244}
245
246/// A position in a `Map` used to navigate and modify the ordered map.
247///
248/// A cursor always points at a key-value pair in the map, or "off the end" which is a position
249/// after the last entry in the map.
250pub struct MapCursor<'a, K, V, C>
251where
252    K: 'a + Copy,
253    V: 'a + Copy,
254    C: 'a + Comparator<K>,
255{
256    root: &'a mut PackedOption<Node>,
257    pool: &'a mut NodePool<MapTypes<K, V>>,
258    comp: &'a C,
259    path: Path<MapTypes<K, V>>,
260}
261
262impl<'a, K, V, C> MapCursor<'a, K, V, C>
263where
264    K: Copy,
265    V: Copy,
266    C: Comparator<K>,
267{
268    /// Create a cursor with a default (off-the-end) location.
269    fn new(container: &'a mut Map<K, V>, forest: &'a mut MapForest<K, V>, comp: &'a C) -> Self {
270        Self {
271            root: &mut container.root,
272            pool: &mut forest.nodes,
273            comp,
274            path: Path::default(),
275        }
276    }
277
278    /// Is this cursor pointing to an empty map?
279    pub fn is_empty(&self) -> bool {
280        self.root.is_none()
281    }
282
283    /// Move cursor to the next key-value pair and return it.
284    ///
285    /// If the cursor reaches the end, return `None` and leave the cursor at the off-the-end
286    /// position.
287    #[cfg_attr(feature = "cargo-clippy", allow(clippy::should_implement_trait))]
288    pub fn next(&mut self) -> Option<(K, V)> {
289        self.path.next(self.pool)
290    }
291
292    /// Move cursor to the previous key-value pair and return it.
293    ///
294    /// If the cursor is already pointing at the first entry, leave it there and return `None`.
295    pub fn prev(&mut self) -> Option<(K, V)> {
296        self.root
297            .expand()
298            .and_then(|root| self.path.prev(root, self.pool))
299    }
300
301    /// Get the current key, or `None` if the cursor is at the end.
302    pub fn key(&self) -> Option<K> {
303        self.path
304            .leaf_pos()
305            .and_then(|(node, entry)| self.pool[node].unwrap_leaf().0.get(entry).cloned())
306    }
307
308    /// Get the current value, or `None` if the cursor is at the end.
309    pub fn value(&self) -> Option<V> {
310        self.path
311            .leaf_pos()
312            .and_then(|(node, entry)| self.pool[node].unwrap_leaf().1.get(entry).cloned())
313    }
314
315    /// Get a mutable reference to the current value, or `None` if the cursor is at the end.
316    pub fn value_mut(&mut self) -> Option<&mut V> {
317        self.path
318            .leaf_pos()
319            .and_then(move |(node, entry)| self.pool[node].unwrap_leaf_mut().1.get_mut(entry))
320    }
321
322    /// Move this cursor to `key`.
323    ///
324    /// If `key` is in the map, place the cursor at `key` and return the corresponding value.
325    ///
326    /// If `key` is not in the set, place the cursor at the next larger element (or the end) and
327    /// return `None`.
328    pub fn goto(&mut self, elem: K) -> Option<V> {
329        self.root.expand().and_then(|root| {
330            let v = self.path.find(elem, root, self.pool, self.comp);
331            if v.is_none() {
332                self.path.normalize(self.pool);
333            }
334            v
335        })
336    }
337
338    /// Move this cursor to the first element.
339    pub fn goto_first(&mut self) -> Option<V> {
340        self.root.map(|root| self.path.first(root, self.pool).1)
341    }
342
343    /// Insert `(key, value))` into the map and leave the cursor at the inserted pair.
344    ///
345    /// If the map did not contain `key`, return `None`.
346    ///
347    /// If `key` is already present, replace the existing with `value` and return the old value.
348    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
349        match self.root.expand() {
350            None => {
351                let root = self.pool.alloc_node(NodeData::leaf(key, value));
352                *self.root = root.into();
353                self.path.set_root_node(root);
354                None
355            }
356            Some(root) => {
357                // TODO: Optimize the case where `self.path` is already at the correct insert pos.
358                let old = self.path.find(key, root, self.pool, self.comp);
359                if old.is_some() {
360                    *self.path.value_mut(self.pool) = value;
361                } else {
362                    *self.root = self.path.insert(key, value, self.pool).into();
363                }
364                old
365            }
366        }
367    }
368
369    /// Remove the current entry (if any) and return the mapped value.
370    /// This advances the cursor to the next entry after the removed one.
371    pub fn remove(&mut self) -> Option<V> {
372        let value = self.value();
373        if value.is_some() {
374            *self.root = self.path.remove(self.pool).into();
375        }
376        value
377    }
378}
379
380/// An iterator visiting the key-value pairs of a `Map`.
381pub struct MapIter<'a, K, V>
382where
383    K: 'a + Copy,
384    V: 'a + Copy,
385{
386    root: PackedOption<Node>,
387    pool: &'a NodePool<MapTypes<K, V>>,
388    path: Path<MapTypes<K, V>>,
389}
390
391impl<'a, K, V> Iterator for MapIter<'a, K, V>
392where
393    K: 'a + Copy,
394    V: 'a + Copy,
395{
396    type Item = (K, V);
397
398    fn next(&mut self) -> Option<Self::Item> {
399        // We use `self.root` to indicate if we need to go to the first element. Reset to `None`
400        // once we've returned the first element. This also works for an empty tree since the
401        // `path.next()` call returns `None` when the path is empty. This also fuses the iterator.
402        match self.root.take() {
403            Some(root) => Some(self.path.first(root, self.pool)),
404            None => self.path.next(self.pool),
405        }
406    }
407}
408
409#[cfg(test)]
410impl<'a, K, V, C> MapCursor<'a, K, V, C>
411where
412    K: Copy + fmt::Display,
413    V: Copy + fmt::Display,
414    C: Comparator<K>,
415{
416    fn verify(&self) {
417        self.path.verify(self.pool);
418        self.root.map(|root| self.pool.verify_tree(root, self.comp));
419    }
420
421    /// Get a text version of the path to the current position.
422    fn tpath(&self) -> String {
423        use alloc::string::ToString;
424        self.path.to_string()
425    }
426}
427
428#[cfg(test)]
429mod tests {
430    use super::super::NodeData;
431    use super::*;
432    use alloc::vec::Vec;
433    use core::mem;
434
435    #[test]
436    fn node_size() {
437        // check that nodes are cache line sized when keys and values are 32 bits.
438        type F = MapTypes<u32, u32>;
439        assert_eq!(mem::size_of::<NodeData<F>>(), 64);
440    }
441
442    #[test]
443    fn empty() {
444        let mut f = MapForest::<u32, f32>::new();
445        f.clear();
446
447        let mut m = Map::<u32, f32>::new();
448        assert!(m.is_empty());
449        m.clear(&mut f);
450
451        assert_eq!(m.get(7, &f, &()), None);
452        assert_eq!(m.iter(&f).next(), None);
453        assert_eq!(m.get_or_less(7, &f, &()), None);
454        m.retain(&mut f, |_, _| unreachable!());
455
456        let mut c = m.cursor(&mut f, &());
457        assert!(c.is_empty());
458        assert_eq!(c.key(), None);
459        assert_eq!(c.value(), None);
460        assert_eq!(c.next(), None);
461        assert_eq!(c.prev(), None);
462        c.verify();
463        assert_eq!(c.tpath(), "<empty path>");
464        assert_eq!(c.goto_first(), None);
465        assert_eq!(c.tpath(), "<empty path>");
466    }
467
468    #[test]
469    fn inserting() {
470        let f = &mut MapForest::<u32, f32>::new();
471        let mut m = Map::<u32, f32>::new();
472
473        // The first seven values stay in a single leaf node.
474        assert_eq!(m.insert(50, 5.0, f, &()), None);
475        assert_eq!(m.insert(50, 5.5, f, &()), Some(5.0));
476        assert_eq!(m.insert(20, 2.0, f, &()), None);
477        assert_eq!(m.insert(80, 8.0, f, &()), None);
478        assert_eq!(m.insert(40, 4.0, f, &()), None);
479        assert_eq!(m.insert(60, 6.0, f, &()), None);
480        assert_eq!(m.insert(90, 9.0, f, &()), None);
481        assert_eq!(m.insert(200, 20.0, f, &()), None);
482
483        m.verify(f, &());
484
485        assert_eq!(
486            m.iter(f).collect::<Vec<_>>(),
487            [
488                (20, 2.0),
489                (40, 4.0),
490                (50, 5.5),
491                (60, 6.0),
492                (80, 8.0),
493                (90, 9.0),
494                (200, 20.0),
495            ]
496        );
497
498        assert_eq!(m.get(0, f, &()), None);
499        assert_eq!(m.get(20, f, &()), Some(2.0));
500        assert_eq!(m.get(30, f, &()), None);
501        assert_eq!(m.get(40, f, &()), Some(4.0));
502        assert_eq!(m.get(50, f, &()), Some(5.5));
503        assert_eq!(m.get(60, f, &()), Some(6.0));
504        assert_eq!(m.get(70, f, &()), None);
505        assert_eq!(m.get(80, f, &()), Some(8.0));
506        assert_eq!(m.get(100, f, &()), None);
507
508        assert_eq!(m.get_or_less(0, f, &()), None);
509        assert_eq!(m.get_or_less(20, f, &()), Some((20, 2.0)));
510        assert_eq!(m.get_or_less(30, f, &()), Some((20, 2.0)));
511        assert_eq!(m.get_or_less(40, f, &()), Some((40, 4.0)));
512        assert_eq!(m.get_or_less(200, f, &()), Some((200, 20.0)));
513        assert_eq!(m.get_or_less(201, f, &()), Some((200, 20.0)));
514
515        {
516            let mut c = m.cursor(f, &());
517            assert_eq!(c.prev(), Some((200, 20.0)));
518            assert_eq!(c.prev(), Some((90, 9.0)));
519            assert_eq!(c.prev(), Some((80, 8.0)));
520            assert_eq!(c.prev(), Some((60, 6.0)));
521            assert_eq!(c.prev(), Some((50, 5.5)));
522            assert_eq!(c.prev(), Some((40, 4.0)));
523            assert_eq!(c.prev(), Some((20, 2.0)));
524            assert_eq!(c.prev(), None);
525        }
526
527        // Test some removals where the node stays healthy.
528        assert_eq!(m.tpath(50, f, &()), "node0[2]");
529        assert_eq!(m.tpath(80, f, &()), "node0[4]");
530        assert_eq!(m.tpath(200, f, &()), "node0[6]");
531
532        assert_eq!(m.remove(80, f, &()), Some(8.0));
533        assert_eq!(m.tpath(50, f, &()), "node0[2]");
534        assert_eq!(m.tpath(80, f, &()), "node0[4]");
535        assert_eq!(m.tpath(200, f, &()), "node0[5]");
536        assert_eq!(m.remove(80, f, &()), None);
537        m.verify(f, &());
538
539        assert_eq!(m.remove(20, f, &()), Some(2.0));
540        assert_eq!(m.tpath(50, f, &()), "node0[1]");
541        assert_eq!(m.tpath(80, f, &()), "node0[3]");
542        assert_eq!(m.tpath(200, f, &()), "node0[4]");
543        assert_eq!(m.remove(20, f, &()), None);
544        m.verify(f, &());
545
546        // [ 40 50 60 90 200 ]
547
548        {
549            let mut c = m.cursor(f, &());
550            assert_eq!(c.goto_first(), Some(4.0));
551            assert_eq!(c.key(), Some(40));
552            assert_eq!(c.value(), Some(4.0));
553            assert_eq!(c.next(), Some((50, 5.5)));
554            assert_eq!(c.next(), Some((60, 6.0)));
555            assert_eq!(c.next(), Some((90, 9.0)));
556            assert_eq!(c.next(), Some((200, 20.0)));
557            c.verify();
558            assert_eq!(c.next(), None);
559            c.verify();
560        }
561
562        // Removals from the root leaf node beyond underflow.
563        assert_eq!(m.remove(200, f, &()), Some(20.0));
564        assert_eq!(m.remove(40, f, &()), Some(4.0));
565        assert_eq!(m.remove(60, f, &()), Some(6.0));
566        m.verify(f, &());
567        assert_eq!(m.remove(50, f, &()), Some(5.5));
568        m.verify(f, &());
569        assert_eq!(m.remove(90, f, &()), Some(9.0));
570        m.verify(f, &());
571        assert!(m.is_empty());
572    }
573
574    #[test]
575    fn split_level0_leaf() {
576        // Various ways of splitting a full leaf node at level 0.
577        let f = &mut MapForest::<u32, f32>::new();
578
579        fn full_leaf(f: &mut MapForest<u32, f32>) -> Map<u32, f32> {
580            let mut m = Map::new();
581            for n in 1..8 {
582                m.insert(n * 10, n as f32 * 1.1, f, &());
583            }
584            m
585        }
586
587        // Insert at front of leaf.
588        let mut m = full_leaf(f);
589        m.insert(5, 4.2, f, &());
590        m.verify(f, &());
591        assert_eq!(m.get(5, f, &()), Some(4.2));
592
593        // Retain even entries, with altered values.
594        m.retain(f, |k, v| {
595            *v = (k / 10) as f32;
596            (k % 20) == 0
597        });
598        assert_eq!(
599            m.iter(f).collect::<Vec<_>>(),
600            [(20, 2.0), (40, 4.0), (60, 6.0)]
601        );
602
603        // Insert at back of leaf.
604        let mut m = full_leaf(f);
605        m.insert(80, 4.2, f, &());
606        m.verify(f, &());
607        assert_eq!(m.get(80, f, &()), Some(4.2));
608
609        // Insert before middle (40).
610        let mut m = full_leaf(f);
611        m.insert(35, 4.2, f, &());
612        m.verify(f, &());
613        assert_eq!(m.get(35, f, &()), Some(4.2));
614
615        // Insert after middle (40).
616        let mut m = full_leaf(f);
617        m.insert(45, 4.2, f, &());
618        m.verify(f, &());
619        assert_eq!(m.get(45, f, &()), Some(4.2));
620
621        m.clear(f);
622        assert!(m.is_empty());
623    }
624
625    #[test]
626    fn split_level1_leaf() {
627        // Various ways of splitting a full leaf node at level 1.
628        let f = &mut MapForest::<u32, f32>::new();
629
630        // Return a map whose root node is a full inner node, and the leaf nodes are all full
631        // containing:
632        //
633        // 110, 120, ..., 170
634        // 210, 220, ..., 270
635        // ...
636        // 810, 820, ..., 870
637        fn full(f: &mut MapForest<u32, f32>) -> Map<u32, f32> {
638            let mut m = Map::new();
639
640            // Start by inserting elements in order.
641            // This should leave 8 leaf nodes with 4 elements in each.
642            for row in 1..9 {
643                for col in 1..5 {
644                    m.insert(row * 100 + col * 10, row as f32 + col as f32 * 0.1, f, &());
645                }
646            }
647
648            // Then top up the leaf nodes without splitting them.
649            for row in 1..9 {
650                for col in 5..8 {
651                    m.insert(row * 100 + col * 10, row as f32 + col as f32 * 0.1, f, &());
652                }
653            }
654
655            m
656        }
657
658        let mut m = full(f);
659        // Verify geometry. Get get node2 as the root and leaves node0, 1, 3, ...
660        m.verify(f, &());
661        assert_eq!(m.tpath(110, f, &()), "node2[0]--node0[0]");
662        assert_eq!(m.tpath(140, f, &()), "node2[0]--node0[3]");
663        assert_eq!(m.tpath(210, f, &()), "node2[1]--node1[0]");
664        assert_eq!(m.tpath(270, f, &()), "node2[1]--node1[6]");
665        assert_eq!(m.tpath(310, f, &()), "node2[2]--node3[0]");
666        assert_eq!(m.tpath(810, f, &()), "node2[7]--node8[0]");
667        assert_eq!(m.tpath(870, f, &()), "node2[7]--node8[6]");
668
669        {
670            let mut c = m.cursor(f, &());
671            assert_eq!(c.goto_first(), Some(1.1));
672            assert_eq!(c.key(), Some(110));
673        }
674
675        // Front of first leaf.
676        m.insert(0, 4.2, f, &());
677        m.verify(f, &());
678        assert_eq!(m.get(0, f, &()), Some(4.2));
679
680        // First leaf split 4-4 after appending to LHS.
681        f.clear();
682        m = full(f);
683        m.insert(135, 4.2, f, &());
684        m.verify(f, &());
685        assert_eq!(m.get(135, f, &()), Some(4.2));
686
687        // First leaf split 4-4 after prepending to RHS.
688        f.clear();
689        m = full(f);
690        m.insert(145, 4.2, f, &());
691        m.verify(f, &());
692        assert_eq!(m.get(145, f, &()), Some(4.2));
693
694        // First leaf split 4-4 after appending to RHS.
695        f.clear();
696        m = full(f);
697        m.insert(175, 4.2, f, &());
698        m.verify(f, &());
699        assert_eq!(m.get(175, f, &()), Some(4.2));
700
701        // Left-middle leaf split, ins LHS.
702        f.clear();
703        m = full(f);
704        m.insert(435, 4.2, f, &());
705        m.verify(f, &());
706        assert_eq!(m.get(435, f, &()), Some(4.2));
707
708        // Left-middle leaf split, ins RHS.
709        f.clear();
710        m = full(f);
711        m.insert(445, 4.2, f, &());
712        m.verify(f, &());
713        assert_eq!(m.get(445, f, &()), Some(4.2));
714
715        // Right-middle leaf split, ins LHS.
716        f.clear();
717        m = full(f);
718        m.insert(535, 4.2, f, &());
719        m.verify(f, &());
720        assert_eq!(m.get(535, f, &()), Some(4.2));
721
722        // Right-middle leaf split, ins RHS.
723        f.clear();
724        m = full(f);
725        m.insert(545, 4.2, f, &());
726        m.verify(f, &());
727        assert_eq!(m.get(545, f, &()), Some(4.2));
728
729        // Last leaf split, ins LHS.
730        f.clear();
731        m = full(f);
732        m.insert(835, 4.2, f, &());
733        m.verify(f, &());
734        assert_eq!(m.get(835, f, &()), Some(4.2));
735
736        // Last leaf split, ins RHS.
737        f.clear();
738        m = full(f);
739        m.insert(845, 4.2, f, &());
740        m.verify(f, &());
741        assert_eq!(m.get(845, f, &()), Some(4.2));
742
743        // Front of last leaf.
744        f.clear();
745        m = full(f);
746        m.insert(805, 4.2, f, &());
747        m.verify(f, &());
748        assert_eq!(m.get(805, f, &()), Some(4.2));
749
750        m.clear(f);
751        m.verify(f, &());
752    }
753
754    // Make a tree with two barely healthy leaf nodes:
755    // [ 10 20 30 40 ] [ 50 60 70 80 ]
756    fn two_leaf(f: &mut MapForest<u32, f32>) -> Map<u32, f32> {
757        f.clear();
758        let mut m = Map::new();
759        for n in 1..9 {
760            m.insert(n * 10, n as f32, f, &());
761        }
762        m
763    }
764
765    #[test]
766    fn remove_level1() {
767        let f = &mut MapForest::<u32, f32>::new();
768        let mut m = two_leaf(f);
769
770        // Verify geometry.
771        m.verify(f, &());
772        assert_eq!(m.tpath(10, f, &()), "node2[0]--node0[0]");
773        assert_eq!(m.tpath(40, f, &()), "node2[0]--node0[3]");
774        assert_eq!(m.tpath(49, f, &()), "node2[0]--node0[4]");
775        assert_eq!(m.tpath(50, f, &()), "node2[1]--node1[0]");
776        assert_eq!(m.tpath(80, f, &()), "node2[1]--node1[3]");
777
778        // Remove the front entry from a node that stays healthy.
779        assert_eq!(m.insert(55, 5.5, f, &()), None);
780        assert_eq!(m.remove(50, f, &()), Some(5.0));
781        m.verify(f, &());
782        assert_eq!(m.tpath(49, f, &()), "node2[0]--node0[4]");
783        assert_eq!(m.tpath(50, f, &()), "node2[0]--node0[4]");
784        assert_eq!(m.tpath(55, f, &()), "node2[1]--node1[0]");
785
786        // Remove the front entry from the first leaf node: No critical key to update.
787        assert_eq!(m.insert(15, 1.5, f, &()), None);
788        assert_eq!(m.remove(10, f, &()), Some(1.0));
789        m.verify(f, &());
790
791        // [ 15 20 30 40 ] [ 55 60 70 80 ]
792
793        // Remove the front entry from a right-most node that underflows.
794        // No rebalancing for the right-most node. Still need critical key update.
795        assert_eq!(m.remove(55, f, &()), Some(5.5));
796        m.verify(f, &());
797        assert_eq!(m.tpath(55, f, &()), "node2[0]--node0[4]");
798        assert_eq!(m.tpath(60, f, &()), "node2[1]--node1[0]");
799
800        // [ 15 20 30 40 ] [ 60 70 80 ]
801
802        // Replenish the right leaf.
803        assert_eq!(m.insert(90, 9.0, f, &()), None);
804        assert_eq!(m.insert(100, 10.0, f, &()), None);
805        m.verify(f, &());
806        assert_eq!(m.tpath(55, f, &()), "node2[0]--node0[4]");
807        assert_eq!(m.tpath(60, f, &()), "node2[1]--node1[0]");
808
809        // [ 15 20 30 40 ] [ 60 70 80 90 100 ]
810
811        // Removing one entry from the left leaf should trigger a rebalancing from the right
812        // sibling.
813        assert_eq!(m.remove(20, f, &()), Some(2.0));
814        m.verify(f, &());
815
816        // [ 15 30 40 60 ] [ 70 80 90 100 ]
817        // Check that the critical key was updated correctly.
818        assert_eq!(m.tpath(50, f, &()), "node2[0]--node0[3]");
819        assert_eq!(m.tpath(60, f, &()), "node2[0]--node0[3]");
820        assert_eq!(m.tpath(70, f, &()), "node2[1]--node1[0]");
821
822        // Remove front entry from the left-most leaf node, underflowing.
823        // This should cause two leaf nodes to be merged and the root node to go away.
824        assert_eq!(m.remove(15, f, &()), Some(1.5));
825        m.verify(f, &());
826    }
827
828    #[test]
829    fn remove_level1_rightmost() {
830        let f = &mut MapForest::<u32, f32>::new();
831        let mut m = two_leaf(f);
832
833        // [ 10 20 30 40 ] [ 50 60 70 80 ]
834
835        // Remove entries from the right leaf. This doesn't trigger a rebalancing.
836        assert_eq!(m.remove(60, f, &()), Some(6.0));
837        assert_eq!(m.remove(80, f, &()), Some(8.0));
838        assert_eq!(m.remove(50, f, &()), Some(5.0));
839        m.verify(f, &());
840
841        // [ 10 20 30 40 ] [ 70 ]
842        assert_eq!(m.tpath(50, f, &()), "node2[0]--node0[4]");
843        assert_eq!(m.tpath(70, f, &()), "node2[1]--node1[0]");
844
845        // Removing the last entry from the right leaf should cause a collapse.
846        assert_eq!(m.remove(70, f, &()), Some(7.0));
847        m.verify(f, &());
848    }
849
850    // Make a 3-level tree with barely healthy nodes.
851    // 1 root, 8 inner nodes, 7*4+5=33 leaf nodes, 4 entries each.
852    fn level3_sparse(f: &mut MapForest<u32, f32>) -> Map<u32, f32> {
853        f.clear();
854        let mut m = Map::new();
855        for n in 1..133 {
856            m.insert(n * 10, n as f32, f, &());
857        }
858        m
859    }
860
861    #[test]
862    fn level3_removes() {
863        let f = &mut MapForest::<u32, f32>::new();
864        let mut m = level3_sparse(f);
865        m.verify(f, &());
866
867        // Check geometry.
868        // Root: node11
869        // [ node2 170 node10 330 node16 490 node21 650 node26 810 node31 970 node36 1130 node41 ]
870        // L1: node11
871        assert_eq!(m.tpath(0, f, &()), "node11[0]--node2[0]--node0[0]");
872        assert_eq!(m.tpath(10000, f, &()), "node11[7]--node41[4]--node40[4]");
873
874        // 650 is a critical key in the middle of the root.
875        assert_eq!(m.tpath(640, f, &()), "node11[3]--node21[3]--node19[3]");
876        assert_eq!(m.tpath(650, f, &()), "node11[4]--node26[0]--node20[0]");
877
878        // Deleting 640 triggers a rebalance from node19 to node 20, cascading to n21 -> n26.
879        assert_eq!(m.remove(640, f, &()), Some(64.0));
880        m.verify(f, &());
881        assert_eq!(m.tpath(650, f, &()), "node11[3]--node26[3]--node20[3]");
882
883        // 1130 is in the first leaf of the last L1 node. Deleting it triggers a rebalance node35
884        // -> node37, but no rebalance above where there is no right sibling.
885        assert_eq!(m.tpath(1130, f, &()), "node11[6]--node41[0]--node35[0]");
886        assert_eq!(m.tpath(1140, f, &()), "node11[6]--node41[0]--node35[1]");
887        assert_eq!(m.remove(1130, f, &()), Some(113.0));
888        m.verify(f, &());
889        assert_eq!(m.tpath(1140, f, &()), "node11[6]--node41[0]--node37[0]");
890    }
891
892    #[test]
893    fn insert_many() {
894        let f = &mut MapForest::<u32, f32>::new();
895        let mut m = Map::<u32, f32>::new();
896
897        let mm = 4096;
898        let mut x = 0;
899
900        for n in 0..mm {
901            assert_eq!(m.insert(x, n as f32, f, &()), None);
902            m.verify(f, &());
903
904            x = (x + n + 1) % mm;
905        }
906
907        x = 0;
908        for n in 0..mm {
909            assert_eq!(m.get(x, f, &()), Some(n as f32));
910            x = (x + n + 1) % mm;
911        }
912
913        x = 0;
914        for n in 0..mm {
915            assert_eq!(m.remove(x, f, &()), Some(n as f32));
916            m.verify(f, &());
917
918            x = (x + n + 1) % mm;
919        }
920
921        assert!(m.is_empty());
922    }
923}
cranelift_bforest/map.rs

cranelift_bforest/
map.rs
