Move btree unit test to their native, privileged location

5 files changed, 20 insertions, 2184 deletions

diff --git a/library/alloc/tests/btree/map.rs b/library/alloc/tests/btree/map.rs
deleted file mode 100644
index 5777bd60907..00000000000
--- a/library/alloc/tests/btree/map.rs
+++ /dev/null
@@ -1,1487 +0,0 @@
-use std::collections::btree_map::Entry::{Occupied, Vacant};
-use std::collections::BTreeMap;
-use std::convert::TryFrom;
-use std::fmt::Debug;
-use std::iter::FromIterator;
-use std::mem;
-use std::ops::Bound::{self, Excluded, Included, Unbounded};
-use std::ops::RangeBounds;
-use std::panic::{catch_unwind, AssertUnwindSafe};
-use std::rc::Rc;
-use std::sync::atomic::{AtomicUsize, Ordering};
-
-use super::DeterministicRng;
-
-// Value of node::CAPACITY, thus capacity of a tree with a single level,
-// i.e. a tree who's root is a leaf node at height 0.
-const NODE_CAPACITY: usize = 11;
-
-// Minimum number of elements to insert in order to guarantee a tree with 2 levels,
-// i.e. a tree who's root is an internal node at height 1, with edges to leaf nodes.
-// It's not the minimum size: removing an element from such a tree does not always reduce height.
-const MIN_INSERTS_HEIGHT_1: usize = NODE_CAPACITY + 1;
-
-// Minimum number of elements to insert in order to guarantee a tree with 3 levels,
-// i.e. a tree who's root is an internal node at height 2, with edges to more internal nodes.
-// It's not the minimum size: removing an element from such a tree does not always reduce height.
-const MIN_INSERTS_HEIGHT_2: usize = NODE_CAPACITY + (NODE_CAPACITY + 1) * NODE_CAPACITY + 1;
-
-// Gather all references from a mutable iterator and make sure Miri notices if
-// using them is dangerous.
-fn test_all_refs<'a, T: 'a>(dummy: &mut T, iter: impl Iterator<Item = &'a mut T>) {
-    // Gather all those references.
-    let mut refs: Vec<&mut T> = iter.collect();
-    // Use them all. Twice, to be sure we got all interleavings.
-    for r in refs.iter_mut() {
-        mem::swap(dummy, r);
-    }
-    for r in refs {
-        mem::swap(dummy, r);
-    }
-}
-
-#[test]
-fn test_basic_large() {
-    let mut map = BTreeMap::new();
-    // Miri is too slow
-    let size = if cfg!(miri) { MIN_INSERTS_HEIGHT_2 } else { 10000 };
-    assert_eq!(map.len(), 0);
-
-    for i in 0..size {
-        assert_eq!(map.insert(i, 10 * i), None);
-        assert_eq!(map.len(), i + 1);
-    }
-
-    assert_eq!(map.first_key_value(), Some((&0, &0)));
-    assert_eq!(map.last_key_value(), Some((&(size - 1), &(10 * (size - 1)))));
-    assert_eq!(map.first_entry().unwrap().key(), &0);
-    assert_eq!(map.last_entry().unwrap().key(), &(size - 1));
-
-    for i in 0..size {
-        assert_eq!(map.get(&i).unwrap(), &(i * 10));
-    }
-
-    for i in size..size * 2 {
-        assert_eq!(map.get(&i), None);
-    }
-
-    for i in 0..size {
-        assert_eq!(map.insert(i, 100 * i), Some(10 * i));
-        assert_eq!(map.len(), size);
-    }
-
-    for i in 0..size {
-        assert_eq!(map.get(&i).unwrap(), &(i * 100));
-    }
-
-    for i in 0..size / 2 {
-        assert_eq!(map.remove(&(i * 2)), Some(i * 200));
-        assert_eq!(map.len(), size - i - 1);
-    }
-
-    for i in 0..size / 2 {
-        assert_eq!(map.get(&(2 * i)), None);
-        assert_eq!(map.get(&(2 * i + 1)).unwrap(), &(i * 200 + 100));
-    }
-
-    for i in 0..size / 2 {
-        assert_eq!(map.remove(&(2 * i)), None);
-        assert_eq!(map.remove(&(2 * i + 1)), Some(i * 200 + 100));
-        assert_eq!(map.len(), size / 2 - i - 1);
-    }
-}
-
-#[test]
-fn test_basic_small() {
-    let mut map = BTreeMap::new();
-    // Empty, root is absent (None):
-    assert_eq!(map.remove(&1), None);
-    assert_eq!(map.len(), 0);
-    assert_eq!(map.get(&1), None);
-    assert_eq!(map.get_mut(&1), None);
-    assert_eq!(map.first_key_value(), None);
-    assert_eq!(map.last_key_value(), None);
-    assert_eq!(map.keys().count(), 0);
-    assert_eq!(map.values().count(), 0);
-    assert_eq!(map.range(..).next(), None);
-    assert_eq!(map.range(..1).next(), None);
-    assert_eq!(map.range(1..).next(), None);
-    assert_eq!(map.range(1..=1).next(), None);
-    assert_eq!(map.range(1..2).next(), None);
-    assert_eq!(map.insert(1, 1), None);
-
-    // 1 key-value pair:
-    assert_eq!(map.len(), 1);
-    assert_eq!(map.get(&1), Some(&1));
-    assert_eq!(map.get_mut(&1), Some(&mut 1));
-    assert_eq!(map.first_key_value(), Some((&1, &1)));
-    assert_eq!(map.last_key_value(), Some((&1, &1)));
-    assert_eq!(map.keys().collect::<Vec<_>>(), vec![&1]);
-    assert_eq!(map.values().collect::<Vec<_>>(), vec![&1]);
-    assert_eq!(map.insert(1, 2), Some(1));
-    assert_eq!(map.len(), 1);
-    assert_eq!(map.get(&1), Some(&2));
-    assert_eq!(map.get_mut(&1), Some(&mut 2));
-    assert_eq!(map.first_key_value(), Some((&1, &2)));
-    assert_eq!(map.last_key_value(), Some((&1, &2)));
-    assert_eq!(map.keys().collect::<Vec<_>>(), vec![&1]);
-    assert_eq!(map.values().collect::<Vec<_>>(), vec![&2]);
-    assert_eq!(map.insert(2, 4), None);
-
-    // 2 key-value pairs:
-    assert_eq!(map.len(), 2);
-    assert_eq!(map.get(&2), Some(&4));
-    assert_eq!(map.get_mut(&2), Some(&mut 4));
-    assert_eq!(map.first_key_value(), Some((&1, &2)));
-    assert_eq!(map.last_key_value(), Some((&2, &4)));
-    assert_eq!(map.keys().collect::<Vec<_>>(), vec![&1, &2]);
-    assert_eq!(map.values().collect::<Vec<_>>(), vec![&2, &4]);
-    assert_eq!(map.remove(&1), Some(2));
-
-    // 1 key-value pair:
-    assert_eq!(map.len(), 1);
-    assert_eq!(map.get(&1), None);
-    assert_eq!(map.get_mut(&1), None);
-    assert_eq!(map.get(&2), Some(&4));
-    assert_eq!(map.get_mut(&2), Some(&mut 4));
-    assert_eq!(map.first_key_value(), Some((&2, &4)));
-    assert_eq!(map.last_key_value(), Some((&2, &4)));
-    assert_eq!(map.keys().collect::<Vec<_>>(), vec![&2]);
-    assert_eq!(map.values().collect::<Vec<_>>(), vec![&4]);
-    assert_eq!(map.remove(&2), Some(4));
-
-    // Empty but root is owned (Some(...)):
-    assert_eq!(map.len(), 0);
-    assert_eq!(map.get(&1), None);
-    assert_eq!(map.get_mut(&1), None);
-    assert_eq!(map.first_key_value(), None);
-    assert_eq!(map.last_key_value(), None);
-    assert_eq!(map.keys().count(), 0);
-    assert_eq!(map.values().count(), 0);
-    assert_eq!(map.range(..).next(), None);
-    assert_eq!(map.range(..1).next(), None);
-    assert_eq!(map.range(1..).next(), None);
-    assert_eq!(map.range(1..=1).next(), None);
-    assert_eq!(map.range(1..2).next(), None);
-    assert_eq!(map.remove(&1), None);
-}
-
-#[test]
-fn test_iter() {
-    // Miri is too slow
-    let size = if cfg!(miri) { 200 } else { 10000 };
-
-    let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
-
-    fn test<T>(size: usize, mut iter: T)
-    where
-        T: Iterator<Item = (usize, usize)>,
-    {
-        for i in 0..size {
-            assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
-            assert_eq!(iter.next().unwrap(), (i, i));
-        }
-        assert_eq!(iter.size_hint(), (0, Some(0)));
-        assert_eq!(iter.next(), None);
-    }
-    test(size, map.iter().map(|(&k, &v)| (k, v)));
-    test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
-    test(size, map.into_iter());
-}
-
-#[test]
-fn test_iter_rev() {
-    // Miri is too slow
-    let size = if cfg!(miri) { 200 } else { 10000 };
-
-    let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
-
-    fn test<T>(size: usize, mut iter: T)
-    where
-        T: Iterator<Item = (usize, usize)>,
-    {
-        for i in 0..size {
-            assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
-            assert_eq!(iter.next().unwrap(), (size - i - 1, size - i - 1));
-        }
-        assert_eq!(iter.size_hint(), (0, Some(0)));
-        assert_eq!(iter.next(), None);
-    }
-    test(size, map.iter().rev().map(|(&k, &v)| (k, v)));
-    test(size, map.iter_mut().rev().map(|(&k, &mut v)| (k, v)));
-    test(size, map.into_iter().rev());
-}
-
-/// Specifically tests iter_mut's ability to mutate the value of pairs in-line
-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,
-{
-    let zero = T::try_from(0).unwrap();
-    let mut map: BTreeMap<T, T> = (0..size).map(|i| (T::try_from(i).unwrap(), zero)).collect();
-
-    // Forward and backward iteration sees enough pairs (also tested elsewhere)
-    assert_eq!(map.iter_mut().count(), size);
-    assert_eq!(map.iter_mut().rev().count(), size);
-
-    // Iterate forwards, trying to mutate to unique values
-    for (i, (k, v)) in map.iter_mut().enumerate() {
-        assert_eq!(*k, T::try_from(i).unwrap());
-        assert_eq!(*v, zero);
-        *v = T::try_from(i + 1).unwrap();
-    }
-
-    // Iterate backwards, checking that mutations succeeded and trying to mutate again
-    for (i, (k, v)) in map.iter_mut().rev().enumerate() {
-        assert_eq!(*k, T::try_from(size - i - 1).unwrap());
-        assert_eq!(*v, T::try_from(size - i).unwrap());
-        *v = T::try_from(2 * size - i).unwrap();
-    }
-
-    // Check that backward mutations succeeded
-    for (i, (k, v)) in map.iter_mut().enumerate() {
-        assert_eq!(*k, T::try_from(i).unwrap());
-        assert_eq!(*v, T::try_from(size + i + 1).unwrap());
-    }
-}
-
-#[derive(Clone, Copy, Debug, Eq, PartialEq, PartialOrd, Ord)]
-#[repr(align(32))]
-struct Align32(usize);
-
-impl TryFrom<usize> for Align32 {
-    type Error = ();
-
-    fn try_from(s: usize) -> Result<Align32, ()> {
-        Ok(Align32(s))
-    }
-}
-
-#[test]
-fn test_iter_mut_mutation() {
-    // Check many alignments and trees with roots at various heights.
-    do_test_iter_mut_mutation::<u8>(0);
-    do_test_iter_mut_mutation::<u8>(1);
-    do_test_iter_mut_mutation::<u8>(MIN_INSERTS_HEIGHT_1);
-    do_test_iter_mut_mutation::<u8>(127); // not enough unique values to test MIN_INSERTS_HEIGHT_2
-    do_test_iter_mut_mutation::<u16>(1);
-    do_test_iter_mut_mutation::<u16>(MIN_INSERTS_HEIGHT_1);
-    do_test_iter_mut_mutation::<u16>(MIN_INSERTS_HEIGHT_2);
-    do_test_iter_mut_mutation::<u32>(1);
-    do_test_iter_mut_mutation::<u32>(MIN_INSERTS_HEIGHT_1);
-    do_test_iter_mut_mutation::<u32>(MIN_INSERTS_HEIGHT_2);
-    do_test_iter_mut_mutation::<u64>(1);
-    do_test_iter_mut_mutation::<u64>(MIN_INSERTS_HEIGHT_1);
-    do_test_iter_mut_mutation::<u64>(MIN_INSERTS_HEIGHT_2);
-    do_test_iter_mut_mutation::<u128>(1);
-    do_test_iter_mut_mutation::<u128>(MIN_INSERTS_HEIGHT_1);
-    do_test_iter_mut_mutation::<u128>(MIN_INSERTS_HEIGHT_2);
-    do_test_iter_mut_mutation::<Align32>(1);
-    do_test_iter_mut_mutation::<Align32>(MIN_INSERTS_HEIGHT_1);
-    do_test_iter_mut_mutation::<Align32>(MIN_INSERTS_HEIGHT_2);
-}
-
-#[test]
-#[cfg_attr(miri, ignore)] // FIXME: fails in Miri <https://github.com/rust-lang/rust/issues/73915>
-fn test_values_mut() {
-    let mut a: BTreeMap<_, _> = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)).collect();
-    test_all_refs(&mut 13, a.values_mut());
-}
-
-#[test]
-fn test_values_mut_mutation() {
-    let mut a = BTreeMap::new();
-    a.insert(1, String::from("hello"));
-    a.insert(2, String::from("goodbye"));
-
-    for value in a.values_mut() {
-        value.push_str("!");
-    }
-
-    let values: Vec<String> = a.values().cloned().collect();
-    assert_eq!(values, [String::from("hello!"), String::from("goodbye!")]);
-}
-
-#[test]
-#[cfg_attr(miri, ignore)] // FIXME: fails in Miri <https://github.com/rust-lang/rust/issues/73915>
-fn test_iter_entering_root_twice() {
-    let mut map: BTreeMap<_, _> = (0..2).map(|i| (i, i)).collect();
-    let mut it = map.iter_mut();
-    let front = it.next().unwrap();
-    let back = it.next_back().unwrap();
-    assert_eq!(front, (&0, &mut 0));
-    assert_eq!(back, (&1, &mut 1));
-    *front.1 = 24;
-    *back.1 = 42;
-    assert_eq!(front, (&0, &mut 24));
-    assert_eq!(back, (&1, &mut 42));
-}
-
-#[test]
-#[cfg_attr(miri, ignore)] // FIXME: fails in Miri <https://github.com/rust-lang/rust/issues/73915>
-fn test_iter_descending_to_same_node_twice() {
-    let mut map: BTreeMap<_, _> = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i)).collect();
-    let mut it = map.iter_mut();
-    // Descend into first child.
-    let front = it.next().unwrap();
-    // Descend into first child again, after running through second child.
-    while it.next_back().is_some() {}
-    // Check immutable access.
-    assert_eq!(front, (&0, &mut 0));
-    // Perform mutable access.
-    *front.1 = 42;
-}
-
-#[test]
-fn test_iter_mixed() {
-    // Miri is too slow
-    let size = if cfg!(miri) { 200 } else { 10000 };
-
-    let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
-
-    fn test<T>(size: usize, mut iter: T)
-    where
-        T: Iterator<Item = (usize, usize)> + DoubleEndedIterator,
-    {
-        for i in 0..size / 4 {
-            assert_eq!(iter.size_hint(), (size - i * 2, Some(size - i * 2)));
-            assert_eq!(iter.next().unwrap(), (i, i));
-            assert_eq!(iter.next_back().unwrap(), (size - i - 1, size - i - 1));
-        }
-        for i in size / 4..size * 3 / 4 {
-            assert_eq!(iter.size_hint(), (size * 3 / 4 - i, Some(size * 3 / 4 - i)));
-            assert_eq!(iter.next().unwrap(), (i, i));
-        }
-        assert_eq!(iter.size_hint(), (0, Some(0)));
-        assert_eq!(iter.next(), None);
-    }
-    test(size, map.iter().map(|(&k, &v)| (k, v)));
-    test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
-    test(size, map.into_iter());
-}
-
-#[test]
-#[cfg_attr(miri, ignore)] // FIXME: fails in Miri <https://github.com/rust-lang/rust/issues/73915>
-fn test_iter_min_max() {
-    let mut a = BTreeMap::new();
-    assert_eq!(a.iter().min(), None);
-    assert_eq!(a.iter().max(), None);
-    assert_eq!(a.iter_mut().min(), None);
-    assert_eq!(a.iter_mut().max(), None);
-    assert_eq!(a.range(..).min(), None);
-    assert_eq!(a.range(..).max(), None);
-    assert_eq!(a.range_mut(..).min(), None);
-    assert_eq!(a.range_mut(..).max(), None);
-    assert_eq!(a.keys().min(), None);
-    assert_eq!(a.keys().max(), None);
-    assert_eq!(a.values().min(), None);
-    assert_eq!(a.values().max(), None);
-    assert_eq!(a.values_mut().min(), None);
-    assert_eq!(a.values_mut().max(), None);
-    a.insert(1, 42);
-    a.insert(2, 24);
-    assert_eq!(a.iter().min(), Some((&1, &42)));
-    assert_eq!(a.iter().max(), Some((&2, &24)));
-    assert_eq!(a.iter_mut().min(), Some((&1, &mut 42)));
-    assert_eq!(a.iter_mut().max(), Some((&2, &mut 24)));
-    assert_eq!(a.range(..).min(), Some((&1, &42)));
-    assert_eq!(a.range(..).max(), Some((&2, &24)));
-    assert_eq!(a.range_mut(..).min(), Some((&1, &mut 42)));
-    assert_eq!(a.range_mut(..).max(), Some((&2, &mut 24)));
-    assert_eq!(a.keys().min(), Some(&1));
-    assert_eq!(a.keys().max(), Some(&2));
-    assert_eq!(a.values().min(), Some(&24));
-    assert_eq!(a.values().max(), Some(&42));
-    assert_eq!(a.values_mut().min(), Some(&mut 24));
-    assert_eq!(a.values_mut().max(), Some(&mut 42));
-}
-
-fn range_keys(map: &BTreeMap<i32, i32>, range: impl RangeBounds<i32>) -> Vec<i32> {
-    map.range(range)
-        .map(|(&k, &v)| {
-            assert_eq!(k, v);
-            k
-        })
-        .collect()
-}
-
-#[test]
-fn test_range_small() {
-    let size = 4;
-
-    let map: BTreeMap<_, _> = (1..=size).map(|i| (i, i)).collect();
-    let all: Vec<_> = (1..=size).collect();
-    let (first, last) = (vec![all[0]], vec![all[size as usize - 1]]);
-
-    assert_eq!(range_keys(&map, (Excluded(0), Excluded(size + 1))), all);
-    assert_eq!(range_keys(&map, (Excluded(0), Included(size + 1))), all);
-    assert_eq!(range_keys(&map, (Excluded(0), Included(size))), all);
-    assert_eq!(range_keys(&map, (Excluded(0), Unbounded)), all);
-    assert_eq!(range_keys(&map, (Included(0), Excluded(size + 1))), all);
-    assert_eq!(range_keys(&map, (Included(0), Included(size + 1))), all);
-    assert_eq!(range_keys(&map, (Included(0), Included(size))), all);
-    assert_eq!(range_keys(&map, (Included(0), Unbounded)), all);
-    assert_eq!(range_keys(&map, (Included(1), Excluded(size + 1))), all);
-    assert_eq!(range_keys(&map, (Included(1), Included(size + 1))), all);
-    assert_eq!(range_keys(&map, (Included(1), Included(size))), all);
-    assert_eq!(range_keys(&map, (Included(1), Unbounded)), all);
-    assert_eq!(range_keys(&map, (Unbounded, Excluded(size + 1))), all);
-    assert_eq!(range_keys(&map, (Unbounded, Included(size + 1))), all);
-    assert_eq!(range_keys(&map, (Unbounded, Included(size))), all);
-    assert_eq!(range_keys(&map, ..), all);
-
-    assert_eq!(range_keys(&map, (Excluded(0), Excluded(1))), vec![]);
-    assert_eq!(range_keys(&map, (Excluded(0), Included(0))), vec![]);
-    assert_eq!(range_keys(&map, (Included(0), Included(0))), vec![]);
-    assert_eq!(range_keys(&map, (Included(0), Excluded(1))), vec![]);
-    assert_eq!(range_keys(&map, (Unbounded, Excluded(1))), vec![]);
-    assert_eq!(range_keys(&map, (Unbounded, Included(0))), vec![]);
-    assert_eq!(range_keys(&map, (Excluded(0), Excluded(2))), first);
-    assert_eq!(range_keys(&map, (Excluded(0), Included(1))), first);
-    assert_eq!(range_keys(&map, (Included(0), Excluded(2))), first);
-    assert_eq!(range_keys(&map, (Included(0), Included(1))), first);
-    assert_eq!(range_keys(&map, (Included(1), Excluded(2))), first);
-    assert_eq!(range_keys(&map, (Included(1), Included(1))), first);
-    assert_eq!(range_keys(&map, (Unbounded, Excluded(2))), first);
-    assert_eq!(range_keys(&map, (Unbounded, Included(1))), first);
-    assert_eq!(range_keys(&map, (Excluded(size - 1), Excluded(size + 1))), last);
-    assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size + 1))), last);
-    assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size))), last);
-    assert_eq!(range_keys(&map, (Excluded(size - 1), Unbounded)), last);
-    assert_eq!(range_keys(&map, (Included(size), Excluded(size + 1))), last);
-    assert_eq!(range_keys(&map, (Included(size), Included(size + 1))), last);
-    assert_eq!(range_keys(&map, (Included(size), Included(size))), last);
-    assert_eq!(range_keys(&map, (Included(size), Unbounded)), last);
-    assert_eq!(range_keys(&map, (Excluded(size), Excluded(size + 1))), vec![]);
-    assert_eq!(range_keys(&map, (Excluded(size), Included(size))), vec![]);
-    assert_eq!(range_keys(&map, (Excluded(size), Unbounded)), vec![]);
-    assert_eq!(range_keys(&map, (Included(size + 1), Excluded(size + 1))), vec![]);
-    assert_eq!(range_keys(&map, (Included(size + 1), Included(size + 1))), vec![]);
-    assert_eq!(range_keys(&map, (Included(size + 1), Unbounded)), vec![]);
-
-    assert_eq!(range_keys(&map, ..3), vec![1, 2]);
-    assert_eq!(range_keys(&map, 3..), vec![3, 4]);
-    assert_eq!(range_keys(&map, 2..=3), vec![2, 3]);
-}
-
-#[test]
-fn test_range_height_1() {
-    // Tests tree with a root and 2 leaves. Depending on details we don't want or need
-    // to rely upon, the single key at the root will be 6 or 7.
-
-    let map: BTreeMap<_, _> = (1..=MIN_INSERTS_HEIGHT_1 as i32).map(|i| (i, i)).collect();
-    for &root in &[6, 7] {
-        assert_eq!(range_keys(&map, (Excluded(root), Excluded(root + 1))), vec![]);
-        assert_eq!(range_keys(&map, (Excluded(root), Included(root + 1))), vec![root + 1]);
-        assert_eq!(range_keys(&map, (Included(root), Excluded(root + 1))), vec![root]);
-        assert_eq!(range_keys(&map, (Included(root), Included(root + 1))), vec![root, root + 1]);
-
-        assert_eq!(range_keys(&map, (Excluded(root - 1), Excluded(root))), vec![]);
-        assert_eq!(range_keys(&map, (Included(root - 1), Excluded(root))), vec![root - 1]);
-        assert_eq!(range_keys(&map, (Excluded(root - 1), Included(root))), vec![root]);
-        assert_eq!(range_keys(&map, (Included(root - 1), Included(root))), vec![root - 1, root]);
-    }
-}
-
-#[test]
-fn test_range_large() {
-    let size = 200;
-
-    let map: BTreeMap<_, _> = (1..=size).map(|i| (i, i)).collect();
-    let all: Vec<_> = (1..=size).collect();
-    let (first, last) = (vec![all[0]], vec![all[size as usize - 1]]);
-
-    assert_eq!(range_keys(&map, (Excluded(0), Excluded(size + 1))), all);
-    assert_eq!(range_keys(&map, (Excluded(0), Included(size + 1))), all);
-    assert_eq!(range_keys(&map, (Excluded(0), Included(size))), all);
-    assert_eq!(range_keys(&map, (Excluded(0), Unbounded)), all);
-    assert_eq!(range_keys(&map, (Included(0), Excluded(size + 1))), all);
-    assert_eq!(range_keys(&map, (Included(0), Included(size + 1))), all);
-    assert_eq!(range_keys(&map, (Included(0), Included(size))), all);
-    assert_eq!(range_keys(&map, (Included(0), Unbounded)), all);
-    assert_eq!(range_keys(&map, (Included(1), Excluded(size + 1))), all);
-    assert_eq!(range_keys(&map, (Included(1), Included(size + 1))), all);
-    assert_eq!(range_keys(&map, (Included(1), Included(size))), all);
-    assert_eq!(range_keys(&map, (Included(1), Unbounded)), all);
-    assert_eq!(range_keys(&map, (Unbounded, Excluded(size + 1))), all);
-    assert_eq!(range_keys(&map, (Unbounded, Included(size + 1))), all);
-    assert_eq!(range_keys(&map, (Unbounded, Included(size))), all);
-    assert_eq!(range_keys(&map, ..), all);
-
-    assert_eq!(range_keys(&map, (Excluded(0), Excluded(1))), vec![]);
-    assert_eq!(range_keys(&map, (Excluded(0), Included(0))), vec![]);
-    assert_eq!(range_keys(&map, (Included(0), Included(0))), vec![]);
-    assert_eq!(range_keys(&map, (Included(0), Excluded(1))), vec![]);
-    assert_eq!(range_keys(&map, (Unbounded, Excluded(1))), vec![]);
-    assert_eq!(range_keys(&map, (Unbounded, Included(0))), vec![]);
-    assert_eq!(range_keys(&map, (Excluded(0), Excluded(2))), first);
-    assert_eq!(range_keys(&map, (Excluded(0), Included(1))), first);
-    assert_eq!(range_keys(&map, (Included(0), Excluded(2))), first);
-    assert_eq!(range_keys(&map, (Included(0), Included(1))), first);
-    assert_eq!(range_keys(&map, (Included(1), Excluded(2))), first);
-    assert_eq!(range_keys(&map, (Included(1), Included(1))), first);
-    assert_eq!(range_keys(&map, (Unbounded, Excluded(2))), first);
-    assert_eq!(range_keys(&map, (Unbounded, Included(1))), first);
-    assert_eq!(range_keys(&map, (Excluded(size - 1), Excluded(size + 1))), last);
-    assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size + 1))), last);
-    assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size))), last);
-    assert_eq!(range_keys(&map, (Excluded(size - 1), Unbounded)), last);
-    assert_eq!(range_keys(&map, (Included(size), Excluded(size + 1))), last);
-    assert_eq!(range_keys(&map, (Included(size), Included(size + 1))), last);
-    assert_eq!(range_keys(&map, (Included(size), Included(size))), last);
-    assert_eq!(range_keys(&map, (Included(size), Unbounded)), last);
-    assert_eq!(range_keys(&map, (Excluded(size), Excluded(size + 1))), vec![]);
-    assert_eq!(range_keys(&map, (Excluded(size), Included(size))), vec![]);
-    assert_eq!(range_keys(&map, (Excluded(size), Unbounded)), vec![]);
-    assert_eq!(range_keys(&map, (Included(size + 1), Excluded(size + 1))), vec![]);
-    assert_eq!(range_keys(&map, (Included(size + 1), Included(size + 1))), vec![]);
-    assert_eq!(range_keys(&map, (Included(size + 1), Unbounded)), vec![]);
-
-    fn check<'a, L, R>(lhs: L, rhs: R)
-    where
-        L: IntoIterator<Item = (&'a i32, &'a i32)>,
-        R: IntoIterator<Item = (&'a i32, &'a i32)>,
-    {
-        let lhs: Vec<_> = lhs.into_iter().collect();
-        let rhs: Vec<_> = rhs.into_iter().collect();
-        assert_eq!(lhs, rhs);
-    }
-
-    check(map.range(..=100), map.range(..101));
-    check(map.range(5..=8), vec![(&5, &5), (&6, &6), (&7, &7), (&8, &8)]);
-    check(map.range(-1..=2), vec![(&1, &1), (&2, &2)]);
-}
-
-#[test]
-fn test_range_inclusive_max_value() {
-    let max = usize::MAX;
-    let map: BTreeMap<_, _> = vec![(max, 0)].into_iter().collect();
-
-    assert_eq!(map.range(max..=max).collect::<Vec<_>>(), &[(&max, &0)]);
-}
-
-#[test]
-fn test_range_equal_empty_cases() {
-    let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
-    assert_eq!(map.range((Included(2), Excluded(2))).next(), None);
-    assert_eq!(map.range((Excluded(2), Included(2))).next(), None);
-}
-
-#[test]
-#[should_panic]
-fn test_range_equal_excluded() {
-    let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
-    map.range((Excluded(2), Excluded(2)));
-}
-
-#[test]
-#[should_panic]
-fn test_range_backwards_1() {
-    let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
-    map.range((Included(3), Included(2)));
-}
-
-#[test]
-#[should_panic]
-fn test_range_backwards_2() {
-    let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
-    map.range((Included(3), Excluded(2)));
-}
-
-#[test]
-#[should_panic]
-fn test_range_backwards_3() {
-    let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
-    map.range((Excluded(3), Included(2)));
-}
-
-#[test]
-#[should_panic]
-fn test_range_backwards_4() {
-    let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
-    map.range((Excluded(3), Excluded(2)));
-}
-
-#[test]
-fn test_range_1000() {
-    // Miri is too slow
-    let size = if cfg!(miri) { MIN_INSERTS_HEIGHT_2 as u32 } else { 1000 };
-    let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
-
-    fn test(map: &BTreeMap<u32, u32>, size: u32, min: Bound<&u32>, max: Bound<&u32>) {
-        let mut kvs = map.range((min, max)).map(|(&k, &v)| (k, v));
-        let mut pairs = (0..size).map(|i| (i, i));
-
-        for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
-            assert_eq!(kv, pair);
-        }
-        assert_eq!(kvs.next(), None);
-        assert_eq!(pairs.next(), None);
-    }
-    test(&map, size, Included(&0), Excluded(&size));
-    test(&map, size, Unbounded, Excluded(&size));
-    test(&map, size, Included(&0), Included(&(size - 1)));
-    test(&map, size, Unbounded, Included(&(size - 1)));
-    test(&map, size, Included(&0), Unbounded);
-    test(&map, size, Unbounded, Unbounded);
-}
-
-#[test]
-fn test_range_borrowed_key() {
-    let mut map = BTreeMap::new();
-    map.insert("aardvark".to_string(), 1);
-    map.insert("baboon".to_string(), 2);
-    map.insert("coyote".to_string(), 3);
-    map.insert("dingo".to_string(), 4);
-    // NOTE: would like to use simply "b".."d" here...
-    let mut iter = map.range::<str, _>((Included("b"), Excluded("d")));
-    assert_eq!(iter.next(), Some((&"baboon".to_string(), &2)));
-    assert_eq!(iter.next(), Some((&"coyote".to_string(), &3)));
-    assert_eq!(iter.next(), None);
-}
-
-#[test]
-fn test_range() {
-    let size = 200;
-    // Miri is too slow
-    let step = if cfg!(miri) { 66 } else { 1 };
-    let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
-
-    for i in (0..size).step_by(step) {
-        for j in (i..size).step_by(step) {
-            let mut kvs = map.range((Included(&i), Included(&j))).map(|(&k, &v)| (k, v));
-            let mut pairs = (i..=j).map(|i| (i, i));
-
-            for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
-                assert_eq!(kv, pair);
-            }
-            assert_eq!(kvs.next(), None);
-            assert_eq!(pairs.next(), None);
-        }
-    }
-}
-
-#[test]
-fn test_range_mut() {
-    let size = 200;
-    // Miri is too slow
-    let step = if cfg!(miri) { 66 } else { 1 };
-    let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
-
-    for i in (0..size).step_by(step) {
-        for j in (i..size).step_by(step) {
-            let mut kvs = map.range_mut((Included(&i), Included(&j))).map(|(&k, &mut v)| (k, v));
-            let mut pairs = (i..=j).map(|i| (i, i));
-
-            for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
-                assert_eq!(kv, pair);
-            }
-            assert_eq!(kvs.next(), None);
-            assert_eq!(pairs.next(), None);
-        }
-    }
-}
-
-mod test_drain_filter {
-    use super::*;
-
-    #[test]
-    fn empty() {
-        let mut map: BTreeMap<i32, i32> = BTreeMap::new();
-        map.drain_filter(|_, _| unreachable!("there's nothing to decide on"));
-        assert!(map.is_empty());
-    }
-
-    #[test]
-    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()));
-    }
-
-    #[test]
-    fn consuming_all() {
-        let pairs = (0..3).map(|i| (i, i));
-        let mut map: BTreeMap<_, _> = pairs.clone().collect();
-        assert!(map.drain_filter(|_, _| true).eq(pairs));
-    }
-
-    #[test]
-    fn mutating_and_keeping() {
-        let pairs = (0..3).map(|i| (i, i));
-        let mut map: BTreeMap<_, _> = pairs.collect();
-        assert!(
-            map.drain_filter(|_, v| {
-                *v += 6;
-                false
-            })
-            .eq(std::iter::empty())
-        );
-        assert!(map.keys().copied().eq(0..3));
-        assert!(map.values().copied().eq(6..9));
-    }
-
-    #[test]
-    fn mutating_and_removing() {
-        let pairs = (0..3).map(|i| (i, i));
-        let mut map: BTreeMap<_, _> = pairs.collect();
-        assert!(
-            map.drain_filter(|_, v| {
-                *v += 6;
-                true
-            })
-            .eq((0..3).map(|i| (i, i + 6)))
-        );
-        assert!(map.is_empty());
-    }
-
-    #[test]
-    fn underfull_keeping_all() {
-        let pairs = (0..3).map(|i| (i, i));
-        let mut map: BTreeMap<_, _> = pairs.collect();
-        map.drain_filter(|_, _| false);
-        assert!(map.keys().copied().eq(0..3));
-    }
-
-    #[test]
-    fn underfull_removing_one() {
-        let pairs = (0..3).map(|i| (i, i));
-        for doomed in 0..3 {
-            let mut map: BTreeMap<_, _> = pairs.clone().collect();
-            map.drain_filter(|i, _| *i == doomed);
-            assert_eq!(map.len(), 2);
-        }
-    }
-
-    #[test]
-    fn underfull_keeping_one() {
-        let pairs = (0..3).map(|i| (i, i));
-        for sacred in 0..3 {
-            let mut map: BTreeMap<_, _> = pairs.clone().collect();
-            map.drain_filter(|i, _| *i != sacred);
-            assert!(map.keys().copied().eq(sacred..=sacred));
-        }
-    }
-
-    #[test]
-    fn underfull_removing_all() {
-        let pairs = (0..3).map(|i| (i, i));
-        let mut map: BTreeMap<_, _> = pairs.collect();
-        map.drain_filter(|_, _| true);
-        assert!(map.is_empty());
-    }
-
-    #[test]
-    fn height_0_keeping_all() {
-        let pairs = (0..NODE_CAPACITY).map(|i| (i, i));
-        let mut map: BTreeMap<_, _> = pairs.collect();
-        map.drain_filter(|_, _| false);
-        assert!(map.keys().copied().eq(0..NODE_CAPACITY));
-    }
-
-    #[test]
-    fn height_0_removing_one() {
-        let pairs = (0..NODE_CAPACITY).map(|i| (i, i));
-        for doomed in 0..NODE_CAPACITY {
-            let mut map: BTreeMap<_, _> = pairs.clone().collect();
-            map.drain_filter(|i, _| *i == doomed);
-            assert_eq!(map.len(), NODE_CAPACITY - 1);
-        }
-    }
-
-    #[test]
-    fn height_0_keeping_one() {
-        let pairs = (0..NODE_CAPACITY).map(|i| (i, i));
-        for sacred in 0..NODE_CAPACITY {
-            let mut map: BTreeMap<_, _> = pairs.clone().collect();
-            map.drain_filter(|i, _| *i != sacred);
-            assert!(map.keys().copied().eq(sacred..=sacred));
-        }
-    }
-
-    #[test]
-    fn height_0_removing_all() {
-        let pairs = (0..NODE_CAPACITY).map(|i| (i, i));
-        let mut map: BTreeMap<_, _> = pairs.collect();
-        map.drain_filter(|_, _| true);
-        assert!(map.is_empty());
-    }
-
-    #[test]
-    fn height_0_keeping_half() {
-        let mut map: BTreeMap<_, _> = (0..16).map(|i| (i, i)).collect();
-        assert_eq!(map.drain_filter(|i, _| *i % 2 == 0).count(), 8);
-        assert_eq!(map.len(), 8);
-    }
-
-    #[test]
-    fn height_1_removing_all() {
-        let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i));
-        let mut map: BTreeMap<_, _> = pairs.collect();
-        map.drain_filter(|_, _| true);
-        assert!(map.is_empty());
-    }
-
-    #[test]
-    fn height_1_removing_one() {
-        let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i));
-        for doomed in 0..MIN_INSERTS_HEIGHT_1 {
-            let mut map: BTreeMap<_, _> = pairs.clone().collect();
-            map.drain_filter(|i, _| *i == doomed);
-            assert_eq!(map.len(), MIN_INSERTS_HEIGHT_1 - 1);
-        }
-    }
-
-    #[test]
-    fn height_1_keeping_one() {
-        let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i));
-        for sacred in 0..MIN_INSERTS_HEIGHT_1 {
-            let mut map: BTreeMap<_, _> = pairs.clone().collect();
-            map.drain_filter(|i, _| *i != sacred);
-            assert!(map.keys().copied().eq(sacred..=sacred));
-        }
-    }
-
-    #[cfg(not(miri))] // Miri is too slow
-    #[test]
-    fn height_2_removing_one() {
-        let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
-        for doomed in (0..MIN_INSERTS_HEIGHT_2).step_by(12) {
-            let mut map: BTreeMap<_, _> = pairs.clone().collect();
-            map.drain_filter(|i, _| *i == doomed);
-            assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2 - 1);
-        }
-    }
-
-    #[cfg(not(miri))] // Miri is too slow
-    #[test]
-    fn height_2_keeping_one() {
-        let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
-        for sacred in (0..MIN_INSERTS_HEIGHT_2).step_by(12) {
-            let mut map: BTreeMap<_, _> = pairs.clone().collect();
-            map.drain_filter(|i, _| *i != sacred);
-            assert!(map.keys().copied().eq(sacred..=sacred));
-        }
-    }
-
-    #[test]
-    fn height_2_removing_all() {
-        let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
-        let mut map: BTreeMap<_, _> = pairs.collect();
-        map.drain_filter(|_, _| true);
-        assert!(map.is_empty());
-    }
-
-    #[test]
-    fn drop_panic_leak() {
-        static PREDS: AtomicUsize = AtomicUsize::new(0);
-        static DROPS: AtomicUsize = AtomicUsize::new(0);
-
-        struct D;
-        impl Drop for D {
-            fn drop(&mut self) {
-                if DROPS.fetch_add(1, Ordering::SeqCst) == 1 {
-                    panic!("panic in `drop`");
-                }
-            }
-        }
-
-        // Keys are multiples of 4, so that each key is counted by a hexadecimal digit.
-        let mut map = (0..3).map(|i| (i * 4, D)).collect::<BTreeMap<_, _>>();
-
-        catch_unwind(move || {
-            drop(map.drain_filter(|i, _| {
-                PREDS.fetch_add(1usize << i, Ordering::SeqCst);
-                true
-            }))
-        })
-        .unwrap_err();
-
-        assert_eq!(PREDS.load(Ordering::SeqCst), 0x011);
-        assert_eq!(DROPS.load(Ordering::SeqCst), 3);
-    }
-
-    #[test]
-    fn pred_panic_leak() {
-        static PREDS: AtomicUsize = AtomicUsize::new(0);
-        static DROPS: AtomicUsize = AtomicUsize::new(0);
-
-        struct D;
-        impl Drop for D {
-            fn drop(&mut self) {
-                DROPS.fetch_add(1, Ordering::SeqCst);
-            }
-        }
-
-        // Keys are multiples of 4, so that each key is counted by a hexadecimal digit.
-        let mut map = (0..3).map(|i| (i * 4, D)).collect::<BTreeMap<_, _>>();
-
-        catch_unwind(AssertUnwindSafe(|| {
-            drop(map.drain_filter(|i, _| {
-                PREDS.fetch_add(1usize << i, Ordering::SeqCst);
-                match i {
-                    0 => true,
-                    _ => panic!(),
-                }
-            }))
-        }))
-        .unwrap_err();
-
-        assert_eq!(PREDS.load(Ordering::SeqCst), 0x011);
-        assert_eq!(DROPS.load(Ordering::SeqCst), 1);
-        assert_eq!(map.len(), 2);
-        assert_eq!(map.first_entry().unwrap().key(), &4);
-        assert_eq!(map.last_entry().unwrap().key(), &8);
-    }
-
-    // Same as above, but attempt to use the iterator again after the panic in the predicate
-    #[test]
-    fn pred_panic_reuse() {
-        static PREDS: AtomicUsize = AtomicUsize::new(0);
-        static DROPS: AtomicUsize = AtomicUsize::new(0);
-
-        struct D;
-        impl Drop for D {
-            fn drop(&mut self) {
-                DROPS.fetch_add(1, Ordering::SeqCst);
-            }
-        }
-
-        // Keys are multiples of 4, so that each key is counted by a hexadecimal digit.
-        let mut map = (0..3).map(|i| (i * 4, D)).collect::<BTreeMap<_, _>>();
-
-        {
-            let mut it = map.drain_filter(|i, _| {
-                PREDS.fetch_add(1usize << i, Ordering::SeqCst);
-                match i {
-                    0 => true,
-                    _ => panic!(),
-                }
-            });
-            catch_unwind(AssertUnwindSafe(|| while it.next().is_some() {})).unwrap_err();
-            // Iterator behaviour after a panic is explicitly unspecified,
-            // so this is just the current implementation:
-            let result = catch_unwind(AssertUnwindSafe(|| it.next()));
-            assert!(matches!(result, Ok(None)));
-        }
-
-        assert_eq!(PREDS.load(Ordering::SeqCst), 0x011);
-        assert_eq!(DROPS.load(Ordering::SeqCst), 1);
-        assert_eq!(map.len(), 2);
-        assert_eq!(map.first_entry().unwrap().key(), &4);
-        assert_eq!(map.last_entry().unwrap().key(), &8);
-    }
-}
-
-#[test]
-fn test_borrow() {
-    // make sure these compile -- using the Borrow trait
-    {
-        let mut map = BTreeMap::new();
-        map.insert("0".to_string(), 1);
-        assert_eq!(map["0"], 1);
-    }
-
-    {
-        let mut map = BTreeMap::new();
-        map.insert(Box::new(0), 1);
-        assert_eq!(map[&0], 1);
-    }
-
-    {
-        let mut map = BTreeMap::new();
-        map.insert(Box::new([0, 1]) as Box<[i32]>, 1);
-        assert_eq!(map[&[0, 1][..]], 1);
-    }
-
-    {
-        let mut map = BTreeMap::new();
-        map.insert(Rc::new(0), 1);
-        assert_eq!(map[&0], 1);
-    }
-}
-
-#[test]
-fn test_entry() {
-    let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
-
-    let mut map: BTreeMap<_, _> = xs.iter().cloned().collect();
-
-    // Existing key (insert)
-    match map.entry(1) {
-        Vacant(_) => unreachable!(),
-        Occupied(mut view) => {
-            assert_eq!(view.get(), &10);
-            assert_eq!(view.insert(100), 10);
-        }
-    }
-    assert_eq!(map.get(&1).unwrap(), &100);
-    assert_eq!(map.len(), 6);
-
-    // Existing key (update)
-    match map.entry(2) {
-        Vacant(_) => unreachable!(),
-        Occupied(mut view) => {
-            let v = view.get_mut();
-            *v *= 10;
-        }
-    }
-    assert_eq!(map.get(&2).unwrap(), &200);
-    assert_eq!(map.len(), 6);
-
-    // Existing key (take)
-    match map.entry(3) {
-        Vacant(_) => unreachable!(),
-        Occupied(view) => {
-            assert_eq!(view.remove(), 30);
-        }
-    }
-    assert_eq!(map.get(&3), None);
-    assert_eq!(map.len(), 5);
-
-    // Inexistent key (insert)
-    match map.entry(10) {
-        Occupied(_) => unreachable!(),
-        Vacant(view) => {
-            assert_eq!(*view.insert(1000), 1000);
-        }
-    }
-    assert_eq!(map.get(&10).unwrap(), &1000);
-    assert_eq!(map.len(), 6);
-}
-
-#[test]
-fn test_extend_ref() {
-    let mut a = BTreeMap::new();
-    a.insert(1, "one");
-    let mut b = BTreeMap::new();
-    b.insert(2, "two");
-    b.insert(3, "three");
-
-    a.extend(&b);
-
-    assert_eq!(a.len(), 3);
-    assert_eq!(a[&1], "one");
-    assert_eq!(a[&2], "two");
-    assert_eq!(a[&3], "three");
-}
-
-#[test]
-fn test_zst() {
-    let mut m = BTreeMap::new();
-    assert_eq!(m.len(), 0);
-
-    assert_eq!(m.insert((), ()), None);
-    assert_eq!(m.len(), 1);
-
-    assert_eq!(m.insert((), ()), Some(()));
-    assert_eq!(m.len(), 1);
-    assert_eq!(m.iter().count(), 1);
-
-    m.clear();
-    assert_eq!(m.len(), 0);
-
-    for _ in 0..100 {
-        m.insert((), ());
-    }
-
-    assert_eq!(m.len(), 1);
-    assert_eq!(m.iter().count(), 1);
-}
-
-// This test's only purpose is to ensure that zero-sized keys with nonsensical orderings
-// do not cause segfaults when used with zero-sized values. All other map behavior is
-// undefined.
-#[test]
-fn test_bad_zst() {
-    use std::cmp::Ordering;
-
-    struct Bad;
-
-    impl PartialEq for Bad {
-        fn eq(&self, _: &Self) -> bool {
-            false
-        }
-    }
-
-    impl Eq for Bad {}
-
-    impl PartialOrd for Bad {
-        fn partial_cmp(&self, _: &Self) -> Option<Ordering> {
-            Some(Ordering::Less)
-        }
-    }
-
-    impl Ord for Bad {
-        fn cmp(&self, _: &Self) -> Ordering {
-            Ordering::Less
-        }
-    }
-
-    let mut m = BTreeMap::new();
-
-    for _ in 0..100 {
-        m.insert(Bad, Bad);
-    }
-}
-
-#[test]
-fn test_clone() {
-    let mut map = BTreeMap::new();
-    let size = MIN_INSERTS_HEIGHT_1;
-    assert_eq!(map.len(), 0);
-
-    for i in 0..size {
-        assert_eq!(map.insert(i, 10 * i), None);
-        assert_eq!(map.len(), i + 1);
-        assert_eq!(map, map.clone());
-    }
-
-    for i in 0..size {
-        assert_eq!(map.insert(i, 100 * i), Some(10 * i));
-        assert_eq!(map.len(), size);
-        assert_eq!(map, map.clone());
-    }
-
-    for i in 0..size / 2 {
-        assert_eq!(map.remove(&(i * 2)), Some(i * 200));
-        assert_eq!(map.len(), size - i - 1);
-        assert_eq!(map, map.clone());
-    }
-
-    for i in 0..size / 2 {
-        assert_eq!(map.remove(&(2 * i)), None);
-        assert_eq!(map.remove(&(2 * i + 1)), Some(i * 200 + 100));
-        assert_eq!(map.len(), size / 2 - i - 1);
-        assert_eq!(map, map.clone());
-    }
-
-    // Test a tree with 2 chock-full levels and a tree with 3 levels.
-    map = (1..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)).collect();
-    assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2 - 1);
-    assert_eq!(map, map.clone());
-    map.insert(0, 0);
-    assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2);
-    assert_eq!(map, map.clone());
-}
-
-#[test]
-fn test_clone_from() {
-    let mut map1 = BTreeMap::new();
-    let max_size = MIN_INSERTS_HEIGHT_1;
-
-    // Range to max_size inclusive, because i is the size of map1 being tested.
-    for i in 0..=max_size {
-        let mut map2 = BTreeMap::new();
-        for j in 0..i {
-            let mut map1_copy = map2.clone();
-            map1_copy.clone_from(&map1); // small cloned from large
-            assert_eq!(map1_copy, map1);
-            let mut map2_copy = map1.clone();
-            map2_copy.clone_from(&map2); // large cloned from small
-            assert_eq!(map2_copy, map2);
-            map2.insert(100 * j + 1, 2 * j + 1);
-        }
-        map2.clone_from(&map1); // same length
-        assert_eq!(map2, map1);
-        map1.insert(i, 10 * i);
-    }
-}
-
-#[test]
-#[allow(dead_code)]
-fn test_variance() {
-    use std::collections::btree_map::{IntoIter, Iter, Keys, Range, Values};
-
-    fn map_key<'new>(v: BTreeMap<&'static str, ()>) -> BTreeMap<&'new str, ()> {
-        v
-    }
-    fn map_val<'new>(v: BTreeMap<(), &'static str>) -> BTreeMap<(), &'new str> {
-        v
-    }
-    fn iter_key<'a, 'new>(v: Iter<'a, &'static str, ()>) -> Iter<'a, &'new str, ()> {
-        v
-    }
-    fn iter_val<'a, 'new>(v: Iter<'a, (), &'static str>) -> Iter<'a, (), &'new str> {
-        v
-    }
-    fn into_iter_key<'new>(v: IntoIter<&'static str, ()>) -> IntoIter<&'new str, ()> {
-        v
-    }
-    fn into_iter_val<'new>(v: IntoIter<(), &'static str>) -> IntoIter<(), &'new str> {
-        v
-    }
-    fn range_key<'a, 'new>(v: Range<'a, &'static str, ()>) -> Range<'a, &'new str, ()> {
-        v
-    }
-    fn range_val<'a, 'new>(v: Range<'a, (), &'static str>) -> Range<'a, (), &'new str> {
-        v
-    }
-    fn keys<'a, 'new>(v: Keys<'a, &'static str, ()>) -> Keys<'a, &'new str, ()> {
-        v
-    }
-    fn vals<'a, 'new>(v: Values<'a, (), &'static str>) -> Values<'a, (), &'new str> {
-        v
-    }
-}
-
-#[test]
-fn test_occupied_entry_key() {
-    let mut a = BTreeMap::new();
-    let key = "hello there";
-    let value = "value goes here";
-    assert!(a.is_empty());
-    a.insert(key.clone(), value.clone());
-    assert_eq!(a.len(), 1);
-    assert_eq!(a[key], value);
-
-    match a.entry(key.clone()) {
-        Vacant(_) => panic!(),
-        Occupied(e) => assert_eq!(key, *e.key()),
-    }
-    assert_eq!(a.len(), 1);
-    assert_eq!(a[key], value);
-}
-
-#[test]
-fn test_vacant_entry_key() {
-    let mut a = BTreeMap::new();
-    let key = "hello there";
-    let value = "value goes here";
-
-    assert!(a.is_empty());
-    match a.entry(key.clone()) {
-        Occupied(_) => panic!(),
-        Vacant(e) => {
-            assert_eq!(key, *e.key());
-            e.insert(value.clone());
-        }
-    }
-    assert_eq!(a.len(), 1);
-    assert_eq!(a[key], value);
-}
-
-#[test]
-fn test_first_last_entry() {
-    let mut a = BTreeMap::new();
-    assert!(a.first_entry().is_none());
-    assert!(a.last_entry().is_none());
-    a.insert(1, 42);
-    assert_eq!(a.first_entry().unwrap().key(), &1);
-    assert_eq!(a.last_entry().unwrap().key(), &1);
-    a.insert(2, 24);
-    assert_eq!(a.first_entry().unwrap().key(), &1);
-    assert_eq!(a.last_entry().unwrap().key(), &2);
-    a.insert(0, 6);
-    assert_eq!(a.first_entry().unwrap().key(), &0);
-    assert_eq!(a.last_entry().unwrap().key(), &2);
-    let (k1, v1) = a.first_entry().unwrap().remove_entry();
-    assert_eq!(k1, 0);
-    assert_eq!(v1, 6);
-    let (k2, v2) = a.last_entry().unwrap().remove_entry();
-    assert_eq!(k2, 2);
-    assert_eq!(v2, 24);
-    assert_eq!(a.first_entry().unwrap().key(), &1);
-    assert_eq!(a.last_entry().unwrap().key(), &1);
-}
-
-macro_rules! create_append_test {
-    ($name:ident, $len:expr) => {
-        #[test]
-        fn $name() {
-            let mut a = BTreeMap::new();
-            for i in 0..8 {
-                a.insert(i, i);
-            }
-
-            let mut b = BTreeMap::new();
-            for i in 5..$len {
-                b.insert(i, 2 * i);
-            }
-
-            a.append(&mut b);
-
-            assert_eq!(a.len(), $len);
-            assert_eq!(b.len(), 0);
-
-            for i in 0..$len {
-                if i < 5 {
-                    assert_eq!(a[&i], i);
-                } else {
-                    assert_eq!(a[&i], 2 * i);
-                }
-            }
-
-            assert_eq!(a.remove(&($len - 1)), Some(2 * ($len - 1)));
-            assert_eq!(a.insert($len - 1, 20), None);
-        }
-    };
-}
-
-// These are mostly for testing the algorithm that "fixes" the right edge after insertion.
-// Single node.
-create_append_test!(test_append_9, 9);
-// Two leafs that don't need fixing.
-create_append_test!(test_append_17, 17);
-// Two leafs where the second one ends up underfull and needs stealing at the end.
-create_append_test!(test_append_14, 14);
-// Two leafs where the second one ends up empty because the insertion finished at the root.
-create_append_test!(test_append_12, 12);
-// Three levels; insertion finished at the root.
-create_append_test!(test_append_144, 144);
-// Three levels; insertion finished at leaf while there is an empty node on the second level.
-create_append_test!(test_append_145, 145);
-// Tests for several randomly chosen sizes.
-create_append_test!(test_append_170, 170);
-create_append_test!(test_append_181, 181);
-#[cfg(not(miri))] // Miri is too slow
-create_append_test!(test_append_239, 239);
-#[cfg(not(miri))] // Miri is too slow
-create_append_test!(test_append_1700, 1700);
-
-fn rand_data(len: usize) -> Vec<(u32, u32)> {
-    let mut rng = DeterministicRng::new();
-    Vec::from_iter((0..len).map(|_| (rng.next(), rng.next())))
-}
-
-#[test]
-fn test_split_off_empty_right() {
-    let mut data = rand_data(173);
-
-    let mut map = BTreeMap::from_iter(data.clone());
-    let right = map.split_off(&(data.iter().max().unwrap().0 + 1));
-
-    data.sort();
-    assert!(map.into_iter().eq(data));
-    assert!(right.into_iter().eq(None));
-}
-
-#[test]
-fn test_split_off_empty_left() {
-    let mut data = rand_data(314);
-
-    let mut map = BTreeMap::from_iter(data.clone());
-    let right = map.split_off(&data.iter().min().unwrap().0);
-
-    data.sort();
-    assert!(map.into_iter().eq(None));
-    assert!(right.into_iter().eq(data));
-}
-
-// In a tree with 3 levels, if all but a part of the first leaf node is split off,
-// make sure fix_top eliminates both top levels.
-#[test]
-fn test_split_off_tiny_left_height_2() {
-    let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
-    let mut left: BTreeMap<_, _> = pairs.clone().collect();
-    let right = left.split_off(&1);
-    assert_eq!(left.len(), 1);
-    assert_eq!(right.len(), MIN_INSERTS_HEIGHT_2 - 1);
-    assert_eq!(*left.first_key_value().unwrap().0, 0);
-    assert_eq!(*right.first_key_value().unwrap().0, 1);
-}
-
-// In a tree with 3 levels, if only part of the last leaf node is split off,
-// make sure fix_top eliminates both top levels.
-#[test]
-fn test_split_off_tiny_right_height_2() {
-    let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
-    let last = MIN_INSERTS_HEIGHT_2 - 1;
-    let mut left: BTreeMap<_, _> = pairs.clone().collect();
-    assert_eq!(*left.last_key_value().unwrap().0, last);
-    let right = left.split_off(&last);
-    assert_eq!(left.len(), MIN_INSERTS_HEIGHT_2 - 1);
-    assert_eq!(right.len(), 1);
-    assert_eq!(*left.last_key_value().unwrap().0, last - 1);
-    assert_eq!(*right.last_key_value().unwrap().0, last);
-}
-
-#[test]
-fn test_split_off_large_random_sorted() {
-    // Miri is too slow
-    let mut data = if cfg!(miri) { rand_data(529) } else { rand_data(1529) };
-    // special case with maximum height.
-    data.sort();
-
-    let mut map = BTreeMap::from_iter(data.clone());
-    let key = data[data.len() / 2].0;
-    let right = map.split_off(&key);
-
-    assert!(map.into_iter().eq(data.clone().into_iter().filter(|x| x.0 < key)));
-    assert!(right.into_iter().eq(data.into_iter().filter(|x| x.0 >= key)));
-}
-
-#[test]
-fn test_into_iter_drop_leak_height_0() {
-    static DROPS: AtomicUsize = AtomicUsize::new(0);
-
-    struct D;
-
-    impl Drop for D {
-        fn drop(&mut self) {
-            if DROPS.fetch_add(1, Ordering::SeqCst) == 3 {
-                panic!("panic in `drop`");
-            }
-        }
-    }
-
-    let mut map = BTreeMap::new();
-    map.insert("a", D);
-    map.insert("b", D);
-    map.insert("c", D);
-    map.insert("d", D);
-    map.insert("e", D);
-
-    catch_unwind(move || drop(map.into_iter())).unwrap_err();
-
-    assert_eq!(DROPS.load(Ordering::SeqCst), 5);
-}
-
-#[test]
-fn test_into_iter_drop_leak_height_1() {
-    let size = MIN_INSERTS_HEIGHT_1;
-    static DROPS: AtomicUsize = AtomicUsize::new(0);
-    static PANIC_POINT: AtomicUsize = AtomicUsize::new(0);
-
-    struct D;
-    impl Drop for D {
-        fn drop(&mut self) {
-            if DROPS.fetch_add(1, Ordering::SeqCst) == PANIC_POINT.load(Ordering::SeqCst) {
-                panic!("panic in `drop`");
-            }
-        }
-    }
-
-    for panic_point in vec![0, 1, size - 2, size - 1] {
-        DROPS.store(0, Ordering::SeqCst);
-        PANIC_POINT.store(panic_point, Ordering::SeqCst);
-        let map: BTreeMap<_, _> = (0..size).map(|i| (i, D)).collect();
-        catch_unwind(move || drop(map.into_iter())).unwrap_err();
-        assert_eq!(DROPS.load(Ordering::SeqCst), size);
-    }
-}
-
-#[test]
-fn test_into_keys() {
-    let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
-    let map: BTreeMap<_, _> = vec.into_iter().collect();
-    let keys: Vec<_> = map.into_keys().collect();
-
-    assert_eq!(keys.len(), 3);
-    assert!(keys.contains(&1));
-    assert!(keys.contains(&2));
-    assert!(keys.contains(&3));
-}
-
-#[test]
-fn test_into_values() {
-    let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
-    let map: BTreeMap<_, _> = vec.into_iter().collect();
-    let values: Vec<_> = map.into_values().collect();
-
-    assert_eq!(values.len(), 3);
-    assert!(values.contains(&'a'));
-    assert!(values.contains(&'b'));
-    assert!(values.contains(&'c'));
-}
diff --git a/library/alloc/tests/btree/mod.rs b/library/alloc/tests/btree/mod.rs
deleted file mode 100644
index 1d08ae13e05..00000000000
--- a/library/alloc/tests/btree/mod.rs
+++ /dev/null
@@ -1,27 +0,0 @@
-mod map;
-mod set;
-
-/// XorShiftRng
-struct DeterministicRng {
-    x: u32,
-    y: u32,
-    z: u32,
-    w: u32,
-}
-
-impl DeterministicRng {
-    fn new() -> Self {
-        DeterministicRng { x: 0x193a6754, y: 0xa8a7d469, z: 0x97830e05, w: 0x113ba7bb }
-    }
-
-    fn next(&mut self) -> u32 {
-        let x = self.x;
-        let t = x ^ (x << 11);
-        self.x = self.y;
-        self.y = self.z;
-        self.z = self.w;
-        let w_ = self.w;
-        self.w = w_ ^ (w_ >> 19) ^ (t ^ (t >> 8));
-        self.w
-    }
-}
diff --git a/library/alloc/tests/btree/set.rs b/library/alloc/tests/btree/set.rs
deleted file mode 100644
index b6c34b7c6c3..00000000000
--- a/library/alloc/tests/btree/set.rs
+++ /dev/null
@@ -1,666 +0,0 @@
-use std::collections::BTreeSet;
-use std::iter::FromIterator;
-use std::panic::{catch_unwind, AssertUnwindSafe};
-use std::sync::atomic::{AtomicU32, Ordering};
-
-use super::DeterministicRng;
-
-#[test]
-fn test_clone_eq() {
-    let mut m = BTreeSet::new();
-
-    m.insert(1);
-    m.insert(2);
-
-    assert_eq!(m.clone(), m);
-}
-
-#[test]
-fn test_hash() {
-    use crate::hash;
-
-    let mut x = BTreeSet::new();
-    let mut y = BTreeSet::new();
-
-    x.insert(1);
-    x.insert(2);
-    x.insert(3);
-
-    y.insert(3);
-    y.insert(2);
-    y.insert(1);
-
-    assert_eq!(hash(&x), hash(&y));
-}
-
-#[test]
-fn test_iter_min_max() {
-    let mut a = BTreeSet::new();
-    assert_eq!(a.iter().min(), None);
-    assert_eq!(a.iter().max(), None);
-    assert_eq!(a.range(..).min(), None);
-    assert_eq!(a.range(..).max(), None);
-    assert_eq!(a.difference(&BTreeSet::new()).min(), None);
-    assert_eq!(a.difference(&BTreeSet::new()).max(), None);
-    assert_eq!(a.intersection(&a).min(), None);
-    assert_eq!(a.intersection(&a).max(), None);
-    assert_eq!(a.symmetric_difference(&BTreeSet::new()).min(), None);
-    assert_eq!(a.symmetric_difference(&BTreeSet::new()).max(), None);
-    assert_eq!(a.union(&a).min(), None);
-    assert_eq!(a.union(&a).max(), None);
-    a.insert(1);
-    a.insert(2);
-    assert_eq!(a.iter().min(), Some(&1));
-    assert_eq!(a.iter().max(), Some(&2));
-    assert_eq!(a.range(..).min(), Some(&1));
-    assert_eq!(a.range(..).max(), Some(&2));
-    assert_eq!(a.difference(&BTreeSet::new()).min(), Some(&1));
-    assert_eq!(a.difference(&BTreeSet::new()).max(), Some(&2));
-    assert_eq!(a.intersection(&a).min(), Some(&1));
-    assert_eq!(a.intersection(&a).max(), Some(&2));
-    assert_eq!(a.symmetric_difference(&BTreeSet::new()).min(), Some(&1));
-    assert_eq!(a.symmetric_difference(&BTreeSet::new()).max(), Some(&2));
-    assert_eq!(a.union(&a).min(), Some(&1));
-    assert_eq!(a.union(&a).max(), Some(&2));
-}
-
-fn check<F>(a: &[i32], b: &[i32], expected: &[i32], f: F)
-where
-    F: FnOnce(&BTreeSet<i32>, &BTreeSet<i32>, &mut dyn FnMut(&i32) -> bool) -> bool,
-{
-    let mut set_a = BTreeSet::new();
-    let mut set_b = BTreeSet::new();
-
-    for x in a {
-        assert!(set_a.insert(*x))
-    }
-    for y in b {
-        assert!(set_b.insert(*y))
-    }
-
-    let mut i = 0;
-    f(&set_a, &set_b, &mut |&x| {
-        if i < expected.len() {
-            assert_eq!(x, expected[i]);
-        }
-        i += 1;
-        true
-    });
-    assert_eq!(i, expected.len());
-}
-
-#[test]
-fn test_intersection() {
-    fn check_intersection(a: &[i32], b: &[i32], expected: &[i32]) {
-        check(a, b, expected, |x, y, f| x.intersection(y).all(f))
-    }
-
-    check_intersection(&[], &[], &[]);
-    check_intersection(&[1, 2, 3], &[], &[]);
-    check_intersection(&[], &[1, 2, 3], &[]);
-    check_intersection(&[2], &[1, 2, 3], &[2]);
-    check_intersection(&[1, 2, 3], &[2], &[2]);
-    check_intersection(&[11, 1, 3, 77, 103, 5, -5], &[2, 11, 77, -9, -42, 5, 3], &[3, 5, 11, 77]);
-
-    if cfg!(miri) {
-        // Miri is too slow
-        return;
-    }
-
-    let large = (0..100).collect::<Vec<_>>();
-    check_intersection(&[], &large, &[]);
-    check_intersection(&large, &[], &[]);
-    check_intersection(&[-1], &large, &[]);
-    check_intersection(&large, &[-1], &[]);
-    check_intersection(&[0], &large, &[0]);
-    check_intersection(&large, &[0], &[0]);
-    check_intersection(&[99], &large, &[99]);
-    check_intersection(&large, &[99], &[99]);
-    check_intersection(&[100], &large, &[]);
-    check_intersection(&large, &[100], &[]);
-    check_intersection(&[11, 5000, 1, 3, 77, 8924], &large, &[1, 3, 11, 77]);
-}
-
-#[test]
-fn test_intersection_size_hint() {
-    let x: BTreeSet<i32> = [3, 4].iter().copied().collect();
-    let y: BTreeSet<i32> = [1, 2, 3].iter().copied().collect();
-    let mut iter = x.intersection(&y);
-    assert_eq!(iter.size_hint(), (1, Some(1)));
-    assert_eq!(iter.next(), Some(&3));
-    assert_eq!(iter.size_hint(), (0, Some(0)));
-    assert_eq!(iter.next(), None);
-
-    iter = y.intersection(&y);
-    assert_eq!(iter.size_hint(), (0, Some(3)));
-    assert_eq!(iter.next(), Some(&1));
-    assert_eq!(iter.size_hint(), (0, Some(2)));
-}
-
-#[test]
-fn test_difference() {
-    fn check_difference(a: &[i32], b: &[i32], expected: &[i32]) {
-        check(a, b, expected, |x, y, f| x.difference(y).all(f))
-    }
-
-    check_difference(&[], &[], &[]);
-    check_difference(&[1, 12], &[], &[1, 12]);
-    check_difference(&[], &[1, 2, 3, 9], &[]);
-    check_difference(&[1, 3, 5, 9, 11], &[3, 9], &[1, 5, 11]);
-    check_difference(&[1, 3, 5, 9, 11], &[3, 6, 9], &[1, 5, 11]);
-    check_difference(&[1, 3, 5, 9, 11], &[0, 1], &[3, 5, 9, 11]);
-    check_difference(&[1, 3, 5, 9, 11], &[11, 12], &[1, 3, 5, 9]);
-    check_difference(
-        &[-5, 11, 22, 33, 40, 42],
-        &[-12, -5, 14, 23, 34, 38, 39, 50],
-        &[11, 22, 33, 40, 42],
-    );
-
-    if cfg!(miri) {
-        // Miri is too slow
-        return;
-    }
-
-    let large = (0..100).collect::<Vec<_>>();
-    check_difference(&[], &large, &[]);
-    check_difference(&[-1], &large, &[-1]);
-    check_difference(&[0], &large, &[]);
-    check_difference(&[99], &large, &[]);
-    check_difference(&[100], &large, &[100]);
-    check_difference(&[11, 5000, 1, 3, 77, 8924], &large, &[5000, 8924]);
-    check_difference(&large, &[], &large);
-    check_difference(&large, &[-1], &large);
-    check_difference(&large, &[100], &large);
-}
-
-#[test]
-fn test_difference_size_hint() {
-    let s246: BTreeSet<i32> = [2, 4, 6].iter().copied().collect();
-    let s23456: BTreeSet<i32> = (2..=6).collect();
-    let mut iter = s246.difference(&s23456);
-    assert_eq!(iter.size_hint(), (0, Some(3)));
-    assert_eq!(iter.next(), None);
-
-    let s12345: BTreeSet<i32> = (1..=5).collect();
-    iter = s246.difference(&s12345);
-    assert_eq!(iter.size_hint(), (0, Some(3)));
-    assert_eq!(iter.next(), Some(&6));
-    assert_eq!(iter.size_hint(), (0, Some(0)));
-    assert_eq!(iter.next(), None);
-
-    let s34567: BTreeSet<i32> = (3..=7).collect();
-    iter = s246.difference(&s34567);
-    assert_eq!(iter.size_hint(), (0, Some(3)));
-    assert_eq!(iter.next(), Some(&2));
-    assert_eq!(iter.size_hint(), (0, Some(2)));
-    assert_eq!(iter.next(), None);
-
-    let s1: BTreeSet<i32> = (-9..=1).collect();
-    iter = s246.difference(&s1);
-    assert_eq!(iter.size_hint(), (3, Some(3)));
-
-    let s2: BTreeSet<i32> = (-9..=2).collect();
-    iter = s246.difference(&s2);
-    assert_eq!(iter.size_hint(), (2, Some(2)));
-    assert_eq!(iter.next(), Some(&4));
-    assert_eq!(iter.size_hint(), (1, Some(1)));
-
-    let s23: BTreeSet<i32> = (2..=3).collect();
-    iter = s246.difference(&s23);
-    assert_eq!(iter.size_hint(), (1, Some(3)));
-    assert_eq!(iter.next(), Some(&4));
-    assert_eq!(iter.size_hint(), (1, Some(1)));
-
-    let s4: BTreeSet<i32> = (4..=4).collect();
-    iter = s246.difference(&s4);
-    assert_eq!(iter.size_hint(), (2, Some(3)));
-    assert_eq!(iter.next(), Some(&2));
-    assert_eq!(iter.size_hint(), (1, Some(2)));
-    assert_eq!(iter.next(), Some(&6));
-    assert_eq!(iter.size_hint(), (0, Some(0)));
-    assert_eq!(iter.next(), None);
-
-    let s56: BTreeSet<i32> = (5..=6).collect();
-    iter = s246.difference(&s56);
-    assert_eq!(iter.size_hint(), (1, Some(3)));
-    assert_eq!(iter.next(), Some(&2));
-    assert_eq!(iter.size_hint(), (0, Some(2)));
-
-    let s6: BTreeSet<i32> = (6..=19).collect();
-    iter = s246.difference(&s6);
-    assert_eq!(iter.size_hint(), (2, Some(2)));
-    assert_eq!(iter.next(), Some(&2));
-    assert_eq!(iter.size_hint(), (1, Some(1)));
-
-    let s7: BTreeSet<i32> = (7..=19).collect();
-    iter = s246.difference(&s7);
-    assert_eq!(iter.size_hint(), (3, Some(3)));
-}
-
-#[test]
-fn test_symmetric_difference() {
-    fn check_symmetric_difference(a: &[i32], b: &[i32], expected: &[i32]) {
-        check(a, b, expected, |x, y, f| x.symmetric_difference(y).all(f))
-    }
-
-    check_symmetric_difference(&[], &[], &[]);
-    check_symmetric_difference(&[1, 2, 3], &[2], &[1, 3]);
-    check_symmetric_difference(&[2], &[1, 2, 3], &[1, 3]);
-    check_symmetric_difference(&[1, 3, 5, 9, 11], &[-2, 3, 9, 14, 22], &[-2, 1, 5, 11, 14, 22]);
-}
-
-#[test]
-fn test_symmetric_difference_size_hint() {
-    let x: BTreeSet<i32> = [2, 4].iter().copied().collect();
-    let y: BTreeSet<i32> = [1, 2, 3].iter().copied().collect();
-    let mut iter = x.symmetric_difference(&y);
-    assert_eq!(iter.size_hint(), (0, Some(5)));
-    assert_eq!(iter.next(), Some(&1));
-    assert_eq!(iter.size_hint(), (0, Some(4)));
-    assert_eq!(iter.next(), Some(&3));
-    assert_eq!(iter.size_hint(), (0, Some(1)));
-}
-
-#[test]
-fn test_union() {
-    fn check_union(a: &[i32], b: &[i32], expected: &[i32]) {
-        check(a, b, expected, |x, y, f| x.union(y).all(f))
-    }
-
-    check_union(&[], &[], &[]);
-    check_union(&[1, 2, 3], &[2], &[1, 2, 3]);
-    check_union(&[2], &[1, 2, 3], &[1, 2, 3]);
-    check_union(
-        &[1, 3, 5, 9, 11, 16, 19, 24],
-        &[-2, 1, 5, 9, 13, 19],
-        &[-2, 1, 3, 5, 9, 11, 13, 16, 19, 24],
-    );
-}
-
-#[test]
-fn test_union_size_hint() {
-    let x: BTreeSet<i32> = [2, 4].iter().copied().collect();
-    let y: BTreeSet<i32> = [1, 2, 3].iter().copied().collect();
-    let mut iter = x.union(&y);
-    assert_eq!(iter.size_hint(), (3, Some(5)));
-    assert_eq!(iter.next(), Some(&1));
-    assert_eq!(iter.size_hint(), (2, Some(4)));
-    assert_eq!(iter.next(), Some(&2));
-    assert_eq!(iter.size_hint(), (1, Some(2)));
-}
-
-#[test]
-// Only tests the simple function definition with respect to intersection
-fn test_is_disjoint() {
-    let one = [1].iter().collect::<BTreeSet<_>>();
-    let two = [2].iter().collect::<BTreeSet<_>>();
-    assert!(one.is_disjoint(&two));
-}
-
-#[test]
-// Also implicitly tests the trivial function definition of is_superset
-fn test_is_subset() {
-    fn is_subset(a: &[i32], b: &[i32]) -> bool {
-        let set_a = a.iter().collect::<BTreeSet<_>>();
-        let set_b = b.iter().collect::<BTreeSet<_>>();
-        set_a.is_subset(&set_b)
-    }
-
-    assert_eq!(is_subset(&[], &[]), true);
-    assert_eq!(is_subset(&[], &[1, 2]), true);
-    assert_eq!(is_subset(&[0], &[1, 2]), false);
-    assert_eq!(is_subset(&[1], &[1, 2]), true);
-    assert_eq!(is_subset(&[2], &[1, 2]), true);
-    assert_eq!(is_subset(&[3], &[1, 2]), false);
-    assert_eq!(is_subset(&[1, 2], &[1]), false);
-    assert_eq!(is_subset(&[1, 2], &[1, 2]), true);
-    assert_eq!(is_subset(&[1, 2], &[2, 3]), false);
-    assert_eq!(
-        is_subset(&[-5, 11, 22, 33, 40, 42], &[-12, -5, 11, 14, 22, 23, 33, 34, 38, 39, 40, 42]),
-        true
-    );
-    assert_eq!(is_subset(&[-5, 11, 22, 33, 40, 42], &[-12, -5, 11, 14, 22, 23, 34, 38]), false);
-
-    if cfg!(miri) {
-        // Miri is too slow
-        return;
-    }
-
-    let large = (0..100).collect::<Vec<_>>();
-    assert_eq!(is_subset(&[], &large), true);
-    assert_eq!(is_subset(&large, &[]), false);
-    assert_eq!(is_subset(&[-1], &large), false);
-    assert_eq!(is_subset(&[0], &large), true);
-    assert_eq!(is_subset(&[1, 2], &large), true);
-    assert_eq!(is_subset(&[99, 100], &large), false);
-}
-
-#[test]
-fn test_drain_filter() {
-    let mut x: BTreeSet<_> = [1].iter().copied().collect();
-    let mut y: BTreeSet<_> = [1].iter().copied().collect();
-
-    x.drain_filter(|_| true);
-    y.drain_filter(|_| false);
-    assert_eq!(x.len(), 0);
-    assert_eq!(y.len(), 1);
-}
-
-#[test]
-fn test_drain_filter_drop_panic_leak() {
-    static PREDS: AtomicU32 = AtomicU32::new(0);
-    static DROPS: AtomicU32 = AtomicU32::new(0);
-
-    #[derive(PartialEq, Eq, PartialOrd, Ord)]
-    struct D(i32);
-    impl Drop for D {
-        fn drop(&mut self) {
-            if DROPS.fetch_add(1, Ordering::SeqCst) == 1 {
-                panic!("panic in `drop`");
-            }
-        }
-    }
-
-    let mut set = BTreeSet::new();
-    set.insert(D(0));
-    set.insert(D(4));
-    set.insert(D(8));
-
-    catch_unwind(move || {
-        drop(set.drain_filter(|d| {
-            PREDS.fetch_add(1u32 << d.0, Ordering::SeqCst);
-            true
-        }))
-    })
-    .ok();
-
-    assert_eq!(PREDS.load(Ordering::SeqCst), 0x011);
-    assert_eq!(DROPS.load(Ordering::SeqCst), 3);
-}
-
-#[test]
-fn test_drain_filter_pred_panic_leak() {
-    static PREDS: AtomicU32 = AtomicU32::new(0);
-    static DROPS: AtomicU32 = AtomicU32::new(0);
-
-    #[derive(PartialEq, Eq, PartialOrd, Ord)]
-    struct D(i32);
-    impl Drop for D {
-        fn drop(&mut self) {
-            DROPS.fetch_add(1, Ordering::SeqCst);
-        }
-    }
-
-    let mut set = BTreeSet::new();
-    set.insert(D(0));
-    set.insert(D(4));
-    set.insert(D(8));
-
-    catch_unwind(AssertUnwindSafe(|| {
-        drop(set.drain_filter(|d| {
-            PREDS.fetch_add(1u32 << d.0, Ordering::SeqCst);
-            match d.0 {
-                0 => true,
-                _ => panic!(),
-            }
-        }))
-    }))
-    .ok();
-
-    assert_eq!(PREDS.load(Ordering::SeqCst), 0x011);
-    assert_eq!(DROPS.load(Ordering::SeqCst), 1);
-    assert_eq!(set.len(), 2);
-    assert_eq!(set.first().unwrap().0, 4);
-    assert_eq!(set.last().unwrap().0, 8);
-}
-
-#[test]
-fn test_clear() {
-    let mut x = BTreeSet::new();
-    x.insert(1);
-
-    x.clear();
-    assert!(x.is_empty());
-}
-
-#[test]
-fn test_zip() {
-    let mut x = BTreeSet::new();
-    x.insert(5);
-    x.insert(12);
-    x.insert(11);
-
-    let mut y = BTreeSet::new();
-    y.insert("foo");
-    y.insert("bar");
-
-    let x = x;
-    let y = y;
-    let mut z = x.iter().zip(&y);
-
-    assert_eq!(z.next().unwrap(), (&5, &("bar")));
-    assert_eq!(z.next().unwrap(), (&11, &("foo")));
-    assert!(z.next().is_none());
-}
-
-#[test]
-fn test_from_iter() {
-    let xs = [1, 2, 3, 4, 5, 6, 7, 8, 9];
-
-    let set: BTreeSet<_> = xs.iter().cloned().collect();
-
-    for x in &xs {
-        assert!(set.contains(x));
-    }
-}
-
-#[test]
-fn test_show() {
-    let mut set = BTreeSet::new();
-    let empty = BTreeSet::<i32>::new();
-
-    set.insert(1);
-    set.insert(2);
-
-    let set_str = format!("{:?}", set);
-
-    assert_eq!(set_str, "{1, 2}");
-    assert_eq!(format!("{:?}", empty), "{}");
-}
-
-#[test]
-fn test_extend_ref() {
-    let mut a = BTreeSet::new();
-    a.insert(1);
-
-    a.extend(&[2, 3, 4]);
-
-    assert_eq!(a.len(), 4);
-    assert!(a.contains(&1));
-    assert!(a.contains(&2));
-    assert!(a.contains(&3));
-    assert!(a.contains(&4));
-
-    let mut b = BTreeSet::new();
-    b.insert(5);
-    b.insert(6);
-
-    a.extend(&b);
-
-    assert_eq!(a.len(), 6);
-    assert!(a.contains(&1));
-    assert!(a.contains(&2));
-    assert!(a.contains(&3));
-    assert!(a.contains(&4));
-    assert!(a.contains(&5));
-    assert!(a.contains(&6));
-}
-
-#[test]
-fn test_recovery() {
-    use std::cmp::Ordering;
-
-    #[derive(Debug)]
-    struct Foo(&'static str, i32);
-
-    impl PartialEq for Foo {
-        fn eq(&self, other: &Self) -> bool {
-            self.0 == other.0
-        }
-    }
-
-    impl Eq for Foo {}
-
-    impl PartialOrd for Foo {
-        fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
-            self.0.partial_cmp(&other.0)
-        }
-    }
-
-    impl Ord for Foo {
-        fn cmp(&self, other: &Self) -> Ordering {
-            self.0.cmp(&other.0)
-        }
-    }
-
-    let mut s = BTreeSet::new();
-    assert_eq!(s.replace(Foo("a", 1)), None);
-    assert_eq!(s.len(), 1);
-    assert_eq!(s.replace(Foo("a", 2)), Some(Foo("a", 1)));
-    assert_eq!(s.len(), 1);
-
-    {
-        let mut it = s.iter();
-        assert_eq!(it.next(), Some(&Foo("a", 2)));
-        assert_eq!(it.next(), None);
-    }
-
-    assert_eq!(s.get(&Foo("a", 1)), Some(&Foo("a", 2)));
-    assert_eq!(s.take(&Foo("a", 1)), Some(Foo("a", 2)));
-    assert_eq!(s.len(), 0);
-
-    assert_eq!(s.get(&Foo("a", 1)), None);
-    assert_eq!(s.take(&Foo("a", 1)), None);
-
-    assert_eq!(s.iter().next(), None);
-}
-
-#[test]
-#[allow(dead_code)]
-fn test_variance() {
-    use std::collections::btree_set::{IntoIter, Iter, Range};
-
-    fn set<'new>(v: BTreeSet<&'static str>) -> BTreeSet<&'new str> {
-        v
-    }
-    fn iter<'a, 'new>(v: Iter<'a, &'static str>) -> Iter<'a, &'new str> {
-        v
-    }
-    fn into_iter<'new>(v: IntoIter<&'static str>) -> IntoIter<&'new str> {
-        v
-    }
-    fn range<'a, 'new>(v: Range<'a, &'static str>) -> Range<'a, &'new str> {
-        v
-    }
-}
-
-#[test]
-fn test_append() {
-    let mut a = BTreeSet::new();
-    a.insert(1);
-    a.insert(2);
-    a.insert(3);
-
-    let mut b = BTreeSet::new();
-    b.insert(3);
-    b.insert(4);
-    b.insert(5);
-
-    a.append(&mut b);
-
-    assert_eq!(a.len(), 5);
-    assert_eq!(b.len(), 0);
-
-    assert_eq!(a.contains(&1), true);
-    assert_eq!(a.contains(&2), true);
-    assert_eq!(a.contains(&3), true);
-    assert_eq!(a.contains(&4), true);
-    assert_eq!(a.contains(&5), true);
-}
-
-#[test]
-fn test_first_last() {
-    let mut a = BTreeSet::new();
-    assert_eq!(a.first(), None);
-    assert_eq!(a.last(), None);
-    a.insert(1);
-    assert_eq!(a.first(), Some(&1));
-    assert_eq!(a.last(), Some(&1));
-    a.insert(2);
-    assert_eq!(a.first(), Some(&1));
-    assert_eq!(a.last(), Some(&2));
-    for i in 3..=12 {
-        a.insert(i);
-    }
-    assert_eq!(a.first(), Some(&1));
-    assert_eq!(a.last(), Some(&12));
-    assert_eq!(a.pop_first(), Some(1));
-    assert_eq!(a.pop_last(), Some(12));
-    assert_eq!(a.pop_first(), Some(2));
-    assert_eq!(a.pop_last(), Some(11));
-    assert_eq!(a.pop_first(), Some(3));
-    assert_eq!(a.pop_last(), Some(10));
-    assert_eq!(a.pop_first(), Some(4));
-    assert_eq!(a.pop_first(), Some(5));
-    assert_eq!(a.pop_first(), Some(6));
-    assert_eq!(a.pop_first(), Some(7));
-    assert_eq!(a.pop_first(), Some(8));
-    assert_eq!(a.clone().pop_last(), Some(9));
-    assert_eq!(a.pop_first(), Some(9));
-    assert_eq!(a.pop_first(), None);
-    assert_eq!(a.pop_last(), None);
-}
-
-fn rand_data(len: usize) -> Vec<u32> {
-    let mut rng = DeterministicRng::new();
-    Vec::from_iter((0..len).map(|_| rng.next()))
-}
-
-#[test]
-fn test_split_off_empty_right() {
-    let mut data = rand_data(173);
-
-    let mut set = BTreeSet::from_iter(data.clone());
-    let right = set.split_off(&(data.iter().max().unwrap() + 1));
-
-    data.sort();
-    assert!(set.into_iter().eq(data));
-    assert!(right.into_iter().eq(None));
-}
-
-#[test]
-fn test_split_off_empty_left() {
-    let mut data = rand_data(314);
-
-    let mut set = BTreeSet::from_iter(data.clone());
-    let right = set.split_off(data.iter().min().unwrap());
-
-    data.sort();
-    assert!(set.into_iter().eq(None));
-    assert!(right.into_iter().eq(data));
-}
-
-#[test]
-fn test_split_off_large_random_sorted() {
-    // Miri is too slow
-    let mut data = if cfg!(miri) { rand_data(529) } else { rand_data(1529) };
-    // special case with maximum height.
-    data.sort();
-
-    let mut set = BTreeSet::from_iter(data.clone());
-    let key = data[data.len() / 2];
-    let right = set.split_off(&key);
-
-    assert!(set.into_iter().eq(data.clone().into_iter().filter(|x| *x < key)));
-    assert!(right.into_iter().eq(data.into_iter().filter(|x| *x >= key)));
-}
diff --git a/library/alloc/tests/btree_set_hash.rs b/library/alloc/tests/btree_set_hash.rs
new file mode 100644
index 00000000000..e06a95ded94
--- /dev/null
+++ b/library/alloc/tests/btree_set_hash.rs
@@ -0,0 +1,19 @@
+use std::collections::BTreeSet;
+
+#[test]
+fn test_hash() {
+    use crate::hash;
+
+    let mut x = BTreeSet::new();
+    let mut y = BTreeSet::new();
+
+    x.insert(1);
+    x.insert(2);
+    x.insert(3);
+
+    y.insert(3);
+    y.insert(2);
+    y.insert(1);
+
+    assert_eq!(hash(&x), hash(&y));
+}
diff --git a/library/alloc/tests/lib.rs b/library/alloc/tests/lib.rs
index 3aacd4a687e..f2ba1ab6481 100644
--- a/library/alloc/tests/lib.rs
+++ b/library/alloc/tests/lib.rs
@@ -1,10 +1,7 @@
 #![feature(allocator_api)]
 #![feature(box_syntax)]
-#![feature(btree_drain_filter)]
 #![feature(drain_filter)]
 #![feature(exact_size_is_empty)]
-#![feature(map_first_last)]
-#![feature(map_into_keys_values)]
 #![feature(new_uninit)]
 #![feature(pattern)]
 #![feature(str_split_once)]
@@ -25,7 +22,7 @@ mod arc;
 mod binary_heap;
 mod borrow;
 mod boxed;
-mod btree;
+mod btree_set_hash;
 mod cow_str;
 mod fmt;
 mod heap;