From 698f8c2f01ea549d77d7dc3338a12e04c11057b9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:02:58 +0200 Subject: Adding upstream version 1.64.0+dfsg1. Signed-off-by: Daniel Baumann --- compiler/rustc_index/src/bit_set/tests.rs | 873 ++++++++++++++++++++++++++++++ 1 file changed, 873 insertions(+) create mode 100644 compiler/rustc_index/src/bit_set/tests.rs (limited to 'compiler/rustc_index/src/bit_set/tests.rs') diff --git a/compiler/rustc_index/src/bit_set/tests.rs b/compiler/rustc_index/src/bit_set/tests.rs new file mode 100644 index 000000000..351d62fee --- /dev/null +++ b/compiler/rustc_index/src/bit_set/tests.rs @@ -0,0 +1,873 @@ +use super::*; + +extern crate test; +use std::hint::black_box; +use test::Bencher; + +#[test] +fn test_new_filled() { + for i in 0..128 { + let idx_buf = BitSet::new_filled(i); + let elems: Vec = idx_buf.iter().collect(); + let expected: Vec = (0..i).collect(); + assert_eq!(elems, expected); + } +} + +#[test] +fn bitset_iter_works() { + let mut bitset: BitSet = BitSet::new_empty(100); + bitset.insert(1); + bitset.insert(10); + bitset.insert(19); + bitset.insert(62); + bitset.insert(63); + bitset.insert(64); + bitset.insert(65); + bitset.insert(66); + bitset.insert(99); + assert_eq!(bitset.iter().collect::>(), [1, 10, 19, 62, 63, 64, 65, 66, 99]); +} + +#[test] +fn bitset_iter_works_2() { + let mut bitset: BitSet = BitSet::new_empty(320); + bitset.insert(0); + bitset.insert(127); + bitset.insert(191); + bitset.insert(255); + bitset.insert(319); + assert_eq!(bitset.iter().collect::>(), [0, 127, 191, 255, 319]); +} + +#[test] +fn bitset_clone_from() { + let mut a: BitSet = BitSet::new_empty(10); + a.insert(4); + a.insert(7); + a.insert(9); + + let mut b = BitSet::new_empty(2); + b.clone_from(&a); + assert_eq!(b.domain_size(), 10); + assert_eq!(b.iter().collect::>(), [4, 7, 9]); + + b.clone_from(&BitSet::new_empty(40)); + assert_eq!(b.domain_size(), 40); + assert_eq!(b.iter().collect::>(), []); +} + +#[test] +fn union_two_sets() { + let mut set1: BitSet = BitSet::new_empty(65); + let mut set2: BitSet = BitSet::new_empty(65); + assert!(set1.insert(3)); + assert!(!set1.insert(3)); + assert!(set2.insert(5)); + assert!(set2.insert(64)); + assert!(set1.union(&set2)); + assert!(!set1.union(&set2)); + assert!(set1.contains(3)); + assert!(!set1.contains(4)); + assert!(set1.contains(5)); + assert!(!set1.contains(63)); + assert!(set1.contains(64)); +} + +#[test] +fn hybrid_bitset() { + let mut sparse038: HybridBitSet = HybridBitSet::new_empty(256); + assert!(sparse038.is_empty()); + assert!(sparse038.insert(0)); + assert!(sparse038.insert(1)); + assert!(sparse038.insert(8)); + assert!(sparse038.insert(3)); + assert!(!sparse038.insert(3)); + assert!(sparse038.remove(1)); + assert!(!sparse038.is_empty()); + assert_eq!(sparse038.iter().collect::>(), [0, 3, 8]); + + for i in 0..256 { + if i == 0 || i == 3 || i == 8 { + assert!(sparse038.contains(i)); + } else { + assert!(!sparse038.contains(i)); + } + } + + let mut sparse01358 = sparse038.clone(); + assert!(sparse01358.insert(1)); + assert!(sparse01358.insert(5)); + assert_eq!(sparse01358.iter().collect::>(), [0, 1, 3, 5, 8]); + + let mut dense10 = HybridBitSet::new_empty(256); + for i in 0..10 { + assert!(dense10.insert(i)); + } + assert!(!dense10.is_empty()); + assert_eq!(dense10.iter().collect::>(), [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]); + + let mut dense256 = HybridBitSet::new_empty(256); + assert!(dense256.is_empty()); + dense256.insert_all(); + assert!(!dense256.is_empty()); + for i in 0..256 { + assert!(dense256.contains(i)); + } + + assert!(sparse038.superset(&sparse038)); // sparse + sparse (self) + assert!(sparse01358.superset(&sparse038)); // sparse + sparse + assert!(dense10.superset(&sparse038)); // dense + sparse + assert!(dense10.superset(&dense10)); // dense + dense (self) + assert!(dense256.superset(&dense10)); // dense + dense + + let mut hybrid = sparse038.clone(); + assert!(!sparse01358.union(&hybrid)); // no change + assert!(hybrid.union(&sparse01358)); + assert!(hybrid.superset(&sparse01358) && sparse01358.superset(&hybrid)); + assert!(!dense256.union(&dense10)); + + // dense / sparse where dense superset sparse + assert!(!dense10.clone().union(&sparse01358)); + assert!(sparse01358.clone().union(&dense10)); + assert!(dense10.clone().intersect(&sparse01358)); + assert!(!sparse01358.clone().intersect(&dense10)); + assert!(dense10.clone().subtract(&sparse01358)); + assert!(sparse01358.clone().subtract(&dense10)); + + // dense / sparse where sparse superset dense + let dense038 = sparse038.to_dense(); + assert!(!sparse01358.clone().union(&dense038)); + assert!(dense038.clone().union(&sparse01358)); + assert!(sparse01358.clone().intersect(&dense038)); + assert!(!dense038.clone().intersect(&sparse01358)); + assert!(sparse01358.clone().subtract(&dense038)); + assert!(dense038.clone().subtract(&sparse01358)); + + let mut dense = dense10.clone(); + assert!(dense.union(&dense256)); + assert!(dense.superset(&dense256) && dense256.superset(&dense)); + assert!(hybrid.union(&dense256)); + assert!(hybrid.superset(&dense256) && dense256.superset(&hybrid)); + + assert!(!dense10.clone().intersect(&dense256)); + assert!(dense256.clone().intersect(&dense10)); + assert!(dense10.clone().subtract(&dense256)); + assert!(dense256.clone().subtract(&dense10)); + + assert_eq!(dense256.iter().count(), 256); + let mut dense0 = dense256; + for i in 0..256 { + assert!(dense0.remove(i)); + } + assert!(!dense0.remove(0)); + assert!(dense0.is_empty()); +} + +#[test] +fn chunked_bitset() { + let mut b0 = ChunkedBitSet::::new_empty(0); + let b0b = b0.clone(); + assert_eq!(b0, ChunkedBitSet { domain_size: 0, chunks: Box::new([]), marker: PhantomData }); + + // There are no valid insert/remove/contains operations on a 0-domain + // bitset, but we can test `union`. + b0.assert_valid(); + assert!(!b0.union(&b0b)); + assert_eq!(b0.chunks(), vec![]); + assert_eq!(b0.count(), 0); + b0.assert_valid(); + + //----------------------------------------------------------------------- + + let mut b1 = ChunkedBitSet::::new_empty(1); + assert_eq!( + b1, + ChunkedBitSet { domain_size: 1, chunks: Box::new([Zeros(1)]), marker: PhantomData } + ); + + b1.assert_valid(); + assert!(!b1.contains(0)); + assert_eq!(b1.count(), 0); + assert!(b1.insert(0)); + assert!(b1.contains(0)); + assert_eq!(b1.count(), 1); + assert_eq!(b1.chunks(), [Ones(1)]); + assert!(!b1.insert(0)); + assert!(b1.remove(0)); + assert!(!b1.contains(0)); + assert_eq!(b1.count(), 0); + assert_eq!(b1.chunks(), [Zeros(1)]); + b1.assert_valid(); + + //----------------------------------------------------------------------- + + let mut b100 = ChunkedBitSet::::new_filled(100); + assert_eq!( + b100, + ChunkedBitSet { domain_size: 100, chunks: Box::new([Ones(100)]), marker: PhantomData } + ); + + b100.assert_valid(); + for i in 0..100 { + assert!(b100.contains(i)); + } + assert_eq!(b100.count(), 100); + assert!(b100.remove(3)); + assert!(b100.insert(3)); + assert_eq!(b100.chunks(), vec![Ones(100)]); + assert!( + b100.remove(20) && b100.remove(30) && b100.remove(40) && b100.remove(99) && b100.insert(30) + ); + assert_eq!(b100.count(), 97); + assert!(!b100.contains(20) && b100.contains(30) && !b100.contains(99) && b100.contains(50)); + assert_eq!( + b100.chunks(), + vec![Mixed( + 100, + 97, + #[rustfmt::skip] + Rc::new([ + 0b11111111_11111111_11111110_11111111_11111111_11101111_11111111_11111111, + 0b00000000_00000000_00000000_00000111_11111111_11111111_11111111_11111111, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, + ]) + )], + ); + b100.assert_valid(); + let mut num_removed = 0; + for i in 0..100 { + if b100.remove(i) { + num_removed += 1; + } + } + assert_eq!(num_removed, 97); + assert_eq!(b100.chunks(), vec![Zeros(100)]); + b100.assert_valid(); + + //----------------------------------------------------------------------- + + let mut b2548 = ChunkedBitSet::::new_empty(2548); + assert_eq!( + b2548, + ChunkedBitSet { + domain_size: 2548, + chunks: Box::new([Zeros(2048), Zeros(500)]), + marker: PhantomData, + } + ); + + b2548.assert_valid(); + b2548.insert(14); + b2548.remove(14); + assert_eq!(b2548.chunks(), vec![Zeros(2048), Zeros(500)]); + b2548.insert_all(); + for i in 0..2548 { + assert!(b2548.contains(i)); + } + assert_eq!(b2548.count(), 2548); + assert_eq!(b2548.chunks(), vec![Ones(2048), Ones(500)]); + b2548.assert_valid(); + + //----------------------------------------------------------------------- + + let mut b4096 = ChunkedBitSet::::new_empty(4096); + assert_eq!( + b4096, + ChunkedBitSet { + domain_size: 4096, + chunks: Box::new([Zeros(2048), Zeros(2048)]), + marker: PhantomData, + } + ); + + b4096.assert_valid(); + for i in 0..4096 { + assert!(!b4096.contains(i)); + } + assert!(b4096.insert(0) && b4096.insert(4095) && !b4096.insert(4095)); + assert!( + b4096.contains(0) && !b4096.contains(2047) && !b4096.contains(2048) && b4096.contains(4095) + ); + assert_eq!( + b4096.chunks(), + #[rustfmt::skip] + vec![ + Mixed(2048, 1, Rc::new([ + 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 + ])), + Mixed(2048, 1, Rc::new([ + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0x8000_0000_0000_0000 + ])), + ], + ); + assert_eq!(b4096.count(), 2); + b4096.assert_valid(); + + //----------------------------------------------------------------------- + + let mut b10000 = ChunkedBitSet::::new_empty(10000); + assert_eq!( + b10000, + ChunkedBitSet { + domain_size: 10000, + chunks: Box::new([Zeros(2048), Zeros(2048), Zeros(2048), Zeros(2048), Zeros(1808),]), + marker: PhantomData, + } + ); + + b10000.assert_valid(); + assert!(b10000.insert(3000) && b10000.insert(5000)); + assert_eq!( + b10000.chunks(), + #[rustfmt::skip] + vec![ + Zeros(2048), + Mixed(2048, 1, Rc::new([ + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0x0100_0000_0000_0000, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + ])), + Mixed(2048, 1, Rc::new([ + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0x0100, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + ])), + Zeros(2048), + Zeros(1808), + ], + ); + let mut b10000b = ChunkedBitSet::::new_empty(10000); + b10000b.clone_from(&b10000); + assert_eq!(b10000, b10000b); + for i in 6000..7000 { + b10000b.insert(i); + } + assert_eq!(b10000b.count(), 1002); + b10000b.assert_valid(); + b10000b.clone_from(&b10000); + assert_eq!(b10000b.count(), 2); + for i in 2000..8000 { + b10000b.insert(i); + } + b10000.union(&b10000b); + assert_eq!(b10000.count(), 6000); + b10000.union(&b10000b); + assert_eq!(b10000.count(), 6000); + b10000.assert_valid(); + b10000b.assert_valid(); +} + +fn with_elements_chunked(elements: &[usize], domain_size: usize) -> ChunkedBitSet { + let mut s = ChunkedBitSet::new_empty(domain_size); + for &e in elements { + assert!(s.insert(e)); + } + s +} + +fn with_elements_standard(elements: &[usize], domain_size: usize) -> BitSet { + let mut s = BitSet::new_empty(domain_size); + for &e in elements { + assert!(s.insert(e)); + } + s +} + +#[test] +fn chunked_bitset_into_bitset_operations() { + let a = vec![1, 5, 7, 11, 15, 2000, 3000]; + let b = vec![3, 4, 11, 3000, 4000]; + let aub = vec![1, 3, 4, 5, 7, 11, 15, 2000, 3000, 4000]; + let aib = vec![11, 3000]; + + let b = with_elements_chunked(&b, 9876); + + let mut union = with_elements_standard(&a, 9876); + assert!(union.union(&b)); + assert!(!union.union(&b)); + assert!(union.iter().eq(aub.iter().copied())); + + let mut intersection = with_elements_standard(&a, 9876); + assert!(intersection.intersect(&b)); + assert!(!intersection.intersect(&b)); + assert!(intersection.iter().eq(aib.iter().copied())); +} + +#[test] +fn chunked_bitset_iter() { + fn check_iter(bit: &ChunkedBitSet, vec: &Vec) { + // Test collecting via both `.next()` and `.fold()` calls, to make sure both are correct + let mut collect_next = Vec::new(); + let mut bit_iter = bit.iter(); + while let Some(item) = bit_iter.next() { + collect_next.push(item); + } + assert_eq!(vec, &collect_next); + + let collect_fold = bit.iter().fold(Vec::new(), |mut v, item| { + v.push(item); + v + }); + assert_eq!(vec, &collect_fold); + } + + // Empty + let vec: Vec = Vec::new(); + let bit = with_elements_chunked(&vec, 9000); + check_iter(&bit, &vec); + + // Filled + let n = 10000; + let vec: Vec = (0..n).collect(); + let bit = with_elements_chunked(&vec, n); + check_iter(&bit, &vec); + + // Filled with trailing zeros + let n = 10000; + let vec: Vec = (0..n).collect(); + let bit = with_elements_chunked(&vec, 2 * n); + check_iter(&bit, &vec); + + // Mixed + let n = 12345; + let vec: Vec = vec![0, 1, 2, 2010, 2047, 2099, 6000, 6002, 6004]; + let bit = with_elements_chunked(&vec, n); + check_iter(&bit, &vec); +} + +#[test] +fn grow() { + let mut set: GrowableBitSet = GrowableBitSet::with_capacity(65); + for index in 0..65 { + assert!(set.insert(index)); + assert!(!set.insert(index)); + } + set.ensure(128); + + // Check if the bits set before growing are still set + for index in 0..65 { + assert!(set.contains(index)); + } + + // Check if the new bits are all un-set + for index in 65..128 { + assert!(!set.contains(index)); + } + + // Check that we can set all new bits without running out of bounds + for index in 65..128 { + assert!(set.insert(index)); + assert!(!set.insert(index)); + } +} + +#[test] +fn matrix_intersection() { + let mut matrix: BitMatrix = BitMatrix::new(200, 200); + + // (*) Elements reachable from both 2 and 65. + + matrix.insert(2, 3); + matrix.insert(2, 6); + matrix.insert(2, 10); // (*) + matrix.insert(2, 64); // (*) + matrix.insert(2, 65); + matrix.insert(2, 130); + matrix.insert(2, 160); // (*) + + matrix.insert(64, 133); + + matrix.insert(65, 2); + matrix.insert(65, 8); + matrix.insert(65, 10); // (*) + matrix.insert(65, 64); // (*) + matrix.insert(65, 68); + matrix.insert(65, 133); + matrix.insert(65, 160); // (*) + + let intersection = matrix.intersect_rows(2, 64); + assert!(intersection.is_empty()); + + let intersection = matrix.intersect_rows(2, 65); + assert_eq!(intersection, &[10, 64, 160]); +} + +#[test] +fn matrix_iter() { + let mut matrix: BitMatrix = BitMatrix::new(64, 100); + matrix.insert(3, 22); + matrix.insert(3, 75); + matrix.insert(2, 99); + matrix.insert(4, 0); + matrix.union_rows(3, 5); + matrix.insert_all_into_row(6); + + let expected = [99]; + let mut iter = expected.iter(); + for i in matrix.iter(2) { + let j = *iter.next().unwrap(); + assert_eq!(i, j); + } + assert!(iter.next().is_none()); + + let expected = [22, 75]; + let mut iter = expected.iter(); + assert_eq!(matrix.count(3), expected.len()); + for i in matrix.iter(3) { + let j = *iter.next().unwrap(); + assert_eq!(i, j); + } + assert!(iter.next().is_none()); + + let expected = [0]; + let mut iter = expected.iter(); + assert_eq!(matrix.count(4), expected.len()); + for i in matrix.iter(4) { + let j = *iter.next().unwrap(); + assert_eq!(i, j); + } + assert!(iter.next().is_none()); + + let expected = [22, 75]; + let mut iter = expected.iter(); + assert_eq!(matrix.count(5), expected.len()); + for i in matrix.iter(5) { + let j = *iter.next().unwrap(); + assert_eq!(i, j); + } + assert!(iter.next().is_none()); + + assert_eq!(matrix.count(6), 100); + let mut count = 0; + for (idx, i) in matrix.iter(6).enumerate() { + assert_eq!(idx, i); + count += 1; + } + assert_eq!(count, 100); + + if let Some(i) = matrix.iter(7).next() { + panic!("expected no elements in row, but contains element {:?}", i); + } +} + +#[test] +fn sparse_matrix_iter() { + let mut matrix: SparseBitMatrix = SparseBitMatrix::new(100); + matrix.insert(3, 22); + matrix.insert(3, 75); + matrix.insert(2, 99); + matrix.insert(4, 0); + matrix.union_rows(3, 5); + + let expected = [99]; + let mut iter = expected.iter(); + for i in matrix.iter(2) { + let j = *iter.next().unwrap(); + assert_eq!(i, j); + } + assert!(iter.next().is_none()); + + let expected = [22, 75]; + let mut iter = expected.iter(); + for i in matrix.iter(3) { + let j = *iter.next().unwrap(); + assert_eq!(i, j); + } + assert!(iter.next().is_none()); + + let expected = [0]; + let mut iter = expected.iter(); + for i in matrix.iter(4) { + let j = *iter.next().unwrap(); + assert_eq!(i, j); + } + assert!(iter.next().is_none()); + + let expected = [22, 75]; + let mut iter = expected.iter(); + for i in matrix.iter(5) { + let j = *iter.next().unwrap(); + assert_eq!(i, j); + } + assert!(iter.next().is_none()); +} + +#[test] +fn sparse_matrix_operations() { + let mut matrix: SparseBitMatrix = SparseBitMatrix::new(100); + matrix.insert(3, 22); + matrix.insert(3, 75); + matrix.insert(2, 99); + matrix.insert(4, 0); + + let mut disjoint: HybridBitSet = HybridBitSet::new_empty(100); + disjoint.insert(33); + + let mut superset = HybridBitSet::new_empty(100); + superset.insert(22); + superset.insert(75); + superset.insert(33); + + let mut subset = HybridBitSet::new_empty(100); + subset.insert(22); + + // SparseBitMatrix::remove + { + let mut matrix = matrix.clone(); + matrix.remove(3, 22); + assert!(!matrix.row(3).unwrap().contains(22)); + matrix.remove(0, 0); + assert!(matrix.row(0).is_none()); + } + + // SparseBitMatrix::clear + { + let mut matrix = matrix.clone(); + matrix.clear(3); + assert!(!matrix.row(3).unwrap().contains(75)); + matrix.clear(0); + assert!(matrix.row(0).is_none()); + } + + // SparseBitMatrix::intersect_row + { + let mut matrix = matrix.clone(); + assert!(!matrix.intersect_row(3, &superset)); + assert!(matrix.intersect_row(3, &subset)); + matrix.intersect_row(0, &disjoint); + assert!(matrix.row(0).is_none()); + } + + // SparseBitMatrix::subtract_row + { + let mut matrix = matrix.clone(); + assert!(!matrix.subtract_row(3, &disjoint)); + assert!(matrix.subtract_row(3, &subset)); + assert!(matrix.subtract_row(3, &superset)); + matrix.intersect_row(0, &disjoint); + assert!(matrix.row(0).is_none()); + } + + // SparseBitMatrix::union_row + { + let mut matrix = matrix.clone(); + assert!(!matrix.union_row(3, &subset)); + assert!(matrix.union_row(3, &disjoint)); + matrix.union_row(0, &disjoint); + assert!(matrix.row(0).is_some()); + } +} + +#[test] +fn dense_insert_range() { + #[track_caller] + fn check(domain: usize, range: R) + where + R: RangeBounds + Clone + IntoIterator + std::fmt::Debug, + { + let mut set = BitSet::new_empty(domain); + set.insert_range(range.clone()); + for i in set.iter() { + assert!(range.contains(&i)); + } + for i in range.clone() { + assert!(set.contains(i), "{} in {:?}, inserted {:?}", i, set, range); + } + } + check(300, 10..10); + check(300, WORD_BITS..WORD_BITS * 2); + check(300, WORD_BITS - 1..WORD_BITS * 2); + check(300, WORD_BITS - 1..WORD_BITS); + check(300, 10..100); + check(300, 10..30); + check(300, 0..5); + check(300, 0..250); + check(300, 200..250); + + check(300, 10..=10); + check(300, WORD_BITS..=WORD_BITS * 2); + check(300, WORD_BITS - 1..=WORD_BITS * 2); + check(300, WORD_BITS - 1..=WORD_BITS); + check(300, 10..=100); + check(300, 10..=30); + check(300, 0..=5); + check(300, 0..=250); + check(300, 200..=250); + + for i in 0..WORD_BITS * 2 { + for j in i..WORD_BITS * 2 { + check(WORD_BITS * 2, i..j); + check(WORD_BITS * 2, i..=j); + check(300, i..j); + check(300, i..=j); + } + } +} + +#[test] +fn dense_last_set_before() { + fn easy(set: &BitSet, needle: impl RangeBounds) -> Option { + let mut last_leq = None; + for e in set.iter() { + if needle.contains(&e) { + last_leq = Some(e); + } + } + last_leq + } + + #[track_caller] + fn cmp(set: &BitSet, needle: impl RangeBounds + Clone + std::fmt::Debug) { + assert_eq!( + set.last_set_in(needle.clone()), + easy(set, needle.clone()), + "{:?} in {:?}", + needle, + set + ); + } + let mut set = BitSet::new_empty(300); + cmp(&set, 50..=50); + set.insert(WORD_BITS); + cmp(&set, WORD_BITS..=WORD_BITS); + set.insert(WORD_BITS - 1); + cmp(&set, 0..=WORD_BITS - 1); + cmp(&set, 0..=5); + cmp(&set, 10..100); + set.insert(100); + cmp(&set, 100..110); + cmp(&set, 99..100); + cmp(&set, 99..=100); + + for i in 0..=WORD_BITS * 2 { + for j in i..=WORD_BITS * 2 { + for k in 0..WORD_BITS * 2 { + let mut set = BitSet::new_empty(300); + cmp(&set, i..j); + cmp(&set, i..=j); + set.insert(k); + cmp(&set, i..j); + cmp(&set, i..=j); + } + } + } +} + +/// Merge dense hybrid set into empty sparse hybrid set. +#[bench] +fn union_hybrid_sparse_empty_to_dense(b: &mut Bencher) { + let mut pre_dense: HybridBitSet = HybridBitSet::new_empty(256); + for i in 0..10 { + assert!(pre_dense.insert(i)); + } + let pre_sparse: HybridBitSet = HybridBitSet::new_empty(256); + b.iter(|| { + let dense = pre_dense.clone(); + let mut sparse = pre_sparse.clone(); + sparse.union(&dense); + }) +} + +/// Merge dense hybrid set into full hybrid set with same indices. +#[bench] +fn union_hybrid_sparse_full_to_dense(b: &mut Bencher) { + let mut pre_dense: HybridBitSet = HybridBitSet::new_empty(256); + for i in 0..10 { + assert!(pre_dense.insert(i)); + } + let mut pre_sparse: HybridBitSet = HybridBitSet::new_empty(256); + for i in 0..SPARSE_MAX { + assert!(pre_sparse.insert(i)); + } + b.iter(|| { + let dense = pre_dense.clone(); + let mut sparse = pre_sparse.clone(); + sparse.union(&dense); + }) +} + +/// Merge dense hybrid set into full hybrid set with indices over the whole domain. +#[bench] +fn union_hybrid_sparse_domain_to_dense(b: &mut Bencher) { + let mut pre_dense: HybridBitSet = HybridBitSet::new_empty(SPARSE_MAX * 64); + for i in 0..10 { + assert!(pre_dense.insert(i)); + } + let mut pre_sparse: HybridBitSet = HybridBitSet::new_empty(SPARSE_MAX * 64); + for i in 0..SPARSE_MAX { + assert!(pre_sparse.insert(i * 64)); + } + b.iter(|| { + let dense = pre_dense.clone(); + let mut sparse = pre_sparse.clone(); + sparse.union(&dense); + }) +} + +/// Merge dense hybrid set into empty hybrid set where the domain is very small. +#[bench] +fn union_hybrid_sparse_empty_small_domain(b: &mut Bencher) { + let mut pre_dense: HybridBitSet = HybridBitSet::new_empty(SPARSE_MAX); + for i in 0..SPARSE_MAX { + assert!(pre_dense.insert(i)); + } + let pre_sparse: HybridBitSet = HybridBitSet::new_empty(SPARSE_MAX); + b.iter(|| { + let dense = pre_dense.clone(); + let mut sparse = pre_sparse.clone(); + sparse.union(&dense); + }) +} + +/// Merge dense hybrid set into full hybrid set where the domain is very small. +#[bench] +fn union_hybrid_sparse_full_small_domain(b: &mut Bencher) { + let mut pre_dense: HybridBitSet = HybridBitSet::new_empty(SPARSE_MAX); + for i in 0..SPARSE_MAX { + assert!(pre_dense.insert(i)); + } + let mut pre_sparse: HybridBitSet = HybridBitSet::new_empty(SPARSE_MAX); + for i in 0..SPARSE_MAX { + assert!(pre_sparse.insert(i)); + } + b.iter(|| { + let dense = pre_dense.clone(); + let mut sparse = pre_sparse.clone(); + sparse.union(&dense); + }) +} + +#[bench] +fn bench_insert(b: &mut Bencher) { + let mut bs = BitSet::new_filled(99999usize); + b.iter(|| { + black_box(bs.insert(black_box(100u32))); + }); +} + +#[bench] +fn bench_remove(b: &mut Bencher) { + let mut bs = BitSet::new_filled(99999usize); + b.iter(|| { + black_box(bs.remove(black_box(100u32))); + }); +} + +#[bench] +fn bench_iter(b: &mut Bencher) { + let bs = BitSet::new_filled(99999usize); + b.iter(|| { + bs.iter().map(|b: usize| black_box(b)).for_each(drop); + }); +} + +#[bench] +fn bench_intersect(b: &mut Bencher) { + let mut ba: BitSet = BitSet::new_filled(99999usize); + let bb = BitSet::new_filled(99999usize); + b.iter(|| { + ba.intersect(black_box(&bb)); + }); +} -- cgit v1.2.3