1 use super::super::map::RandomState;
4 use crate::panic::{catch_unwind, AssertUnwindSafe};
5 use crate::sync::atomic::{AtomicU32, Ordering};
8 fn test_zero_capacities() {
9 type HS = HashSet<i32>;
12 assert_eq!(s.capacity(), 0);
14 let s = HS::default();
15 assert_eq!(s.capacity(), 0);
17 let s = HS::with_hasher(RandomState::new());
18 assert_eq!(s.capacity(), 0);
20 let s = HS::with_capacity(0);
21 assert_eq!(s.capacity(), 0);
23 let s = HS::with_capacity_and_hasher(0, RandomState::new());
24 assert_eq!(s.capacity(), 0);
26 let mut s = HS::new();
32 assert_eq!(s.capacity(), 0);
34 let mut s = HS::new();
36 assert_eq!(s.capacity(), 0);
41 let mut xs = HashSet::new();
42 let mut ys = HashSet::new();
43 assert!(xs.is_disjoint(&ys));
44 assert!(ys.is_disjoint(&xs));
45 assert!(xs.insert(5));
46 assert!(ys.insert(11));
47 assert!(xs.is_disjoint(&ys));
48 assert!(ys.is_disjoint(&xs));
49 assert!(xs.insert(7));
50 assert!(xs.insert(19));
51 assert!(xs.insert(4));
52 assert!(ys.insert(2));
53 assert!(ys.insert(-11));
54 assert!(xs.is_disjoint(&ys));
55 assert!(ys.is_disjoint(&xs));
56 assert!(ys.insert(7));
57 assert!(!xs.is_disjoint(&ys));
58 assert!(!ys.is_disjoint(&xs));
62 fn test_subset_and_superset() {
63 let mut a = HashSet::new();
66 assert!(a.insert(11));
69 let mut b = HashSet::new();
72 assert!(b.insert(19));
73 assert!(b.insert(250));
74 assert!(b.insert(11));
75 assert!(b.insert(200));
77 assert!(!a.is_subset(&b));
78 assert!(!a.is_superset(&b));
79 assert!(!b.is_subset(&a));
80 assert!(!b.is_superset(&a));
84 assert!(a.is_subset(&b));
85 assert!(!a.is_superset(&b));
86 assert!(!b.is_subset(&a));
87 assert!(b.is_superset(&a));
92 let mut a = HashSet::new();
96 let mut observed: u32 = 0;
100 assert_eq!(observed, 0xFFFF_FFFF);
104 fn test_intersection() {
105 let mut a = HashSet::new();
106 let mut b = HashSet::new();
107 assert!(a.intersection(&b).next().is_none());
109 assert!(a.insert(11));
110 assert!(a.insert(1));
111 assert!(a.insert(3));
112 assert!(a.insert(77));
113 assert!(a.insert(103));
114 assert!(a.insert(5));
115 assert!(a.insert(-5));
117 assert!(b.insert(2));
118 assert!(b.insert(11));
119 assert!(b.insert(77));
120 assert!(b.insert(-9));
121 assert!(b.insert(-42));
122 assert!(b.insert(5));
123 assert!(b.insert(3));
126 let expected = [3, 5, 11, 77];
127 for x in a.intersection(&b) {
128 assert!(expected.contains(x));
131 assert_eq!(i, expected.len());
133 assert!(a.insert(9)); // make a bigger than b
136 for x in a.intersection(&b) {
137 assert!(expected.contains(x));
140 assert_eq!(i, expected.len());
143 for x in b.intersection(&a) {
144 assert!(expected.contains(x));
147 assert_eq!(i, expected.len());
151 fn test_difference() {
152 let mut a = HashSet::new();
153 let mut b = HashSet::new();
155 assert!(a.insert(1));
156 assert!(a.insert(3));
157 assert!(a.insert(5));
158 assert!(a.insert(9));
159 assert!(a.insert(11));
161 assert!(b.insert(3));
162 assert!(b.insert(9));
165 let expected = [1, 5, 11];
166 for x in a.difference(&b) {
167 assert!(expected.contains(x));
170 assert_eq!(i, expected.len());
174 fn test_symmetric_difference() {
175 let mut a = HashSet::new();
176 let mut b = HashSet::new();
178 assert!(a.insert(1));
179 assert!(a.insert(3));
180 assert!(a.insert(5));
181 assert!(a.insert(9));
182 assert!(a.insert(11));
184 assert!(b.insert(-2));
185 assert!(b.insert(3));
186 assert!(b.insert(9));
187 assert!(b.insert(14));
188 assert!(b.insert(22));
191 let expected = [-2, 1, 5, 11, 14, 22];
192 for x in a.symmetric_difference(&b) {
193 assert!(expected.contains(x));
196 assert_eq!(i, expected.len());
201 let mut a = HashSet::new();
202 let mut b = HashSet::new();
203 assert!(a.union(&b).next().is_none());
204 assert!(b.union(&a).next().is_none());
206 assert!(a.insert(1));
207 assert!(a.insert(3));
208 assert!(a.insert(11));
209 assert!(a.insert(16));
210 assert!(a.insert(19));
211 assert!(a.insert(24));
213 assert!(b.insert(-2));
214 assert!(b.insert(1));
215 assert!(b.insert(5));
216 assert!(b.insert(9));
217 assert!(b.insert(13));
218 assert!(b.insert(19));
221 let expected = [-2, 1, 3, 5, 9, 11, 13, 16, 19, 24];
222 for x in a.union(&b) {
223 assert!(expected.contains(x));
226 assert_eq!(i, expected.len());
228 assert!(a.insert(9)); // make a bigger than b
229 assert!(a.insert(5));
232 for x in a.union(&b) {
233 assert!(expected.contains(x));
236 assert_eq!(i, expected.len());
239 for x in b.union(&a) {
240 assert!(expected.contains(x));
243 assert_eq!(i, expected.len());
247 fn test_from_iter() {
248 let xs = [1, 2, 2, 3, 4, 5, 6, 7, 8, 9];
250 let set: HashSet<_> = xs.iter().cloned().collect();
253 assert!(set.contains(x));
256 assert_eq!(set.iter().len(), xs.len() - 1);
260 fn test_move_iter() {
262 let mut hs = HashSet::new();
270 let v = hs.into_iter().collect::<Vec<char>>();
271 assert!(v == ['a', 'b'] || v == ['b', 'a']);
276 // These constants once happened to expose a bug in insert().
277 // I'm keeping them around to prevent a regression.
278 let mut s1 = HashSet::new();
284 let mut s2 = HashSet::new();
298 let mut set = HashSet::new();
299 let empty = HashSet::<i32>::new();
304 let set_str = format!("{:?}", set);
306 assert!(set_str == "{1, 2}" || set_str == "{2, 1}");
307 assert_eq!(format!("{:?}", empty), "{}");
311 fn test_trivial_drain() {
312 let mut s = HashSet::<i32>::new();
313 for _ in s.drain() {}
314 assert!(s.is_empty());
317 let mut s = HashSet::<i32>::new();
319 assert!(s.is_empty());
324 let mut s: HashSet<_> = (1..100).collect();
326 // try this a bunch of times to make sure we don't screw up internal state.
328 assert_eq!(s.len(), 99);
332 let mut d = s.drain();
333 for (i, x) in d.by_ref().take(50).enumerate() {
337 assert_eq!(last_i, 49);
341 panic!("s should be empty!");
344 // reset to try again.
354 struct Foo(&'static str, i32);
356 impl PartialEq for Foo {
357 fn eq(&self, other: &Self) -> bool {
364 impl hash::Hash for Foo {
365 fn hash<H: hash::Hasher>(&self, h: &mut H) {
370 let mut s = HashSet::new();
371 assert_eq!(s.replace(Foo("a", 1)), None);
372 assert_eq!(s.len(), 1);
373 assert_eq!(s.replace(Foo("a", 2)), Some(Foo("a", 1)));
374 assert_eq!(s.len(), 1);
376 let mut it = s.iter();
377 assert_eq!(it.next(), Some(&Foo("a", 2)));
378 assert_eq!(it.next(), None);
382 fn test_extend_ref() {
383 let mut a = HashSet::new();
386 a.extend(&[2, 3, 4]);
388 assert_eq!(a.len(), 4);
389 assert!(a.contains(&1));
390 assert!(a.contains(&2));
391 assert!(a.contains(&3));
392 assert!(a.contains(&4));
394 let mut b = HashSet::new();
400 assert_eq!(a.len(), 6);
401 assert!(a.contains(&1));
402 assert!(a.contains(&2));
403 assert!(a.contains(&3));
404 assert!(a.contains(&4));
405 assert!(a.contains(&5));
406 assert!(a.contains(&6));
411 let xs = [1, 2, 3, 4, 5, 6];
412 let mut set: HashSet<i32> = xs.iter().cloned().collect();
413 set.retain(|&k| k % 2 == 0);
414 assert_eq!(set.len(), 3);
415 assert!(set.contains(&2));
416 assert!(set.contains(&4));
417 assert!(set.contains(&6));
421 fn test_drain_filter() {
422 let mut x: HashSet<_> = [1].iter().copied().collect();
423 let mut y: HashSet<_> = [1].iter().copied().collect();
425 x.drain_filter(|_| true);
426 y.drain_filter(|_| false);
427 assert_eq!(x.len(), 0);
428 assert_eq!(y.len(), 1);
432 fn test_drain_filter_drop_panic_leak() {
433 static PREDS: AtomicU32 = AtomicU32::new(0);
434 static DROPS: AtomicU32 = AtomicU32::new(0);
436 #[derive(PartialEq, Eq, PartialOrd, Hash)]
440 if DROPS.fetch_add(1, Ordering::SeqCst) == 1 {
441 panic!("panic in `drop`");
446 let mut set = (0..3).map(|i| D(i)).collect::<HashSet<_>>();
448 catch_unwind(move || {
449 drop(set.drain_filter(|_| {
450 PREDS.fetch_add(1, Ordering::SeqCst);
456 assert_eq!(PREDS.load(Ordering::SeqCst), 3);
457 assert_eq!(DROPS.load(Ordering::SeqCst), 3);
461 fn test_drain_filter_pred_panic_leak() {
462 static PREDS: AtomicU32 = AtomicU32::new(0);
463 static DROPS: AtomicU32 = AtomicU32::new(0);
465 #[derive(PartialEq, Eq, PartialOrd, Hash)]
469 DROPS.fetch_add(1, Ordering::SeqCst);
473 let mut set: HashSet<_> = (0..3).map(|_| D).collect();
475 catch_unwind(AssertUnwindSafe(|| {
476 drop(set.drain_filter(|_| match PREDS.fetch_add(1, Ordering::SeqCst) {
483 assert_eq!(PREDS.load(Ordering::SeqCst), 1);
484 assert_eq!(DROPS.load(Ordering::SeqCst), 3);
485 assert_eq!(set.len(), 0);