cranelift_bforest/
node.rs

1//! B+-tree nodes.
2
3use super::{slice_insert, slice_shift, Forest, Node, SetValue, INNER_SIZE};
4use core::borrow::{Borrow, BorrowMut};
5use core::fmt;
6
7/// B+-tree node.
8///
9/// A B+-tree has different node types for inner nodes and leaf nodes. Inner nodes contain M node
10/// references and M-1 keys while leaf nodes contain N keys and values. Values for M and N are
11/// chosen such that a node is exactly 64 bytes (a cache line) when keys and values are 32 bits
12/// each.
13///
14/// An inner node contains at least M/2 node references unless it is the right-most node at its
15/// level. A leaf node contains at least N/2 keys unless it is the right-most leaf.
16pub(super) enum NodeData<F: Forest> {
17    Inner {
18        /// The number of keys in this node.
19        /// The number of node references is always one more.
20        size: u8,
21
22        /// Keys discriminating sub-trees.
23        ///
24        /// The key in `keys[i]` is greater than all keys in `tree[i]` and less than or equal to
25        /// all keys in `tree[i+1]`.
26        keys: [F::Key; INNER_SIZE - 1],
27
28        /// Sub-trees.
29        tree: [Node; INNER_SIZE],
30    },
31    Leaf {
32        /// Number of key-value pairs in this node.
33        size: u8,
34
35        // Key array.
36        keys: F::LeafKeys,
37
38        // Value array.
39        vals: F::LeafValues,
40    },
41    /// An unused node on the free list.
42    Free { next: Option<Node> },
43}
44
45// Implement `Clone` and `Copy` manually, because deriving them would also require `Forest` to
46// implement `Clone`.
47impl<F: Forest> Copy for NodeData<F> {}
48impl<F: Forest> Clone for NodeData<F> {
49    fn clone(&self) -> Self {
50        *self
51    }
52}
53
54impl<F: Forest> NodeData<F> {
55    /// Is this a free/unused node?
56    pub fn is_free(&self) -> bool {
57        match *self {
58            Self::Free { .. } => true,
59            _ => false,
60        }
61    }
62
63    /// Get the number of entries in this node.
64    ///
65    /// This is the number of outgoing edges in an inner node, or the number of key-value pairs in
66    /// a leaf node.
67    pub fn entries(&self) -> usize {
68        match *self {
69            Self::Inner { size, .. } => usize::from(size) + 1,
70            Self::Leaf { size, .. } => usize::from(size),
71            Self::Free { .. } => panic!("freed node"),
72        }
73    }
74
75    /// Create an inner node with a single key and two sub-trees.
76    pub fn inner(left: Node, key: F::Key, right: Node) -> Self {
77        // Splat the key and right node to the whole array.
78        // Saves us from inventing a default/reserved value.
79        let mut tree = [right; INNER_SIZE];
80        tree[0] = left;
81        Self::Inner {
82            size: 1,
83            keys: [key; INNER_SIZE - 1],
84            tree,
85        }
86    }
87
88    /// Create a leaf node with a single key-value pair.
89    pub fn leaf(key: F::Key, value: F::Value) -> Self {
90        Self::Leaf {
91            size: 1,
92            keys: F::splat_key(key),
93            vals: F::splat_value(value),
94        }
95    }
96
97    /// Unwrap an inner node into two slices (keys, trees).
98    pub fn unwrap_inner(&self) -> (&[F::Key], &[Node]) {
99        match *self {
100            Self::Inner {
101                size,
102                ref keys,
103                ref tree,
104            } => {
105                let size = usize::from(size);
106                // TODO: We could probably use `get_unchecked()` here since `size` is always in
107                // range.
108                (&keys[0..size], &tree[0..=size])
109            }
110            _ => panic!("Expected inner node"),
111        }
112    }
113
114    /// Unwrap a leaf node into two slices (keys, values) of the same length.
115    pub fn unwrap_leaf(&self) -> (&[F::Key], &[F::Value]) {
116        match *self {
117            Self::Leaf {
118                size,
119                ref keys,
120                ref vals,
121            } => {
122                let size = usize::from(size);
123                let keys = keys.borrow();
124                let vals = vals.borrow();
125                // TODO: We could probably use `get_unchecked()` here since `size` is always in
126                // range.
127                (&keys[0..size], &vals[0..size])
128            }
129            _ => panic!("Expected leaf node"),
130        }
131    }
132
133    /// Unwrap a mutable leaf node into two slices (keys, values) of the same length.
134    pub fn unwrap_leaf_mut(&mut self) -> (&mut [F::Key], &mut [F::Value]) {
135        match *self {
136            Self::Leaf {
137                size,
138                ref mut keys,
139                ref mut vals,
140            } => {
141                let size = usize::from(size);
142                let keys = keys.borrow_mut();
143                let vals = vals.borrow_mut();
144                // TODO: We could probably use `get_unchecked_mut()` here since `size` is always in
145                // range.
146                (&mut keys[0..size], &mut vals[0..size])
147            }
148            _ => panic!("Expected leaf node"),
149        }
150    }
151
152    /// Get the critical key for a leaf node.
153    /// This is simply the first key.
154    pub fn leaf_crit_key(&self) -> F::Key {
155        match *self {
156            Self::Leaf { size, ref keys, .. } => {
157                debug_assert!(size > 0, "Empty leaf node");
158                keys.borrow()[0]
159            }
160            _ => panic!("Expected leaf node"),
161        }
162    }
163
164    /// Try to insert `(key, node)` at key-position `index` in an inner node.
165    /// This means that `key` is inserted at `keys[i]` and `node` is inserted at `tree[i + 1]`.
166    /// If the node is full, this leaves the node unchanged and returns false.
167    pub fn try_inner_insert(&mut self, index: usize, key: F::Key, node: Node) -> bool {
168        match *self {
169            Self::Inner {
170                ref mut size,
171                ref mut keys,
172                ref mut tree,
173            } => {
174                let sz = usize::from(*size);
175                debug_assert!(sz <= keys.len());
176                debug_assert!(index <= sz, "Can't insert at {index} with {sz} keys");
177
178                if let Some(ks) = keys.get_mut(0..=sz) {
179                    *size = (sz + 1) as u8;
180                    slice_insert(ks, index, key);
181                    slice_insert(&mut tree[1..=sz + 1], index, node);
182                    true
183                } else {
184                    false
185                }
186            }
187            _ => panic!("Expected inner node"),
188        }
189    }
190
191    /// Try to insert `key, value` at `index` in a leaf node, but fail and return false if the node
192    /// is full.
193    pub fn try_leaf_insert(&mut self, index: usize, key: F::Key, value: F::Value) -> bool {
194        match *self {
195            Self::Leaf {
196                ref mut size,
197                ref mut keys,
198                ref mut vals,
199            } => {
200                let sz = usize::from(*size);
201                let keys = keys.borrow_mut();
202                let vals = vals.borrow_mut();
203                debug_assert!(sz <= keys.len());
204                debug_assert!(index <= sz);
205
206                if let Some(ks) = keys.get_mut(0..=sz) {
207                    *size = (sz + 1) as u8;
208                    slice_insert(ks, index, key);
209                    slice_insert(&mut vals[0..=sz], index, value);
210                    true
211                } else {
212                    false
213                }
214            }
215            _ => panic!("Expected leaf node"),
216        }
217    }
218
219    /// Split off the second half of this node.
220    /// It is assumed that this a completely full inner or leaf node.
221    ///
222    /// The `insert_index` parameter is the position where an insertion was tried and failed. The
223    /// node will be split in half with a bias towards an even split after the insertion is retried.
224    pub fn split(&mut self, insert_index: usize) -> SplitOff<F> {
225        match *self {
226            Self::Inner {
227                ref mut size,
228                ref keys,
229                ref tree,
230            } => {
231                debug_assert_eq!(usize::from(*size), keys.len(), "Node not full");
232
233                // Number of tree entries in the lhs node.
234                let l_ents = split_pos(tree.len(), insert_index + 1);
235                let r_ents = tree.len() - l_ents;
236
237                // With INNER_SIZE=8, we get l_ents=4 and:
238                //
239                // self: [ n0 k0 n1 k1 n2 k2 n3 k3 n4 k4 n5 k5 n6 k6 n7 ]
240                // lhs:  [ n0 k0 n1 k1 n2 k2 n3 ]
241                // crit_key = k3 (not present in either node)
242                // rhs:  [ n4 k4 n5 k5 n6 k6 n7 ]
243
244                // 1. Truncate the LHS.
245                *size = (l_ents - 1) as u8;
246
247                // 2. Copy second half to `rhs_data`.
248                let mut r_keys = *keys;
249                r_keys[0..r_ents - 1].copy_from_slice(&keys[l_ents..]);
250
251                let mut r_tree = *tree;
252                r_tree[0..r_ents].copy_from_slice(&tree[l_ents..]);
253
254                SplitOff {
255                    lhs_entries: l_ents,
256                    rhs_entries: r_ents,
257                    crit_key: keys[l_ents - 1],
258                    rhs_data: Self::Inner {
259                        size: (r_ents - 1) as u8,
260                        keys: r_keys,
261                        tree: r_tree,
262                    },
263                }
264            }
265            Self::Leaf {
266                ref mut size,
267                ref keys,
268                ref vals,
269            } => {
270                let o_keys = keys.borrow();
271                let o_vals = vals.borrow();
272                debug_assert_eq!(usize::from(*size), o_keys.len(), "Node not full");
273
274                let l_size = split_pos(o_keys.len(), insert_index);
275                let r_size = o_keys.len() - l_size;
276
277                // 1. Truncate the LHS node at `l_size`.
278                *size = l_size as u8;
279
280                // 2. Copy second half to `rhs_data`.
281                let mut r_keys = *keys;
282                r_keys.borrow_mut()[0..r_size].copy_from_slice(&o_keys[l_size..]);
283
284                let mut r_vals = *vals;
285                r_vals.borrow_mut()[0..r_size].copy_from_slice(&o_vals[l_size..]);
286
287                SplitOff {
288                    lhs_entries: l_size,
289                    rhs_entries: r_size,
290                    crit_key: o_keys[l_size],
291                    rhs_data: Self::Leaf {
292                        size: r_size as u8,
293                        keys: r_keys,
294                        vals: r_vals,
295                    },
296                }
297            }
298            _ => panic!("Expected leaf node"),
299        }
300    }
301
302    /// Remove the sub-tree at `index` from this inner node.
303    ///
304    /// Note that `index` refers to a sub-tree entry and not a key entry as it does for
305    /// `try_inner_insert()`. It is possible to remove the first sub-tree (which can't be inserted
306    /// by `try_inner_insert()`).
307    ///
308    /// Return an indication of the node's health (i.e. below half capacity).
309    pub fn inner_remove(&mut self, index: usize) -> Removed {
310        match *self {
311            Self::Inner {
312                ref mut size,
313                ref mut keys,
314                ref mut tree,
315            } => {
316                let ents = usize::from(*size) + 1;
317                debug_assert!(ents <= tree.len());
318                debug_assert!(index < ents);
319                // Leave an invalid 0xff size when node becomes empty.
320                *size = ents.wrapping_sub(2) as u8;
321                if ents > 1 {
322                    slice_shift(&mut keys[index.saturating_sub(1)..ents - 1], 1);
323                }
324                slice_shift(&mut tree[index..ents], 1);
325                Removed::new(index, ents - 1, tree.len())
326            }
327            _ => panic!("Expected inner node"),
328        }
329    }
330
331    /// Remove the key-value pair at `index` from this leaf node.
332    ///
333    /// Return an indication of the node's health (i.e. below half capacity).
334    pub fn leaf_remove(&mut self, index: usize) -> Removed {
335        match *self {
336            Self::Leaf {
337                ref mut size,
338                ref mut keys,
339                ref mut vals,
340            } => {
341                let sz = usize::from(*size);
342                let keys = keys.borrow_mut();
343                let vals = vals.borrow_mut();
344                *size -= 1;
345                slice_shift(&mut keys[index..sz], 1);
346                slice_shift(&mut vals[index..sz], 1);
347                Removed::new(index, sz - 1, keys.len())
348            }
349            _ => panic!("Expected leaf node"),
350        }
351    }
352
353    /// Balance this node with its right sibling.
354    ///
355    /// It is assumed that the current node has underflowed. Look at the right sibling node and do
356    /// one of two things:
357    ///
358    /// 1. Move all entries to the right node, leaving this node empty, or
359    /// 2. Distribute entries evenly between the two nodes.
360    ///
361    /// In the first case, `None` is returned. In the second case, the new critical key for the
362    /// right sibling node is returned.
363    pub fn balance(&mut self, crit_key: F::Key, rhs: &mut Self) -> Option<F::Key> {
364        match (self, rhs) {
365            (
366                &mut Self::Inner {
367                    size: ref mut l_size,
368                    keys: ref mut l_keys,
369                    tree: ref mut l_tree,
370                },
371                &mut Self::Inner {
372                    size: ref mut r_size,
373                    keys: ref mut r_keys,
374                    tree: ref mut r_tree,
375                },
376            ) => {
377                let l_ents = usize::from(*l_size) + 1;
378                let r_ents = usize::from(*r_size) + 1;
379                let ents = l_ents + r_ents;
380
381                if ents <= r_tree.len() {
382                    // All entries will fit in the RHS node.
383                    // We'll leave the LHS node empty, but first use it as a scratch space.
384                    *l_size = 0;
385                    // Insert `crit_key` between the two nodes.
386                    l_keys[l_ents - 1] = crit_key;
387                    l_keys[l_ents..ents - 1].copy_from_slice(&r_keys[0..r_ents - 1]);
388                    r_keys[0..ents - 1].copy_from_slice(&l_keys[0..ents - 1]);
389                    l_tree[l_ents..ents].copy_from_slice(&r_tree[0..r_ents]);
390                    r_tree[0..ents].copy_from_slice(&l_tree[0..ents]);
391                    *r_size = (ents - 1) as u8;
392                    None
393                } else {
394                    // The entries don't all fit in one node. Distribute some from RHS -> LHS.
395                    // Split evenly with a bias to putting one entry in LHS.
396                    let r_goal = ents / 2;
397                    let l_goal = ents - r_goal;
398                    debug_assert!(l_goal > l_ents, "Node must be underflowed");
399
400                    l_keys[l_ents - 1] = crit_key;
401                    l_keys[l_ents..l_goal - 1].copy_from_slice(&r_keys[0..l_goal - 1 - l_ents]);
402                    l_tree[l_ents..l_goal].copy_from_slice(&r_tree[0..l_goal - l_ents]);
403                    *l_size = (l_goal - 1) as u8;
404
405                    let new_crit = r_keys[r_ents - r_goal - 1];
406                    slice_shift(&mut r_keys[0..r_ents - 1], r_ents - r_goal);
407                    slice_shift(&mut r_tree[0..r_ents], r_ents - r_goal);
408                    *r_size = (r_goal - 1) as u8;
409
410                    Some(new_crit)
411                }
412            }
413            (
414                &mut Self::Leaf {
415                    size: ref mut l_size,
416                    keys: ref mut l_keys,
417                    vals: ref mut l_vals,
418                },
419                &mut Self::Leaf {
420                    size: ref mut r_size,
421                    keys: ref mut r_keys,
422                    vals: ref mut r_vals,
423                },
424            ) => {
425                let l_ents = usize::from(*l_size);
426                let l_keys = l_keys.borrow_mut();
427                let l_vals = l_vals.borrow_mut();
428                let r_ents = usize::from(*r_size);
429                let r_keys = r_keys.borrow_mut();
430                let r_vals = r_vals.borrow_mut();
431                let ents = l_ents + r_ents;
432
433                if ents <= r_vals.len() {
434                    // We can fit all entries in the RHS node.
435                    // We'll leave the LHS node empty, but first use it as a scratch space.
436                    *l_size = 0;
437                    l_keys[l_ents..ents].copy_from_slice(&r_keys[0..r_ents]);
438                    r_keys[0..ents].copy_from_slice(&l_keys[0..ents]);
439                    l_vals[l_ents..ents].copy_from_slice(&r_vals[0..r_ents]);
440                    r_vals[0..ents].copy_from_slice(&l_vals[0..ents]);
441                    *r_size = ents as u8;
442                    None
443                } else {
444                    // The entries don't all fit in one node. Distribute some from RHS -> LHS.
445                    // Split evenly with a bias to putting one entry in LHS.
446                    let r_goal = ents / 2;
447                    let l_goal = ents - r_goal;
448                    debug_assert!(l_goal > l_ents, "Node must be underflowed");
449
450                    l_keys[l_ents..l_goal].copy_from_slice(&r_keys[0..l_goal - l_ents]);
451                    l_vals[l_ents..l_goal].copy_from_slice(&r_vals[0..l_goal - l_ents]);
452                    *l_size = l_goal as u8;
453
454                    slice_shift(&mut r_keys[0..r_ents], r_ents - r_goal);
455                    slice_shift(&mut r_vals[0..r_ents], r_ents - r_goal);
456                    *r_size = r_goal as u8;
457
458                    Some(r_keys[0])
459                }
460            }
461            _ => panic!("Mismatched nodes"),
462        }
463    }
464}
465
466/// Find the right split position for halving a full node with `len` entries to recover from a
467/// failed insertion at `ins`.
468///
469/// If `len` is even, we should split straight down the middle regardless of `len`.
470///
471/// If `len` is odd, we should split the node such that the two halves are the same size after the
472/// insertion is retried.
473fn split_pos(len: usize, ins: usize) -> usize {
474    // Anticipate `len` being a compile time constant, so this all folds away when `len` is even.
475    if ins <= len / 2 {
476        len / 2
477    } else {
478        (len + 1) / 2
479    }
480}
481
482/// The result of splitting off the second half of a node.
483pub(super) struct SplitOff<F: Forest> {
484    /// The number of entries left in the original node which becomes the left-hand-side of the
485    /// pair. This is the number of outgoing node edges for an inner node, and the number of
486    /// key-value pairs for a leaf node.
487    pub lhs_entries: usize,
488
489    /// The number of entries in the new RHS node.
490    pub rhs_entries: usize,
491
492    /// The critical key separating the LHS and RHS nodes. All keys in the LHS sub-tree are less
493    /// than the critical key, and all entries in the RHS sub-tree are greater or equal to the
494    /// critical key.
495    pub crit_key: F::Key,
496
497    /// The RHS node data containing the elements that were removed from the original node (now the
498    /// LHS).
499    pub rhs_data: NodeData<F>,
500}
501
502/// The result of removing an entry from a node.
503#[derive(Clone, Copy, Debug, PartialEq, Eq)]
504pub(super) enum Removed {
505    /// An entry was removed, and the node is still in good shape.
506    Healthy,
507
508    /// The node is in good shape after removing the rightmost element.
509    Rightmost,
510
511    /// The node has too few entries now, and it should be balanced with a sibling node.
512    Underflow,
513
514    /// The last entry was removed. For an inner node, this means that the `keys` array is empty
515    /// and there is just a single sub-tree left.
516    Empty,
517}
518
519impl Removed {
520    /// Create a `Removed` status from a size and capacity.
521    fn new(removed: usize, new_size: usize, capacity: usize) -> Self {
522        if 2 * new_size >= capacity {
523            if removed == new_size {
524                Self::Rightmost
525            } else {
526                Self::Healthy
527            }
528        } else if new_size > 0 {
529            Self::Underflow
530        } else {
531            Self::Empty
532        }
533    }
534}
535
536// Display ": value" or nothing at all for `()`.
537pub(super) trait ValDisp {
538    fn valfmt(&self, f: &mut fmt::Formatter) -> fmt::Result;
539}
540
541impl ValDisp for SetValue {
542    fn valfmt(&self, _: &mut fmt::Formatter) -> fmt::Result {
543        Ok(())
544    }
545}
546
547impl<T: fmt::Display> ValDisp for T {
548    fn valfmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
549        write!(f, ":{self}")
550    }
551}
552
553impl<F> fmt::Display for NodeData<F>
554where
555    F: Forest,
556    F::Key: fmt::Display,
557    F::Value: ValDisp,
558{
559    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
560        match *self {
561            Self::Inner { size, keys, tree } => {
562                write!(f, "[ {}", tree[0])?;
563                for i in 0..usize::from(size) {
564                    write!(f, " {} {}", keys[i], tree[i + 1])?;
565                }
566                write!(f, " ]")
567            }
568            Self::Leaf { size, keys, vals } => {
569                let keys = keys.borrow();
570                let vals = vals.borrow();
571                write!(f, "[")?;
572                for i in 0..usize::from(size) {
573                    write!(f, " {}", keys[i])?;
574                    vals[i].valfmt(f)?;
575                }
576                write!(f, " ]")
577            }
578            Self::Free { next: Some(n) } => write!(f, "[ free -> {n} ]"),
579            Self::Free { next: None } => write!(f, "[ free ]"),
580        }
581    }
582}
583
584#[cfg(test)]
585mod tests {
586    use super::*;
587    use alloc::string::ToString;
588    use core::mem;
589
590    // Forest impl for a set implementation.
591    struct TF();
592
593    impl Forest for TF {
594        type Key = char;
595        type Value = SetValue;
596        type LeafKeys = [char; 15];
597        type LeafValues = [SetValue; 15];
598
599        fn splat_key(key: Self::Key) -> Self::LeafKeys {
600            [key; 15]
601        }
602
603        fn splat_value(value: Self::Value) -> Self::LeafValues {
604            [value; 15]
605        }
606    }
607
608    #[test]
609    fn inner() {
610        let n1 = Node(1);
611        let n2 = Node(2);
612        let n3 = Node(3);
613        let n4 = Node(4);
614        let mut inner = NodeData::<TF>::inner(n1, 'c', n4);
615        assert_eq!(mem::size_of_val(&inner), 64);
616        assert_eq!(inner.to_string(), "[ node1 c node4 ]");
617
618        assert!(inner.try_inner_insert(0, 'a', n2));
619        assert_eq!(inner.to_string(), "[ node1 a node2 c node4 ]");
620
621        assert!(inner.try_inner_insert(1, 'b', n3));
622        assert_eq!(inner.to_string(), "[ node1 a node2 b node3 c node4 ]");
623
624        for i in 3..7 {
625            assert!(inner.try_inner_insert(
626                usize::from(i),
627                ('a' as u8 + i) as char,
628                Node(i as u32 + 2),
629            ));
630        }
631        assert_eq!(
632            inner.to_string(),
633            "[ node1 a node2 b node3 c node4 d node5 e node6 f node7 g node8 ]"
634        );
635
636        // Now the node is full and insertion should fail anywhere.
637        assert!(!inner.try_inner_insert(0, 'x', n3));
638        assert!(!inner.try_inner_insert(4, 'x', n3));
639        assert!(!inner.try_inner_insert(7, 'x', n3));
640
641        // Splitting should be independent of the hint because we have an even number of node
642        // references.
643        let saved = inner;
644        let sp = inner.split(1);
645        assert_eq!(sp.lhs_entries, 4);
646        assert_eq!(sp.rhs_entries, 4);
647        assert_eq!(sp.crit_key, 'd');
648        // The critical key is not present in either of the resulting nodes.
649        assert_eq!(inner.to_string(), "[ node1 a node2 b node3 c node4 ]");
650        assert_eq!(sp.rhs_data.to_string(), "[ node5 e node6 f node7 g node8 ]");
651
652        assert_eq!(inner.inner_remove(0), Removed::Underflow);
653        assert_eq!(inner.to_string(), "[ node2 b node3 c node4 ]");
654
655        assert_eq!(inner.inner_remove(1), Removed::Underflow);
656        assert_eq!(inner.to_string(), "[ node2 c node4 ]");
657
658        assert_eq!(inner.inner_remove(1), Removed::Underflow);
659        assert_eq!(inner.to_string(), "[ node2 ]");
660
661        assert_eq!(inner.inner_remove(0), Removed::Empty);
662
663        inner = saved;
664        let sp = inner.split(6);
665        assert_eq!(sp.lhs_entries, 4);
666        assert_eq!(sp.rhs_entries, 4);
667        assert_eq!(sp.crit_key, 'd');
668        assert_eq!(inner.to_string(), "[ node1 a node2 b node3 c node4 ]");
669        assert_eq!(sp.rhs_data.to_string(), "[ node5 e node6 f node7 g node8 ]");
670    }
671
672    #[test]
673    fn leaf() {
674        let mut leaf = NodeData::<TF>::leaf('d', SetValue());
675        assert_eq!(leaf.to_string(), "[ d ]");
676
677        assert!(leaf.try_leaf_insert(0, 'a', SetValue()));
678        assert_eq!(leaf.to_string(), "[ a d ]");
679        assert!(leaf.try_leaf_insert(1, 'b', SetValue()));
680        assert!(leaf.try_leaf_insert(2, 'c', SetValue()));
681        assert_eq!(leaf.to_string(), "[ a b c d ]");
682        for i in 4..15 {
683            assert!(leaf.try_leaf_insert(usize::from(i), ('a' as u8 + i) as char, SetValue()));
684        }
685        assert_eq!(leaf.to_string(), "[ a b c d e f g h i j k l m n o ]");
686
687        // Now the node is full and insertion should fail anywhere.
688        assert!(!leaf.try_leaf_insert(0, 'x', SetValue()));
689        assert!(!leaf.try_leaf_insert(8, 'x', SetValue()));
690        assert!(!leaf.try_leaf_insert(15, 'x', SetValue()));
691
692        // The index given to `split` is not the split position, it's a hint for balancing the node.
693        let saved = leaf;
694        let sp = leaf.split(12);
695        assert_eq!(sp.lhs_entries, 8);
696        assert_eq!(sp.rhs_entries, 7);
697        assert_eq!(sp.crit_key, 'i');
698        assert_eq!(leaf.to_string(), "[ a b c d e f g h ]");
699        assert_eq!(sp.rhs_data.to_string(), "[ i j k l m n o ]");
700
701        assert!(leaf.try_leaf_insert(8, 'i', SetValue()));
702        assert_eq!(leaf.leaf_remove(2), Removed::Healthy);
703        assert_eq!(leaf.to_string(), "[ a b d e f g h i ]");
704        assert_eq!(leaf.leaf_remove(7), Removed::Underflow);
705        assert_eq!(leaf.to_string(), "[ a b d e f g h ]");
706
707        leaf = saved;
708        let sp = leaf.split(7);
709        assert_eq!(sp.lhs_entries, 7);
710        assert_eq!(sp.rhs_entries, 8);
711        assert_eq!(sp.crit_key, 'h');
712        assert_eq!(leaf.to_string(), "[ a b c d e f g ]");
713        assert_eq!(sp.rhs_data.to_string(), "[ h i j k l m n o ]");
714    }
715
716    #[test]
717    fn optimal_split_pos() {
718        // An even split is easy.
719        assert_eq!(split_pos(8, 0), 4);
720        assert_eq!(split_pos(8, 8), 4);
721
722        // Easy cases for odd splits.
723        assert_eq!(split_pos(7, 0), 3);
724        assert_eq!(split_pos(7, 7), 4);
725
726        // If the insertion point is the same as the split position, we
727        // will append to the lhs node.
728        assert_eq!(split_pos(7, 3), 3);
729        assert_eq!(split_pos(7, 4), 4);
730    }
731
732    #[test]
733    fn inner_balance() {
734        let n1 = Node(1);
735        let n2 = Node(2);
736        let n3 = Node(3);
737        let mut lhs = NodeData::<TF>::inner(n1, 'a', n2);
738        assert!(lhs.try_inner_insert(1, 'b', n3));
739        assert_eq!(lhs.to_string(), "[ node1 a node2 b node3 ]");
740
741        let n11 = Node(11);
742        let n12 = Node(12);
743        let mut rhs = NodeData::<TF>::inner(n11, 'p', n12);
744
745        for i in 1..4 {
746            assert!(rhs.try_inner_insert(
747                usize::from(i),
748                ('p' as u8 + i) as char,
749                Node(i as u32 + 12),
750            ));
751        }
752        assert_eq!(
753            rhs.to_string(),
754            "[ node11 p node12 q node13 r node14 s node15 ]"
755        );
756
757        // 3+5 elements fit in RHS.
758        assert_eq!(lhs.balance('o', &mut rhs), None);
759        assert_eq!(
760            rhs.to_string(),
761            "[ node1 a node2 b node3 o node11 p node12 q node13 r node14 s node15 ]"
762        );
763
764        // 2+8 elements are redistributed.
765        lhs = NodeData::<TF>::inner(Node(20), 'x', Node(21));
766        assert_eq!(lhs.balance('y', &mut rhs), Some('o'));
767        assert_eq!(
768            lhs.to_string(),
769            "[ node20 x node21 y node1 a node2 b node3 ]"
770        );
771        assert_eq!(
772            rhs.to_string(),
773            "[ node11 p node12 q node13 r node14 s node15 ]"
774        );
775    }
776
777    #[test]
778    fn leaf_balance() {
779        let mut lhs = NodeData::<TF>::leaf('a', SetValue());
780        for i in 1..6 {
781            assert!(lhs.try_leaf_insert(usize::from(i), ('a' as u8 + i) as char, SetValue()));
782        }
783        assert_eq!(lhs.to_string(), "[ a b c d e f ]");
784
785        let mut rhs = NodeData::<TF>::leaf('0', SetValue());
786        for i in 1..8 {
787            assert!(rhs.try_leaf_insert(usize::from(i), ('0' as u8 + i) as char, SetValue()));
788        }
789        assert_eq!(rhs.to_string(), "[ 0 1 2 3 4 5 6 7 ]");
790
791        // 6+8 elements all fits in rhs.
792        assert_eq!(lhs.balance('0', &mut rhs), None);
793        assert_eq!(rhs.to_string(), "[ a b c d e f 0 1 2 3 4 5 6 7 ]");
794
795        assert!(lhs.try_leaf_insert(0, 'x', SetValue()));
796        assert!(lhs.try_leaf_insert(1, 'y', SetValue()));
797        assert!(lhs.try_leaf_insert(2, 'z', SetValue()));
798        assert_eq!(lhs.to_string(), "[ x y z ]");
799
800        // 3+14 elements need redistribution.
801        assert_eq!(lhs.balance('a', &mut rhs), Some('0'));
802        assert_eq!(lhs.to_string(), "[ x y z a b c d e f ]");
803        assert_eq!(rhs.to_string(), "[ 0 1 2 3 4 5 6 7 ]");
804    }
805}
cranelift_bforest/node.rs

cranelift_bforest/
node.rs
