]>
Commit | Line | Data |
---|---|---|
29967ef6 | 1 | use super::super::navigate; |
3dfed10e | 2 | use super::*; |
29967ef6 XL |
3 | use crate::fmt::Debug; |
4 | use crate::string::String; | |
29967ef6 XL |
5 | |
6 | impl<'a, K: 'a, V: 'a> NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal> { | |
fc512014 | 7 | // Asserts that the back pointer in each reachable node points to its parent. |
29967ef6 XL |
8 | pub fn assert_back_pointers(self) { |
9 | if let ForceResult::Internal(node) = self.force() { | |
10 | for idx in 0..=node.len() { | |
11 | let edge = unsafe { Handle::new_edge(node, idx) }; | |
12 | let child = edge.descend(); | |
13 | assert!(child.ascend().ok() == Some(edge)); | |
14 | child.assert_back_pointers(); | |
15 | } | |
16 | } | |
17 | } | |
18 | ||
fc512014 XL |
19 | // Renders a multi-line display of the keys in order and in tree hierarchy, |
20 | // picturing the tree growing sideways from its root on the left to its | |
21 | // leaves on the right. | |
29967ef6 XL |
22 | pub fn dump_keys(self) -> String |
23 | where | |
24 | K: Debug, | |
25 | { | |
26 | let mut result = String::new(); | |
27 | self.visit_nodes_in_order(|pos| match pos { | |
28 | navigate::Position::Leaf(leaf) => { | |
29 | let depth = self.height(); | |
30 | let indent = " ".repeat(depth); | |
5869c6ff | 31 | result += &format!("\n{}{:?}", indent, leaf.keys()); |
29967ef6 XL |
32 | } |
33 | navigate::Position::Internal(_) => {} | |
34 | navigate::Position::InternalKV(kv) => { | |
35 | let depth = self.height() - kv.into_node().height(); | |
36 | let indent = " ".repeat(depth); | |
37 | result += &format!("\n{}{:?}", indent, kv.into_kv().0); | |
38 | } | |
39 | }); | |
40 | result | |
41 | } | |
42 | } | |
3dfed10e XL |
43 | |
44 | #[test] | |
45 | fn test_splitpoint() { | |
46 | for idx in 0..=CAPACITY { | |
47 | let (middle_kv_idx, insertion) = splitpoint(idx); | |
48 | ||
49 | // Simulate performing the split: | |
50 | let mut left_len = middle_kv_idx; | |
51 | let mut right_len = CAPACITY - middle_kv_idx - 1; | |
52 | match insertion { | |
fc512014 | 53 | LeftOrRight::Left(edge_idx) => { |
3dfed10e XL |
54 | assert!(edge_idx <= left_len); |
55 | left_len += 1; | |
56 | } | |
fc512014 | 57 | LeftOrRight::Right(edge_idx) => { |
3dfed10e XL |
58 | assert!(edge_idx <= right_len); |
59 | right_len += 1; | |
60 | } | |
61 | } | |
29967ef6 XL |
62 | assert!(left_len >= MIN_LEN_AFTER_SPLIT); |
63 | assert!(right_len >= MIN_LEN_AFTER_SPLIT); | |
3dfed10e XL |
64 | assert!(left_len + right_len == CAPACITY); |
65 | } | |
66 | } | |
1b1a35ee | 67 | |
29967ef6 | 68 | #[test] |
6a06907d | 69 | fn test_partial_eq() { |
fc512014 | 70 | let mut root1 = NodeRef::new_leaf(); |
5869c6ff XL |
71 | root1.borrow_mut().push(1, ()); |
72 | let mut root1 = NodeRef::new_internal(root1.forget_type()).forget_type(); | |
fc512014 XL |
73 | let root2 = Root::new(); |
74 | root1.reborrow().assert_back_pointers(); | |
75 | root2.reborrow().assert_back_pointers(); | |
29967ef6 | 76 | |
fc512014 XL |
77 | let leaf_edge_1a = root1.reborrow().first_leaf_edge().forget_node_type(); |
78 | let leaf_edge_1b = root1.reborrow().last_leaf_edge().forget_node_type(); | |
79 | let top_edge_1 = root1.reborrow().first_edge(); | |
80 | let top_edge_2 = root2.reborrow().first_edge(); | |
29967ef6 XL |
81 | |
82 | assert!(leaf_edge_1a == leaf_edge_1a); | |
83 | assert!(leaf_edge_1a != leaf_edge_1b); | |
84 | assert!(leaf_edge_1a != top_edge_1); | |
85 | assert!(leaf_edge_1a != top_edge_2); | |
86 | assert!(top_edge_1 == top_edge_1); | |
87 | assert!(top_edge_1 != top_edge_2); | |
88 | ||
29967ef6 | 89 | root1.pop_internal_level(); |
5869c6ff XL |
90 | unsafe { root1.into_dying().deallocate_and_ascend() }; |
91 | unsafe { root2.into_dying().deallocate_and_ascend() }; | |
29967ef6 XL |
92 | } |
93 | ||
1b1a35ee XL |
94 | #[test] |
95 | #[cfg(target_arch = "x86_64")] | |
96 | fn test_sizes() { | |
97 | assert_eq!(core::mem::size_of::<LeafNode<(), ()>>(), 16); | |
6a06907d XL |
98 | assert_eq!(core::mem::size_of::<LeafNode<i64, i64>>(), 16 + CAPACITY * 2 * 8); |
99 | assert_eq!(core::mem::size_of::<InternalNode<(), ()>>(), 16 + (CAPACITY + 1) * 8); | |
100 | assert_eq!(core::mem::size_of::<InternalNode<i64, i64>>(), 16 + (CAPACITY * 3 + 1) * 8); | |
1b1a35ee | 101 | } |