1 //! B+-tree nodes.
2
3 use super::{Forest, INNER_SIZE, Node, SetValue, slice_insert, slice_shift};
4 use core::borrow::{Borrow, BorrowMut};
5 use 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.
16 pub(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`.
47 impl<F: Forest> Copy for NodeData<F> {}
48 impl<F: Forest> Clone for NodeData<F> {
clone(&self) -> Self49 fn clone(&self) -> Self {
50 *self
51 }
52 }
53
54 impl<F: Forest> NodeData<F> {
55 /// Is this a free/unused node?
is_free(&self) -> bool56 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.
entries(&self) -> usize67 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.
inner(left: Node, key: F::Key, right: Node) -> Self76 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.
leaf(key: F::Key, value: F::Value) -> Self89 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).
unwrap_inner(&self) -> (&[F::Key], &[Node])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.
unwrap_leaf(&self) -> (&[F::Key], &[F::Value])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.
unwrap_leaf_mut(&mut self) -> (&mut [F::Key], &mut [F::Value])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.
leaf_crit_key(&self) -> F::Key154 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.
try_inner_insert(&mut self, index: usize, key: F::Key, node: Node) -> bool167 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.
try_leaf_insert(&mut self, index: usize, key: F::Key, value: F::Value) -> bool193 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.
split(&mut self, insert_index: usize) -> SplitOff<F>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).
inner_remove(&mut self, index: usize) -> Removed309 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).
leaf_remove(&mut self, index: usize) -> Removed334 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.
balance(&mut self, crit_key: F::Key, rhs: &mut Self) -> Option<F::Key>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.
split_pos(len: usize, ins: usize) -> usize473 fn 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.
483 pub(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)]
504 pub(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
519 impl Removed {
520 /// Create a `Removed` status from a size and capacity.
new(removed: usize, new_size: usize, capacity: usize) -> Self521 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 `()`.
537 pub(super) trait ValDisp {
valfmt(&self, f: &mut fmt::Formatter) -> fmt::Result538 fn valfmt(&self, f: &mut fmt::Formatter) -> fmt::Result;
539 }
540
541 impl ValDisp for SetValue {
valfmt(&self, _: &mut fmt::Formatter) -> fmt::Result542 fn valfmt(&self, _: &mut fmt::Formatter) -> fmt::Result {
543 Ok(())
544 }
545 }
546
547 impl<T: fmt::Display> ValDisp for T {
valfmt(&self, f: &mut fmt::Formatter) -> fmt::Result548 fn valfmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
549 write!(f, ":{self}")
550 }
551 }
552
553 impl<F> fmt::Display for NodeData<F>
554 where
555 F: Forest,
556 F::Key: fmt::Display,
557 F::Value: ValDisp,
558 {
fmt(&self, f: &mut fmt::Formatter) -> fmt::Result559 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)]
585 mod 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
splat_key(key: Self::Key) -> Self::LeafKeys599 fn splat_key(key: Self::Key) -> Self::LeafKeys {
600 [key; 15]
601 }
602
splat_value(value: Self::Value) -> Self::LeafValues603 fn splat_value(value: Self::Value) -> Self::LeafValues {
604 [value; 15]
605 }
606 }
607
608 #[test]
inner()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]
leaf()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]
optimal_split_pos()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]
inner_balance()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]
leaf_balance()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 }
806