library/alloc/src/collections/btree/node/tests.rs

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