library/std/src/collections/hash/map/tests.rs

   1 use super::Entry::{Occupied, Vacant};
   2 use super::HashMap;
   3 use super::RandomState;
   4 use crate::assert_matches::assert_matches;
   5 use crate::cell::RefCell;
   6 use crate::test_helpers::test_rng;
   7 use rand::Rng;
   8 use realstd::collections::TryReserveErrorKind::*;
   9
  10 // https://github.com/rust-lang/rust/issues/62301
  11 fn _assert_hashmap_is_unwind_safe() {
  12     fn assert_unwind_safe<T: crate::panic::UnwindSafe>() {}
  13     assert_unwind_safe::<HashMap<(), crate::cell::UnsafeCell<()>>>();
  14 }
  15
  16 #[test]
  17 fn test_zero_capacities() {
  18     type HM = HashMap<i32, i32>;
  19
  20     let m = HM::new();
  21     assert_eq!(m.capacity(), 0);
  22
  23     let m = HM::default();
  24     assert_eq!(m.capacity(), 0);
  25
  26     let m = HM::with_hasher(RandomState::new());
  27     assert_eq!(m.capacity(), 0);
  28
  29     let m = HM::with_capacity(0);
  30     assert_eq!(m.capacity(), 0);
  31
  32     let m = HM::with_capacity_and_hasher(0, RandomState::new());
  33     assert_eq!(m.capacity(), 0);
  34
  35     let mut m = HM::new();
  36     m.insert(1, 1);
  37     m.insert(2, 2);
  38     m.remove(&1);
  39     m.remove(&2);
  40     m.shrink_to_fit();
  41     assert_eq!(m.capacity(), 0);
  42
  43     let mut m = HM::new();
  44     m.reserve(0);
  45     assert_eq!(m.capacity(), 0);
  46 }
  47
  48 #[test]
  49 fn test_create_capacity_zero() {
  50     let mut m = HashMap::with_capacity(0);
  51
  52     assert!(m.insert(1, 1).is_none());
  53
  54     assert!(m.contains_key(&1));
  55     assert!(!m.contains_key(&0));
  56 }
  57
  58 #[test]
  59 fn test_insert() {
  60     let mut m = HashMap::new();
  61     assert_eq!(m.len(), 0);
  62     assert!(m.insert(1, 2).is_none());
  63     assert_eq!(m.len(), 1);
  64     assert!(m.insert(2, 4).is_none());
  65     assert_eq!(m.len(), 2);
  66     assert_eq!(*m.get(&1).unwrap(), 2);
  67     assert_eq!(*m.get(&2).unwrap(), 4);
  68 }
  69
  70 #[test]
  71 fn test_clone() {
  72     let mut m = HashMap::new();
  73     assert_eq!(m.len(), 0);
  74     assert!(m.insert(1, 2).is_none());
  75     assert_eq!(m.len(), 1);
  76     assert!(m.insert(2, 4).is_none());
  77     assert_eq!(m.len(), 2);
  78     let m2 = m.clone();
  79     assert_eq!(*m2.get(&1).unwrap(), 2);
  80     assert_eq!(*m2.get(&2).unwrap(), 4);
  81     assert_eq!(m2.len(), 2);
  82 }
  83
  84 thread_local! { static DROP_VECTOR: RefCell<Vec<i32>> = RefCell::new(Vec::new()) }
  85
  86 #[derive(Hash, PartialEq, Eq)]
  87 struct Droppable {
  88     k: usize,
  89 }
  90
  91 impl Droppable {
  92     fn new(k: usize) -> Droppable {
  93         DROP_VECTOR.with(|slot| {
  94             slot.borrow_mut()[k] += 1;
  95         });
  96
  97         Droppable { k }
  98     }
  99 }
 100
 101 impl Drop for Droppable {
 102     fn drop(&mut self) {
 103         DROP_VECTOR.with(|slot| {
 104             slot.borrow_mut()[self.k] -= 1;
 105         });
 106     }
 107 }
 108
 109 impl Clone for Droppable {
 110     fn clone(&self) -> Droppable {
 111         Droppable::new(self.k)
 112     }
 113 }
 114
 115 #[test]
 116 fn test_drops() {
 117     DROP_VECTOR.with(|slot| {
 118         *slot.borrow_mut() = vec![0; 200];
 119     });
 120
 121     {
 122         let mut m = HashMap::new();
 123
 124         DROP_VECTOR.with(|v| {
 125             for i in 0..200 {
 126                 assert_eq!(v.borrow()[i], 0);
 127             }
 128         });
 129
 130         for i in 0..100 {
 131             let d1 = Droppable::new(i);
 132             let d2 = Droppable::new(i + 100);
 133             m.insert(d1, d2);
 134         }
 135
 136         DROP_VECTOR.with(|v| {
 137             for i in 0..200 {
 138                 assert_eq!(v.borrow()[i], 1);
 139             }
 140         });
 141
 142         for i in 0..50 {
 143             let k = Droppable::new(i);
 144             let v = m.remove(&k);
 145
 146             assert!(v.is_some());
 147
 148             DROP_VECTOR.with(|v| {
 149                 assert_eq!(v.borrow()[i], 1);
 150                 assert_eq!(v.borrow()[i + 100], 1);
 151             });
 152         }
 153
 154         DROP_VECTOR.with(|v| {
 155             for i in 0..50 {
 156                 assert_eq!(v.borrow()[i], 0);
 157                 assert_eq!(v.borrow()[i + 100], 0);
 158             }
 159
 160             for i in 50..100 {
 161                 assert_eq!(v.borrow()[i], 1);
 162                 assert_eq!(v.borrow()[i + 100], 1);
 163             }
 164         });
 165     }
 166
 167     DROP_VECTOR.with(|v| {
 168         for i in 0..200 {
 169             assert_eq!(v.borrow()[i], 0);
 170         }
 171     });
 172 }
 173
 174 #[test]
 175 fn test_into_iter_drops() {
 176     DROP_VECTOR.with(|v| {
 177         *v.borrow_mut() = vec![0; 200];
 178     });
 179
 180     let hm = {
 181         let mut hm = HashMap::new();
 182
 183         DROP_VECTOR.with(|v| {
 184             for i in 0..200 {
 185                 assert_eq!(v.borrow()[i], 0);
 186             }
 187         });
 188
 189         for i in 0..100 {
 190             let d1 = Droppable::new(i);
 191             let d2 = Droppable::new(i + 100);
 192             hm.insert(d1, d2);
 193         }
 194
 195         DROP_VECTOR.with(|v| {
 196             for i in 0..200 {
 197                 assert_eq!(v.borrow()[i], 1);
 198             }
 199         });
 200
 201         hm
 202     };
 203
 204     // By the way, ensure that cloning doesn't screw up the dropping.
 205     drop(hm.clone());
 206
 207     {
 208         let mut half = hm.into_iter().take(50);
 209
 210         DROP_VECTOR.with(|v| {
 211             for i in 0..200 {
 212                 assert_eq!(v.borrow()[i], 1);
 213             }
 214         });
 215
 216         for _ in half.by_ref() {}
 217
 218         DROP_VECTOR.with(|v| {
 219             let nk = (0..100).filter(|&i| v.borrow()[i] == 1).count();
 220
 221             let nv = (0..100).filter(|&i| v.borrow()[i + 100] == 1).count();
 222
 223             assert_eq!(nk, 50);
 224             assert_eq!(nv, 50);
 225         });
 226     };
 227
 228     DROP_VECTOR.with(|v| {
 229         for i in 0..200 {
 230             assert_eq!(v.borrow()[i], 0);
 231         }
 232     });
 233 }
 234
 235 #[test]
 236 fn test_empty_remove() {
 237     let mut m: HashMap<i32, bool> = HashMap::new();
 238     assert_eq!(m.remove(&0), None);
 239 }
 240
 241 #[test]
 242 fn test_empty_entry() {
 243     let mut m: HashMap<i32, bool> = HashMap::new();
 244     match m.entry(0) {
 245         Occupied(_) => panic!(),
 246         Vacant(_) => {}
 247     }
 248     assert!(*m.entry(0).or_insert(true));
 249     assert_eq!(m.len(), 1);
 250 }
 251
 252 #[test]
 253 fn test_empty_iter() {
 254     let mut m: HashMap<i32, bool> = HashMap::new();
 255     assert_eq!(m.drain().next(), None);
 256     assert_eq!(m.keys().next(), None);
 257     assert_eq!(m.values().next(), None);
 258     assert_eq!(m.values_mut().next(), None);
 259     assert_eq!(m.iter().next(), None);
 260     assert_eq!(m.iter_mut().next(), None);
 261     assert_eq!(m.len(), 0);
 262     assert!(m.is_empty());
 263     assert_eq!(m.into_iter().next(), None);
 264 }
 265
 266 #[test]
 267 fn test_lots_of_insertions() {
 268     let mut m = HashMap::new();
 269
 270     // Try this a few times to make sure we never screw up the hashmap's
 271     // internal state.
 272     let loops = if cfg!(miri) { 2 } else { 10 };
 273     for _ in 0..loops {
 274         assert!(m.is_empty());
 275
 276         let count = if cfg!(miri) { 101 } else { 1001 };
 277
 278         for i in 1..count {
 279             assert!(m.insert(i, i).is_none());
 280
 281             for j in 1..=i {
 282                 let r = m.get(&j);
 283                 assert_eq!(r, Some(&j));
 284             }
 285
 286             for j in i + 1..count {
 287                 let r = m.get(&j);
 288                 assert_eq!(r, None);
 289             }
 290         }
 291
 292         for i in count..(2 * count) {
 293             assert!(!m.contains_key(&i));
 294         }
 295
 296         // remove forwards
 297         for i in 1..count {
 298             assert!(m.remove(&i).is_some());
 299
 300             for j in 1..=i {
 301                 assert!(!m.contains_key(&j));
 302             }
 303
 304             for j in i + 1..count {
 305                 assert!(m.contains_key(&j));
 306             }
 307         }
 308
 309         for i in 1..count {
 310             assert!(!m.contains_key(&i));
 311         }
 312
 313         for i in 1..count {
 314             assert!(m.insert(i, i).is_none());
 315         }
 316
 317         // remove backwards
 318         for i in (1..count).rev() {
 319             assert!(m.remove(&i).is_some());
 320
 321             for j in i..count {
 322                 assert!(!m.contains_key(&j));
 323             }
 324
 325             for j in 1..i {
 326                 assert!(m.contains_key(&j));
 327             }
 328         }
 329     }
 330 }
 331
 332 #[test]
 333 fn test_find_mut() {
 334     let mut m = HashMap::new();
 335     assert!(m.insert(1, 12).is_none());
 336     assert!(m.insert(2, 8).is_none());
 337     assert!(m.insert(5, 14).is_none());
 338     let new = 100;
 339     match m.get_mut(&5) {
 340         None => panic!(),
 341         Some(x) => *x = new,
 342     }
 343     assert_eq!(m.get(&5), Some(&new));
 344 }
 345
 346 #[test]
 347 fn test_insert_overwrite() {
 348     let mut m = HashMap::new();
 349     assert!(m.insert(1, 2).is_none());
 350     assert_eq!(*m.get(&1).unwrap(), 2);
 351     assert!(!m.insert(1, 3).is_none());
 352     assert_eq!(*m.get(&1).unwrap(), 3);
 353 }
 354
 355 #[test]
 356 fn test_insert_conflicts() {
 357     let mut m = HashMap::with_capacity(4);
 358     assert!(m.insert(1, 2).is_none());
 359     assert!(m.insert(5, 3).is_none());
 360     assert!(m.insert(9, 4).is_none());
 361     assert_eq!(*m.get(&9).unwrap(), 4);
 362     assert_eq!(*m.get(&5).unwrap(), 3);
 363     assert_eq!(*m.get(&1).unwrap(), 2);
 364 }
 365
 366 #[test]
 367 fn test_conflict_remove() {
 368     let mut m = HashMap::with_capacity(4);
 369     assert!(m.insert(1, 2).is_none());
 370     assert_eq!(*m.get(&1).unwrap(), 2);
 371     assert!(m.insert(5, 3).is_none());
 372     assert_eq!(*m.get(&1).unwrap(), 2);
 373     assert_eq!(*m.get(&5).unwrap(), 3);
 374     assert!(m.insert(9, 4).is_none());
 375     assert_eq!(*m.get(&1).unwrap(), 2);
 376     assert_eq!(*m.get(&5).unwrap(), 3);
 377     assert_eq!(*m.get(&9).unwrap(), 4);
 378     assert!(m.remove(&1).is_some());
 379     assert_eq!(*m.get(&9).unwrap(), 4);
 380     assert_eq!(*m.get(&5).unwrap(), 3);
 381 }
 382
 383 #[test]
 384 fn test_is_empty() {
 385     let mut m = HashMap::with_capacity(4);
 386     assert!(m.insert(1, 2).is_none());
 387     assert!(!m.is_empty());
 388     assert!(m.remove(&1).is_some());
 389     assert!(m.is_empty());
 390 }
 391
 392 #[test]
 393 fn test_remove() {
 394     let mut m = HashMap::new();
 395     m.insert(1, 2);
 396     assert_eq!(m.remove(&1), Some(2));
 397     assert_eq!(m.remove(&1), None);
 398 }
 399
 400 #[test]
 401 fn test_remove_entry() {
 402     let mut m = HashMap::new();
 403     m.insert(1, 2);
 404     assert_eq!(m.remove_entry(&1), Some((1, 2)));
 405     assert_eq!(m.remove(&1), None);
 406 }
 407
 408 #[test]
 409 fn test_iterate() {
 410     let mut m = HashMap::with_capacity(4);
 411     for i in 0..32 {
 412         assert!(m.insert(i, i * 2).is_none());
 413     }
 414     assert_eq!(m.len(), 32);
 415
 416     let mut observed: u32 = 0;
 417
 418     for (k, v) in &m {
 419         assert_eq!(*v, *k * 2);
 420         observed |= 1 << *k;
 421     }
 422     assert_eq!(observed, 0xFFFF_FFFF);
 423 }
 424
 425 #[test]
 426 fn test_keys() {
 427     let pairs = [(1, 'a'), (2, 'b'), (3, 'c')];
 428     let map: HashMap<_, _> = pairs.into_iter().collect();
 429     let keys: Vec<_> = map.keys().cloned().collect();
 430     assert_eq!(keys.len(), 3);
 431     assert!(keys.contains(&1));
 432     assert!(keys.contains(&2));
 433     assert!(keys.contains(&3));
 434 }
 435
 436 #[test]
 437 fn test_values() {
 438     let pairs = [(1, 'a'), (2, 'b'), (3, 'c')];
 439     let map: HashMap<_, _> = pairs.into_iter().collect();
 440     let values: Vec<_> = map.values().cloned().collect();
 441     assert_eq!(values.len(), 3);
 442     assert!(values.contains(&'a'));
 443     assert!(values.contains(&'b'));
 444     assert!(values.contains(&'c'));
 445 }
 446
 447 #[test]
 448 fn test_values_mut() {
 449     let pairs = [(1, 1), (2, 2), (3, 3)];
 450     let mut map: HashMap<_, _> = pairs.into_iter().collect();
 451     for value in map.values_mut() {
 452         *value = (*value) * 2
 453     }
 454     let values: Vec<_> = map.values().cloned().collect();
 455     assert_eq!(values.len(), 3);
 456     assert!(values.contains(&2));
 457     assert!(values.contains(&4));
 458     assert!(values.contains(&6));
 459 }
 460
 461 #[test]
 462 fn test_into_keys() {
 463     let pairs = [(1, 'a'), (2, 'b'), (3, 'c')];
 464     let map: HashMap<_, _> = pairs.into_iter().collect();
 465     let keys: Vec<_> = map.into_keys().collect();
 466
 467     assert_eq!(keys.len(), 3);
 468     assert!(keys.contains(&1));
 469     assert!(keys.contains(&2));
 470     assert!(keys.contains(&3));
 471 }
 472
 473 #[test]
 474 fn test_into_values() {
 475     let pairs = [(1, 'a'), (2, 'b'), (3, 'c')];
 476     let map: HashMap<_, _> = pairs.into_iter().collect();
 477     let values: Vec<_> = map.into_values().collect();
 478
 479     assert_eq!(values.len(), 3);
 480     assert!(values.contains(&'a'));
 481     assert!(values.contains(&'b'));
 482     assert!(values.contains(&'c'));
 483 }
 484
 485 #[test]
 486 fn test_find() {
 487     let mut m = HashMap::new();
 488     assert!(m.get(&1).is_none());
 489     m.insert(1, 2);
 490     match m.get(&1) {
 491         None => panic!(),
 492         Some(v) => assert_eq!(*v, 2),
 493     }
 494 }
 495
 496 #[test]
 497 fn test_eq() {
 498     let mut m1 = HashMap::new();
 499     m1.insert(1, 2);
 500     m1.insert(2, 3);
 501     m1.insert(3, 4);
 502
 503     let mut m2 = HashMap::new();
 504     m2.insert(1, 2);
 505     m2.insert(2, 3);
 506
 507     assert!(m1 != m2);
 508
 509     m2.insert(3, 4);
 510
 511     assert_eq!(m1, m2);
 512 }
 513
 514 #[test]
 515 fn test_show() {
 516     let mut map = HashMap::new();
 517     let empty: HashMap<i32, i32> = HashMap::new();
 518
 519     map.insert(1, 2);
 520     map.insert(3, 4);
 521
 522     let map_str = format!("{map:?}");
 523
 524     assert!(map_str == "{1: 2, 3: 4}" || map_str == "{3: 4, 1: 2}");
 525     assert_eq!(format!("{empty:?}"), "{}");
 526 }
 527
 528 #[test]
 529 fn test_reserve_shrink_to_fit() {
 530     let mut m = HashMap::new();
 531     m.insert(0, 0);
 532     m.remove(&0);
 533     assert!(m.capacity() >= m.len());
 534     for i in 0..128 {
 535         m.insert(i, i);
 536     }
 537     m.reserve(256);
 538
 539     let usable_cap = m.capacity();
 540     for i in 128..(128 + 256) {
 541         m.insert(i, i);
 542         assert_eq!(m.capacity(), usable_cap);
 543     }
 544
 545     for i in 100..(128 + 256) {
 546         assert_eq!(m.remove(&i), Some(i));
 547     }
 548     m.shrink_to_fit();
 549
 550     assert_eq!(m.len(), 100);
 551     assert!(!m.is_empty());
 552     assert!(m.capacity() >= m.len());
 553
 554     for i in 0..100 {
 555         assert_eq!(m.remove(&i), Some(i));
 556     }
 557     m.shrink_to_fit();
 558     m.insert(0, 0);
 559
 560     assert_eq!(m.len(), 1);
 561     assert!(m.capacity() >= m.len());
 562     assert_eq!(m.remove(&0), Some(0));
 563 }
 564
 565 #[test]
 566 fn test_from_iter() {
 567     let xs = [(1, 1), (2, 2), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
 568
 569     let map: HashMap<_, _> = xs.iter().cloned().collect();
 570
 571     for &(k, v) in &xs {
 572         assert_eq!(map.get(&k), Some(&v));
 573     }
 574
 575     assert_eq!(map.iter().len(), xs.len() - 1);
 576 }
 577
 578 #[test]
 579 fn test_size_hint() {
 580     let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
 581
 582     let map: HashMap<_, _> = xs.iter().cloned().collect();
 583
 584     let mut iter = map.iter();
 585
 586     for _ in iter.by_ref().take(3) {}
 587
 588     assert_eq!(iter.size_hint(), (3, Some(3)));
 589 }
 590
 591 #[test]
 592 fn test_iter_len() {
 593     let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
 594
 595     let map: HashMap<_, _> = xs.iter().cloned().collect();
 596
 597     let mut iter = map.iter();
 598
 599     for _ in iter.by_ref().take(3) {}
 600
 601     assert_eq!(iter.len(), 3);
 602 }
 603
 604 #[test]
 605 fn test_mut_size_hint() {
 606     let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
 607
 608     let mut map: HashMap<_, _> = xs.iter().cloned().collect();
 609
 610     let mut iter = map.iter_mut();
 611
 612     for _ in iter.by_ref().take(3) {}
 613
 614     assert_eq!(iter.size_hint(), (3, Some(3)));
 615 }
 616
 617 #[test]
 618 fn test_iter_mut_len() {
 619     let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
 620
 621     let mut map: HashMap<_, _> = xs.iter().cloned().collect();
 622
 623     let mut iter = map.iter_mut();
 624
 625     for _ in iter.by_ref().take(3) {}
 626
 627     assert_eq!(iter.len(), 3);
 628 }
 629
 630 #[test]
 631 fn test_index() {
 632     let mut map = HashMap::new();
 633
 634     map.insert(1, 2);
 635     map.insert(2, 1);
 636     map.insert(3, 4);
 637
 638     assert_eq!(map[&2], 1);
 639 }
 640
 641 #[test]
 642 #[should_panic]
 643 fn test_index_nonexistent() {
 644     let mut map = HashMap::new();
 645
 646     map.insert(1, 2);
 647     map.insert(2, 1);
 648     map.insert(3, 4);
 649
 650     map[&4];
 651 }
 652
 653 #[test]
 654 fn test_entry() {
 655     let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
 656
 657     let mut map: HashMap<_, _> = xs.iter().cloned().collect();
 658
 659     // Existing key (insert)
 660     match map.entry(1) {
 661         Vacant(_) => unreachable!(),
 662         Occupied(mut view) => {
 663             assert_eq!(view.get(), &10);
 664             assert_eq!(view.insert(100), 10);
 665         }
 666     }
 667     assert_eq!(map.get(&1).unwrap(), &100);
 668     assert_eq!(map.len(), 6);
 669
 670     // Existing key (update)
 671     match map.entry(2) {
 672         Vacant(_) => unreachable!(),
 673         Occupied(mut view) => {
 674             let v = view.get_mut();
 675             let new_v = (*v) * 10;
 676             *v = new_v;
 677         }
 678     }
 679     assert_eq!(map.get(&2).unwrap(), &200);
 680     assert_eq!(map.len(), 6);
 681
 682     // Existing key (take)
 683     match map.entry(3) {
 684         Vacant(_) => unreachable!(),
 685         Occupied(view) => {
 686             assert_eq!(view.remove(), 30);
 687         }
 688     }
 689     assert_eq!(map.get(&3), None);
 690     assert_eq!(map.len(), 5);
 691
 692     // Inexistent key (insert)
 693     match map.entry(10) {
 694         Occupied(_) => unreachable!(),
 695         Vacant(view) => {
 696             assert_eq!(*view.insert(1000), 1000);
 697         }
 698     }
 699     assert_eq!(map.get(&10).unwrap(), &1000);
 700     assert_eq!(map.len(), 6);
 701 }
 702
 703 #[test]
 704 fn test_entry_take_doesnt_corrupt() {
 705     #![allow(deprecated)] //rand
 706     // Test for #19292
 707     fn check(m: &HashMap<i32, ()>) {
 708         for k in m.keys() {
 709             assert!(m.contains_key(k), "{k} is in keys() but not in the map?");
 710         }
 711     }
 712
 713     let mut m = HashMap::new();
 714     let mut rng = test_rng();
 715
 716     // Populate the map with some items.
 717     for _ in 0..50 {
 718         let x = rng.gen_range(-10..10);
 719         m.insert(x, ());
 720     }
 721
 722     for _ in 0..1000 {
 723         let x = rng.gen_range(-10..10);
 724         match m.entry(x) {
 725             Vacant(_) => {}
 726             Occupied(e) => {
 727                 e.remove();
 728             }
 729         }
 730
 731         check(&m);
 732     }
 733 }
 734
 735 #[test]
 736 fn test_extend_ref() {
 737     let mut a = HashMap::new();
 738     a.insert(1, "one");
 739     let mut b = HashMap::new();
 740     b.insert(2, "two");
 741     b.insert(3, "three");
 742
 743     a.extend(&b);
 744
 745     assert_eq!(a.len(), 3);
 746     assert_eq!(a[&1], "one");
 747     assert_eq!(a[&2], "two");
 748     assert_eq!(a[&3], "three");
 749 }
 750
 751 #[test]
 752 fn test_capacity_not_less_than_len() {
 753     let mut a = HashMap::new();
 754     let mut item = 0;
 755
 756     for _ in 0..116 {
 757         a.insert(item, 0);
 758         item += 1;
 759     }
 760
 761     assert!(a.capacity() > a.len());
 762
 763     let free = a.capacity() - a.len();
 764     for _ in 0..free {
 765         a.insert(item, 0);
 766         item += 1;
 767     }
 768
 769     assert_eq!(a.len(), a.capacity());
 770
 771     // Insert at capacity should cause allocation.
 772     a.insert(item, 0);
 773     assert!(a.capacity() > a.len());
 774 }
 775
 776 #[test]
 777 fn test_occupied_entry_key() {
 778     let mut a = HashMap::new();
 779     let key = "hello there";
 780     let value = "value goes here";
 781     assert!(a.is_empty());
 782     a.insert(key, value);
 783     assert_eq!(a.len(), 1);
 784     assert_eq!(a[key], value);
 785
 786     match a.entry(key) {
 787         Vacant(_) => panic!(),
 788         Occupied(e) => assert_eq!(key, *e.key()),
 789     }
 790     assert_eq!(a.len(), 1);
 791     assert_eq!(a[key], value);
 792 }
 793
 794 #[test]
 795 fn test_vacant_entry_key() {
 796     let mut a = HashMap::new();
 797     let key = "hello there";
 798     let value = "value goes here";
 799
 800     assert!(a.is_empty());
 801     match a.entry(key) {
 802         Occupied(_) => panic!(),
 803         Vacant(e) => {
 804             assert_eq!(key, *e.key());
 805             e.insert(value);
 806         }
 807     }
 808     assert_eq!(a.len(), 1);
 809     assert_eq!(a[key], value);
 810 }
 811
 812 #[test]
 813 fn test_retain() {
 814     let mut map: HashMap<i32, i32> = (0..100).map(|x| (x, x * 10)).collect();
 815
 816     map.retain(|&k, _| k % 2 == 0);
 817     assert_eq!(map.len(), 50);
 818     assert_eq!(map[&2], 20);
 819     assert_eq!(map[&4], 40);
 820     assert_eq!(map[&6], 60);
 821 }
 822
 823 #[test]
 824 #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM
 825 #[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc
 826 fn test_try_reserve() {
 827     let mut empty_bytes: HashMap<u8, u8> = HashMap::new();
 828
 829     const MAX_USIZE: usize = usize::MAX;
 830
 831     assert_matches!(
 832         empty_bytes.try_reserve(MAX_USIZE).map_err(|e| e.kind()),
 833         Err(CapacityOverflow),
 834         "usize::MAX should trigger an overflow!"
 835     );
 836
 837     if let Err(AllocError { .. }) = empty_bytes.try_reserve(MAX_USIZE / 16).map_err(|e| e.kind()) {
 838     } else {
 839         // This may succeed if there is enough free memory. Attempt to
 840         // allocate a few more hashmaps to ensure the allocation will fail.
 841         let mut empty_bytes2: HashMap<u8, u8> = HashMap::new();
 842         let _ = empty_bytes2.try_reserve(MAX_USIZE / 16);
 843         let mut empty_bytes3: HashMap<u8, u8> = HashMap::new();
 844         let _ = empty_bytes3.try_reserve(MAX_USIZE / 16);
 845         let mut empty_bytes4: HashMap<u8, u8> = HashMap::new();
 846         assert_matches!(
 847             empty_bytes4.try_reserve(MAX_USIZE / 16).map_err(|e| e.kind()),
 848             Err(AllocError { .. }),
 849             "usize::MAX / 16 should trigger an OOM!"
 850         );
 851     }
 852 }
 853
 854 #[test]
 855 fn test_raw_entry() {
 856     use super::RawEntryMut::{Occupied, Vacant};
 857
 858     let xs = [(1i32, 10i32), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
 859
 860     let mut map: HashMap<_, _> = xs.iter().cloned().collect();
 861
 862     let compute_hash = |map: &HashMap<i32, i32>, k: i32| -> u64 {
 863         use core::hash::{BuildHasher, Hash, Hasher};
 864
 865         let mut hasher = map.hasher().build_hasher();
 866         k.hash(&mut hasher);
 867         hasher.finish()
 868     };
 869
 870     // Existing key (insert)
 871     match map.raw_entry_mut().from_key(&1) {
 872         Vacant(_) => unreachable!(),
 873         Occupied(mut view) => {
 874             assert_eq!(view.get(), &10);
 875             assert_eq!(view.insert(100), 10);
 876         }
 877     }
 878     let hash1 = compute_hash(&map, 1);
 879     assert_eq!(map.raw_entry().from_key(&1).unwrap(), (&1, &100));
 880     assert_eq!(map.raw_entry().from_hash(hash1, |k| *k == 1).unwrap(), (&1, &100));
 881     assert_eq!(map.raw_entry().from_key_hashed_nocheck(hash1, &1).unwrap(), (&1, &100));
 882     assert_eq!(map.len(), 6);
 883
 884     // Existing key (update)
 885     match map.raw_entry_mut().from_key(&2) {
 886         Vacant(_) => unreachable!(),
 887         Occupied(mut view) => {
 888             let v = view.get_mut();
 889             let new_v = (*v) * 10;
 890             *v = new_v;
 891         }
 892     }
 893     let hash2 = compute_hash(&map, 2);
 894     assert_eq!(map.raw_entry().from_key(&2).unwrap(), (&2, &200));
 895     assert_eq!(map.raw_entry().from_hash(hash2, |k| *k == 2).unwrap(), (&2, &200));
 896     assert_eq!(map.raw_entry().from_key_hashed_nocheck(hash2, &2).unwrap(), (&2, &200));
 897     assert_eq!(map.len(), 6);
 898
 899     // Existing key (take)
 900     let hash3 = compute_hash(&map, 3);
 901     match map.raw_entry_mut().from_key_hashed_nocheck(hash3, &3) {
 902         Vacant(_) => unreachable!(),
 903         Occupied(view) => {
 904             assert_eq!(view.remove_entry(), (3, 30));
 905         }
 906     }
 907     assert_eq!(map.raw_entry().from_key(&3), None);
 908     assert_eq!(map.raw_entry().from_hash(hash3, |k| *k == 3), None);
 909     assert_eq!(map.raw_entry().from_key_hashed_nocheck(hash3, &3), None);
 910     assert_eq!(map.len(), 5);
 911
 912     // Nonexistent key (insert)
 913     match map.raw_entry_mut().from_key(&10) {
 914         Occupied(_) => unreachable!(),
 915         Vacant(view) => {
 916             assert_eq!(view.insert(10, 1000), (&mut 10, &mut 1000));
 917         }
 918     }
 919     assert_eq!(map.raw_entry().from_key(&10).unwrap(), (&10, &1000));
 920     assert_eq!(map.len(), 6);
 921
 922     // Ensure all lookup methods produce equivalent results.
 923     for k in 0..12 {
 924         let hash = compute_hash(&map, k);
 925         let v = map.get(&k).cloned();
 926         let kv = v.as_ref().map(|v| (&k, v));
 927
 928         assert_eq!(map.raw_entry().from_key(&k), kv);
 929         assert_eq!(map.raw_entry().from_hash(hash, |q| *q == k), kv);
 930         assert_eq!(map.raw_entry().from_key_hashed_nocheck(hash, &k), kv);
 931
 932         match map.raw_entry_mut().from_key(&k) {
 933             Occupied(mut o) => assert_eq!(Some(o.get_key_value()), kv),
 934             Vacant(_) => assert_eq!(v, None),
 935         }
 936         match map.raw_entry_mut().from_key_hashed_nocheck(hash, &k) {
 937             Occupied(mut o) => assert_eq!(Some(o.get_key_value()), kv),
 938             Vacant(_) => assert_eq!(v, None),
 939         }
 940         match map.raw_entry_mut().from_hash(hash, |q| *q == k) {
 941             Occupied(mut o) => assert_eq!(Some(o.get_key_value()), kv),
 942             Vacant(_) => assert_eq!(v, None),
 943         }
 944     }
 945 }
 946
 947 mod test_drain_filter {
 948     use super::*;
 949
 950     use crate::panic::{catch_unwind, AssertUnwindSafe};
 951     use crate::sync::atomic::{AtomicUsize, Ordering};
 952
 953     trait EqSorted: Iterator {
 954         fn eq_sorted<I: IntoIterator<Item = Self::Item>>(self, other: I) -> bool;
 955     }
 956
 957     impl<T: Iterator> EqSorted for T
 958     where
 959         T::Item: Eq + Ord,
 960     {
 961         fn eq_sorted<I: IntoIterator<Item = Self::Item>>(self, other: I) -> bool {
 962             let mut v: Vec<_> = self.collect();
 963             v.sort_unstable();
 964             v.into_iter().eq(other)
 965         }
 966     }
 967
 968     #[test]
 969     fn empty() {
 970         let mut map: HashMap<i32, i32> = HashMap::new();
 971         map.drain_filter(|_, _| unreachable!("there's nothing to decide on"));
 972         assert!(map.is_empty());
 973     }
 974
 975     #[test]
 976     fn consuming_nothing() {
 977         let pairs = (0..3).map(|i| (i, i));
 978         let mut map: HashMap<_, _> = pairs.collect();
 979         assert!(map.drain_filter(|_, _| false).eq_sorted(crate::iter::empty()));
 980         assert_eq!(map.len(), 3);
 981     }
 982
 983     #[test]
 984     fn consuming_all() {
 985         let pairs = (0..3).map(|i| (i, i));
 986         let mut map: HashMap<_, _> = pairs.clone().collect();
 987         assert!(map.drain_filter(|_, _| true).eq_sorted(pairs));
 988         assert!(map.is_empty());
 989     }
 990
 991     #[test]
 992     fn mutating_and_keeping() {
 993         let pairs = (0..3).map(|i| (i, i));
 994         let mut map: HashMap<_, _> = pairs.collect();
 995         assert!(
 996             map.drain_filter(|_, v| {
 997                 *v += 6;
 998                 false
 999             })
1000             .eq_sorted(crate::iter::empty())
1001         );
1002         assert!(map.keys().copied().eq_sorted(0..3));
1003         assert!(map.values().copied().eq_sorted(6..9));
1004     }
1005
1006     #[test]
1007     fn mutating_and_removing() {
1008         let pairs = (0..3).map(|i| (i, i));
1009         let mut map: HashMap<_, _> = pairs.collect();
1010         assert!(
1011             map.drain_filter(|_, v| {
1012                 *v += 6;
1013                 true
1014             })
1015             .eq_sorted((0..3).map(|i| (i, i + 6)))
1016         );
1017         assert!(map.is_empty());
1018     }
1019
1020     #[test]
1021     fn drop_panic_leak() {
1022         static PREDS: AtomicUsize = AtomicUsize::new(0);
1023         static DROPS: AtomicUsize = AtomicUsize::new(0);
1024
1025         struct D;
1026         impl Drop for D {
1027             fn drop(&mut self) {
1028                 if DROPS.fetch_add(1, Ordering::SeqCst) == 1 {
1029                     panic!("panic in `drop`");
1030                 }
1031             }
1032         }
1033
1034         let mut map = (0..3).map(|i| (i, D)).collect::<HashMap<_, _>>();
1035
1036         catch_unwind(move || {
1037             drop(map.drain_filter(|_, _| {
1038                 PREDS.fetch_add(1, Ordering::SeqCst);
1039                 true
1040             }))
1041         })
1042         .unwrap_err();
1043
1044         assert_eq!(PREDS.load(Ordering::SeqCst), 3);
1045         assert_eq!(DROPS.load(Ordering::SeqCst), 3);
1046     }
1047
1048     #[test]
1049     fn pred_panic_leak() {
1050         static PREDS: AtomicUsize = AtomicUsize::new(0);
1051         static DROPS: AtomicUsize = AtomicUsize::new(0);
1052
1053         struct D;
1054         impl Drop for D {
1055             fn drop(&mut self) {
1056                 DROPS.fetch_add(1, Ordering::SeqCst);
1057             }
1058         }
1059
1060         let mut map = (0..3).map(|i| (i, D)).collect::<HashMap<_, _>>();
1061
1062         catch_unwind(AssertUnwindSafe(|| {
1063             drop(map.drain_filter(|_, _| match PREDS.fetch_add(1, Ordering::SeqCst) {
1064                 0 => true,
1065                 _ => panic!(),
1066             }))
1067         }))
1068         .unwrap_err();
1069
1070         assert_eq!(PREDS.load(Ordering::SeqCst), 2);
1071         assert_eq!(DROPS.load(Ordering::SeqCst), 1);
1072         assert_eq!(map.len(), 2);
1073     }
1074
1075     // Same as above, but attempt to use the iterator again after the panic in the predicate
1076     #[test]
1077     fn pred_panic_reuse() {
1078         static PREDS: AtomicUsize = AtomicUsize::new(0);
1079         static DROPS: AtomicUsize = AtomicUsize::new(0);
1080
1081         struct D;
1082         impl Drop for D {
1083             fn drop(&mut self) {
1084                 DROPS.fetch_add(1, Ordering::SeqCst);
1085             }
1086         }
1087
1088         let mut map = (0..3).map(|i| (i, D)).collect::<HashMap<_, _>>();
1089
1090         {
1091             let mut it = map.drain_filter(|_, _| match PREDS.fetch_add(1, Ordering::SeqCst) {
1092                 0 => true,
1093                 _ => panic!(),
1094             });
1095             catch_unwind(AssertUnwindSafe(|| while it.next().is_some() {})).unwrap_err();
1096             // Iterator behaviour after a panic is explicitly unspecified,
1097             // so this is just the current implementation:
1098             let result = catch_unwind(AssertUnwindSafe(|| it.next()));
1099             assert!(result.is_err());
1100         }
1101
1102         assert_eq!(PREDS.load(Ordering::SeqCst), 3);
1103         assert_eq!(DROPS.load(Ordering::SeqCst), 1);
1104         assert_eq!(map.len(), 2);
1105     }
1106 }
1107
1108 #[test]
1109 fn from_array() {
1110     let map = HashMap::from([(1, 2), (3, 4)]);
1111     let unordered_duplicates = HashMap::from([(3, 4), (1, 2), (1, 2)]);
1112     assert_eq!(map, unordered_duplicates);
1113
1114     // This next line must infer the hasher type parameter.
1115     // If you make a change that causes this line to no longer infer,
1116     // that's a problem!
1117     let _must_not_require_type_annotation = HashMap::from([(1, 2)]);
1118 }
1119
1120 #[test]
1121 fn const_with_hasher() {
1122     const X: HashMap<(), (), ()> = HashMap::with_hasher(());
1123     assert_eq!(X.len(), 0);
1124 }