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

   1 use super::super::{node, DeterministicRng};
   2 use super::Entry::{Occupied, Vacant};
   3 use super::*;
   4 use crate::boxed::Box;
   5 use crate::fmt::Debug;
   6 use crate::rc::Rc;
   7 use crate::string::{String, ToString};
   8 use crate::vec::Vec;
   9 use std::convert::TryFrom;
  10 use std::iter::{self, FromIterator};
  11 use std::mem;
  12 use std::ops::Bound::{self, Excluded, Included, Unbounded};
  13 use std::ops::RangeBounds;
  14 use std::panic::{catch_unwind, AssertUnwindSafe};
  15 use std::sync::atomic::{AtomicUsize, Ordering};
  16
  17 mod ord_chaos;
  18 use ord_chaos::{Cyclic3, Governed, Governor};
  19
  20 // Capacity of a tree with a single level,
  21 // i.e., a tree who's root is a leaf node at height 0.
  22 const NODE_CAPACITY: usize = node::CAPACITY;
  23
  24 // Minimum number of elements to insert, to guarantee a tree with 2 levels,
  25 // i.e., a tree who's root is an internal node at height 1, with edges to leaf nodes.
  26 // It's not the minimum size: removing an element from such a tree does not always reduce height.
  27 const MIN_INSERTS_HEIGHT_1: usize = NODE_CAPACITY + 1;
  28
  29 // Minimum number of elements to insert in ascending order, to guarantee a tree with 3 levels,
  30 // i.e., a tree who's root is an internal node at height 2, with edges to more internal nodes.
  31 // It's not the minimum size: removing an element from such a tree does not always reduce height.
  32 const MIN_INSERTS_HEIGHT_2: usize = 89;
  33
  34 // Gathers all references from a mutable iterator and makes sure Miri notices if
  35 // using them is dangerous.
  36 fn test_all_refs<'a, T: 'a>(dummy: &mut T, iter: impl Iterator<Item = &'a mut T>) {
  37     // Gather all those references.
  38     let mut refs: Vec<&mut T> = iter.collect();
  39     // Use them all. Twice, to be sure we got all interleavings.
  40     for r in refs.iter_mut() {
  41         mem::swap(dummy, r);
  42     }
  43     for r in refs {
  44         mem::swap(dummy, r);
  45     }
  46 }
  47
  48 impl<K, V> BTreeMap<K, V> {
  49     // Panics if the map (or the code navigating it) is corrupted.
  50     fn check_invariants(&self) {
  51         if let Some(root) = &self.root {
  52             let root_node = root.reborrow();
  53
  54             // Check the back pointers top-down, before we attempt to rely on
  55             // more serious navigation code.
  56             assert!(root_node.ascend().is_err());
  57             root_node.assert_back_pointers();
  58
  59             // Check consistenty of `length` and some of the navigation.
  60             assert_eq!(self.length, root_node.calc_length());
  61             assert_eq!(self.length, self.keys().count());
  62
  63             // Lastly, check the invariant causing the least harm.
  64             root_node.assert_min_len(if root_node.height() > 0 { 1 } else { 0 });
  65         } else {
  66             // Check consistenty of `length` and some of the navigation.
  67             assert_eq!(self.length, 0);
  68             assert_eq!(self.length, self.keys().count());
  69         }
  70     }
  71
  72     // Panics if the map is corrupted or if the keys are not in strictly
  73     // ascending order, in the current opinion of the `Ord` implementation.
  74     // If the `Ord` implementation does not honor transitivity, this method
  75     // does not guarantee that all the keys are unique, just that adjacent
  76     // keys are unique.
  77     fn check(&self)
  78     where
  79         K: Debug + Ord,
  80     {
  81         self.check_invariants();
  82         self.assert_strictly_ascending();
  83     }
  84
  85     // Returns the height of the root, if any.
  86     fn height(&self) -> Option<usize> {
  87         self.root.as_ref().map(node::Root::height)
  88     }
  89
  90     fn dump_keys(&self) -> String
  91     where
  92         K: Debug,
  93     {
  94         if let Some(root) = self.root.as_ref() {
  95             root.reborrow().dump_keys()
  96         } else {
  97             String::from("not yet allocated")
  98         }
  99     }
 100
 101     // Panics if the keys are not in strictly ascending order.
 102     fn assert_strictly_ascending(&self)
 103     where
 104         K: Debug + Ord,
 105     {
 106         let mut keys = self.keys();
 107         if let Some(mut previous) = keys.next() {
 108             for next in keys {
 109                 assert!(previous < next, "{:?} >= {:?}", previous, next);
 110                 previous = next;
 111             }
 112         }
 113     }
 114 }
 115
 116 impl<'a, K: 'a, V: 'a> NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal> {
 117     fn assert_min_len(self, min_len: usize) {
 118         assert!(self.len() >= min_len, "{} < {}", self.len(), min_len);
 119         if let node::ForceResult::Internal(node) = self.force() {
 120             for idx in 0..=node.len() {
 121                 let edge = unsafe { Handle::new_edge(node, idx) };
 122                 edge.descend().assert_min_len(MIN_LEN);
 123             }
 124         }
 125     }
 126 }
 127
 128 // Tests our value of MIN_INSERTS_HEIGHT_2. It may change according to the
 129 // implementation of insertion, but it's best to be aware of when it does.
 130 #[test]
 131 fn test_levels() {
 132     let mut map = BTreeMap::new();
 133     map.check();
 134     assert_eq!(map.height(), None);
 135     assert_eq!(map.len(), 0);
 136
 137     map.insert(0, ());
 138     while map.height() == Some(0) {
 139         let last_key = *map.last_key_value().unwrap().0;
 140         map.insert(last_key + 1, ());
 141     }
 142     map.check();
 143     // Structure:
 144     // - 1 element in internal root node with 2 children
 145     // - 6 elements in left leaf child
 146     // - 5 elements in right leaf child
 147     assert_eq!(map.height(), Some(1));
 148     assert_eq!(map.len(), MIN_INSERTS_HEIGHT_1, "{}", map.dump_keys());
 149
 150     while map.height() == Some(1) {
 151         let last_key = *map.last_key_value().unwrap().0;
 152         map.insert(last_key + 1, ());
 153     }
 154     map.check();
 155     // Structure:
 156     // - 1 element in internal root node with 2 children
 157     // - 6 elements in left internal child with 7 grandchildren
 158     // - 42 elements in left child's 7 grandchildren with 6 elements each
 159     // - 5 elements in right internal child with 6 grandchildren
 160     // - 30 elements in right child's 5 first grandchildren with 6 elements each
 161     // - 5 elements in right child's last grandchild
 162     assert_eq!(map.height(), Some(2));
 163     assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2, "{}", map.dump_keys());
 164 }
 165
 166 // Ensures the testing infrastructure usually notices order violations.
 167 #[test]
 168 #[should_panic]
 169 fn test_check_ord_chaos() {
 170     let gov = Governor::new();
 171     let map: BTreeMap<_, _> = (0..2).map(|i| (Governed(i, &gov), ())).collect();
 172     gov.flip();
 173     map.check();
 174 }
 175
 176 // Ensures the testing infrastructure doesn't always mind order violations.
 177 #[test]
 178 fn test_check_invariants_ord_chaos() {
 179     let gov = Governor::new();
 180     let map: BTreeMap<_, _> = (0..2).map(|i| (Governed(i, &gov), ())).collect();
 181     gov.flip();
 182     map.check_invariants();
 183 }
 184
 185 #[test]
 186 fn test_basic_large() {
 187     let mut map = BTreeMap::new();
 188     // Miri is too slow
 189     let size = if cfg!(miri) { MIN_INSERTS_HEIGHT_2 } else { 10000 };
 190     let size = size + (size % 2); // round up to even number
 191     assert_eq!(map.len(), 0);
 192
 193     for i in 0..size {
 194         assert_eq!(map.insert(i, 10 * i), None);
 195         assert_eq!(map.len(), i + 1);
 196     }
 197
 198     assert_eq!(map.first_key_value(), Some((&0, &0)));
 199     assert_eq!(map.last_key_value(), Some((&(size - 1), &(10 * (size - 1)))));
 200     assert_eq!(map.first_entry().unwrap().key(), &0);
 201     assert_eq!(map.last_entry().unwrap().key(), &(size - 1));
 202
 203     for i in 0..size {
 204         assert_eq!(map.get(&i).unwrap(), &(i * 10));
 205     }
 206
 207     for i in size..size * 2 {
 208         assert_eq!(map.get(&i), None);
 209     }
 210
 211     for i in 0..size {
 212         assert_eq!(map.insert(i, 100 * i), Some(10 * i));
 213         assert_eq!(map.len(), size);
 214     }
 215
 216     for i in 0..size {
 217         assert_eq!(map.get(&i).unwrap(), &(i * 100));
 218     }
 219
 220     for i in 0..size / 2 {
 221         assert_eq!(map.remove(&(i * 2)), Some(i * 200));
 222         assert_eq!(map.len(), size - i - 1);
 223     }
 224
 225     for i in 0..size / 2 {
 226         assert_eq!(map.get(&(2 * i)), None);
 227         assert_eq!(map.get(&(2 * i + 1)).unwrap(), &(i * 200 + 100));
 228     }
 229
 230     for i in 0..size / 2 {
 231         assert_eq!(map.remove(&(2 * i)), None);
 232         assert_eq!(map.remove(&(2 * i + 1)), Some(i * 200 + 100));
 233         assert_eq!(map.len(), size / 2 - i - 1);
 234     }
 235     map.check();
 236 }
 237
 238 #[test]
 239 fn test_basic_small() {
 240     let mut map = BTreeMap::new();
 241     // Empty, root is absent (None):
 242     assert_eq!(map.remove(&1), None);
 243     assert_eq!(map.len(), 0);
 244     assert_eq!(map.get(&1), None);
 245     assert_eq!(map.get_mut(&1), None);
 246     assert_eq!(map.first_key_value(), None);
 247     assert_eq!(map.last_key_value(), None);
 248     assert_eq!(map.keys().count(), 0);
 249     assert_eq!(map.values().count(), 0);
 250     assert_eq!(map.range(..).next(), None);
 251     assert_eq!(map.range(..1).next(), None);
 252     assert_eq!(map.range(1..).next(), None);
 253     assert_eq!(map.range(1..=1).next(), None);
 254     assert_eq!(map.range(1..2).next(), None);
 255     assert_eq!(map.height(), None);
 256     assert_eq!(map.insert(1, 1), None);
 257     assert_eq!(map.height(), Some(0));
 258     map.check();
 259
 260     // 1 key-value pair:
 261     assert_eq!(map.len(), 1);
 262     assert_eq!(map.get(&1), Some(&1));
 263     assert_eq!(map.get_mut(&1), Some(&mut 1));
 264     assert_eq!(map.first_key_value(), Some((&1, &1)));
 265     assert_eq!(map.last_key_value(), Some((&1, &1)));
 266     assert_eq!(map.keys().collect::<Vec<_>>(), vec![&1]);
 267     assert_eq!(map.values().collect::<Vec<_>>(), vec![&1]);
 268     assert_eq!(map.insert(1, 2), Some(1));
 269     assert_eq!(map.len(), 1);
 270     assert_eq!(map.get(&1), Some(&2));
 271     assert_eq!(map.get_mut(&1), Some(&mut 2));
 272     assert_eq!(map.first_key_value(), Some((&1, &2)));
 273     assert_eq!(map.last_key_value(), Some((&1, &2)));
 274     assert_eq!(map.keys().collect::<Vec<_>>(), vec![&1]);
 275     assert_eq!(map.values().collect::<Vec<_>>(), vec![&2]);
 276     assert_eq!(map.insert(2, 4), None);
 277     assert_eq!(map.height(), Some(0));
 278     map.check();
 279
 280     // 2 key-value pairs:
 281     assert_eq!(map.len(), 2);
 282     assert_eq!(map.get(&2), Some(&4));
 283     assert_eq!(map.get_mut(&2), Some(&mut 4));
 284     assert_eq!(map.first_key_value(), Some((&1, &2)));
 285     assert_eq!(map.last_key_value(), Some((&2, &4)));
 286     assert_eq!(map.keys().collect::<Vec<_>>(), vec![&1, &2]);
 287     assert_eq!(map.values().collect::<Vec<_>>(), vec![&2, &4]);
 288     assert_eq!(map.remove(&1), Some(2));
 289     assert_eq!(map.height(), Some(0));
 290     map.check();
 291
 292     // 1 key-value pair:
 293     assert_eq!(map.len(), 1);
 294     assert_eq!(map.get(&1), None);
 295     assert_eq!(map.get_mut(&1), None);
 296     assert_eq!(map.get(&2), Some(&4));
 297     assert_eq!(map.get_mut(&2), Some(&mut 4));
 298     assert_eq!(map.first_key_value(), Some((&2, &4)));
 299     assert_eq!(map.last_key_value(), Some((&2, &4)));
 300     assert_eq!(map.keys().collect::<Vec<_>>(), vec![&2]);
 301     assert_eq!(map.values().collect::<Vec<_>>(), vec![&4]);
 302     assert_eq!(map.remove(&2), Some(4));
 303     assert_eq!(map.height(), Some(0));
 304     map.check();
 305
 306     // Empty but root is owned (Some(...)):
 307     assert_eq!(map.len(), 0);
 308     assert_eq!(map.get(&1), None);
 309     assert_eq!(map.get_mut(&1), None);
 310     assert_eq!(map.first_key_value(), None);
 311     assert_eq!(map.last_key_value(), None);
 312     assert_eq!(map.keys().count(), 0);
 313     assert_eq!(map.values().count(), 0);
 314     assert_eq!(map.range(..).next(), None);
 315     assert_eq!(map.range(..1).next(), None);
 316     assert_eq!(map.range(1..).next(), None);
 317     assert_eq!(map.range(1..=1).next(), None);
 318     assert_eq!(map.range(1..2).next(), None);
 319     assert_eq!(map.remove(&1), None);
 320     assert_eq!(map.height(), Some(0));
 321     map.check();
 322 }
 323
 324 #[test]
 325 fn test_iter() {
 326     // Miri is too slow
 327     let size = if cfg!(miri) { 200 } else { 10000 };
 328
 329     let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 330
 331     fn test<T>(size: usize, mut iter: T)
 332     where
 333         T: Iterator<Item = (usize, usize)>,
 334     {
 335         for i in 0..size {
 336             assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
 337             assert_eq!(iter.next().unwrap(), (i, i));
 338         }
 339         assert_eq!(iter.size_hint(), (0, Some(0)));
 340         assert_eq!(iter.next(), None);
 341     }
 342     test(size, map.iter().map(|(&k, &v)| (k, v)));
 343     test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
 344     test(size, map.into_iter());
 345 }
 346
 347 #[test]
 348 fn test_iter_rev() {
 349     // Miri is too slow
 350     let size = if cfg!(miri) { 200 } else { 10000 };
 351
 352     let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 353
 354     fn test<T>(size: usize, mut iter: T)
 355     where
 356         T: Iterator<Item = (usize, usize)>,
 357     {
 358         for i in 0..size {
 359             assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
 360             assert_eq!(iter.next().unwrap(), (size - i - 1, size - i - 1));
 361         }
 362         assert_eq!(iter.size_hint(), (0, Some(0)));
 363         assert_eq!(iter.next(), None);
 364     }
 365     test(size, map.iter().rev().map(|(&k, &v)| (k, v)));
 366     test(size, map.iter_mut().rev().map(|(&k, &mut v)| (k, v)));
 367     test(size, map.into_iter().rev());
 368 }
 369
 370 // Specifically tests iter_mut's ability to mutate the value of pairs in-line.
 371 fn do_test_iter_mut_mutation<T>(size: usize)
 372 where
 373     T: Copy + Debug + Ord + TryFrom<usize>,
 374     <T as TryFrom<usize>>::Error: Debug,
 375 {
 376     let zero = T::try_from(0).unwrap();
 377     let mut map: BTreeMap<T, T> = (0..size).map(|i| (T::try_from(i).unwrap(), zero)).collect();
 378
 379     // Forward and backward iteration sees enough pairs (also tested elsewhere)
 380     assert_eq!(map.iter_mut().count(), size);
 381     assert_eq!(map.iter_mut().rev().count(), size);
 382
 383     // Iterate forwards, trying to mutate to unique values
 384     for (i, (k, v)) in map.iter_mut().enumerate() {
 385         assert_eq!(*k, T::try_from(i).unwrap());
 386         assert_eq!(*v, zero);
 387         *v = T::try_from(i + 1).unwrap();
 388     }
 389
 390     // Iterate backwards, checking that mutations succeeded and trying to mutate again
 391     for (i, (k, v)) in map.iter_mut().rev().enumerate() {
 392         assert_eq!(*k, T::try_from(size - i - 1).unwrap());
 393         assert_eq!(*v, T::try_from(size - i).unwrap());
 394         *v = T::try_from(2 * size - i).unwrap();
 395     }
 396
 397     // Check that backward mutations succeeded
 398     for (i, (k, v)) in map.iter_mut().enumerate() {
 399         assert_eq!(*k, T::try_from(i).unwrap());
 400         assert_eq!(*v, T::try_from(size + i + 1).unwrap());
 401     }
 402     map.check();
 403 }
 404
 405 #[derive(Clone, Copy, Debug, Eq, PartialEq, PartialOrd, Ord)]
 406 #[repr(align(32))]
 407 struct Align32(usize);
 408
 409 impl TryFrom<usize> for Align32 {
 410     type Error = ();
 411
 412     fn try_from(s: usize) -> Result<Align32, ()> {
 413         Ok(Align32(s))
 414     }
 415 }
 416
 417 #[test]
 418 fn test_iter_mut_mutation() {
 419     // Check many alignments and trees with roots at various heights.
 420     do_test_iter_mut_mutation::<u8>(0);
 421     do_test_iter_mut_mutation::<u8>(1);
 422     do_test_iter_mut_mutation::<u8>(MIN_INSERTS_HEIGHT_1);
 423     do_test_iter_mut_mutation::<u8>(MIN_INSERTS_HEIGHT_2);
 424     do_test_iter_mut_mutation::<u16>(1);
 425     do_test_iter_mut_mutation::<u16>(MIN_INSERTS_HEIGHT_1);
 426     do_test_iter_mut_mutation::<u16>(MIN_INSERTS_HEIGHT_2);
 427     do_test_iter_mut_mutation::<u32>(1);
 428     do_test_iter_mut_mutation::<u32>(MIN_INSERTS_HEIGHT_1);
 429     do_test_iter_mut_mutation::<u32>(MIN_INSERTS_HEIGHT_2);
 430     do_test_iter_mut_mutation::<u64>(1);
 431     do_test_iter_mut_mutation::<u64>(MIN_INSERTS_HEIGHT_1);
 432     do_test_iter_mut_mutation::<u64>(MIN_INSERTS_HEIGHT_2);
 433     do_test_iter_mut_mutation::<u128>(1);
 434     do_test_iter_mut_mutation::<u128>(MIN_INSERTS_HEIGHT_1);
 435     do_test_iter_mut_mutation::<u128>(MIN_INSERTS_HEIGHT_2);
 436     do_test_iter_mut_mutation::<Align32>(1);
 437     do_test_iter_mut_mutation::<Align32>(MIN_INSERTS_HEIGHT_1);
 438     do_test_iter_mut_mutation::<Align32>(MIN_INSERTS_HEIGHT_2);
 439 }
 440
 441 #[test]
 442 fn test_values_mut() {
 443     let mut a: BTreeMap<_, _> = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)).collect();
 444     test_all_refs(&mut 13, a.values_mut());
 445     a.check();
 446 }
 447
 448 #[test]
 449 fn test_values_mut_mutation() {
 450     let mut a = BTreeMap::new();
 451     a.insert(1, String::from("hello"));
 452     a.insert(2, String::from("goodbye"));
 453
 454     for value in a.values_mut() {
 455         value.push_str("!");
 456     }
 457
 458     let values: Vec<String> = a.values().cloned().collect();
 459     assert_eq!(values, [String::from("hello!"), String::from("goodbye!")]);
 460     a.check();
 461 }
 462
 463 #[test]
 464 fn test_iter_entering_root_twice() {
 465     let mut map: BTreeMap<_, _> = (0..2).map(|i| (i, i)).collect();
 466     let mut it = map.iter_mut();
 467     let front = it.next().unwrap();
 468     let back = it.next_back().unwrap();
 469     assert_eq!(front, (&0, &mut 0));
 470     assert_eq!(back, (&1, &mut 1));
 471     *front.1 = 24;
 472     *back.1 = 42;
 473     assert_eq!(front, (&0, &mut 24));
 474     assert_eq!(back, (&1, &mut 42));
 475     assert_eq!(it.next(), None);
 476     assert_eq!(it.next_back(), None);
 477     map.check();
 478 }
 479
 480 #[test]
 481 fn test_iter_descending_to_same_node_twice() {
 482     let mut map: BTreeMap<_, _> = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i)).collect();
 483     let mut it = map.iter_mut();
 484     // Descend into first child.
 485     let front = it.next().unwrap();
 486     // Descend into first child again, after running through second child.
 487     while it.next_back().is_some() {}
 488     // Check immutable access.
 489     assert_eq!(front, (&0, &mut 0));
 490     // Perform mutable access.
 491     *front.1 = 42;
 492     map.check();
 493 }
 494
 495 #[test]
 496 fn test_iter_mixed() {
 497     // Miri is too slow
 498     let size = if cfg!(miri) { 200 } else { 10000 };
 499
 500     let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 501
 502     fn test<T>(size: usize, mut iter: T)
 503     where
 504         T: Iterator<Item = (usize, usize)> + DoubleEndedIterator,
 505     {
 506         for i in 0..size / 4 {
 507             assert_eq!(iter.size_hint(), (size - i * 2, Some(size - i * 2)));
 508             assert_eq!(iter.next().unwrap(), (i, i));
 509             assert_eq!(iter.next_back().unwrap(), (size - i - 1, size - i - 1));
 510         }
 511         for i in size / 4..size * 3 / 4 {
 512             assert_eq!(iter.size_hint(), (size * 3 / 4 - i, Some(size * 3 / 4 - i)));
 513             assert_eq!(iter.next().unwrap(), (i, i));
 514         }
 515         assert_eq!(iter.size_hint(), (0, Some(0)));
 516         assert_eq!(iter.next(), None);
 517     }
 518     test(size, map.iter().map(|(&k, &v)| (k, v)));
 519     test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
 520     test(size, map.into_iter());
 521 }
 522
 523 #[test]
 524 fn test_iter_min_max() {
 525     let mut a = BTreeMap::new();
 526     assert_eq!(a.iter().min(), None);
 527     assert_eq!(a.iter().max(), None);
 528     assert_eq!(a.iter_mut().min(), None);
 529     assert_eq!(a.iter_mut().max(), None);
 530     assert_eq!(a.range(..).min(), None);
 531     assert_eq!(a.range(..).max(), None);
 532     assert_eq!(a.range_mut(..).min(), None);
 533     assert_eq!(a.range_mut(..).max(), None);
 534     assert_eq!(a.keys().min(), None);
 535     assert_eq!(a.keys().max(), None);
 536     assert_eq!(a.values().min(), None);
 537     assert_eq!(a.values().max(), None);
 538     assert_eq!(a.values_mut().min(), None);
 539     assert_eq!(a.values_mut().max(), None);
 540     a.insert(1, 42);
 541     a.insert(2, 24);
 542     assert_eq!(a.iter().min(), Some((&1, &42)));
 543     assert_eq!(a.iter().max(), Some((&2, &24)));
 544     assert_eq!(a.iter_mut().min(), Some((&1, &mut 42)));
 545     assert_eq!(a.iter_mut().max(), Some((&2, &mut 24)));
 546     assert_eq!(a.range(..).min(), Some((&1, &42)));
 547     assert_eq!(a.range(..).max(), Some((&2, &24)));
 548     assert_eq!(a.range_mut(..).min(), Some((&1, &mut 42)));
 549     assert_eq!(a.range_mut(..).max(), Some((&2, &mut 24)));
 550     assert_eq!(a.keys().min(), Some(&1));
 551     assert_eq!(a.keys().max(), Some(&2));
 552     assert_eq!(a.values().min(), Some(&24));
 553     assert_eq!(a.values().max(), Some(&42));
 554     assert_eq!(a.values_mut().min(), Some(&mut 24));
 555     assert_eq!(a.values_mut().max(), Some(&mut 42));
 556     a.check();
 557 }
 558
 559 fn range_keys(map: &BTreeMap<i32, i32>, range: impl RangeBounds<i32>) -> Vec<i32> {
 560     map.range(range)
 561         .map(|(&k, &v)| {
 562             assert_eq!(k, v);
 563             k
 564         })
 565         .collect()
 566 }
 567
 568 #[test]
 569 fn test_range_small() {
 570     let size = 4;
 571
 572     let map: BTreeMap<_, _> = (1..=size).map(|i| (i, i)).collect();
 573     let all: Vec<_> = (1..=size).collect();
 574     let (first, last) = (vec![all[0]], vec![all[size as usize - 1]]);
 575
 576     assert_eq!(range_keys(&map, (Excluded(0), Excluded(size + 1))), all);
 577     assert_eq!(range_keys(&map, (Excluded(0), Included(size + 1))), all);
 578     assert_eq!(range_keys(&map, (Excluded(0), Included(size))), all);
 579     assert_eq!(range_keys(&map, (Excluded(0), Unbounded)), all);
 580     assert_eq!(range_keys(&map, (Included(0), Excluded(size + 1))), all);
 581     assert_eq!(range_keys(&map, (Included(0), Included(size + 1))), all);
 582     assert_eq!(range_keys(&map, (Included(0), Included(size))), all);
 583     assert_eq!(range_keys(&map, (Included(0), Unbounded)), all);
 584     assert_eq!(range_keys(&map, (Included(1), Excluded(size + 1))), all);
 585     assert_eq!(range_keys(&map, (Included(1), Included(size + 1))), all);
 586     assert_eq!(range_keys(&map, (Included(1), Included(size))), all);
 587     assert_eq!(range_keys(&map, (Included(1), Unbounded)), all);
 588     assert_eq!(range_keys(&map, (Unbounded, Excluded(size + 1))), all);
 589     assert_eq!(range_keys(&map, (Unbounded, Included(size + 1))), all);
 590     assert_eq!(range_keys(&map, (Unbounded, Included(size))), all);
 591     assert_eq!(range_keys(&map, ..), all);
 592
 593     assert_eq!(range_keys(&map, (Excluded(0), Excluded(1))), vec![]);
 594     assert_eq!(range_keys(&map, (Excluded(0), Included(0))), vec![]);
 595     assert_eq!(range_keys(&map, (Included(0), Included(0))), vec![]);
 596     assert_eq!(range_keys(&map, (Included(0), Excluded(1))), vec![]);
 597     assert_eq!(range_keys(&map, (Unbounded, Excluded(1))), vec![]);
 598     assert_eq!(range_keys(&map, (Unbounded, Included(0))), vec![]);
 599     assert_eq!(range_keys(&map, (Excluded(0), Excluded(2))), first);
 600     assert_eq!(range_keys(&map, (Excluded(0), Included(1))), first);
 601     assert_eq!(range_keys(&map, (Included(0), Excluded(2))), first);
 602     assert_eq!(range_keys(&map, (Included(0), Included(1))), first);
 603     assert_eq!(range_keys(&map, (Included(1), Excluded(2))), first);
 604     assert_eq!(range_keys(&map, (Included(1), Included(1))), first);
 605     assert_eq!(range_keys(&map, (Unbounded, Excluded(2))), first);
 606     assert_eq!(range_keys(&map, (Unbounded, Included(1))), first);
 607     assert_eq!(range_keys(&map, (Excluded(size - 1), Excluded(size + 1))), last);
 608     assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size + 1))), last);
 609     assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size))), last);
 610     assert_eq!(range_keys(&map, (Excluded(size - 1), Unbounded)), last);
 611     assert_eq!(range_keys(&map, (Included(size), Excluded(size + 1))), last);
 612     assert_eq!(range_keys(&map, (Included(size), Included(size + 1))), last);
 613     assert_eq!(range_keys(&map, (Included(size), Included(size))), last);
 614     assert_eq!(range_keys(&map, (Included(size), Unbounded)), last);
 615     assert_eq!(range_keys(&map, (Excluded(size), Excluded(size + 1))), vec![]);
 616     assert_eq!(range_keys(&map, (Excluded(size), Included(size))), vec![]);
 617     assert_eq!(range_keys(&map, (Excluded(size), Unbounded)), vec![]);
 618     assert_eq!(range_keys(&map, (Included(size + 1), Excluded(size + 1))), vec![]);
 619     assert_eq!(range_keys(&map, (Included(size + 1), Included(size + 1))), vec![]);
 620     assert_eq!(range_keys(&map, (Included(size + 1), Unbounded)), vec![]);
 621
 622     assert_eq!(range_keys(&map, ..3), vec![1, 2]);
 623     assert_eq!(range_keys(&map, 3..), vec![3, 4]);
 624     assert_eq!(range_keys(&map, 2..=3), vec![2, 3]);
 625 }
 626
 627 #[test]
 628 fn test_range_height_1() {
 629     // Tests tree with a root and 2 leaves. The single key in the root node is
 630     // close to the middle among the keys.
 631
 632     let map: BTreeMap<_, _> = (0..MIN_INSERTS_HEIGHT_1 as i32).map(|i| (i, i)).collect();
 633     let middle = MIN_INSERTS_HEIGHT_1 as i32 / 2;
 634     for root in middle - 2..=middle + 2 {
 635         assert_eq!(range_keys(&map, (Excluded(root), Excluded(root + 1))), vec![]);
 636         assert_eq!(range_keys(&map, (Excluded(root), Included(root + 1))), vec![root + 1]);
 637         assert_eq!(range_keys(&map, (Included(root), Excluded(root + 1))), vec![root]);
 638         assert_eq!(range_keys(&map, (Included(root), Included(root + 1))), vec![root, root + 1]);
 639
 640         assert_eq!(range_keys(&map, (Excluded(root - 1), Excluded(root))), vec![]);
 641         assert_eq!(range_keys(&map, (Included(root - 1), Excluded(root))), vec![root - 1]);
 642         assert_eq!(range_keys(&map, (Excluded(root - 1), Included(root))), vec![root]);
 643         assert_eq!(range_keys(&map, (Included(root - 1), Included(root))), vec![root - 1, root]);
 644     }
 645 }
 646
 647 #[test]
 648 fn test_range_large() {
 649     let size = 200;
 650
 651     let map: BTreeMap<_, _> = (1..=size).map(|i| (i, i)).collect();
 652     let all: Vec<_> = (1..=size).collect();
 653     let (first, last) = (vec![all[0]], vec![all[size as usize - 1]]);
 654
 655     assert_eq!(range_keys(&map, (Excluded(0), Excluded(size + 1))), all);
 656     assert_eq!(range_keys(&map, (Excluded(0), Included(size + 1))), all);
 657     assert_eq!(range_keys(&map, (Excluded(0), Included(size))), all);
 658     assert_eq!(range_keys(&map, (Excluded(0), Unbounded)), all);
 659     assert_eq!(range_keys(&map, (Included(0), Excluded(size + 1))), all);
 660     assert_eq!(range_keys(&map, (Included(0), Included(size + 1))), all);
 661     assert_eq!(range_keys(&map, (Included(0), Included(size))), all);
 662     assert_eq!(range_keys(&map, (Included(0), Unbounded)), all);
 663     assert_eq!(range_keys(&map, (Included(1), Excluded(size + 1))), all);
 664     assert_eq!(range_keys(&map, (Included(1), Included(size + 1))), all);
 665     assert_eq!(range_keys(&map, (Included(1), Included(size))), all);
 666     assert_eq!(range_keys(&map, (Included(1), Unbounded)), all);
 667     assert_eq!(range_keys(&map, (Unbounded, Excluded(size + 1))), all);
 668     assert_eq!(range_keys(&map, (Unbounded, Included(size + 1))), all);
 669     assert_eq!(range_keys(&map, (Unbounded, Included(size))), all);
 670     assert_eq!(range_keys(&map, ..), all);
 671
 672     assert_eq!(range_keys(&map, (Excluded(0), Excluded(1))), vec![]);
 673     assert_eq!(range_keys(&map, (Excluded(0), Included(0))), vec![]);
 674     assert_eq!(range_keys(&map, (Included(0), Included(0))), vec![]);
 675     assert_eq!(range_keys(&map, (Included(0), Excluded(1))), vec![]);
 676     assert_eq!(range_keys(&map, (Unbounded, Excluded(1))), vec![]);
 677     assert_eq!(range_keys(&map, (Unbounded, Included(0))), vec![]);
 678     assert_eq!(range_keys(&map, (Excluded(0), Excluded(2))), first);
 679     assert_eq!(range_keys(&map, (Excluded(0), Included(1))), first);
 680     assert_eq!(range_keys(&map, (Included(0), Excluded(2))), first);
 681     assert_eq!(range_keys(&map, (Included(0), Included(1))), first);
 682     assert_eq!(range_keys(&map, (Included(1), Excluded(2))), first);
 683     assert_eq!(range_keys(&map, (Included(1), Included(1))), first);
 684     assert_eq!(range_keys(&map, (Unbounded, Excluded(2))), first);
 685     assert_eq!(range_keys(&map, (Unbounded, Included(1))), first);
 686     assert_eq!(range_keys(&map, (Excluded(size - 1), Excluded(size + 1))), last);
 687     assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size + 1))), last);
 688     assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size))), last);
 689     assert_eq!(range_keys(&map, (Excluded(size - 1), Unbounded)), last);
 690     assert_eq!(range_keys(&map, (Included(size), Excluded(size + 1))), last);
 691     assert_eq!(range_keys(&map, (Included(size), Included(size + 1))), last);
 692     assert_eq!(range_keys(&map, (Included(size), Included(size))), last);
 693     assert_eq!(range_keys(&map, (Included(size), Unbounded)), last);
 694     assert_eq!(range_keys(&map, (Excluded(size), Excluded(size + 1))), vec![]);
 695     assert_eq!(range_keys(&map, (Excluded(size), Included(size))), vec![]);
 696     assert_eq!(range_keys(&map, (Excluded(size), Unbounded)), vec![]);
 697     assert_eq!(range_keys(&map, (Included(size + 1), Excluded(size + 1))), vec![]);
 698     assert_eq!(range_keys(&map, (Included(size + 1), Included(size + 1))), vec![]);
 699     assert_eq!(range_keys(&map, (Included(size + 1), Unbounded)), vec![]);
 700
 701     fn check<'a, L, R>(lhs: L, rhs: R)
 702     where
 703         L: IntoIterator<Item = (&'a i32, &'a i32)>,
 704         R: IntoIterator<Item = (&'a i32, &'a i32)>,
 705     {
 706         let lhs: Vec<_> = lhs.into_iter().collect();
 707         let rhs: Vec<_> = rhs.into_iter().collect();
 708         assert_eq!(lhs, rhs);
 709     }
 710
 711     check(map.range(..=100), map.range(..101));
 712     check(map.range(5..=8), vec![(&5, &5), (&6, &6), (&7, &7), (&8, &8)]);
 713     check(map.range(-1..=2), vec![(&1, &1), (&2, &2)]);
 714 }
 715
 716 #[test]
 717 fn test_range_inclusive_max_value() {
 718     let max = usize::MAX;
 719     let map: BTreeMap<_, _> = vec![(max, 0)].into_iter().collect();
 720
 721     assert_eq!(map.range(max..=max).collect::<Vec<_>>(), &[(&max, &0)]);
 722 }
 723
 724 #[test]
 725 fn test_range_equal_empty_cases() {
 726     let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
 727     assert_eq!(map.range((Included(2), Excluded(2))).next(), None);
 728     assert_eq!(map.range((Excluded(2), Included(2))).next(), None);
 729 }
 730
 731 #[test]
 732 #[should_panic]
 733 fn test_range_equal_excluded() {
 734     let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
 735     map.range((Excluded(2), Excluded(2)));
 736 }
 737
 738 #[test]
 739 #[should_panic]
 740 fn test_range_backwards_1() {
 741     let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
 742     map.range((Included(3), Included(2)));
 743 }
 744
 745 #[test]
 746 #[should_panic]
 747 fn test_range_backwards_2() {
 748     let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
 749     map.range((Included(3), Excluded(2)));
 750 }
 751
 752 #[test]
 753 #[should_panic]
 754 fn test_range_backwards_3() {
 755     let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
 756     map.range((Excluded(3), Included(2)));
 757 }
 758
 759 #[test]
 760 #[should_panic]
 761 fn test_range_backwards_4() {
 762     let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
 763     map.range((Excluded(3), Excluded(2)));
 764 }
 765
 766 #[test]
 767 #[should_panic]
 768 fn test_range_backwards_5() {
 769     let mut map = BTreeMap::new();
 770     map.insert(Cyclic3::B, ());
 771     // Lacking static_assert, call `range` conditionally, to emphasise that
 772     // we cause a different panic than `test_range_backwards_1` does.
 773     // A more refined `should_panic` would be welcome.
 774     if Cyclic3::C < Cyclic3::A {
 775         map.range(Cyclic3::C..=Cyclic3::A);
 776     }
 777 }
 778
 779 #[test]
 780 fn test_range_1000() {
 781     // Miri is too slow
 782     let size = if cfg!(miri) { MIN_INSERTS_HEIGHT_2 as u32 } else { 1000 };
 783     let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 784
 785     fn test(map: &BTreeMap<u32, u32>, size: u32, min: Bound<&u32>, max: Bound<&u32>) {
 786         let mut kvs = map.range((min, max)).map(|(&k, &v)| (k, v));
 787         let mut pairs = (0..size).map(|i| (i, i));
 788
 789         for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
 790             assert_eq!(kv, pair);
 791         }
 792         assert_eq!(kvs.next(), None);
 793         assert_eq!(pairs.next(), None);
 794     }
 795     test(&map, size, Included(&0), Excluded(&size));
 796     test(&map, size, Unbounded, Excluded(&size));
 797     test(&map, size, Included(&0), Included(&(size - 1)));
 798     test(&map, size, Unbounded, Included(&(size - 1)));
 799     test(&map, size, Included(&0), Unbounded);
 800     test(&map, size, Unbounded, Unbounded);
 801 }
 802
 803 #[test]
 804 fn test_range_borrowed_key() {
 805     let mut map = BTreeMap::new();
 806     map.insert("aardvark".to_string(), 1);
 807     map.insert("baboon".to_string(), 2);
 808     map.insert("coyote".to_string(), 3);
 809     map.insert("dingo".to_string(), 4);
 810     // NOTE: would like to use simply "b".."d" here...
 811     let mut iter = map.range::<str, _>((Included("b"), Excluded("d")));
 812     assert_eq!(iter.next(), Some((&"baboon".to_string(), &2)));
 813     assert_eq!(iter.next(), Some((&"coyote".to_string(), &3)));
 814     assert_eq!(iter.next(), None);
 815 }
 816
 817 #[test]
 818 fn test_range() {
 819     let size = 200;
 820     // Miri is too slow
 821     let step = if cfg!(miri) { 66 } else { 1 };
 822     let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 823
 824     for i in (0..size).step_by(step) {
 825         for j in (i..size).step_by(step) {
 826             let mut kvs = map.range((Included(&i), Included(&j))).map(|(&k, &v)| (k, v));
 827             let mut pairs = (i..=j).map(|i| (i, i));
 828
 829             for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
 830                 assert_eq!(kv, pair);
 831             }
 832             assert_eq!(kvs.next(), None);
 833             assert_eq!(pairs.next(), None);
 834         }
 835     }
 836 }
 837
 838 #[test]
 839 fn test_range_mut() {
 840     let size = 200;
 841     // Miri is too slow
 842     let step = if cfg!(miri) { 66 } else { 1 };
 843     let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 844
 845     for i in (0..size).step_by(step) {
 846         for j in (i..size).step_by(step) {
 847             let mut kvs = map.range_mut((Included(&i), Included(&j))).map(|(&k, &mut v)| (k, v));
 848             let mut pairs = (i..=j).map(|i| (i, i));
 849
 850             for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
 851                 assert_eq!(kv, pair);
 852             }
 853             assert_eq!(kvs.next(), None);
 854             assert_eq!(pairs.next(), None);
 855         }
 856     }
 857     map.check();
 858 }
 859
 860 #[test]
 861 fn test_retain() {
 862     let mut map: BTreeMap<i32, i32> = (0..100).map(|x| (x, x * 10)).collect();
 863
 864     map.retain(|&k, _| k % 2 == 0);
 865     assert_eq!(map.len(), 50);
 866     assert_eq!(map[&2], 20);
 867     assert_eq!(map[&4], 40);
 868     assert_eq!(map[&6], 60);
 869 }
 870
 871 mod test_drain_filter {
 872     use super::*;
 873
 874     #[test]
 875     fn empty() {
 876         let mut map: BTreeMap<i32, i32> = BTreeMap::new();
 877         map.drain_filter(|_, _| unreachable!("there's nothing to decide on"));
 878         assert!(map.is_empty());
 879         map.check();
 880     }
 881
 882     #[test]
 883     fn consumed_keeping_all() {
 884         let pairs = (0..3).map(|i| (i, i));
 885         let mut map: BTreeMap<_, _> = pairs.collect();
 886         assert!(map.drain_filter(|_, _| false).eq(iter::empty()));
 887         map.check();
 888     }
 889
 890     #[test]
 891     fn consumed_removing_all() {
 892         let pairs = (0..3).map(|i| (i, i));
 893         let mut map: BTreeMap<_, _> = pairs.clone().collect();
 894         assert!(map.drain_filter(|_, _| true).eq(pairs));
 895         assert!(map.is_empty());
 896         map.check();
 897     }
 898
 899     #[test]
 900     fn dropped_removing_all() {
 901         let pairs = (0..3).map(|i| (i, i));
 902         let mut map: BTreeMap<_, _> = pairs.collect();
 903         map.drain_filter(|_, _| true);
 904         assert!(map.is_empty());
 905         map.check();
 906     }
 907
 908     #[test]
 909     fn mutating_and_keeping() {
 910         let pairs = (0..3).map(|i| (i, i));
 911         let mut map: BTreeMap<_, _> = pairs.collect();
 912         assert!(
 913             map.drain_filter(|_, v| {
 914                 *v += 6;
 915                 false
 916             })
 917             .eq(iter::empty())
 918         );
 919         assert!(map.keys().copied().eq(0..3));
 920         assert!(map.values().copied().eq(6..9));
 921         map.check();
 922     }
 923
 924     #[test]
 925     fn mutating_and_removing() {
 926         let pairs = (0..3).map(|i| (i, i));
 927         let mut map: BTreeMap<_, _> = pairs.collect();
 928         assert!(
 929             map.drain_filter(|_, v| {
 930                 *v += 6;
 931                 true
 932             })
 933             .eq((0..3).map(|i| (i, i + 6)))
 934         );
 935         assert!(map.is_empty());
 936         map.check();
 937     }
 938
 939     #[test]
 940     fn underfull_keeping_all() {
 941         let pairs = (0..3).map(|i| (i, i));
 942         let mut map: BTreeMap<_, _> = pairs.collect();
 943         map.drain_filter(|_, _| false);
 944         assert!(map.keys().copied().eq(0..3));
 945         map.check();
 946     }
 947
 948     #[test]
 949     fn underfull_removing_one() {
 950         let pairs = (0..3).map(|i| (i, i));
 951         for doomed in 0..3 {
 952             let mut map: BTreeMap<_, _> = pairs.clone().collect();
 953             map.drain_filter(|i, _| *i == doomed);
 954             assert_eq!(map.len(), 2);
 955             map.check();
 956         }
 957     }
 958
 959     #[test]
 960     fn underfull_keeping_one() {
 961         let pairs = (0..3).map(|i| (i, i));
 962         for sacred in 0..3 {
 963             let mut map: BTreeMap<_, _> = pairs.clone().collect();
 964             map.drain_filter(|i, _| *i != sacred);
 965             assert!(map.keys().copied().eq(sacred..=sacred));
 966             map.check();
 967         }
 968     }
 969
 970     #[test]
 971     fn underfull_removing_all() {
 972         let pairs = (0..3).map(|i| (i, i));
 973         let mut map: BTreeMap<_, _> = pairs.collect();
 974         map.drain_filter(|_, _| true);
 975         assert!(map.is_empty());
 976         map.check();
 977     }
 978
 979     #[test]
 980     fn height_0_keeping_all() {
 981         let pairs = (0..NODE_CAPACITY).map(|i| (i, i));
 982         let mut map: BTreeMap<_, _> = pairs.collect();
 983         map.drain_filter(|_, _| false);
 984         assert!(map.keys().copied().eq(0..NODE_CAPACITY));
 985         map.check();
 986     }
 987
 988     #[test]
 989     fn height_0_removing_one() {
 990         let pairs = (0..NODE_CAPACITY).map(|i| (i, i));
 991         for doomed in 0..NODE_CAPACITY {
 992             let mut map: BTreeMap<_, _> = pairs.clone().collect();
 993             map.drain_filter(|i, _| *i == doomed);
 994             assert_eq!(map.len(), NODE_CAPACITY - 1);
 995             map.check();
 996         }
 997     }
 998
 999     #[test]
1000     fn height_0_keeping_one() {
1001         let pairs = (0..NODE_CAPACITY).map(|i| (i, i));
1002         for sacred in 0..NODE_CAPACITY {
1003             let mut map: BTreeMap<_, _> = pairs.clone().collect();
1004             map.drain_filter(|i, _| *i != sacred);
1005             assert!(map.keys().copied().eq(sacred..=sacred));
1006             map.check();
1007         }
1008     }
1009
1010     #[test]
1011     fn height_0_removing_all() {
1012         let pairs = (0..NODE_CAPACITY).map(|i| (i, i));
1013         let mut map: BTreeMap<_, _> = pairs.collect();
1014         map.drain_filter(|_, _| true);
1015         assert!(map.is_empty());
1016         map.check();
1017     }
1018
1019     #[test]
1020     fn height_0_keeping_half() {
1021         let mut map: BTreeMap<_, _> = (0..16).map(|i| (i, i)).collect();
1022         assert_eq!(map.drain_filter(|i, _| *i % 2 == 0).count(), 8);
1023         assert_eq!(map.len(), 8);
1024         map.check();
1025     }
1026
1027     #[test]
1028     fn height_1_removing_all() {
1029         let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i));
1030         let mut map: BTreeMap<_, _> = pairs.collect();
1031         map.drain_filter(|_, _| true);
1032         assert!(map.is_empty());
1033         map.check();
1034     }
1035
1036     #[test]
1037     fn height_1_removing_one() {
1038         let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i));
1039         for doomed in 0..MIN_INSERTS_HEIGHT_1 {
1040             let mut map: BTreeMap<_, _> = pairs.clone().collect();
1041             map.drain_filter(|i, _| *i == doomed);
1042             assert_eq!(map.len(), MIN_INSERTS_HEIGHT_1 - 1);
1043             map.check();
1044         }
1045     }
1046
1047     #[test]
1048     fn height_1_keeping_one() {
1049         let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i));
1050         for sacred in 0..MIN_INSERTS_HEIGHT_1 {
1051             let mut map: BTreeMap<_, _> = pairs.clone().collect();
1052             map.drain_filter(|i, _| *i != sacred);
1053             assert!(map.keys().copied().eq(sacred..=sacred));
1054             map.check();
1055         }
1056     }
1057
1058     #[test]
1059     fn height_2_removing_one() {
1060         let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
1061         for doomed in (0..MIN_INSERTS_HEIGHT_2).step_by(12) {
1062             let mut map: BTreeMap<_, _> = pairs.clone().collect();
1063             map.drain_filter(|i, _| *i == doomed);
1064             assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2 - 1);
1065             map.check();
1066         }
1067     }
1068
1069     #[test]
1070     fn height_2_keeping_one() {
1071         let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
1072         for sacred in (0..MIN_INSERTS_HEIGHT_2).step_by(12) {
1073             let mut map: BTreeMap<_, _> = pairs.clone().collect();
1074             map.drain_filter(|i, _| *i != sacred);
1075             assert!(map.keys().copied().eq(sacred..=sacred));
1076             map.check();
1077         }
1078     }
1079
1080     #[test]
1081     fn height_2_removing_all() {
1082         let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
1083         let mut map: BTreeMap<_, _> = pairs.collect();
1084         map.drain_filter(|_, _| true);
1085         assert!(map.is_empty());
1086         map.check();
1087     }
1088
1089     #[test]
1090     fn drop_panic_leak() {
1091         static PREDS: AtomicUsize = AtomicUsize::new(0);
1092         static DROPS: AtomicUsize = AtomicUsize::new(0);
1093
1094         struct D;
1095         impl Drop for D {
1096             fn drop(&mut self) {
1097                 if DROPS.fetch_add(1, Ordering::SeqCst) == 1 {
1098                     panic!("panic in `drop`");
1099                 }
1100             }
1101         }
1102
1103         // Keys are multiples of 4, so that each key is counted by a hexadecimal digit.
1104         let mut map = (0..3).map(|i| (i * 4, D)).collect::<BTreeMap<_, _>>();
1105
1106         catch_unwind(move || {
1107             drop(map.drain_filter(|i, _| {
1108                 PREDS.fetch_add(1usize << i, Ordering::SeqCst);
1109                 true
1110             }))
1111         })
1112         .unwrap_err();
1113
1114         assert_eq!(PREDS.load(Ordering::SeqCst), 0x011);
1115         assert_eq!(DROPS.load(Ordering::SeqCst), 3);
1116     }
1117
1118     #[test]
1119     fn pred_panic_leak() {
1120         static PREDS: AtomicUsize = AtomicUsize::new(0);
1121         static DROPS: AtomicUsize = AtomicUsize::new(0);
1122
1123         struct D;
1124         impl Drop for D {
1125             fn drop(&mut self) {
1126                 DROPS.fetch_add(1, Ordering::SeqCst);
1127             }
1128         }
1129
1130         // Keys are multiples of 4, so that each key is counted by a hexadecimal digit.
1131         let mut map = (0..3).map(|i| (i * 4, D)).collect::<BTreeMap<_, _>>();
1132
1133         catch_unwind(AssertUnwindSafe(|| {
1134             drop(map.drain_filter(|i, _| {
1135                 PREDS.fetch_add(1usize << i, Ordering::SeqCst);
1136                 match i {
1137                     0 => true,
1138                     _ => panic!(),
1139                 }
1140             }))
1141         }))
1142         .unwrap_err();
1143
1144         assert_eq!(PREDS.load(Ordering::SeqCst), 0x011);
1145         assert_eq!(DROPS.load(Ordering::SeqCst), 1);
1146         assert_eq!(map.len(), 2);
1147         assert_eq!(map.first_entry().unwrap().key(), &4);
1148         assert_eq!(map.last_entry().unwrap().key(), &8);
1149         map.check();
1150     }
1151
1152     // Same as above, but attempt to use the iterator again after the panic in the predicate
1153     #[test]
1154     fn pred_panic_reuse() {
1155         static PREDS: AtomicUsize = AtomicUsize::new(0);
1156         static DROPS: AtomicUsize = AtomicUsize::new(0);
1157
1158         struct D;
1159         impl Drop for D {
1160             fn drop(&mut self) {
1161                 DROPS.fetch_add(1, Ordering::SeqCst);
1162             }
1163         }
1164
1165         // Keys are multiples of 4, so that each key is counted by a hexadecimal digit.
1166         let mut map = (0..3).map(|i| (i * 4, D)).collect::<BTreeMap<_, _>>();
1167
1168         {
1169             let mut it = map.drain_filter(|i, _| {
1170                 PREDS.fetch_add(1usize << i, Ordering::SeqCst);
1171                 match i {
1172                     0 => true,
1173                     _ => panic!(),
1174                 }
1175             });
1176             catch_unwind(AssertUnwindSafe(|| while it.next().is_some() {})).unwrap_err();
1177             // Iterator behaviour after a panic is explicitly unspecified,
1178             // so this is just the current implementation:
1179             let result = catch_unwind(AssertUnwindSafe(|| it.next()));
1180             assert!(matches!(result, Ok(None)));
1181         }
1182
1183         assert_eq!(PREDS.load(Ordering::SeqCst), 0x011);
1184         assert_eq!(DROPS.load(Ordering::SeqCst), 1);
1185         assert_eq!(map.len(), 2);
1186         assert_eq!(map.first_entry().unwrap().key(), &4);
1187         assert_eq!(map.last_entry().unwrap().key(), &8);
1188         map.check();
1189     }
1190 }
1191
1192 #[test]
1193 fn test_borrow() {
1194     // make sure these compile -- using the Borrow trait
1195     {
1196         let mut map = BTreeMap::new();
1197         map.insert("0".to_string(), 1);
1198         assert_eq!(map["0"], 1);
1199     }
1200
1201     {
1202         let mut map = BTreeMap::new();
1203         map.insert(Box::new(0), 1);
1204         assert_eq!(map[&0], 1);
1205     }
1206
1207     {
1208         let mut map = BTreeMap::new();
1209         map.insert(Box::new([0, 1]) as Box<[i32]>, 1);
1210         assert_eq!(map[&[0, 1][..]], 1);
1211     }
1212
1213     {
1214         let mut map = BTreeMap::new();
1215         map.insert(Rc::new(0), 1);
1216         assert_eq!(map[&0], 1);
1217     }
1218 }
1219
1220 #[test]
1221 fn test_entry() {
1222     let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
1223
1224     let mut map: BTreeMap<_, _> = xs.iter().cloned().collect();
1225
1226     // Existing key (insert)
1227     match map.entry(1) {
1228         Vacant(_) => unreachable!(),
1229         Occupied(mut view) => {
1230             assert_eq!(view.get(), &10);
1231             assert_eq!(view.insert(100), 10);
1232         }
1233     }
1234     assert_eq!(map.get(&1).unwrap(), &100);
1235     assert_eq!(map.len(), 6);
1236
1237     // Existing key (update)
1238     match map.entry(2) {
1239         Vacant(_) => unreachable!(),
1240         Occupied(mut view) => {
1241             let v = view.get_mut();
1242             *v *= 10;
1243         }
1244     }
1245     assert_eq!(map.get(&2).unwrap(), &200);
1246     assert_eq!(map.len(), 6);
1247     map.check();
1248
1249     // Existing key (take)
1250     match map.entry(3) {
1251         Vacant(_) => unreachable!(),
1252         Occupied(view) => {
1253             assert_eq!(view.remove(), 30);
1254         }
1255     }
1256     assert_eq!(map.get(&3), None);
1257     assert_eq!(map.len(), 5);
1258     map.check();
1259
1260     // Inexistent key (insert)
1261     match map.entry(10) {
1262         Occupied(_) => unreachable!(),
1263         Vacant(view) => {
1264             assert_eq!(*view.insert(1000), 1000);
1265         }
1266     }
1267     assert_eq!(map.get(&10).unwrap(), &1000);
1268     assert_eq!(map.len(), 6);
1269     map.check();
1270 }
1271
1272 #[test]
1273 fn test_extend_ref() {
1274     let mut a = BTreeMap::new();
1275     a.insert(1, "one");
1276     let mut b = BTreeMap::new();
1277     b.insert(2, "two");
1278     b.insert(3, "three");
1279
1280     a.extend(&b);
1281
1282     assert_eq!(a.len(), 3);
1283     assert_eq!(a[&1], "one");
1284     assert_eq!(a[&2], "two");
1285     assert_eq!(a[&3], "three");
1286     a.check();
1287 }
1288
1289 #[test]
1290 fn test_zst() {
1291     let mut m = BTreeMap::new();
1292     assert_eq!(m.len(), 0);
1293
1294     assert_eq!(m.insert((), ()), None);
1295     assert_eq!(m.len(), 1);
1296
1297     assert_eq!(m.insert((), ()), Some(()));
1298     assert_eq!(m.len(), 1);
1299     assert_eq!(m.iter().count(), 1);
1300
1301     m.clear();
1302     assert_eq!(m.len(), 0);
1303
1304     for _ in 0..100 {
1305         m.insert((), ());
1306     }
1307
1308     assert_eq!(m.len(), 1);
1309     assert_eq!(m.iter().count(), 1);
1310     m.check();
1311 }
1312
1313 // This test's only purpose is to ensure that zero-sized keys with nonsensical orderings
1314 // do not cause segfaults when used with zero-sized values. All other map behavior is
1315 // undefined.
1316 #[test]
1317 fn test_bad_zst() {
1318     use std::cmp::Ordering;
1319
1320     #[derive(Clone, Copy, Debug)]
1321     struct Bad;
1322
1323     impl PartialEq for Bad {
1324         fn eq(&self, _: &Self) -> bool {
1325             false
1326         }
1327     }
1328
1329     impl Eq for Bad {}
1330
1331     impl PartialOrd for Bad {
1332         fn partial_cmp(&self, _: &Self) -> Option<Ordering> {
1333             Some(Ordering::Less)
1334         }
1335     }
1336
1337     impl Ord for Bad {
1338         fn cmp(&self, _: &Self) -> Ordering {
1339             Ordering::Less
1340         }
1341     }
1342
1343     let mut m = BTreeMap::new();
1344
1345     for _ in 0..100 {
1346         m.insert(Bad, Bad);
1347     }
1348     m.check();
1349 }
1350
1351 #[test]
1352 fn test_clone() {
1353     let mut map = BTreeMap::new();
1354     let size = MIN_INSERTS_HEIGHT_1;
1355     assert_eq!(map.len(), 0);
1356
1357     for i in 0..size {
1358         assert_eq!(map.insert(i, 10 * i), None);
1359         assert_eq!(map.len(), i + 1);
1360         map.check();
1361         assert_eq!(map, map.clone());
1362     }
1363
1364     for i in 0..size {
1365         assert_eq!(map.insert(i, 100 * i), Some(10 * i));
1366         assert_eq!(map.len(), size);
1367         map.check();
1368         assert_eq!(map, map.clone());
1369     }
1370
1371     for i in 0..size / 2 {
1372         assert_eq!(map.remove(&(i * 2)), Some(i * 200));
1373         assert_eq!(map.len(), size - i - 1);
1374         map.check();
1375         assert_eq!(map, map.clone());
1376     }
1377
1378     for i in 0..size / 2 {
1379         assert_eq!(map.remove(&(2 * i)), None);
1380         assert_eq!(map.remove(&(2 * i + 1)), Some(i * 200 + 100));
1381         assert_eq!(map.len(), size / 2 - i - 1);
1382         map.check();
1383         assert_eq!(map, map.clone());
1384     }
1385
1386     // Test a tree with 2 semi-full levels and a tree with 3 levels.
1387     map = (1..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)).collect();
1388     assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2 - 1);
1389     assert_eq!(map, map.clone());
1390     map.insert(0, 0);
1391     assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2);
1392     assert_eq!(map, map.clone());
1393     map.check();
1394 }
1395
1396 #[test]
1397 fn test_clone_from() {
1398     let mut map1 = BTreeMap::new();
1399     let max_size = MIN_INSERTS_HEIGHT_1;
1400
1401     // Range to max_size inclusive, because i is the size of map1 being tested.
1402     for i in 0..=max_size {
1403         let mut map2 = BTreeMap::new();
1404         for j in 0..i {
1405             let mut map1_copy = map2.clone();
1406             map1_copy.clone_from(&map1); // small cloned from large
1407             assert_eq!(map1_copy, map1);
1408             let mut map2_copy = map1.clone();
1409             map2_copy.clone_from(&map2); // large cloned from small
1410             assert_eq!(map2_copy, map2);
1411             map2.insert(100 * j + 1, 2 * j + 1);
1412         }
1413         map2.clone_from(&map1); // same length
1414         map2.check();
1415         assert_eq!(map2, map1);
1416         map1.insert(i, 10 * i);
1417         map1.check();
1418     }
1419 }
1420
1421 #[allow(dead_code)]
1422 fn test_variance() {
1423     fn map_key<'new>(v: BTreeMap<&'static str, ()>) -> BTreeMap<&'new str, ()> {
1424         v
1425     }
1426     fn map_val<'new>(v: BTreeMap<(), &'static str>) -> BTreeMap<(), &'new str> {
1427         v
1428     }
1429
1430     fn iter_key<'a, 'new>(v: Iter<'a, &'static str, ()>) -> Iter<'a, &'new str, ()> {
1431         v
1432     }
1433     fn iter_val<'a, 'new>(v: Iter<'a, (), &'static str>) -> Iter<'a, (), &'new str> {
1434         v
1435     }
1436
1437     fn into_iter_key<'new>(v: IntoIter<&'static str, ()>) -> IntoIter<&'new str, ()> {
1438         v
1439     }
1440     fn into_iter_val<'new>(v: IntoIter<(), &'static str>) -> IntoIter<(), &'new str> {
1441         v
1442     }
1443
1444     fn into_keys_key<'new>(v: IntoKeys<&'static str, ()>) -> IntoKeys<&'new str, ()> {
1445         v
1446     }
1447     fn into_keys_val<'new>(v: IntoKeys<(), &'static str>) -> IntoKeys<(), &'new str> {
1448         v
1449     }
1450
1451     fn into_values_key<'new>(v: IntoValues<&'static str, ()>) -> IntoValues<&'new str, ()> {
1452         v
1453     }
1454     fn into_values_val<'new>(v: IntoValues<(), &'static str>) -> IntoValues<(), &'new str> {
1455         v
1456     }
1457
1458     fn range_key<'a, 'new>(v: Range<'a, &'static str, ()>) -> Range<'a, &'new str, ()> {
1459         v
1460     }
1461     fn range_val<'a, 'new>(v: Range<'a, (), &'static str>) -> Range<'a, (), &'new str> {
1462         v
1463     }
1464
1465     fn keys_key<'a, 'new>(v: Keys<'a, &'static str, ()>) -> Keys<'a, &'new str, ()> {
1466         v
1467     }
1468     fn keys_val<'a, 'new>(v: Keys<'a, (), &'static str>) -> Keys<'a, (), &'new str> {
1469         v
1470     }
1471
1472     fn values_key<'a, 'new>(v: Values<'a, &'static str, ()>) -> Values<'a, &'new str, ()> {
1473         v
1474     }
1475     fn values_val<'a, 'new>(v: Values<'a, (), &'static str>) -> Values<'a, (), &'new str> {
1476         v
1477     }
1478 }
1479
1480 #[allow(dead_code)]
1481 fn test_sync() {
1482     fn map<T: Sync>(v: &BTreeMap<T, T>) -> impl Sync + '_ {
1483         v
1484     }
1485
1486     fn into_iter<T: Sync>(v: BTreeMap<T, T>) -> impl Sync {
1487         v.into_iter()
1488     }
1489
1490     fn into_keys<T: Sync + Ord>(v: BTreeMap<T, T>) -> impl Sync {
1491         v.into_keys()
1492     }
1493
1494     fn into_values<T: Sync + Ord>(v: BTreeMap<T, T>) -> impl Sync {
1495         v.into_values()
1496     }
1497
1498     fn drain_filter<T: Sync + Ord>(v: &mut BTreeMap<T, T>) -> impl Sync + '_ {
1499         v.drain_filter(|_, _| false)
1500     }
1501
1502     fn iter<T: Sync>(v: &BTreeMap<T, T>) -> impl Sync + '_ {
1503         v.iter()
1504     }
1505
1506     fn iter_mut<T: Sync>(v: &mut BTreeMap<T, T>) -> impl Sync + '_ {
1507         v.iter_mut()
1508     }
1509
1510     fn keys<T: Sync>(v: &BTreeMap<T, T>) -> impl Sync + '_ {
1511         v.keys()
1512     }
1513
1514     fn values<T: Sync>(v: &BTreeMap<T, T>) -> impl Sync + '_ {
1515         v.values()
1516     }
1517
1518     fn values_mut<T: Sync>(v: &mut BTreeMap<T, T>) -> impl Sync + '_ {
1519         v.values_mut()
1520     }
1521
1522     fn range<T: Sync + Ord>(v: &BTreeMap<T, T>) -> impl Sync + '_ {
1523         v.range(..)
1524     }
1525
1526     fn range_mut<T: Sync + Ord>(v: &mut BTreeMap<T, T>) -> impl Sync + '_ {
1527         v.range_mut(..)
1528     }
1529
1530     fn entry<T: Sync + Ord + Default>(v: &mut BTreeMap<T, T>) -> impl Sync + '_ {
1531         v.entry(Default::default())
1532     }
1533
1534     fn occupied_entry<T: Sync + Ord + Default>(v: &mut BTreeMap<T, T>) -> impl Sync + '_ {
1535         match v.entry(Default::default()) {
1536             Occupied(entry) => entry,
1537             _ => unreachable!(),
1538         }
1539     }
1540
1541     fn vacant_entry<T: Sync + Ord + Default>(v: &mut BTreeMap<T, T>) -> impl Sync + '_ {
1542         match v.entry(Default::default()) {
1543             Vacant(entry) => entry,
1544             _ => unreachable!(),
1545         }
1546     }
1547 }
1548
1549 #[allow(dead_code)]
1550 fn test_send() {
1551     fn map<T: Send>(v: BTreeMap<T, T>) -> impl Send {
1552         v
1553     }
1554
1555     fn into_iter<T: Send>(v: BTreeMap<T, T>) -> impl Send {
1556         v.into_iter()
1557     }
1558
1559     fn into_keys<T: Send + Ord>(v: BTreeMap<T, T>) -> impl Send {
1560         v.into_keys()
1561     }
1562
1563     fn into_values<T: Send + Ord>(v: BTreeMap<T, T>) -> impl Send {
1564         v.into_values()
1565     }
1566
1567     fn drain_filter<T: Send + Ord>(v: &mut BTreeMap<T, T>) -> impl Send + '_ {
1568         v.drain_filter(|_, _| false)
1569     }
1570
1571     fn iter<T: Send + Sync>(v: &BTreeMap<T, T>) -> impl Send + '_ {
1572         v.iter()
1573     }
1574
1575     fn iter_mut<T: Send>(v: &mut BTreeMap<T, T>) -> impl Send + '_ {
1576         v.iter_mut()
1577     }
1578
1579     fn keys<T: Send + Sync>(v: &BTreeMap<T, T>) -> impl Send + '_ {
1580         v.keys()
1581     }
1582
1583     fn values<T: Send + Sync>(v: &BTreeMap<T, T>) -> impl Send + '_ {
1584         v.values()
1585     }
1586
1587     fn values_mut<T: Send>(v: &mut BTreeMap<T, T>) -> impl Send + '_ {
1588         v.values_mut()
1589     }
1590
1591     fn range<T: Send + Sync + Ord>(v: &BTreeMap<T, T>) -> impl Send + '_ {
1592         v.range(..)
1593     }
1594
1595     fn range_mut<T: Send + Ord>(v: &mut BTreeMap<T, T>) -> impl Send + '_ {
1596         v.range_mut(..)
1597     }
1598
1599     fn entry<T: Send + Ord + Default>(v: &mut BTreeMap<T, T>) -> impl Send + '_ {
1600         v.entry(Default::default())
1601     }
1602
1603     fn occupied_entry<T: Send + Ord + Default>(v: &mut BTreeMap<T, T>) -> impl Send + '_ {
1604         match v.entry(Default::default()) {
1605             Occupied(entry) => entry,
1606             _ => unreachable!(),
1607         }
1608     }
1609
1610     fn vacant_entry<T: Send + Ord + Default>(v: &mut BTreeMap<T, T>) -> impl Send + '_ {
1611         match v.entry(Default::default()) {
1612             Vacant(entry) => entry,
1613             _ => unreachable!(),
1614         }
1615     }
1616 }
1617
1618 #[allow(dead_code)]
1619 fn test_const() {
1620     const MAP: &'static BTreeMap<(), ()> = &BTreeMap::new();
1621     const LEN: usize = MAP.len();
1622     const IS_EMPTY: bool = MAP.is_empty();
1623 }
1624
1625 #[test]
1626 fn test_occupied_entry_key() {
1627     let mut a = BTreeMap::new();
1628     let key = "hello there";
1629     let value = "value goes here";
1630     assert!(a.is_empty());
1631     a.insert(key.clone(), value.clone());
1632     assert_eq!(a.len(), 1);
1633     assert_eq!(a[key], value);
1634
1635     match a.entry(key.clone()) {
1636         Vacant(_) => panic!(),
1637         Occupied(e) => assert_eq!(key, *e.key()),
1638     }
1639     assert_eq!(a.len(), 1);
1640     assert_eq!(a[key], value);
1641     a.check();
1642 }
1643
1644 #[test]
1645 fn test_vacant_entry_key() {
1646     let mut a = BTreeMap::new();
1647     let key = "hello there";
1648     let value = "value goes here";
1649
1650     assert!(a.is_empty());
1651     match a.entry(key.clone()) {
1652         Occupied(_) => panic!(),
1653         Vacant(e) => {
1654             assert_eq!(key, *e.key());
1655             e.insert(value.clone());
1656         }
1657     }
1658     assert_eq!(a.len(), 1);
1659     assert_eq!(a[key], value);
1660     a.check();
1661 }
1662
1663 #[test]
1664 fn test_first_last_entry() {
1665     let mut a = BTreeMap::new();
1666     assert!(a.first_entry().is_none());
1667     assert!(a.last_entry().is_none());
1668     a.insert(1, 42);
1669     assert_eq!(a.first_entry().unwrap().key(), &1);
1670     assert_eq!(a.last_entry().unwrap().key(), &1);
1671     a.insert(2, 24);
1672     assert_eq!(a.first_entry().unwrap().key(), &1);
1673     assert_eq!(a.last_entry().unwrap().key(), &2);
1674     a.insert(0, 6);
1675     assert_eq!(a.first_entry().unwrap().key(), &0);
1676     assert_eq!(a.last_entry().unwrap().key(), &2);
1677     let (k1, v1) = a.first_entry().unwrap().remove_entry();
1678     assert_eq!(k1, 0);
1679     assert_eq!(v1, 6);
1680     let (k2, v2) = a.last_entry().unwrap().remove_entry();
1681     assert_eq!(k2, 2);
1682     assert_eq!(v2, 24);
1683     assert_eq!(a.first_entry().unwrap().key(), &1);
1684     assert_eq!(a.last_entry().unwrap().key(), &1);
1685     a.check();
1686 }
1687
1688 #[test]
1689 fn test_insert_into_full_left() {
1690     let mut map: BTreeMap<_, _> = (0..NODE_CAPACITY).map(|i| (i * 2, ())).collect();
1691     assert!(map.insert(NODE_CAPACITY, ()).is_none());
1692     map.check();
1693 }
1694
1695 #[test]
1696 fn test_insert_into_full_right() {
1697     let mut map: BTreeMap<_, _> = (0..NODE_CAPACITY).map(|i| (i * 2, ())).collect();
1698     assert!(map.insert(NODE_CAPACITY + 2, ()).is_none());
1699     map.check();
1700 }
1701
1702 macro_rules! create_append_test {
1703     ($name:ident, $len:expr) => {
1704         #[test]
1705         fn $name() {
1706             let mut a = BTreeMap::new();
1707             for i in 0..8 {
1708                 a.insert(i, i);
1709             }
1710
1711             let mut b = BTreeMap::new();
1712             for i in 5..$len {
1713                 b.insert(i, 2 * i);
1714             }
1715
1716             a.append(&mut b);
1717
1718             assert_eq!(a.len(), $len);
1719             assert_eq!(b.len(), 0);
1720
1721             for i in 0..$len {
1722                 if i < 5 {
1723                     assert_eq!(a[&i], i);
1724                 } else {
1725                     assert_eq!(a[&i], 2 * i);
1726                 }
1727             }
1728
1729             a.check();
1730             assert_eq!(a.remove(&($len - 1)), Some(2 * ($len - 1)));
1731             assert_eq!(a.insert($len - 1, 20), None);
1732             a.check();
1733         }
1734     };
1735 }
1736
1737 // These are mostly for testing the algorithm that "fixes" the right edge after insertion.
1738 // Single node.
1739 create_append_test!(test_append_9, 9);
1740 // Two leafs that don't need fixing.
1741 create_append_test!(test_append_17, 17);
1742 // Two leafs where the second one ends up underfull and needs stealing at the end.
1743 create_append_test!(test_append_14, 14);
1744 // Two leafs where the second one ends up empty because the insertion finished at the root.
1745 create_append_test!(test_append_12, 12);
1746 // Three levels; insertion finished at the root.
1747 create_append_test!(test_append_144, 144);
1748 // Three levels; insertion finished at leaf while there is an empty node on the second level.
1749 create_append_test!(test_append_145, 145);
1750 // Tests for several randomly chosen sizes.
1751 create_append_test!(test_append_170, 170);
1752 create_append_test!(test_append_181, 181);
1753 #[cfg(not(miri))] // Miri is too slow
1754 create_append_test!(test_append_239, 239);
1755 #[cfg(not(miri))] // Miri is too slow
1756 create_append_test!(test_append_1700, 1700);
1757
1758 #[test]
1759 fn test_append_drop_leak() {
1760     static DROPS: AtomicUsize = AtomicUsize::new(0);
1761
1762     struct D;
1763
1764     impl Drop for D {
1765         fn drop(&mut self) {
1766             if DROPS.fetch_add(1, Ordering::SeqCst) == 0 {
1767                 panic!("panic in `drop`");
1768             }
1769         }
1770     }
1771
1772     let mut left = BTreeMap::new();
1773     let mut right = BTreeMap::new();
1774     left.insert(0, D);
1775     left.insert(1, D); // first to be dropped during append
1776     left.insert(2, D);
1777     right.insert(1, D);
1778     right.insert(2, D);
1779
1780     catch_unwind(move || left.append(&mut right)).unwrap_err();
1781
1782     assert_eq!(DROPS.load(Ordering::SeqCst), 4); // Rust issue #47949 ate one little piggy
1783 }
1784
1785 #[test]
1786 fn test_append_ord_chaos() {
1787     let mut map1 = BTreeMap::new();
1788     map1.insert(Cyclic3::A, ());
1789     map1.insert(Cyclic3::B, ());
1790     let mut map2 = BTreeMap::new();
1791     map2.insert(Cyclic3::A, ());
1792     map2.insert(Cyclic3::B, ());
1793     map2.insert(Cyclic3::C, ()); // lands first, before A
1794     map2.insert(Cyclic3::B, ()); // lands first, before C
1795     map1.check();
1796     map2.check(); // keys are not unique but still strictly ascending
1797     assert_eq!(map1.len(), 2);
1798     assert_eq!(map2.len(), 4);
1799     map1.append(&mut map2);
1800     assert_eq!(map1.len(), 5);
1801     assert_eq!(map2.len(), 0);
1802     map1.check();
1803     map2.check();
1804 }
1805
1806 fn rand_data(len: usize) -> Vec<(u32, u32)> {
1807     assert!(len * 2 <= 70029); // from that point on numbers repeat
1808     let mut rng = DeterministicRng::new();
1809     Vec::from_iter((0..len).map(|_| (rng.next(), rng.next())))
1810 }
1811
1812 #[test]
1813 fn test_split_off_empty_right() {
1814     let mut data = rand_data(173);
1815
1816     let mut map = BTreeMap::from_iter(data.clone());
1817     let right = map.split_off(&(data.iter().max().unwrap().0 + 1));
1818     map.check();
1819     right.check();
1820
1821     data.sort();
1822     assert!(map.into_iter().eq(data));
1823     assert!(right.into_iter().eq(None));
1824 }
1825
1826 #[test]
1827 fn test_split_off_empty_left() {
1828     let mut data = rand_data(314);
1829
1830     let mut map = BTreeMap::from_iter(data.clone());
1831     let right = map.split_off(&data.iter().min().unwrap().0);
1832     map.check();
1833     right.check();
1834
1835     data.sort();
1836     assert!(map.into_iter().eq(None));
1837     assert!(right.into_iter().eq(data));
1838 }
1839
1840 // In a tree with 3 levels, if all but a part of the first leaf node is split off,
1841 // make sure fix_top eliminates both top levels.
1842 #[test]
1843 fn test_split_off_tiny_left_height_2() {
1844     let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
1845     let mut left: BTreeMap<_, _> = pairs.clone().collect();
1846     let right = left.split_off(&1);
1847     left.check();
1848     right.check();
1849     assert_eq!(left.len(), 1);
1850     assert_eq!(right.len(), MIN_INSERTS_HEIGHT_2 - 1);
1851     assert_eq!(*left.first_key_value().unwrap().0, 0);
1852     assert_eq!(*right.first_key_value().unwrap().0, 1);
1853 }
1854
1855 // In a tree with 3 levels, if only part of the last leaf node is split off,
1856 // make sure fix_top eliminates both top levels.
1857 #[test]
1858 fn test_split_off_tiny_right_height_2() {
1859     let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
1860     let last = MIN_INSERTS_HEIGHT_2 - 1;
1861     let mut left: BTreeMap<_, _> = pairs.clone().collect();
1862     assert_eq!(*left.last_key_value().unwrap().0, last);
1863     let right = left.split_off(&last);
1864     left.check();
1865     right.check();
1866     assert_eq!(left.len(), MIN_INSERTS_HEIGHT_2 - 1);
1867     assert_eq!(right.len(), 1);
1868     assert_eq!(*left.last_key_value().unwrap().0, last - 1);
1869     assert_eq!(*right.last_key_value().unwrap().0, last);
1870 }
1871
1872 #[test]
1873 fn test_split_off_large_random_sorted() {
1874     // Miri is too slow
1875     let mut data = if cfg!(miri) { rand_data(529) } else { rand_data(1529) };
1876     // special case with maximum height.
1877     data.sort();
1878
1879     let mut map = BTreeMap::from_iter(data.clone());
1880     let key = data[data.len() / 2].0;
1881     let right = map.split_off(&key);
1882     map.check();
1883     right.check();
1884
1885     assert!(map.into_iter().eq(data.clone().into_iter().filter(|x| x.0 < key)));
1886     assert!(right.into_iter().eq(data.into_iter().filter(|x| x.0 >= key)));
1887 }
1888
1889 #[test]
1890 fn test_into_iter_drop_leak_height_0() {
1891     static DROPS: AtomicUsize = AtomicUsize::new(0);
1892
1893     struct D;
1894
1895     impl Drop for D {
1896         fn drop(&mut self) {
1897             if DROPS.fetch_add(1, Ordering::SeqCst) == 3 {
1898                 panic!("panic in `drop`");
1899             }
1900         }
1901     }
1902
1903     let mut map = BTreeMap::new();
1904     map.insert("a", D);
1905     map.insert("b", D);
1906     map.insert("c", D);
1907     map.insert("d", D);
1908     map.insert("e", D);
1909
1910     catch_unwind(move || drop(map.into_iter())).unwrap_err();
1911
1912     assert_eq!(DROPS.load(Ordering::SeqCst), 5);
1913 }
1914
1915 #[test]
1916 fn test_into_iter_drop_leak_height_1() {
1917     let size = MIN_INSERTS_HEIGHT_1;
1918     static DROPS: AtomicUsize = AtomicUsize::new(0);
1919     static PANIC_POINT: AtomicUsize = AtomicUsize::new(0);
1920
1921     struct D;
1922     impl Drop for D {
1923         fn drop(&mut self) {
1924             if DROPS.fetch_add(1, Ordering::SeqCst) == PANIC_POINT.load(Ordering::SeqCst) {
1925                 panic!("panic in `drop`");
1926             }
1927         }
1928     }
1929
1930     for panic_point in vec![0, 1, size - 2, size - 1] {
1931         DROPS.store(0, Ordering::SeqCst);
1932         PANIC_POINT.store(panic_point, Ordering::SeqCst);
1933         let map: BTreeMap<_, _> = (0..size).map(|i| (i, D)).collect();
1934         catch_unwind(move || drop(map.into_iter())).unwrap_err();
1935         assert_eq!(DROPS.load(Ordering::SeqCst), size);
1936     }
1937 }
1938
1939 #[test]
1940 fn test_into_keys() {
1941     let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
1942     let map: BTreeMap<_, _> = vec.into_iter().collect();
1943     let keys: Vec<_> = map.into_keys().collect();
1944
1945     assert_eq!(keys.len(), 3);
1946     assert!(keys.contains(&1));
1947     assert!(keys.contains(&2));
1948     assert!(keys.contains(&3));
1949 }
1950
1951 #[test]
1952 fn test_into_values() {
1953     let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
1954     let map: BTreeMap<_, _> = vec.into_iter().collect();
1955     let values: Vec<_> = map.into_values().collect();
1956
1957     assert_eq!(values.len(), 3);
1958     assert!(values.contains(&'a'));
1959     assert!(values.contains(&'b'));
1960     assert!(values.contains(&'c'));
1961 }
1962
1963 #[test]
1964 fn test_insert_remove_intertwined() {
1965     let loops = if cfg!(miri) { 100 } else { 1_000_000 };
1966     let mut map = BTreeMap::new();
1967     let mut i = 1;
1968     let offset = 165; // somewhat arbitrarily chosen to cover some code paths
1969     for _ in 0..loops {
1970         i = (i + offset) & 0xFF;
1971         map.insert(i, i);
1972         map.remove(&(0xFF - i));
1973     }
1974     map.check();
1975 }
1976
1977 #[test]
1978 fn test_insert_remove_intertwined_ord_chaos() {
1979     let loops = if cfg!(miri) { 100 } else { 1_000_000 };
1980     let gov = Governor::new();
1981     let mut map = BTreeMap::new();
1982     let mut i = 1;
1983     let offset = 165; // more arbitrarily copied from above
1984     for _ in 0..loops {
1985         i = (i + offset) & 0xFF;
1986         map.insert(Governed(i, &gov), ());
1987         map.remove(&Governed(0xFF - i, &gov));
1988         gov.flip();
1989     }
1990     map.check_invariants();
1991 }