Check that all leaf nodes in the tree are reachable via the linked list.
(&self)
| 96 | |
| 97 | /// Check that all leaf nodes in the tree are reachable via the linked list. |
| 98 | fn check_leaf_linked_list_completeness(&self) -> TreeResult<()> { |
| 99 | // Collect all leaf node IDs from the tree structure |
| 100 | let mut tree_leaf_ids = Vec::new(); |
| 101 | self.collect_leaf_ids(&self.root, &mut tree_leaf_ids); |
| 102 | tree_leaf_ids.sort(); |
| 103 | |
| 104 | // Collect all leaf node IDs from the linked list |
| 105 | let mut linked_list_ids = Vec::new(); |
| 106 | let mut current_id = self.get_first_leaf_id(); |
| 107 | while let Some(id) = current_id { |
| 108 | linked_list_ids.push(id); |
| 109 | if let Some(leaf) = self.get_leaf(id) { |
| 110 | current_id = if leaf.next != crate::types::NULL_NODE { |
| 111 | Some(leaf.next) |
| 112 | } else { |
| 113 | None |
| 114 | }; |
| 115 | } else { |
| 116 | break; |
| 117 | } |
| 118 | } |
| 119 | linked_list_ids.sort(); |
| 120 | |
| 121 | // Compare the two lists |
| 122 | if tree_leaf_ids != linked_list_ids { |
| 123 | return Err(BPlusTreeError::corrupted_tree( |
| 124 | "Linked list", |
| 125 | &format!( |
| 126 | "tree has {:?}, linked list has {:?}", |
| 127 | tree_leaf_ids, linked_list_ids |
| 128 | ), |
| 129 | )); |
| 130 | } |
| 131 | |
| 132 | Ok(()) |
| 133 | } |
| 134 | |
| 135 | /// Collect all leaf node IDs from the tree structure. |
| 136 | fn collect_leaf_ids(&self, node: &NodeRef<K, V>, ids: &mut Vec<NodeId>) { |
no test coverage detected