1 use super::super::map::RandomState; 2 use super::HashSet; 3 4 use crate::std::panic::{catch_unwind, AssertUnwindSafe}; 5 use crate::std::sync::atomic::{AtomicU32, Ordering}; 6 use crate::std::sync::Arc; 7 8 #[test] 9 fn test_zero_capacities() { 10 type HS = HashSet<i32>; 11 12 let s = HS::new(); 13 assert_eq!(s.capacity(), 0); 14 15 let s = HS::default(); 16 assert_eq!(s.capacity(), 0); 17 18 let s = HS::with_hasher(RandomState::new()); 19 assert_eq!(s.capacity(), 0); 20 21 let s = HS::with_capacity(0); 22 assert_eq!(s.capacity(), 0); 23 24 let s = HS::with_capacity_and_hasher(0, RandomState::new()); 25 assert_eq!(s.capacity(), 0); 26 27 let mut s = HS::new(); 28 s.insert(1); 29 s.insert(2); 30 s.remove(&1); 31 s.remove(&2); 32 s.shrink_to_fit(); 33 assert_eq!(s.capacity(), 0); 34 35 let mut s = HS::new(); 36 s.reserve(0); 37 assert_eq!(s.capacity(), 0); 38 } 39 40 #[test] 41 fn test_disjoint() { 42 let mut xs = HashSet::new(); 43 let mut ys = HashSet::new(); 44 assert!(xs.is_disjoint(&ys)); 45 assert!(ys.is_disjoint(&xs)); 46 assert!(xs.insert(5)); 47 assert!(ys.insert(11)); 48 assert!(xs.is_disjoint(&ys)); 49 assert!(ys.is_disjoint(&xs)); 50 assert!(xs.insert(7)); 51 assert!(xs.insert(19)); 52 assert!(xs.insert(4)); 53 assert!(ys.insert(2)); 54 assert!(ys.insert(-11)); 55 assert!(xs.is_disjoint(&ys)); 56 assert!(ys.is_disjoint(&xs)); 57 assert!(ys.insert(7)); 58 assert!(!xs.is_disjoint(&ys)); 59 assert!(!ys.is_disjoint(&xs)); 60 } 61 62 #[test] 63 fn test_subset_and_superset() { 64 let mut a = HashSet::new(); 65 assert!(a.insert(0)); 66 assert!(a.insert(5)); 67 assert!(a.insert(11)); 68 assert!(a.insert(7)); 69 70 let mut b = HashSet::new(); 71 assert!(b.insert(0)); 72 assert!(b.insert(7)); 73 assert!(b.insert(19)); 74 assert!(b.insert(250)); 75 assert!(b.insert(11)); 76 assert!(b.insert(200)); 77 78 assert!(!a.is_subset(&b)); 79 assert!(!a.is_superset(&b)); 80 assert!(!b.is_subset(&a)); 81 assert!(!b.is_superset(&a)); 82 83 assert!(b.insert(5)); 84 85 assert!(a.is_subset(&b)); 86 assert!(!a.is_superset(&b)); 87 assert!(!b.is_subset(&a)); 88 assert!(b.is_superset(&a)); 89 } 90 91 #[test] 92 fn test_iterate() { 93 let mut a = HashSet::new(); 94 for i in 0..32 { 95 assert!(a.insert(i)); 96 } 97 let mut observed: u32 = 0; 98 for k in &a { 99 observed |= 1 << *k; 100 } 101 assert_eq!(observed, 0xFFFF_FFFF); 102 } 103 104 #[test] 105 fn test_intersection() { 106 let mut a = HashSet::new(); 107 let mut b = HashSet::new(); 108 assert!(a.intersection(&b).next().is_none()); 109 110 assert!(a.insert(11)); 111 assert!(a.insert(1)); 112 assert!(a.insert(3)); 113 assert!(a.insert(77)); 114 assert!(a.insert(103)); 115 assert!(a.insert(5)); 116 assert!(a.insert(-5)); 117 118 assert!(b.insert(2)); 119 assert!(b.insert(11)); 120 assert!(b.insert(77)); 121 assert!(b.insert(-9)); 122 assert!(b.insert(-42)); 123 assert!(b.insert(5)); 124 assert!(b.insert(3)); 125 126 let mut i = 0; 127 let expected = [3, 5, 11, 77]; 128 for x in a.intersection(&b) { 129 assert!(expected.contains(x)); 130 i += 1 131 } 132 assert_eq!(i, expected.len()); 133 134 assert!(a.insert(9)); // make a bigger than b 135 136 i = 0; 137 for x in a.intersection(&b) { 138 assert!(expected.contains(x)); 139 i += 1 140 } 141 assert_eq!(i, expected.len()); 142 143 i = 0; 144 for x in b.intersection(&a) { 145 assert!(expected.contains(x)); 146 i += 1 147 } 148 assert_eq!(i, expected.len()); 149 } 150 151 #[test] 152 fn test_difference() { 153 let mut a = HashSet::new(); 154 let mut b = HashSet::new(); 155 156 assert!(a.insert(1)); 157 assert!(a.insert(3)); 158 assert!(a.insert(5)); 159 assert!(a.insert(9)); 160 assert!(a.insert(11)); 161 162 assert!(b.insert(3)); 163 assert!(b.insert(9)); 164 165 let mut i = 0; 166 let expected = [1, 5, 11]; 167 for x in a.difference(&b) { 168 assert!(expected.contains(x)); 169 i += 1 170 } 171 assert_eq!(i, expected.len()); 172 } 173 174 #[test] 175 fn test_symmetric_difference() { 176 let mut a = HashSet::new(); 177 let mut b = HashSet::new(); 178 179 assert!(a.insert(1)); 180 assert!(a.insert(3)); 181 assert!(a.insert(5)); 182 assert!(a.insert(9)); 183 assert!(a.insert(11)); 184 185 assert!(b.insert(-2)); 186 assert!(b.insert(3)); 187 assert!(b.insert(9)); 188 assert!(b.insert(14)); 189 assert!(b.insert(22)); 190 191 let mut i = 0; 192 let expected = [-2, 1, 5, 11, 14, 22]; 193 for x in a.symmetric_difference(&b) { 194 assert!(expected.contains(x)); 195 i += 1 196 } 197 assert_eq!(i, expected.len()); 198 } 199 200 #[test] 201 fn test_union() { 202 let mut a = HashSet::new(); 203 let mut b = HashSet::new(); 204 assert!(a.union(&b).next().is_none()); 205 assert!(b.union(&a).next().is_none()); 206 207 assert!(a.insert(1)); 208 assert!(a.insert(3)); 209 assert!(a.insert(11)); 210 assert!(a.insert(16)); 211 assert!(a.insert(19)); 212 assert!(a.insert(24)); 213 214 assert!(b.insert(-2)); 215 assert!(b.insert(1)); 216 assert!(b.insert(5)); 217 assert!(b.insert(9)); 218 assert!(b.insert(13)); 219 assert!(b.insert(19)); 220 221 let mut i = 0; 222 let expected = [-2, 1, 3, 5, 9, 11, 13, 16, 19, 24]; 223 for x in a.union(&b) { 224 assert!(expected.contains(x)); 225 i += 1 226 } 227 assert_eq!(i, expected.len()); 228 229 assert!(a.insert(9)); // make a bigger than b 230 assert!(a.insert(5)); 231 232 i = 0; 233 for x in a.union(&b) { 234 assert!(expected.contains(x)); 235 i += 1 236 } 237 assert_eq!(i, expected.len()); 238 239 i = 0; 240 for x in b.union(&a) { 241 assert!(expected.contains(x)); 242 i += 1 243 } 244 assert_eq!(i, expected.len()); 245 } 246 247 #[test] 248 fn test_from_iter() { 249 let xs = [1, 2, 2, 3, 4, 5, 6, 7, 8, 9]; 250 251 let set: HashSet<_> = xs.iter().cloned().collect(); 252 253 for x in &xs { 254 assert!(set.contains(x)); 255 } 256 257 assert_eq!(set.iter().len(), xs.len() - 1); 258 } 259 260 #[test] 261 fn test_move_iter() { 262 let hs = { 263 let mut hs = HashSet::new(); 264 265 hs.insert('a'); 266 hs.insert('b'); 267 268 hs 269 }; 270 271 let v = hs.into_iter().collect::<Vec<char>>(); 272 assert!(v == ['a', 'b'] || v == ['b', 'a']); 273 } 274 275 #[test] 276 fn test_eq() { 277 // These constants once happened to expose a bug in insert(). 278 // I'm keeping them around to prevent a regression. 279 let mut s1 = HashSet::new(); 280 281 s1.insert(1); 282 s1.insert(2); 283 s1.insert(3); 284 285 let mut s2 = HashSet::new(); 286 287 s2.insert(1); 288 s2.insert(2); 289 290 assert!(s1 != s2); 291 292 s2.insert(3); 293 294 assert_eq!(s1, s2); 295 } 296 297 #[test] 298 fn test_show() { 299 let mut set = HashSet::new(); 300 let empty = HashSet::<i32>::new(); 301 302 set.insert(1); 303 set.insert(2); 304 305 let set_str = format!("{set:?}"); 306 307 assert!(set_str == "{1, 2}" || set_str == "{2, 1}"); 308 assert_eq!(format!("{empty:?}"), "{}"); 309 } 310 311 #[test] 312 fn test_trivial_drain() { 313 let mut s = HashSet::<i32>::new(); 314 for _ in s.drain() {} 315 assert!(s.is_empty()); 316 drop(s); 317 318 let mut s = HashSet::<i32>::new(); 319 drop(s.drain()); 320 assert!(s.is_empty()); 321 } 322 323 #[test] 324 fn test_drain() { 325 let mut s: HashSet<_> = (1..100).collect(); 326 327 // try this a bunch of times to make sure we don't screw up internal state. 328 for _ in 0..20 { 329 assert_eq!(s.len(), 99); 330 331 { 332 let mut last_i = 0; 333 let mut d = s.drain(); 334 for (i, x) in d.by_ref().take(50).enumerate() { 335 last_i = i; 336 assert!(x != 0); 337 } 338 assert_eq!(last_i, 49); 339 } 340 341 for _ in &s { 342 panic!("s should be empty!"); 343 } 344 345 // reset to try again. 346 s.extend(1..100); 347 } 348 } 349 350 #[test] 351 fn test_replace() { 352 use crate::std::hash; 353 354 #[derive(Debug)] 355 struct Foo(&'static str, i32); 356 357 impl PartialEq for Foo { 358 fn eq(&self, other: &Self) -> bool { 359 self.0 == other.0 360 } 361 } 362 363 impl Eq for Foo {} 364 365 impl hash::Hash for Foo { 366 fn hash<H: hash::Hasher>(&self, h: &mut H) { 367 self.0.hash(h); 368 } 369 } 370 371 let mut s = HashSet::new(); 372 assert_eq!(s.replace(Foo("a", 1)), None); 373 assert_eq!(s.len(), 1); 374 assert_eq!(s.replace(Foo("a", 2)), Some(Foo("a", 1))); 375 assert_eq!(s.len(), 1); 376 377 let mut it = s.iter(); 378 assert_eq!(it.next(), Some(&Foo("a", 2))); 379 assert_eq!(it.next(), None); 380 } 381 382 #[test] 383 fn test_extend_ref() { 384 let mut a = HashSet::new(); 385 a.insert(1); 386 387 a.extend(&[2, 3, 4]); 388 389 assert_eq!(a.len(), 4); 390 assert!(a.contains(&1)); 391 assert!(a.contains(&2)); 392 assert!(a.contains(&3)); 393 assert!(a.contains(&4)); 394 395 let mut b = HashSet::new(); 396 b.insert(5); 397 b.insert(6); 398 399 a.extend(&b); 400 401 assert_eq!(a.len(), 6); 402 assert!(a.contains(&1)); 403 assert!(a.contains(&2)); 404 assert!(a.contains(&3)); 405 assert!(a.contains(&4)); 406 assert!(a.contains(&5)); 407 assert!(a.contains(&6)); 408 } 409 410 #[test] 411 fn test_retain() { 412 let xs = [1, 2, 3, 4, 5, 6]; 413 let mut set: HashSet<i32> = xs.iter().cloned().collect(); 414 set.retain(|&k| k % 2 == 0); 415 assert_eq!(set.len(), 3); 416 assert!(set.contains(&2)); 417 assert!(set.contains(&4)); 418 assert!(set.contains(&6)); 419 } 420 421 #[test] 422 fn test_extract_if() { 423 let mut x: HashSet<_> = [1].iter().copied().collect(); 424 let mut y: HashSet<_> = [1].iter().copied().collect(); 425 426 x.extract_if(|_| true).for_each(drop); 427 y.extract_if(|_| false).for_each(drop); 428 assert_eq!(x.len(), 0); 429 assert_eq!(y.len(), 1); 430 } 431 432 #[test] 433 fn test_extract_if_drop_panic_leak() { 434 static PREDS: AtomicU32 = AtomicU32::new(0); 435 static DROPS: AtomicU32 = AtomicU32::new(0); 436 437 #[derive(PartialEq, Eq, PartialOrd, Hash)] 438 struct D(i32); 439 impl Drop for D { 440 fn drop(&mut self) { 441 if DROPS.fetch_add(1, Ordering::SeqCst) == 1 { 442 panic!("panic in `drop`"); 443 } 444 } 445 } 446 447 let mut set = (0..3).map(|i| D(i)).collect::<HashSet<_>>(); 448 449 catch_unwind(move || { 450 set.extract_if(|_| { 451 PREDS.fetch_add(1, Ordering::SeqCst); 452 true 453 }) 454 .for_each(drop) 455 }) 456 .ok(); 457 458 assert_eq!(PREDS.load(Ordering::SeqCst), 2); 459 assert_eq!(DROPS.load(Ordering::SeqCst), 3); 460 } 461 462 #[test] 463 fn test_extract_if_pred_panic_leak() { 464 static PREDS: AtomicU32 = AtomicU32::new(0); 465 static DROPS: AtomicU32 = AtomicU32::new(0); 466 467 #[derive(PartialEq, Eq, PartialOrd, Hash)] 468 struct D; 469 impl Drop for D { 470 fn drop(&mut self) { 471 DROPS.fetch_add(1, Ordering::SeqCst); 472 } 473 } 474 475 let mut set: HashSet<_> = (0..3).map(|_| D).collect(); 476 477 catch_unwind(AssertUnwindSafe(|| { 478 set.extract_if(|_| match PREDS.fetch_add(1, Ordering::SeqCst) { 479 0 => true, 480 _ => panic!(), 481 }) 482 .for_each(drop) 483 })) 484 .ok(); 485 486 assert_eq!(PREDS.load(Ordering::SeqCst), 1); 487 assert_eq!(DROPS.load(Ordering::SeqCst), 3); 488 assert_eq!(set.len(), 0); 489 } 490 491 #[test] 492 fn from_array() { 493 let set = HashSet::from([1, 2, 3, 4]); 494 let unordered_duplicates = HashSet::from([4, 1, 4, 3, 2]); 495 assert_eq!(set, unordered_duplicates); 496 497 // This next line must infer the hasher type parameter. 498 // If you make a change that causes this line to no longer infer, 499 // that's a problem! 500 let _must_not_require_type_annotation = HashSet::from([1, 2]); 501 } 502 503 #[test] 504 fn const_with_hasher() { 505 const X: HashSet<(), ()> = HashSet::with_hasher(()); 506 assert_eq!(X.len(), 0); 507 } 508 509 #[test] 510 fn test_insert_does_not_overwrite_the_value() { 511 let first_value = Arc::new(17); 512 let second_value = Arc::new(17); 513 514 let mut set = HashSet::new(); 515 let inserted = set.insert(first_value.clone()); 516 assert!(inserted); 517 518 let inserted = set.insert(second_value); 519 assert!(!inserted); 520 521 assert!( 522 Arc::ptr_eq(set.iter().next().unwrap(), &first_value), 523 "Insert must not overwrite the value, so the contained value pointer \ 524 must be the same as first value pointer we inserted" 525 ); 526 } 527