1 use super::Entry::{Occupied, Vacant}; 2 use super::HashMap; 3 use super::RandomState; 4 use crate::std::assert_matches::assert_matches; 5 use crate::std::cell::RefCell; 6 use crate::std::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::std::panic::UnwindSafe>() {} 13 assert_unwind_safe::<HashMap<(), crate::std::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_extract_if { 948 use super::*; 949 950 use crate::std::panic::{catch_unwind, AssertUnwindSafe}; 951 use crate::std::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.extract_if(|_, _| unreachable!("there's nothing to decide on")).for_each(drop); 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.extract_if(|_, _| false).eq_sorted(crate::std::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.extract_if(|_, _| 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.extract_if(|_, v| { 997 *v += 6; 998 false 999 }) 1000 .eq_sorted(crate::std::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.extract_if(|_, 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 map.extract_if(|_, _| { 1038 PREDS.fetch_add(1, Ordering::SeqCst); 1039 true 1040 }) 1041 .for_each(drop) 1042 }) 1043 .unwrap_err(); 1044 1045 assert_eq!(PREDS.load(Ordering::SeqCst), 2); 1046 assert_eq!(DROPS.load(Ordering::SeqCst), 3); 1047 } 1048 1049 #[test] 1050 fn pred_panic_leak() { 1051 static PREDS: AtomicUsize = AtomicUsize::new(0); 1052 static DROPS: AtomicUsize = AtomicUsize::new(0); 1053 1054 struct D; 1055 impl Drop for D { 1056 fn drop(&mut self) { 1057 DROPS.fetch_add(1, Ordering::SeqCst); 1058 } 1059 } 1060 1061 let mut map = (0..3).map(|i| (i, D)).collect::<HashMap<_, _>>(); 1062 1063 catch_unwind(AssertUnwindSafe(|| { 1064 map.extract_if(|_, _| match PREDS.fetch_add(1, Ordering::SeqCst) { 1065 0 => true, 1066 _ => panic!(), 1067 }) 1068 .for_each(drop) 1069 })) 1070 .unwrap_err(); 1071 1072 assert_eq!(PREDS.load(Ordering::SeqCst), 2); 1073 assert_eq!(DROPS.load(Ordering::SeqCst), 1); 1074 assert_eq!(map.len(), 2); 1075 } 1076 1077 // Same as above, but attempt to use the iterator again after the panic in the predicate 1078 #[test] 1079 fn pred_panic_reuse() { 1080 static PREDS: AtomicUsize = AtomicUsize::new(0); 1081 static DROPS: AtomicUsize = AtomicUsize::new(0); 1082 1083 struct D; 1084 impl Drop for D { 1085 fn drop(&mut self) { 1086 DROPS.fetch_add(1, Ordering::SeqCst); 1087 } 1088 } 1089 1090 let mut map = (0..3).map(|i| (i, D)).collect::<HashMap<_, _>>(); 1091 1092 { 1093 let mut it = map.extract_if(|_, _| match PREDS.fetch_add(1, Ordering::SeqCst) { 1094 0 => true, 1095 _ => panic!(), 1096 }); 1097 catch_unwind(AssertUnwindSafe(|| while it.next().is_some() {})).unwrap_err(); 1098 // Iterator behaviour after a panic is explicitly unspecified, 1099 // so this is just the current implementation: 1100 let result = catch_unwind(AssertUnwindSafe(|| it.next())); 1101 assert!(result.is_err()); 1102 } 1103 1104 assert_eq!(PREDS.load(Ordering::SeqCst), 3); 1105 assert_eq!(DROPS.load(Ordering::SeqCst), 1); 1106 assert_eq!(map.len(), 2); 1107 } 1108 } 1109 1110 #[test] 1111 fn from_array() { 1112 let map = HashMap::from([(1, 2), (3, 4)]); 1113 let unordered_duplicates = HashMap::from([(3, 4), (1, 2), (1, 2)]); 1114 assert_eq!(map, unordered_duplicates); 1115 1116 // This next line must infer the hasher type parameter. 1117 // If you make a change that causes this line to no longer infer, 1118 // that's a problem! 1119 let _must_not_require_type_annotation = HashMap::from([(1, 2)]); 1120 } 1121 1122 #[test] 1123 fn const_with_hasher() { 1124 const X: HashMap<(), (), ()> = HashMap::with_hasher(()); 1125 assert_eq!(X.len(), 0); 1126 } 1127