diff options
| -rw-r--r-- | library/alloc/src/collections/btree/map/tests.rs | 89 | ||||
| -rw-r--r-- | library/alloc/src/collections/btree/node/tests.rs | 105 |
2 files changed, 115 insertions, 79 deletions
diff --git a/library/alloc/src/collections/btree/map/tests.rs b/library/alloc/src/collections/btree/map/tests.rs index 118e173bb16..b51b95a635c 100644 --- a/library/alloc/src/collections/btree/map/tests.rs +++ b/library/alloc/src/collections/btree/map/tests.rs @@ -1,4 +1,4 @@ -use super::super::{navigate::Position, node, DeterministicRng}; +use super::super::{node, DeterministicRng}; use super::Entry::{Occupied, Vacant}; use super::*; use crate::boxed::Box; @@ -7,7 +7,7 @@ use crate::rc::Rc; use crate::string::{String, ToString}; use crate::vec::Vec; use std::convert::TryFrom; -use std::iter::FromIterator; +use std::iter::{self, FromIterator}; use std::mem; use std::ops::Bound::{self, Excluded, Included, Unbounded}; use std::ops::RangeBounds; @@ -42,19 +42,6 @@ fn test_all_refs<'a, T: 'a>(dummy: &mut T, iter: impl Iterator<Item = &'a mut T> } } -struct SeriesChecker<T> { - previous: Option<T>, -} - -impl<T: Copy + Debug + Ord> SeriesChecker<T> { - fn is_ascending(&mut self, next: T) { - if let Some(previous) = self.previous { - assert!(previous < next, "{:?} >= {:?}", previous, next); - } - self.previous = Some(next); - } -} - impl<'a, K: 'a, V: 'a> BTreeMap<K, V> { /// Panics if the map (or the code navigating it) is corrupted. fn check(&self) @@ -63,44 +50,10 @@ impl<'a, K: 'a, V: 'a> BTreeMap<K, V> { { if let Some(root) = &self.root { let root_node = root.node_as_ref(); - let mut checker = SeriesChecker { previous: None }; - let mut internal_length = 0; - let mut internal_kv_count = 0; - let mut leaf_length = 0; - root_node.visit_nodes_in_order(|pos| match pos { - Position::Leaf(node) => { - let is_root = root_node.height() == 0; - let min_len = if is_root { 0 } else { node::MIN_LEN }; - assert!(node.len() >= min_len, "{} < {}", node.len(), min_len); - - for idx in 0..node.len() { - let key = *unsafe { node.key_at(idx) }; - checker.is_ascending(key); - } - leaf_length += node.len(); - } - Position::Internal(node) => { - let is_root = root_node.height() == node.height(); - let min_len = if is_root { 1 } else { node::MIN_LEN }; - assert!(node.len() >= min_len, "{} < {}", node.len(), min_len); - - for idx in 0..=node.len() { - let edge = unsafe { node::Handle::new_edge(node, idx) }; - assert!(edge.descend().ascend().ok().unwrap() == edge); - } - - internal_length += node.len(); - } - Position::InternalKV(kv) => { - let key = *kv.into_kv().0; - checker.is_ascending(key); - - internal_kv_count += 1; - } - }); - assert_eq!(internal_length, internal_kv_count); - assert_eq!(root_node.calc_length(), internal_length + leaf_length); - assert_eq!(self.length, internal_length + leaf_length); + assert!(root_node.ascend().is_err()); + root_node.assert_back_pointers(); + root_node.assert_ascending(); + assert_eq!(self.length, root_node.assert_and_add_lengths()); } else { assert_eq!(self.length, 0); } @@ -116,28 +69,7 @@ impl<'a, K: 'a, V: 'a> BTreeMap<K, V> { K: Debug, { if let Some(root) = self.root.as_ref() { - let mut result = String::new(); - let root_node = root.node_as_ref(); - root_node.visit_nodes_in_order(|pos| match pos { - Position::Leaf(leaf) => { - let depth = root_node.height(); - let indent = " ".repeat(depth); - result += &format!("\n{}", indent); - for idx in 0..leaf.len() { - if idx > 0 { - result += ", "; - } - result += &format!("{:?}", unsafe { leaf.key_at(idx) }); - } - } - Position::Internal(_) => {} - Position::InternalKV(kv) => { - let depth = root_node.height() - kv.into_node().height(); - let indent = " ".repeat(depth); - result += &format!("\n{}{:?}", indent, kv.into_kv().0); - } - }); - result + root.node_as_ref().dump_keys() } else { String::from("not yet allocated") } @@ -170,7 +102,6 @@ fn test_levels() { let last_key = *map.last_key_value().unwrap().0; map.insert(last_key + 1, ()); } - println!("{}", map.dump_keys()); map.check(); // Structure: // - 1 element in internal root node with 2 children @@ -372,7 +303,7 @@ fn test_iter_rev() { fn do_test_iter_mut_mutation<T>(size: usize) where T: Copy + Debug + Ord + TryFrom<usize>, - <T as std::convert::TryFrom<usize>>::Error: std::fmt::Debug, + <T as TryFrom<usize>>::Error: Debug, { let zero = T::try_from(0).unwrap(); let mut map: BTreeMap<T, T> = (0..size).map(|i| (T::try_from(i).unwrap(), zero)).collect(); @@ -857,7 +788,7 @@ mod test_drain_filter { fn consuming_nothing() { let pairs = (0..3).map(|i| (i, i)); let mut map: BTreeMap<_, _> = pairs.collect(); - assert!(map.drain_filter(|_, _| false).eq(std::iter::empty())); + assert!(map.drain_filter(|_, _| false).eq(iter::empty())); map.check(); } @@ -878,7 +809,7 @@ mod test_drain_filter { *v += 6; false }) - .eq(std::iter::empty()) + .eq(iter::empty()) ); assert!(map.keys().copied().eq(0..3)); assert!(map.values().copied().eq(6..9)); diff --git a/library/alloc/src/collections/btree/node/tests.rs b/library/alloc/src/collections/btree/node/tests.rs index 2ef9aad0ccd..e56fc2aa51e 100644 --- a/library/alloc/src/collections/btree/node/tests.rs +++ b/library/alloc/src/collections/btree/node/tests.rs @@ -1,6 +1,111 @@ +use super::super::navigate; use super::*; +use crate::fmt::Debug; +use crate::string::String; use core::cmp::Ordering::*; +impl<'a, K: 'a, V: 'a> NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal> { + pub fn assert_back_pointers(self) { + match self.force() { + ForceResult::Leaf(_) => {} + ForceResult::Internal(node) => { + for idx in 0..=node.len() { + let edge = unsafe { Handle::new_edge(node, idx) }; + let child = edge.descend(); + assert!(child.ascend().ok() == Some(edge)); + child.assert_back_pointers(); + } + } + } + } + + pub fn assert_ascending(self) + where + K: Copy + Debug + Ord, + { + struct SeriesChecker<T> { + previous: Option<T>, + } + impl<T: Copy + Debug + Ord> SeriesChecker<T> { + fn is_ascending(&mut self, next: T) { + if let Some(previous) = self.previous { + assert!(previous < next, "{:?} >= {:?}", previous, next); + } + self.previous = Some(next); + } + } + + let mut checker = SeriesChecker { previous: None }; + self.visit_nodes_in_order(|pos| match pos { + navigate::Position::Leaf(node) => { + for idx in 0..node.len() { + let key = *unsafe { node.key_at(idx) }; + checker.is_ascending(key); + } + } + navigate::Position::InternalKV(kv) => { + let key = *kv.into_kv().0; + checker.is_ascending(key); + } + navigate::Position::Internal(_) => {} + }); + } + + pub fn assert_and_add_lengths(self) -> usize { + let mut internal_length = 0; + let mut internal_kv_count = 0; + let mut leaf_length = 0; + self.visit_nodes_in_order(|pos| match pos { + navigate::Position::Leaf(node) => { + let is_root = self.height() == 0; + let min_len = if is_root { 0 } else { MIN_LEN }; + assert!(node.len() >= min_len, "{} < {}", node.len(), min_len); + leaf_length += node.len(); + } + navigate::Position::Internal(node) => { + let is_root = self.height() == node.height(); + let min_len = if is_root { 1 } else { MIN_LEN }; + assert!(node.len() >= min_len, "{} < {}", node.len(), min_len); + internal_length += node.len(); + } + navigate::Position::InternalKV(_) => { + internal_kv_count += 1; + } + }); + assert_eq!(internal_length, internal_kv_count); + let total = internal_length + leaf_length; + assert_eq!(self.calc_length(), total); + total + } + + pub fn dump_keys(self) -> String + where + K: Debug, + { + let mut result = String::new(); + self.visit_nodes_in_order(|pos| match pos { + navigate::Position::Leaf(leaf) => { + let depth = self.height(); + let indent = " ".repeat(depth); + result += &format!("\n{}", indent); + for idx in 0..leaf.len() { + if idx > 0 { + result += ", "; + } + result += &format!("{:?}", unsafe { leaf.key_at(idx) }); + } + } + navigate::Position::Internal(_) => {} + navigate::Position::InternalKV(kv) => { + let depth = self.height() - kv.into_node().height(); + let indent = " ".repeat(depth); + result += &format!("\n{}{:?}", indent, kv.into_kv().0); + } + }); + result + } +} + #[test] fn test_splitpoint() { for idx in 0..=CAPACITY { |