library/alloc/tests/btree/map.rs

   1 use std::collections::btree_map::Entry::{Occupied, Vacant};
   2 use std::collections::BTreeMap;
   3 use std::convert::TryFrom;
   4 use std::fmt::Debug;
   5 use std::iter::FromIterator;
   6 use std::mem;
   7 use std::ops::Bound::{self, Excluded, Included, Unbounded};
   8 use std::ops::RangeBounds;
   9 use std::panic::{catch_unwind, AssertUnwindSafe};
  10 use std::rc::Rc;
  11 use std::sync::atomic::{AtomicUsize, Ordering};
  12
  13 use super::DeterministicRng;
  14
  15 // Value of node::CAPACITY, thus capacity of a tree with a single level,
  16 // i.e. a tree who's root is a leaf node at height 0.
  17 const NODE_CAPACITY: usize = 11;
  18
  19 // Minimum number of elements to insert in order to guarantee a tree with 2 levels,
  20 // i.e. a tree who's root is an internal node at height 1, with edges to leaf nodes.
  21 // It's not the minimum size: removing an element from such a tree does not always reduce height.
  22 const MIN_INSERTS_HEIGHT_1: usize = NODE_CAPACITY + 1;
  23
  24 // Minimum number of elements to insert in order to guarantee a tree with 3 levels,
  25 // i.e. a tree who's root is an internal node at height 2, with edges to more internal 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_2: usize = NODE_CAPACITY + (NODE_CAPACITY + 1) * NODE_CAPACITY + 1;
  28
  29 // Gather all references from a mutable iterator and make sure Miri notices if
  30 // using them is dangerous.
  31 fn test_all_refs<'a, T: 'a>(dummy: &mut T, iter: impl Iterator<Item = &'a mut T>) {
  32     // Gather all those references.
  33     let mut refs: Vec<&mut T> = iter.collect();
  34     // Use them all. Twice, to be sure we got all interleavings.
  35     for r in refs.iter_mut() {
  36         mem::swap(dummy, r);
  37     }
  38     for r in refs {
  39         mem::swap(dummy, r);
  40     }
  41 }
  42
  43 #[test]
  44 fn test_basic_large() {
  45     let mut map = BTreeMap::new();
  46     // Miri is too slow
  47     let size = if cfg!(miri) { MIN_INSERTS_HEIGHT_2 } else { 10000 };
  48     assert_eq!(map.len(), 0);
  49
  50     for i in 0..size {
  51         assert_eq!(map.insert(i, 10 * i), None);
  52         assert_eq!(map.len(), i + 1);
  53     }
  54
  55     assert_eq!(map.first_key_value(), Some((&0, &0)));
  56     assert_eq!(map.last_key_value(), Some((&(size - 1), &(10 * (size - 1)))));
  57     assert_eq!(map.first_entry().unwrap().key(), &0);
  58     assert_eq!(map.last_entry().unwrap().key(), &(size - 1));
  59
  60     for i in 0..size {
  61         assert_eq!(map.get(&i).unwrap(), &(i * 10));
  62     }
  63
  64     for i in size..size * 2 {
  65         assert_eq!(map.get(&i), None);
  66     }
  67
  68     for i in 0..size {
  69         assert_eq!(map.insert(i, 100 * i), Some(10 * i));
  70         assert_eq!(map.len(), size);
  71     }
  72
  73     for i in 0..size {
  74         assert_eq!(map.get(&i).unwrap(), &(i * 100));
  75     }
  76
  77     for i in 0..size / 2 {
  78         assert_eq!(map.remove(&(i * 2)), Some(i * 200));
  79         assert_eq!(map.len(), size - i - 1);
  80     }
  81
  82     for i in 0..size / 2 {
  83         assert_eq!(map.get(&(2 * i)), None);
  84         assert_eq!(map.get(&(2 * i + 1)).unwrap(), &(i * 200 + 100));
  85     }
  86
  87     for i in 0..size / 2 {
  88         assert_eq!(map.remove(&(2 * i)), None);
  89         assert_eq!(map.remove(&(2 * i + 1)), Some(i * 200 + 100));
  90         assert_eq!(map.len(), size / 2 - i - 1);
  91     }
  92 }
  93
  94 #[test]
  95 fn test_basic_small() {
  96     let mut map = BTreeMap::new();
  97     // Empty, root is absent (None):
  98     assert_eq!(map.remove(&1), None);
  99     assert_eq!(map.len(), 0);
 100     assert_eq!(map.get(&1), None);
 101     assert_eq!(map.get_mut(&1), None);
 102     assert_eq!(map.first_key_value(), None);
 103     assert_eq!(map.last_key_value(), None);
 104     assert_eq!(map.keys().count(), 0);
 105     assert_eq!(map.values().count(), 0);
 106     assert_eq!(map.range(..).next(), None);
 107     assert_eq!(map.range(..1).next(), None);
 108     assert_eq!(map.range(1..).next(), None);
 109     assert_eq!(map.range(1..=1).next(), None);
 110     assert_eq!(map.range(1..2).next(), None);
 111     assert_eq!(map.insert(1, 1), None);
 112
 113     // 1 key-value pair:
 114     assert_eq!(map.len(), 1);
 115     assert_eq!(map.get(&1), Some(&1));
 116     assert_eq!(map.get_mut(&1), Some(&mut 1));
 117     assert_eq!(map.first_key_value(), Some((&1, &1)));
 118     assert_eq!(map.last_key_value(), Some((&1, &1)));
 119     assert_eq!(map.keys().collect::<Vec<_>>(), vec![&1]);
 120     assert_eq!(map.values().collect::<Vec<_>>(), vec![&1]);
 121     assert_eq!(map.insert(1, 2), Some(1));
 122     assert_eq!(map.len(), 1);
 123     assert_eq!(map.get(&1), Some(&2));
 124     assert_eq!(map.get_mut(&1), Some(&mut 2));
 125     assert_eq!(map.first_key_value(), Some((&1, &2)));
 126     assert_eq!(map.last_key_value(), Some((&1, &2)));
 127     assert_eq!(map.keys().collect::<Vec<_>>(), vec![&1]);
 128     assert_eq!(map.values().collect::<Vec<_>>(), vec![&2]);
 129     assert_eq!(map.insert(2, 4), None);
 130
 131     // 2 key-value pairs:
 132     assert_eq!(map.len(), 2);
 133     assert_eq!(map.get(&2), Some(&4));
 134     assert_eq!(map.get_mut(&2), Some(&mut 4));
 135     assert_eq!(map.first_key_value(), Some((&1, &2)));
 136     assert_eq!(map.last_key_value(), Some((&2, &4)));
 137     assert_eq!(map.keys().collect::<Vec<_>>(), vec![&1, &2]);
 138     assert_eq!(map.values().collect::<Vec<_>>(), vec![&2, &4]);
 139     assert_eq!(map.remove(&1), Some(2));
 140
 141     // 1 key-value pair:
 142     assert_eq!(map.len(), 1);
 143     assert_eq!(map.get(&1), None);
 144     assert_eq!(map.get_mut(&1), None);
 145     assert_eq!(map.get(&2), Some(&4));
 146     assert_eq!(map.get_mut(&2), Some(&mut 4));
 147     assert_eq!(map.first_key_value(), Some((&2, &4)));
 148     assert_eq!(map.last_key_value(), Some((&2, &4)));
 149     assert_eq!(map.keys().collect::<Vec<_>>(), vec![&2]);
 150     assert_eq!(map.values().collect::<Vec<_>>(), vec![&4]);
 151     assert_eq!(map.remove(&2), Some(4));
 152
 153     // Empty but root is owned (Some(...)):
 154     assert_eq!(map.len(), 0);
 155     assert_eq!(map.get(&1), None);
 156     assert_eq!(map.get_mut(&1), None);
 157     assert_eq!(map.first_key_value(), None);
 158     assert_eq!(map.last_key_value(), None);
 159     assert_eq!(map.keys().count(), 0);
 160     assert_eq!(map.values().count(), 0);
 161     assert_eq!(map.range(..).next(), None);
 162     assert_eq!(map.range(..1).next(), None);
 163     assert_eq!(map.range(1..).next(), None);
 164     assert_eq!(map.range(1..=1).next(), None);
 165     assert_eq!(map.range(1..2).next(), None);
 166     assert_eq!(map.remove(&1), None);
 167 }
 168
 169 #[test]
 170 fn test_iter() {
 171     // Miri is too slow
 172     let size = if cfg!(miri) { 200 } else { 10000 };
 173
 174     let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 175
 176     fn test<T>(size: usize, mut iter: T)
 177     where
 178         T: Iterator<Item = (usize, usize)>,
 179     {
 180         for i in 0..size {
 181             assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
 182             assert_eq!(iter.next().unwrap(), (i, i));
 183         }
 184         assert_eq!(iter.size_hint(), (0, Some(0)));
 185         assert_eq!(iter.next(), None);
 186     }
 187     test(size, map.iter().map(|(&k, &v)| (k, v)));
 188     test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
 189     test(size, map.into_iter());
 190 }
 191
 192 #[test]
 193 fn test_iter_rev() {
 194     // Miri is too slow
 195     let size = if cfg!(miri) { 200 } else { 10000 };
 196
 197     let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 198
 199     fn test<T>(size: usize, mut iter: T)
 200     where
 201         T: Iterator<Item = (usize, usize)>,
 202     {
 203         for i in 0..size {
 204             assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
 205             assert_eq!(iter.next().unwrap(), (size - i - 1, size - i - 1));
 206         }
 207         assert_eq!(iter.size_hint(), (0, Some(0)));
 208         assert_eq!(iter.next(), None);
 209     }
 210     test(size, map.iter().rev().map(|(&k, &v)| (k, v)));
 211     test(size, map.iter_mut().rev().map(|(&k, &mut v)| (k, v)));
 212     test(size, map.into_iter().rev());
 213 }
 214
 215 /// Specifically tests iter_mut's ability to mutate the value of pairs in-line
 216 fn do_test_iter_mut_mutation<T>(size: usize)
 217 where
 218     T: Copy + Debug + Ord + TryFrom<usize>,
 219     <T as std::convert::TryFrom<usize>>::Error: std::fmt::Debug,
 220 {
 221     let zero = T::try_from(0).unwrap();
 222     let mut map: BTreeMap<T, T> = (0..size).map(|i| (T::try_from(i).unwrap(), zero)).collect();
 223
 224     // Forward and backward iteration sees enough pairs (also tested elsewhere)
 225     assert_eq!(map.iter_mut().count(), size);
 226     assert_eq!(map.iter_mut().rev().count(), size);
 227
 228     // Iterate forwards, trying to mutate to unique values
 229     for (i, (k, v)) in map.iter_mut().enumerate() {
 230         assert_eq!(*k, T::try_from(i).unwrap());
 231         assert_eq!(*v, zero);
 232         *v = T::try_from(i + 1).unwrap();
 233     }
 234
 235     // Iterate backwards, checking that mutations succeeded and trying to mutate again
 236     for (i, (k, v)) in map.iter_mut().rev().enumerate() {
 237         assert_eq!(*k, T::try_from(size - i - 1).unwrap());
 238         assert_eq!(*v, T::try_from(size - i).unwrap());
 239         *v = T::try_from(2 * size - i).unwrap();
 240     }
 241
 242     // Check that backward mutations succeeded
 243     for (i, (k, v)) in map.iter_mut().enumerate() {
 244         assert_eq!(*k, T::try_from(i).unwrap());
 245         assert_eq!(*v, T::try_from(size + i + 1).unwrap());
 246     }
 247 }
 248
 249 #[derive(Clone, Copy, Debug, Eq, PartialEq, PartialOrd, Ord)]
 250 #[repr(align(32))]
 251 struct Align32(usize);
 252
 253 impl TryFrom<usize> for Align32 {
 254     type Error = ();
 255
 256     fn try_from(s: usize) -> Result<Align32, ()> {
 257         Ok(Align32(s))
 258     }
 259 }
 260
 261 #[test]
 262 fn test_iter_mut_mutation() {
 263     // Check many alignments and trees with roots at various heights.
 264     do_test_iter_mut_mutation::<u8>(0);
 265     do_test_iter_mut_mutation::<u8>(1);
 266     do_test_iter_mut_mutation::<u8>(MIN_INSERTS_HEIGHT_1);
 267     do_test_iter_mut_mutation::<u8>(127); // not enough unique values to test MIN_INSERTS_HEIGHT_2
 268     do_test_iter_mut_mutation::<u16>(1);
 269     do_test_iter_mut_mutation::<u16>(MIN_INSERTS_HEIGHT_1);
 270     do_test_iter_mut_mutation::<u16>(MIN_INSERTS_HEIGHT_2);
 271     do_test_iter_mut_mutation::<u32>(1);
 272     do_test_iter_mut_mutation::<u32>(MIN_INSERTS_HEIGHT_1);
 273     do_test_iter_mut_mutation::<u32>(MIN_INSERTS_HEIGHT_2);
 274     do_test_iter_mut_mutation::<u64>(1);
 275     do_test_iter_mut_mutation::<u64>(MIN_INSERTS_HEIGHT_1);
 276     do_test_iter_mut_mutation::<u64>(MIN_INSERTS_HEIGHT_2);
 277     do_test_iter_mut_mutation::<u128>(1);
 278     do_test_iter_mut_mutation::<u128>(MIN_INSERTS_HEIGHT_1);
 279     do_test_iter_mut_mutation::<u128>(MIN_INSERTS_HEIGHT_2);
 280     do_test_iter_mut_mutation::<Align32>(1);
 281     do_test_iter_mut_mutation::<Align32>(MIN_INSERTS_HEIGHT_1);
 282     do_test_iter_mut_mutation::<Align32>(MIN_INSERTS_HEIGHT_2);
 283 }
 284
 285 #[test]
 286 #[cfg_attr(miri, ignore)] // FIXME: fails in Miri <https://github.com/rust-lang/rust/issues/73915>
 287 fn test_values_mut() {
 288     let mut a: BTreeMap<_, _> = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)).collect();
 289     test_all_refs(&mut 13, a.values_mut());
 290 }
 291
 292 #[test]
 293 fn test_values_mut_mutation() {
 294     let mut a = BTreeMap::new();
 295     a.insert(1, String::from("hello"));
 296     a.insert(2, String::from("goodbye"));
 297
 298     for value in a.values_mut() {
 299         value.push_str("!");
 300     }
 301
 302     let values: Vec<String> = a.values().cloned().collect();
 303     assert_eq!(values, [String::from("hello!"), String::from("goodbye!")]);
 304 }
 305
 306 #[test]
 307 #[cfg_attr(miri, ignore)] // FIXME: fails in Miri <https://github.com/rust-lang/rust/issues/73915>
 308 fn test_iter_entering_root_twice() {
 309     let mut map: BTreeMap<_, _> = (0..2).map(|i| (i, i)).collect();
 310     let mut it = map.iter_mut();
 311     let front = it.next().unwrap();
 312     let back = it.next_back().unwrap();
 313     assert_eq!(front, (&0, &mut 0));
 314     assert_eq!(back, (&1, &mut 1));
 315     *front.1 = 24;
 316     *back.1 = 42;
 317     assert_eq!(front, (&0, &mut 24));
 318     assert_eq!(back, (&1, &mut 42));
 319 }
 320
 321 #[test]
 322 #[cfg_attr(miri, ignore)] // FIXME: fails in Miri <https://github.com/rust-lang/rust/issues/73915>
 323 fn test_iter_descending_to_same_node_twice() {
 324     let mut map: BTreeMap<_, _> = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i)).collect();
 325     let mut it = map.iter_mut();
 326     // Descend into first child.
 327     let front = it.next().unwrap();
 328     // Descend into first child again, after running through second child.
 329     while it.next_back().is_some() {}
 330     // Check immutable access.
 331     assert_eq!(front, (&0, &mut 0));
 332     // Perform mutable access.
 333     *front.1 = 42;
 334 }
 335
 336 #[test]
 337 fn test_iter_mixed() {
 338     // Miri is too slow
 339     let size = if cfg!(miri) { 200 } else { 10000 };
 340
 341     let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 342
 343     fn test<T>(size: usize, mut iter: T)
 344     where
 345         T: Iterator<Item = (usize, usize)> + DoubleEndedIterator,
 346     {
 347         for i in 0..size / 4 {
 348             assert_eq!(iter.size_hint(), (size - i * 2, Some(size - i * 2)));
 349             assert_eq!(iter.next().unwrap(), (i, i));
 350             assert_eq!(iter.next_back().unwrap(), (size - i - 1, size - i - 1));
 351         }
 352         for i in size / 4..size * 3 / 4 {
 353             assert_eq!(iter.size_hint(), (size * 3 / 4 - i, Some(size * 3 / 4 - i)));
 354             assert_eq!(iter.next().unwrap(), (i, i));
 355         }
 356         assert_eq!(iter.size_hint(), (0, Some(0)));
 357         assert_eq!(iter.next(), None);
 358     }
 359     test(size, map.iter().map(|(&k, &v)| (k, v)));
 360     test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
 361     test(size, map.into_iter());
 362 }
 363
 364 #[test]
 365 #[cfg_attr(miri, ignore)] // FIXME: fails in Miri <https://github.com/rust-lang/rust/issues/73915>
 366 fn test_iter_min_max() {
 367     let mut a = BTreeMap::new();
 368     assert_eq!(a.iter().min(), None);
 369     assert_eq!(a.iter().max(), None);
 370     assert_eq!(a.iter_mut().min(), None);
 371     assert_eq!(a.iter_mut().max(), None);
 372     assert_eq!(a.range(..).min(), None);
 373     assert_eq!(a.range(..).max(), None);
 374     assert_eq!(a.range_mut(..).min(), None);
 375     assert_eq!(a.range_mut(..).max(), None);
 376     assert_eq!(a.keys().min(), None);
 377     assert_eq!(a.keys().max(), None);
 378     assert_eq!(a.values().min(), None);
 379     assert_eq!(a.values().max(), None);
 380     assert_eq!(a.values_mut().min(), None);
 381     assert_eq!(a.values_mut().max(), None);
 382     a.insert(1, 42);
 383     a.insert(2, 24);
 384     assert_eq!(a.iter().min(), Some((&1, &42)));
 385     assert_eq!(a.iter().max(), Some((&2, &24)));
 386     assert_eq!(a.iter_mut().min(), Some((&1, &mut 42)));
 387     assert_eq!(a.iter_mut().max(), Some((&2, &mut 24)));
 388     assert_eq!(a.range(..).min(), Some((&1, &42)));
 389     assert_eq!(a.range(..).max(), Some((&2, &24)));
 390     assert_eq!(a.range_mut(..).min(), Some((&1, &mut 42)));
 391     assert_eq!(a.range_mut(..).max(), Some((&2, &mut 24)));
 392     assert_eq!(a.keys().min(), Some(&1));
 393     assert_eq!(a.keys().max(), Some(&2));
 394     assert_eq!(a.values().min(), Some(&24));
 395     assert_eq!(a.values().max(), Some(&42));
 396     assert_eq!(a.values_mut().min(), Some(&mut 24));
 397     assert_eq!(a.values_mut().max(), Some(&mut 42));
 398 }
 399
 400 fn range_keys(map: &BTreeMap<i32, i32>, range: impl RangeBounds<i32>) -> Vec<i32> {
 401     map.range(range)
 402         .map(|(&k, &v)| {
 403             assert_eq!(k, v);
 404             k
 405         })
 406         .collect()
 407 }
 408
 409 #[test]
 410 fn test_range_small() {
 411     let size = 4;
 412
 413     let map: BTreeMap<_, _> = (1..=size).map(|i| (i, i)).collect();
 414     let all: Vec<_> = (1..=size).collect();
 415     let (first, last) = (vec![all[0]], vec![all[size as usize - 1]]);
 416
 417     assert_eq!(range_keys(&map, (Excluded(0), Excluded(size + 1))), all);
 418     assert_eq!(range_keys(&map, (Excluded(0), Included(size + 1))), all);
 419     assert_eq!(range_keys(&map, (Excluded(0), Included(size))), all);
 420     assert_eq!(range_keys(&map, (Excluded(0), Unbounded)), all);
 421     assert_eq!(range_keys(&map, (Included(0), Excluded(size + 1))), all);
 422     assert_eq!(range_keys(&map, (Included(0), Included(size + 1))), all);
 423     assert_eq!(range_keys(&map, (Included(0), Included(size))), all);
 424     assert_eq!(range_keys(&map, (Included(0), Unbounded)), all);
 425     assert_eq!(range_keys(&map, (Included(1), Excluded(size + 1))), all);
 426     assert_eq!(range_keys(&map, (Included(1), Included(size + 1))), all);
 427     assert_eq!(range_keys(&map, (Included(1), Included(size))), all);
 428     assert_eq!(range_keys(&map, (Included(1), Unbounded)), all);
 429     assert_eq!(range_keys(&map, (Unbounded, Excluded(size + 1))), all);
 430     assert_eq!(range_keys(&map, (Unbounded, Included(size + 1))), all);
 431     assert_eq!(range_keys(&map, (Unbounded, Included(size))), all);
 432     assert_eq!(range_keys(&map, ..), all);
 433
 434     assert_eq!(range_keys(&map, (Excluded(0), Excluded(1))), vec![]);
 435     assert_eq!(range_keys(&map, (Excluded(0), Included(0))), vec![]);
 436     assert_eq!(range_keys(&map, (Included(0), Included(0))), vec![]);
 437     assert_eq!(range_keys(&map, (Included(0), Excluded(1))), vec![]);
 438     assert_eq!(range_keys(&map, (Unbounded, Excluded(1))), vec![]);
 439     assert_eq!(range_keys(&map, (Unbounded, Included(0))), vec![]);
 440     assert_eq!(range_keys(&map, (Excluded(0), Excluded(2))), first);
 441     assert_eq!(range_keys(&map, (Excluded(0), Included(1))), first);
 442     assert_eq!(range_keys(&map, (Included(0), Excluded(2))), first);
 443     assert_eq!(range_keys(&map, (Included(0), Included(1))), first);
 444     assert_eq!(range_keys(&map, (Included(1), Excluded(2))), first);
 445     assert_eq!(range_keys(&map, (Included(1), Included(1))), first);
 446     assert_eq!(range_keys(&map, (Unbounded, Excluded(2))), first);
 447     assert_eq!(range_keys(&map, (Unbounded, Included(1))), first);
 448     assert_eq!(range_keys(&map, (Excluded(size - 1), Excluded(size + 1))), last);
 449     assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size + 1))), last);
 450     assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size))), last);
 451     assert_eq!(range_keys(&map, (Excluded(size - 1), Unbounded)), last);
 452     assert_eq!(range_keys(&map, (Included(size), Excluded(size + 1))), last);
 453     assert_eq!(range_keys(&map, (Included(size), Included(size + 1))), last);
 454     assert_eq!(range_keys(&map, (Included(size), Included(size))), last);
 455     assert_eq!(range_keys(&map, (Included(size), Unbounded)), last);
 456     assert_eq!(range_keys(&map, (Excluded(size), Excluded(size + 1))), vec![]);
 457     assert_eq!(range_keys(&map, (Excluded(size), Included(size))), vec![]);
 458     assert_eq!(range_keys(&map, (Excluded(size), Unbounded)), vec![]);
 459     assert_eq!(range_keys(&map, (Included(size + 1), Excluded(size + 1))), vec![]);
 460     assert_eq!(range_keys(&map, (Included(size + 1), Included(size + 1))), vec![]);
 461     assert_eq!(range_keys(&map, (Included(size + 1), Unbounded)), vec![]);
 462
 463     assert_eq!(range_keys(&map, ..3), vec![1, 2]);
 464     assert_eq!(range_keys(&map, 3..), vec![3, 4]);
 465     assert_eq!(range_keys(&map, 2..=3), vec![2, 3]);
 466 }
 467
 468 #[test]
 469 fn test_range_height_1() {
 470     // Tests tree with a root and 2 leaves. Depending on details we don't want or need
 471     // to rely upon, the single key at the root will be 6 or 7.
 472
 473     let map: BTreeMap<_, _> = (1..=MIN_INSERTS_HEIGHT_1 as i32).map(|i| (i, i)).collect();
 474     for &root in &[6, 7] {
 475         assert_eq!(range_keys(&map, (Excluded(root), Excluded(root + 1))), vec![]);
 476         assert_eq!(range_keys(&map, (Excluded(root), Included(root + 1))), vec![root + 1]);
 477         assert_eq!(range_keys(&map, (Included(root), Excluded(root + 1))), vec![root]);
 478         assert_eq!(range_keys(&map, (Included(root), Included(root + 1))), vec![root, root + 1]);
 479
 480         assert_eq!(range_keys(&map, (Excluded(root - 1), Excluded(root))), vec![]);
 481         assert_eq!(range_keys(&map, (Included(root - 1), Excluded(root))), vec![root - 1]);
 482         assert_eq!(range_keys(&map, (Excluded(root - 1), Included(root))), vec![root]);
 483         assert_eq!(range_keys(&map, (Included(root - 1), Included(root))), vec![root - 1, root]);
 484     }
 485 }
 486
 487 #[test]
 488 fn test_range_large() {
 489     let size = 200;
 490
 491     let map: BTreeMap<_, _> = (1..=size).map(|i| (i, i)).collect();
 492     let all: Vec<_> = (1..=size).collect();
 493     let (first, last) = (vec![all[0]], vec![all[size as usize - 1]]);
 494
 495     assert_eq!(range_keys(&map, (Excluded(0), Excluded(size + 1))), all);
 496     assert_eq!(range_keys(&map, (Excluded(0), Included(size + 1))), all);
 497     assert_eq!(range_keys(&map, (Excluded(0), Included(size))), all);
 498     assert_eq!(range_keys(&map, (Excluded(0), Unbounded)), all);
 499     assert_eq!(range_keys(&map, (Included(0), Excluded(size + 1))), all);
 500     assert_eq!(range_keys(&map, (Included(0), Included(size + 1))), all);
 501     assert_eq!(range_keys(&map, (Included(0), Included(size))), all);
 502     assert_eq!(range_keys(&map, (Included(0), Unbounded)), all);
 503     assert_eq!(range_keys(&map, (Included(1), Excluded(size + 1))), all);
 504     assert_eq!(range_keys(&map, (Included(1), Included(size + 1))), all);
 505     assert_eq!(range_keys(&map, (Included(1), Included(size))), all);
 506     assert_eq!(range_keys(&map, (Included(1), Unbounded)), all);
 507     assert_eq!(range_keys(&map, (Unbounded, Excluded(size + 1))), all);
 508     assert_eq!(range_keys(&map, (Unbounded, Included(size + 1))), all);
 509     assert_eq!(range_keys(&map, (Unbounded, Included(size))), all);
 510     assert_eq!(range_keys(&map, ..), all);
 511
 512     assert_eq!(range_keys(&map, (Excluded(0), Excluded(1))), vec![]);
 513     assert_eq!(range_keys(&map, (Excluded(0), Included(0))), vec![]);
 514     assert_eq!(range_keys(&map, (Included(0), Included(0))), vec![]);
 515     assert_eq!(range_keys(&map, (Included(0), Excluded(1))), vec![]);
 516     assert_eq!(range_keys(&map, (Unbounded, Excluded(1))), vec![]);
 517     assert_eq!(range_keys(&map, (Unbounded, Included(0))), vec![]);
 518     assert_eq!(range_keys(&map, (Excluded(0), Excluded(2))), first);
 519     assert_eq!(range_keys(&map, (Excluded(0), Included(1))), first);
 520     assert_eq!(range_keys(&map, (Included(0), Excluded(2))), first);
 521     assert_eq!(range_keys(&map, (Included(0), Included(1))), first);
 522     assert_eq!(range_keys(&map, (Included(1), Excluded(2))), first);
 523     assert_eq!(range_keys(&map, (Included(1), Included(1))), first);
 524     assert_eq!(range_keys(&map, (Unbounded, Excluded(2))), first);
 525     assert_eq!(range_keys(&map, (Unbounded, Included(1))), first);
 526     assert_eq!(range_keys(&map, (Excluded(size - 1), Excluded(size + 1))), last);
 527     assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size + 1))), last);
 528     assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size))), last);
 529     assert_eq!(range_keys(&map, (Excluded(size - 1), Unbounded)), last);
 530     assert_eq!(range_keys(&map, (Included(size), Excluded(size + 1))), last);
 531     assert_eq!(range_keys(&map, (Included(size), Included(size + 1))), last);
 532     assert_eq!(range_keys(&map, (Included(size), Included(size))), last);
 533     assert_eq!(range_keys(&map, (Included(size), Unbounded)), last);
 534     assert_eq!(range_keys(&map, (Excluded(size), Excluded(size + 1))), vec![]);
 535     assert_eq!(range_keys(&map, (Excluded(size), Included(size))), vec![]);
 536     assert_eq!(range_keys(&map, (Excluded(size), Unbounded)), vec![]);
 537     assert_eq!(range_keys(&map, (Included(size + 1), Excluded(size + 1))), vec![]);
 538     assert_eq!(range_keys(&map, (Included(size + 1), Included(size + 1))), vec![]);
 539     assert_eq!(range_keys(&map, (Included(size + 1), Unbounded)), vec![]);
 540
 541     fn check<'a, L, R>(lhs: L, rhs: R)
 542     where
 543         L: IntoIterator<Item = (&'a i32, &'a i32)>,
 544         R: IntoIterator<Item = (&'a i32, &'a i32)>,
 545     {
 546         let lhs: Vec<_> = lhs.into_iter().collect();
 547         let rhs: Vec<_> = rhs.into_iter().collect();
 548         assert_eq!(lhs, rhs);
 549     }
 550
 551     check(map.range(..=100), map.range(..101));
 552     check(map.range(5..=8), vec![(&5, &5), (&6, &6), (&7, &7), (&8, &8)]);
 553     check(map.range(-1..=2), vec![(&1, &1), (&2, &2)]);
 554 }
 555
 556 #[test]
 557 fn test_range_inclusive_max_value() {
 558     let max = usize::MAX;
 559     let map: BTreeMap<_, _> = vec![(max, 0)].into_iter().collect();
 560
 561     assert_eq!(map.range(max..=max).collect::<Vec<_>>(), &[(&max, &0)]);
 562 }
 563
 564 #[test]
 565 fn test_range_equal_empty_cases() {
 566     let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
 567     assert_eq!(map.range((Included(2), Excluded(2))).next(), None);
 568     assert_eq!(map.range((Excluded(2), Included(2))).next(), None);
 569 }
 570
 571 #[test]
 572 #[should_panic]
 573 fn test_range_equal_excluded() {
 574     let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
 575     map.range((Excluded(2), Excluded(2)));
 576 }
 577
 578 #[test]
 579 #[should_panic]
 580 fn test_range_backwards_1() {
 581     let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
 582     map.range((Included(3), Included(2)));
 583 }
 584
 585 #[test]
 586 #[should_panic]
 587 fn test_range_backwards_2() {
 588     let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
 589     map.range((Included(3), Excluded(2)));
 590 }
 591
 592 #[test]
 593 #[should_panic]
 594 fn test_range_backwards_3() {
 595     let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
 596     map.range((Excluded(3), Included(2)));
 597 }
 598
 599 #[test]
 600 #[should_panic]
 601 fn test_range_backwards_4() {
 602     let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
 603     map.range((Excluded(3), Excluded(2)));
 604 }
 605
 606 #[test]
 607 fn test_range_1000() {
 608     // Miri is too slow
 609     let size = if cfg!(miri) { MIN_INSERTS_HEIGHT_2 as u32 } else { 1000 };
 610     let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 611
 612     fn test(map: &BTreeMap<u32, u32>, size: u32, min: Bound<&u32>, max: Bound<&u32>) {
 613         let mut kvs = map.range((min, max)).map(|(&k, &v)| (k, v));
 614         let mut pairs = (0..size).map(|i| (i, i));
 615
 616         for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
 617             assert_eq!(kv, pair);
 618         }
 619         assert_eq!(kvs.next(), None);
 620         assert_eq!(pairs.next(), None);
 621     }
 622     test(&map, size, Included(&0), Excluded(&size));
 623     test(&map, size, Unbounded, Excluded(&size));
 624     test(&map, size, Included(&0), Included(&(size - 1)));
 625     test(&map, size, Unbounded, Included(&(size - 1)));
 626     test(&map, size, Included(&0), Unbounded);
 627     test(&map, size, Unbounded, Unbounded);
 628 }
 629
 630 #[test]
 631 fn test_range_borrowed_key() {
 632     let mut map = BTreeMap::new();
 633     map.insert("aardvark".to_string(), 1);
 634     map.insert("baboon".to_string(), 2);
 635     map.insert("coyote".to_string(), 3);
 636     map.insert("dingo".to_string(), 4);
 637     // NOTE: would like to use simply "b".."d" here...
 638     let mut iter = map.range::<str, _>((Included("b"), Excluded("d")));
 639     assert_eq!(iter.next(), Some((&"baboon".to_string(), &2)));
 640     assert_eq!(iter.next(), Some((&"coyote".to_string(), &3)));
 641     assert_eq!(iter.next(), None);
 642 }
 643
 644 #[test]
 645 fn test_range() {
 646     let size = 200;
 647     // Miri is too slow
 648     let step = if cfg!(miri) { 66 } else { 1 };
 649     let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 650
 651     for i in (0..size).step_by(step) {
 652         for j in (i..size).step_by(step) {
 653             let mut kvs = map.range((Included(&i), Included(&j))).map(|(&k, &v)| (k, v));
 654             let mut pairs = (i..=j).map(|i| (i, i));
 655
 656             for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
 657                 assert_eq!(kv, pair);
 658             }
 659             assert_eq!(kvs.next(), None);
 660             assert_eq!(pairs.next(), None);
 661         }
 662     }
 663 }
 664
 665 #[test]
 666 fn test_range_mut() {
 667     let size = 200;
 668     // Miri is too slow
 669     let step = if cfg!(miri) { 66 } else { 1 };
 670     let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 671
 672     for i in (0..size).step_by(step) {
 673         for j in (i..size).step_by(step) {
 674             let mut kvs = map.range_mut((Included(&i), Included(&j))).map(|(&k, &mut v)| (k, v));
 675             let mut pairs = (i..=j).map(|i| (i, i));
 676
 677             for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
 678                 assert_eq!(kv, pair);
 679             }
 680             assert_eq!(kvs.next(), None);
 681             assert_eq!(pairs.next(), None);
 682         }
 683     }
 684 }
 685
 686 mod test_drain_filter {
 687     use super::*;
 688
 689     #[test]
 690     fn empty() {
 691         let mut map: BTreeMap<i32, i32> = BTreeMap::new();
 692         map.drain_filter(|_, _| unreachable!("there's nothing to decide on"));
 693         assert!(map.is_empty());
 694     }
 695
 696     #[test]
 697     fn consuming_nothing() {
 698         let pairs = (0..3).map(|i| (i, i));
 699         let mut map: BTreeMap<_, _> = pairs.collect();
 700         assert!(map.drain_filter(|_, _| false).eq(std::iter::empty()));
 701     }
 702
 703     #[test]
 704     fn consuming_all() {
 705         let pairs = (0..3).map(|i| (i, i));
 706         let mut map: BTreeMap<_, _> = pairs.clone().collect();
 707         assert!(map.drain_filter(|_, _| true).eq(pairs));
 708     }
 709
 710     #[test]
 711     fn mutating_and_keeping() {
 712         let pairs = (0..3).map(|i| (i, i));
 713         let mut map: BTreeMap<_, _> = pairs.collect();
 714         assert!(
 715             map.drain_filter(|_, v| {
 716                 *v += 6;
 717                 false
 718             })
 719             .eq(std::iter::empty())
 720         );
 721         assert!(map.keys().copied().eq(0..3));
 722         assert!(map.values().copied().eq(6..9));
 723     }
 724
 725     #[test]
 726     fn mutating_and_removing() {
 727         let pairs = (0..3).map(|i| (i, i));
 728         let mut map: BTreeMap<_, _> = pairs.collect();
 729         assert!(
 730             map.drain_filter(|_, v| {
 731                 *v += 6;
 732                 true
 733             })
 734             .eq((0..3).map(|i| (i, i + 6)))
 735         );
 736         assert!(map.is_empty());
 737     }
 738
 739     #[test]
 740     fn underfull_keeping_all() {
 741         let pairs = (0..3).map(|i| (i, i));
 742         let mut map: BTreeMap<_, _> = pairs.collect();
 743         map.drain_filter(|_, _| false);
 744         assert!(map.keys().copied().eq(0..3));
 745     }
 746
 747     #[test]
 748     fn underfull_removing_one() {
 749         let pairs = (0..3).map(|i| (i, i));
 750         for doomed in 0..3 {
 751             let mut map: BTreeMap<_, _> = pairs.clone().collect();
 752             map.drain_filter(|i, _| *i == doomed);
 753             assert_eq!(map.len(), 2);
 754         }
 755     }
 756
 757     #[test]
 758     fn underfull_keeping_one() {
 759         let pairs = (0..3).map(|i| (i, i));
 760         for sacred in 0..3 {
 761             let mut map: BTreeMap<_, _> = pairs.clone().collect();
 762             map.drain_filter(|i, _| *i != sacred);
 763             assert!(map.keys().copied().eq(sacred..=sacred));
 764         }
 765     }
 766
 767     #[test]
 768     fn underfull_removing_all() {
 769         let pairs = (0..3).map(|i| (i, i));
 770         let mut map: BTreeMap<_, _> = pairs.collect();
 771         map.drain_filter(|_, _| true);
 772         assert!(map.is_empty());
 773     }
 774
 775     #[test]
 776     fn height_0_keeping_all() {
 777         let pairs = (0..NODE_CAPACITY).map(|i| (i, i));
 778         let mut map: BTreeMap<_, _> = pairs.collect();
 779         map.drain_filter(|_, _| false);
 780         assert!(map.keys().copied().eq(0..NODE_CAPACITY));
 781     }
 782
 783     #[test]
 784     fn height_0_removing_one() {
 785         let pairs = (0..NODE_CAPACITY).map(|i| (i, i));
 786         for doomed in 0..NODE_CAPACITY {
 787             let mut map: BTreeMap<_, _> = pairs.clone().collect();
 788             map.drain_filter(|i, _| *i == doomed);
 789             assert_eq!(map.len(), NODE_CAPACITY - 1);
 790         }
 791     }
 792
 793     #[test]
 794     fn height_0_keeping_one() {
 795         let pairs = (0..NODE_CAPACITY).map(|i| (i, i));
 796         for sacred in 0..NODE_CAPACITY {
 797             let mut map: BTreeMap<_, _> = pairs.clone().collect();
 798             map.drain_filter(|i, _| *i != sacred);
 799             assert!(map.keys().copied().eq(sacred..=sacred));
 800         }
 801     }
 802
 803     #[test]
 804     fn height_0_removing_all() {
 805         let pairs = (0..NODE_CAPACITY).map(|i| (i, i));
 806         let mut map: BTreeMap<_, _> = pairs.collect();
 807         map.drain_filter(|_, _| true);
 808         assert!(map.is_empty());
 809     }
 810
 811     #[test]
 812     fn height_0_keeping_half() {
 813         let mut map: BTreeMap<_, _> = (0..16).map(|i| (i, i)).collect();
 814         assert_eq!(map.drain_filter(|i, _| *i % 2 == 0).count(), 8);
 815         assert_eq!(map.len(), 8);
 816     }
 817
 818     #[test]
 819     fn height_1_removing_all() {
 820         let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i));
 821         let mut map: BTreeMap<_, _> = pairs.collect();
 822         map.drain_filter(|_, _| true);
 823         assert!(map.is_empty());
 824     }
 825
 826     #[test]
 827     fn height_1_removing_one() {
 828         let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i));
 829         for doomed in 0..MIN_INSERTS_HEIGHT_1 {
 830             let mut map: BTreeMap<_, _> = pairs.clone().collect();
 831             map.drain_filter(|i, _| *i == doomed);
 832             assert_eq!(map.len(), MIN_INSERTS_HEIGHT_1 - 1);
 833         }
 834     }
 835
 836     #[test]
 837     fn height_1_keeping_one() {
 838         let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i));
 839         for sacred in 0..MIN_INSERTS_HEIGHT_1 {
 840             let mut map: BTreeMap<_, _> = pairs.clone().collect();
 841             map.drain_filter(|i, _| *i != sacred);
 842             assert!(map.keys().copied().eq(sacred..=sacred));
 843         }
 844     }
 845
 846     #[cfg(not(miri))] // Miri is too slow
 847     #[test]
 848     fn height_2_removing_one() {
 849         let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
 850         for doomed in (0..MIN_INSERTS_HEIGHT_2).step_by(12) {
 851             let mut map: BTreeMap<_, _> = pairs.clone().collect();
 852             map.drain_filter(|i, _| *i == doomed);
 853             assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2 - 1);
 854         }
 855     }
 856
 857     #[cfg(not(miri))] // Miri is too slow
 858     #[test]
 859     fn height_2_keeping_one() {
 860         let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
 861         for sacred in (0..MIN_INSERTS_HEIGHT_2).step_by(12) {
 862             let mut map: BTreeMap<_, _> = pairs.clone().collect();
 863             map.drain_filter(|i, _| *i != sacred);
 864             assert!(map.keys().copied().eq(sacred..=sacred));
 865         }
 866     }
 867
 868     #[test]
 869     fn height_2_removing_all() {
 870         let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
 871         let mut map: BTreeMap<_, _> = pairs.collect();
 872         map.drain_filter(|_, _| true);
 873         assert!(map.is_empty());
 874     }
 875
 876     #[test]
 877     fn drop_panic_leak() {
 878         static PREDS: AtomicUsize = AtomicUsize::new(0);
 879         static DROPS: AtomicUsize = AtomicUsize::new(0);
 880
 881         struct D;
 882         impl Drop for D {
 883             fn drop(&mut self) {
 884                 if DROPS.fetch_add(1, Ordering::SeqCst) == 1 {
 885                     panic!("panic in `drop`");
 886                 }
 887             }
 888         }
 889
 890         // Keys are multiples of 4, so that each key is counted by a hexadecimal digit.
 891         let mut map = (0..3).map(|i| (i * 4, D)).collect::<BTreeMap<_, _>>();
 892
 893         catch_unwind(move || {
 894             drop(map.drain_filter(|i, _| {
 895                 PREDS.fetch_add(1usize << i, Ordering::SeqCst);
 896                 true
 897             }))
 898         })
 899         .unwrap_err();
 900
 901         assert_eq!(PREDS.load(Ordering::SeqCst), 0x011);
 902         assert_eq!(DROPS.load(Ordering::SeqCst), 3);
 903     }
 904
 905     #[test]
 906     fn pred_panic_leak() {
 907         static PREDS: AtomicUsize = AtomicUsize::new(0);
 908         static DROPS: AtomicUsize = AtomicUsize::new(0);
 909
 910         struct D;
 911         impl Drop for D {
 912             fn drop(&mut self) {
 913                 DROPS.fetch_add(1, Ordering::SeqCst);
 914             }
 915         }
 916
 917         // Keys are multiples of 4, so that each key is counted by a hexadecimal digit.
 918         let mut map = (0..3).map(|i| (i * 4, D)).collect::<BTreeMap<_, _>>();
 919
 920         catch_unwind(AssertUnwindSafe(|| {
 921             drop(map.drain_filter(|i, _| {
 922                 PREDS.fetch_add(1usize << i, Ordering::SeqCst);
 923                 match i {
 924                     0 => true,
 925                     _ => panic!(),
 926                 }
 927             }))
 928         }))
 929         .unwrap_err();
 930
 931         assert_eq!(PREDS.load(Ordering::SeqCst), 0x011);
 932         assert_eq!(DROPS.load(Ordering::SeqCst), 1);
 933         assert_eq!(map.len(), 2);
 934         assert_eq!(map.first_entry().unwrap().key(), &4);
 935         assert_eq!(map.last_entry().unwrap().key(), &8);
 936     }
 937
 938     // Same as above, but attempt to use the iterator again after the panic in the predicate
 939     #[test]
 940     fn pred_panic_reuse() {
 941         static PREDS: AtomicUsize = AtomicUsize::new(0);
 942         static DROPS: AtomicUsize = AtomicUsize::new(0);
 943
 944         struct D;
 945         impl Drop for D {
 946             fn drop(&mut self) {
 947                 DROPS.fetch_add(1, Ordering::SeqCst);
 948             }
 949         }
 950
 951         // Keys are multiples of 4, so that each key is counted by a hexadecimal digit.
 952         let mut map = (0..3).map(|i| (i * 4, D)).collect::<BTreeMap<_, _>>();
 953
 954         {
 955             let mut it = map.drain_filter(|i, _| {
 956                 PREDS.fetch_add(1usize << i, Ordering::SeqCst);
 957                 match i {
 958                     0 => true,
 959                     _ => panic!(),
 960                 }
 961             });
 962             catch_unwind(AssertUnwindSafe(|| while it.next().is_some() {})).unwrap_err();
 963             // Iterator behaviour after a panic is explicitly unspecified,
 964             // so this is just the current implementation:
 965             let result = catch_unwind(AssertUnwindSafe(|| it.next()));
 966             assert!(matches!(result, Ok(None)));
 967         }
 968
 969         assert_eq!(PREDS.load(Ordering::SeqCst), 0x011);
 970         assert_eq!(DROPS.load(Ordering::SeqCst), 1);
 971         assert_eq!(map.len(), 2);
 972         assert_eq!(map.first_entry().unwrap().key(), &4);
 973         assert_eq!(map.last_entry().unwrap().key(), &8);
 974     }
 975 }
 976
 977 #[test]
 978 fn test_borrow() {
 979     // make sure these compile -- using the Borrow trait
 980     {
 981         let mut map = BTreeMap::new();
 982         map.insert("0".to_string(), 1);
 983         assert_eq!(map["0"], 1);
 984     }
 985
 986     {
 987         let mut map = BTreeMap::new();
 988         map.insert(Box::new(0), 1);
 989         assert_eq!(map[&0], 1);
 990     }
 991
 992     {
 993         let mut map = BTreeMap::new();
 994         map.insert(Box::new([0, 1]) as Box<[i32]>, 1);
 995         assert_eq!(map[&[0, 1][..]], 1);
 996     }
 997
 998     {
 999         let mut map = BTreeMap::new();
1000         map.insert(Rc::new(0), 1);
1001         assert_eq!(map[&0], 1);
1002     }
1003 }
1004
1005 #[test]
1006 fn test_entry() {
1007     let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
1008
1009     let mut map: BTreeMap<_, _> = xs.iter().cloned().collect();
1010
1011     // Existing key (insert)
1012     match map.entry(1) {
1013         Vacant(_) => unreachable!(),
1014         Occupied(mut view) => {
1015             assert_eq!(view.get(), &10);
1016             assert_eq!(view.insert(100), 10);
1017         }
1018     }
1019     assert_eq!(map.get(&1).unwrap(), &100);
1020     assert_eq!(map.len(), 6);
1021
1022     // Existing key (update)
1023     match map.entry(2) {
1024         Vacant(_) => unreachable!(),
1025         Occupied(mut view) => {
1026             let v = view.get_mut();
1027             *v *= 10;
1028         }
1029     }
1030     assert_eq!(map.get(&2).unwrap(), &200);
1031     assert_eq!(map.len(), 6);
1032
1033     // Existing key (take)
1034     match map.entry(3) {
1035         Vacant(_) => unreachable!(),
1036         Occupied(view) => {
1037             assert_eq!(view.remove(), 30);
1038         }
1039     }
1040     assert_eq!(map.get(&3), None);
1041     assert_eq!(map.len(), 5);
1042
1043     // Inexistent key (insert)
1044     match map.entry(10) {
1045         Occupied(_) => unreachable!(),
1046         Vacant(view) => {
1047             assert_eq!(*view.insert(1000), 1000);
1048         }
1049     }
1050     assert_eq!(map.get(&10).unwrap(), &1000);
1051     assert_eq!(map.len(), 6);
1052 }
1053
1054 #[test]
1055 fn test_extend_ref() {
1056     let mut a = BTreeMap::new();
1057     a.insert(1, "one");
1058     let mut b = BTreeMap::new();
1059     b.insert(2, "two");
1060     b.insert(3, "three");
1061
1062     a.extend(&b);
1063
1064     assert_eq!(a.len(), 3);
1065     assert_eq!(a[&1], "one");
1066     assert_eq!(a[&2], "two");
1067     assert_eq!(a[&3], "three");
1068 }
1069
1070 #[test]
1071 fn test_zst() {
1072     let mut m = BTreeMap::new();
1073     assert_eq!(m.len(), 0);
1074
1075     assert_eq!(m.insert((), ()), None);
1076     assert_eq!(m.len(), 1);
1077
1078     assert_eq!(m.insert((), ()), Some(()));
1079     assert_eq!(m.len(), 1);
1080     assert_eq!(m.iter().count(), 1);
1081
1082     m.clear();
1083     assert_eq!(m.len(), 0);
1084
1085     for _ in 0..100 {
1086         m.insert((), ());
1087     }
1088
1089     assert_eq!(m.len(), 1);
1090     assert_eq!(m.iter().count(), 1);
1091 }
1092
1093 // This test's only purpose is to ensure that zero-sized keys with nonsensical orderings
1094 // do not cause segfaults when used with zero-sized values. All other map behavior is
1095 // undefined.
1096 #[test]
1097 fn test_bad_zst() {
1098     use std::cmp::Ordering;
1099
1100     struct Bad;
1101
1102     impl PartialEq for Bad {
1103         fn eq(&self, _: &Self) -> bool {
1104             false
1105         }
1106     }
1107
1108     impl Eq for Bad {}
1109
1110     impl PartialOrd for Bad {
1111         fn partial_cmp(&self, _: &Self) -> Option<Ordering> {
1112             Some(Ordering::Less)
1113         }
1114     }
1115
1116     impl Ord for Bad {
1117         fn cmp(&self, _: &Self) -> Ordering {
1118             Ordering::Less
1119         }
1120     }
1121
1122     let mut m = BTreeMap::new();
1123
1124     for _ in 0..100 {
1125         m.insert(Bad, Bad);
1126     }
1127 }
1128
1129 #[test]
1130 fn test_clone() {
1131     let mut map = BTreeMap::new();
1132     let size = MIN_INSERTS_HEIGHT_1;
1133     assert_eq!(map.len(), 0);
1134
1135     for i in 0..size {
1136         assert_eq!(map.insert(i, 10 * i), None);
1137         assert_eq!(map.len(), i + 1);
1138         assert_eq!(map, map.clone());
1139     }
1140
1141     for i in 0..size {
1142         assert_eq!(map.insert(i, 100 * i), Some(10 * i));
1143         assert_eq!(map.len(), size);
1144         assert_eq!(map, map.clone());
1145     }
1146
1147     for i in 0..size / 2 {
1148         assert_eq!(map.remove(&(i * 2)), Some(i * 200));
1149         assert_eq!(map.len(), size - i - 1);
1150         assert_eq!(map, map.clone());
1151     }
1152
1153     for i in 0..size / 2 {
1154         assert_eq!(map.remove(&(2 * i)), None);
1155         assert_eq!(map.remove(&(2 * i + 1)), Some(i * 200 + 100));
1156         assert_eq!(map.len(), size / 2 - i - 1);
1157         assert_eq!(map, map.clone());
1158     }
1159
1160     // Test a tree with 2 chock-full levels and a tree with 3 levels.
1161     map = (1..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)).collect();
1162     assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2 - 1);
1163     assert_eq!(map, map.clone());
1164     map.insert(0, 0);
1165     assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2);
1166     assert_eq!(map, map.clone());
1167 }
1168
1169 #[test]
1170 fn test_clone_from() {
1171     let mut map1 = BTreeMap::new();
1172     let max_size = MIN_INSERTS_HEIGHT_1;
1173
1174     // Range to max_size inclusive, because i is the size of map1 being tested.
1175     for i in 0..=max_size {
1176         let mut map2 = BTreeMap::new();
1177         for j in 0..i {
1178             let mut map1_copy = map2.clone();
1179             map1_copy.clone_from(&map1); // small cloned from large
1180             assert_eq!(map1_copy, map1);
1181             let mut map2_copy = map1.clone();
1182             map2_copy.clone_from(&map2); // large cloned from small
1183             assert_eq!(map2_copy, map2);
1184             map2.insert(100 * j + 1, 2 * j + 1);
1185         }
1186         map2.clone_from(&map1); // same length
1187         assert_eq!(map2, map1);
1188         map1.insert(i, 10 * i);
1189     }
1190 }
1191
1192 #[test]
1193 #[allow(dead_code)]
1194 fn test_variance() {
1195     use std::collections::btree_map::{IntoIter, Iter, Keys, Range, Values};
1196
1197     fn map_key<'new>(v: BTreeMap<&'static str, ()>) -> BTreeMap<&'new str, ()> {
1198         v
1199     }
1200     fn map_val<'new>(v: BTreeMap<(), &'static str>) -> BTreeMap<(), &'new str> {
1201         v
1202     }
1203     fn iter_key<'a, 'new>(v: Iter<'a, &'static str, ()>) -> Iter<'a, &'new str, ()> {
1204         v
1205     }
1206     fn iter_val<'a, 'new>(v: Iter<'a, (), &'static str>) -> Iter<'a, (), &'new str> {
1207         v
1208     }
1209     fn into_iter_key<'new>(v: IntoIter<&'static str, ()>) -> IntoIter<&'new str, ()> {
1210         v
1211     }
1212     fn into_iter_val<'new>(v: IntoIter<(), &'static str>) -> IntoIter<(), &'new str> {
1213         v
1214     }
1215     fn range_key<'a, 'new>(v: Range<'a, &'static str, ()>) -> Range<'a, &'new str, ()> {
1216         v
1217     }
1218     fn range_val<'a, 'new>(v: Range<'a, (), &'static str>) -> Range<'a, (), &'new str> {
1219         v
1220     }
1221     fn keys<'a, 'new>(v: Keys<'a, &'static str, ()>) -> Keys<'a, &'new str, ()> {
1222         v
1223     }
1224     fn vals<'a, 'new>(v: Values<'a, (), &'static str>) -> Values<'a, (), &'new str> {
1225         v
1226     }
1227 }
1228
1229 #[test]
1230 fn test_occupied_entry_key() {
1231     let mut a = BTreeMap::new();
1232     let key = "hello there";
1233     let value = "value goes here";
1234     assert!(a.is_empty());
1235     a.insert(key.clone(), value.clone());
1236     assert_eq!(a.len(), 1);
1237     assert_eq!(a[key], value);
1238
1239     match a.entry(key.clone()) {
1240         Vacant(_) => panic!(),
1241         Occupied(e) => assert_eq!(key, *e.key()),
1242     }
1243     assert_eq!(a.len(), 1);
1244     assert_eq!(a[key], value);
1245 }
1246
1247 #[test]
1248 fn test_vacant_entry_key() {
1249     let mut a = BTreeMap::new();
1250     let key = "hello there";
1251     let value = "value goes here";
1252
1253     assert!(a.is_empty());
1254     match a.entry(key.clone()) {
1255         Occupied(_) => panic!(),
1256         Vacant(e) => {
1257             assert_eq!(key, *e.key());
1258             e.insert(value.clone());
1259         }
1260     }
1261     assert_eq!(a.len(), 1);
1262     assert_eq!(a[key], value);
1263 }
1264
1265 #[test]
1266 fn test_first_last_entry() {
1267     let mut a = BTreeMap::new();
1268     assert!(a.first_entry().is_none());
1269     assert!(a.last_entry().is_none());
1270     a.insert(1, 42);
1271     assert_eq!(a.first_entry().unwrap().key(), &1);
1272     assert_eq!(a.last_entry().unwrap().key(), &1);
1273     a.insert(2, 24);
1274     assert_eq!(a.first_entry().unwrap().key(), &1);
1275     assert_eq!(a.last_entry().unwrap().key(), &2);
1276     a.insert(0, 6);
1277     assert_eq!(a.first_entry().unwrap().key(), &0);
1278     assert_eq!(a.last_entry().unwrap().key(), &2);
1279     let (k1, v1) = a.first_entry().unwrap().remove_entry();
1280     assert_eq!(k1, 0);
1281     assert_eq!(v1, 6);
1282     let (k2, v2) = a.last_entry().unwrap().remove_entry();
1283     assert_eq!(k2, 2);
1284     assert_eq!(v2, 24);
1285     assert_eq!(a.first_entry().unwrap().key(), &1);
1286     assert_eq!(a.last_entry().unwrap().key(), &1);
1287 }
1288
1289 macro_rules! create_append_test {
1290     ($name:ident, $len:expr) => {
1291         #[test]
1292         fn $name() {
1293             let mut a = BTreeMap::new();
1294             for i in 0..8 {
1295                 a.insert(i, i);
1296             }
1297
1298             let mut b = BTreeMap::new();
1299             for i in 5..$len {
1300                 b.insert(i, 2 * i);
1301             }
1302
1303             a.append(&mut b);
1304
1305             assert_eq!(a.len(), $len);
1306             assert_eq!(b.len(), 0);
1307
1308             for i in 0..$len {
1309                 if i < 5 {
1310                     assert_eq!(a[&i], i);
1311                 } else {
1312                     assert_eq!(a[&i], 2 * i);
1313                 }
1314             }
1315
1316             assert_eq!(a.remove(&($len - 1)), Some(2 * ($len - 1)));
1317             assert_eq!(a.insert($len - 1, 20), None);
1318         }
1319     };
1320 }
1321
1322 // These are mostly for testing the algorithm that "fixes" the right edge after insertion.
1323 // Single node.
1324 create_append_test!(test_append_9, 9);
1325 // Two leafs that don't need fixing.
1326 create_append_test!(test_append_17, 17);
1327 // Two leafs where the second one ends up underfull and needs stealing at the end.
1328 create_append_test!(test_append_14, 14);
1329 // Two leafs where the second one ends up empty because the insertion finished at the root.
1330 create_append_test!(test_append_12, 12);
1331 // Three levels; insertion finished at the root.
1332 create_append_test!(test_append_144, 144);
1333 // Three levels; insertion finished at leaf while there is an empty node on the second level.
1334 create_append_test!(test_append_145, 145);
1335 // Tests for several randomly chosen sizes.
1336 create_append_test!(test_append_170, 170);
1337 create_append_test!(test_append_181, 181);
1338 #[cfg(not(miri))] // Miri is too slow
1339 create_append_test!(test_append_239, 239);
1340 #[cfg(not(miri))] // Miri is too slow
1341 create_append_test!(test_append_1700, 1700);
1342
1343 fn rand_data(len: usize) -> Vec<(u32, u32)> {
1344     let mut rng = DeterministicRng::new();
1345     Vec::from_iter((0..len).map(|_| (rng.next(), rng.next())))
1346 }
1347
1348 #[test]
1349 fn test_split_off_empty_right() {
1350     let mut data = rand_data(173);
1351
1352     let mut map = BTreeMap::from_iter(data.clone());
1353     let right = map.split_off(&(data.iter().max().unwrap().0 + 1));
1354
1355     data.sort();
1356     assert!(map.into_iter().eq(data));
1357     assert!(right.into_iter().eq(None));
1358 }
1359
1360 #[test]
1361 fn test_split_off_empty_left() {
1362     let mut data = rand_data(314);
1363
1364     let mut map = BTreeMap::from_iter(data.clone());
1365     let right = map.split_off(&data.iter().min().unwrap().0);
1366
1367     data.sort();
1368     assert!(map.into_iter().eq(None));
1369     assert!(right.into_iter().eq(data));
1370 }
1371
1372 // In a tree with 3 levels, if all but a part of the first leaf node is split off,
1373 // make sure fix_top eliminates both top levels.
1374 #[test]
1375 fn test_split_off_tiny_left_height_2() {
1376     let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
1377     let mut left: BTreeMap<_, _> = pairs.clone().collect();
1378     let right = left.split_off(&1);
1379     assert_eq!(left.len(), 1);
1380     assert_eq!(right.len(), MIN_INSERTS_HEIGHT_2 - 1);
1381     assert_eq!(*left.first_key_value().unwrap().0, 0);
1382     assert_eq!(*right.first_key_value().unwrap().0, 1);
1383 }
1384
1385 // In a tree with 3 levels, if only part of the last leaf node is split off,
1386 // make sure fix_top eliminates both top levels.
1387 #[test]
1388 fn test_split_off_tiny_right_height_2() {
1389     let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
1390     let last = MIN_INSERTS_HEIGHT_2 - 1;
1391     let mut left: BTreeMap<_, _> = pairs.clone().collect();
1392     assert_eq!(*left.last_key_value().unwrap().0, last);
1393     let right = left.split_off(&last);
1394     assert_eq!(left.len(), MIN_INSERTS_HEIGHT_2 - 1);
1395     assert_eq!(right.len(), 1);
1396     assert_eq!(*left.last_key_value().unwrap().0, last - 1);
1397     assert_eq!(*right.last_key_value().unwrap().0, last);
1398 }
1399
1400 #[test]
1401 fn test_split_off_large_random_sorted() {
1402     // Miri is too slow
1403     let mut data = if cfg!(miri) { rand_data(529) } else { rand_data(1529) };
1404     // special case with maximum height.
1405     data.sort();
1406
1407     let mut map = BTreeMap::from_iter(data.clone());
1408     let key = data[data.len() / 2].0;
1409     let right = map.split_off(&key);
1410
1411     assert!(map.into_iter().eq(data.clone().into_iter().filter(|x| x.0 < key)));
1412     assert!(right.into_iter().eq(data.into_iter().filter(|x| x.0 >= key)));
1413 }
1414
1415 #[test]
1416 fn test_into_iter_drop_leak_height_0() {
1417     static DROPS: AtomicUsize = AtomicUsize::new(0);
1418
1419     struct D;
1420
1421     impl Drop for D {
1422         fn drop(&mut self) {
1423             if DROPS.fetch_add(1, Ordering::SeqCst) == 3 {
1424                 panic!("panic in `drop`");
1425             }
1426         }
1427     }
1428
1429     let mut map = BTreeMap::new();
1430     map.insert("a", D);
1431     map.insert("b", D);
1432     map.insert("c", D);
1433     map.insert("d", D);
1434     map.insert("e", D);
1435
1436     catch_unwind(move || drop(map.into_iter())).unwrap_err();
1437
1438     assert_eq!(DROPS.load(Ordering::SeqCst), 5);
1439 }
1440
1441 #[test]
1442 fn test_into_iter_drop_leak_height_1() {
1443     let size = MIN_INSERTS_HEIGHT_1;
1444     static DROPS: AtomicUsize = AtomicUsize::new(0);
1445     static PANIC_POINT: AtomicUsize = AtomicUsize::new(0);
1446
1447     struct D;
1448     impl Drop for D {
1449         fn drop(&mut self) {
1450             if DROPS.fetch_add(1, Ordering::SeqCst) == PANIC_POINT.load(Ordering::SeqCst) {
1451                 panic!("panic in `drop`");
1452             }
1453         }
1454     }
1455
1456     for panic_point in vec![0, 1, size - 2, size - 1] {
1457         DROPS.store(0, Ordering::SeqCst);
1458         PANIC_POINT.store(panic_point, Ordering::SeqCst);
1459         let map: BTreeMap<_, _> = (0..size).map(|i| (i, D)).collect();
1460         catch_unwind(move || drop(map.into_iter())).unwrap_err();
1461         assert_eq!(DROPS.load(Ordering::SeqCst), size);
1462     }
1463 }
1464
1465 #[test]
1466 fn test_into_keys() {
1467     let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
1468     let map: BTreeMap<_, _> = vec.into_iter().collect();
1469     let keys: Vec<_> = map.into_keys().collect();
1470
1471     assert_eq!(keys.len(), 3);
1472     assert!(keys.contains(&1));
1473     assert!(keys.contains(&2));
1474     assert!(keys.contains(&3));
1475 }
1476
1477 #[test]
1478 fn test_into_values() {
1479     let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
1480     let map: BTreeMap<_, _> = vec.into_iter().collect();
1481     let values: Vec<_> = map.into_values().collect();
1482
1483     assert_eq!(values.len(), 3);
1484     assert!(values.contains(&'a'));
1485     assert!(values.contains(&'b'));
1486     assert!(values.contains(&'c'));
1487 }